Finite Singularities and Hypergeometric Solutions of Linear Recurrence Equations

Mark van Hoeij^{∗}

August 31, 1998

Abstract

In this paper the notion of finite singularities of difference operators is introduced, in order to adapt methods for differential equations to the case of recurrence 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 applications. 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 differential case. For a finite singularity p ∈ C/ZZ we will consider left solutions and right solutions of the difference equation. 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 a larger 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, called the valuation growths, that give useful information about the singularity, information that only depends on the type of the equation. These integers lead to an algorithm for computing hypergeometric solutions, given in section 5. This algorithm is the analogue of the Beke/Schlesinger algorithm which treats the equivalent problem for the differential case, see

[5] and section 1.2.

We can also use this deformation to define a map from the left solutions to the right solutions of the original (not deformed) equation, and a map from the right to the left solutions. In section 6 we use the ranks of these maps to prove two theorems that show over which field of constants the hypergeometric solutions can be found. This makes it possible to avoid the main bottleneck (splitting fields) in the computation of hypergeometric solutions. Previously only degree bounds were known, but not the fields themselves, so there was no easy way to avoid splitting fields. The theorems in section 6 are essential for the efficiency in case these splitting fields are large.

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.

∗Department of Mathematics, Florida State University, Tallahassee, FL 32306-3027. This research was partially supported by CRC/FYAP Grant 132859548

1.1 Differential and difference operators

A linear homogeneous differential equation

a_{n}y^{(n)} + a_{n−1}y^{(n−1)} + ⋯ + a_{1}y′ + a_{0}y = 0

corresponds to a differential operator

L = a_{n}∂^{n} + a_{n−1}∂^{n−1} + ⋯ + a_{0}∂^{0}

acting on y. The coefficients a_{i} that are considered here are elements of the differential field C(x) and ∂ is a differentiation d/dx. The differential operator L is an element of the non-commutative ring C(x)[∂], which is an Ore ring, cf. [14]. Multiplication in this ring corresponds to composition of operators. A factorization L = L_{1}L_{2} where L_{1}, L_{2} ∈ C(x)[∂] is useful for computing solutions of L because solutions of the right-hand factor L_{2} are solutions of L as well. Right-hand factors of order 1 are particularly interesting because these are easy to solve. A right-hand factor ∂ − r where r ∈ C(x) corresponds to an exponential solution exp(∫ r). Multiplying L on the left by 1/a_{n} does not change the solution space, so without loss of generality we may assume that a_{n} = 1, i.e. L is monic.

Similarly one can also study difference operators

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

where τ maps x to x + 1. Such a difference operator corresponds to a difference equation or recurrence equation

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

Often one is interested in solutions that are sequences: u(0), u(1), u(2), …, so then u is a function from N to C. It will be useful to consider other kinds of solutions as well. If u is a solution of a difference equation of order 1, so u(x+1) = r(x)u(x) for some rational function r ∈ C(x), then u is called hypergeometric. Just like exponential solutions in the differential case, hypergeometric solutions correspond to first order right-hand factors τ − r ∈ C(x)[τ] of L.

1.2 Finding exponential solutions

Consider the function exp(∫ r) where r ∈ C(x). How to find such solutions for a monic operator L = ∂^{n} + a_{n−1}∂^{n−1} + ⋯ + a_{0}∂^{0}? In [11] two methods are given, the classical method [5] that dates back to the previous century, and a new method. The classical method can be explained as follows. The function exp(∫ r) is meromorphic at all but a finite number of points p ∈ P^{1}(C) = C ⋃{∞}. The “non-meromorphicness” of exp(∫ r) at a point p ∈ P^{1}(C) can be classified by the so-called exponential part which (in this case) is an element of C[x^{−1}]/ZZ. For example the function x^{1/3} = exp(∫ \frac{1/3}{x}) has exponential part 1/3 + ZZ at the point 0. If e ∈ C[x^{−1}] then exp(∫ \frac{e}{x}) has exponential part e+ZZ at x = 0. The collection of the exponential parts of exp(∫ r) at all points p ∈ P^{1}(C) corresponds 1–1 with the type of exp(∫ r). The type describes the “non-meromorphicness” of exp(∫ r). Two exponential functions exp(∫ r_{1}) and exp(∫ r_{2}) have the same type if and only if their quotient is a rational function, so if and only if r_{1} − r_{2} = y′/y for some y ∈ C(x).

At every singularity p ∈ P^{1}(C) of the operator L one can compute the “non-meromorphicness” of all local solutions; one can compute all exponential parts at p. The number of different exponential parts at p is at most the order of the operator L. There are only finitely many singularities, and at regular points only the trivial exponential part occurs. This leaves only a finite number (but possibly exponentially large number) of cases for the type of an exponential solution exp(∫ r). When the type of an exponential solution s is known, then s is known up to a rational factor, so s = y · exp(∫ r) for some known r ∈ C(x) and unknown y ∈ C(x). The C(x)-automorphism of C(x)[∂] given by ∂ ↦ ∂ + r transforms L into an operator L◯ s (∂ + r).

The solutions of this operator are the solutions of L divided by exp(∫ r). This way, finding s is reduced to finding rational solutions y ∈ C(x) of L◯ s (∂ +r). So computing exponential solutions can be done by making a finite list of possible types, and computing rational solutions for each case.

1.3 Finding hypergeometric solutions

Similar to the differential case, computing hypergeometric solutions is equivalent to computing first order factors τ − r ∈ C(x)[τ] of a difference operator L. Two hypergeometric expressions u_{1} and u_{2} have the same type if their quotient is a rational function. These u_{1} and u_{2} are solutions of τ − r_{1} and τ − r_{2} where r_{i} = τ(u_{i})/u_{i}. The two operators τ − r_{1} and τ − r_{2} have the same type (meaning that their solutions have the same type) if r_{1}/r_{2} = τ(y)/y for some y ∈ C(x)^{∗} = C(x) \ {0}. One can compute local information about solutions at the point ∞, cf. [4, 7]. This is similar to the differential case. In the differential case all singularities are needed for determining the possible types. Likewise, in the difference case, the singularity at infinity is not sufficient. Finite singularities are needed as well.

The C(x)-automorphism τ which maps x to x + 1 can be extended to C((1/x)) but not to C((x − p)). As a consequence, for finite p a construction like in the differential case does not work in the difference case. This is why finite singularities of difference equations have not been studied before; a different approach is needed for this case. The key to find the definition of finite singularities is to study what is needed to be able to mimic methods (in particular: exponential solutions) from the differential case to the case of difference operators. In the differential case, the exponential parts determine the local type of an exponential solution, and the combination of all local types determines the type. Once the possible types are known, computing exponential solutions becomes easy. What kind of local data is needed to determine the type of a hypergeometric solution of a difference operator, or equivalently, the type of a first order right-hand factor?

