Difference Equations with Hypergeometric Coefficients
Manuel Bronstein
Café Project, INRIA SophiaAntipolis
Algorithms Seminar
March 3, 2000
[summary by Anne Fredet]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
Let k be a difference field with automorphism s. Let b be
an element of k, and L be a linear ordinary difference operator
with coefficients in k. A classical problem in the theory of
difference equations is to compute all the solutions in k of the
equation L(y)=b. If C denotes a constant field and if k=C(n)
and s n =n+1 or s n =qn, there are known algorithms (see
[2] for example). Manuel Bronstein presents here a
generalization to monomial extensions of C(n) (see
[5] for details and generalization).
1 Historical Context
The rational solutions of linear differential equations (equations of
the form å_{i=0}^{n} a_{i} y^{(i)}) have been first studied a long
time ago, for example by Beke and Schlesinger at the end of the last
century. In the middle of this century, R. H. Risch gave an
algorithm to compute elementary integrals (see
[11, 12, 13]). In [8], M. Karr considered
difference equations (equations of the form å_{i=0}^{n} a_{i}
y(x+i)). The link between the linear differential equations and the
linear difference equations is now clear, and in [1], an
algorithm to compute the rational solutions of this two types of
equations with coefficients in C(x) is given. In [2],
the author extends the previous algorithm to qlinear difference
equations (equations of the form å_{i=0}^{n} a_{i} y(q^{i} x)).
Algorithms to compute the rational solutions of linear differential,
difference and qdifference equations with coefficients in C(x)
are now available, and extensions of C(x) have been considered.
In [14], M. F. Singer gives an algorithm to compute the
rational solutions of linear differential equations with coefficients
in almost all the Liouvillian extensions of C(x), i.e., the
extensions built up using integral, exponential of integral, and
algebraic functions. In [7], the authors improve
the algorithm for the rational solutions of linear differential
equations with coefficients in an exponential extension of C(x). In
[6], M. Bronstein adapts the algorithm given in
[1] to monomial extensions, and in [5],
the author uses the methods given in [2, 6] to
find the solutions of linear difference equations in their coefficient
field.
2 Introduction
In [6], the author introduced the splitting
factorization: he decomposed a polynomial in two factors, the
normal part where every irreducible factor is coprime with
its derivative, and the special part where every irreducible
factor divides its derivative. He then gave an algorithm to compute
the normal part of the denominator of rational solutions of a linear
differential equation with coefficients in a monomial extension. In
[2], S. Abramov proposed an algorithm to compute a
polynomial which is divisible by the denominator of any rational
solution of a linear difference equation with coefficients in C(n),
where s n =n+1 or s n = qn. In
[7], a method to compute the numerator of the
rational solution of a linear differential equation with coefficients
in an exponential extension of C(x) is given. Manuel Bronstein now
considers difference equations with hypergeometric terms in the
coefficients (a term h(n) is hypergeometric if h(n+1)/h(n) is in
C(n)). He adapts the previous methods to difference equations with
coefficients in an hypergeometric extension of C(n), and this gives
an efficient algorithm to compute the rational solutions of such
equations. Remark that an algorithm to compute the hypergeometric
solutions of linear difference equation with coefficients in C(n) is
given in [10] and in [4] for
qhypergeometric solutions of qdifference equations.
3 Difference Equations and Hypergeometric Extensions
Let R be a commutative ring of characteristic 0.
Let s be an automorphism of R.
Define

