Finite Singularities and Hypergeometric Solutions of Linear Recurrence Equations

Mark van Hoeij

October 22, 1997

Abstract

In this paper the notion of finite singularities of difference operators is introduced. An application is given, namely a new algorithm for computing hypergeometric solutions of difference equations.

1 Introduction

The goal of this paper is to introduce the notion of finite singularities of difference equations (recurrence equations) and to give some of their properties. So far only the singularity at infinity has been studied because that is the only point in P^{1}(C) which is invariant under the shift operator τ, where τ(x) = x+1. Since x ↦ x+1 does not leave the elements of C invariant, the finite singularities should be elements of C/ZZ instead of C.

In the theory of differential operators, a singularity p is studied by considering differential operators over C((x − p)), or C((1/x)) if p = ∞. The shift operator τ : C(x) → C(x) can be extended to C((1/x)) but not to C((x−p)) for p ∈ C, and so for finite singularities we can not use a construction similar to the one in the differential case. For a finite singularity p = q+ZZ ∈ C/ZZ where q ∈ C we will consider left solutions u : {q − M, q − (M + 1), q − (M + 2), …} → C and right solutions u : {q + M, q + M + 1, q + M + 2, …} → C of the difference equation, where M is a sufficiently large integer. We will show how one can obtain right solutions from left solutions by deforming the difference equation with x ↦ x + ϵ. After the deformation the left solutions are defined over the field of constants C(ϵ), and a 1-1 map from these left solutions to the corresponding right solutions can be given. Then one can study the difference in ϵ-valuation between these left and right solutions. That yields integers about the singularity p which are useful for efficient computation of hypergeometric solutions.

Furthermore we can also use this construction to define a map from the left solutions to the right solutions of the original (not deformed) equation. This map will in general not be 1-1. If it is 1-1 then after a transformation the singularity can be discarded, similar to the differential case where semi-regular points can be discarded in Beke’s algorithm (c.f. section 4 in [7]). The kernel and image of this map can sometimes be used for computing hypergeometric solutions as well. We also give two relations between infinite and finite singularities in the case of an equation of order 1, similar to Fuchs’ relation in the differential case.

2 Preliminaries and definitions

Let W be the set of all functions to C that are defined on some subset of C. Let k = C(x) and τ the C-automorphism of k defined by τ(x) = x + 1. A difference operator is an operator

L = a_{n}τ^{n} + ⋯ a_{0}τ^{0}  (1)

that acts in the following way on f ∈ W

(L(f))(x) = a_{n}f(x + n) + ⋯ + a_{0}f(x).

In this paper the coefficients a_{i} will be elements of k. The function L(f) ∈ W is defined for those x ∈ C for which f(x), …, f(x + n) and a_{0}(x), …, a_{n}(x) are defined. If a_{n} ≠ 0 then n is called the order of L.

The set of all difference operators is

k[τ] = {a_{n}τ^{n} + ⋯ a_{0}τ^{0}|n ∈ N, a_{0}, …, a_{n} ∈ k}.

The following

τ · a = τ(a)τ  (2)

defines the multiplication on k[τ]. This turns k[τ] into a non-commutative ring. Using this relation (2) any product of difference operators can be written in a unique way in the form (1), i.e. the coefficients in k appear on the left of the τ^{i}. Multiplication in k[τ] corresponds to composition of difference operators; if L = L_{1} · L_{2} then L(f) = L_{1}(L_{2}(f)) (on the subset of C where both are defined).

A sequence u(0), u(1), u(2), … of complex numbers is a function

u : N → C.

So a sequence is an element of W. Now u is called a solution of L if L(u) = 0, i.e.

L(u)(x) = a_{n}u(x + n) + ⋯ + a_{0}u(x) = 0

for all x for which L(u)(x) is defined. So a difference operator L = a_{n}τ^{n} + ⋯ a_{0}τ^{0} of order n corresponds to a recurrence relation of order n. For example u(m) = m! is a solution of L = τ − (x + 1).

We would also like to consider sequences that are solutions of an operator like L = τ −1/(x− 3), however, the coefficients of this L are not defined for all x ∈ N. To avoid such problems with domains of definition we will consider sets V_{p,r} and V_{p,l} consisting of germs of sequences. For p ∈ C/ZZ, p = q + ZZ for some q ∈ C, define W_{p} as the set of functions from q + ZZ to C. Define the equivalence relations ∼_{r} and ∼_{l} on W_{p} as

u ∼_{r} v ⟺ ∃_{M}∀_{x>M}u(x) = v(x)

and

u ∼_{l} v ⟺ ∃_{M}∀_{x<M}u(x) = v(x).