Consider the following example: u(n) = n! = Γ(n + 1), then u is a solution of τ − (x + 1). At negative integers, u has a pole of order 1 (the valuation is −1) and at positive integers the valuation is 0 (i.e. u has no pole and no root at positive integers). So, going through the integers from the left to the right, the valuation increases by 1. For p ∈ C/ZZ the valuation growth of u is 1 at p = 0 + ZZ ∈ C/ZZ, and it is 0 otherwise. At the point infinity one can compute local data that resembles the exponential parts in the differential case. We will show that the valuation growths at each element of C/ZZ combined with local data at infinity determines the type of u. So by determining the possible valuation growths and computing some local data at infinity it is possible to give a finite list of possible types of hypergeometric solutions. Similar to differential equations, for each possible type in this list one needs to compute rational solutions of a certain transformation of the operator L.

The behavior of L at p ∈ C/ZZ will be studied by considering a deformation of L. This way a finite set \overline{g}_{p}(L) can be computed, and it is shown that for all hypergeometric solutions of L the valuation growth at p is an element of \overline{g}_{p}(L). A finite list of possible types can then be determined, and then we can proceed as in the Beke/Schlesinger method sketched in section 1.2.

1.4 An example in Maple

Consider the following difference operator L ∈ C(x)[τ]

L = (3 x + 8) (3 x + 10) (x + 3) (x + 2) (x + 1) τ^{3} − 3 (3 x + 5) (3 x + 7) (x + 2) (x + 1) τ^{2}

+ 3 (3 x + 2) (3 x + 4) (x + 1) τ − (3 x − 1) (3 x + 1)

Solving the corresponding recurrence equation with Maple 5.4 and simplifying the result gives

u(x) = \frac{1}{2} \frac{−(x − 1) (x − 2) u(0) − 16 x (x − 2) u(1) + 70 x (x − 1) u(2)}{(3 x − 1) (3 x + 1) Γ(x + 1)}

All solutions of this difference operator L have the same type; each solution u(x) is a rational function times 1/Γ(x + 1). However, the algorithm in [15] will still distinguish a number of different cases. The number of cases in this example can be reduced to 1 by computing the \overline{g}_{p}(L) defined in section 4. In fact, whenever all solutions of a difference operator L are hypergeometric and of the same type, the number of cases in the algorithm in section 5 is always 1, whereas in the method in [15] the number of cases to check can still be exponentially high. Both methods are fast on this example though, because of the fact that all roots of the leading and trailing coefficients (the coefficients of the highest and of the lowest power of τ in L) are rational numbers, which makes this example relatively easy.

1.5 A harder example

The following example was a motivation to start working on this problem. It was sent to Maple as a bug-report in the procedure hypergeomsols in the LREtools package. After having fixed the bug, the algorithm still did not perform satisfactory; it takes weeks to run this example.

L = a_{3}τ^{3} + a_{2}τ^{2} + a_{1}τ + a_{0}
a_{0} = 18 (2 x + 3)(x + 2)(140 x^{3} + 1151 x^{2} + 3114 x + 2781)(x + 1)^{2}
a_{1} = −(x + 2)(23660 x^{6} + 302879 x^{5} + 1581604 x^{4} + 4314577 x^{3}
+6487290 x^{2} + 5099454 x + 1638144)
a_{2} = (18380306 x^{2} + 13291032 x + 237304 x^{6} + 1637876 x^{5} + 4046652
+14560 x^{7} + 6200310 x^{4} + 13887720 x^{3})
a_{3} = −4 (140 x^{3} + 731 x^{2} + 1232 x + 678)(2 x + 7)^{2}(x + 3)^{2}.

The current algorithm tries all combinations of all factors in C[x] of a_{3} and all factors of a_{0}, that is 6912 cases. Computing with these factors requires computing with the splitting field of a_{0}a_{3}. This makes the computation slow.

The computation can be done much faster by computing the sets \overline{g}_{p}(L) for each finite singularity p ∈ C/ZZ, as defined in section 4. The roots of a_{3} are −7/2, −3, α_{1}, α_{2}, α_{3} where α_{i} ∈ C are the three roots of 140x^{3}+731x^{2}+1232x+678. The roots of a_{0} are −3/2, −2, −1, α_{1}− 1, α_{2} − 1, α_{3} − 1. The finite singularities of L are the roots of a_{0}a_{3} modulo the integers, so the finite singularities are p_{1} = α_{1} + ZZ, p_{2} = α_{2} + ZZ, p_{3} = α_{3} + ZZ, p_{4} = 0 + ZZ, p_{5} = 1/2 + ZZ. Using a deformation of L we will show how in section 4.2 how to compute the sets

\overline{g}_{p_{1}}(L) = \overline{g}_{p_{2}}(L) = \overline{g}_{p_{3}}(L) = \{0\}
\overline{g}_{p_{4}}(L) = \{−2, −1, 0, 1, 2\}
\overline{g}_{p_{5}}(L) = \{−2, −1, 0, 1\}

Hence if u is a hypergeometric solution, then for its valuation growth at p where p ∈ C/ZZ there are 5 cases if p = p_{4}, 4 cases if p = p_{5} and only 1 case otherwise. So this leaves only 4·5 = 20 cases instead of the 6912 cases in the algorithm in [15]. The singularity at infinity is not taken into consideration in this comparison, although it would make the difference slightly larger because of Fuchs’ relations that we will introduce. What is more important for the computation timings than this 6912 to 20 ratio is that in our method the only singularities that really matter (i.e. where there is more than 1 case) are p_{4} and p_{5}. So these 20 cases involve no algebraic extensions, and hence each of these cases is much easier than most of the 6912 cases (most of those do involve algebraic extensions). This way the computation can be done in less than a minute, which is more than 10000 times faster than Maple’s implementation of [15]. The result of the computation is that this example has no non-zero hypergeometric solutions.

Splitting fields could be avoided in this example because of the fact that p_{1}, p_{2}, p_{3} were apparent singularities. The same conclusion could (in this example, not in general) also be drawn by computing local information at infinity. But even without this information we could still obtain this conclusion from theorem 3 in section 6.

If an operator does not have hypergeometric solutions then this can often quickly be detected by computing the p-curvature, see [16] for a definition. However, in the example above this does not help because even though it does not have first order factors in characteristic 0, it does have first order factors modulo prime numbers. We verified this for primes ≤ 29.

2 Preliminaries and definitions

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 a function f

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

In this paper the coefficients a_{i} will be elements of k. The function L(f) 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 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) coincides with 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.

A function 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 the sequence u : N → C, u(m) = m! = Γ(m + 1) 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, just like the set S in [16]. A germ of a sequence u is u modulo the ideal of sequences with finite support. So two sequences have the same germ if and only if their difference has finite support.

Denote q + N = {q, q + 1, q + 2, …} ⊂ q + ZZ and q − N = {q, q − 1, q − 2, …} ⊂ q + ZZ. For a, b in q + ZZ define an ordering by a > b iff a − b > 0.

Define V_{q,l} as the set of germs of functions u : q − N → C. So V_{q,l} is the ring of all functions from q − N to C modulo the ideal of functions that are non-zero at only finitely many points x in q − N. Note that if q_{1} − q_{2} ∈ ZZ then V_{q_{1},l} and V_{q_{2},l} can be identified, and so V_{p,l} can be defined for p ∈ C/ZZ as well. Similarly define V_{q,r} as the set of germs of functions u : q +N → C.