R_{s} = { x Î R such that s x = x } (the
set of invariant elements of R);
 R_{s }^{*} = { x Î R such that s ^{n} x
= x for some n>0 } (the set of periodic elements);
 R^{s} = { x Î R such that s x = ux
for some u Î R^{*} } (the set of semiinvariant elements);
 R^{s }^{*} = { x Î R such that s ^{n} x
= ux for some n>0, u Î R^{*} } (the set of
semiperiodic elements).
It is clear that we have the inclusion R_{s} Í
R^{s} Í R^{s }^{*}. If R is a unique
factorization domain then R ^{s }^{*} is closed under
taking factors, i.e., for any polynomial q in R^{s }^{*},
each factor p of q is in R^{s }^{*}. This property is
false for R_{s} and R^{s}, as shown by the example
R=Q[t] and s(t) = 1t: s (1t) = t and s (t 
t^{2}) = t  t^{2} is in R_{s} (and then in R^{s} and in
R^{s }^{*}), whereas t and 1t are in R^{s
}^{*}, but neither in R^{s} nor in R_{s}.
3.1 Monomial extensions
Let k be a difference field with automorphism s.
Let (K,s) be an extension of (k,s).
Definition 1
t in K is a monomial over k if t is transcendental
over k with s t in k[t].
Let s be an automorphism of K such that s(t) is in
k[t]. Then s induces an automorphism of k(t), an
automorphism of k[t], and thus s(t) = a t + b for some a
in k^{*} and b in k
Proposition 1 [[9]]
If for all w in k^{*} we have s w ¹ aw +b, then t
is transcendental over k and the following equalities hold: k(t)
_{s} = k_{s} and k[t] ^{s} = k[t] ^{s}^{*} =
k.
3.2 Hypergeometric extensions
Let s be such that s t = at for some a Î k^{*}.
Proposition 2 [[9]]
If for all w in k ^{*} and n >0 we have s w ¹ a ^{n}
w, then t is transcendental over k and the following equalities
hold: k(t) _{s} = k_{s} and k[t] ^{s} = k[t]
^{s }^{*} = { c t^{m} c Î k, m³ 0 }.
For example, in C[n], let s be such that s n = q n for
some q Î C ^{*}. The property holds whenever q is not a root
of unity. Or we can consider C[n,t], with s such that
s_{ C} = id_{C}, s n = n+1 and s t = (n+1)
t; in other words t represents n!.
4 Dispersion
Definition 2
Let K be a field of characteristic 0.
Let f: K[X] ® K[X] be a function.
Let p and q be nonzero polynomials in K[X].
One defines

the spread of p and q with respect to f:
Spr 

(p,q) = { m ³ 0 such that p
and f ^{m} q have a non trivial gcd } 
 the dispersion of p and q with respect to f:
Dis 

(p,q)= 

1 

max(Spr(p,q)) 
if Spr 

(p,q) is a finite
nonempty set; 

+ ¥ 
if Spr 

(p,q) is an infinite
set. 



These definitions are specialized to the case p=q: Spr_{f}(p) = Spr_{f}(p,p) and Dis_{f}(p)=Dis_{f}(p,p).
Examples are:

Dis_{d/dx} (p(x)) is
the maximum of the multiplicity of a root of p minus 1;
 Spr_{n ® n+1}
(p(n)) is finite (and then Dis_{n ® n+1}
(p(n)) < + ¥);
 Dis_{n ® qn}
(n) is infinite.
Let s be an automorphism of k[t] such that s k Í
k.
Then the dispersion Dis_{s}(q) is infinite if and only if there exists p in
k[t]^{s }^{*} \ k such that p divides q.
Also, the dispersion Dis_{s}(h,q) is infinite if and only if there exists p in
k[t]^{s }^{*} \ k such that p divides q and
s ^{n} p divides h.
Example 1
Let a=2n^{7} + 19n^{6}+63n^{5}+81n^{4}+27n^{3} be in Q[n] and f be the
automorphism of Q[n] over Q that maps n to n+1.
The resultant of a and f ^{m} a is 4m^{19} (2m+5)^{3} (2m+1)^{3}
(2m1)^{3} (2m5)^{3} (m3)^{9} (m+3)^{9},
implying that
Spr_{f}(a)={0,3} and Dis_{f}(a)=3
4.1 Splitting factorization
One now extends the splitting factorization of polynomials to
difference field: let q in k[t] be decomposed into two factors q
= q_{¥} q such that

the gcd of q_{¥} and q is equal to 1,
 for all irreducible factor p of q, p divides q_{¥}