Now V_{p,r} = W_{p}/ ∼_{r} is the set of right germs of W_{p} and V_{p,l} = W_{p}/ ∼_{l} is the set of left germs of W_{p}. Every element of V_{p,r} is a germ of a function to C that is defined on {q+M, q+M +1, …} ⊂ C for some sufficiently large integer M. Now the action of L = τ − 1/(x − 3) is not defined on W_{0}, because the images of L are not defined at x = 3 and hence these images are not elements of W_{0}. However, L is defined on V_{p,r} and on V_{p,l} for all p. The elements of the set V_{0,r} can be represented by sequences u : N → C that are defined on all but a finite number of elements of N, where two sequences are identified if they differ at only finitely many places. Similarly elements of V_{p,r} can be represented by germs of functions u : q + N → C. Multiplication and addition on V_{p,r} corresponds to multiplication and addition of functions u : q + N → C. The invertible elements of V_{p,r} correspond to those u for which u(x) = 0 for only finitely many x ∈ q + N. If u is zero for infinitely many x ∈ q + N then 1/u is not defined. In this case u is either 0 in V_{p,r} (if the number of x for which u(x) ≠ 0 is finite) or a zero-divisor in V_{p,r} otherwise.

Each element f ∈ k is a function from C to C that is defined on all but a finite number of elements of C, so f is defined on the set {q + M, q + M + 1, …} ⊂ C whenever M is sufficiently large. This way k can be viewed as a subset of the sets V_{p,r}, and similarly also as a subset of V_{p,l}. Now V_{p,r} and V_{p,l} are k-algebras and k[τ]-modules. The set V_{0,r} is called S in [11], where it is shown that the Picard-Vessiot ring of L over k can be embedded in S. This Picard-Vessiot ring can be embedded in each of the V_{p,r} and V_{p,l}.

Definition 1 Let L = a_{n}τ^{n} + ⋯ + a_{0}τ^{0} ∈ k[τ] and L ≠ 0. Denote

ord(L) = max({i|a_{i} ≠ 0}) − min({i|a_{i} ≠ 0})
order(L) = max({i|a_{i} ≠ 0}).

L is called normal if a_{0} ≠ 0, i.e. if ord(L) = order(L). Let

V_{p,r}(L) = {u ∈ V_{p,r}|L(u) = 0}
V_{p,l}(L) = {u ∈ V_{p,l}|L(u) = 0}

be the kernels of L on V_{p,r} and on V_{p,l}. These will be called the solution spaces of L in V_{p,r} and in V_{p,l}.

The leading coefficient of L is the highest non-zero coefficient of L (which is a_{n} if a_{n} ≠ 0). The trailing coefficient is the lowest non-zero coefficient of L (which is a_{0} if L is normal). L is called monic if the leading coefficient is 1.

Theorem 1 The dimension (as a C-vector space) of the solution spaces is

dim(V_{p,r}(L)) = dim(V_{p,l}(L)) = ord(L).

The problems with the domain of definition and problems with vanishing of the leading or trailing coefficients of L have been eliminated by taking germs of sequences (i.e. sequences modulo the given equivalence relation). This makes the theorem easy to prove, it corresponds to the well-known statement that recurrence relations of order n, for which the leading and trailing coefficients never vanish, have an n-dimensional solution space.

Definition 2 A k-algebra V is called a universal extension of k if

1. τ : V → V is an automorphism that extends τ : k → k,

2. for every L ∈ k[τ] the kernel of L : V → V is an ord(L)-dimensional C-vector space, and

3. for every u ∈ V there exists a non-zero L ∈ k[τ] such that L(u) = 0.

A universal extension exists because one can verify that {u ∈ V_{p,r}|∃_{L}L(u) = 0} is a k[τ]-module and k-algebra (to show closure under addition and multiplication use LCLM and symmetric products of operators, see below for a definition). See section 6.2 in [11] for another existence proof, where a universal extension is constructed using a difference ring extension of C((1/x)) (so a local construction at the point p = ∞, we used a finite point p ∈ C/ZZ).

Let V be a universal extension of k. V is unique (see [11]) up to difference isomorphisms (i.e. isomorphisms that commute with τ). V can be embedded in each of the V_{p,r} and V_{p,l} for any p ∈ C/ZZ but not in a unique way because V has many difference automorphisms. We denote the solution space of L in V by V (L). We use this notation V (L) instead of V_{p,r}(L) or V_{p,l} when the p ∈ C/ZZ and the choice l or r (left or right) are not relevant.

