Solution Spaces of H-Systems and the Ore-Sato Theorem^{∗}

S. A. Abramov^{†}

Russian Academy of Sciences Dorodnicyn Computing Centre

Vavilova 40, 119991, Moscow GSP-1, Russia

            sabramov@ccas.ru

M. Petkovšek^{‡}

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

                                               marko.petkovsek@fmf.uni-lj.si

Abstract

An H-system is a system of first-order linear homogeneous difference equations for a single unknown function T, with coefficients which are polynomials with complex coefficients. We consider solutions of H-systems which are of the form T : dom(T) → ℂ where either dom(T) = ℤ^{d}, or dom(T) = ℤ^{d} \ S and S is the set of integer singularities of the system. It is shown that any natural number is the dimension of the solution space of some H-system, and that in the case d ≥ 2 there are H-systems whose solution space is infinite-dimensional. The relationships between dimensions of solution spaces in the two cases dom(T) = ℤ^{d} and dom(T) = ℤ^{d} \ S are investigated. Finally we give an appropriate formulation of the Ore-Sato theorem on possible forms of solutions of H-systems in this setting.

Résumé

Par un H-système nous désignons un système des équations aux differences linéaires homogènes pour une seule fonction inconnue T, à coefficients polynomiaux sur le corps des nombres complexes. Nous considérons les solutions des H-systèmes de la forme T : dom(T) → ℂ où soit dom(T) = ℤ^{d}, soit dom(T) = ℤ^{d} \ S, et S est l’ensemble des singularités entières du système. Nous montrons que chaque nombre naturel est égal à la dimension de l’éspace des solutions d’un H-système, et que dans le cas d ≥ 2 il y a des H-systèmes dont la dimension de l’éspace des solutions est infinie. Les rélations entre les dimensions des éspaces des solutions dans les cas dom(T) = ℤ^{d} et dom(T) = ℤ^{d}\S sont recherchées. Enfin nous présentons une formulation propre du théorême d’Ore-Sato sur les formes possibles des solutions des H-systèmes.

1 Introduction

Linear homogeneous recurrence equations with polynomial coefficients and systems of such equations play a significant role in combinatorics and in the theory of hypergeometric functions; the question of the dimension of the space of solutions of such systems is of great importance for many problems.

Let n_{1}, …, n_{d} be variables ranging over the integers and E_{n_{i}} the corresponding shift operators, acting on functions (sequences) of n_{1}, …, n_{d} by E_{n_{i}}f(n_{1}, …, n_{i}) = f(n_{1}, …, n_{i} + 1, …, n_{d}), i = 1, …, d. We consider H-systems, i.e., systems of equations of the form f_{i} E_{n_{i}}T = g_{i}T, where f_{i}, g_{i} ∈ ℂ[n_{1}, …, n_{d}] \ {0} for i = 1, …, d. The notion of singular points (singularities) of such systems can be defined in the usual way. Such singularities make obstacles (sometimes insuperable) for continuation of partial solutions of the system on all of ℤ^{d}.

In this paper we consider two spaces of solutions of H-systems: the space V_{1} of solutions defined everywhere on ℤ^{d}, and the space V_{2} of solutions that are defined at all nonsingular points of ℤ^{d} (more precisely, if W is the set of all solutions of a given system that are defined at least at all non-singular elements of ℤ^{d}, then V_{2} contains the restrictions of all elements of W to the set of all non-singular elements of ℤ^{d}). In Sections 3 and 4 we investigate the dimensions of the spaces V_{1}, V_{2}. It is well known [7] that if (in the case d = 1) one considers the germs of sequences at infinity (i.e., classes of sequences which agree from some point on), then the dimension of the solution space is 1. However, the situation is different with dim V_{1} and dim V_{2}. In Section 3 we prove for the case d = 1 that if the equation has singularities then 1 ≤ dim V_{1} < dim V_{2} < ∞, and for any integers s, t such that 1 ≤ s < t there exists an equation with dim V_{1} = s and dim V_{2} = t (the case where there is no singularity is trivial: dim V_{1} = dim V_{2} = 1). In turn, in Section 4 we show that in the case d > 1 the possibilities are even richer: for any s, t ∈ ℤ_{+} ∪{∞} there exists an H-system with dim V_{1} = s and dim V_{2} = t.

∗The work is partially supported by the ECO-NET program of the French Foreign Affairs Ministry.

†Partially supported by RFBR grant 04-01-00757.

‡Partially supported by MŠZŠ RS under grant P1-0294.

