Applicability of the q-Analogue of Zeilberger’s Algorithm

William Y.C. Chen^{1}, Qing-Hu Hou^{2} and Yan-Ping Mu^{3}

Center for Combinatorics, LPMC Nankai University, Tianjin 300071, P. R. China

E-mail: ^{1}chen@nankai.edu.cn, ^{2}qhhou@nankai.edu.cn, ^{3}myphb@eyou.com

Abstract

The applicability or terminating condition for the ordinary case of Zeilberger’s algorithm was recently obtained by Abramov. For the qanalogue, the question of whether a bivariate q-hypergeometric term has a qZ-pair remains open. Le has found a solution to this problem when the given bivariate q-hypergeometric term is a rational function in certain powers of q. We solve the problem for the general case by giving a characterization of bivariate q-hypergeometric terms for which the q-analogue of Zeilberger’s algorithm terminates. Moreover, we give an algorithm to determine whether a bivariate q-hypergeometric term has a qZ-pair.

AMS Classification: 33F10, 68W30

Keywords: Zeilberger’s algorithm, q-hypergeometric term, Z-pair, qZ-pair, proper hypergeometric term, q-proper hypergeometric term.

1 Introduction

Zeilberger’s algorithm [10,16,19], also known as the method of creative telescoping, is devised for proving hypergeometric identities of the form

∑_{k=−∞}^{∞} F (n, k) = f(n),

where F (n, k) is a bivariate hypergeometric term and f(n) is a given function (for most cases a hypergeometric term plus a constant). The algorithm can be easily adapted to the q-case, which is called the q-analogue of Zeilberger’s algorithm [7, 12, 15, 18]. Let N and K be the shift operators with respect to n and k respectively, defined by

NT (n, k) = T (n + 1, k)  and  KT (n, k) = T (n, k + 1).

Given a bivariate q-hypergeometric term T (n, k), the q-analogue of Zeilberger’s algorithm aims to find a qZ-pair (L, G), where L is a linear difference operator with coefficients in the ring of polynomials in q^{n}

L = a_{0}(q^{n})N^{0} + a_{1}(q^{n})N^{1} + ⋯ + a_{r}(q^{n})N^{r}

and G is a bivariate q-hypergeometric term G(n, k) such that

LT (n, k) = (K − 1)G(n, k).

Zeilberger’s algorithm has been widely used as a powerful tool to prove hypergeometric identities. It was an open question when the algorithm terminates.

This problem was solved recently by Abramov [1,2]. For the q-analogue of Zeilberger’s algorithm, Le [13] found a solution to the termination problem for the case of rational functions. In this paper we provide a complete solution for the general q-case.

We begin with an additive decomposition of univariate q-hypergeometric terms. Using this decomposition, a univariate q-hypergeometric term T (n) can be represented as

T (n) = (N − 1)T_{1}(n) + T_{2}(n),

where T_{1}(n) and T_{2}(n) are q-hypergeometric terms, and T_{2}(n) has the following form

T_{2}(n) = \frac{u_{1}(q^{n})}{u_{2}(q^{n})} ∏_{j=n_{0}}^{n−1} \frac{f_{1}(q^{j})}{f_{2}(q^{j})},

where v_{1}, v_{2}, f_{1}, f_{2} are polynomials and for any integer m, u_{2}(x) and u_{2}(xq^{m}) have no common factors except for a power of x. Consequently, a bivariate q-hypergeometric term T (n, k) can be decomposed as

T (n, k) = (K − 1)T_{1}(n, k) + T_{2}(n, k)  (1.1)

such that

T_{2}(n, k) = T (n, k_{0})V (q^{n}, q^{k}) ∏_{j=k_{0}}^{k−1} F (q^{n}, q^{j}),

where V, F are rational functions and the denominator v_{2} of V satisfies the conditions that for any integer m, v_{2}(x, y) and v_{2}(x, yq^{m}) have no common factors except for a power of y. The polynomial v_{2}(x, y) with the above property is called ε_{y}-free. We should note that the above decomposition does not solve the minimal additive decomposition problem and is not unique. However, for the purpose of constructing a qZ-pair, it turns out that one may choice any decomposition.

Then we consider the structure of bivariate q-hypergeometric terms. The structure of ordinary hypergeometric terms has been studied by Ore [14], Sato-Shintani-Muro [17], Abramov-Petkovšek [6] and Hou [11]. To a large extent, the q-case is analogous to the ordinary case. For each bivariate q-hypergeometric term, we associate it with a normal representation (q-NR) which consists of four polynomials r, s, u, v. Based on the properties of the representation, we may give a definition of q-proper hypergeometric terms and prove that under the condition that v is ε_{y}-free, a bivariate q-hypergeometric term has a qZ-pair if and only if it is a q-proper term. Applying the decomposition (1.1), we deduce that for any bivariate q-hypergeometric term T, it has a qZ-pair if and only if T_{2} is q-proper.

This paper is concluded with some examples.

2 ε-Free Decomposition

Throughout the paper, we let ℤ, ℤ^{+} and ℕ denote the set of integers, positive integers and nonnegative integers, respectively. For integers (or polynomials) a, b, we denote by gcd(a, b) the (monic) greatest common divisor of a and b. We also write a ⊥ b to indicate that a and b are relatively prime, i.e., gcd(a, b) = 1.

Let 𝔽 be a field of characteristic zero, q ∈ 𝔽 a nonzero element which is not a root of unity, and x transcendental over 𝔽. Denote by ε the unique automorphism of 𝔽(x) which fixes 𝔽 and satisfies εx = qx. Then 𝔽(x) together with the q-shift operator ε is a difference field [8]. Let r and s be two polynomials. We say that r/s is ε-reduced if r ⊥ ε^{h}s for all h ∈ ℤ.