k[τ] is a Euclidean ring; one can compute GCRD(L_{1}, L_{2}), the greatest common right divisor of two operators L_{1} and L_{2}, c.f. [8, 4]. One can also compute an operator LCLM(L_{1}, L_{2}), the least common left multiple. Requiring that the LCLM and GCRD are monic makes them uniquely defined.

Lemma 1 For every non-zero M ∈ k[τ] there exists a unique monic normal L ∈ k[τ] for which

V (L) = V (M).

If L_{1} and L_{2} are normal operators then

1. L_{1} is a right-hand factor of L_{2} if and only if V (L_{1}) ⊂ V (L_{2}).

2. L_{3} = GCRD(L_{1}, L_{2}) is normal and V (L_{3}) = V (L_{1}) ⋂ V (L_{2}).

3. L_{4} = LCLM(L_{1}, L_{2}) is normal and V (L_{4}) = V (L_{1}) + V (L_{2}).

We will skip the proof. Later in the paper we will often only consider operators that are normal, or normal and monic. According to the lemma this is no real restriction.

Definition 3 An element u of V_{p,r} or V_{p,l} or V is called rational if it is an element of k, and it is called hypergeometric if it is a solution of an operator of order 1, so τ(u) = ru for some r ∈ k. The set of all hypergeometric elements of V is denoted by H.

For example the sequence u(n) = n! is hypergeometric, it corresponds to a hypergeometric element of V. Rational sequences (u is a rational function in n) are also hypergeometric. H^{∗} = H \ {0} is a group under multiplication; hence for example u(n) = (n!)^{3}/(n + 3) is hypergeometric. If u ∈ H^{∗} and L ∈ k[τ] then L(u)/u ∈ k and hence L(u) ∈ H. H is not closed under addition.

Lemma 2 If a, b ∈ H^{∗} then a + b ∈ H ⟺ a/b ∈ k^{∗}.

Proof: Let u = a/b ∈ H^{∗}. If u ∈ k^{∗} = k \ {0} then it is easy to see that a + b ∈ H. If a + b = 0 ∈ H then clearly u ∈ k^{∗}. Now assume a, b, c ∈ H^{∗} where c = a + b, and u ∉ k. Then by definition of hypergeometric, τ(a) = ra, τ(b) = sb and τ(c) = tc for some r, s, t ∈ k^{∗}. Then ta + tb = tc = τ(c) = τ(a + b) = τ(a) + τ(b) = ra + sb so (r − t)a + (s − t)b = 0. If r ≠ t then u = a/b = −(s − t)/(r − t) ∈ k, and if r = t then 0 + (s − t)b = 0 so s = t = r and hence τ(a/b) = (ra)/(sb) = a/b which implies a/b ∈ C ⊂ k.

□

In a similar way it can be shown more generally that for u_{1}, …, u_{n} ∈ H^{∗}, if u_{1} + ⋯ + u_{n} = 0 then u_{i}/u_{j} ∈ k^{∗} for some i ≠ j. Similar to the differential case one can define

Definition 4 Let L_{1}, L_{2} ∈ k[τ] be normal and of order ≥ 1. Then the symmetric product L = L_{1}◯ s L_{2} is defined as the normal monic operator of minimal order such that y_{1}y_{2} ∈ V (L) for all y_{1} ∈ V (L_{1}) and y_{2} ∈ V (L_{2}).

Using the relation L_{1}(y_{1}) = 0 we can write any τ^{i}(y_{1}) as a k-linear combination of τ^{0}(y_{1}), …, τ^{n−1}(y_{1}) where n = order(L_{1}), and similarly for the τ^{i}(y_{2}). Then L can be obtained by computing a k-linear relation between y_{1}y_{2}, τ(y_{1})τ(y_{2}), τ^{2}(y_{1})τ^{2}(y_{2}), . . ..

Lemma 3 If L_{1} = τ − r with r ∈ k^{∗}, u ∈ H^{∗} with L_{1}(u) = 0, and L_{2} is monic and normal then

su · L_{2} · \frac{1}{u} = L_{1}◯ s L_{2} ∈ k[τ] where s = τ^{order(L_{2})}(u)/u ∈ k^{∗}.

To prove this note that su·L_{2}·\frac{1}{u} is monic and has the same solution space as L_{1}◯ s L_{2}. Furthermore L_{2} · v ∈ v · k[τ] for every v ∈ H^{∗} so su · L_{2} · \frac{1}{u} ∈ su · 1/u · k[τ] = k[τ].

3 A generalization of Gosper’s algorithm