In Section 5 we revisit the Sato-Ore theorem [5, 6, 8] and show that, contrary to some interpretations in the literature (e.g., [3, 4]), this theorem does not imply that any solution of an H-system is of the form

R(n_{1}, …, n_{d})\frac{∏_{i=1}^{p} Γ(a_{i1}n_{1} + … + a_{id}n_{d} + α_{i})}{∏_{j=1}^{q} Γ(b_{j1}n_{1} + … + b_{jd}n_{d} + β_{j})} u_{1}^{n_{1}} ⋯ u_{d}^{n_{d}},  (1)

where R ∈ ℂ(x_{1}, …, x_{d}), a_{ik}, b_{jk} ∈ ℤ, and α_{i}, β_{j} ∈ ℂ (for the case when the solution of the system is holonomic, and R is required to be a polynomial, we have already noted this in [2]). Finally we give an appropriate corollary of the Ore-Sato theorem on possible forms of solutions of systems under consideration.

We write p ⊥ q to indicate that polynomials p, q ∈ ℂ[x_{1}, …, x_{d}] are relatively prime. We call a set A ⊆ ℤ^{d} algebraic if there is a polynomial p ∈ ℂ[x_{1}, …, x_{d}] \ {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. We write T =_{a} T′ if the set {(n_{1}, …, n_{d}) ∈ ℤ^{d}; T (n_{1}, …, n_{d}) ≠ T′(n_{1}, …, n_{d})} is algebraic.

Definition 1 Let E denote the shift operator corresponding to x, so that Ef(x) = f(x + 1) for every f ∈ ℂ(x). A rational function u ∈ ℂ(x) is shift-reduced if there are a, b ∈ ℂ[x] such that u = a/b and a ⊥ E^{k}b for all k ∈ ℤ.

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

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

(ii) u is shift-reduced.

Definition 2 If u, v, F are as in Theorem 1, (u, v) is a rational normal form, or RNF, of F. We denote the set of all RNF’s of F by RNF(F).

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

For proofs of Theorems 1 and 2, see [1].

2 H-systems and their solution spaces

Definition 3 An H-system^{1} is a system of equations

f_{i}(n_{1}, …, n_{d})T (n_{1}, …, n_{i} + 1, …, n_{d}) = g_{i}(n_{1}, …, n_{d})T (n_{1}, …, n_{i}, …, n_{d}),  i = 1, 2, …, d, (2)

where f_{i}, g_{i} ∈ ℂ[n_{1}, …, n_{d}] \ {0} and f_{i} ⊥ g_{i}. We say that a d-variate sequence T (i.e., a function T : dom(T) → ℂ) is a solution of (2) if (2) is satisfied for all (n_{1}, …, n_{i}, …, n_{d}) ∈ dom(T) such that (n_{1}, …, n_{i} + 1, …, n_{d}) ∈ dom(T) as well.

Definition 4 Let A be an H-system of the form (2).

A d-tuple (n_{1}, …, n_{d}) ∈ ℤ^{d} is a trailing integer singularity of A if there exists i, 1 ≤ i ≤ d, such that g_{i}(n_{1}, …, n_{d}) = 0. A d-tuple (n_{1}, …, n_{d}) ∈ ℤ^{d} is a leading integer singularity of A if there exists i, 1 ≤ i ≤ d, such that f_{i}(n_{1}, …, n_{i−1}, n_{i} − 1, n_{i+1}, …, n_{d}) = 0. A d-tuple (n_{1}, …, n_{d}) ∈ ℤ^{d} is an integer singularity of A if it is a leading or a trailing integer singularity of A.

1The prefix “H” refers to Jakob Horn and to the adjective “hypergeometric” as well.

Let S(A) denote the set of all integer singularities of A. Denote by V_{1}(A) the ℂ-linear space of all solutions of A which are defined at all elements of ℤ^{d}, and by V_{2}(A) the ℂ-linear space of all solutions of A which are defined at all elements of ℤ^{d} \ S(A).

We consider only integer singularities here, therefore we will drop the adjective “integer” in the sequel. Sometimes we will also drop the name of the H-system, and will write V_{1}, V_{2} instead of V_{1}(A), V_{2}(A).

Definition 5 Call the two d-tuples (n_{1}, …, n_{d}), (n′_{1}, …, n′_{d}) ∈ ℤ^{d} adjacent if ∑_{i=1}^{d} |n_{i} − n′_{i}| = 1. Call a finite sequence t_{1}, …, t_{k} ∈ ℤ^{d} a path from t_{1} to t_{k} if t_{i} is adjacent to t_{i+1} for all i = 1, …, k − 1. Given an H-system A, we define components induced by A on ℤ^{d} as the equivalence classes of the following equivalence relation ∼ in ℤ^{d}: t′ ∼ t′′ iff there exists a path from t′ to t′′ which contains no singularity of A. If T is a solution of an H-system A, then its constituent is the sequence that is the restriction of T on a component induced by A.

Definition 6 Rational functions F_{1}, …, F_{d} ∈ ℂ(n_{1}, …, n_{d}) are consistent if

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

for all 1 ≤ i ≤ j ≤ d.

Note that a single rational function (corresponding to the case d = 1) is always consistent.

Proposition 1 Let A be an H-system of the form (2) where g_{1}/f_{1}, …, g_{d}/f_{d} are consistent rational functions. Then dim V_{2} is equal to the number of components induced by A.

Proof: To each component C_{i} induced by A on ℤ^{d} we assign a solution T_{i} of (2) which is 1 at a selected point p_{i} ∈ C_{i}, and 0 on all the remaining components. The values of T_{i} on the remaining points of C_{i} are uniquely determined by (2). It is clear that the set of all T_{i} is a basis for V_{2}. □

3 Dimensions of solution spaces: The univariate case

When d = 1 the system (2) is of the form

f(n)T (n + 1) = g(n)T (n)  (3)

where f(n), g(n) ∈ ℂ[n] \ {0} and f(n) ⊥ g(n).

Example 1 (dim V_{1} = 1, dim V_{2} = k) Consider the recurrence

T (n + 1) = p_{k}(n) T (n)  (4)

where k ≥ 1 and p_{k}(n) = ∏_{i=0}^{k−2}(n − 2i + 1). Here we use the convention that a product is 1 if its lower limit exceeds its upper limit. Clearly the set of singularities of (4) is {2i − 1; i = 0, 1, …, k − 2}, so dim V_{2} = k. To compute dim V_{1}, note that any solution T (n) of (4) defined for all n ∈ ℤ is a constant multiple of

F_{k}(n) = \{ \begin{matrix}(−1)^{(k−1)n}/∏_{i=0}^{k−2}(2i − n − 1)!, & n < 0, \\ 0, & n ≥ 0. \end{matrix}

Therefore dim V_{1} = 1.

Example 2 (dim V_{1} = m, dim V_{2} = m + 1) Now consider the recurrence

q_{m}(n + 1) T (n + 1) = q_{m}(n) T (n)  (5)

where m ≥ 1 and q_{m}(n) = ∏_{i=1}^{m}(n + 2i + 1). The set of singularities is {−(2i + 1); i = 1, 2, …, m}, so dim V_{2} = m + 1. Let T (n) be a solution of (5) defined for all n ∈ ℤ. By substituting n = −2(i + 1) for i = 1, 2, …, m into (5), we see that T (n) = 0 for these values of n. Likewise, by substituting n = −3 into (5), we find that T (−2) = 0. Using (5) it follows by induction on n that T (n) = 0 for all n ≤ −2(m + 1) and for all n ≥ −2 as well. On the other hand, it is easy to check that

G_{m}^{(i)}(n) = δ_{n,−(2i+1)}

(where δ is the Kronecker delta) is a solution of (5) for i = 1, 2, …, m. Therefore dim V_{1} = m.

Before describing the general situation we need a definition and a lemma.

Definition 7 Let A be an H-system of the form (3). An interval of integers

I = {k, k + 1, …, k + m}, m ≥ 0,  (6)

is a segment of singularities of A if I ⊆ S(A) while k − 1, k + m + 1 ∉ S(A).

Lemma 1 Each segments of singularities (6) of equation (3) is of one of the following types:

(i) all elements of the segment are trailing singularities;

(ii) all elements of the segment are leading singularities;

(iii) there exists j, 0 ≤ j < m, such that k, k+1, …, k+j are leading singularities, while k+j +1, …, k+m are trailing singularities.

Proof: If u ∈ ℤ is a trailing singularity and u + 1 a leading singularity of (3) then f(u) = g(u) = 0, contrary to the assumption f ⊥ g. So any segment of singularities of (3) consists of a (possiby empty) interval of leading singularities followed by a (possiby empty) interval of trailing singularities. □

Theorem 3 Let S denote the set of singularities of equation (3).

a) If S = ∅ then dim V_{1} = dim V_{2} = 1.

b) If S ≠ ∅ then 1 ≤ dim V_{1} < dim V_{2} < ∞.

