The Beginner's Guide to qMultiSum

Axel Riese

Research Institute for Symbolic Computation
J. Kepler University Linz
A–4040 Linz, Austria

February 21, 2005

Introduction

This notebook accompanies my Mathematica package qMultiSum, an implementation for computing recurrences for q–hypergeometric multiple sums. Its purpose is to introduce the usage of the package to new users. To this end we will prove together a certain identity step by step. However, I assume that the reader is familiar with the basic notions of q–hypergeometric functions and to some extent with Mathematica, too.

More detailed information both on the theoretical background and on the implementation can be found in the paper

Axel Riese,  qMultiSum — A Package for Proving q–Hypergeometric Multiple Summation Identities, J. Symbolic Comput., 35 (2003), 349—376.

This paper, as well as the latest version of the implementation, is available also at the qMultiSum homepage at

http://www.risc.uni–linz.ac.at/research/combinat/software/qMultiSum

Please take part in the development of the package by sending your feedback, comments, questions, bug reports, etc. to

Axel.Riese@risc.uni–linz.ac.at

An Example

The application we are considering here is the double–sum case of the well–known q–multinomial theorem in the form

(Underscript[(∑_(i≥0,j≥0)), i+j≤n])(((Subscript[(x;q), i])(Subscript[(y;q), j])(Subscript[(z;q), n-i-j]))/((Subscript[(q;q), i])(Subscript[(q;q), j])(Subscript[(q;q), n-i-j])))(y^i)(z^(i+j))=((Subscript[(x y z;q), n])/(Subscript[(q;q), n])).

We will prove this identity by computing a linear recurrence in n with q–polynomial coefficients for the left–hand side and showing that the right–hand side satisfies the same recurrence.

Loading the Package

First of all we have to load the package. Make sure that you substitute the correct path to qMultiSum.m in the following command.

<<RISC`qMultiSum`

qMultiSum Package version 2.53
written by Axel Riese
Copyright 1995-2010, Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Defining the Summand

The summand can be entered as follows:

summand=((qPochhammer[x,q,i] qPochhammer[y,q,j] qPochhammer[z,q,n-i-j](y^i) (z^(i+j)))/(qPochhammer[q,q,i] qPochhammer[q,q,j] qPochhammer[q,q,n-i-j]))

Computing a Recurrence for the Summand

In the first step we compute a recurrence for the summand by using Wilf and Zeilberger's q–multivariate generalization of Sister Celine's technique together with ideas of Verbaeten, Wegschaider, and Zimmermann. Note that this is the most difficult step from the user's point of view, because in general we don't know where such recurrences live. More precisely, we don't know in advance the so–called structure set S for which our summand, say F(n,i,j), satisfies

(∑_((a,b,c)∈S))(Subscript[σ, a,b,c])(n)F(n-a,i-b,j-c)=0,

where the (Subscript[σ, a,b,c]) are polynomials in (q^n), not all zero, and S is a finite set of integer triples. Hence we will proceed by trial and error.

First of all, let us have a look at the underlying functions qFindStructureSet[] and qFindRecurrence[]:

?qFindStructureSet

?qFindRecurrence

Here F is our summand, the recurrence variable (of the sum) is (Subscript[n, 1])=n, the summation variables are (Subscript[k, 1])=i and (Subscript[k, 2])=j, and we try first with (Subscript[deg, 1])=(Subscript[deg, 2])=0, i.e. we compute a recurrence where the coefficients do not depend on the summation variables as shown above (a generalization of this method will be described below).

The main task now is to find a good choice of the dimensions (Subscript[ndim, 1]), (Subscript[kdim, 1]) and (Subscript[kdim, 2]) of our initial structure set. This means that we start with the rectangular structure set  S={(a,b,c)∈(ℕ^3)|0≤a≤(Subscript[ndim, 1]),0≤b≤(Subscript[kdim, 1]),0≤c≤(Subscript[kdim, 2])}. To this set our program then adds by a procedure called Verbaeten completion certain other points in a rather sophisticated way. Finally, if the completed set contains a subset over which a recurrence exists, a randomized procedure quickly determines this set with very high probability. For more details the interested reader is referred to the paper mentioned above. Note that beginning with version 2.49 it is no longer necessary to specify NumericCheck->True, since this is the default now.

Most likely there exists a recurrence for the initial structure set of dimension 1000×1000×1000, but with this choice we will immediately run out of memory, and therefore I cannot recommend this kind of approach. Even worse, the run–time increases rather quickly with the size of S. Hence one should always try to keep the structure set small.

Why not starting with the smallest possible structure set? To see what's going on we also set the option qProtocol to True:

qFindStructureSet[summand,{n},{i,j},{0},{0,0},qProtocol->True]

Well, for a one–element structure set (note that Verbaeten completion did nothing here) it's not very surprising that we did not succeed. So let us increase the dimensions a bit:

qFindStructureSet[summand,{n},{i,j},{1},{0,0},qProtocol->True]

Bad luck again (Verbaeten completion again did nothing)...

qFindStructureSet[summand,{n},{i,j},{1},{1,0},qProtocol->True]

...and again (although Verbaeten completion now entered the game)...

qFindStructureSet[summand,{n},{i,j},{1},{1,1},qProtocol->True]

Yeah, great. At least for this simple example our brute–force strategy worked. Now we may compute a recurrence.

rec=qFindRecurrence[summand,{n},{i,j},{1},{1,1},qProtocol->True, StructSet->%[[1]]]

Computing a Recurrence for the Sum

Once we have found a recurrence for the summand, its transformation into a recurrence for the sum is easy provided that we have standard boundary conditions. The corresponding function is called qSumRecurrence[].

?qSumRecurrence

sumrec=qSumRecurrence[rec]

Checking the Closed Form

To complete the proof of our identity it remains to check that the right–hand side satisfies the same recurrence. This can be done with the help of the function qCheckRecurrence[].

?qCheckRecurrence

qCheckRecurrence[sumrec,((qPochhammer[x y z,q,n])/(qPochhammer[q,q,n]))]

What remains to do is to show that our identity holds for n∈{0,1,2}.

Spin–Offs

In the example above we have computed a recurrence for the summand in which the coefficients do not depend on the summation variables. However, one may relax this restriction a bit (again I omit the details here). As Kurt Wegschaider observed in the q=1 case, structure sets for recurrences depending on the summation variables are in many cases considerably smaller.

To illustrate this, let us compute a recurrence for the summand in which the coefficients may depend on  (q^j) (but not on (q^i) or (q^(2j)), for instance). This can be done by calling qFindStructureSet[] with (Subscript[deg, 1])=0 and (Subscript[deg, 2])=1.

qFindStructureSet[summand,{n},{i,j},{1},{1,1},{0,1},qProtocol->True]

From this we see that there indeed exists a recurrence over a structure set with only six elements, namely:

newrec=qFindRecurrence[summand,{n},{i,j},{0},{1,1},{0,1},qProtocol->True,StructSet->%[[1]]]

qSumRecurrence[newrec]

At least we could decrease the order of the sum–recurrence from 3 to 2. However, it seems that Sister Celine's method misses the minimal order 1 recurrence for this sum.