To be more specific, the rational functions involved in the q-hypergeometric terms (see Definition 2.4) are rational functions of q^{n}. However, for a rational function R ∈ 𝔽(x), we have

N R(q^{n}) = R(q^{n+1}) = εR(q^{n}) and R(q^{n}) = 0 ∀ n ≥ n_{0} ⇔ R(x) = 0.

Therefore, there is a natural one-to-one correspondence between the set of rational functions of q^{n} together with the shift operator N and the field 𝔽(x) together with the q-shift operator ε. In this paper, we adopt the notation of 𝔽(x) as in the work of Abramov-Paule-Petkovšek [4].

The concept of rational normal forms introduced by Abramov and Petkovšek [5] can be extended to the q-case.

Definition 2.1 Let R ∈ 𝔽(x) be a rational function. If polynomials r, s, u, v ∈ 𝔽[x] satisfy

(i) R = \frac{r}{s} · \frac{ε(u/v)}{(u/v)} where u ⊥ v and u, v have no factor x,

(ii) r/s is ε-reduced,

then (r, s, u, v) is called a q-rational normal form (q-RNF) of R.

Recall that a monic polynomial that has no factor x is called a q-monic polynomials by Abramov, Paule, and Petkovšek [4]. The following factorization theorem was given in [4].

Theorem 2.2 Let R ∈ 𝔽(x) \ {0}. Then there exist z ∈ 𝔽 and monic polynomials a, b, c ∈ 𝔽[x] such that

R(x) = z \frac{a(x)}{b(x)} \frac{c(qx)}{c(x)},

gcd(a(x), b(q^{n}x)) = 1, for all n ∈ ℕ,

gcd(a(x), c(x)) = gcd(b(x), c(qx)) = 1 and c(0) ≠ 0.

(2.1)

We call (az, b, c) a q-Gosper form (q-GF) of R.

Theorem 2.3 Every rational function R ∈ 𝔽(x) has a q-RNF.

Proof. It is clear that (0, 1, 1, 1) is a q-RNF of 0. For R ≠ 0, by Theorem 2.2, there exists a q-GF (az, b, c) of R. Applying Theorem 2.2 again to b(x)/a(x), we get a q-GF (r, s, d). From the construction given in [4], we have r | b and s | a. Hence s(x) ⊥ r(xq^{n}) for any n ∈ ℕ because (az, b, c) is a q-GF. Since (r, s, d) is also a q-GF, we have r(x) ⊥ s(xq^{n}) for any n ∈ ℕ. Thus s/r is ε-reduced and (zs, r, c/ gcd(c, d), d/ gcd(c, d)) is a q-RNF of R.

The above proof provides an algorithm to generate a q-RNF of R. Algorithm q-RNF

if R = 0 then

return (0, 1, 1, 1); else

compute ‘q-GF’ of R, we get (a, b, c); compute ‘q-GF’ of b/a, we get (r, s, d); return (s, r, c/ gcd(c, d), d/ gcd(c, d));

We now come to the q-multiplicative representation of a general q-hypergeometric term. This is the starting point of the ε-free decomposition algorithm.

Definition 2.4 Suppose T (n) is a function from ℕ to 𝔽. If there exist a nonnegative integer n_{0} and a nonzero rational function R(x) ∈ 𝔽(x) such that T (n + 1) = R(q^{n})T (n) for all n ≥ n_{0}, then we call T (n) a (univariate) qhypergeometric term.

Suppose (r, s, u, v) is a q-RNF of a rational function R. Then the corresponding q-hypergeometric term T (n) satisfies

T (n) = T (n_{0}) ∏_{j=n_{0}}^{n−1} R(q^{j}) = \frac{T (n_{0})}{u(q^{n_{0}})/v(q^{n_{0}})} · \frac{u(q^{n})}{v(q^{n})} ∏_{j=n_{0}}^{n−1} \frac{r(q^{j})}{s(q^{j})}, ∀ n ≥ n_{0}.

This leads to the following definition.

Definition 2.5 Let T (n) be a q-hypergeometric term and D, U be two rational functions such that D(q^{n}) has neither poles nor zeros and U(q^{n}) has no poles for all n ≥ n_{0}. Suppose that

T (n) = U(q^{n}) ∏_{j=n_{0}}^{n−1} D(q^{j}), ∀ n ≥ n_{0}.

Then we call (D, U, n_{0}) a q-multiplicative representation (q-MR) of T.

Let Δ = N − 1 be the difference operator with respect to n. The following lemma can be easily verified.

Lemma 2.6 Let T and T_{1} be two q-hypergeometric terms with q-MRs (D, U, n_{0}) and (D, U_{1}, n_{0}), respectively. Suppose that

T_{2} = T − ΔT_{1} and U_{2} = U − D · εU_{1} + U_{1}.

Then (D, U_{2}, n_{0}) is a q-MR of T_{2}.

For u, v ∈ 𝔽[x], let R be the set of all nonnegative integers h such that there exists an irreducible polynomial p(x) ≠ x satisfying p(x) | u(x) and p(x) | v(q^{h}x). Define qdis(u, v) to be max{h ∈ R} or −1 if R is empty. Note that R is a finite set, and “qdis” is well defined. If qdis(v, v) = 0, we say that v is ε-free.

Given a q-hypergeometric term T with a q-MR (D, U, n_{0}). Usually the denominator u of U is not ε-free. However, translating the decomposition algorithm of [5] into the q-case, we have the following ε-free decomposition algorithm “q-decomp”, which decomposes T = ΔT_{1}+T_{2} such that T_{2} has a q-MR (F, V, n_{0}) where the denominator of V is ε-free. Algorithm q-decomp Input: (D, U, n_{0}) Output: U_{1}, F, V ∈ 𝔽(x)

d_{1} := numer(D); d_{2} := denom(D); U_{1} := 0; U_{2} := U; u_{2} := denom(U); N := qdis(u_{2}, u_{2}); for h := N down to 1 do

