On the Structure of Multivariate Hypergeometric Terms

S. A. Abramov^{∗}

Computer Center of the Russian Academy of Science, Vavilova 40, Moscow 117967, Russia

                 abramov@ccas.ru

M. Petkovšek^{†}

Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI-1000 Ljubljana, Slovenia

                                                  marko.petkovsek@uni-lj.si

Abstract

Wilf and Zeilberger conjectured in 1992 that a hypergeometric term is proper-hypergeometric if and only if it is holonomic. We prove a slightly modified version of this conjecture in the case of several discrete variables.

1 Introduction

Let K be a field of characteristic zero, n_{1}, …, n_{d} variables ranging over the nonnegative integers, and E_{i} the corresponding shift operators, acting on functions of n_{1}, …, n_{d} by E_{i}f(n_{1}, …, n_{i}, …, n_{d}) = f(n_{1}, …, n_{i} + 1, …, n_{d}). A K-valued function T (n_{1}, …, n_{d}) is a hypergeometric term if there are rational functions F_{i} ∈ K(n_{1}, …, n_{d}) (called the certificates of T) such that E_{i}T = F_{i}T, for i = 1, …, d. T (n_{1}, …, n_{d}) is holonomic if partial derivatives of its generating function ∑_{n_{1},...,n_{d}≥0} T (n_{1}, …, n_{d})x_{1}^{n_{1}} ⋯ x_{d}^{n_{d}} lie in a finite-dimensional vector space over the rational function field K(x_{1}, …, x_{d}). A holonomic sequence satisfies a system of homogeneous linear recurrences of a special form. If T is holonomic then its definite sums w.r.t. some of the variables are still holonomic as functions of the remaining variables. If T is also hypergeometric then the holonomic recurrences satisfied by these sums can be found efficiently by means of Zeilberger’s Creative Telescoping algorithm [21, 22, 19].

A hypergeometric term is proper if it can be expressed as a product of a polynomial, several factorials of linear forms with integer coefficients, their reciprocals, and exponential functions. In [20] it is proved that proper hypergeometric terms are holonomic. Wilf and Zeilberger conjectured [19, p. 585] that a hypergeometric term is proper if and only if it is holonomic. Their conjecture concerns hypergeometric terms which depend on several discrete and continuous variables. We prove a slightly modified version of their conjecture in the discrete case, namely that every holonomic hypergeometric term is conjugate to a proper term (meaning that the two terms have the same certificates). This modification is necessary as shown, e.g., by the bivariate hypergeometric term T (n, k) = |n − k| which is holonomic since its generating function ∑_{n,k≥0} |n − k|x^{n}y^{k} = (x/(1 − x)^{2} + y/(1 − y)^{2})/(1 − xy) is rational, but T is not proper (see Example 6).

Our proof of the modified Wilf-Zeilberger conjecture is based on the Ore-Sato Theorem (as it is called in [5]) which states essentially that for every hypergeometric term T there is a rational function R and a proper term T′ such that (E_{i}T)/T = (E_{i}(RT′))/(RT′) for all i. This was proved in the bivariate case by Ore using elementary means [11, 12], and in the multivariate case by Sato using homological algebra [15, Appendix]. We give an elementary proof of the multivariate Ore-Sato Theorem. The necessary tools that are useful also for other purposes are developed in Section 3 (normal forms of rational functions) and Section 4 (shift-invariant and pairwise shift-invariant polynomials). The certificates F_{i} of a hypergeometric term clearly satisfy the compatibility conditions (E_{j}F_{i}) / F_{i} = (E_{i}F_{j}) / F_{j}. In Section 5 we give an algorithm which, given compatible rational functions F_{1}, …, F_{d}, computes compatible rational functions F′_{1}, …, F′_{d}, and a rational function R such that F_{i} = (E_{i}R/R)F′_{i}, and the numerators and denominators of F′_{i} factor into integer-linear factors (i.e., polynomials of the form a_{1}x_{1} + ⋯ + a_{d}x_{d} + c where the a_{i}’s are integers). In Section 6 we use this structure theorem to prove the Ore-Sato Theorem (Corollary 4). In Section 7 we show that a rational sequence is holonomic if and only if its denominator factors into integer-linear factors. Together with the Ore-Sato Theorem, this yields our main result: Every holonomic hypergeometric term is conjugate to a nontrivial proper term (Theorem 14). In these results, hypergeometric terms are treated as algebraic objects. But in applications hypergeometric terms are functions which take on specific values, therefore it is important to deal also with the questions of their zeros and of singularities of their certificates – which have received little attention in the literature referred to above. To overcome these problems we introduce the notion of nonvanishing rising factorials (Section 1), and two equivalence relations among nontrivial hypergeometric terms, namely equality modulo an algebraic set, and conjugacy between solutions of a first-order system of recurrences with polynomial coefficients (Section 2).

∗Partially supported by the French-Russian Lyapunov Institute under grant 98-03.

†Partially supported by MZT RS under grant J2-8549.

After we had obtained our results in the bivariate case [3, 4], it was brought to our attention that the bivariate Wilf-Zeilberger conjecture has been proved independently, and at almost the same time, also by Hou [8, 9].

Throughout the paper, K is a field of characteristic zero, and ℕ denotes the set of nonnegative integers. We write u = (u_{1}, u_{2}, …, u_{d}) for d-tuples of numbers or indeterminates, u ≥ v when u_{i} ≥ v_{i} for 1 ≤ i ≤ d, and u^{T} v = ∑_{i=1}^{d} u_{i}v_{i}. If u^{T} v = 0 then u and v are called orthogonal. We denote by e_{i} the d-tuple whose components are zero except the i-th one which is 1, and by s the d-tuple with all components equal to s. The monomial x_{1}^{u_{1}} ⋯ x_{d}^{u_{d}} is denoted by x^{u}. Following [7], we write p ⊥ q to indicate that polynomials p, q ∈ K[x] are relatively prime. By a factor of a rational function f ∈ K(x) we mean any polynomial factor of either p or q where f = p/q, p, q ∈ K[x], and p ⊥ q. We use E_{i} to denote the operator that shifts the i-th variable by 1. In particular, if T : ℕ^{d} → K is a d-variate sequence then E_{i}T (n_{1}, …, n_{i}, …, n_{d}) = T (n_{1}, …, n_{i} + 1, …, n_{d}), and if f ∈ K(x_{1}, x_{2}, …, x_{d}) is a rational function then E_{i}T (x_{1}, …, x_{i}, …, x_{d}) = T (x_{1}, …, x_{i} + 1, …, x_{d}).

We define the rising factorial (α)_{n} for all α ∈ K and n ∈ ℤ by

