Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory

Moa APAGODU^{1} and Doron ZEILBERGER ^{1}

Dedicated to Amitai Regev (b. Dec. 7, 1940)

Amitai Regev and Integrals and Sums

Superficially, this article, dedicated with friendship and admiration to Amitai Regev, has nothing to do with either Polynomial Identity Rings, Representation Theory, or Young tableaux, to all of which he made so many outstanding contributions. But anyone who knows even a little about Amitai Regev’s remarkable and versatile research, would know that both sums (and multi-sums!), and especially integrals (and multi-integrals!) show up very frequently, e.g. see [R], where one of us (DZ) collaborated in the apppendix that consisted in an explicit evaluation of a certain multi-integral. We should also mention that back in the early eighties, Amitai, together with William Beckner [BR], deduced the then wide-open Macdonald-Mehta conjecture for the classical root systems B-D from Selberg’s integral, a fact that was acknowledged in [M] (albeit with characteristic Macdonaldian understatement). Hence, it is clear that sums, multisums, integrals, and multi-integrals, are Amitai’s bread and butter, and also cup of tea, so the present work has the potential to help him in his future research.

A Multi-Variable Zeilberger Algorithm

Notation. For k integer, (z)_{k} := z(z + 1) … (z + k − 1), if k ≥ 0 and (z)_{k} := 1/(z + k)_{−k} if k < 0. In order to avoid too many subscripts in this article, we will denote (z)_{k} by RF (z , k). For any polynomial in (k_{1}, …, k_{r}) and possibly other variables, deg(f) denotes the total degree w.r.t. (k_{1}, …, k_{r}).

Theorem mZ. Let

F (n; k_{1}, …, k_{r}) = P OL(n; k_{1}, …, k_{r}) · H(n; k_{1}, …, k_{r}) , (MultiP roperHypergeometric)

where P OL(n; k_{1}, …, k_{r}) is a polynomial in (n, k_{1}, …, k_{r}) and

H(n; k_{1}, …, k_{r}) = \frac{∏_{j=1}^{A} RF (a′′_{j} , a′_{j}n + ∑_{i=1}^{r} a_{ji}k_{i})}{∏_{j=1}^{C} RF (c′′_{j} , c′_{j}n + ∑_{i=1}^{r} c_{ji}k_{i})} ∏_{i=1}^{r} z_{i}^{k_{i}} , (MultiP ureHypergeometric)

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. [mohamudm, zeilberg] at math dot rutgers dot edu , http://www.math.rutgers.edu/~[mohamudm, zeilberg]/.

First version: Dec. 8, 2004. This version: Sept. 7, 2005. Accompanied by Maple packages: MultiZeilberger, MultiZeilbergerDen, qMultiZeilberger, MultiAlmkvistZeilberger, and SMAZ, available from http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html. Supported in part by the NSF.

The former name (changed Aug. 2005) of M. Apagodu was M. Mohammed.

where the a′_{j}, c′_{j} are non-negative integers and the a_{ji}, c_{ji} are integers, while a′′_{j}, c′′_{j} and z_{1}, …, z_{r} are commuting indeterminates. Then there exists an integer L, to be explicitly constructed in the course of the proof, and there exist polynomials in n, e_{0}(n), e_{1}(n), …, e_{L}(n), not all zero, and there also exist r rational functions of (n, k_{1}, …, k_{r}), R_{i}(n; k_{1}, …, k_{r}) (i = 1, …, r), such that

G_{i}(n; k_{1}, …, k_{r}) := R_{i}(n; k_{1}, …, k_{r})F (n; k_{1}, …, k_{r})

satisfy

∑_{i=0}^{L} e_{i}(n)F (n+i, k) = ∑_{i=1}^{r}[G_{i}(n; k_{1}, …, k_{i−1}, k_{i}+1, k_{i+1}, …, k_{r})−G_{i}(n; k_{1}, …, k_{r})] . (W Ztuple)

Proof. Let

\overline{H}(n; k_{1}, …, k_{r}) = \frac{∏_{j=1}^{A} RF (a′′_{j} , a′_{j}n + ∑_{i=1}^{r} a_{ji}k_{i})}{∏_{j=1}^{C} RF (c′′_{j} , c′_{j}(n + L) + ∑_{i=1}^{r} c_{ji}k_{i})} ∏_{i=1}^{r} z_{i}^{k_{i}} ,

and for i = 1, …, r,