Proof: a) This is clear.

b) There is only a finite set of components induced on ℤ by (3), therefore dim V_{2} < ∞.

Next we prove that dim V_{1} < dim V_{2}. First we show that if (6) is a segment of singularities of (3), then the restriction of V_{1} to

Î = {k − 1, k, , …, k + m, k + m + 1}

has dimension ≤ 1, while the analogous restriction of V_{2} has dimension 2. Indeed, if u is a trailing singularity, then any sequence from V_{1} vanishes at u + 1; and if u is a leading singularity, then any sequence from V_{1} vanishes at u − 1. By Lemma 1 we have three possibilities (i), (ii), (iii) for (6). In case (i) we have T (k + 1) = T (k + 2) = … = T (k + m + 1) = 0, in case (ii) T (k − 1) = T (k) = … = T (k + m − 1) = 0, in case (iii) T (k − 1) = T (k) = … T (k + j − 1) = 0 and T (k + j + 1) = T (k + j + 2) = … = T (k + m + 1) = 0; in each case T (n) can be nonzero at most in two points of Î, however the value at one of them is uniquely determined by the value at the other one. Therefore the dimension of the restricted V_{1} is ≤ 1. The same holds for dimension of the restriction of V_{1} to the set

{k − v, k − v + 1, …, k, k + 1, …, k + m, k + m + 1, …, k + w},