if p is in k[t] ^{s }^{*},
 and for all irreducible factor p of q, p divides q
if p is not in k[t] ^{s }^{*}.
The polynomial q_{¥} is the infinite part of q, and
q is its finite part.
We note that the dispersion Dis_{s}
(q) is finite, the dispersion
Dis_{s}(q_{¥}) is infinite, and
for all h the dispersion
Dis_{s}(h,q) is finite.
4.2 sOrbits
Given a and b in a field K, the problem of the orbit is
to find m ³ 0 such that a ^{m} = b. A bound for the
smallest m such that a ^{m} = b is given in
[3]. The main ideas are as follows: if there exists d
such that a ^{d} =1 then one can test whether a ^{i} = b
for 0 £ i £ d. If it is not the case, then the orbit problem
has no solution, otherwise its solutions consist of all the integers
of the form i_{0} + kd_{0} where k ³ 0, i_{0} is the smallest i
³ 0 such that a ^{i} = b and d_{0} is the smallest d >0
such that a ^{d} =1. One can now assume that a is not a
root of unity, which implies that the orbit problem has at most one
solution. If a is transcendental over Q, the orbit problem
has a solution if and only if b is algebraic over
Q(a). Looking at the degree at which a appears in
b gives at most one candidate solution for the orbit problem.
One can now assume that a is algebraic over Q. This
generalizes to find m ³ 0 such that a ^{m,s} = a
( s a ) ... (
s ^{m1} a) = b (see [3]).
4.3 Computation of the dispersion
Let s: K[X] ® K[X] be an automorphism such that
s K Í K. Then
Spr 

æ ç ç è 


p 

, 

q 


ö ÷ ÷ ø 
=


Spr 

(p_{i},q_{j})
and
Dis 

æ ç ç è 


p 

, Õ 
_{j} q 


ö ÷ ÷ ø 
= 

Dis 

(p_{i},q_{j}).