f_{i}(k_{1}, …, k_{r}) = ∏_{{1≤j≤A \atop a_{ji}>0}} RF (a′_{j}n+a′′_{j}+∑_{i=1}^{r} a_{ji}k_{i} , a_{ji}) ∏_{{1≤j≤C \atop c_{ji}<0}} RF (c′_{j}(n+L)+c′′_{j}+c_{ji}+∑_{i=1}^{r} c_{ji}k_{i} , −c_{ji}) ,

and

g_{i}(k_{1}, …, k_{r}) = ∏_{{1≤j≤A \atop a_{ji}<0}} RF (a′_{j}n+a′′_{j}+a_{ji}+∑_{i=1}^{r} a_{ji}k_{i} , −a_{ji}) ∏_{{1≤j≤C \atop c_{ji}>0}} RF (c′_{j}(n+L)+c′′_{j}+∑_{i=1}^{r} c_{ji}k_{i} , c_{ji}) .

Note that

\frac{\overline{H}(n; k_{1}, …, k_{i−1}, k_{i} + 1, k_{i+1}, ⋯, k_{r})}{\overline{H}(n; k_{1}, …, k_{r})} = \frac{f_{i}(k_{1}, …, k_{r})}{g_{i}(k_{1}, …, k_{r})}z_{i} .

Write

G_{i}(n, k) := g_{i}(k_{1}, …, k_{i−1}, k_{i} − 1, k_{i+1}, …, k_{r}) · X_{i}(k_{1}, …, k_{r}) · \overline{H}(n; k_{1}, …, k_{r}) · (Ansatz)

Substituting into (W Ztuple) and dividing both sides by \overline{H}(n; k_{1}, …, k_{r}), shows that it is equivalent to

∑_{i=1}^{r}[z_{i}·f_{i}(k_{1}, …, k_{r})X_{i}(k_{1}, …, k_{i−1}, k_{i}+1, k_{i+1}, …, k_{r})−g_{i}(k_{1}, …, k_{i−1}, k_{i}−1, k_{i+1}, …, k_{r})X_{i}(k_{1}, …, k_{r})]

− h(k_{1}, …, k_{r}) = 0 ,  (MultiGosper)

where

h(k_{1}, …, k_{r}) := ∑_{i=0}^{L} e_{i}(n)P OL(n + i; k_{1}, …, k_{r}) · \frac{H(n + i; k_{1}, …, k_{r})}{\overline{H}(n; k_{1}, …, k_{r})} .

Note that h(k_{1}, …, k_{r}) is a polynomial since

\frac{H(n + i; k_{1}, …, k_{r})}{\overline{H}(n; k_{1}, …, k_{r})} = ∏_{j=1}^{A} RF (a′′_{j}+a′_{j}n+∑_{i=1}^{r} a_{ji}k_{i} , ia′_{j}) ∏_{j=1}^{C} RF (c′′_{j}+c′_{j}(n+i)+∑_{i=1}^{r} c_{ji}k_{i} , (L−i)c′_{j}) .

Now write each of the X_{i}’s in generic form, with undetermined coefficients, as polynomials in k_{1}, …, k_{r} of degree M := deg(h) − max({deg(f_{i}), deg(g_{i})}). Plug them all into (MultiGosper), expand this gigantic polynomial of k_{1}, …, k_{r}, and equate all the coefficients to zero, getting a huge system of linear homogeneous equations whose unknowns are the e_{i}(n)’s and the coefficients of the X_{i}’s. There are r\binom{M+r}{r}+L+1 unknowns and \binom{deg(h)+r}{r} equations. In order to guarantee a not-all-zero solution we must insist that #unknowns>#equations. So choose L to be the smallest integer such that

r\binom{M + r}{r} + L + 1 > \binom{deg(h) + r}{r} ,

in other words

L ≥ \binom{deg(h) + r}{r} − r\binom{M + r}{r} .

We will now show that such an L exists. Indeed,

deg(h) = deg(P OL) + L · max(∑_{j=1}^{A} a′_{j}, ∑_{j=1}^{C} c′_{j}) = b_{0} + b_{1}L ,

for some specific positive integers b_{0}, b_{1}. Also

b_{2} := max({deg(f_{i}), deg(g_{i})})

is some specific positive integer (independent of L). We need to find an L such that

r\binom{b_{0} + b_{1}L − b_{2} + r}{r} − \binom{b_{0} + b_{1}L + r}{r} + L ≥ 0 .