where k, k + 1, …, k + m are singularities, while k − v, …, k − 1 and k + m + 1, …, k + w are not. Gluing together two such restrictions with coinciding, say, k + m + 1, …, k + w, and non-intersecting singular parts, we get the dimension ≤ 2, while the dimension of the corresponding restriction of V_{2} is 3 and so on. This proves that dim V_{1} < dim V_{2}.

Finally we prove that if the set of singularities is not empty, then dim V_{1} ≥ 1. If there is a segment of singularities of type (iii) then V_{1} contains a solution T (n) such that T (n + j) = 1 and T (n) = 0 when n ≠ k + j and n ≠ k + j + 1. If all the segments are of types (i) and (ii), then either the segment with the minimal k is of type (i), or the segment with the maximal k is of type (ii), or there is a segment of type (ii) immediately followed by a segment of type (i). In each of the cases V_{1} contains a nonzero solution. □

Theorem 4 For any integers s, t such that 1 ≤ s < t there exists an equation of the form (3) such that dim V_{1} = s and dim V_{2} = t.

Proof: Consider the recurrence

q_{m}(n + 1) T (n + 1) = p_{k}(n)q_{m}(n) T (n)  (7)

where k, m ≥ 1, p_{k}(n) is as in Example 1, and q_{m}(n) is as in Example 2. Here the set of singularities is {2i − 1; i = 0, 1, …, k − 2} ∪ {−(2i + 1); i = 1, 2, …, m}, so dim V_{2} = k + m. Let T (n) be a solution of (7) defined for all n ∈ ℤ. In exactly the same way as in Example 2 we can see that T (n) = 0 for n = −2, −4, …, −2(m + 1), n ≤ −2(m + 1) or n ≥ −2, and that G_{m}^{(i)}(n) = δ_{n,−(2i+1)} is a solution of (7) for i = 1, 2, …, m. Therefore dim V_{1} = m.

If 1 ≤ s < t, let m = s and k = t − s. Then for equation (7), dim V_{1} = m = s and dim V_{2} = k + m = t. □

We conclude this section by remarks on computation of dim V_{1} and dim V_{2}. Let A denote equation (3). According to Proposition 1, dim V_{2}(A) is the number of components induced on ℤ by A and is thus easy to compute. We claim that dim V_{1}(A) equals the dimension of the kernel of a bidiagonal matrix B defined as follows. Let α be the maximum and β the minimum of the integer roots of f(x)g(x); if A has no integer singularities then we can take α = β = 1. Let B be the (α − β + 1) × (α − β + 2) matrix with entries