Gosper’s algorithm (c.f. [6]) answers the following question: Let M = δ = τ − 1, u ∈ H^{∗}, compute (if it exists) v ∈ H^{∗} such that δ(v) = u. In [2] this was generalized to u ∈ V; given L ∈ k[τ] of minimal order such that u ∈ V (L), then [2] gives a method to find L̃ of minimal order such that δ(V (L̃)) = V (L), and if the orders of L and L̃ are the same then r ∈ k[τ] is given such that v = r(u) is a solution of δ(v) = u.

Now we will give a different generalization of Gosper’s algorithm (which also generalizes [10]), let u ∈ H^{∗}, r ∈ k^{∗} with (τ − r)(u) = 0, and let M be any element of k[τ]. Compute, if it exists, v ∈ H^{∗} such that M(v) = u.

Since M(v) ∈ k · v for all v ∈ H we have v = au for some a ∈ k^{∗}. Now u = M(v) = M(ua) = u(\frac{1}{u} · M · u)(a), so 1 = (\frac{1}{u} · M · u)(a) = s · L(a) where L = M ◯ s (τ − 1/r) and s = τ^{order(M)}(u)/u ∈ k^{∗}. Hence we can compute all v ∈ H^{∗} for which M(v) = u by computing all rational solutions of L(a) = 1/s, a problem for which algorithms exist, c.f. [1]. A similar result can be obtained for the differential case as well.

4 The singularity at infinity

It is well-known that one can study the singularity of L at the point p = ∞, and that this leads to several algorithms for difference operators. However, the finite singularities of L have not been studied until now, and these are useful as well. In section 6 we will show how the finite singularities can be used to give a more efficient algorithm for computing hypergeometric solutions of difference equations. In this section we will list the things we need to use from the singularity p = ∞. The finite singularities p ∈ C/ZZ will be introduced in section 5.

Let L = τ − r or L = a · (τ − r) for some a ∈ k^{∗}, and let u ∈ H^{∗} be a non-zero solution of L. Define the commutative group

H_{∞} = C^{∗} × ZZ × (C/ZZ).

We will use the additive notation for this group, (c_{1}, n_{1}, d_{1}) + (c_{2}, n_{2}, d_{2}) = (c_{1}c_{2}, n_{1} + n_{2}, d_{1} + d_{2}) ∈ H_{∞}. Let t = 1/x. Then r can be written as r = c · t^{n} · (1 + dt + e) for some c, d ∈ C and e ∈ t^{2}C[[t]]. Now define the growth of L and growth of u at ∞ as

g_{∞}(u) = g_{∞}(L) = (c, n, d + ZZ) ∈ H_{∞}.

C((t)) where t = 1/x is a difference field extension of k, τ(t) = τ(1/x) = 1/(x + 1) = t/(1 + t) ∈ C((t)). The definition of g_{∞}(L) for an operator L of order 1 applies for C((t))[τ] as well.

Definition 5 Let L ∈ C((t))[τ] be normal. Then \overline{g}_{∞}(L) is defined as the set of g_{∞}(M) for all right-hand factors M ∈ C((t))[τ] of L of order 1.

If L ∈ k[τ] then the set \overline{g}_{∞}(L) may contain more elements than the set of g_{∞}(M) for all first order right-hand factors M ∈ k[τ], because L can have more right-hand factors in C((t))[τ] than in k[τ].

Lemma 4 The number of elements of \overline{g}_{∞}(L) is at most order(L).

This follows from factorization properties in C((t))[τ], and also from the structure of the formal solutions at the point ∞. We give a brief sketch, for more details see [3, 5, 12]. The elements (c, n, d) ∈ C × ZZ × (C/ZZ) of \overline{g}_{∞}(L) can be computed as follows: For the ring C((t))[τ] one can define a Newton polygon and Newton polynomial (called the τ-polygon and characteristic equation in [3]). The slopes of that polygon give the possible values for n, and c must be a root of the corresponding Newton polynomial. To find d we take the symmetric product of the operator with τ − 1/(ct^{n}), then we need to search for a factor τ − (1 + dt + e) for some e ∈ t^{2}C[[t]]. Let δ = τ − 1. By writing the operator as a polynomial in δ instead of τ one can define a different Newton polygon (called the δ-polygon in [3]). Then d can be found as a root of a Newton polynomial for slope 1. This way the (c, n, d), and hence \overline{g}_{∞}(L), can be found with little computation.

5 Finite singularities of difference equations

The definitions in this section are the main results in this paper.

Definition 6 Let L = a_{n}τ^{n} + ⋯ a_{0}τ^{0} ∈ k[τ]. Then p ∈ C/ZZ is called a singularity of L if there is an a_{i} with a pole in p + ZZ, or if the leading or trailing coefficient (a_{n} and a_{0} if a_{n} ≠ 0 and a_{0} ≠ 0) has a root in p + ZZ. The point ∞ is considered a singularity as well.