v_{2} := u_{2}/ gcd(u_{2}, d_{2})

s(x) := gcd(v_{2}(x), v_{2}(q^{−h}x));

(s̃, ũ_{2}) := pump(s, u_{2});

write U_{2} = a/ũ_{2} + b/s̃ where a, b ∈ 𝔽[x]; U′_{1} := −b/s̃; U_{1} := U_{1} + U′_{1}; U_{2} := U_{2} − D · εU′_{1} + U′_{1}; u_{2} := denom(U_{2});

f_{1} := d_{1}; f_{2} := d_{2}; v_{1} := numer(U_{2}); v_{2} := denom(U_{2}); w := gcd(d_{2}, v_{2}); v_{2} := v_{2}/w; f_{2} := εwf_{2}/w; F := f_{1}/f_{2}; V := (1/w(q^{n_{0}})) · v_{1}/v_{2}; return (U_{1}, F, V).

The procedure “pump” is the same as in the ordinary case. Algorithm pump Input: f, g ∈ 𝔽[x]; Output: f̃, g̃ ∈ 𝔽[x].

f̃:= f; g̃ := g/f; repeat

d := gcd(f̃, g̃); f̃:= f̃d; g̃ := g̃/d; until deg d = 0; return (f̃, g̃). The following theorem shows that the ε-free algorithm generates the desired

decomposition.

Theorem 2.7 Let T be a q-hypergeometric term with a q-MR (D, U, n_{0}) and U_{1}, F, V be given by the algorithm q-decomp. Then there exist q-hypergeometric terms T_{1} and T_{2} such that

(1) T = ΔT_{1} + T_{2}.

(2) T_{1} has a q-MR (D, U_{1}, n_{0}) and T_{2} has a q-MR (F, V, n_{0}).

(3) The denominator of V is ε-free.

Furthermore, if D is ε-reduced, so is F.

Proof. Let u_{0} be the denominator of U. We first use induction to show that after iterating the loop of h in the algorithm i times, the denominator u_{2} of U_{2} satisfies:

(a) qdis(v_{2}, v_{2}) ≤ N − i,

(b) u_{2}(q^{n}) has no zeros for all n ≥ n_{0},

where v_{2} = u_{2}/ gcd(u_{2}, d_{2}), and d_{2} is the denominator of D.

The case for i = 0 is trivial. Assume that the assertion holds for i − 1. Let u_{2} and u′_{2} be the denominator of U_{2} after i − 1 and i iterations, respectively.

Set h = N − (i − 1) > 0 and w_{2} = gcd(u_{2}, d_{2}). From the algorithm q-decomp we have

v_{2} = u_{2}/w_{2} and s = gcd(v_{2}(x), v_{2}(q^{−h}x)).

Suppose the prime decomposition of s is p_{1}^{α_{1}} ⋯ p_{r}^{α_{r}} and v_{2} = p_{1}^{β_{1}} ⋯ p_{r}^{β_{r}}v′, w_{2} = p_{1}^{γ_{1}} ⋯ p_{r}^{γ_{r}}w′ where v′ ⊥ s, w′ ⊥ s. Then the algorithm “pump” enables us to decompose u_{2} as p_{1}^{β_{1}+γ_{1}} ⋯ p_{r}^{β_{r}+γ_{r}} · (v′w′). That is, s̃ = p_{1}^{β_{1}+γ_{1}} ⋯ p_{r}^{β_{r}+γ_{r}} and ũ_{2} = v′w′. Since

U_{2} = \frac{a}{ũ_{2}} + \frac{d_{1}}{d_{2}} · ε (\frac{b}{s̃}) ,

it follows that u′_{2} divides the least common multiple of ũ_{2} and d_{2}εs̃. Hence we have that u′_{2} divides v′d_{2} · εs̃. Let v′′ = v′ · εs̃. Assume that there exist an integer m ≥ h and an irreducible polynomial p(x) ≠ x such that p | v′′ and p | ε^{m}v′′. We may encounter four cases:

• p | v′ and p | ε^{m}v′.

From v′ | v_{2} and qdis(v_{2}, v_{2}) ≤ h, it follows that m = h. Therefore, ε^{−h}p | ε^{−h}v_{2} and ε^{−h}p | v_{2}. Consequently, we have ε^{−h}p | s, which contradicts v′ ⊥ s.

• p | v′ and p | ε^{m+1}s̃.

Since s and s̃ have the same prime factors, we have p | ε^{m+1}s, implying that p | ε^{m+1}v_{2}. On the other hand, we have p | v_{2}, which contradicts qdis(v_{2}, v_{2}) ≤ h.

• p | εs̃ and p | ε^{m}v′.

In this situation, we have ε^{−1}p | s̃, which implies that ε^{−1}p | ε^{−h}v_{2}, or equivalently, ε^{h−1}p | v_{2}. On the other hand, ε^{h−1}p | ε^{m+h−1}v_{2}. Since qdis(v_{2}, v_{2}) ≤ h, we get m + h − 1 ≤ h, and hence m = 1. Now we have p | εs and p | εv′, which contradicts v′ ⊥ s.

• p | εs̃ and p | ε^{m+1}s̃.

Similarly, we have ε^{−1}p | s and hence ε^{−1}p | ε^{−h}v_{2}, i.e., ε^{h−1}p | v_{2}. However, we have ε^{h−1}p | ε^{m+h}v_{2}. Thus, we obtain m + h ≤ h, which is also a contradiction.