Multiplication and addition in V_{p,r} where p = q + ZZ 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 u has finite support) 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. Hence k can be embedded in the ring V_{p,r}, and also in V_{p,l}. Now V_{p,r} and V_{p,l} are k-algebras and k[τ]-modules.

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 are 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.

The set V_{0,r} is called S in [16], where it is shown that the Picard-Vessiot ring of L over k can be embedded in S. The same proof also shows that the Picard-Vessiot ring can be embedded in each of the V_{p,r} and V_{p,l}, and hence the following proposition holds (this is part 2 of proposition 4.1 in chapter 4 in [16]).

Proposition 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).

Problems with vanishing of the leading or trailing coefficients of L, or coefficients having poles, have been eliminated by taking germs of sequences. Hence the proposition corresponds to the well-known statement that recurrence relations of order n, for which the leading and trailing coefficients do not vanish, have an n-dimensional solution space.

Definition 2 A k-algebra V is called a universal extension of k if the following three conditions hold

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.

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, a definition follows later). See section 6.2 in [16] 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 = ∞).

Let V be a universal extension of k. V is unique (see [16]) 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).

From now on, unless mentioned otherwise, by solutions of a difference operator L we will mean elements of V (L). A solution y ∈ V (L) can also be interpreted as an element of V_{p,r}(L) or V_{p,l}, but only after having chosen an embedding of V in those rings.

The ring of difference operators k[τ] is a non-commutative 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. [14, 6]. 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}).

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. The lemma appears to be known but not explicitly written down. It is a immediate consequence of the fact that every finite dimensional G-invariant subspace of V (such as V (L_{1}) ⋂ V (L_{2}) and V (L_{1}) + V (L_{2})) is the solution space of some element of k[τ], where G is the difference Galois group. This is a non-trivial result, proven in [10], where it is also shown that the dimension of the solution space is always ≤ ord(L) in any Picard-Vessiot extension of k.

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! = Γ(n + 1) is hypergeometric. The sequence c^{n} where c ∈ C is also hypergeometric. Rational sequences (u is a rational function in n) are also hypergeometric. H^{∗} = H \ {0} is a group under multiplication; hence products:

u ∈ S = V_{0,r}, u(n) = c^{n}R(n)Γ(n + a_{1})^{e_{1}} ⋯ Γ(n + a_{s})^{e_{s}}

are also hypergeometric, where c, a_{i} ∈ C, e_{i} ∈ ZZ and R is a rational function. Every hypergeometric element of V_{0,r} can be represented in this way. If u ∈ H^{∗} and L ∈ k[τ] then L(u)/u ∈ k and hence L(u) ∈ H. However, H is not a k[τ]-module because H is not closed under addition. 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}).

Any τ^{i}(y_{1}) can be written as a k-linear combination of τ^{0}(y_{1}), …, τ^{n−1}(y_{1}) using the relation L_{1}(y_{1}) = 0, where n = order(L_{1}). A similar statement holds 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}), . . .. The same construction is also found in the proof of lemma 6.8 in [10], where it is also shown that every finite dimensional G-invariant subspace of V occurs as the solution space of an element of k[τ], which implies that V (L_{1}◯ s L_{2}) is spanned by {y_{1}y_{2}|y_{1} ∈ V (L_{1}), y_{2} ∈ V (L_{2})}. Note that the situation is easier when one of these two operators has order 1. Then L_{1}◯ s L_{2} can be computed without solving linear equations.

Lemma 2 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 The point at infinity

The local properties of the operator L at the point p = ∞ have been well studied (see [4, 7, 18, 13] and references therein). This in contrast to finite singularities of L, which have not been considered before, but are useful as well. In this section we will review the local information we need from the singularity at infinity (we consider the point at infinity to be a singularity of every difference operator). Finite singularities will be introduced in section 4. The local types at all singularities (finite singularities and the point at infinity) will be used in section 5 to give a new and more efficient algorithm for computing hypergeometric solutions of difference equations. This algorithm can be viewed as the analogue for the difference case of the Beke/Schlesinger algorithm. Other local properties at finite singularities (the maps E_{p,l} and E_{p,r}) will be introduced in order to prove the theorems in section 6. Those theorems are used to improve the efficiency of the algorithm in section 5.

Let L = a · (τ − r) for some a and r in k^{∗}. 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 in the form r = c · t^{n} · (1 + dt + O(t^{2})) for some c, d ∈ C. Now define the local type of L at ∞ as

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

Define the following groups with multiplication ◯ s

k_{◯ s}^{∗} = {τ − r|r ∈ k^{∗}} and k_{R}^{∗} = {τ − τ(r)/r|r ∈ k^{∗}} ⊂ k_{◯ s}^{∗}

We have (τ − r_{1})◯ s (τ − r_{2}) = τ − r_{1}r_{2} so k_{◯ s}^{∗} is isomorphic with the multiplicative group k^{∗}. It is easy to verify that g_{∞} is a surjective group homomorphism from k_{◯ s}^{∗} to H_{∞}. Furthermore g_{∞}(τ − r) = g_{∞}(τ − τ(r)) and hence k_{R}^{∗} is a subgroup of the kernel of g_{∞}. So g_{∞}(L) only depends on the type (see definition below) of L.

Definition 5 Let L = a(τ − r) where a, r ∈ k^{∗}. Then the type of L is defined as the image of τ − r in the group (with ◯ s as multiplication) k_{◯ s}^{∗}/k_{R}^{∗}.

The type is trivial, i.e. type(L) is the identity in k_{◯ s}^{∗}/k_{R}^{∗}, if and only if the solutions of L are rational. The type can be defined for operators of higher order as well:

Definition 6 Two operators L_{1} and L_{2} have the same type if and only if ord(L_{1}) = ord(L_{2}) and there exists an operator r ∈ k[τ] such that r(V (L_{1})) = V (L_{2}).

This is equivalent with the existence of two operators r, r′ ∈ k[τ] for which r(V (L_{1})) = V (L_{2}) and r′(V (L_{2})) = V (L_{1}). This r′ can be computed from r by the extended Euclidean algorithm for k[τ]. With this algorithm one can find r′, s ∈ k[τ] for which r′r + sL_{1} = 1. For order 1 the two definitions of the type coincide. See [17] for several characterizations of the notion of type for the differential case (the difference case works in the same way).

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

Definition 7 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 of g_{∞}(M) for all first order right-hand factors M ∈ k[τ] can be a proper subset of \overline{g}_{∞}(L), because L may have more right-hand factors in C((t))[τ] than in k[τ].

The characteristic classes in [13] determine the isomorphism classes of all factors in C((t))[τ] of L, whereas the set \overline{g}_{∞}(L) determines only the isomorphism classes of first order factors of L in C((t))[τ]. The set \overline{g}_{∞}(L) gives a part of the information encoded in the characteristic classes, namely the part that we use for computing hypergeometric solutions. So the following lemma can be viewed as a special case of results in [13].

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