For r = 1 we get that L = b_{2} will do, and for r > 1 the left side is a polynomial of L of degree r with a leading coefficient that is positive, hence tends to ∞ when L → ∞, Hence the inequality holds for sufficiently large L, and the smallest such L is our desired (sharp!) upper bound.

However, so far, we only ruled out the scenario that all the e_{i}(n)’s and all the X_{i}’s are all equal to 0. Can it happen that all the e_{i}(n)’s are equal to 0? No way! We are doing things generically, in particular with generic z_{i}’s, and if all the e_{i}(n)’s are zero, they would have to be identically zero as a function of the z_{i}’s and all the other generic (symbolic) parameters a′′_{j} etc. In particular if we make all the z_{i}’s zero except for a single one, reducing the multi-sum to a single sum, then all the e_{i}(n)’s would still have to be identically zero. This scenario has been ruled out in [MZ]. .

Remark 1. The condition that the a′_{j}’s and c′_{j}’s are non-negative integers is w.l.o.g., since one can obtain an equivalent summand with these properties by shadowing (see [MZ]).

Remark 2. Theorem mZ is both of theoretical and practical interest. The former because it considerably improves the upper bound for the order of the recurrence established in [WZ]. The latter since it gives an efficient algorithm for computing recurrences, superseding the ad-hoc pseudo algorithm that accompanied [WZ].

Remark 3. In specific situations (as opposed to the generic case), one may be able to get a smaller L, by taking the X_{i}’s to be rational functions, rather than mere polynomials. This is implemented in the Maple package MultiZeilbergerDen, where the user is allowed to pick the denominators.

A Multi-Variable q-Zeilberger Algorithm

q-Notation. For k integer, [a]_{k} := (1−q^{a})(1−q^{a+1}) ⋯ (1−q^{a+k−1}), if k ≥ 0 and [a]_{k} := 1/[a+k]_{−k} if k < 0. In order to avoid too many subscripts, we will denote [a]_{k} by qRF (a , k).

Theorem qmZ. Let

F (n; k_{1}, …, k_{r}) = P OL(n; k_{1}, …, k_{r}) · H(n; k_{1}, …, k_{r}) , (qMultiP roperHypergeometric)

where P OL(n; k_{1}, …, k_{r}) is a Laurent polynomial in (q^{n}, q^{k_{1}}, …, q^{k_{r}}), and

H(n; k_{1}, …, k_{r}) = \frac{∏_{j=1}^{A} qRF (a′′_{j} , a′_{j}n + ∑_{i=1}^{r} a_{ji}k_{i})}{∏_{j=1}^{C} qRF (c′′_{j} , c′_{j}n + ∑_{i=1}^{r} c_{ji}k_{i})} · q^{Q(n;k_{1},...,k_{r})} · ∏_{i=1}^{r} z_{i}^{k_{i}} ,

(qMultiP ureHypergeometric)

where the a′_{j}, c′_{j} are non-negative integers and the a_{ji}, c_{ji} are integers, while a′′_{j}, c′′_{j} and z_{1}, …, z_{r} are commuting indeterminates, and Q(n; k_{1}, …, k_{r}) is a quadratic form in (n, k_{1}, …, k_{r}). Then there exists an integer L, to be explicitly constructed in the course of the proof, and there exist L+1 polynomials in q^{n}, e_{0}(q^{n}), e_{1}(q^{n}), …, e_{L}(q^{n}), not all zero, and r rational functions of (q^{n}, q^{k_{1}}, …, q^{k_{r}}), R_{i}(n; k_{1}, …, k_{r}) (i = 1, …, r) such that

G_{i}(n; k_{1}, …, k_{r}) := R_{i}(n; k_{1}, …, k_{r})F (n; k_{1}, …, k_{r})

satisfy

∑_{i=0}^{L} e_{i}(q^{n})F (n + i, k) = ∑_{i=1}^{r}[G_{i}(n; k_{1}, …, k_{i−1}, k_{i} + 1, k_{i+1}, …, k_{r}) − G_{i}(n; k_{1}, …, k_{r})] .

(qW Ztuple)

Plan of Proof: q-analogize the proof of Theorem mZ, in the same way as it was carried out for the single-sum case in [MZ].

Remark 4. In many cases one can get a lower order, L, for the recurrence satisfied by the sum a(n) := ∑_{k} F (n; k) , by replacing F (n; k) , by its Paule Symmetrization [P] (adapted to many variables).