In summary, we may conclude that qdis(v′′, v′′) ≤ h − 1. Because u′_{2} divides v′′ · d_{2}, there exist v̄ | v′′ and w̄ | d_{2} such that u′_{2} = v̄w̄. Let v′_{2} = u′_{2}/ gcd(u′_{2}, d_{2}). From w̄ | gcd(u′_{2}, d_{2}), it follows that v′_{2} | v̄. So we get qdis(v′_{2}, v′_{2}) ≤ h−1 = N −i. Thus, we have proved (a). Since u′_{2}|u_{2} · εu_{2} · d_{2}, (b) immediately follows from the induction hypothesis.

On the other hand, since s̃| u_{2}, (b) implies that U_{1}(q^{n}) has no poles for all n ≥ n_{0}. Let

T_{1}(n) = U_{1}(q^{n}) ∏_{j=n_{0}}^{n−1} D(q^{j}) and T_{2}(n) = U_{2}(q^{n}) ∏_{j=n_{0}}^{n−1} D(q^{j}).  (2.2)

Noting that U_{2} = U − DεU_{1} + U_{1}, by Lemma 2.6, we obtain T = ΔT_{1} + T_{2}. Because w | d_{2} and d_{2}(q^{n}) ≠ 0 for all n ≥ n_{0}, we can write T_{2}(n) as

T_{2}(n) = \frac{1}{w(q^{n_{0}})}U_{2}(q^{n})w(q^{n}) ∏_{j=n_{0}}^{n−1} D(q^{j})\frac{w(q^{j})}{w(q^{j+1})} = V (q^{n}) ∏_{j=n_{0}}^{n−1} F (q^{j}).

Let v be the denominator of V. Then (a) implies qdis(v, v) = 0, that is, v is ε-free.

Finally, notice that f_{1} = d_{1} and f_{2} = εw · (d_{2}/w) where w | d_{2}. Therefore, F is ε-reduced provided that D is ε-reduced. This completes the proof.

3 Bivariate q-Hypergeometric Terms

We begin this section with the definition of bivariate q-hypergeometric terms.

Definition 3.1 Suppose T (n, k) is a function from ℕ^{2} to 𝔽. If there exist rational functions R_{1}(x, y), R_{2}(x, y) ∈ 𝔽(x, y) and n_{0} ∈ ℕ such that

T (n + 1, k) = R_{1}(q^{n}, q^{k})T (n, k) and T (n, k + 1) = R_{2}(q^{n}, q^{k})T (n, k),

for all n, k ≥ n_{0}, then we call T (n, k) a bivariate q-hypergeometric term.

Without loss of generality, from now on we may assume that n_{0} = 0 and that R_{1}(q^{n}, q^{k}), R_{2}(q^{n}, q^{k}) have neither zeros nor poles for all n, k ≥ 0.

Denote by ε_{x} and ε_{y} the shift operators on 𝔽(x, y) defined by ε_{x}x = qx, ε_{x}|_{𝔽(y)} = id (the identity map) and ε_{y}y = qy, ε_{y}|_{𝔽(x)} = id, respectively. The idea of q-RNF can be easily adopted to the bivariate case by taking 𝔽(y) as the ground field. Let R(x, y) be a rational function of x and y, its q-rational normal form (q-RNF with respect to ε_{x}) is represented by (r, s, u, v) as in the univariate case. By using the ground field 𝔽(x), we may find a q-RNF of R(x, y) with respect to ε_{y}.

Let T (n, k) be a bivariate q-hypergeometric term. By definition, there exists a rational function R such that

T (n + 1, k)/T (n, k) = R(q^{n}, q^{k}).

Suppose (r, s, u, v) is a q-RNF of R with respect to ε_{x}. We call (r, s, u, v) a q-normal representation (q-NR) of T (n, k) with respect to the shift operator N. Similarly, we can define the q-NR of T (n, k) with respect to the shift operator K.

We next give a characterization of the polynomials involved in the q-NR of q-hypergeometric terms.

Theorem 3.2 Let T (n, k) be a bivariate q-hypergeometric term that has a q-NR (r, s, u, v) with respect to N. Then r and s are products of polynomials having the form

(x^{c}y^{d}) · ∏_{l=1}^{a} p(q^{w_{l}}x^{a}y^{b}),

where p is a Laurent polynomial of one variable, a ∈ ℤ^{+}, b, c, d, w_{l} ∈ ℤ, a ⊥ b, and w_{i} ≢ w_{j} (mod a), ∀ i ≠ j.

Similarly, suppose (r, s, u, v) is a q-NR of T with respect to K. Then r and s are products of polynomials having the form

(x^{c}y^{d}) · ∏_{l=1}^{a} p(q^{w_{l}}x^{b}y^{a})

under the same conditions.

Sketch of the proof. The proof of the ordinary case [11, Theorem 3.4] can be carried over to the q-case except that we need to consider the characterization of polynomials f(x, y) such that f(q^{a}x, q^{b}y) = Cf(x, y) for certain integers a, b and C ∈ 𝔽.

Consequently, we have

Corollary 3.3 Let T (n, k) be a bivariate q-hypergeometric term that has a q-NR (r, s, u, v) with respect to N (or K respectively). Then we have

T (n, k) = C · \frac{u(q^{n}, q^{k})}{v(q^{n}, q^{k})} · \frac{∏_{l=1}^{uu} ∏_{j=0}^{a_{l}n+b_{l}k+c_{l}} f_{l}(q^{j})}{∏_{l=1}^{vv} ∏_{j=0}^{a′_{l}n+b′_{l}k+c′_{l}} g_{l}(q^{j})},

where C ∈ 𝔽, uu, vv ∈ ℕ, a_{l}, b_{l}, c_{l}, a′_{l}, b′_{l}, c′_{l} ∈ ℤ and f_{l}, g_{l} are polynomials.

Corollary 3.3 enables us to give the following definition of q-proper hypergeometric terms.