This lemma 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 on factorization and formal solutions see [4, 7, 18]. The elements (c, n, d) ∈ H_{∞} 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 [4]). 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 factors of the form τ − (1 + dt + O(t^{2})). Let δ = τ − 1. By writing the operator as a polynomial in δ instead of τ one can define a different Newton polygon (called the δ-polygon in [4]). Then d can be computed using the Newton polynomial for slope 1. This way the (c, n, d), and hence \overline{g}_{∞}(L), can be obtained with little computational effort.

4 Finite singularities of difference equations

The two previous sections (preliminaries and the singularity at infinity) form a summary of known work that we will use. The new results in this paper are the definitions in this section and their applications (theorems 2, 3 and the algorithm in section 5).

Definition 8 Let L = a_{n}τ^{n} + ⋯ a_{0}τ^{0} ∈ k[τ] with a_{n} ≠ 0 and a_{0} ≠ 0. After multiplying L on the left by a suitable element of k we may assume the coefficients a_{i} are in C[x] and gcd(a_{0}, …, a_{n}) = 1. Then q ∈ C is called a problem point of L if q is a root of the polynomial a_{0}(x)a_{n}(x − n). And p ∈ C/ZZ is called a singularity of L if a_{0}a_{n} has a root in p. The point ∞ is considered a singularity as well.

If using the recurrence relation for solutions u of L we can not determine u(q) from u(q − 1), …, u(q − n), or we can not determine u(q) from u(q + 1), …, u(q + n), then the point q ∈ C is a problem point. The finite singularities in C/ZZ are the problem points modulo ZZ. The set of singularities of L is a finite subset of C/ZZ ⋃{∞}.

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

Definition 9 Let p ∈ C/ZZ. Define the group homomorphism v_{p} : k^{∗} → ZZ as

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

Let L = a · (τ − r) for some a, r ∈ k^{∗}. Then the valuation growth or local type of L at p is defined as

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 the collection of all local types

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

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

The map g_{p} where p ∈ C/ZZ is a group homomorphism from k_{◯ s}^{∗} to ZZ. Furthermore v_{p}(τ(r)) = v_{p}(r) and so k_{R}^{∗} is contained in the kernel of g_{p} for finite p as well. Hence g(L) only depends on type(L) ∈ k_{◯ s}^{∗}/k_{R}^{∗}.

Definition 10 Let H_{F} be the set of all (f, (c, n, d + ZZ)) ∈ H 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)

The relations (3) are called Fuchs’ relations, because in the differential case a similar relation with the same name (lemma 9.2 in [11]) exists between the exponential parts, which are the differential equivalent of the g_{p}(L). So H_{F} is the set of all elements of H that satisfy the Fuchs’ relations. It is a subgroup of H. Note that the two sums are defined because f has a finite support; f(p) ≠ 0 for only finitely many p ∈ C/ZZ.

Theorem 1 The map g : k_{◯ s}^{∗} → H is a group homomorphism. The kernel is k_{R}^{∗}. The image is H_{F}. So g induces an isomorphism between the group of types of normal operators of order 1 and the group H_{F}.

Proof: To show that the image is contained in H_{F} we only need to verify that this is true for the generators τ − c and τ − (x − q) of the group k_{◯ s}^{∗}, where c ∈ C^{∗} and q ∈ C. The map is surjective because if F = (f, (c, n, d + ZZ)) ∈ H_{F} then F = g(F′) where F′ = τ − c(x − q_{1})^{f(q_{1})} ⋯ (x − q_{m})^{f(q_{m})}. Here q_{1}, …, q_{m} are representants in C for the p_{1}, …, p_{m} ∈ C/ZZ for which f(p_{i}) ≠ 0, and p_{i} ≠ p_{j} if i ≠ j. It is easy to see that such F′ can only be in k_{R}^{∗} if c = 1 and f = 0, i.e. if F = (0, (1, 0, ZZ)) which is the identity in H_{F}. So the kernel is contained in k_{R}^{∗}, and hence equal to k_{R}^{∗}.

□

That the kernel is k_{R}^{∗} is lemma 2.1 in section 2.1 in [16]. The rest of this theorem (the Fuchs’ relations and the group homomorphism g) appears to be new.

The map u ↦ τ −τ(u)/u (note that u is a solution of τ −τ(u)/u) induces group isomorphisms H^{∗}/C^{∗} → k_{◯ s}^{∗} and H^{∗}/k^{∗} → k_{◯ s}^{∗}/k_{R}^{∗}. This way the local types g_{p}(u) of u at p ∈ C/ZZ ⋃{∞} can be defined for u ∈ H^{∗} or u ∈ H^{∗}/k^{∗}.

4.1 Valuation growths

According to theorem 1 the type of u ∈ H^{∗} (i.e. the type of operators L = τ −τ(u)/u of order 1) is determined by the local types g_{p}(u) at all p ∈ C/ZZ ⋃{∞}. To determine all hypergeometric solutions u ∈ H^{∗} of an operator L of order > 1 we will define in this section for every finite singularity p ∈ C/ZZ a finite set \overline{g}_{p}(L) of valuation growths such that g_{p}(u) ∈ \overline{g}_{p}(L) for every hypergeometric solution u of L. Then, by trying all combinations that satisfy Fuchs’ relations, we obtain a finite set of possibilities for the type of u. For each type, we divide all solutions of L by a u′ ∈ H^{∗} with the same type, so u/u′ ∈ k^{∗}, and then to find u the problem is reduced to finding rational solutions. This leads to the algorithm in section 5, given in more detail in section 6. First we will give an intuitive idea of valuation growths using an example. Then we will define the set of valuation growths, and show in section 4.2 how it can be computed, and that this set is finite.

Example. Let u ∈ H^{∗} be the gamma function u(n) = Γ(n) = (n − 1)!. This is a function on C that has poles of order 1 (interpret this as valuation −1) at the non-positive integers. It has no poles and no roots (i.e. valuation 0) at the positive integers. So, going trough the integers from the left to the right (passing the problem point), the valuation increases by 1; the valuation growth g_{p}(u) = 1 at p = ZZ ∈ C/ZZ. If p ∈ C/ZZ is not equal to ZZ then u has valuation 0 (i.e. no poles and no roots) on p, so going trough p from the left to the right, the valuation remains the same; g_{p}(u) = 0. Also, if p ≠ ZZ then there are no problem points on p so p is not a singularity. This u is a solution of L = τ − x, and indeed g_{p}(L) is 1 if p = ZZ and 0 for all other p ∈ C/ZZ. The statement that the solution u of L has valuation 0 at positive integers and valuation −1 at negative integers uses analytic continuation, because this is a property of the function Γ(n), and that is a continuation of (n − 1)!. We can not perform exact analytic continuation on a computer, so to make this algorithmic requires an algebraic definition of the valuation of a solution at a point. This will be done by extending the field of constants to C(ϵ) where ϵ is transcendental over C, so ϵ is a new indeterminate. Then we can consider solutions ũ : ZZ → C(ϵ) of an operator L_{ϵ} = τ − (x + ϵ) ∈ C(ϵ, x)[τ]. We can take a solution ũ of L_{ϵ} for which ũ(1) = 1. Then ũ(n) = ∏_{i=1}^{n−1}(i + ϵ) for n ≥ 1, and ũ(n) = 1/ ∏_{i=n}^{0}(i + ϵ) for n ≤ 0. Now ũ(n) has value u(n) at ϵ = 0 for every integer n ≥ 1. For n ≤ 0, ũ(n) has a pole at ϵ = 0 of order 1, i.e. the ϵ-valuation v_{ϵ}(ũ(n)) is −1 for n ≤ 0, a definition follows later. Now the valuation growth is

