Difference Equations with Hypergeometric Coefficients

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=0ⁿ a_i y⁽ⁱ⁾) 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ⁿ 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 q-linear difference equations (equations of the form å_i=0ⁿ a_i y(qⁱ 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

R_s = { x Î R such that s x = x } (the set of invariant elements of R);
R_s^_* = { x Î R such that s ⁿ 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 semi-invariant elements);
R^s^{^*} = { x Î R such that s ⁿ x = ux for some n>0, u Î R^* } (the set of semi-periodic 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) = 1-t: s (1-t) = t and s (t - t²) = t - t² is in R_s (and then in R^s and in R^s^{^*}), whereas t and 1-t 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 ⁿ 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 non-zero polynomials in K[X]. One defines

the spread of p and q with respect to f:

Spr

f
(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

f
(p,q)=

-1

if Spr

f
(p,q) is empty;

max(Spr(p,q))

if Spr

f
(p,q) is a finite nonempty set;

+ ¥

if Spr

f
(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 ⁿ p divides h.

Example 1 Let a=2n⁷ + 19n⁶+63n⁵+81n⁴+27n³ 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¹⁹ (2m+5)³ (2m+1)³ (2m-1)³ (2m-5)³ (m-3)⁹ (m+3)⁹,

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 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 ⁱ = 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₀ + kd₀ where k ³ 0, i₀ is the smallest i ³ 0 such that a ⁱ = b and d₀ 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

æ
ç
ç
è

e_i

f_j

ö
÷
÷
ø

i,j

Spr

(p_i,q_j) and Dis

æ
ç
ç
è

e_i

, Õ

_j q

f_j

ö
÷
÷
ø

max

i,j

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ⁿ + å_i=0^n-1 p_i tⁱ and q = tⁿ + å_i=0^n-1 q_i tⁱ. 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 ^n-i 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 ⁱ be a linear difference operator, with the a_i's in k[t] and both a₀ 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₀ be decomposed: a₀ = a_0,¥ a₀. 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₀) - N). Let h >0 be an integer. One can compute an operator L_h = b_s s^sh + b_s-1 s ^(s-1)h + ... + b₀ 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₁ s ^h(y) = d_h

where c₀,...,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 ² - (t+n) s + n(t -1). a_N = 1, a₀ = a₀ = n(t-1) and Dis_s(a_N,a₀) = -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 q-difference equation: let q be transcendental over Q. Let s be such that s x = qx. Consider the q-difference equation

q³ (qx+1) y(q²x) - 2 q² (x+1) y(qx) + (x+q) y(x)=0

We have a₀=x+q, a₂ = q³ (qx+1). The resultant of a₂ and s ^m (a₀) is q³ (q² - q^m), which implies that Dis_s(a₂,a₀)=2 hence that any solution of (1) has a denominator of the form xⁿ 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² (x+1)),s^-2 (q³ (qx+1))) = gcd(x+q,q(x+q),q²(x+q))=x+q. Therefore, any rational solution of (1) can be written as y=p/ (xⁿ (x+q)) where n ³ 0 and p is in Q[x].

The indicial equation at x=0 is qZ² -2q²Z+q³=0 (see [2]). Its only solution of the form Z=qⁿ 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² 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 ⁱ is a difference operator, with a_i Î k[t] and non-zero a₀ 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_dt^d+...+y_gt^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_dt^d)=0;
either g £ deg b-d, or L_d (y_gt^g)=0.

The problem is reduced to considering difference operators T = å_i=m^M A_i s ⁱ with A_i Î C[n] for non-zero 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_nA_m -deg_nT)/e £ g £ (deg_nT - deg_nA_M)/e;
if e <0 then (deg_nT - deg_nA_m)/e £ g £ (deg_nA_m - deg_nT)/e;
if e=0 then a = a(¥) Î C^*. We decompose A_i = a_i,a_{_i} n^a_ⁱ+ ··· . We define Q(z) = å_i|a_{_i}₌_max_{_j}_(a_{_j}₎ a_i,a_{_i} zⁱ. 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^dy. 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₀,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₀ + t z where z₀ = z(0) is in C(n). Then L₀(z₀) = b₀ and one can find z₀. So, L(z) = (L - L₀) (z₀) + L (t z ) + L₀(z₀) and L(z) = b implies

L ( t z ) = b - b₀ - (L-L₀) z₀

t

~

L

(z)
=

t æ
ç
ç
è

b-b₀

t
ö
÷
÷
ø - t

(L - L₀ ) z₀

t

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 ² - ( t+n) s + n(t-1)= t ( n - s) + (s ² - n s - n ) = t L₁ + L₀

Using the same notations as previously, e = - n _¥ (s t/t) = - n _¥ (n+1) =1 and then y = y₀ + y₁ t. One first considers L₀(y₀) = s ² y₀ - n s y₀ -n y₀ =0, and finds that y₀ = 0. Then:

L (t z₁) = (n+2)(n+1) t s ² (z₁) - (n+1)(t+n) t s(y₁) + n(t-1) ty₁,

from which follows that

(y₁) = (n+2)(n+1) s ²(y₁) - (n+1)(t+n) s(y₁) + n (t-1) y₁ =0.

This implies that y₁ = c/n. Then y=y₁ 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 L^AT_EX by H^EV^EA.