The set of singularities of L is a finite subset of C/ZZ ⋃{∞}. One can multiply L on the left by an element of C[x] in order to obtain an element of C[x, τ] with the same solution space. So without loss of generality we may assume that L ∈ C[x, τ]. Then the finite singularities are the roots modulo ZZ of the leading and trailing coefficients of L.

Let p ∈ C and r ∈ k^{∗}. The valuation v_{p}(r) is the largest integer n such that r/(x − p)^{n} ∈ C[[x − p]]. The value of v_{p}(0) is ∞.

Definition 7 Let r ∈ k^{∗} and p ∈ C/ZZ. Then the valuation of r at p is

v_{p}(r) = ∑_{q∈p+ZZ} v_{q}(r).

Let L = τ − r or L = a · (τ − r) for some a ∈ k^{∗}, and let u ∈ H^{∗} be a non-zero solution of L. Then the valuation growth or growth of L and u at p is defined as

g_{p}(u) = g_{p}(L) = v_{p}(r) ∈ ZZ.

Define H as the product of the additive group of all functions C/ZZ → ZZ with finite support and the group H_{∞}. Then define

g(u) = g(L) = (p ↦ g_{p}(u), g_{∞}(u)) ∈ H.

For example u(n) = 2^{n}(n!). Then g_{p}(u) is 1 if p = ZZ, it is (2, −1, 0) if p = ∞ and 0 otherwise.

A non-zero hypergeometric solution u ∈ H^{∗} of L corresponds to a first order right-hand factor τ − r ∈ k[τ] of L where r = τ(u)/u. The map u ↦ τ(u)/u induces isomorphisms of multiplicative groups H^{∗}/C^{∗} → k^{∗} and H^{∗}/k^{∗} → k^{∗}/ ≃, where r_{1} ≃ r_{2} iff r_{1}/r_{2} can be written as τ(y)/y for some y ∈ k^{∗}.

Lemma 5 The map g : H^{∗} → H is a group homomorphism. The kernel is k^{∗}. The image is the set of (f, (c, n, d + ZZ)) where f : C/ZZ → ZZ and c, d ∈ C and n ∈ ZZ for which:

n + ∑_{p∈C/ZZ} f(p) = 0 and d + ∑_{p∈C/ZZ} f(p)p ≡ 0 mod ZZ.  (3)

We omit the proof. The relations (3) will be called Fuchs’ relations, because in the differential case a similar relation with the same name (lemma 9.2 in [7]) exists between the exponential parts, which are the differential equivalent of the g_{p}(L). Note that the two sums are defined because f has a finite support; f(p) ≠ 0 for only finitely many p ∈ C/ZZ. The equivalence class of u ∈ H^{∗} in H^{∗}/k^{∗} is called the type of u. The type of an operator L = τ − r, r ∈ k^{∗} with non-zero solution u is the type of u, which corresponds to the image of r in k^{∗}/ ≃. According to the lemma the type of u or L is given by g(u) or g(L).

Definition 8 Let L ∈ k[τ] and suppose p ∈ C/ZZ is not a singularity. Then for every u ∈ V_{p,l} there is a unique sequence ũ : p + ZZ → C such that L(ũ) = 0 and such that the equivalence class of ũ in V_{p,l} is u. Taking the equivalence class (i.e. the germ) of ũ in V_{p,r} defines a 1-1 map:

E_{p,r} : V_{p,l}(L) → V_{p,r}(L)

called the extension map, or extension to the right. Similarly define

E_{p,l} : V_{p,r}(L) → V_{p,l}(L)

which is extension to the left.