lim inf_{n→∞} v_{ϵ}(ũ(n)) − lim inf_{n→−∞} v_{ϵ}(ũ(n))

which is 1 in this example. The liminf suggests that this describes local behavior at infinity. However, that is not the case because in this liminf n does not need to go to ∞ or −∞ but only needs to pass the problem points. Note that substituting ϵ = 0 in ũ results in an non-zero rightsolution of L, i.e. a non-zero element of V_{0,r}(L). Evaluating ϵ · ũ at ϵ = 0 results in a non-zero left-solution of L. So apparently there is a canonical way to define maps E_{0,r} : V_{0,l}(L) → V_{0,r}(L) and E_{0,l} : V_{0,r}(L) → V_{0,l}(L) in this example. Such maps can be defined in general as well. We will use the ranks of these maps to avoid splitting fields in the computation of hypergeometric solutions.

Definition 11 Let L ∈ k[τ] and suppose p ∈ C/ZZ is not a singularity. Then define V_{p}(L) as the set of functions u : p → C that are solutions of L. If p is not a singularity then V_{p,l}(L) and V_{p,r}(L) can both be identified with V_{p}(L).

The dimension of V_{p}(L) equals ord(L), c.f. proposition 1. This identification of V_{p,l}(L) with V_{p,r}(L) for non-singular p yields identification maps E_{p,l} : V_{p,r}(L) → V_{p,l}(L) and E_{p,r} : V_{p,l}(L) → V_{p,r}(L). Later we will generalize these maps to singular p as well, in which case we will see that these maps are 1 − 1 if and only if p is a semi-apparent singularity, definitions follow later.

Definition 12 Let ϵ be a new indeterminate; ϵ is transcendental over C. Define the action of τ on C(ϵ, x) as τ(ϵ) = ϵ and τ(x) = x + 1. This turns C(ϵ, x) into a difference field with C(ϵ) as the field of constants. For a ∈ C(ϵ) the ϵ-valuation is

v_{ϵ}(a) = sup{m ∈ ZZ|a ∈ ϵ^{m}C[[ϵ]]} ∈ ZZ ⋃{∞}.

Let L ∈ k[τ]. Define L_{ϵ} ∈ C(ϵ, x)[τ] as the operator one obtains from L by replacing x by x + ϵ. We call L_{ϵ} the deformation of L.

The map L ↦ L_{ϵ} defines an embedding (as non-commutative rings) of k[τ] in C(ϵ, x)[τ]; if L = MN then L_{ϵ} = M_{ϵ}N_{ϵ}.

Suppose ũ : q + N → C(ϵ) with q ∈ C, and L̃ ∈ C(ϵ, x)[τ]. Let ũ_{ϵ=0} : q + N → C and L̃_{ϵ=0} ∈ k[τ] be the result of substituting ϵ = 0 in ũ and L̃, and assume that this substitution can be done, i.e. that there are no poles at ϵ = 0. Then (L̃(ũ))_{ϵ=0} = L̃_{ϵ=0}(ũ_{ϵ=0}), i.e. substituting ϵ = 0 commutes with applying an operator. In particular, if ũ : q + N → C(ϵ) is a solution of L_{ϵ}, then ũ_{ϵ=0} (if the substitution ϵ = 0 can be done) is a solution of L.

If L ∈ k[τ] and p ∈ C/ZZ ⊂ C(ϵ)/ZZ then p is not a singularity of L_{ϵ}. So the ord(L)- dimensional C(ϵ)-vector spaces V_{p,l}(L_{ϵ}) and V_{p,r}(L_{ϵ}) can be identified with V_{p}(L_{ϵ}) = {ũ : p → C(ϵ)|L_{ϵ}(ũ) = 0}.

Let L = a_{n}τ^{0} + ⋯ + a_{0}τ^{0} ∈ k[τ] with a_{n} ≠ 0 and a_{0} ≠ 0, and let p ∈ C/ZZ. Let q_{l} (resp. q_{r}) be the smallest (resp. largest) root of a_{0}(x)a_{n}(x − n) in p, so q_{l} (resp. q_{r}) is the smallest (resp. largest) problem point at p. If p is not a singularity (so then there are no problem points at p) then choose arbitrary elements q_{l}, q_{r} ∈ p.

Definition 13 With notations as above, for non-zero ũ ∈ V_{p}(L_{ϵ}) define the left valuation

v_{ϵ,l}(ũ) = min{v_{ϵ}(ũ(m))|m ∈ q_{l} − 1 − N}

the right valuation

v_{ϵ,r}(ũ) = min{v_{ϵ}(ũ(m))|m ∈ q_{r} + 1 + N}

and the valuation growth

g_{p,ϵ}(ũ) = v_{ϵ,r}(ũ) − v_{ϵ,l}(ũ) ∈ ZZ.

Define the set of valuation growths of L at p

\overline{g}_{p}(L) = \{g_{p,ϵ}(ũ)|ũ ∈ V_{p}(L_{ϵ}), ũ ≠ 0\} ⊂ ZZ.

If v_{ϵ,l}(ũ) ≥ 0 then the left projection ρ_{l}(ũ) ∈ V_{p,l}(L) is defined by substituting ϵ = 0 in ũ. Similarly if v_{ϵ,r}(ũ) ≥ 0 then the right projection ρ_{r}(ũ) ∈ V_{p,r}(L) is defined.

Note that for all m ∈ q_{l} − 1 − N the leading and trailing coefficient of L_{ϵ} have ϵ-valuation 0 and all other coefficients of L_{ϵ} have ϵ-valuation ≥ 0. Since the ũ(m) for m ∈ q_{l} − 1 − N are determined by L_{ϵ} and the ũ(m) for m ∈ {q_{l} − 1, q_{l} − 2, …, q_{l} − n}, it follows that

v_{ϵ,l}(ũ) = min{v_{ϵ}(ũ(m))|m ∈ {q_{l} − 1, q_{l} − 2, …, q_{l} − n}}

and similarly

v_{ϵ,r}(ũ) = min{v_{ϵ}(ũ(m))|m ∈ {q_{r} + 1, q_{r} + 2, …, q_{r} + n}}.