Definition 3.4 A polynomial f ∈ 𝔽[x, y] is said to be q-proper if for each of its irreducible factor p(x, y) ∈ 𝔽[x, y], there exist a, b ∈ ℤ, not both zeros, such that p(x, y)|p(q^{a}x, q^{b}y). A bivariate q-hypergeometric term T is said to be q-proper if v is a q-proper polynomial where (r, s, u, v) is a q-NR of T with respect to N or K.

Suppose that T is a bivariate q-hypergeometric term that has a q-NR (r, s, u, v) with respect to N (or K). Theorem 3.2 guarantees that r and s are both q-proper polynomials.

As in the case of ordinary bivariate hypergeometric terms ( [11, Theorems 4.2]), we have an analogous “fundamental theorem” for the q-case.

Theorem 3.5 Let T (n, k) be a bivariate q-hypergeometric term. Then T is qproper if and only if there exist polynomials a_{ij}(x) ∈ 𝔽[x], not all zero, such that

∑_{0≤i≤I, 0≤j≤J} a_{ij}(q^{n})T (n + i, k + j) = 0 ∀ n, k ≥ 0.

Based on an analogous argument for the ordinary case as in [16, Theorem 6.2.1], we get

Corollary 3.6 Any q-proper hypergeometric term has a qZ-pair.

4 The Existence of qZ-Pairs

In this section, we obtain a necessary and sufficient condition for the existence of qZ-pairs for any bivariate q-hypergeometric term based on its q-NR with respect to K.

From Theorem 3.2, we have Corollary 4.1 Let T (n, k) be a bivariate q-hypergeometric term that has a q-NR (r, s, u, v) with respect to K. There exist polynomials f_{i}(x), g_{i}(x) ∈ 𝔽[x] and a_{i}, a′_{i}, b_{i}, b′_{i} ∈ ℤ such that

∏_{j=0}^{k−1} (\frac{r(q^{n+1}, q^{j})}{r(q^{n}, q^{j})} · \frac{s(q^{n}, q^{j})}{s(q^{n+1}, q^{j})}) = ∏_{i=1}^{ℓ} \frac{f_{i}(q^{a_{i}k+b_{i}n})}{g_{i}(q^{a′_{i}k+b′_{i}n})}.

We need to consider the following ratio

\frac{T (n + i, k)}{T (n, k)} = \frac{T (n + i, 0)}{T (n, 0)} ∏_{j=0}^{k−1} \{\frac{T (n + i, j + 1)}{T (n + i, j)} \frac{T (n, j)}{T (n, j + 1)}\} ,

which can be rewritten as

\frac{T (n + i, k)}{T (n, k)} = ∏_{l=0}^{i−1} ∏_{j=0}^{k−1} \{\frac{r(q^{n+l+1}, q^{j})}{r(q^{n+l}, q^{j})} \frac{s(q^{n+l}, q^{j})}{s(q^{n+l+1}, q^{j})}\} ∏_{l=0}^{i−1} \frac{T (n + l + 1, 0)}{T (n + l, 0)}

· \frac{u(q^{n+i}, q^{k})}{u(q^{n+i}, q^{0})} \frac{u(q^{n}, q^{0})}{u(q^{n}, q^{k})} \frac{v(q^{n+i}, q^{0})}{v(q^{n+i}, q^{k})} \frac{v(q^{n}, q^{k})}{v(q^{n}, q^{0})}.  (4.1)

From Corollary 4.1 we get the following expression.

Lemma 4.2 Let T (n, k) be a bivariate q-hypergeometric term that has a q-NR (r, s, u, v) with respect to K. Then for each i ≥ 0, there exist q-proper polynomials w_{1}^{(i)}(x, y) and w_{2}^{(i)}(x, y) such that

\frac{T (n + i, k)}{T (n, k)} = \frac{u(q^{n+i}, q^{k})}{v(q^{n+i}, q^{k})} · \frac{v(q^{n}, q^{k})}{u(q^{n}, q^{k})} · \frac{w_{1}^{(i)}(q^{n}, q^{k})}{w_{2}^{(i)}(q^{n}, q^{k})}, ∀ n, k ≥ 0.  (4.2)

An ε_{y}-free polynomial that is not q-proper has a special factor.

Lemma 4.3 Let f ∈ 𝔽[x, y] be a non-q-proper and ε_{y}-free polynomial. Then there exists an irreducible factor p of f such that

\begin{matrix}p(x, y) ⊥ p(q^{i}x, q^{j}y), ∀ (i, j) ∈ ℤ^{2} \ \{(0, 0)\}, \\ p(x, y) ⊥ f(q^{i}x, q^{j}y), ∀ (i, j) ∈ (ℕ × ℤ) \ \{(0, 0)\}. \end{matrix}  (4.3)

Proof. Since f(x, y) is non-q-proper, by definition it has an irreducible factor p_{1}(x, y) such that p_{1}(x, y) ⊥ p_{1}(q^{i}x, q^{j}y), ∀ (i, j) ∈ ℤ^{2} \ {(0, 0)}.

We may factor f(x, y) as

f(x, y) = p_{1}^{α_{1}}(q^{a_{1}}x, q^{b_{1}}y) ⋯ p_{1}^{α_{r}}(q^{a_{r}}x, q^{b_{r}}y)f_{1}(x, y),

where (a_{i}, b_{i}) ∈ ℤ^{2} are distinct pairs, α_{i} ∈ ℤ^{+}, and p_{1}(q^{i}x, q^{j}y) ⊥ f_{1}(x, y) for all i, j ∈ ℤ. Since f(x, y) is ε_{y}-free, it follows that a_{i} ≠ a_{j} as long as i ≠ j. Without loss of generality, we may assume that a_{1} < a_{2} < ⋯ < a_{r}. Thus, p(x, y) = p_{1}(q^{a_{1}}x, q^{b_{1}}y) satisfies the condition (4.3).

We are now ready to give a criterion for the existence of qZ-pairs.