Sharp Upper Bounds for the Almkvist-Zeilberger Algorithm

This section is a discrete-continuous analog of [MZ]. It simplifies (part of) [AZ], and provides a sharp upper bound for the order of the outputted recurrence.

Notation. If f is function of the continuous variable x (among possibly other continuous and/or discrete variables), then D_{x}f denotes the derivative of f with respect to x, in other words D_{x}f := \frac{∂f}{∂x}.

Theorem AZ. Let

F (n, x) = P OL(n, x) · H(n, x) ,  (DiscreteContHypergeometric)

where P OL(n, x) is a polynomial of (n, x), and

H(n, x) = e^{a(x)/b(x)} · (∏_{p=1}^{P} S_{p}(x)^{α_{p}}) · (\frac{s(x)}{t(x)})^{n} ,  (P ureDiscreteContHypergeometric)

where a(x), b(x), s(x), t(x) and S_{p}(x) (1 ≤ p ≤ P) are polynomials of x, while the α_{p}’s are commuting indeterminates. Let

L = deg(b) + deg(s) + deg(t) + (∑_{p=1}^{P} deg(S_{p})) + max(deg(a), deg(b)) − 1 ,

then there exist L+1 polynomials in n, e_{0}(n), e_{1}(n), …, e_{L}(n), not all zero, and a rational function R(n, x) such that G(n, x) := R(n, x)F (n, x) satisfies

∑_{i=0}^{L} e_{i}(n)F (n + i, x) = D_{x}G(n, x) .  (GertDoron)

If F (n, α) = 0 and F (n, β) = 0 (and hence G(n, α) = 0 and G(n, β) = 0), it follows, by integrating from x = α to x = β that

a(n) := ∫_{α}^{β} F (n, x)dx ,

satisfies the linear recurrence equation with polynomial coefficients

∑_{i=0}^{L} e_{i}(n)a(n + i) = 0 .

Proof: Let L, for now, be any non-negative integer. Let

\overline{H}(n, x) = e^{a(x)/b(x)} · (∏_{p=1}^{P} S_{p}(x)^{α_{p}}) · \frac{s(x)^{n}}{t(x)^{n+L}} .

We have

∑_{i=0}^{L} e_{i}(n)F (n + i, x) = h(x) · \overline{H}(n, x) ,

where

h(x) := ∑_{i=0}^{L} e_{i}(n)P OL(n + i, x)s(x)^{i}t(x)^{L−i} .

Let q(x) and r(x) be the numerator and denominator, respectively, of the logarithmic derivative of \overline{H}(n, x), i.e.

\frac{D_{x}\overline{H}(n, x)}{\overline{H}(n, x)} = \frac{q(x)}{r(x)} .

Write

G(n, x) = \overline{H}(n, x) · r(x) · X(x) ,  (Ansatz)

where X(x) is a polynomial to be determined. Now (GertDoron) is equivalent to

(r′(x) + q(x)) · X(x) + r(x)X′(x) = h(x) .  (ContGosper)

Let M := deg(h) − max(deg(r′ + q), deg(r) − 1), and write X(x) as a polynomial in x of degree M with undetermined coefficients. Plugging this into (ContGosper), and equating coefficients, results in deg(h) + 1 equations for L + M + 2 unknowns. In order to guarantee a solution, we need

L + M + 2 > deg(h) + 1 ,

in other words

(L + M + 2) − (deg(h) + 1) ≥ 0 ,

in other words,

L ≥ max(deg(r′ + q), deg(r) − 1) .

We leave it to the reader to verify that the expression on the right is indeed

L = deg(b) + deg(s) + deg(t) + (∑_{p=1}^{P} deg(S_{p})) + max(deg(a), deg(b)) − 1 .

A Multi-Variable Almkvist-Zeilberger Algorithm

The above theorem, and algorithm, can be extended to many variables as follows.

Theorem mAZ. Let

F (n; x_{1}, …, x_{d}) = P OL(n; x_{1}, …, x_{d}) · H(n; x_{1}, …, x_{d}) ,
(MultiDiscreteContHypergeometric)

where P OL(n; x_{1}, …, x_{d}) is a polynomial of (n, x_{1}, …, x_{d}), and

H(n; x_{1}, …, x_{d}) = e^{a(x_{1},...,x_{d})/b(x_{1},...,x_{d})} · (∏_{p=1}^{P} S_{p}(x_{1}, …, x_{d})^{α_{p}}) · (\frac{s(x_{1}, …, x_{d})}{t(x_{1}, …, x_{d})})^{n} ,