In fact, if S is any set of n consecutive elements of q_{l} − 1 − N then one can apply the same argument and show that v_{ϵ,l}(ũ) = min{v_{ϵ}(ũ(m))|m ∈ S}. Hence, for ũ ∈ V_{p}(L_{ϵ}), ũ ≠ 0

v_{ϵ,l}(ũ) = lim inf_{m→−∞} v_{ϵ}(ũ(m))

and

v_{ϵ,r}(ũ) = lim inf_{m→∞} v_{ϵ}(ũ(m))

where the two limits are taken over m ∈ p using the ordering < that was defined on the set p. It is easy to compute the valuation growth of ũ ∈ V_{p}(L_{ϵ}) if L has order n = 1, and one obtains:

Lemma 4 If L is normal and order(L) = 1 then the set \overline{g}_{p}(L) contains only one element, \overline{g}_{p}(L) = \{g_{p}(L)\}.

Lemma 5 Let L, N, M ∈ k[τ] be normal, L = NM. Then \overline{g}_{p}(M) ⊂ \overline{g}_{p}(L).

Proof: M is a right-hand factor of L, so M_{ϵ} is a right-hand factor of L_{ϵ}, so V_{p}(M_{ϵ}) ⊂ V_{p}(L_{ϵ}) and hence the lemma follows for p ∈ C/Z. For p = ∞ the statement follows directly from the definitions.

□

Without proof we mention that \overline{g}_{p}(N) ⊂ \overline{g}_{p}(L) as well, and that \overline{g}_{∞}(L) = \overline{g}_{∞}(M) ⋃ \overline{g}_{∞}(N). However, if p is finite then examples show that in general the set \overline{g}_{p}(L) is not determined by \overline{g}_{p}(M) and \overline{g}_{p}(N). The two lemmas show that

\{g_{p}(u)|u ∈ V (L) ⋂ H^{∗}\} ⊂ \overline{g}_{p}(L)

(recall that g_{p}(u) for u ∈ H^{∗} has been defined as g_{p}(τ − r) where r = τ(u)/u ∈ k^{∗}). This inclusion is not always an equality.

4.2 Computing the set of valuation growths

With L = a_{n}τ^{n} + ⋯ + a_{0}τ^{0}, a_{n}a_{0} ≠ 0, q_{l} and q_{r} as before, define u_{i} : q_{l} − 1 − N → 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 + N → C. For each basis element u_{i} of V_{p,l}(L) we can choose ũ_{i} ∈ V_{p}(L_{ϵ}) with left valuation ≥ 0 and ρ_{l}(ũ_{i}) = u_{i}, by setting ũ_{i}(q_{l} − j) = u_{i}(q_{l} − j) for j from 1 through n. Similarly we can choose ṽ_{i} ∈ V_{p}(L_{ϵ}) with right valuation ≥ 0 and ρ_{r}(ṽ_{i}) = v_{i}.

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

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

Define the maximum valuation growth as

g_{p,l}(L) = max{g_{p,ϵ}(ṽ_{i})|1 ≤ i ≤ n} ∈ ZZ.

Define the following C-linear maps by their action on the basis elements u_{i} and v_{i}

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

With ũ_{i} and ṽ_{i} as above, every non-zero ũ ∈ V_{p}(L_{ϵ}) can be written as

ũ = ϵ^{v_{ϵ,l}(ũ)} ∑_{i} a_{i}ũ_{i} = ϵ^{v_{ϵ,r}(ũ)} ∑_{i} b_{i}ṽ_{i}

for some a_{i}, b_{i} ∈ C(ϵ) with v_{ϵ}(a_{i}) ≥ 0 and v_{ϵ}(b_{i}) ≥ 0. As a consequence

g_{p,r}(L) = min(\overline{g}_{p}(L)) and g_{p,l}(L) = max(\overline{g}_{p}(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 ambiguity could occur, these maps should be denoted as E_{p,r,L} and E_{p,l,L}. If g_{p,ϵ}(ũ_{i}) < g_{p,ϵ}(ṽ_{j}) then one can verify that

{g_{p,ϵ}(ũ_{i} + cϵ^{m}ṽ_{j})|c ∈ C, m ∈ ZZ} = {e ∈ ZZ|g_{p,ϵ}(ũ_{i}) ≤ e ≤ g_{p,ϵ}(ṽ_{j})}

and hence the set of valuation growths \overline{g}_{p}(L) is given by the following formula

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

To compute this set we need to use the recurrence relation (the operator L_{ϵ}) to compute the values of the ũ_{i} at the points on the right of q_{r} (recall that q_{r} is the largest problem point at p); we need to compute ũ_{i}(q_{r} + 1), …, ũ_{i}(q_{r} + n). And we need to compute the values of the ṽ_{i} on the left of q_{l}. Then g_{p,r}(L) and g_{p,l}(L) can be determined from the ϵ-valuation of these values. This computation should be done modulo a suitable power of ϵ in order to reduce intermediate expression swell. We can combine this with modular arithmetic to eliminate expression swell. The ϵ-valuations of these ũ_{i} and ṽ_{i} at the points between q_{l} and q_{r} can be used to bound the denominators of rational solutions (this statement is the content of [12]).

The valuation growth g_{p} has been defined for (solutions of) operators L of order 1 (c.f. definition 9) and corresponds to the valuation growth g_{p,ϵ} of solutions of L_{ϵ}. For higher order L, if u ∈ V (L) is hypergeometric, g_{p}(u) has been defined as the valuation growth of the corresponding right-hand factor τ − τ(u)/u ∈ k[τ] of L. However, in general g_{p}(u) can not be defined for every u ∈ V (L). Because if g_{p}(u) for u ∈ V (L) can be defined, and p is an essential singularity, then g_{p}(u) is either not minimal, or not maximal (or both), so (use any embedding V → V_{p,r} and V → V_{p,l}) we have u ∈ Ker(E_{p,r}), or u ∈ Ker(E_{p,l}) (or both). This can not hold for all u ∈ V (L) because a vector space V (L) can not be the union of two vector spaces Ker(E_{p,r}) and Ker(E_{p,l}) of lower dimension. Hence one can not define g_{p}(u) for all u ∈ V (L) in a way that corresponds to the definition of g_{p,ϵ}.

If L_{1} and L_{2} are normal operators of order 1, then we have seen that g(L_{1}◯ s L_{2}) = g(L_{1}) + g(L_{2}). It is not difficult to prove the following generalization Lemma 6 Let L_{1}, L_{2} ∈ k[τ] be normal, and let order(L_{2}) = 1. Then \overline{g}_{p}(L_{1}◯ s L_{2}) = \{e + g_{p}(L_{2})|e ∈ \overline{g}_{p}(L_{1})\} for all p ∈ C/ZZ ⋃\{∞\}.

Lemma 7 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 E_{p,r} ∘ E_{p,l} = 0 and E_{p,l} ∘ E_{p,r} = 0, in other words

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

Proof: E_{p,r}(E_{p,l}(v_{i})) = E_{p,r}(ρ_{l}(ṽ_{i}ϵ^{g_{p,l}(L)})) = ρ_{r}(ṽ_{i}ϵ^{g_{p,l}(L)}/ϵ^{g_{p,r}(L)}) = ρ_{r}(ṽ_{i}ϵ^{s}) where s = g_{p,l}(L) − g_{p,r}(L). Now v_{ϵ,r}(ṽ_{i}ϵ^{s}) = v_{ϵ,r}(ṽ_{i}) + s = s, which is > 0 if p is an essential singularity and 0 otherwise. In the former case ρ_{r}(ṽ_{i}ϵ^{s}) = 0, and in the latter case ρ_{r}(ṽ_{i}ϵ^{s}) = v_{i}. The linear map E_{p,l} ∘ E_{p,r} can be computed in the same way.

□

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 [16]) of L. However, at essential 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.

5 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 u can be found by trying all possible values of 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} ∈ k[τ] 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 Fuchs’ relations do