Let L = a_{n}τ^{0} + ⋯ + a_{0}τ^{0} ∈ k[τ] with a_{n} ≠ 0 and a_{0} ≠ 0, and let p ∈ C/ZZ be a singularity. We choose a basis for V_{p,l}(L) as follows. Let q_{l} (resp. q_{r}) in p + ZZ be the minimum (resp. maximum) of the problem points at p, i.e. the elements of the set p + ZZ that occur as a root of a_{n}a_{0} or as a pole in {a_{0}, …, a_{n}}. Define u_{i} : {q_{l} − 1, q_{l} − 2, …} → C by: for 1 ≤ j ≤ n let u_{i}(q_{l} − j) be 1 if i = j and 0 otherwise. The other values of u_{i} are determined by the recurrence equation L(u_{i}) = 0. Now u_{1}, …, u_{n} is a basis of V_{p,l}(L). Similarly we can define a basis v_{1}, …, v_{n} of V_{p,r}(L) where v_{i} : {q_{r} + 1, q_{r} + 2, …} → C. Let L_{ϵ} ∈ C(x, ϵ)[τ] be the deformation of L, which is L with x replaced by x + ϵ, where ϵ is a new constant (a is called a constant if τ(a) = a). So we increased the field of constants from C to C(ϵ). For a ∈ C(ϵ) the valuation v_{ϵ}(a) is the largest integer m for which a/ϵ^{m} ∈ C[[ϵ]]. Now p ∈ C/ZZ ⊂ C(ϵ)/ZZ is not a singularity of L_{ϵ}. So the C(ϵ)-vector spaces V_{p,l}(L_{ϵ}) and V_{p,r}(L_{ϵ}) can be identified by E_{p,r} and elements u of these sets can be identified with a function u : p + ZZ → C(ϵ) for which L_{ϵ}(u) = 0. For such u define the left valuation v_{ϵ,l}(u) as min({v_{ϵ}(u(m))|m ∈ p + ZZ, m < q_{l}}) and the right valuation v_{ϵ,r}(u) = min({v_{ϵ}(u(m))|m ∈ p + ZZ, m > q_{r}}). If v_{ϵ,l}(u) ≥ 0 then we can define the left projection ρ_{l}(u) ∈ V_{p,l}(L) by substituting ϵ = 0 in u (in other words: taking u mod ϵ). Similarly if v_{ϵ,r}(u) ≥ 0 then the right projection ρ_{r}(u) ∈ V_{p,r}(L) is defined. For each basis element u_{i} of V_{p,l}(L) we can choose ũ_{i} ∈ V_{p,l}(L_{ϵ}) with left valuation ≥ 0 and ρ_{l}(ũ_{i}) = u_{i}. These ũ_{i} are not unique. Similarly we can choose ṽ_{i} ∈ V_{p,r}(L_{ϵ}) with right valuation ≥ 0 and ρ_{r}(ṽ_{i}) = v_{i}. The following definition is the main result of this paper.

Definition 9 With notations as above, define the minimum valuation growth of L at p as