(P ureDiscreteContHypergeometric)

where a(x_{1}, …, x_{d}), b(x_{1}, …, x_{d}), s(x_{1}, …, x_{d}), t(x_{1}, …, x_{d}) and S_{p}(x_{1}, …, x_{d}) (1 ≤ p ≤ P) are polynomials of (x_{1}, …, x_{d}), while the α_{p}’s are commuting indeterminates. There exists a nonnegative integer L, to be constructed in the proof, and there exist L + 1 polynomials in n, e_{0}(n), e_{1}(n), …, e_{L}(n), not all zero, and there also exist d rational functions R_{i}(n; x_{1}, …, x_{d}) (i = 1, …, d) such that

G_{i}(n; x_{1}, …, x_{d}) := R_{i}(n; x_{1}, …, x_{d})F (n; x_{1}, …, x_{d})

satisfy

∑_{i=0}^{L} e_{i}(n)F (n + i; x_{1}, …, x_{d}) = ∑_{i=1}^{d} D_{x_{i}}G_{i}(n; x_{1}, …, x_{d}) .  (MultiGertDoron)

If F (n; ±∞) = 0 (and hence G(n; ±∞) = 0) it follows, by integrating over [−∞, ∞]^{d}, that

a(n) := ∫_{−∞}^{∞} … ∫_{−∞}^{∞} F (n; x_{1}, …, x_{d})dx_{1} … dx_{d} ,

satisfies the linear recurrence equation with polynomial coefficients

∑_{i=0}^{L} e_{i}(n)a(n + i) = 0 .

Sketch of Proof and Algorithm. Let L, for now, be any non-negative integer. Let

\overline{H}(n; x_{1}, …, x_{d}) = e^{a(x_{1},...,x_{d})/b(x_{1},...,x_{d})} · (∏_{p=1}^{P} S_{p}(x_{1}, …, x_{d})^{α_{p}}) · \frac{s(x_{1}, …, x_{d})^{n}}{t(x_{1}, …, x_{d})^{n+L}} .

We have

∑_{i=0}^{L} e_{i}(n)F (n + i; x_{1}, …, x_{d}) = h(x_{1}, …, x_{d}) · \overline{H}(n; x_{1}, …, x_{d}) ,

where

h(x_{1}, …, x_{d}) := ∑_{i=0}^{L} e_{i}(n)P OL(n + i; x_{1}, …, x_{d})s(x_{1}, …, x_{d})^{i}t(x_{1}, …, x_{d})^{L−i} .

For i = 1, …, d, let q_{i}(x_{1}, …, x_{d}) and r_{i}(x_{1}, ….x_{d}) be the numerator and denominator, respectively, of the logarithmic derivative of \overline{H}(n; x_{1}, …, x_{d}) w.r.t. x_{i}:

\frac{D_{x_{i}} \overline{H}(n; x_{1}, …, x_{d})}{\overline{H}(n; x_{1}, …, x_{d})} = \frac{q_{i}(x_{1}, …, x_{d})}{r_{i}(x_{1}, …, x_{d})} .

Write, for i = 1, …, d,

G_{i}(n; x_{1}, …, x_{d}) = \overline{H}(n; x_{1}, …, x_{d}) · r_{i}(x_{1}, …, x_{d}) · X_{i}(x_{1}, …, x_{d}) ,  (Ansatz)

where X_{i}(x_{1}, …, x_{d}) are polynomials to be determined. Now (MultiGertDoron) is equivalent to

∑_{i=1}^{d}[D_{x_{i}}r_{i}(x_{1}, …, x_{d}) + q_{i}(x_{1}, …, x_{d})] · X_{i}(x_{1}, …, x_{d}) + r_{i}(x_{1}, …, x_{d}) · D_{x_{i}}X_{i}(x_{1}, …, x_{d})

= h(x_{1}, …, x_{d}) .  (MultiContGosper)

The rest of the proof of the existence of L is analogous to the proof of Theorem mZ, since the degree of h is of the form “ integer+ (positive integer)·L”, and for sufficiently large L, the number of unknowns will exceed the number of equations, and we will be guaranteed a solution. Once again, by genericity, it is not possible for all the e_{i}(n)’s to be zero.

Remark 6. Theorem mAZ sharpens and improves on the work of Akalu Tefera[T], which, in turn, was a great improvement on the pseudo algorithm for multi-integration that accompanied [WZ].