(a) Construct r ∈ k^{∗} such that all 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. Output: result.

Step 3a is theorem 1 and computing \overline{g}_{p_{i}}(L) is section 4.2. Note that we could remove all apparent finite singularities from S, 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 C_{0} of C such that L ∈ C_{0}(x)[τ]. This is always a finite extension of Q and hence not an algebraically closed field. After multiplying by a polynomial we may assume that the coefficients a_{i} of L = a_{n}τ^{n} +⋯+a_{0}τ^{0} are in C_{0}[x]. Then the algorithm in [15] computes in the splitting field of a_{n}a_{0} over K. The degree of this field extension can be very high, in which case the computation becomes infeasible. Avoiding large algebraic extensions is the main problem in computing hypergeometric solutions. Results on this are given in [9] for order 2, where one tries all factors of the discriminant of the defining polynomial of the singularities. If C_{0} = Q then one has to factor in ZZ (works fine unless the coefficients are big) but for larger fields this becomes complicated.

The algorithm above computes in a splitting field; the field generated by all essential singularities. This is a subfield of the splitting field of a_{n}a_{0}. Since semi-apparent singularities do not contribute to this subfield, it can be much smaller than the splitting field of a_{n}a_{0}, and this makes significant difference. However, although less frequent, the problem of exponentially large algebraic extensions can still occur in the above algorithm, causing the computer to “run forever” or run out of memory. So the main problem has been reduced, not yet solved. The introduction of finite singularities is the main result of this paper because it makes it possible to solve this problem. For order < 4 this is done in section 6 using the maps E_{p,l} and E_{p,r}. The higher order case is more technical as there are more cases to distinguish. This will be done later.

Another advantage of our algorithm is that the number of cases (the number of loops in step 3) in our algorithm is in general much smaller than (but at most equal to) the number of cases in [15], where one takes all combinations of all factors of a_{0} with all factors of a_{n}. If a_{n} is square-free then the number of factors of a_{n} is 2^{d} where d is the degree.

6 Avoiding splitting fields.

When during the computation 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 (c.f. [8] or [1]). Multiplying the hypergeometric solutions of M by u gives the hypergeometric solutions of L. This process is known as reduction of order. It may speed up the algorithm in the previous section if a hypergeometric solution is found early in the computation, but it is not always an improvement.

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 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 7 we have Im(E_{p,r}) = Ker(E_{p,l}) and Im(E_{p,l}) = Ker(E_{p,r}) at every essential singularity p. 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 two 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 C_{p} ⊂ C be the smallest field over which p and L are defined. Then all right-hand factors τ − r that we find are defined over C_{p}, because Ker(E_{p,r}) and Ker(E_{p,l}) are 1-dimensional and are defined over C_{p}. So then r must be an element of C_{p}(x) for every essential singularity p, and we can conclude

Theorem 2 Let L ∈ C_{0}(x)[τ] be an operator of order 2, where C_{0} ⊂ C and let C_{p} = C_{0}(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} C_{p}.

If S = ∅ then computing the first order right-hand factors is easy. In this case the only algebraic extension needed is the c ∈ C^{∗} in (c, n, d) at infinity, 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.

A similar result can be obtained for order 3. To compute the hypergeometric solutions efficiently, we first try only those r in step 3a of the algorithm that involve no algebraic extensions. Splitting fields over C_{0} are not needed for this computation. If no hypergeometric solutions are found this way then we use the lemma and theorem below in order to find all hypergeometric solutions (including the ones that involve algebraic extensions) without having to compute with splitting fields.

Lemma 8 Let L ∈ C_{0}(x)[τ] a monic normal operator of order 3. If L has a first order righthand factor τ −r ∈ k[τ] and no first order right-hand factor in C_{0}(x)[τ] then L can be written as L = LCLM(τ −r_{1}, τ −r_{2}, τ −r_{3}) for some r_{i} ∈ \overline{C_{0}}(x) or as L = L_{1}L_{2} for some L_{1}, L_{2} ∈ C_{0}(x)[∂] with order(L_{2}) = 2.

Proof: If L has a first order right-hand factor in k[τ] then using the algorithm in section 5 we can find a first order right-hand factor τ − r ∈ \overline{C_{0}}(x)[τ]. Then take L_{2} as the LCLM of τ − r and its conjugates over C_{0}. One sees that L_{2} is invariant under the Galois group of \overline{C_{0}}/C_{0} and hence L_{2} ∈ C_{0}(x)[∂]. If order(L_{2}) = 3 then the first case holds, otherwise the second case.

□

In the second case in the lemma we can find L_{1} by computing those hypergeometric solutions of the adjoint of L (see [1] for a definition) that involve no algebraic extensions of C_{0}. Then to compute the hypergeometric solutions of L we apply theorem 2 on L_{2}. The remaining case is that L is an LCLM of three first-order operators in \overline{C_{0}}(x)[τ].

Theorem 3 Let L ∈ C_{0}(x)[τ] be a monic normal operator of order 3 which is reducible in k[τ]. Let p ∈ C/ZZ be an essential singularity. Then L is reducible in C_{p}(x)[τ].

Proof: We may assume that L is irreducible in C_{0}(x)[τ] and reducible in k[τ]. Then lemma 8 says that L = LCLM(τ − r_{1}, τ − r_{2}, τ − r_{3}) for some r_{i} ∈ \overline{C_{0}}(x).

Let u_{i} ∈ H^{∗} be a solution of τ − r_{i}, for i ∈ {1, 2, 3}. The solution space of LCLM(τ − r_{1}, τ − r_{2}, τ −r_{3}) is spanned by the u_{i}, and hence the u_{i} are linearly independent. For each of the u_{i}, the valuation growth is not minimal (then u_{i} ∈ Ker(E_{p,r})) or not maximal (then u_{i} ∈ Ker(E_{p,l})). The dimension of these kernels is at most 2 (the order minus 1). At least one of the following two cases must hold: at least two u_{i} do not have minimal valuation growth, or at least two u_{i} do not have maximal valuation growth. Hence at least one of the the two kernels is spanned by two of the u_{i}. Assume that Ker(E_{p,r}) is spanned by u_{1}, u_{2}. Let M = LCLM(τ − r_{1}, τ − r_{2}). Then V_{p,l}(M) = Ker(E_{p,r}), and hence this solution space is defined over the field C_{p}, or equivalently, the Galois group of \overline{C_{0}}/C_{p} maps V_{p,l}(M) to itself. Since the monic normal operator M is uniquely determined by its solution space, it follows that M is invariant under this Galois group as well, and hence L has a right-hand factor M ∈ C_{p}(x)[τ] of order 2. Now L = NM for some N ∈ C_{p}(x)[τ] of order 1. To find a right-hand factor in C_{p}(x)[τ] of L of order 1, we can compute those hypergeometric solutions of L that have the same type as N.