g_{p,r}(L) = min({v_{ϵ,r}(ũ_{i})|1 ≤ i ≤ n).

Define the maximum valuation growth as

g_{p,l}(L) = −min({v_{ϵ,l}(ṽ_{i})|1 ≤ i ≤ n).

Define the C-linear maps

E_{p,r} : V_{p,l}(L) → V_{p,r}(L) and E_{p,l} : V_{p,r}(L) → V_{p,l}(L)

by

E_{p,r}(u_{i}) = ρ_{r}(ũ_{i}/ϵ^{g_{p,r}(L)}) and E_{p,l}(v_{i}) = ρ_{l}(ṽ_{i}ϵ^{g_{p,l}(L)}).

Define

\overline{g}_{p}(L) = \{i ∈ ZZ|g_{p,r}(L) ≤ i ≤ g_{p,l}(L)\}.

If p ∈ C/ZZ is not singular then \overline{g}_{p}(L) = \{0\}. If p ∈ C/ZZ is singular and \overline{g}_{p}(L) = \{0\} then p is called an apparent singularity. If \overline{g}_{p}(L) has only 1 element then p is called a semi-apparent singularity. If \overline{g}_{p}(L) has more than 1 element then p is called an essential singularity. Note that the definition of E_{p,r} and E_{p,l} depends on L because g_{p,r}(L) and g_{p,l}(L) depend on L. So, if confusion could occur, these should be denoted as E_{p,r,L} and E_{p,l,L}.

Lemma 6 For all non-zero solutions u of L_{ϵ} we have v_{ϵ,r}(u) − v_{ϵ,l}(u) ∈ \overline{g}_{p}(L). In particular for all p ∈ C/ZZ we have \overline{g}_{p}(L) ≠ ∅, i.e. g_{p,r}(L) ≤ g_{p,l}(L).

Proof: Without loss of generality we may assume that v_{ϵ,l}(u) = 0. Write u on the basis ũ_{i} (notations the same as above), u = c_{1}ũ_{1} + ⋯ + c_{n}ũ_{n} with c_{i} ∈ C(ϵ). Since v_{ϵ}(u) ≥ 0 it follows that v_{ϵ}(c_{i}) ≥ 0. Hence the right valuation of u must be at least the minimum of the right valuations of the ũ_{i}, so v_{ϵ,r}(u) ≥ g_{p,r}(L), hence v_{ϵ,r}(u) − v_{ϵ,l}(u) ≥ g_{p,r}(L). In a similar way one has v_{ϵ,r}(u) − v_{ϵ,l}(u) ≤ g_{p,l}(L), and the statement follows.

□

Lemma 7 If L is normal and order(L) = 1 then g_{p,r}(L) = g_{p,l}(L) = g_{p}(L), in other words \overline{g}_{p}(L) = \{g_{p}(L)\}.

We skip the proof. The following lemma follows from lemma 6.

Lemma 8 Let L, L_{1}, L_{2} ∈ k[τ] be normal and L = L_{1}L_{2}. Then \overline{g}_{p}(L_{2}) ⊂ \overline{g}_{p}(L).

Lemma 9 Let L_{1}, L_{2} ∈ k[τ] be normal, and let order(L_{2}) = 1. Then \overline{g}_{p}(L_{1}◯ s L_{2}) = \overline{g}_{p}(L_{1}) + g_{p}(L_{2}) for all p ∈ C/ZZ ⋃{∞}.

Lemma 10 If g_{p,r}(L) = g_{p,l}(L) (i.e. p is a semi-apparent singularity) then E_{p,r} and E_{p,l} are each other’s inverses. If g_{p,r}(L) ≠ g_{p,l}(L) (i.e. p is an essential singularity) then the image of E_{p,r} (resp. E_{p,l}) is a subset of the kernel of E_{p,l} (resp. E_{p,r}).

Im(E_{p,r}) ⊂ Ker(E_{p,l}) and Im(E_{p,l}) ⊂ Ker(E_{p,r}).

If p ∈ C/ZZ is not a singularity then E_{p,l} and E_{p,r} are isomorphisms of G-modules where G is the difference Galois group (for a definition see [11]) of L. However, at singularities the linear maps E_{p,r} and E_{p,l} are in general not G-homomorphisms, because at essential singularities the kernels and images are non-trivial even when L is irreducible.

6 Computing hypergeometric solutions

Computing hypergeometric solutions is equivalent to computing first order right-hand factors; if u ∈ H^{∗} is a non-zero hypergeometric solution then τ − τ(u)/u ∈ k[τ] is a right-hand factor of L. The type of u is determined by g(u), so when g(u) is known, an operator τ − r with the same type can be constructed. By taking the symmetric product with τ − 1/r we get a right-hand factor τ − (τ(u)/u)/r which has the trivial type and hence a rational solution. So all u can be found by trying all possible g(u) and computing rational solutions for each case. This leads to the following algorithm.

Algorithm hypergeometric solutions Input: L = a_{n}τ^{n} + ⋯ + a_{0}τ^{0} with a_{n} ≠ 0, a_{0} ≠ 0 and n ≥ 2. Output: All hypergeometric solutions, parametrized by constants c_{i}.

1. Let S = {p_{1}, …, p_{m}} ⊂ C/ZZ ⋃{∞} be the set of singularities.

2. result := {}

3. For all h = (h_{1}, …, h_{m}) with h_{i} ∈ \overline{g}_{p_{i}}(L) that satisfy Fuch’s relations (3) do

(a) Construct r ∈ k^{∗} such that the singularities of τ − r are in S, and g_{p_{i}}(τ − r) = h_{i}.

(b) Let b_{1}, …, b_{q} ∈ k be a basis of rational solutions of L◯ s (τ − 1/r).

(c) If q > 0 then result := result ⋃{u · (c_{1}b_{1} + ⋯ + c_{q}b_{q})} where c_{i} are parameters and u ∈ H^{∗} is a solution of τ − r.

4. RETURN result.

Note that we could skip all apparent finite singularities in the algorithm, that would not change the computation. Furthermore we can compute r ∈ k^{∗} such that \{g_{p}(τ − r)\} = \overline{g}_{p}(L) for all semi-apparent singularities p ∈ C/ZZ and such that τ − r does not have other finite singularities. Then L◯ s (τ − 1/r) has an apparent singularity at all these p, and this way these p can be discarded as well.

For L ∈ k[τ] the field of definition is the smallest subfield of C over which all coefficients are defined. This is always a finite extension of Q and hence not an algebraically closed field. One of the main benefits of our algorithm over the algorithm in [9] is that instead of having to compute in the splitting field of all singularities, our algorithm “only” needs to compute in the splitting field of the essential singularities, which is likely to be much smaller. Furthermore the number of cases (the number of loops in step 3) in our algorithm is usually much smaller than (but at most equal to) the number of cases in [9].

7 Improvements

A small improvement is the following: when during the algorithm a hypergeometric solution u is found (equivalently: when a first order right hand factor τ − r is found where r = τ(u)/u ∈ k^{∗}), we can write L = L_{2} · (τ − r). Let M = L◯ s (τ − 1/r) = L_{3} · (τ − 1) for some L_{3} with order(L_{3}) = order(L) − 1. The non-constant hypergeometric solutions of M can be obtained by computing the hypergeometric solutions of L_{3} and applying Gosper’s algorithm on those. Multiplying the hypergeometric solutions of M by u gives the hypergeometric solutions of L. This process is called reduction of order. It may speed up the algorithm in the previous section if a hypergeometric solution is found early in the computation.

If all singularities are semi-apparent then the algorithm in the previous section is fast because there are few cases to check in step 3. If p ∈ C/ZZ is not semi-apparent then in some cases we can also use the images and kernels of E_{p,r} and E_{p,l} to find factors or hypergeometric solutions of L. For example if L is normal and has order 2 then by lemma 10 we have Im(E_{p,r}) = Ker(E_{p,l}) and Im(E_{p,l}) = Ker(E_{p,r}). If u ∈ H^{∗} is a hypergeometric solution of L, then either g_{p}(u) = g_{p,r}(L) or u ∈ Ker(E_{p,r}). And either g_{p}(u) = g_{p,l}(L) or u ∈ Ker(E_{p,l}). So u ∈ Ker(E_{p,r}) or u ∈ Ker(E_{p,l}) (or both). Let r = τ(u)/u ∈ k^{∗}. If we had bounds on the degrees of the numerator and denominator of r then r can be computed by checking both cases u ∈ Ker(E_{p,r}) or u ∈ Ker(E_{p,l}). So there are at most two possible r. Such bounds can be obtained by a careful study of the algorithm in the previous section. Let K_{p} be the smallest field over which p and L are defined. Then all right-hand factors τ − r that we find are defined over K_{p}, because Ker(E_{p,r}) and Ker(E_{p,l}) are 1-dimensional and are defined over K_{p}. So then r must be an element of K_{p} for every essential singularity p, and we can conclude

Theorem 2 Let L ∈ K(x)[τ] be an operator of order 2, where K ⊂ C and let K_{p} = K(q) if p = q + ZZ for some q ∈ C. Let S ⊂ C/ZZ be the set of essential singularities. If S ≠ ∅ then the number of first order monic right-hand factors τ − r is at most two, and they are elements of K̃(x)[τ] where K̃ = ⋂_{p∈S} K_{p}.

If S = ∅ then computing the first order right-hand factors is easy. In this case the only algebraic extension that can occur is the c ∈ C^{∗} in (c, n, d), which can be at most an extension of degree order(L) = 2. If S ≠ ∅ then we can skip all cases in the algorithm that would lead to an extension larger than K̃. This way computations with exponentially large algebraic extensions are avoided in the algorithm in the case of order 2.

References

[1] S. A. Abramov. Rational solutions of linear difference and q-difference equations with polynomial coefficients, Programming and Comput. Software 21, No 6, p. 273 – 278. Transl. from Programmirovanie, No 6, p. 3 – 11, 1995.

[2] S.A. Abramov and M. van Hoeij. A method for the Integration of Solutions of Ore Equations, ISSAC’97 Proceedings, p. 172 – 175, 1997.

[3] A. Barkatou and A. Duval. Sur les séries formelles solutions d’équations aux différences polynomiales. Ann. Inst. Fourier (Grenoble), 44(2):495–524, 1994.

[4] M. Bronstein and M. Petkovšek. An introduction to pseudo-linear algebra. Theoret. Comput. Sci., 157(1):3–33, 1996.

[5] A. Duval. Lemmes de Hensel et factorisation formelle pour les opérateurs aux différences. Funkcial. Ekvac., 26(3):349–368, 1983.

[6] Jr. Gosper, R. William. Decision procedure for indefinite hypergeometric summation. Proc. Nat. Acad. Sci. U.S.A., 75(1):40–42, 1978.

[7] M. van Hoeij. Factorization of Differential Operators with Rational Functions Coefficients, to appear in J. Symb. Comp. 1997.

[8] O. Ore. The theory of non-commutative polynomials, Ann. Maths. 34, 480 – 508, 1933.

[9] M. Petkovšek. Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symbolic Comput., 14(2-3):243–264, 1992.

[10] M. Petkovšek. A generalization of Gosper’s algorithm. Discrete Math., 134(1-3):125–131, 1994. Algebraic and topological methods in graph theory (Lake Bled, 1991).

[11] M. van der Put, M.F. Singer, Galois Theory of Difference Equations, ISBN 3-540-63243-3, 1997.

[12] E. Tournier. Solutions formelles d’équations différentielles, Thèse d’Etat, Faculté des Sciences de Grenoble, 1987.