Remark 7. In many cases in practice, one can reduce the order (L), by replacing (Ansatz) by

G_{i}(n; x_{1}, …, x_{d}) = \overline{H}(n; x_{1}, …, x_{d}) · X_{i}(x_{1}, …, x_{d}) ,  (Ansatz′)

in other words, not assuming that G_{i}/\overline{H} is divisible by r_{i}. This is how it is done in Mul-

tiAlmkvistZeilberger.

Differential Operators

Theorems cAZ and cmAZ below are analogs of AZ and mAZ that treat the case where the integrand’s arguments are all continuous, including the ‘parameter’ variable that is not being integrated on. In this case, of course, the output satisfies a linear differential equation with polynomial coefficients. Theorems cAZ and cmAZ are not yet implemented in Maple.

Theorem cAZ. Let

F (x, y) = P OL(x, y) · H(x, y)  (P ureContHypergeometric)

where P OL(x, y) is a polynomial of (x, y), and

H(x, y) = e^{\frac{a(x,y)}{b(x,y)}} · (∏_{p=1}^{P} S_{p}(x, y)^{α_{p}}) ,  (P ureContHypergeometric) ,

where a(x, y), b(x, y) and S_{p}(x, y) (1 ≤ p ≤ P) are polynomials of (x, y) while the α_{p} are commuting indeterminates.

Let

L := deg(b) + ∑_{p=1}^{P} deg(S_{p}) + max(deg(a), deg(b)) − 1 .

There exist L + 1 polynomials, e_{0}(x), e_{0}(x), …, e_{L}(x), not all zero, and rational function R(x, y) such that G(x, y) := R(x, y)F (x, y) satisfies

∑_{i=0}^{L} e_{i}(x)D_{x}^{i}F (x, y) = D_{x}G(x, y), .  (ContGertDoron)

If F (x, α) = 0 and F (x, β) = 0 (and hence G(x, α) = 0 and G(x, β) = 0), it follows, by integrating from y = α to y = β that

a(x) := ∫_{α}^{β} F (x, y)dy ,

satisfies the linear differential equation with polynomial coefficients

∑_{i=0}^{L} e_{i}(x)D_{x}^{i}a(x) = 0 .

Sketch of the Proof: The proof makes repeated use of Leibnitz rule together with induction. Let

\overline{H}(x, y) = \frac{e^{\frac{a(x,y)}{b(x,y)}}}{b(x, y)^{2L}} · (∏_{p=1}^{P} S_{p}(x, y)^{α_{p}−L}) .

We have

∑_{i=0}^{L} e_{i}(x)F (x, y) = h(x) · \overline{H}(x, y) ,

where h(x) is the expression

∑_{i=0}^{L} a_{i}(x) ∑_{{k_{1}+k_{2}+k_{3}=i \atop k_{i}≥0}} \binom{i}{k_{1}, k_{2}, k_{3}}(D_{x}^{k_{1}}P OL(x, y)) (∏_{p=1}^{P} S_{p}(x, y)^{L−k_{2}})·T_{k_{2}}(x, y)·b(x, y)^{2(L−k_{3})}·m_{k_{3}}(x, y) ,

where m_{k_{3}}(x, y) is a polynomial in (x, y) for which

D_{x}^{k_{2}} (∏_{p=1}^{P} S_{p}(x, y)^{α_{p}}) = (∏_{p=1}^{P} S_{p}(x, y)^{α_{p}−k_{2}}) · T_{k_{2}}(x, y) .

and T_{k_{3}}(x, y) is a polynomial in (x, y) such that

D_{x}^{k_{3}} (e^{a(x,y)/b(x,y)}) = \frac{m_{k_{3}}(x, y)}{b(x, y)^{2k_{3}}}e^{a(x,y)/b(x,y)} ,

respectively.

Let q(x) and r(x) be the numerator and denominator, respectively, of the logarithmic derivative of \overline{H}(x, y), i.e.

\frac{D_{x}\overline{H}(x, y)}{\overline{H}(x, y)} = \frac{q(x)}{r(x)} .

Write

G(x, y) = \overline{H}(x, y) · r(x) · X(x) ,  (Ansatz)

where X(x) is a polynomial to be determined. Now (ContGertDoron) is equivalent to

(r′(x) + q(x)) · X(x) + r(x)X′(x) = h(x) .  (ContGosper)

