Difference Equations with Hypergeometric Coefficients

Manuel Bronstein

Caf Project, INRIA Sophia-Antipolis

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=0n ai 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=0n ai 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 q-linear difference equations (equations of the form i=0n ai y(qi x)).

Algorithms to compute the rational solutions of linear differential, difference and q-difference 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 q-hypergeometric solutions of q-difference equations.

3   Difference Equations and Hypergeometric Extensions

Let R be a commutative ring of characteristic 0. Let s be an automorphism of R. Define It is clear that we have the inclusion Rs Rs Rs *. If R is a unique factorization domain then R s * is closed under taking factors, i.e., for any polynomial q in Rs *, each factor p of q is in Rs *. This property is false for Rs and Rs, as shown by the example R=Q[t] and s(t) = 1-t: s (1-t) = t and s (t - t2) = t - t2 is in Rs (and then in Rs and in Rs *), whereas t and 1-t are in Rs *, but neither in Rs nor in Rs.

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 = ks 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 = ks and k[t] s = k[t] s * = { c tm| 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 = idC, 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 non-zero polynomials in K[X]. One defines These definitions are specialized to the case p=q: Sprf(p) = Sprf(p,p) and Disf(p)=Disf(p,p).
Examples are: Let s be an automorphism of k[t] such that s k k. Then the dispersion Diss(q) is infinite if and only if there exists p in k[t]s * \ k such that p divides q. Also, the dispersion Diss(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=2n7 + 19n6+63n5+81n4+27n3 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
4m19 (2m+5)3 (2m+1)3 (2m-1)3 (2m-5)3 (m-3)9 (m+3)9,
implying that Sprf(a)={0,3} and Disf(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 polynomial q is the infinite part of q, and q is its finite part. We note that the dispersion Diss (q) is finite, the dispersion Diss(q) is infinite, and for all h the dispersion Diss(h,q) is finite.

4.2   s-Orbits

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 i0 + kd0 where k 0, i0 is the smallest i 0 such that a i = b and d0 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 m-1 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
 
s



 
i
p
ei
 
i
,
 
j
q
fj
 
j



=
 
i,j
Spr
 
s
(pi,qj)   and   Dis
 
s



 
i
p
ei
 
i
, j q
fj
 
j



=
 
max
i,j
Dis
 
s
(pi,qj).
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 Sprs(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 = tn + i=0n-1 pi ti and q = tn + i=0n-1 qi ti. Assume that s t = at for some a k*. Then m is in Sprs(p,q) implies aim,s = bi for all i such that pi qi 0, where bi =qi/pi and ai = a n-i qi / s qi. Therefore, if Sprs(p,q) is not empty then pi and qi 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 Sprs(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 Diss(f) = max ( Diss (p), Diss(p,q) , Diss(q,p) , Diss (q)) and n (f) = deg q - deg p. Then n (f m,s) = m n (f). And if f is not in C then Diss(f m,s) = Diss(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=0N ai s i be a linear difference operator, with the ai's in k[t] and both a0 and aN 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 a0 be decomposed: a0 = a0, a0. Let y be in k(t) such that L(y) = b, where y=p/d and d = d d. Then Diss(d)max(-1, Diss (aN,a0) - N). Let h >0 be an integer. One can compute an operator Lh = bs ssh + bs-1 s (s-1)h + ... + b0 such that Lh = RL for some R in k(t)[s]. It follows that Lh(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
cs s hs(y) + ... + c1 s h(y) = dh
where c0,...,cs,dh are in k[t] and cs 0. If h was chosen such that Diss(d) < h then d divides gcd0 i s ( s -ih ci ). 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). aN = 1, a0 = a0 = n(t-1) and Diss(aN,a0) = -1. Then Diss(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 q-difference equation: let q be transcendental over Q. Let s be such that s x = qx. Consider the q-difference equation
q3 (qx+1) y(q2x) - 2 q2 (x+1) y(qx) + (x+q) y(x)=0
We have a0=x+q, a2 = q3 (qx+1). The resultant of a2 and s m (a0) is q3 (q2 - qm), which implies that Diss(a2,a0)=2 hence that any solution of (1) has a denominator of the form xn d where Diss(d) 0. Using the bound h=1, we get Lh = L and d divides the greatest common divisor of gcd0 i 2 ( s-i ai) = gcd (x+q,s -1 (q2 (x+1)),s-2 (q3 (qx+1))) = gcd(x+q,q(x+q),q2(x+q))=x+q. Therefore, any rational solution of (1) can be written as y=p/ (xn (x+q)) where n 0 and p is in Q[x].

The indicial equation at
x=0 is qZ2 -2q2Z+q3=0 (see [2]). Its only solution of the form Z=qn 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(q2 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=0N ai s i is a difference operator, with ai k[t] and non-zero a0 and aN. This decomposes in two steps:
  1. find a bound for the degree and the order in t of y;
  2. 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=nd tj Lj where the Lj's are in k[s] and Ln and Ld are not equal to zero. Let y=ydtd+...+ygtg be in k[t,t-1] for integers g and d satisfying g d and such that neither yd nor yg is equal to zero. Let b be in k[t,t-1]. If L(y)=b, then
  1. either d n(b) - n, or Ln(ydtd)=0;
  2. either g deg b-d, or Ld (ygtg)=0.
The problem is reduced to considering difference operators T = i=mM Ai s i with Ai C[n] for non-zero Am and AM, and to searching bounds for gZ such that T(z tg)=0 for some z in C(n). Let e =- n (s t/t) = n (a). There are three possibilities:

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 degt (y) g and valt(y) d. Let z=tdy. Note that degt(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=0d tj Lj with Lj in k[s], and L0,Ld not equal to zero.
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(t-1)= t ( n - s) + (s 2 - n s - n ) = t L1 + L0
Using the same notations as previously, e = - n (s t/t) = - n (n+1) =1 and then y = y0 + y1 t. One first considers L0(y0) = s 2 y0 - n s y0 -n y0 =0, and finds that y0 = 0. Then:
L (t z1) = (n+2)(n+1) t s 2 (z1) - (n+1)(t+n) t s(y1) + n(t-1) ty1,
from which follows that
~
L
 
(y1) = (n+2)(n+1) s 2(y1) - (n+1)(t+n) s(y1) + n (t-1) y1 =0.
This implies that y1 = c/n. Then y=y1 t = (c/n)n! = c(n-1)!.

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. 1611--1620, 1757. -- Transl. from Akademiya Nauk SSSR. Zhurnal Vychislitelc'noi Matematiki i Matematicheskoi Fiziki.

[2]
Abramov (S. A.). -- Rational solutions of linear difference and q-difference equations with polynomial coefficients. In Levelt (A. H. M.) (editor), Symbolic and Algebraic Computation. pp. 285--289. -- 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). -- q-hypergeometric solutions of q-difference equations. In Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995), vol. 180, pp. 3--22. -- 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. 413--439.

[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 29--31, 1999). pp. 173--179. -- 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. 305--350.

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

[10]
Petkovsek (Marko). -- Hypergeometric solutions of linear recurrences with polynomial coefficients. Journal of Symbolic Computation, vol. 14, n°2-3, 1992, pp. 243--264.

[11]
Risch (R. H.). -- On the integration of elementary functions which are built up using algebraic operations. -- Report n°SP-2801/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. 167--189.

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

[14]
Singer (Michael F.). -- Liouvillian solutions of linear differential equations with Liouvillian coefficients. Journal of Symbolic Computation, vol. 11, n°3, 1991, pp. 251--273.

This document was translated from LATEX by HEVEA.