The computation of the dispersion reduces to the computation of the
dispersion of two irreducible polynomials.
Let p and q be irreducible polynomials.
Let m be in Spr_{s}(p,q). This means that
the greatest common divisor of p and s ^{m} q is not trivial. The polynomials being irreducible,
this is equivalent to the existence of u in K ^{*} such that
s ^{m} q = u p. This implies that deg p=deg q.
One just has to consider irreducible polynomials with common
degree.
Let p and q be monic irreducible polynomials of k[t] with degree n:
p = t^{n} + å_{i=0}^{n1} p_{i} t^{i} and q = t^{n} + å_{i=0}^{n1}
q_{i} t^{i}.
Assume that s t = at for some a Î k^{*}.
Then m is in Spr_{s}(p,q) implies a_{i}^{m,s} = b_{i} for all
i such that p_{i} q_{i} ¹ 0, where b_{i} =q_{i}/p_{i} and
a_{i} = a ^{ni} q_{i} / s q_{i}.
Therefore, if Spr_{s}(p,q) is not empty then
p_{i} and q_{i} vanish simultaneously.
If p=q=t then Dis(p,q)=+¥.
Otherwise, this reduces to the orbit problem a ^{m,s} = b
for a, b in k^{*} and m in Spr(p,q).
Remark that if s w ¹ a ^{d} w for all w in k^{*} and
d>0 then a ^{d} ¹ 1 for all d>0. So, the orbit problem has
at most one solution and then Spr_{s}(p,q) has
at most one element.
One can extend the computation of the dispersion to rational functions:
let f = p/q with relatively prime p and q in C[n].
Let Dis_{s}(f) = max ( Dis_{s} (p), Dis_{s}(p,q) , Dis_{s}(q,p) , Dis_{s} (q)) and n _{¥}(f) =
deg q  deg p.
Then n_{¥} (f ^{m,s}) = m n _{¥}(f).
And if f is not in C then Dis_{s}(f
^{m,s}) = Dis_{s}(f) + m 1.
This last equality allows us to reduce orbit problems to dispersions
whenever a is not constant.
5 Rational Solutions of Difference Equations
Let t be a monomial over k=C(n).
Let s be such that s n = n+1 and s t = at for
some a in k such that s w ¹ a ^{d} w, for all w in
k^{*} and d >0.
Let L = å_{i=0}^{N} a_{i} s ^{i} be a linear difference operator, with
the a_{i}'s in k[t] and both a_{0} and a_{N} not equal to 0.
Let b be in k[t].
The aim of this section is to described an algorithm to find y in
k(t) such that L(y)=b (if there exists such a y).
5.1 Denominator of a rational solution
The first problem is to find a bound for the finite part of any y in
k(t) such that L(y)=b. This means to compute a polynomial q in
k[t] such that if L(y)=b then yq = p/d_{¥} where p is in
k[t] and d_{¥} in k[t] ^{s }^{*}. We outline the
ideas here, proofs and technical details are given in [5].
Let a_{0} be decomposed: a_{0} = a_{0,¥} a_{0}.
Let y be in k(t) such that L(y) = b, where y=p/d and
d = d_{¥} d.
Then Dis_{s}(d)£max(1, Dis_{s}
(a_{N},a_{0})  N).
Let h >0 be an integer.
One can compute an operator L_{h} = b_{s} s^{sh} + b_{s1} s
^{(s1)h} + ... + b_{0} such that L_{h} = RL for some R in
k(t)[s].
It follows that L_{h}(y) = Rb for any b in k[t] and any solution y
in k(t) of L(y)=b.
We get that every solution y in k(t) of L(y)=b satisfies an
equation of the form c_{s} s ^{hs}(y) + ... + c_{1} s
^{h}(y) = d_{h}
where c_{0},...,c_{s},d_{h} are in k[t] and c_{s} ¹ 0.
If h was chosen such that
Dis_{s}(d) < h then d
divides gcd_{0 £ i £ s} ( s ^{ih} c_{i} ).
This gives us a polynomial q such that if L(y) = b then qy =
p/d_{¥} with p in k[t] and d_{¥} in
k[t] ^{s }^{*}
Example 2
Consider y(n+2)  (n! + n) y(n+1) + n(n!
1) y(n) =0.
If we define s by s n=n+1 and s t = (n+1) t then
the associated difference operator is s ^{2}  (t+n) s + n(t
1).
a_{N} = 1, a_{0} = a_{0} = n(t1) and
Dis_{s}(a_{N},a_{0}) = 1.
Then Dis_{s}(d) £ 1 and d Î C(n).
So, if there exists y Î C(n)(t) such that L(y)=b then y is in C(n)[t,t^{1}].
Remark 1
The same results holds for the qdifference equation:
let q be transcendental over Q.
Let s be such that s x = qx.
Consider the qdifference equation

q^{3} (qx+1) y(q^{2}x)  2 q^{2} (x+1) y(qx) + (x+q) y(x)=0 
We have a_{0}=x+q, a_{2} = q^{3} (qx+1).
The resultant of a_{2} and s ^{m} (a_{0}) is q^{3} (q^{2} 
q^{m}), which implies that
Dis_{s}(a_{2},a_{0})=2 hence that any
solution of (1) has a denominator of the form x^{n}
d where Dis_{s}(d) £ 0.
Using the bound h=1, we get L_{h} = L and d divides the
greatest common divisor of gcd_{0 £ i £ 2} ( s^{i} a_{i})
= gcd (x+q,s ^{1} (q^{2} (x+1)),s^{2} (q^{3}
(qx+1))) = gcd(x+q,q(x+q),q^{2}(x+q))=x+q.
Therefore, any rational solution of (1) can be written
as y=p/ (x^{n} (x+q)) where n ³ 0 and p is in Q[x].
The indicial equation at x=0 is qZ^{2} 2q^{2}Z+q^{3}=0 (see
[2]). Its only solution of the form Z=q^{n} is for
n=1, which implies that any rational solution of
(1) can be written as y=p/(x(x+q)).
Replacing y by this form, we get p(q^{2} x)  2 p(qx)+p(x)=0 (whose
solution space is Q (q), which implies that the general rational
solution of (1) is y=C/(x(x+q)) for any
C in Q (q)).
5.2 Laurent polynomial solution
The problem of finding rational solutions y of L(y)=b is reduced
to finding y in k[t,t^{1}] such that L(y)=b, where b is in
k[t,t^{1}] and L =å_{i=0}^{N} a_{i} s ^{i} is a difference
operator, with a_{i} Î k[t] and nonzero a_{0} and a_{N}. This
decomposes in two steps:

find a bound for the degree and the order in t of y;
 compute the coefficients of y, seen as a Laurent polynomial in t.
5.2.1 Bound for the degree and order of a polynomial solution
One rewrites L as å_{j=n}^{d} t^{j} L_{j} where the L_{j}'s are
in k[s] and L_{n} and L_{d} are not equal to zero. Let
y=y_{d}t^{d}+...+y_{g}t^{g} be in k[t,t^{1}]
for integers g and d satisfying g
³ d and such that neither y_{d} nor y_{g} is equal
to zero. Let b be in k[t,t^{1}]. If L(y)=b, then

either d ³ n(b)  n, or L_{n}(y_{d}t^{d})=0;
 either g £ deg bd, or L_{d} (y_{g}t^{g})=0.
The problem is reduced to considering difference operators T =
å_{i=m}^{M} A_{i} s ^{i} with A_{i} Î C[n] for nonzero A_{m}
and A_{M}, and to searching bounds for gÎZ such that T(z
t^{g})=0 for some z in C(n). Let e = n _{¥}
(s t/t) = n _{¥}(a). There are three possibilities:

if e > 0 then (deg_{n}A_{m} deg_{n}T)/e £ g £
(deg_{n}T  deg_{n}A_{M})/e;
 if e <0 then (deg_{n}T  deg_{n}A_{m})/e £ g £
(deg_{n}A_{m}  deg_{n}T)/e;
 if e=0 then a = a(¥) Î C^{*}. We
decompose A_{i} = a_{i,a}_{i} n^{a}_{i}+ ··· .
We define Q(z) = å_{ia}_{i}_{ = }_{max}_{j}_{ (a}_{j}_{) }
a_{i,a}_{i} z^{i}. We have Q(a ^{g})=0. This problem can be solved if a ^{d} ¹
1 for all d ³ 0 (see section 4.2).
5.2.2 Coefficients of a Laurent polynomial solution
This is a generalization of the specialization given in [7].
We have found g and d such that if y is in
k[t,t^{1}] with L(y)=b then deg_{t} (y) £ g and val_{t}(y)
³ d.
Let z=t^{d}y. Note that deg_{t}(z) £ g 
d = J.
One has to consider the problem L(z) =b where L is in
k[t][s] and b in k[t].
Let L = å_{j=0}^{d} t^{j} L_{j} with L_{j} in k[s], and
L_{0},L_{d} not equal to zero.

if J =0 then L(z) = å_{j=0}^{d} t^{j} (L_{j} z). But L_{j}(z)
is in k so L(z)=b implies L_{j}(z) = b_{j} for all j and this reduces
to difference equations with coefficients in C[n];
 if J >0 then one decomposes z = z_{0} + t z where
z_{0} = z(0) is in C(n).
Then L_{0}(z_{0}) = b_{0} and one can find z_{0}.
So, L(z) = (L  L_{0}) (z_{0}) + L (t z ) + L_{0}(z_{0}) and L(z) = b implies
L ( t z ) 
= 
b  b_{0}  (LL_{0}) z_{0} 

= 