Let M := deg(h) − max(deg(r′ + q), deg(r) − 1), and write X(x) as a polynomial in x of degree M with undetermined coefficients. Plugging this into (ContGosper), and equating coefficients, results in deg(h) + 1 equations for L + M + 2 unknowns. In order to guarantee a solution, we need

L + M + 2 > deg(h) + 1 ,

in other words

(L + M + 2) − (deg(h) + 1) ≥ 0 ,

in other words,

L ≥ max(deg(r′ + q), deg(r) − 1) .

We leave it to the reader to verify that the expression on the right is indeed

L = deg(b) + max(deg(a), deg(b)) + (∑_{p=1}^{P} deg(S_{p})) − 1 .

Theorem cmAZ. Let

F (x; y_{1}, …, y_{d}) = P OL(x; y_{1}, …, y_{d}) · H(x; y_{1}, …, y_{d}) ,  (MultiContHypergeometric)

where P OL(x; y_{1}, …, y_{d}) is a polynomial of (x, y_{1}, …, y_{d}), and

H(x; y_{1}, …, y_{d}) = e^{a(x,y_{1},...,y_{d})/b(x,y_{1},...,y_{d})} · (∏_{p=1}^{P} S_{p}(x; y_{1}, …, y_{d})^{α_{p}}) ,

(MultiP ureContHypergeometric)

where a(y_{1}, …, y_{d}), b(y_{1}, …, y_{d}), S_{p}(y_{1}, …, y_{d}) (1 ≤ p ≤ P) are polynomials of (y_{1}, …, y_{d}), while the α_{p}’s are commuting indeterminates. There exists a non-negative integer L, to be constructed in the proof, and there exist L + 1 polynomials in x, e_{0}(x), e_{1}(x), …, e_{L}(x), not all zero, and there also exist d rational functions R_{i}(x; y_{1}, …, y_{d}) (i = 1, …, d) such that

G_{i}(x; y_{1}, …, y_{d}) := R_{i}(x; y_{1}, …, y_{d})F (x; y_{1}, …, y_{d})

satisfy

∑_{i=0}^{L} e_{i}(x)D_{x}^{i}F (x; y_{1}, …, y_{d}) = ∑_{i=1}^{d} D_{x_{i}}G_{i}(x; y_{1}, …, y_{d}) .  (MultiContGertDoron)

If F (x; ±∞) = 0 (and hence G(x; ±∞) = 0) it follows, by integrating over [−∞, ∞]^{d}, that

a(x) := ∫_{−∞}^{∞} … ∫_{−∞}^{∞} F (x; y_{1}, …, y_{d})dy_{1} … dy_{d} ,

satisfies the linear recurrence equation with polynomial coefficients

∑_{i=0}^{L} e_{i}(x)D_{x}^{i}a(x) = 0 .

Sketch of Proof and Algorithm. Let L, for now, be any non-negative integer. Let

\overline{H}(x; y_{1}, …, y_{d}) = \frac{e^{a(x;y_{1},...,y_{d})/b(x;y_{1},...,y_{d})}}{b(x; y_{1}, …, y_{d})^{2L}} · (∏_{p=1}^{P} S_{p}(x; y_{1}, …, y_{d})^{α_{p}}) .

We have

∑_{i=0}^{L} e_{i}(x)D_{x}^{i}F (x; y_{1}, …, y_{d}) = h(y_{1}, …, y_{d}) · \overline{H}(x; y_{1}, …, y_{d}) ,

where h(y_{1}, …, y_{d}) is the expression given by

∑_{i=0}^{L} a_{i}(x) ∑_{{k_{1}+k_{2}+k_{3}=i \atop k_{i}≥0}} \binom{i}{k_{1}, k_{2}, k_{3}}(D_{x}^{k_{1}}P OL(x; y_{1}, …, y_{d})) (∏_{p=1}^{P} S_{p}(x; y_{1}, …, y_{d})^{L−k_{2}})·T_{k_{2}}(x; y_{1}, …, y_{d})·

b(x; y_{1}, …, y_{d})^{2(L−k_{3})} · m_{k_{3}}(x; y_{1}, …, y_{d}) ,

where T_{k_{2}}(x; y_{1}, …, y_{d}) is a polynomial in (y_{1}, …, y_{d}) for which