Theorem 4.4 Let T (n, k) be a bivariate q-hypergeometric term that has a q-NR (r, s, u, v) with respect to K such that v is ε_{y}-free. Then T (n, k) has a qZ-pair if and only if v is a q-proper polynomial.

Proof. Because of Corollary 3.6, it suffices to show that if T (n, k) has a qZpair, then it is q-proper. To this end, we assume that T (n, k) is a bivariate q-hypergeometric term. Moreover, we assume that T (n, k) is not q-proper, but it has a qZ-pair. We proceed to find a contradiction.

Clearly, for a difference operator L ∈ 𝔽[q^{n}, N], we have

(N · L)T (n, k) = (K − 1)G(n, k) ⟺ LT (n, k) = (K − 1)G(n − 1, k).

Therefore, we may assume that T (n, k) has a qZ-pair (L, G) of the form

L = ∑_{i=0}^{I} a_{i}(q^{n})N^{i},

where a_{i}(q^{n}) are polynomials in q^{n} and a_{0} ≠ 0. Since LT/T and (K − 1)G/G are both rational functions of q^{n} and q^{k}, we may assume that

G(n, k) = \frac{f(q^{n}, q^{k})}{g(q^{n}, q^{k})}T (n, k),

where f, g ∈ 𝔽[x, y] are two relatively prime polynomials.

By the definition of qZ-pairs, we have

∑_{i=0}^{I} a_{i}(q^{n})\frac{T (n + i, k)}{T (n, k)} = \frac{f(q^{n}, q^{k+1})}{g(q^{n}, q^{k+1})} \frac{T (n, k + 1)}{T (n, k)} − \frac{f(q^{n}, q^{k})}{g(q^{n}, q^{k})}.  (4.4)

Substituting (4.2) into (4.4), we obtain

∑_{i=0}^{I} a_{i}(x)\frac{u(q^{i}x, y)}{v(q^{i}x, y)} \frac{w_{1}^{(i)}(x, y)}{w_{2}^{(i)}(x, y)} = \frac{f(x, qy)}{g(x, qy)} \frac{r(x, y)}{s(x, y)} \frac{u(x, qy)}{v(x, qy)} − \frac{f(x, y)}{g(x, y)} \frac{u(x, y)}{v(x, y)}. (4.5)

Let u_{1} = u/ gcd(u, g), g_{1} = g/ gcd(u, g). Multiplying

g_{1}(x, qy)g_{1}(x, y)v(x, qy)s(x, y) ∏_{j=0}^{I} v(q^{j}x, y)w_{2}^{(j)}(x, y)

to both sides of (4.5), we arrive at

g_{1}(x, qy)g_{1}(x, y)v(x, qy)s(x, y)

· ∑_{i=0}^{I} a_{i}(x)u(q^{i}x, y)w_{1}^{(i)}(x, y) ∏_{j≠i} v(q^{j}x, y)w_{2}^{(j)}(x, y)

=f(x, qy)r(x, y)u_{1}(x, qy)g_{1}(x, y) ∏_{j=0}^{I} v(q^{j}x, y)w_{2}^{(j)}(x, y)

− f(x, y)u_{1}(x, y)g_{1}(x, qy)v(x, qy)s(x, y)w_{2}^{(0)}(x, y) · ∏_{j=1}^{I} v(q^{j}x, y)w_{2}^{(j)}(x, y). (4.6)

Since T (n, k) is not q-proper, from Lemma 4.3 it follows that there exists an irreducible factor p of v satisfying the condition (4.3). Noting that p(x, y) divides each term of the left-hand side of (4.6) except for the first term, we obtain that p(x, y) divides

g_{1}(x, qy)v(x, qy)s(x, y) ∏_{j=1}^{I} v(q^{j}x, y)w_{2}^{(j)}(x, y)

× (g_{1}(x, y)a_{0}(x)u(x, y)w_{1}^{(0)}(x, y) + f(x, y)u_{1}(x, y)w_{2}^{(0)}(x, y)).

From (4.3) it follows that

p(x, y) ⊥ v(x, qy) ∏_{j=1}^{I} v(q^{j}x, y).

Since s and w_{2}^{(j)} are q-proper, they are also relatively prime to p. This implies that p(x, y) divides

g_{1}(x, qy)(g_{1}(x, y)a_{0}(x)u(x, y)w_{1}^{(0)}(x, y) + f(x, y)u_{1}(x, y)w_{2}^{(0)}(x, y)). (4.7)

Similarly, since p(x, qy) divides both sides of (4.6) and u ⊥ v, we have

p(x, qy) | f(x, qy)g_{1}(x, y).  (4.8)

Case 1. Suppose p(x, qy) | f(x, qy). Since p(x, y) divides (4.7), it follows that

p(x, y) | g_{1}(x, qy)g_{1}(x, y)a_{0}(x)u(x, y)w_{1}^{(0)}(x, y).

Since f ⊥ g, u ⊥ v, a_{0} and w_{1}^{(0)} are q-proper polynomials, we may deduce that p(x, y) | g_{1}(x, qy), i.e., p(x, q^{−1}y) | g_{1}(x, y). Let m(>0) be the greatest integer such that p(x, q^{−m}y) | g_{1}(x, y). By virtue of (4.6), we have that p(x, q^{−m}y) divides

f(x, y)u_{1}(x, y)g_{1}(x, qy)v(x, qy)s(x, y)w_{2}^{(0)}(x, y) ∏_{j=1}^{I} v(q^{j}x, y)w_{2}^{(j)}(x, y).

However, f ⊥ g and g_{1} ⊥ u_{1} imply that p(x, q^{−m}y) | g_{1}(x, qy), which contradicts the choice of m.

Case 2. Suppose p(x, qy) | g_{1}(x, y). Let M > 0 be the greatest integer such that p(x, q^{M}y) | g_{1}(x, y). Similarly, from (4.6) it follows that p(x, q^{M+1}y) divides