□

Note that if there are no essential singularities, then the only algebraic extension needed in the algorithm is the c of the (c, n, d) at the point infinity. This is an algebraic extension of degree ≤ 3.

The consequence of theorems 2 and 3 is that computing hypergeometric solutions of operators of order ≤ 3 can be done very efficiently, because either a singularity p is semi-apparent (and can be discarded after a transformation of L), or p reduces the algebraic extension of C_{0} over which solutions have to be searched. For order ≤ 3 the algebraic extensions we have to compute with will be small because of this. Once we know a field C over which the solutions can be found, then we do not need to use splitting fields anymore, because we can apply the following algorithm.

Algorithm: Compute all hypergeometric solutions that are defined over a given field C ⊂ C. Input: L = ∑_{i=0}^{n} a_{i}τ^{i} where a_{i} ∈ C[x] with a_{0} and a_{n} non-zero. Output: all solutions u of L for which τ(u)/u ∈ C(x).

1. Let S be the set of irreducible monic factors of a_{0}a_{n} in C[x]. Whenever S contains two factors P ≠ Q for which P (x) = Q(x+i) for some integer i remove either P or Q, until there are no more factors in S that are an integer shift of each other. Let S = {P_{1}, …, P_{m−1}} be the set of factors that remains. The singularities are the roots (modulo the integers) of these polynomials and the point at infinity.

2. Compute \overline{g}_{∞}(L) using the τ and δ polygon, see section 3. Remove the elements from \overline{g}_{∞}(L) that are not defined over C. If there are no elements left then then there are no non-zero hypergeometric solutions defined over C.

3. For each P_{k} ∈ S do

(a) Let α_{k} be root of P_{k}. This can be done by introducing a new variable Y and letting C(α_{k}) = C[Y]/(P_{k}(Y)). Now p_{k} = α_{k}+ZZ ∈ C/ZZ is a finite singularity of L. Compute the roots of a_{0} and a_{n} on p_{k} and determine the smallest and largest problem point q_{l} and q_{r} on p_{k}.

(b) Let ũ_{i}(q_{l} − j) be 1 if i = j and 0 if i ≠ j for all integers i, j from 1 to n, and the same for ṽ_{i}(q_{r} + j).

(c) Letting ũ_{i} and ṽ_{i} be solutions of L_{ϵ} determines ũ_{i}(q), ṽ_{i}(q) ∈ C(α_{k}, ϵ) for every q ∈ p_{k}. These values can be computed by applying the recurrence relation given by L_{ϵ}.

(d) \overline{g}_{p_{k}}(L) is a set of consecutive integers. Compute the right-valuation of the ũ_{i} by computing the smallest ϵ-valuation of ũ_{i}(q_{r} + j) where j runs from 1 through n. The smallest right-valuation of the ũ_{i} equals the smallest element of \overline{g}_{p_{k}}(L). Then compute the smallest left-valuation of the ṽ_{i}. Multiply this by −1 to obtain the largest element of \overline{g}_{p_{k}}(L).

4. Let p_{m} = ∞. For every combination (e_{1}, …, e_{m}) with e_{i} ∈ \overline{g}_{p_{i}}(L) that satisfies the Fuchs’ relations do

(a) Now e_{1}, …, e_{m−1} are integers and that e_{m} is a 3-tuple. Let c be the first entry of e_{m}. Let r = c ∏_{i=1}^{m−1} P_{i}^{e_{i}}, so g_{p_{i}}(τ − r) = e_{i} for i from 1 through m − 1. Note that the fact that the e_{i} satisfy Fuchs’ relations simply means that g_{∞}(τ − r) = e_{m}.

(b) Compute the rational solutions of L◯ s (τ −1/r). Multiply them by a non-zero solution of τ −r and return the product as output. Note that to compute rational solutions we first need to bound the denominators of rational solutions; for each point q we need a lower bound for the valuation of these rational solutions at q. Such a bound can be obtained from the ϵ-valuation of the ũ_{i}(q) and ṽ_{i}(q). This idea is treated in more detail for the case of systems in [12].

The following remarks are topics for a subsequent paper. The set \overline{g}_{p} can also be defined and computed for systems of equations τ(Y) = AY where A ∈ GL_{n}(k), without having to use cyclic vectors, so our algorithm works for systems as well. In fact the definition for systems when p is finite is less technical than the one for operators given in this paper. Furthermore certain facts, for example that \overline{g}_{p}(L) depends only on the type of L, are easier to prove using systems. A reason for treating only operators in this paper is that the three given theorems easier to prove that way.

The same methods can also be used to compute solutions that are m-interlacings of hypergeometric sequences (see [10] for a definition), because the valuation growths are the same and computing bounds for the denominators of interlacings of rational functions also works the same. The methods in this paper can be applied for q-difference equations as well if q is not a root of unity. The main difference is that in the q-difference case there are two special singularities (0 and infinity) instead of just one, and so the Fuchs’ relations will be different.

References

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

[2] S. A. Abramov, M.A. Barkatou. Rational Solutions of First Order Linear Difference Systems, to appear in ISSAC’98 Proceedings (1998).

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

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

[5] E. Beke. Die Irreduzibilität der homogenen linearen Differentialgleichungen, Math. Ann. 45, p. 278-294, 1894.

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

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

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

[9] P. A. Hendriks. Algebraic aspects of linear differential and difference equations. Ph.D thesis. Rijksuniversiteit Groningen, 1996.

[10] P. A. Hendriks, M.F. Singer. Solving Difference Equations in Finite Terms. preprint. Avail-

   able from http://www.math.ncsu.edu/~singer

[11] M. van Hoeij. Factorization of Differential Operators with Rational Functions Coefficients. J. Symbolic Comput., 24, 537-561, 1997.

[12] M. van Hoeij. Rational Solutions of Linear Difference Equations. to appear in ISSAC’98

   Proceedings, 1998. Available from http://www.math.fsu.edu/~hoeij/papers.html

[13] A.H.M. Levelt, A. Fahim. Characteristic classes for difference operators. to appear in Compositio Mathematica.

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

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

[16] M. van der Put, M.F. Singer. Galois Theory of Difference Equations. Lecture Notes in Mathematics, Vol. 1666, Springer-Verlag, ISBN 3-540-63243-3, 1997.

[17] M.F. Singer. Testing reducibility of linear differential operators: a group theoretic perspective. Applicable Algebra in Engineering, Communication and Computing, 7, 77–104, 1996.

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