D_{x}^{k_{2}} (∏_{p=1}^{P} S_{p}(x; y_{1}, …, y_{d})^{α_{p}}) = (∏_{p=1}^{P} S_{p}(x; y_{1}, …, y_{d})^{α_{p}−k_{2}}) · T_{k_{2}}(x; y_{1}, …, y_{d}) .

and m_{k_{3}}(x; y_{1}, …, y_{d}) is a polynomial in (x; y_{1}, …, y_{d}) such that

D_{x}^{k_{3}} (e^{a(x;y_{1},...,y_{d})/b(x;y_{1},...,y_{d})}) = \frac{m_{k_{3}}(x; y_{1}, …, y_{d})}{b(x; y_{1}, …, y_{d})^{2k_{3}}}e^{a(x;y_{1},...,y_{d})/b(x;y_{1},...,y_{d})} ,

respectively. For i = 1, …, d, let q_{i}(y_{1}, …, y_{d}) and r_{i}(y_{1}, ….y_{d}) be the numerator and denominator, respectively, of the logarithmic derivative of \overline{H}(x; y_{1}, …, y_{d}) w.r.t. y_{i}:

\frac{D_{y_{i}} \overline{H}(x; y_{1}, …, y_{d})}{\overline{H}(x; y_{1}, …, y_{d})} = \frac{q_{i}(y_{1}, …, y_{d})}{r_{i}(y_{1}, …, y_{d})} .

Write, for i = 1, …, d,

G_{i}(x; y_{1}, …, y_{d}) = \overline{H}(x; y_{1}, …, y_{d}) · r_{i}(y_{1}, …, y_{d}) · X_{i}(y_{1}, …, y_{d}) ,  (Ansatz)

where X_{i}(y_{1}, …, y_{d}) are polynomials to be determined. Now (MultiContGertDoron) is equivalent to

∑_{i=1}^{d}[D_{y_{i}}r_{i}(y_{1}, …, y_{d}) + q_{i}(y_{1}, …, y_{d})] · X_{i}(y_{1}, …, y_{d}) + r_{i}(y_{1}, …, y_{d}) · D_{y_{i}}X_{i}(y_{1}, …, y_{d})

= h(y_{1}, …, y_{d}) .  (MultiContGosper)

The rest of the proof of the existence of L is analogous to the proof of Theorem mAZ, since the degree of h is of the form “ integer+ (positive integer)·L”, and for sufficiently large L, the number of unknowns will exceed the number of equations, and we will be guaranteed a solution. Once again, by genericity, it is not possible for all the e_{i}(x)’s to be zero.

Accompanying Maple packages and Examples

The multi-Zeilberger algorithm, as described in Theorem mZ, is implemented in the Maple package multiZeilberger. The refined version, where the user is allowed to specify denominators, is given in MultiZeilbergerDen. The q-multi-Zeilberger algorithm, as stated in theorem qmZ, is implemented in the Maple package qMultiZeilberger, while the multi-Almkvist-Zeilberger algorithm, as described in Theorem mAZ, is contained in MultiAlmkvistZeilberger. Finally SMAZ is a more efficient rendition for symmetric integrands.

These five packages are available from the webpage of this article

http://www.math.rutgers.edu/~zeilberg/ mamarim/mamarimhtml/multiZ.html, where there

is also sample input and output. Readers can generate many more examples on their own.

REFERENCES

[AZ] G. Almkvist and D. Zeilberger, The method of differentiating under the integral sign, J. Symbolic Computation 10 (1990), 571-591.

[BR] W. Beckner and A. Regev, unpublished, untitled, and undated manuscript, c. 1980

[M] I.G. Macdonald, Some conjectures for root systems, SIAM J. Math. Anal. 13(1982), 988-1007.

[MZ] M. Mohammed and D. Zeilberger, Sharp Upper Bounds for the Orders of The Recurrences Outputted by the Zeilberger and q-Zeilberger Algorithms, J. Symbolic Computation 39 (2005), 201-207.

[P] P. Paule, Short and easy computer proofs of the Rogers-Ramanujan identities and of identities of similar type, Elect. J. of Combinatorics 1 (1994), R10.

[R] A. Regev, Combinatorial sums, identities and trace identities of the 2 × 2 matrices, Adv. in Math. 46 (1982), 230-240.

[T] A. Tefera, MultInt, a Maple Package for Multiple Integration by the WZ Method, J. of Symbolic Computation 34 (2002), 329-353.

[WZ] H.S. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and ”q”) multisum/integral identities, Invent. Math. 108 (1992), 575-633. [available on-line from the authors’ websites.]