f(x, qy)r(x, y)u_{1}(x, qy)g_{1}(x, y) ∏_{j=0}^{I} v(q^{j}x, y)w_{2}^{(j)}(x, y).

Hence we get p(x, q^{M+1}y) | g_{1}(x, y), which is again a contradiction.

To extend the above result to general bivariate q-hypergeometric terms, we need the concept of similar q-hypergeometric terms. Two bivariate q-hypergeometric terms T_{1}, T_{2} are called similar if there exists a rational function R ∈ 𝔽(x, y) such that T_{1}(n, k)/T_{2}(n, k) = R(q^{n}, q^{k}).

As in the ordinary case, the existence of qZ-pairs is preserved under addition of similar bivariate q-hypergeometric terms.

Lemma 4.5 Suppose there exist qZ-pairs for two similar bivariate q-hypergeometric terms T_{1}(n, k) and T_{2}(n, k). Then there exists a qZ-pair for T (n, k) = T_{1}(n, k)+ T_{2}(n, k).

Notice that T (n, k) = (K − 1)G(n, k) has a qZ-pair (1, G). Combining Theorem 4.4 and Lemma 4.5, we obtain the main result of this paper.

Theorem 4.6 Let T (n, k) be a bivariate q-hypergeometric term. Let T_{1}, T_{2} be two similar bivariate q-hypergeometric terms satisfying

T (n, k) = (K − 1)T_{1}(n, k) + T_{2}(n, k)

and T_{2}(n, k) has a q-NR (r, s, u, v) with respect to K such that v is ε_{y}-free. Then T (n, k) has a qZ-pair if and only if T_{2}(n, k) is a q-proper hypergeometric term, or equivalently, if and only if v(x, y) is a q-proper polynomial.

5 Algorithms

Let T (n, k) be a bivariate q-hypergeometric term. By the algorithm “q-RNF”, we may find a q-RNF (r, s, u, v) of T (n, k) with respect to K. Let

F (k) = \frac{u(x, q^{k})}{v(x, q^{k})} ∏_{j=0}^{k−1} \frac{r(x, q^{j})}{s(x, q^{j})}, ∀ k ∈ ℕ.

Then F (k) is a univariate q-hypergeometric term over the field 𝔽(x) with a q-MR (r/s, u/v, 0). On the other hand, by Equation (4.1), we have

\frac{F (k)|_{x=q^{n+1}}}{F (k)|_{x=q^{n}}} = \frac{u(q^{n+1}, q^{k})v(q^{n}, q^{k})}{u(q^{n}, q^{k})v(q^{n+1}, q^{k})} ∏_{j=0}^{k−1} \frac{r(q^{n+1}, q^{j})s(q^{n}, q^{j})}{r(q^{n}, q^{j})s(q^{n+1}, q^{j})}

= \frac{T (n + 1, k)}{T (n, k)} · \frac{T (n, 0)}{T (n + 1, 0)} · \frac{u(q^{n+1}, q^{0})v(q^{n}, q^{0})}{u(q^{n}, q^{0})v(q^{n+1}, q^{0})},

which is also a rational function on q^{n} and q^{k}. Hence F̃(n, k) = F (k)|_{x=q^{n}} is a bivariate q-hypergeometric term.

Using the algorithm “q-decomp” given in Section 2, one may find univariate q-hypergeometric terms F_{1}(k), F_{2}(k) such that

F (k) = (K − 1)F_{1}(k) + F_{2}(k)

and F_{2}(k) has a q-MR (f_{1}/f_{2}, v_{1}/v_{2}, 0) with v_{2} being ε_{y}-free. Since f_{1}/f_{2}, v_{1}/v_{2} ∈ 𝔽(x)(y), we may assume that f_{1}, f_{2}, v_{1}, v_{2} ∈ 𝔽[x, y] and f_{1} ⊥ f_{2}, v_{1} ⊥ v_{2}. From the fact that r/s is ε_{y}-reduced, it follows that f_{1}/f_{2} is also ε_{y}-reduced.

Let

T_{1}(n, k) = T (n, 0)\frac{v(q^{n}, q^{0})}{u(q^{n}, q^{0})} · F_{1}(k)|_{x=q^{n}},

T_{2}(n, k) = T (n, 0)\frac{v(q^{n}, q^{0})}{u(q^{n}, q^{0})} · F_{2}(k)|_{x=q^{n}}.

Since Equation (2.2) implies that

F_{1}(k) = \frac{U_{1}}{u/v} · F (k) and F_{2}(k) = \frac{v_{1}/v_{2}}{u/v} · F (k),

it follows that T_{1}(n, k) and T_{2}(n, k) are similar bivariate q-hypergeometric terms. It is easily verified that

T (n, k) = (K − 1)T_{1}(n, k) + T_{2}(n, k)

and (f_{1}, f_{2}, v_{1}, v_{2}) is a q-NR of T_{2} with respect to K. Therefore, Theorem 4.6 implies that T (n, k) has a qZ-pair if and only if v_{2} is a q-proper polynomial.

Finally, we need the algorithm given by Le [13] for determining whether or not a polynomial is q-proper.

We are now ready to describe the algorithm to determine whether a bivariate q-hypergeometric term T (n, k) has a qZ-pair.

  1. Apply the algorithm in [7] to find a rational function R ∈ 𝔽(x, y)
     such that