This gives us a new difference equation with a solution z
of degree strictly less than J. By induction, one can find z.
Example 3
Consider y(n+2)  (n! + n) y(n+1) + n(n!
1) y(n) =0, which is associated to the difference operator
L= s ^{2}  ( t+n) s + n(t1)= t ( n  s) + (s ^{2}  n s  n ) = t L_{1} + L_{0} 
Using the same notations as previously, e =  n _{¥} (s
t/t) =  n _{¥} (n+1) =1 and then y = y_{0} + y_{1} t. One
first considers L_{0}(y_{0}) = s ^{2} y_{0}  n s y_{0} n y_{0} =0,
and finds that y_{0} = 0. Then:
L (t z_{1}) = (n+2)(n+1) t s ^{2} (z_{1}) 
(n+1)(t+n) t s(y_{1}) + n(t1) ty_{1},
from which follows that

(y_{1}) =
(n+2)(n+1) s ^{2}(y_{1})  (n+1)(t+n) s(y_{1}) + n (t1) y_{1} =0. 
This implies that y_{1} = c/n. Then y=y_{1} t = (c/n)n! = c(n1)!.
References
 [1]

Abramov (S. A.). 
Rational solutions of linear differential and difference equations
with polynomial coefficients. Computational Mathematics and Mathematical
Physics, vol. 29, n°11, 1989, pp. 16111620, 1757. 
Transl. from Akademiya Nauk SSSR. Zhurnal Vychislitelc'noi
Matematiki i Matematicheskoi Fiziki.
 [2]

Abramov (S. A.). 
Rational solutions of linear difference and qdifference equations
with polynomial coefficients. In Levelt (A. H. M.) (editor), Symbolic
and Algebraic Computation. pp. 285289. 
ACM Press, New York, 1995. Proceedings of ISSAC'95,
Montreal, Canada.
 [3]

Abramov (Sergei) and Bronstein (Manuel). 
Hypergeometric dispersion and the orbit problem. In Proceedings
of ISSAC'00, St Andrews (Scotland). 
ACM Press, 2000.
 [4]

Abramov (Sergei A.), Paule (Peter), and Petkovsek (Marko). 
qhypergeometric solutions of qdifference equations. In Proceedings of the 7th Conference on Formal Power Series and Algebraic
Combinatorics (NoisyleGrand, 1995), vol. 180, pp. 322. 
1998.
 [5]

Bronstein (Manuel). 
On solutions of linear ordinary difference equations in their
coefficient field. Journal of Symbolic Computation. 
To appear. Preliminary version available as INRIA Research Report
n°3797.
 [6]

Bronstein (Manuel). 
On solutions of linear ordinary differential equations in their
coefficient field. Journal of Symbolic Computation, vol. 13, n°4,
1992, pp. 413439.
 [7]

Bronstein (Manuel) and Fredet (Anne). 
Solving linear ordinary differential equations over
C(x,expò f(x)dx). In Dooley (Sam) (editor), ISSAC'99
(July 2931, 1999). pp. 173179. 
ACM Press, 1999. Proceedings of the 1999 International
Symposium on Symbolic and Algebraic Computation.
 [8]

Karr (Michael). 
Summation in finite terms. Journal of the ACM, vol. 28,
n°2, 1981, pp. 305350.
 [9]

Karr (Michael). 
Theory of summation in finite terms. Journal of Symbolic
Computation, vol. 1, n°3, 1985, pp. 303315.
 [10]

Petkovsek (Marko). 
Hypergeometric solutions of linear recurrences with polynomial
coefficients. Journal of Symbolic Computation, vol. 14, n°23,
1992, pp. 243264.
 [11]

Risch (R. H.). 
On the integration of elementary functions which are built up
using algebraic operations. 
Report n°SP2801/002/00, Sys. Dev. Corp., Santa Monica, CA,
1968.
 [12]

Risch (Robert H.). 
The problem of integration in finite terms. Transactions of the
AMS, vol. 139, 1969, pp. 167189.
 [13]

Risch (Robert H.). 
The solution of the problem of integration in finite terms. Bulletin of the AMS, vol. 76, 1970, pp. 605608.
 [14]

Singer (Michael F.). 
Liouvillian solutions of linear differential equations with
Liouvillian coefficients. Journal of Symbolic Computation, vol. 11,
n°3, 1991, pp. 251273.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.