b_{i,j} = \{ \begin{matrix}f(α − i + 1), & j = i, \\ −g(α − i + 1), & j = i + 1, \\ 0, & otherwise, \end{matrix}

where 1 ≤ i ≤ α − β + 1 and 1 ≤ j ≤ α − β + 2. Indeed, any vector v such that Bv = 0 can be extended to a solution of A in a unique way. This mapping is an isomorphism between the kernel of B and V_{1}(A).

Incidentally, this gives an alternative proof of the inequality dim V_{1} ≥ 1: B has more columns than rows, hence its kernel is nontrivial.

4 Dimensions of solution spaces: The multivariate case

If d ≥ 2 in (2) then the dimensions of V_{1} and/or V_{2} can be infinite as shown by the following examples.

Example 3 (dim V_{1} = ∞, dim V_{2} = 1) Let A be the system

(n_{1} − 4n_{2} + 1)T (n_{1} + 1, n_{2}) = (n_{1} − 4n_{2})T (n_{1}, n_{2}),
(n_{1} − 4n_{2} − 4)T (n_{1}, n_{2} + 1) = (n_{1} − 4n_{2})T (n_{1}, n_{2}).

It is easy to check that

T_{i}(n_{1}, n_{2}) = δ_{n_{1},4i}δ_{n_{2},i}, for i ∈ ℤ,

are linearly independent solutions of A on all of ℤ^{2}, hence dim V_{1} = ∞. On the other hand, S(A) = {(n_{1}, n_{2}); n_{1} = 4n_{2}}, so A induces a single component on ℤ^{2}, and dim V_{2} = 1.

Example 4 (dim V_{1} = 1, dim V_{2} = ∞) Let B be the system

(n_{1} − 4n_{2})T (n_{1} + 1, n_{2}) = (n_{1} − 4n_{2} + 1)T (n_{1}, n_{2}),
(n_{1} − 4n_{2})T (n_{1}, n_{2} + 1) = (n_{1} − 4n_{2} − 4)T (n_{1}, n_{2}).

It can be shown that any solution of B defined on all ℤ^{2} is a constant multiple of n_{1} − 4n_{2}, so dim V_{1} = 1. On the other hand, S(B) = {(n_{1}, n_{2}); n_{1} − 4n_{2} ∈ {−4, −1, 1, 4}}, so each of the points (4i, i) for i ∈ ℤ is a separate component of ℤ^{2} induced by B, hence dim V_{2} = ∞.

Example 5 (dim V_{1} = dim V_{2} = ∞) Let C be the system

(n_{1} − n_{2} − 1)(n_{1} − n_{2} + 1)T (n_{1} + 1, n_{2}) = (n_{1} − n_{2})(n_{1} − n_{2} + 2)T (n_{1}, n_{2}),
(n_{1} − n_{2} − 1)(n_{1} − n_{2} + 1)T (n_{1}, n_{2} + 1) = (n_{1} − n_{2})(n_{1} − n_{2} − 2)T (n_{1}, n_{2}).

It is easy to check that

T_{i}(n_{1}, n_{2}) = δ_{n_{1},i}δ_{n_{2},i},  for i ∈ ℤ,  (8)

are linearly independent solutions of C on all of ℤ^{2}, hence dim V_{1} = ∞. As S(C) = {(n_{1}, n_{2}); n_{1} − n_{2} ∈ {−2, 0, 2}}, each of the points (i, i − 1) and (i, i + 1) for i ∈ ℤ is a separate component of ℤ^{2} induced by C, so dim V_{2} = ∞ as well.

The following theorem describes the general situation.

Theorem 5 Let 1 ≤ s, t ≤ ∞. Then there exists an H-system such that dim V_{1} = s and dim V_{2} = t.

Proof: Let t ≥ 2 and p_{t}(n_{1}, n_{2}) = ∏_{i=0}^{t−2}(n_{1} − n_{2} + 3i). Then the set of singularities of

p_{t}(n_{1} + 1, n_{2})T (n_{1} + 1, n_{2}) = p_{t}(n_{1}, n_{2})T (n_{1}, n_{2}),
p_{t}(n_{1}, n_{2} + 1)T (n_{1}, n_{2} + 1) = p_{t}(n_{1}, n_{2})T (n_{1}, n_{2})

is S = {(n_{1}, n_{2}); n_{1}−n_{2} ∈ {−3i; 0 ≤ i ≤ t−2}}. As in Example 5, the functions (8) are linearly independent solutions of this system on all of ℤ^{2}, hence dim V_{1} = ∞. On the other hand, the number of components induced on ℤ^{2} is t, so dim V_{2} = t.

Let s ≥ 2 and

q_{s}(n_{1}, n_{2}) = ∏_{i=1}^{s−1}((n_{1} − 2i)^{2} + n_{2}^{2}).  (9)

Then the set of singularities of

(n_{1} − 4n_{2})q_{s+1}(n_{1} + 1, n_{2})T (n_{1} + 1, n_{2}) = (n_{1} − 4n_{2} + 1)q_{s+1}(n_{1}, n_{2})T (n_{1}, n_{2}),
(n_{1} − 4n_{2})q_{s+1}(n_{1}, n_{2} + 1)T (n_{1}, n_{2} + 1) = (n_{1} − 4n_{2} − 4)q_{s+1}(n_{1}, n_{2})T (n_{1}, n_{2})

is S = {(n_{1}, n_{2}); n_{1} − 4n_{2} ∈ {−4, −1, 1, 4}} ∪ {(2i, 0); 1 ≤ i ≤ s}. Each of the points (4i, i) for i ∈ ℤ is a separate component, so dim V_{2} = ∞. It can be shown that any solution T (n_{1}, n_{2}) defined on all ℤ^{2} vanishes everywhere except at the points (2i, 0) where 1 ≤ i ≤ s, and that

T_{i}(n_{1}, n_{2}) = δ_{n_{1},2i}δ_{n_{2},0},  (10)

for i = 1, 2, …, s, are linearly independent solutions of this system defined on all ℤ^{2}. Hence dim V_{1} = ∞. Together with Examples 3 – 5 this proves the assertion in the case when at least one of s, t is infinite. Now assume that s, t are natural numbers, and let r_{t}(n_{1}, n_{2}) = ∏_{i=1}^{t−1}(n_{1} + 2i + 1). Consider the system

q_{s}(n_{1} + 1, n_{2})T (n_{1} + 1, n_{2}) = q_{s}(n_{1}, n_{2})r_{t}(n_{1}, n_{2})T (n_{1}, n_{2}),
q_{s}(n_{1}, n_{2} + 1)T (n_{1}, n_{2} + 1) = q_{s}(n_{1}, n_{2})T (n_{1}, n_{2}),

where q_{s} is as in (9). It can be shown that any solution T (n_{1}, n_{2}) defined on all ℤ^{2} vanishes for all (n_{1}, n_{2}) such that n_{1} > −(2t − 1) and (n_{1}, n_{2}) is not of the form (2i, 0) with 1 ≤ i ≤ s − 1. Further, a basis of V_{1} is given by the s functions T_{i}(n_{1}, n_{2}) for i = 0, 1, …, s − 1 where

T_{0}(n_{1}, n_{2}) = \{ \begin{matrix}\frac{(−1)^{(t−1)n_{1}}}{∏_{i=1}^{s−1}((n_{1}−2i)^{2}+n_{2}^{2}) ∏_{i=1}^{t−1}(−n_{1}−2i−1)!}, & n_{1} ≤ −(2t − 1), \\ 0, & otherwise, \end{matrix}

and T_{i}(n_{1}, n_{2}) are as in (10) for i = 1, 2, …, s − 1. It follows that dim V_{1} = s. The set of singularities of this system is S = {(2i, 0); 1 ≤ i ≤ s − 1} ∪ {(−(2i + 1), j); 1 ≤ i ≤ t − 1, j ∈ ℤ}, and the number of components induced on ℤ^{2} is t, so dim V_{2} = t as desired. □

We considered the case d = 2 here. The corresponding H-systems for the case of an orbitrary d > 1 can be obtained by adding equations E_{n_{i}}T = T, i = 3, …, d, to the systems with d = 2.

5 The Ore-Sato theorem and its consequences

The well-known Ore-Sato theorem (see [5], [6], [8]) is commonly believed to imply that any solution of an H-system (2) is of the form (1). We show that this is not so, and give an appropriate corollary of the Ore-Sato theorem on possible forms of solutions of H-systems in our setting.

Definition 8 Let T be a solution of (2). We write supp T for the support of T, i.e., for the set of points in ℤ^{d} where T is defined and does not vanish.

If (2) has a solution with non-algebraic support, then the rational functions f_{i}/g_{i}, i = 1, …, d, are consistent, and uniquely determined by this solution (see [2]).

Definition 9 A polynomial p ∈ ℂ[x_{1}, …, x_{d}] is integer-linear if p(x_{1}, …, x_{d}) = a_{0} +a_{1}x_{1} +⋯+a_{d}x_{d} where a_{1}, …, a_{d} ∈ ℤ.

The Ore-Sato theorem states (in the case d = 2) that for any consistent rational functions F_{1}(x, y) and F_{2}(x, y) there are consistent rational functions G_{1}(x, y) and G_{2}(x, y) which factor into integer-linear factors, and a rational function R(x, y) such that F_{1}(x, y) = G_{1}(x, y)R(x + 1, y)/R(x, y) and F_{2}(x, y) = G_{2}(x, y)R(x, y + 1)/R(x, y). The full statement gives a precise description of the integer-linear factors.

In the literature one often encounters the claim that as a corollary of this theorem, any solution of an H-system (2) is of the form (1). For example, in [3, p. 223] one can read: “From Ore’s result it can be deduced that the most general form of A_{mn} is of the form

A_{mn} = R(m, n)γ_{mn}a^{m}b^{n}

where R is a fixed rational function of m and n, a and b are constants, and γ_{mn} is a gamma product (…) that is to say it is of the form

γ_{mn} = ∏_{i} Γ(a_{i} + u_{i}m + v_{i}n)/Γ(a_{i})

where the a_{i} are arbitrary (real or complex) constants, and the u_{i} and v_{i} are arbitrary integers which may be positive, negative, or zero.” A similar quote can be found in [4, p. 5].

It may be the case that in the literature referred to above the term A_{mn} is implicitly assumed to be nonzero for all m, n ∈ ℤ. This possibility is supported by the fact that, e.g., in [3] the corresponding H-system is given in terms of the two quotients A_{m+1,n}/A_{mn} and A_{m,n+1}/A_{mn}. But such a severe restriction would preclude many important functions from being hypergeometric, such as the binomial coefficient T (n_{1}, n_{2}) = \binom{n_{1}}{n_{2}}, and all polynomials with integer roots.

However if we do not adopt this restriction, then there are hypergeometric terms which cannot be written in the form (1), as illustrated by the following examples.

Example 6 Take the H-system

p(n_{1}, n_{2})T (n_{1} + 1, n_{2}) = p(n_{1} + 1, n_{2})T (n_{1}, n_{2}),  (11)
p(n_{1}, n_{2})T (n_{1}, n_{2} + 1) = p(n_{1}, n_{2} + 1)T (n_{1}, n_{2}),

where p(n_{1}, n_{2}) = (n_{1}−n_{2}−1)(n_{1}−n_{2}+1). It can be checked that any sequence T which satisfies T (n_{1}, n_{2}) = 0 unless n_{1} = n_{2} is a solution of (11). In particular, the sequence

T (n_{1}, n_{2}) = \{ \begin{matrix}2^{n_{1}^{2}}, & n_{1} = n_{2}, \\ 0, & otherwise, \end{matrix}

is a solution of (11), even though it does not have the form (1) because it grows too fast along the diagonal.

There are examples which look less artificial and where the solution has a non-algebraic support.

Example 7 Let T (n_{1}, n_{2}) = |n_{1} − n_{2}|. Then

(n_{1} − n_{2})T (n_{1} + 1, n_{2}) = (n_{1} − n_{2} + 1)T (n_{1}, n_{2}),  (12)
(n_{1} − n_{2})T (n_{1}, n_{2} + 1) = (n_{1} − n_{2} − 1)T (n_{1}, n_{2})

for all n_{1}, n_{2} ∈ ℤ, so T (n_{1}, n_{2}) is a hypergeometric term. It is also holonomic as its generating function is rational

∑_{n_{1},n_{2}≥0} |n_{1} − n_{2}|z_{1}^{n_{1}}z_{2}^{n_{2}} = (\frac{z_{1}}{(1 − z_{1})^{2}} + \frac{z_{2}}{(1 − z_{2})^{2}} ) \frac{1}{1 − z_{1}z_{2}} .  (13)

We claim that |n_{1} − n_{2}| is not equal to any term of the form (1), not even modulo an algebraic set. To prove this, assume on the contrary that |n_{1} − n_{2}| =_{a} T′(n_{1}, n_{2}) where T′(n_{1}, n_{2}) is of the form (1). Then there is a nonzero polynomial P ∈ ℂ[x, y] such that |n_{1} − n_{2}| P (n_{1}, n_{2}) = T′(n_{1}, n_{2}) P (n_{1}, n_{2}) for all n_{1}, n_{2} ∈ ℤ. Write

T′(n_{1}, n_{2}) = R(n_{1}, n_{2}) u^{n_{1}}v^{n_{2}} \frac{∏_{i=1}^{p} Γ(a_{i}n_{1} + b_{i}n_{2} + α_{i})}{∏_{j=1}^{q} Γ(c_{j}n_{1} + d_{j}n_{2} + β_{j})}

where R ∈ ℂ(x, y), u, v, α_{i}, β_{j} ∈ ℂ, and a_{i}, b_{i}, c_{j}, d_{j} ∈ ℤ.

Pick k_{1}, k_{2} ∈ ℤ such that k_{1} < k_{2} and P (k_{1}, k_{2}) ≠ 0. Such k_{1}, k_{2} certainly exist, for otherwise the univariate polynomials p_{k_{1}}(n_{2}) = P (k_{1}, n_{2}) would be identically zero for each k_{1}, as they would vanish for all n_{2} > k_{1}, and hence P itself would be the zero polynomial. Let t(n_{1}) = T′(n_{1}, k_{2}) P (n_{1}, k_{2}) = |n_{1} − k_{2}| P (n_{1}, k_{2}). It can be verified that for n ∈ ℤ, a ∈ ℤ \ {0} and z ∈ ℂ such that an + z is not a negative integer,

Γ(an + z) = \{ \begin{matrix}Ca^{an} ∏_{i=0}^{a−1} Γ(n + (z + i)/a), & a ∈ ℤ, a > 0, \\ Ca^{an}/ ∏_{i=1}^{|a|} Γ(n + (z − i)/a), & a ∈ ℤ, a < 0, \end{matrix}

where C ∈ ℂ is independent of n. Therefore t can be written in the form

t(n_{1}) = r(n_{1}) w^{n_{1}} \frac{∏_{i=1}^{p′} Γ(n_{1} + γ_{i})}{∏_{j=1}^{q′} Γ(n_{1} + δ_{j})}, for all n_{1} ∈ ℤ,  (14)

where r ∈ ℂ(x) and w, γ_{i}, δ_{j} ∈ ℂ. If γ_{i} − δ_{j} ∈ ℤ then Γ(n_{1} + γ_{i})/Γ(n_{1} + δ_{j}) is a rational function of n_{1}, hence we can rewrite (14) as

t(n_{1}) = s(n_{1}) w^{n_{1}} t′(n_{1}), for all n_{1} ∈ ℤ,

where s ∈ ℂ(x) and f′(n_{1}) := t′(n_{1} + 1)/t′(n_{1}) is a shift-reduced rational function. Let

f(n_{1}) =_{a} \frac{t(n_{1} + 1)}{t(n_{1})} =_{a} \frac{|n_{1} + 1 − k_{2}|}{|n_{1} − k_{2}|} \frac{P (n_{1} + 1, k_{2})}{P (n_{1}, k_{2})}
=_{a} \frac{n_{1} + 1 − k_{2}}{n_{1} − k_{2}} \frac{P (n_{1} + 1, k_{2})}{P (n_{1}, k_{2})}.

Then both (w f′(n_{1}), r(n_{1})) and (1, (n_{1} − k_{2}) P (n_{1}, k_{2})) belong to RNF(f). It follows from Theorem 2 that w f′(n_{1}) = 1, hence t′(n_{1}) = c/w^{n_{1}} for all n_{1} ∈ ℤ, where c ∈ ℂ \ {0} is a constant, so t(n_{1}) = c s(n_{1}) for all n_{1} ∈ ℤ. But t(n_{1}) = |n_{1} − k_{2}| P (n_{1}, k_{2}) = (n_{1} − k_{2}) P (n_{1}, k_{2}) for all n_{1} ≥ k_{2}, therefore the two rational functions c s(n_{1}) and (n_{1}−k_{2}) P (n_{1}, k_{2}) agree infinitely often and so must be identical. Thus t(n_{1}) = (n_{1} −k_{2}) P (n_{1}, k_{2}) = |n_{1} −k_{2}| P (n_{1}, k_{2}) for all n_{1} ∈ ℤ. In particular, |k_{1} −k_{2}| P (k_{1}, k_{2}) = (k_{1} −k_{2}) P (k_{1}, k_{2}). As P (k_{1}, k_{2}) ≠ 0, it follows that |k_{1} − k_{2}| = k_{1} − k_{2}, contrary to our choice of k_{1} < k_{2}. This contradiction proves our claim.

In the theory of multivariate hypergeometric series H-systems are used to specify coefficients for such series. The simple rational function in the right-hand side of (13) has series expansion whose coefficients satisfy the H-system (12), however are not of the form (1).

The following statement is a corollary of the Ore-Sato theorem.

Corollary 1 Any constituent (see Definition 5) of a solution with non-algebraic support of an H-system (2) is of the form (1).

References

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

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

[3] H. Bateman, A. Erdelyi, Higher Transcendental Functions, Vol. 1, McGraw-Hill, New York–Toronto– London 1953.

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

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

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

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

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