\frac{T (n, k + 1)}{T (n, k)} = R(q^{n}, q^{k}).

  2. Find a q-RNF (r, s, u, v) of R.
  3. For D = r/s, U = u/v and n_{0} = 0, apply the algorithm `q-decomp'

to get V = v_{1}/v_{2}.

  4. Use the algorithm in [13] to determine whether v_{2} is q-proper.
     If the answer is yes, then T has a qZ-pair; otherwise, T does
     not have any qZ-pair.

Here are two examples. Example 1. Let

T (n, k) = \frac{q^{k}(1 + q^{n+1} + q^{k+2})}{(q^{n} + q^{k} + 1)(q^{n} + q^{k+1} + 1) ∏_{j=1}^{k+1}(1 − q^{j})}.

Then

\frac{T (n, k + 1)}{T (n, k)} = \frac{q(1 + q^{n+1} + q^{k+3})(q^{n} + q^{k} + 1)}{(q^{n} + q^{k+2} + 1)(1 + q^{n+1} + q^{k+2})(1 − q^{k+2})},

and we have

r = q, s = 1 − q^{2}y, u = 1 + qx + q^{2}y, v = (x + y + 1)(x + qy + 1)

is a q-NR of T with respect to K. For D = r/s, U = u/v and n_{0} = 0, applying the algorithm “q-decomp”, we get

V = v_{1}/v_{2} = \frac{−q^{2}}{(−1 + q^{2})(x + 1)}.

Clearly, v_{2} is q-proper, so T (n, k) has a qZ-pair. Indeed, we can check that

L = 1, G = \frac{1}{(q^{n} + q^{k} + 1) ∏_{j=1}^{k}(1 − q^{j})}

is a qZ-pair for T (n, k). Example 2. Let

T (n, k) = \frac{q^{k}(1 + q^{n+1} + q^{k+2})}{(q^{n} + q^{k} + 1)(q^{n} + q^{k+1} + 1) ∏_{j=1}^{k}(1 − q^{j})}.

Then

\frac{T (n, k + 1)}{T (n, k)} = \frac{q(1 + q^{n+1} + q^{k+3})(q^{n} + q^{k} + 1)}{(q^{n} + q^{k+2} + 1)(1 + q^{n+1} + q^{k+2})(1 − q^{k+1})},

and we have

r = q, s = 1 − qy, u = 1 + qx + q^{2}y, v = (x + y + 1)(x + qy + 1)

is a q-NR of T with respect to K. For D = r/s, U = u/v and n_{0} = 0, applying the algorithm “q-decomp”, we get

V = v_{1}/v_{2} = \frac{−(x + y + 1)q^{2}}{(q − 1)(x + 1)(x + qy + 1)}.

Since x + qy + 1 is not a q-proper polynomial, it follows that T (n, k) has no qZ-pair.

Acknowledgments. The authors are grateful to the referees for many helpful comments and suggestions. This work was done under the auspices of the 973 Project on Mathematical Mechanization and the National Science Foundation of China. We thank Professor Marko Petkovšek for bringing our attention to the work of Ore and Sato.

References

[1] S.A. Abramov, Applicability of Zeilberger’s algorithm to hypergeometric terms, In: Proc. Int. Symp. on Symbolic and Algebraic Computation, ACM Press, 2002.

[2] S.A. Abramov, When does Zeilberger’s algorithm succeed?, Adv. Appl. Math., 30 (2003) 424–441.

[3] S.A. Abramov and H.Q. Le, A criterion for the applicability of Zeilberger’s algorithm to rational functions, Discrete Math., 259 (2002) 1–17.

[4] S.A. Abramov, P. Paule, and M. Petkovšek, q-Hypergeometric solutions of q-difference equations, Discrete Math. 180 (1998) 3–22.

[5] S.A. Abramov and M. Petkovšek, Rational normal forms and minimal decompositions of hypergeometric terms, J. Symbolic Comput. 33 (2002) 521–543.

[6] S.A. Abramov and M. Petkovšek, On the structure of multivariate hypergeometric terms, Adv. Appl. Math. 29 (2002) 386–411.

[7] H. Böing and W. Koepf, Algorithms for q-hypergeometric summation in computer algebra, J. Symbolic Comput. 28 (1999) 777–799.

[8] R.M. Cohn, Difference Algebra, Interscience Publishers, New York, 1965.

[9] I. M. Gel’fand, M. I. Graev and V. S. Retakh, General hypergeometric systems of equations and series of hypergeometric type (Russian), Uspekhi Mat. Nauk 47 (1992) 3–82, 235; translation in Russian Math. Surveys 47 (1992) 1–88.

[10] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, 2nd Edition, Addison-Wesley, Reading, MA, 1994.

[11] Q.H. Hou, k-Free recurrences of double hypergeometric terms, Adv. Appl. Math. 32 (2004) 468-484.

[12] T.H. Koornwinder, On Zeilberger’s algorithm and its q-analogue, J. Comput. Appl. Math. 48 (1993) 91–111.

[13] H.Q. Le, On the q-analogue of Zeilberger’s algorithm to rational functions, Program. Comput. Software (Programmirovanie) 27 (2001) 49–58.

[14] O. Ore, Sur la forme des fonctions hypergéométriques de plusieurs variables, J. Math. Pures Appl. 9 (1930) 311–326.

[15] P. Paule and A. Riese, A Mathematica q-analogue of Zeilberger’s algorithm based on an algebraically motivated approach to q-hypergeometric telescoping, In: Special Functions, q-Series and Related Topics (Toronto, ON, 1995), 179–210, Fields Inst. Commun., 14, Amer. Math. Soc., Providence, RI, 1997.

[16] M. Petkovšek, H.S. Wilf, and D. Zeilberger, A=B, A.K. Peters, Wellesley, MA, 1996.

[17] M. Sato, T. Shintani and M. Muro, Theory of prehomogeneous vector spaces (algebraic part), Nagoya Math. J. 120 (1990) 1–34.

[18] H. Wilf and D. Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and “q”) multisum/integral identities, Invent. Math. 108 (1992) 575–633.

[19] D. Zeilberger, The method of creative telescoping, J. Symbolic Comput. 11 (1991) 195–204.