(α)_{n} = \{ \begin{matrix}∏_{i=0}^{n−1}(α + i), & n ≥ 0, \\ ∏_{i=1}^{−n} \frac{1}{α − i}, & n < 0 and α ≠ 1, 2, …, −n, \\ 0, & otherwise. \end{matrix}

Let Z(α) be the set of all n ∈ ℤ such that (α)_{n} = 0. Obviously,

Z(α) = \{ \begin{matrix}\{n ∈ ℤ; n + α ≤ 0\}, & α ∈ ℤ and α > 0, \\ \{n ∈ ℤ; n + α > 0\}, & α ∈ ℤ and α ≤ 0, \\ ∅, & otherwise. \end{matrix}  (1)

Note that (α + n)_{−n} serves as a kind of a pseudo-inverse for (α)_{n}, in the following sense:

• if (α)_{n} ≠ 0 then (α + n)_{−n} = 1/(α)_{n},

• if (α)_{n} = 0 then (α + n)_{−n} = 0.

It is easy to verify that the sequence (α)_{n} satisfies the first-order recurrence

(n + α)(α)_{n+1} − (n + α)^{2}(α)_{n} = 0  (2)

for all n ∈ ℤ. We will also need another solution of (2) which is nonzero for all α ∈ K and n ∈ ℤ. We call it the nonvanishing rising factorial and denote it (α)_{n}^{∗}. It is defined as the usual rising factorial, except that zero factors are omitted wherever they appear:

(α)_{n}^{∗} = \{ \begin{matrix}(α)_{n}, & (α)_{n} ≠ 0, \\ (α)_{1−α}(0)_{α+n}, & α ∈ ℤ and α > 0 and α + n ≤ 0, \\ (α)_{−α}(1)_{α+n−1}, & α ∈ ℤ and α ≤ 0 and α + n > 0. \end{matrix}

Now we have (α + n)_{−n}^{∗} = 1/(α)_{n}^{∗} for all n ∈ ℤ.

Example 1 According to our definitions,

(1)_{n} = \{ \begin{matrix}n!, & n ≥ 0, \\ 0, & n ≤ −1 \end{matrix} , (0)_{n} = \{ \begin{matrix}0, & n ≥ 1, \\ \frac{(−1)^{n}}{(−n)!} , & n ≤ 0 \end{matrix} ,

(1)_{n}^{∗} = \{ \begin{matrix}n!, & n ≥ 0, \\ \frac{(−1)^{n+1}}{(−n−1)!}, & n ≤ −1 \end{matrix} , (0)_{n}^{∗} = \{ \begin{matrix}(n − 1)!, & n ≥ 1, \\ \frac{(−1)^{n}}{(−n)!} , & n ≤ 0 \end{matrix} .

Remark 1 Proper hypergeometric terms are usually defined in terms of factorials of complex argument, with z! denoting Γ(z + 1) and 1/z! defined to be zero when z is a negative integer. If n is an integer variable and α ∈ ℂ, we can rewrite the sequence (n + α)! with rising factorials as

(n + α)! = \{ \begin{matrix}α! (α + 1)_{n}, & α ∉ ℤ, \\ (1)_{n+α}, & α ∈ ℤ \end{matrix}  (3)

whenever the left-hand side is defined (i.e., n + α is not a negative integer), and its reciprocal as

\frac{1}{(n + α)!} = \{ \begin{matrix}\frac{(n+α+1)_{−n}}{α!} , & α ∉ ℤ, \\ (n + α + 1)_{−(n+α)}, & α ∈ ℤ, \end{matrix}  (4)

where ordinary factorials (or the Γ-function) are applied only to constants on the right-hand side. The advantage of rising factorials over ordinary ones is that the former do not rely on the Γ-function and are well defined in any field of characteristic zero.

Wilf and Zeilberger [18] associate with (n + α)! its shadow

\frac{(−1)^{n}}{(−n − α − 1)!}

which satisfies the same first-order recurrence w.r.t. n. When α ∉ ℤ the shadow is just a constant-factor multiple of (n + α)! (the constant being −(sin απ)/π), while for α ∈ ℤ the shadow is complementary to (n + α)!, in the sense that the latter is defined when n + α ≥ 0, and the former when n + α < 0. If we replace the rising factorials in the right-hand side of (3) by their nonvanishing counterparts, nothing changes for α ∉ ℤ, but for α ∈ ℤ we have instead of (1)_{n+α}

(1)_{n+α}^{∗} = \{ \begin{matrix}(1)_{n+α} & = & (n + α)!, & n + α ≥ 0, \\ (0)_{n+α+1} & = & \frac{(−1)^{n+α+1}}{(−n−α−1)!}, & n + α < 0. \end{matrix}

Thus rewriting factorials in terms of the nonvanishing rising factorials, we either get the factorial itself or its shadow (perhaps with the opposite sign), whichever is defined.

2 Multivariate sequences

By a sequence T (n) we mean a function T : ℕ^{d} → K. We call a set A ⊆ ℕ^{d} algebraic if there is a polynomial p ∈ K[x] \ {0} which vanishes on A. Clearly, if A is algebraic and B is not, then B \ A is not algebraic. Also, a finite union of algebraic sets is algebraic.

Proposition 1 Let F, G ∈ K(x) be rational functions which agree on a non-algebraic set B ⊆ ℕ^{d}. Then F = G.

Proof: Let F = p/q, G = u/v, where p, q, u, v ∈ K[x]. The polynomial pv − qu vanishes on the non-algebraic set B, hence it is the zero polynomial, and so F = G. □

Definition 1 (equality modulo an algebraic set) We write T =_{a} T′ if the set {n ∈ ℕ^{d}; T (n) ≠ T′(n)} is algebraic. A sequence T (n) is trivial if T =_{a} 0.

Equality modulo an algebraic set is clearly an equivalence relation. It is also a congruence because T_{1} =_{a} T_{2} and T′_{1} =_{a} T′_{2} imply T_{1} + T′_{1} =_{a} T_{2} + T′_{2} and T_{1}T′_{1} =_{a} T_{2}T′_{2}. Trivial sequences can be described as those with algebraic support. Note however that a nontrivial sequence can vanish on a non-algebraic set.

Example 2 The sequence T (n, k) = \binom{n}{k} = (n − k + 1)_{k}(k + 1)_{−k} is nontrivial because supp T = \{(n, k) ∈ ℕ^{2}; n ≥ k} is not algebraic. But neither is its complement {(n, k) ∈ ℕ^{2}; n < k}.

Definition 2 (hypergeometric term, conjugate hypergeometric terms) A sequence T (n) is a hypergeometric term if there are polynomials p_{i}, q_{i} ∈ K[x] \ {0} such that

p_{i}(n)(E_{i}T (n)) = q_{i}(n)T (n)  (5)

for all n ∈ ℕ^{d} and 1 ≤ i ≤ d. Two hypergeometric terms T_{1}, T_{2} are conjugate if they satisfy (5) with the same p_{i}, q_{i}. In this case we write T_{1} ≃ T_{2}.

Proposition 2 (i) The product of two hypergeometric terms is a hypergeometric term.

(ii) If T_{1} ≃ T_{2} and T′_{1} ≃ T′_{2} then T_{1}T′_{1} ≃ T_{2}T′_{2}.

We omit the straightforward proofs.

Proposition 3 If T is a hypergeometric term and T′ =_{a} T then T′ is a hypergeometric term and T′ ≃ T.

Proof: Let T satisfy (5) and let p(n)T′(n) = p(n)T (n) for all n ∈ ℕ^{d}. Then

p(n)(E_{i}p(n))p_{i}(n)(E_{i}T′(n)) = p(n)(E_{i}p(n))q_{i}(n)T′(n)  (6)

for all n ∈ ℕ^{d} and 1 ≤ i ≤ d, hence T′ is a hypergeometric term. Clearly T (n) also satisfies (6), so T′ ≃ T.

□

The converse of Proposition 3 is of course not true, because conjugate hypergeometric terms may differ everywhere, as any constant multiple of a term is clearly conjugate to it.

Example 3 The “patchwork” sequence

T (n, k) = \{ \begin{matrix}2(n − 2k)!, & n > 2k, \\ 3^{k}, & n = 2k, \\ 7\frac{(−1)^{n}}{(2k−n−1)!}, & n < 2k \end{matrix}

= \{ \begin{matrix}2 (1)_{n−2k}, & n > 2k, \\ 3^{k}, & n = 2k, \\ 7 (−1)^{n}(2k − n)_{n−2k+1}, & n < 2k \end{matrix} = \{ \begin{matrix}2 (1)_{n−2k}^{∗}, & n > 2k, \\ 3^{k}, & n = 2k, \\ −7 (1)_{n−2k}^{∗}, & n < 2k \end{matrix}

is a hypergeometric term because it satisfies the recurrences

(n − 2k)(n − 2k + 1)T (n + 1, k) = (n − 2k)(n − 2k + 1)^{2}T (n, k),  (7)
(n − 2k − 2)(n − 2k − 1)^{2}(n − 2k)^{2}T (n, k + 1) = (n − 2k − 2)(n − 2k − 1)(n − 2k)T (n, k)  (8)

for all n, k ∈ ℕ. Clearly, T (n, k) is conjugate to the hypergeometric terms T_{1}(n, k) = (1)_{n−2k}, T_{2}(n, k) = (−1)^{n−2k}(2k − n)_{n−2k+1}, and T_{3}(n, k) = (1)_{1,n−2k}^{∗} which satisfy the same first-order recurrences (7) and (8), but it is not equal to either of them modulo an algebraic set.

Identification of multivariate sequences which agree outside an algebraic set is consistent with identification of univariate sequences which agree outside a finite set (cf. [16]). Such identification enables us to regard every rational function R ∈ K(x) as a sequence R(n), without actually having to specify its values at the singular points of R. Therefore, if T is a hypergeometric term satisfying (5), we can write

E_{i}T (n) =_{a} F_{i}(n)T (n)  (9)

where F_{i} = q_{i}/p_{i}, for 1 ≤ i ≤ d. Sometimes these rational functions are called the certificates of T.

Example 4 For the term T (n, k) defined in Example 3, we have T (n + 1, k) =_{a} (n − 2k + 1)T (n, k) and (n − 2k − 1)(n − 2k)T (n, k + 1) =_{a} T (n, k), so its certificates are n − 2k + 1 and 1/((n − 2k − 1)(n − 2k)).

It is clear that the certificates of a hypergeometric term satisfy certain compatibility conditions.

Definition 3 (compatible rational functions) Rational functions F_{1}, F_{2}, …, F_{d} ∈ K(x) are compatible if they satisfy

(E_{j}F_{i}) F_{j} = (E_{i}F_{j}) F_{i}  (10)

for all 1 ≤ i < j ≤ d.

Proposition 4 Let T (n) be a hypergeometric term which satisfies (9). If T ≠_{a} 0 then

(i) F_{1}, F_{2}, …, F_{d} are compatible,

(ii) F_{1}, F_{2}, …, F_{d} are unique.

Proof: (i) From (9) we have

E_{i}E_{j}T (n) = (E_{j}F_{i}(n))(E_{j}T (n)) = (E_{j}F_{i}(n))F_{j}(n)T (n)
= (E_{i}F_{j}(n))(E_{i}T (n)) = (E_{i}F_{j}(n))F_{i}(n)T (n)

for n outside some algebraic set A. Hence (E_{j}F_{i}(n))F_{j}(n) = (E_{i}F_{j}(n))F_{i}(n) on supp T \ A. As this is a non-algebraic set, Proposition 1 implies that (E_{j}F_{i})F_{j} = (E_{i}F_{j})F_{i}.

(ii) Assume that in addition to (9), E_{i}T (n) =_{a} G_{i}(n)T (n) for 1 ≤ i ≤ d. Then F_{i}(n) = G_{i}(n) on supp T \ A, for some algebraic set A. By Proposition 1, F_{i} = G_{i}. □

From Proposition 4(ii) it follows that nontrivial hypergeometric terms T_{1} and T_{2} are conjugate if and only if they have the same certificate.

Obviously every hypergeometric term is conjugate to the zero term, and also to every trivial term. But when restricted to nontrivial terms, this relation is transitive, and hence an equivalence relation:

Proposition 5 Let T_{1}, T_{2}, T_{3} be hypergeometric terms such that T_{1} ≃ T_{2}, T_{2} ≃ T_{3}. If T_{2} ≠_{a} 0 then T_{1} ≃ T_{3}.

Proof: This follows from Proposition 4(ii). □

Definition 4 (holonomic) Let K((x)) denote the field of fractions of the formal power series ring K[[x]]. A sequence T (n) is holonomic if the set of all partial derivatives of its generating function ∑_{n≥0} T (n)x^{n} spans a finite-dimensional subspace of K((x)) over the subfield of rational functions K(x).

Theorem 1 [10, Thm. 3.7] A sequence T (n) is holonomic if and only if there is an s ∈ ℕ such that

(i) for each i ∈ {1, 2, …, d}, there is a nonempty set H_{i} ⊆ {0, …, s}^{d} and a set of univariate polynomials {p_{h,i} ∈ K[x] \ {0}; h ∈ H_{i}} such that

∑_{h∈H_{i}} p_{h,i}(n_{i}) T (n − h) = 0  (11)

for all n ≥ s, and

(ii) if d ≥ 2, each (d−1)-variate sequence a_{i,k}(n_{1}, …, n_{i−1}, n_{i+1}, …, n_{d}) = T (n_{1}, …, n_{i−1}, k, n_{i+1}, …, n_{d}) with 1 ≤ i ≤ d and 0 ≤ k ≤ s − 1 is holonomic.

Note that if the coefficients in (11) are constant we may use the same recurrence for all i ∈ {1, 2, …, d}.

Example 5 The term T (n, k) = \binom{n}{k} is holonomic because it satisfies condition (i) of Theorem 1 with the constant-coefficient recurrence T (n, k) − T (n − 1, k) − T (n − 1, k − 1) = 0 valid for n, k ≥ s = 1. Condition (ii) is satisfied as well because T (n, 0) − T (n − 1, 0) = 0 for n ≥ 1, and T (0, k) = 0 for k ≥ 1.

The term T (n, k) from Example 3 is also holonomic, because it satisfies condition (i) of Theorem 1 with the constant-coefficient recurrence T (n, k −2)−4 T (n−2, k −3)+3 T (n−4, k −4) = 0 valid for n, k ≥ s = 4. Condition (ii) is obviously satisfied as well.

Theorem 2 The product of two holonomic sequences is holonomic.

For a proof, see [10, Thm. 3.8(i)] or [20, Prop. 3.2’].

Definition 5 (factorial term) A sequence T (n) is a factorial term if there are u ∈ K^{d}, p, q ∈ ℕ, α ∈ K^{p+q}, and a_{1}, a_{2}, …, a_{p} ∈ ℤ^{d} such that

T (n) = u^{n} ∏_{i=1}^{p}(α_{i})_{a}_{i}^{T} _{n} ∏_{i=p+1}^{p+q}(α_{i} + a_{i}^{T} n)_{−a_{i}^{T} n}  (12)

for all n ∈ ℕ^{d}.

Definition 6 (proper term) A sequence T is a proper term if there is a polynomial P ∈ K[x] and a factorial term T′ such that

T = P T′.  (13)

Note that the definitions of hypergeometric, holonomic, factorial, and proper terms are all symmetric in the variables n_{1}, n_{2}, …, n_{d}. Hence if T (n) has one of these properties, then so does T (π(n)) where π is any permutation of n.

Theorem 3 Every proper term is hypergeometric and holonomic.

Proof: Let T (n) be a proper term. Then T (n) = P (n)T′(n) where P ∈ K[x] is a polynomial and T′(n) is of the form (12). As a rational function, P (n) is clearly hypergeometric. By using (2) repeatedly, each factor on the right-hand side of (12) is hypergeometric as well. Hence, by Proposition 2, T (n) is hypergeometric.

Similarly, each factor of T (n) satisfies a recurrence with constant coefficients: If r = deg_{n_{1}} P (n) then Δ_{n_{1}}^{r+1}P (n) = 0. Clearly, u^{n+1} = u^{1}u^{n}. If f(n) = (α)_{a^{T} n+c} or f(n) = (α + a^{T} n)_{−(a^{T} n)} then f(n + h) = f(n) where h is any nonzero integer vector orthogonal to a. The same is true of the factors of each (d − 1)- variate sequence T (n_{1}, …, n_{i−1}, k, n_{i+1}, …, n_{d}) where k ∈ ℕ. Thus by Theorem 1, each factor of T (n) is holonomic, hence by Theorem 2, so is T (n). □

For factorial terms, this result can be found in [17], and for proper terms in [20, 19, 14].

Wilf and Zeilberger conjectured [19, p. 585] that the converse of Theorem 3 holds as well. Taken literally, this is not true as we show in Example 6 of Section 3. However, we prove in Theorem 14 a slightly modified version of their conjecture, namely that over an algebraically closed field, every holonomic hypergeometric term is conjugate to a nontrivial proper term.

3 A normal form for rational functions

In this section E denotes the shift operator corresponding to x, so that Ef(x) = f(x+1) for every f ∈ K(x).

Theorem 4 For every rational function F ∈ K(x) there are polynomials a, b, c ∈ K[x] such that

(i) F = \frac{a}{b} · \frac{Ec}{c},

(ii) a ⊥ E^{k}b for all k ∈ ℕ,

(iii) a ⊥ c and b ⊥ Ec.

For a proof, see [13] or [14]. The original version of this theorem (without (iii)) is due to Gosper [6].

Definition 7 (PNF) If a, b, c, F satisfy (i) and (ii) of Theorem 4, then (a, b, c) is a polynomial normal form or PNF of F. A PNF which satisfies (iii) of Theorem 4 is strict.

Lemma 1 If (a, b, c) is a strict PNF of p/q where p, q ∈ K[x], then a | p and b | q.

Proof: We have pbc = aqEc, hence a | pbc and b | aqEc. By (ii) and (iii), a ⊥ bc and b ⊥ aEc, so a | p and b | q. □

In place of (ii), we need the stronger property that a ⊥ E^{k}b for all k ∈ ℤ. To achieve this we allow c to be a rational function.

Definition 8 (shift-reduced) A rational function u ∈ K(x) is shift-reduced if there are a, b ∈ K[x] such that u = a/b and a ⊥ E^{k}b for all k ∈ ℤ.

Theorem 5 For every rational function F ∈ K(x) there are rational functions u, v ∈ K(x) such that

(i) F = u · \frac{Ev}{v},

(ii) u is shift-reduced.

Proof: If F = 0 take u = 0 and v = 1. Otherwise let (a, b, c) be a PNF of F, and (a_{1}, b_{1}, c_{1}) a strict PNF of b/a. We claim that taking u = b_{1}/a_{1}, v = c/c_{1} satisfies (i) and (ii). Indeed,

u · \frac{Ev}{v} = \frac{b_{1}}{a_{1}} · \frac{c_{1}}{Ec_{1}} · \frac{Ec}{c} = \frac{a}{b} · \frac{Ec}{c} = F,

proving (i). Because a_{1} ⊥ E^{k}b_{1} for k ≥ 0, we have b_{1} ⊥ E^{k}a_{1} for k ≤ 0. By Lemma 1, a_{1} | b and b_{1} | a. As a ⊥ E^{k}b for k ≥ 0, it follows that b_{1} ⊥ E^{k}a_{1} for k ≥ 0 as well, proving (ii). □

Definition 9 (RNF) If u, v, F are as in Theorem 5, (u, v) is a rational normal form, or RNF, of F. We denote the set of all RNF’s of F by RNF_{x}(F).

Note that together with an algorithm for computing strict PNF (to be found in [13] or [14]), the proof of Theorem 5 provides an algorithm for computing an element of RNF_{x}(F).

Theorem 6 Let (u, v) and (u_{1}, v_{1}) be two RNF’s of F ∈ K(x)\{0}. Write u = zp/q and u_{1} = z_{1}p_{1}/q_{1} where z, z_{1} ∈ K, p, q, p_{1}, q_{1} ∈ K[x] are monic, p ⊥ q, and p_{1} ⊥ q_{1}. Then z = z_{1}, deg p = deg p_{1}, and deg q = deg q_{1}.

For a proof, see [4].

Example 6 Let T (n, k) = |n − k|. Then (n − k)T (n + 1, k) − (n − k + 1)T (n, k) = 0 and (n − k)T (n, k + 1) − (n − k − 1)T (n, k) = 0 for all n, k ∈ ℕ, so T (n, k) is a hypergeometric term. It is also holonomic as it satisfies condition (i) of Theorem 1 with the constant-coefficient recurrence T (n, k) − T (n − 1, k − 1) = 0 valid for n, k ≥ s = 1, and condition (ii) is obviously satisfied as well.

We claim that |n − k| is not equal to any proper term, not even modulo an algebraic set. To prove this, assume on the contrary that |n − k| =_{a} T′(n, k) where T′(n, k) is a proper term. Let Q ∈ K[x, y] be a nonzero polynomial such that |n − k| Q(n, k) = T′(n, k) Q(n, k) for all n, k ∈ ℕ. Write

T′(n, k) = P (n, k) u^{n}v^{k} ∏_{i=1}^{p}(α_{i})_{a_{i}n+b_{i}k} ∏_{j=1}^{q}(β_{j} + c_{j}n + d_{j}k)_{−(c_{j}n+d_{j}k)}

where P ∈ K[x, y], u, v, α_{i}, β_{j} ∈ K, and a_{i}, b_{i}, c_{j}, d_{j} ∈ ℤ. If (α_{i})_{a_{i}n_{0}+b_{i}k_{0}} = 0 for some n_{0}, k_{0} ∈ ℕ then, by (1), α_{i} ∈ ℤ and either α_{i} > 0 and α_{i} +a_{i}n_{0} +b_{i}k_{0} ≤ 0, or α_{i} ≤ 0 and α_{i} +a_{i}n_{0} +b_{i}k_{0} > 0. In the former case, a_{i} < 0 or b_{i} < 0, so (α_{i})_{a_{i}n+b_{i}k} vanishes on the non-algebraic set {(n, k) ∈ ℕ^{2}; α_{i} + a_{i}n + b_{i}k ≤ 0}. In the latter case, a_{i} > 0 or b_{i} > 0, so (α_{i})_{a_{i}n+b_{i}k} vanishes on the non-algebraic set {(n, k) ∈ ℕ^{2}; α_{i}+a_{i}n+b_{i}k > 0}. In either case, T′(n, k), and hence |n − k| Q(n, k) would vanish on a non-algebraic set, which is false. Hence (α_{i})_{a_{i}n+b_{i}k} ≠ 0 for all n, k ∈ ℕ. In the same way we see that (β_{j} + c_{j}n + d_{j}k)_{−(c_{j}n+d_{j}k)} ≠ 0 for all n, k ∈ ℕ. Therefore we can write

T′(n, k) = P (n, k) u^{n}v^{k} \frac{∏_{i=1}^{p}(α_{i})_{a_{i}n+b_{i}k}}{∏_{j=1}^{q}(β_{j})_{c_{j}n+d_{j}k}} .

Pick n_{0}, k_{0} ∈ ℕ such that n_{0} < k_{0} and Q(n_{0}, k_{0}) ≠ 0. Such n_{0}, k_{0} certainly exist, for otherwise the univariate polynomial Q(n_{0}, k) would be identically zero for each n_{0}, as it would vanish for all k > n_{0}, and hence Q itself would be the zero polynomial. Let t(n) = T′(n, k_{0}) Q(n, k_{0}) = |n − k_{0}| Q(n, k_{0}). This is a univariate hypergeometric term which can be written in the form

t(n) = p(n) w^{n} \frac{∏_{i=1}^{p′}(γ_{i})_{n}}{∏_{j=1}^{q′}(δ_{j})_{n}} , for all n ∈ ℕ,  (14)

where p ∈ K[x], w, γ_{i}, δ_{j} ∈ K, and (γ_{i})_{n}, (δ_{j})_{n} ≠ 0 for all n ∈ ℕ. If γ_{i} − δ_{j} ∈ ℤ then (γ_{i})_{n}/(δ_{j})_{n} is a rational function of n, hence we can rewrite (14) as

t(n) = r(n) w^{n} t′(n), for all n ∈ ℕ,

where r ∈ K(x) is a rational function, and t′(n) is a nonvanishing univariate hypergeometric term whose certificate f′(n) = t′(n + 1)/t′(n) is a shift-reduced rational function. Let f(n) = t(n + 1)/t(n) = |n + 1 − k_{0}| Q(n+1, k_{0})/(|n−k_{0}| Q(n, k_{0})) =_{a} (n+1−k_{0}) Q(n+1, k_{0})/((n−k_{0}) Q(n, k_{0})). Then both (w f′(n), r(n)) and (1, (n−k_{0}) Q(n, k_{0})) belong to RNF_{n}(f). It follows from Theorem 6 that w f′(n) = 1, hence t′(n) = c/w^{n} for all n ∈ ℕ, where c ∈ K \ {0} is a constant, so t(n) = c r(n) for all n ∈ ℕ. But t(n) = |n − k_{0}| Q(n, k_{0}) =_{a} (n − k_{0}) Q(n, k_{0}), therefore by Proposition 1, the two rational functions c r(n) and (n − k_{0}) Q(n, k_{0}) are identical, and t(n) = (n − k_{0}) Q(n, k_{0}) for all n ∈ ℕ. Thus we have |n − k_{0}| Q(n, k_{0}) = (n − k_{0}) Q(n, k_{0}) for all n ∈ ℕ, and in particular, |n_{0} − k_{0}| Q(n_{0}, k_{0}) = (n_{0} − k_{0}) Q(n_{0}, k_{0}). As Q(n_{0}, k_{0}) ≠ 0, it follows that |n_{0} − k_{0}| = n_{0} − k_{0}, contrary to our choice of n_{0} < k_{0}. This contradiction shows that |n − k| is not equal to any proper term, not even modulo an algebraic set. Note however that |n − k| is conjugate to the nontrivial proper term n − k, as well as to any term T′′ of the form

T′′(n, k) = \{ \begin{matrix}a (n − k), & n ≥ k, \\ b (n − k), & n < k \end{matrix}

where a, b ∈ K are arbitrary.

4 Shift invariance and integer linearity

Definition 10 (shift-invariant, pairwise shift-invariant, integer-linear) A rational function f ∈ K(x) is shift-invariant if there is a nonzero integer vector a ∈ ℤ^{d} such that f(x + a) = f(x). A rational function f ∈ K(x) is pairwise shift-invariant if for each pair of indices i, j, 1 ≤ i < j ≤ d, there are h_{ij}, h_{ji} ∈ ℤ, not both zero, such that E_{i}^{h_{ij}}E_{j}^{h_{ji}}f(x) = f(x). A polynomial p ∈ K[x] is integer-linear if p(x) = u · (a^{T} x) + v where a ∈ ℤ^{d} and u, v ∈ K.

Note the following facts:

• If d = 2, the notions of shift invariance and pairwise shift invariance coincide.

• Any constant polynomial is integer-linear (take u = 0).

• Over an algebraically closed field, any univariate polynomial factors into integer-linear factors.

Lemma 2 Let f ∈ K(x), a ∈ K, a ≠ 0. If f(x + a) = f(x) then f(x) = c ∈ K.

Proof: Write f(x) = p(x)/q(x) where p, q ∈ K[x]. Let x_{0} ∈ K be such that q(x_{0} + ka) ≠ 0 for all k ∈ ℕ. By induction on k, f(x_{0} + ka) = f(x_{0}) for all k ∈ ℕ. Write c = f(x_{0}). Then r(x) = p(x) − c q(x) ∈ K[x] vanishes on {x_{0} + ka; k ∈ ℕ}. In characteristic zero this is an infinite set, hence r is the zero polynomial, and f(x) = c as claimed. □

Lemma 3 Let f ∈ K(x), a ∈ K^{d}, a_{d} ≠ 0. If f(x + a) = f(x) then there is a (d − 1)-variate rational function h ∈ K(x_{1}, x_{2}, …, x_{d−1}) such that

f(x) = h(x_{1} − \frac{a_{1}}{a_{d}} x_{d}, …, x_{d−1} − \frac{a_{d−1}}{a_{d}} x_{d}).

Furthermore, if f ∈ K[x] then h ∈ K[x_{1}, x_{2}, …, x_{d−1}].

Proof: Define

h(x) = f(x_{1} + \frac{a_{1}}{a_{d}} x_{d}, …, x_{d−1} + \frac{a_{d−1}}{a_{d}} x_{d}, x_{d}).

Then f(x) = h(x_{1} − \frac{a_{1}}{a_{d}} x_{d}, …, x_{d−1} − \frac{a_{d−1}}{a_{d}} x_{d}, x_{d}) and h(x_{1}, …, x_{d−1}, x_{d} + a_{d}) = h(x). Considering h as an element of K(x_{1}, x_{2}, …, x_{d−1})(x_{d}), Lemma 2 implies that, in fact, h ∈ K(x_{1}, x_{2}, …, x_{d−1}). □

Proposition 6 A d-variate rational function f ∈ K(x) is shift-invariant if and only if there are nonzero integer vectors v_{1}, v_{2}, …, v_{d−1} ∈ ℤ^{d} and a (d − 1)-variate rational function g ∈ K(x_{1}, x_{2}, …, x_{d−1}) such that

f(x) = g(v_{1}^{T} x, v_{2}^{T} x, …, v_{d−1}^{T}x).  (15)

Furthermore, if f ∈ K[x] then g ∈ K[x_{1}, x_{2}, …, x_{d−1}].

Proof: Let a ∈ ℤ^{d} be a nonzero vector such that f(x + a) = f(x). W.l.g. assume that a_{d} ≠ 0. By Lemma 3, there is a (d − 1)-variate rational function h ∈ K(x_{1}, x_{2}, …, x_{d−1}) such that

f(x) = h(x_{1} − \frac{a_{1}}{a_{d}} x_{d}, …, x_{d−1} − \frac{a_{d−1}}{a_{d}} x_{d}).

Then f(x) = g(a_{d}x_{1} − a_{1}x_{d}, a_{d}x_{2} − a_{2}x_{d}, …, a_{d}x_{d−1} − a_{d−1}x_{d}) = g(v_{1}^{T} x, v_{2}^{T} x, …, v_{d−1}^{T}x) where g(x_{1}, x_{2}, …, x_{d−1}) = h(x_{1}/a_{d}, x_{2}/a_{d}, …, x_{d−1}/a_{d}), and v_{i} = a_{d}e_{i} − a_{i}e_{d} ≠ 0.

Conversely, assume that f is of the form (15). Let a ∈ ℤ^{d} be a nonzero integer vector such that v_{1}^{T} a = v_{2}^{T} a = ⋯ = v_{d−1}^{T}a = 0. Then f(x + a) = f(x). □

Proposition 7 A d-variate rational function f ∈ K(x) is pairwise shift-invariant if and only if there is a nonzero integer vector v ∈ ℤ^{d} and a univariate rational function g ∈ K(x) such that

f(x) = g(v^{T} x).

Furthermore, if f ∈ K[x] then g ∈ K[x].

Proof: First let f be pairwise shift-invariant. We prove by induction on d that f(x) = g(v^{T} x).

• d = 1: The assertion holds vacuously.

• d > 1: Consider f as an element of K(x_{d})(x_{1}, …, x_{d−1}). By the induction hypothesis, there are g′ ∈ K(x_{d})(x) and v′_{1}, …, v′_{d−1} ∈ ℤ, not all zero, such that

f(x_{d})(x_{1}, …, x_{d−1}) = g′(x_{d})(u)  (16)

where u = v′_{1}x_{1} + ⋯ + v′_{d−1}x_{d−1}. W.l.g. assume that v′_{1} ≠ 0. Regarding g′ as an element of K(x_{d}, x), we can write (16) as f(x) = g′(x_{d}, u). Now

g′(x_{d}, u) = f(x) = E_{1}^{h_{1d}}E_{d}^{h_{d1}}f(x) = f(x_{d} + h_{d1})(x_{1} + h_{1d}, x_{2}, …, x_{d−1}) = g′(x_{d} + h_{d1}, u + v′_{1}h_{1d}).

By Proposition 6 applied to the bivariate rational function g′, there are g ∈ K(x) and a, b ∈ ℤ not both zero such that

f(x) = g′(x_{d}, u) = g(au + bx_{d}) = g(v^{T} x)

where v = (av′_{1}, …, av′_{d−1}, b) ≠ 0.

Conversely, let f(x) = g(v^{T} x) and 1 ≤ i < j ≤ d. If v_{i} = v_{j} = 0 then set h_{ij} = h_{ji} = 1, otherwise set h_{ij} = v_{j}, h_{ji} = −v_{i}. In both cases E_{i}^{h_{ij}}E_{j}^{h_{ji}}f(x) = f(x). □

Corollary 1 Assume that K is algebraically closed. If p ∈ K[x] is irreducible and pairwise shift-invariant then p is integer-linear.

Proof: By Proposition 7, there is q ∈ K[x] and a nonzero integer vector a ∈ ℤ^{d} such that p(x) = q(a^{T} x). As p is irreducible, so is q, hence deg q ≤ 1. Thus there are c, d ∈ K such that q(x) = cx + d and, consequently, p(x) = c · (a^{T} x) + d. □

Lemma 4 Fix a pair of indices i, j, 1 ≤ i < j ≤ d. If for every irreducible factor p of P ∈ K[x] with deg_{x_{i}} p, deg_{x_{j}} p > 0 there are a, b ∈ ℤ, a > 0, such that E_{i}^{a}E_{j}^{b}p | P, then for every irreducible factor p of P with deg_{x_{i}} p, deg_{x_{j}} p > 0 there are A, B ∈ ℤ, A > 0, such that E_{i}^{A}E_{j}^{B}p = p.

Proof: Pick any irreducible factor p_{0} of P such that deg_{x_{i}} p_{0}, deg_{x_{j}} p_{0} > 0. Construct a sequence of nonconstant irreducible factors p_{l} of P such that p_{l+1} = E_{i}^{a_{l}}E_{j}^{b_{l}}p_{l} where a_{l}, b_{l} ∈ ℤ and a_{l} > 0, for l ≥ 0. As K[x] is a unique factorization domain, there are indices l_{0} < l_{1} such that p_{l_{0}} = p_{l_{1}}. By definition of p_{l}, it follows that

p_{l_{0}} = E_{i}^{A}E_{j}^{B}p_{l_{0}}  (17)

where A = a_{l_{0}} + a_{l_{0}+1} + ⋯ + a_{l_{1}−1} > 0 and B = b_{l_{0}} + b_{l_{0}+1} + ⋯ + b_{l_{1}−1} are integers. We have additionally

p_{l_{0}} = E_{i}^{A′}E_{j}^{B′}p_{0},  (18)

where A′ = a_{0} + a_{1} + ⋯ + a_{l_{0}−1} > 0 and B′ = b_{0} + b_{1} + ⋯ + b_{l_{0}−1} are integers. Applying E_{i}^{−A′}E_{j}^{−B′} to (17) and using (18) we obtain p_{0} = E_{i}^{A}E_{j}^{B}p_{0}. □

Theorem 7 Let K be algebraically closed, and P ∈ K[x]. If for each irreducible factor p of P and for each pair of indices i, j, 1 ≤ i < j ≤ d with deg_{x_{i}} p, deg_{x_{j}} p > 0 there are a, b ∈ ℤ, a > 0, such that E_{i}^{a}E_{j}^{b}p | P, then P factors into integer-linear factors.

Proof: Lemma 4 implies that each irreducible factor of P is pairwise shift-invariant. Hence by Corollary 1, each irreducible factor of P is integer-linear. □

For the case d = 2, a different proof of Theorem 7 using algebraic functions is given in [2, Lemma 3].

5 Compatible rational functions

Theorem 8 [1] Let a, b, u, v ∈ K[x] \ {0}, u ⊥ v, r = u/v, p an irreducible factor of v, and

a(x)r(x + 1) = b(x)r(x).  (19)

Then there are m, n ∈ ℕ, m ≥ 1, n ≥ 0, such that p(x + m) divides a(x) and p(x − n) divides b(x).

Proof: Rewrite (19) as

a(x)u(x + 1)v(x) = b(x)u(x)v(x + 1).  (20)

Let m ∈ ℕ, m ≥ 1, be such that p(x + m − 1) divides v(x) but p(x + m) does not. Then (20) implies that p(x + m) | a(x)u(x + 1)v(x). As p(x + m) ⊥ u(x + 1)v(x), it follows that p(x + m) | a(x).

Let n ∈ ℕ, n ≥ 0, be such that p(x − n) divides v(x) but p(x − n − 1) does not. Then (20) implies that p(x − n) | b(x)u(x)v(x + 1). As p(x − n) ⊥ u(x)v(x + 1), it follows that p(x − n) | b(x). □

The following property of divisibility in K[x] will be used freely.

Proposition 8 Let p, q ∈ K[x], p irreducible, deg_{x_{d}} p ≠ 0. Then p | q in K[x] if and only if p | q in K(x_{1}, …, x_{d−1})[x_{d}].

Proof: Divisibility in K[x] obviously implies divisibility in K(x_{1}, …, x_{d−1})[x_{d}].

Conversely, let q = p r where r ∈ K(x_{1}, …, x_{d−1})[x_{d}]. As p is irreducible in K[x] and deg_{x_{d}} p ≠ 0, p is primitive when considered as an element of K[x_{1}, …, x_{d−1}][x_{d}]. Write r = (α/β) r′, q = γ q′ where α, β, γ ∈ K[x_{1}, …, x_{d−1}] and q′, r′ ∈ K[x_{1}, …, x_{d−1}][x_{d}] are primitive. Then

β γ q′ = α p r′.

By Gauss’s Lemma p r′ is primitive, hence α = β γ. It follows that r = γ r′ ∈ K[x], hence p | q in K[x]. □

Theorem 9 Let F, G ∈ K(x, y) be compatible rational functions. Let (G′, R) be an RNFof G, considered as a rational function of y over K(x), and F′(x, y) = F (x, y)R(x, y)/R(x + 1, y). Then

(i) F (x, y) = F′(x, y)\frac{R(x+1,y)}{R(x,y)},

(ii) G(x, y) = G′(x, y)\frac{R(x,y+1)}{R(x,y)},

(iii) F′, G′ are compatible rational functions,

(iv) each irreducible factor p ∈ K[x, y] of either F′ or G′ is shift-invariant.

Proof: Properties (i) and (ii) follow from the definitions of F′ and G′, respectively. The compatibility condition (10) for F, G implies that

F′(x, y) G′(x + 1, y) = F′(x, y + 1) G′(x, y),  (21)

so F′, G′ are compatible. It remains to prove (iv). Write

F′(x, y) = \frac{s(x, y)}{t(x, y)}, G′(x, y) = \frac{u(x, y)}{v(x, y)}  (22)

where s, t, u, v ∈ K[x, y], s(x, y) ⊥ t(x, y), and u(x, y) ⊥ v(x, y + m) for all m ∈ ℤ.

Let p ∈ K[x, y] be an irreducible factor of s, t, u, or v. If deg_{x} p = 0 or deg_{y} p = 0 then p is trivially shift-invariant. In the case deg_{x} p, deg_{y} p > 0 we use two lemmas.

Lemma 5 Let F′, G′, s, t, u, v be as in (21), (22). If p ∈ K[x, y] is an irreducible factor of uv, deg_{y} p ≠ 0, then there are A, B ∈ ℤ, A > 0, such that p(x + A, y + B) divides st.

Proof: a) If p | v rewrite (21) as

s(x, y)t(x, y + 1)G′(x + 1, y) = s(x, y + 1)t(x, y)G′(x, y).

By Theorem 8, there is m ∈ ℤ, m ≥ 1, such that

p(x + m, y) | s(x, y)t(x, y + 1).

Then p(x+m, y) | s(x, y) or p(x+m, y−1) | t(x, y). Take (A, B) = (m, 0) in the former case, (A, B) = (m, −1) in the latter.

b) If p | u rewrite (21) as

s(x, y + 1)t(x, y)\frac{1}{G′(x + 1, y)} = s(x, y)t(x, y + 1)\frac{1}{G′(x, y)}.

By Theorem 8, there is m ∈ ℤ, m ≥ 1, such that

p(x + m, y) | s(x, y + 1)t(x, y).

Then p(x+m, y−1) | s(x, y) or p(x+m, y) | t(x, y). Take (A, B) = (m, −1) in the former case, (A, B) = (m, 0) in the latter. □

Lemma 6 Let F′, G′, s, t, u, v be as in (21), (22) where G′(x, y) is shift-reduced w.r.t. y. If q ∈ K[x, y] is an irreducible factor of st and deg_{x} q ≠ 0, then there is C ∈ ℤ such that q(x, y + C) divides uv.

Proof: a) If q | t rewrite (21) as

u(x, y)v(x + 1, y)F′(x, y + 1) = u(x + 1, y)v(x, y)F′(x, y).

By Theorem 8, there are m, n ∈ ℤ such that

q(x, y + m) | u(x, y)v(x + 1, y) and q(x, y − n) | u(x + 1, y)v(x, y).

Since u/v is shift-reduced w.r.t. y it follows that q(x, y + m) | u(x, y) or q(x, y − n) | v(x, y). Take C = m in the former case, C = −n in the latter.

b) If q | s rewrite (21) as

u(x + 1, y)v(x, y)\frac{1}{F′(x, y + 1)} = u(x, y)v(x + 1, y)\frac{1}{F′(x, y)}.

By Theorem 8, there are m, n ∈ ℤ such that

q(x, y + m) | u(x + 1, y)v(x, y) and q(x, y − n) | u(x, y)v(x + 1, y).

Since u/v is shift-reduced w.r.t. y it follows that q(x, y + m) | v(x, y) or q(x, y − n) | u(x, y). Take C = m in the former case, C = −n in the latter. □

Proof of Thm. 9 (cont’d): If p is an irreducible factor of uv then by Lemma 5 there are A, B ∈ ℤ, A > 0, such that p(x + A, y + B) divides st. By Lemma 6, there is C ∈ ℤ such that p(x + A, y + B + C) divides uv. Hence by Lemma 4, all irreducible factors of uv are shift-invariant.

If p is an irreducible factor of st then by Lemma 6 there is C ∈ ℤ such that p(x, y + C) divides uv. By Lemma 5, there are A, B ∈ ℤ, A > 0, such that p(x + A, y + B + C) divides st. By Lemma 4, all irreducible factors of st are shift-invariant. □

Corollary 2 Let F, G ∈ K(x, y) be compatible rational functions over an algebraically closed field K. Then F′, G′ ∈ K(x, y) mentioned in Theorem 9 factor into integer-linear factors.

Proof: By Theorem 9 and Corollary 1. □

Theorem 10 Let F_{1}, F_{2}, …, F_{d} ∈ K(x) be compatible rational functions over an algebraically closed field K. Then there are compatible rational functions F′_{1}, F′_{2}, …, F′_{d} ∈ K(x) which factor into integer-linear factors, and a rational function R ∈ K(x) such that F_{i} = F′_{i} · (E_{i}R)/R, for i = 1, 2, …, d.

Proof: We present an algorithm for computing F′_{1}, F′_{2}, …, F′_{d}, and R with desired properties.

Algorithm Multi-RNF

input: compatible functions F_{1}, F_{2}, …, F_{d} ∈ K(x);
output: R, F′_{1}, F′_{2}, …, F′_{d} ∈ K(x) satisfying Theorem 10;

R_{1} := 1;

for i = 1, …, d do

F_{i}^{(1)} := F_{i};

for k = 2, …, d do

select (F_{k}^{(k)}, S_{k}) ∈ RNF_{x_{k}}(F_{k}^{(k−1)});
R_{k} := S_{k}R_{k−1};
for i = 1, …, d, i ≠ k, do
F_{i}^{(k)} := F_{i}^{(k−1)}S_{k}/(E_{i}S_{k});

return R_{d}, F_{1}^{(d)}, …, F_{d}^{(d)}.

We claim that for k = 1, 2, …, d:

(i) F_{1}^{(k)}, F_{2}^{(k)}, …, F_{d}^{(k)} are compatible, (ii) for i = 1, 2, …, d we have F_{i} = F_{i}^{(k)} \frac{E_{i}R_{k}}{R_{k}},

(iii) each irreducible factor of any of F_{1}^{(k)}, …, F_{d}^{(k)} is pairwise shift-invariant as a polynomial in x_{1}, …, x_{k}.

The proof of this claim is by induction on k.

• k = 1: In this case, (i) – (iii) hold trivially.

• k > 1: Assume that (i) – (iii) hold at k − 1.

(i) Multiplying F_{i}^{(k−1)}(E_{i}F_{j}^{(k−1)}) = (E_{j}F_{i}^{(k−1)})F_{j}^{(k−1)} by S_{k}/(E_{i}E_{j}S_{k}) we obtain F_{i}^{(k)}(E_{i}F_{j}^{(k)}) = (E_{j}F_{i}^{(k)})F_{j}^{(k)}.

(ii) F_{i} = F_{i}^{(k−1)} · \frac{E_{i}R_{k−1}}{R_{k−1}} = F_{i}^{(k−1)} · \frac{S_{k}}{E_{i}S_{k}} · \frac{E_{i}S_{k}}{S_{k}} · \frac{E_{i}R_{k−1}}{R_{k−1}} = F_{i}^{(k)} · \frac{E_{i}R_{k}}{R_{k}}.

(iii) Let p be an irreducible factor of F_{i}^{(k)}. By construction, p is a shift of some irreducible factor q of F_{i}^{(k−1)} or F_{k}^{(k−1)}. By the induction hypothesis, for each pair of indices u, v, 1 ≤ u < v ≤ k − 1, there are a, b ∈ ℤ, not both zero, such that E_{u}^{a}E_{v}^{b}q = q. As p is a shift of q, E_{u}^{a}E_{v}^{b}p = p as well. Now let 1 ≤ u < k. By Theorem 9 applied to F_{k}^{(k−1)} as a rational function of x = x_{u}, y = x_{k}, and considering all the other x_{i} as parameters, there are a, b ∈ ℤ, not both zero, such that E_{u}^{a}E_{k}^{b}p = p. This shows that p is pairwise shift-invariant as a polynomial in x_{1}, …, x_{k}.

This finishes the proof of our claim. As K is algebraically closed, it follows from Corollary 1 that each irreducible factor of F_{1}^{(d)} is an integer-linear polynomial in x_{1}, …, x_{d}, hence the claim at k = d implies the correctness of Algorithm Multi-RNF and thus the assertion of the theorem. □

6 The structure of hypergeometric terms

Definition 11 (Z-term) A hypergeometric term T (n) is a Z-term if its certificates F_{i} in (9) factor into integer-linear factors, for i = 1, 2, …, d.

Theorem 11 Let T (n) be a hypergeometric term over an algebraically closed field K. Then there is a rational function R ∈ K(x) and a Z-term T′(n) such that T =_{a} RT′.

Proof: Let F_{i} ∈ K(x), i = 1, …, d, be such that E_{i}T =_{a} F_{i}T, i = 1, …, d, and let R, F′_{1}, …, F′_{d} ∈ K(x) be the rational functions associated with F_{1}, …, F_{d} by Theorem 10. Take any hypergeometric term T′ such that

T′ =_{a} \frac{T}{R}.

Then T =_{a} RT′, and

E_{i}T′ =_{a} \frac{E_{i}T}{E_{i}R} =_{a} F_{i} \frac{R}{E_{i}R} · \frac{T}{R} =_{a} F′_{i} T′, for 1 ≤ i ≤ d.

As F′_{1}, …, F′_{d} factor into integer-linear factors, T′ is a Z-term. □

Definition 12 (uniform term) Let a_{1}, a_{2}, …, a_{d} be relatively prime integers. A Z-term T (n) is uniform of type a = (a_{1}, a_{2}, …, a_{d}) if there are univariate rational functions F_{i} ∈ K(x) such that

E_{i}T (n) =_{a} F_{i}(a^{T} n)T (n)  (23)

for 1 ≤ i ≤ d.

Proposition 9 For every integer vector a = (a_{1}, a_{2}, …, a_{d}) there is an integer matrix A ∈ ℤ^{d×d} such that the first row of A is a, and det A = gcd(a_{1}, a_{2}, …, a_{d}).

Proof: By induction on d.

• d = 1: This is clear, assuming gcd(a) = a.

• d > 1: Write d = gcd(a_{1}, a_{2}, …, a_{d}) and d′ = gcd(a_{1}, a_{2}, …, a_{d−1}). There are u, v ∈ ℤ such that ud′ − va_{d} = gcd(d′, a_{d}) = d. By the induction hypothesis there is a matrix A′ ∈ ℤ^{(d−1)×(d−1)} whose first row equals (a_{1}, a_{2}, …, a_{d−1}) while det A′ = gcd(a_{1}, a_{2}, …, a_{d−1}). Let

a′ A′  u 0 a_{d} A =

where a′ = (v/d′)(a_{1}, a_{2}, …, a_{d−1}). Then the first row of A is a, and

det A = u det A′ + (−1)^{d+1}a_{d}(v/d′)(−1)^{d−2} det A′ = ud′ − va_{d} = d.

□

Theorem 12 If K is algebraically closed, any uniform term T (n) is conjugate to a nontrivial factorial term.

Proof: Let T (n) be a uniform term of type a. By Proposition 9, there is a unimodular integer matrix A ∈ ℤ^{d×d} whose first row is a. Using (23) repeatedly, we find that for fixed u ∈ ℕ,

E_{i}^{u}T (n) =_{a} F_{i,u}(a^{T} n)T (n),  (24)
E_{i}^{−u}T (n) =_{a} F_{i,−u}(a^{T} n)T (n),  (25)

where F_{i,u}(a^{T} n) = ∏_{j=0}^{u−1} E_{i}^{j}F_{i}(a^{T} n) and F_{i,−u}(a^{T} n) = 1/ ∏_{j=1}^{u} E_{i}^{−j}F_{i}(a^{T} n). Let

T′(n) = T (A^{−1}n)  (26)

be a K-valued function defined on the integer cone A^{−1}n ≥ 0. Write n′ = A^{−1}n. Then

E_{i}T′(n) = E_{i}T (A^{−1}n)
=_{a} T (A^{−1}n + ã^{(i)}) = T (n′ + ã^{(i)})  (27)

where ã^{(i)} is the i-th column of A^{−1}. As a^{T} n′ = a^{T} A^{−1}n = n_{1}, we obtain from (27) using (24), (25) that

E_{i}T′(n) = f_{i}(n_{1})T′(n)

for 1 ≤ i ≤ d, where f_{i}(n_{1}) = ∏_{j=1}^{d} F_{j,ã_{j}^{(i)}}(n_{1} + s_{j}) and s_{j} = ∑_{k=j+1}^{d} a_{k}ã_{k}^{(i)}.

From the compatibility condition (10) applied to F_{i} and F_{1} it follows that f_{i}(n_{1}) is constant for 2 ≤ i ≤ d. Factoring f_{1}(x) over K we can write

f_{1}(x) = v_{1} ∏_{i=1}^{p}(x + α_{i}) ∏_{i=p+1}^{p+q}(x + α_{i})^{−1},
f_{i}(x) = v_{i},

where v_{i} ∈ K, p, q ∈ ℕ, and α_{i} ∈ K. Then the sequence

H′(n) = v^{n} ∏_{i=1}^{p}(α_{i})_{n_{1}} ∏_{i=p+1}^{p+q}(α_{i} + n_{1})_{−n_{1}}  (28)

(defined on A^{−1}n ≥ 0) satisfies the same hypergeometric recurrences as T′(n). Using the inverse substitution of (26), we see that T (n) = T′(An) is conjugate to H(n) = H′(An). But

H(n) = u^{n} ∏_{i=1}^{p}(α_{i})_{a}^{T} _{n} ∏_{i=p+1}^{p+q}(α_{i} + a^{T} n)_{−a^{T} n}

(where u_{i} = v^{ã^{(i)}}) is a factorial term. In (28), when α_{i} ∈ ℤ we are free to replace (α_{i})_{n_{1}} by (1)_{α_{i}+n_{1}−1} or by (0)_{α_{i}+n_{1}}. We can do likewise with its pseudoinverse (α_{i} + n_{1})_{−n_{1}}. By a judicious choice between these alternatives we can always make H(n) nontrivial. □

Corollary 3 If K is algebraically closed, any Z-term T (n) is conjugate to a nontrivial factorial term.

Proof: W.l.g. assume that T is nontrivial. Let T (n) be a Z-term such that E_{i}T (n) =_{a} F_{i}(n)T (n). Let F_{i}(x) = F_{1}^{(i)}(x)F_{2}^{(i)}(x) ⋯ F_{m}^{(i)}(x) be a factorization of F_{i} such that F_{k}^{(i)}F_{k}^{(j)} is a uniform rational function for all 1 ≤ k ≤ m and 1 ≤ i ≤ j ≤ d, while F_{k}^{(i)}F_{l}^{(i)} where 1 ≤ i ≤ d and 1 ≤ k < l ≤ m is not (unless one of F_{k}^{(i)}, F_{l}^{(i)} is constant). It follows from the unique factorization of polynomials in K[x] that F_{k}^{(1)}, F_{k}^{(2)}, …, F_{k}^{(d)} are compatible for each k. It can be shown that there are uniform terms T_{k}(n) satisfying E_{i}T_{k}(n) =_{a} F_{k}^{(i)}(n)T_{k}(n). Then T (n) ≃ ∏_{k=1}^{m} T_{k}(n). As in the proof of Theorem 12, we can achieve that T (n) will be nontrivial. Since products of factorial terms are factorial, the claim follows from Theorem 12.

□

Corollary 4 (Ore-Sato Theorem) If K is algebraically closed, any hypergeometric term T (n) is conjugate to R(n)T′(n) where R ∈ K(x) \ {0} is a rational function and T′(n) is a nontrivial factorial term.

Proof: W.l.g. assume that T is nontrivial. By Theorem 11, T =_{a} RT′′ where R ∈ K(x) and T′′ is a Z-term. By Proposition 3, this implies that T ≃ RT′′. By Corollary 3, T′′ ≃ T′ where T′ is a nontrivial factorial term. Then RT′′ ≃ RT′. As RT′′ ≠_{a} 0, it follows by Proposition 5 that T ≃ RT′. □

7 Holonomic hypergeometric terms

Theorem 13 Assume that K is algebraically closed. If a rational sequence R(n) is conjugate to a nontrivial holonomic hypergeometric term T (n) then the denominator of R factors into integer-linear factors.

Proof: We prove this by induction on d.

• d = 1: Every univariate polynomial over an algebraically closed field factors into integer-linear factors.

• d > 1: Write R = P/Q where P, Q ∈ K[x] and P ⊥ Q. Let Q = V W where V, W ∈ K[x] and V is irreducible. We wish to show that V is integer-linear. Denote T′ = T W and R′ = RW = P/V. Then T′ is holonomic hypergeometric, T′ ≠_{a} 0, and T′ ≃ R′. Hence there are F_{i} ∈ K(x) such that both T′ and R′ satisfy (9). By Proposition 1, F_{i} = (E_{i}R′)/R′. Thus for 1 ≤ i ≤ d,

E_{i}T′(n) =_{a} \frac{E_{i}R′(n)}{R′(n)}T′(n).  (29)

We claim that

E_{1}^{−a_{1}} ⋯ E_{d}^{−a_{d}}T′(n) =_{a} \frac{E_{1}^{−a_{1}} ⋯ E_{d}^{−a_{d}}R′(n)}{R′(n)}T′(n)  (30)

for all a_{1}, …, a_{d} ≥ 0. The proof is by induction on a_{1}+⋯+a_{d}. If a_{1}+⋯+a_{d} = 0 then a_{1} = ⋯ = a_{d} = 0 and the claim is trivial. If a_{1} + ⋯ + a_{d} > 0 assume w.l.g. that a_{1} > 0. Then

E_{1}^{−a_{1}} ⋯ E_{d}^{−a_{d}}T′(n) =_{a} \frac{E_{1}^{−a_{1}} ⋯ E_{d}^{−a_{d}}R′(n)}{E_{1}^{−(a_{1}−1)}E_{2}^{−a_{2}} ⋯ E_{d}^{−a_{d}}R′(n)}E_{1}^{−(a_{1}−1)}E_{2}^{−a_{2}} ⋯ E_{d}^{−a_{d}}T′(n)

=_{a} \frac{E_{1}^{−a_{1}} ⋯ E_{d}^{−a_{d}}R′(n)}{E_{1}^{−(a_{1}−1)}E_{2}^{−a_{2}} ⋯ E_{d}^{−a_{d}}R′(n)} \frac{E_{1}^{−(a_{1}−1)}E_{2}^{−a_{2}} ⋯ E_{d}^{−a_{d}}R′(n)}{R′(n)}T′(n)

=_{a} \frac{E_{1}^{−a_{1}} ⋯ E_{d}^{−a_{d}}R′(n)}{R′(n)}T′(n),

using (29) and the induction hypothesis.

As T′ is holonomic, Theorem 1(i) implies that there is an s ∈ ℕ, a nonempty set H_{1} ⊆ {0, …, s}^{d}, and univariate polynomials p_{h,1} ∈ K[x] \ {0} for each h ∈ H_{1} such that

∑_{h∈H_{1}} p_{h,1}(n_{1}) T′(n − h) = 0

for all n ≥ s. Using (30) we see that there is an algebraic set A such that

∑_{h∈H_{1}} p_{h,1}(n_{1}) R′(n − h) = 0

on supp T′ \ A. As this is non-algebraic, Proposition 1 and R′ = P/V imply that

∑_{h∈H_{1}} p_{h,1}(n_{1}) \frac{P (n − h)}{V (n − h)} = 0.  (31)

Pick h_{0} ∈ H_{1} and clear denominators in (31). The factor V (n − h_{0}) appears explicitly in every term except the one with h = h_{0}. Hence V (x − h_{0}) which is irreducible divides

p_{h_{0},1}(x_{1}) P (x − h_{0}) ∏_{{h∈H_{1} \atop h≠h_{0}}} V (x − h).

If it divides p_{h_{0},1}(x_{1}) then V (x) ∈ K[x_{1}]. As it is irreducible, V is integer-linear. Next, V (x − h_{0}) cannot divide P (x − h_{0}) because V | Q and P ⊥ Q, hence it divides one of V (x − h) where h ≠ h_{0}. But then V (x) = V (x + a) where a = h_{0} − h ≠ 0. W.l.g. assume that a_{d} ≠ 0. Then by Lemma 3, there is a (d − 1)-variate polynomial h ∈ K[x_{1}, …, x_{d−1}] such that

V (x) = h(x_{1} − \frac{a_{1}}{a_{d}} x_{d}, …, x_{d−1} − \frac{a_{d−1}}{a_{d}} x_{d}).  (32)

Define R′′(x_{1}, …, x_{d−1}) := R′(x_{1}, …, x_{d−1}, 0) and T′′(n_{1}, …, n_{d−1}) := T′(n_{1}, …, n_{d−1}, 0). Then R′′, T′′ are hypergeometric terms and R′′ ≃ T′′. By Theorem 1(ii), T′′ is holonomic. Therefore by the induction hypothesis, the denominator V (x_{1}, …, x_{d−1}, 0) of R′′ factors into integer-linear factors. From (32) we find

V (x_{1}, …, x_{d−1}, 0) = h(x_{1}, …, x_{d−1}),

hence

h(x_{1}, …, x_{d−1}) = ∏_{i=1}^{r} (u_{i} ∑_{j=1}^{d−1} c_{ij}x_{j} + v_{i})

for some r ∈ ℕ, u_{i}, v_{i} ∈ K, and c_{ij} ∈ ℤ. Now it follows from (32) that

V (x) = ∏_{i=1}^{r} (u_{i} ∑_{j=1}^{d−1} c_{ij} (x_{j} − \frac{a_{j}}{a_{d}} x_{d}) + v_{i}) = \frac{1}{a_{d}^{r}} ∏_{i=1}^{r} (u_{i} ∑_{j=1}^{d−1} c_{ij} (a_{d}x_{j} − a_{j}x_{d}) + a_{d}v_{i}) .

But V is irreducible, so r = 1 and V is integer-linear.

□

Example 7 In the literature, rational sequences such as 1/(n^{2} + k^{2}) [19, p. 586], 1/(n^{2} + k) [10, p. 358] and 1/(nk + 1) [7, Exer. 5.107] are shown to be nonholonomic by various ad hoc arguments. Using Theorem 13, nonholonomicity of these sequences follows from the fact that their denominators do not factor into integer-linear factors. Likewise, the trivariate rational sequence T (n, m, k) = 1/((n − m)(k − m) + 1) is not holonomic by Theorem 13. Note that T (n, m, k) satisfies condition (i) of Theorem 1 with the constantcoefficient recurrence T (n, m, k) − T (n − 1, m − 1, k − 1) = 0 valid for n, m, k ≥ s = 1, but condition (ii) is not satisfied as the bivariate sequence T (n, 0, k) = 1/(nk + 1) is not holonomic. □

Lemma 7 If Q ∈ K[x]\{0} factors into integer-linear factors then the rational sequence 1/Q(n) is conjugate to a nontrivial factorial term.

Proof: Write Q(n) = u ∏_{i=1}^{p} (a_{i}^{T} n + α_{i}) where u ∈ K \ {0}, p ∈ ℕ, α_{i} ∈ K, and a_{i} ∈ ℤ^{d} for 1 ≤ i ≤ p. W.l.g. assume that each a_{i} has at least one positive component. Then

\frac{1}{α_{i} + a_{i}^{T} n} ≃ \{ \begin{matrix}(1)_{a_{i}^{T} n+α_{i}−1}(a_{i}^{T} n + α_{i} + 1)_{−(a_{i}^{T} n+α_{i})}, & if α_{i} ∈ ℤ and a_{i} ≥ 0, \\ (α_{i})_{a}_{i}^{T} _{n}(a_{i}^{T} n + α_{i} + 1)_{−(a_{i}^{T} n+1)}, & otherwise \end{matrix}

where the right-hand side is conjugate to a nontrivial factorial term. It follows that 1/Q(n) is conjugate to a nontrivial factorial term as well. □

Theorem 14 If K is algebraically closed, any holonomic hypergeometric term T (n) is conjugate to a nontrivial proper term.

Proof: W.l.g. assume that T is nontrivial. By Corollary 4, T ≃ RT_{1} where R ∈ K(x, y) \ {0} and T_{1} is a nontrivial factorial term. By changing all rising factorials in T_{1} into their nonvanishing counterparts, we obtain a conjugate holonomic sequence T_{2} which is nowhere zero. Then T ≃ RT_{2} and 1/T_{2} is also holonomic. So R ≃ T/T_{2}. Note that T/T_{2} is nontrivial, and holonomic by Theorem 2. Write R = P/Q where P, Q ∈ K[x, y] and P ⊥ Q. By Theorem 13, Q factors into integer-linear factors. By Lemma 7, 1/Q is conjugate to a nontrivial proper term T_{3}. Thus T ≃ P T_{2}T_{3} which is a nontrivial proper term. □

Acknowledgement

The authors are indebted to S. P. Tsarev for bringing to their attention the references [5, 12, 15]. They also wish to thank F. Chyzak for providing a copy of [11], and J. Gerhard for streamlining the proof of Proposition 6 in the bivariate case.

References

[1] S. A. Abramov, Rational solutions of linear difference and differential equations with polynomial coefficients USSR Comput. Math. Phys. 29, 7–12. Transl. from Zh. vychisl. mat. mat. fyz. 29 (1989), 1611–1620.

[2] S. A. Abramov and H. Q. Le, Applicability of Zeilberger’s algorithm to rational functions, Proc. FPSAC ’00, LNCS, Springer-Verlag, 2000, 91–102.

[3] S. A. Abramov and M. Petkovšek, Proof of a conjecture of Wilf and Zeilberger, Preprint Series of the Institute of Mathematics, Physics and Mechanics 39 (2001) no. 748, Ljubljana, March 9, 2001.

[4] S. A. Abramov and M. Petkovšek, Canonical representations of hypergeometric terms, Proc. FPSAC ’01, University of Arizona, 2001, 1–10.

[5] 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.

[6] R. W. Gosper, Jr., Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75 (1978) 40–42.

[7] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison-Wesley, Reading, Mass., 2nd ed., 1994.

[8] Q.-H. Hou, Algebraic Method in Combinatorics, Ph.D. Thesis, Nankai University, P.R. of China, 2001.

[9] Q.-H. Hou, k-free recurrences of double hypergeometric terms, preprint, 2001.

[10] L. Lipshitz, D-finite power series, J. Algebra 122 (1989) 353–373.

[11] O. Ore, Sur les fonctions hypergéométriques de plusieurs variables, Comptes Rendus 189 (1929) 1238.

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

[13] M. Petkovšek, Hypergeometric solutions of linear recurrences with polynomial coefficients, J. Symb. Comp. 14 (1992) 243–264.

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

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

[16] R. P. Stanley, Differentially finite power series, European J. Combin. 1 (1980) 175–188.

[17] P. Verbaeten, The automatic construction of pure recurrence relations, Proc. EUROSAM ’74, ACM-SIGSAM Bulletin 8 (1974) 96–98.

[18] H. S. Wilf and D. Zeilberger, Rational functions certify combinatorial identities, J. Amer. Math. Soc. 3 (1990) 147–158.

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

[20] D. Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990) 321–368.

[21] D. Zeilberger, A fast algorithm for proving terminating hypergeometric identities, Discrete Math. 80 (1990) 207–211.

[22] D. Zeilberger, The method of creative telescoping, J. Symb. Comp. 11 (1991) 195–204.