Eigenring and Reducibility of Difference Equations

Raphaël Bomboy

Café Project, INRIA Sophia-Antipolis

Algorithms Seminar

March 6, 2000

[summary by Frédéric Chyzak and Pierre Nicodème]

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
The Galois theory for differential equations is now classical. We consider here a Galois theory for difference equations whose development is more recent. In analogy with the differential case, a concept of Liouvillian solutions of a difference equation is introduced, in relation to equations with solvable Galois group. In the first part of this talk, Bomboy presents the Galois theory for linear finite difference operators. Next he adapts the concept of eigenring introduced in the differential case by Singer [11] to suggest an algorithm searching for Liouvillian solutions of linear difference equations. This direct algorithm solves a subclass of the difference equations without using Petkovsek's algorithm [8].



Introduction

We review in Section 1 the basic notions of Galois theory for difference equations, following the presentation of [7]. As in the differential case, the Galois group is a linear algebraic group. In Section 2 we present the main properties of reducible and completely reducible systems, from the point of view of the structure of their associated matrices. In the differential case, a Liouvillian extension of a differential field is done by algebraic extensions and by the operations of exponentiation and integration of a function of the field. In Section 3 we define Liouvillian solutions in the difference case; these solutions are essentially interlacings of hypergeometric sequences. We describe the notion of eigenring in Section 4 and summarize relevant properties. We finish by presenting Bomboy's algorithm for searching Liouvillian solutions in Section 5, and by concluding comments.

1   Difference Galois Theory

A difference ring (k,f) is a ring k with an automorphism f. (Note that all rings considered here are rings with identity.) For example, let k be the ring C[z] of polynomials or the field C(z) of fractions, and f the automorphism that substitutes z+1 for z. When f(x)=x for xÎ k, x is called a constant of (k,f). The set C(k) of constants is a subring of k.

From now on we assume that k is a field. A (scalar) difference equation has the form
L(y)=fm(y)+am-1fm-1(y)+...+a0 y=0,     (1)
where the ai's are in k and L=fm+am-1fm-1+...+a0 is the difference operator associated to the equation. The set of difference operators or skew polynomials in f with multiplication f a=f(a)f is a non-commutative ring  Pk(f). Equation (1) can be transformed into the system f(Y)=AL Y, where f is applied componentwise to the vector Y and
AL=
æ
ç
ç
ç
ç
ç
è
0 1 0 ... 0
0 0 1 ... 0
·
·
·		 ·
·
·		 ·
·
·		 ·
·
·		 ·
·
·
-a0 -a1 ... ... (-am-1)
ö
÷
÷
÷
÷
÷
ø
.
One sees that y is a solution of L(y)=0 if and only if (y,f(y),...,fm-1(y))T is a solution of f(Y)=AL Y.

More generally, we will consider systems of difference equations of the form
f(Y)=AY     (2)
for an element A of GLn(k), the space of invertible matrices of dimension n over k. If R is a difference ring extension of k, a fundamental matrix for Equation (2) is an element U=(ui,j)ÎGLn(R) such that f(U)=AU where f maps componentwise to matrices. A difference ring extension R of k is called a Picard--Vessiot extension of k for Equation (2) if R is a simple difference ring (the only f-invariants ideals are (0) and R) and R=k[u1,1,...,un,n,(det U)-1] with U a fundamental matrix. The following theorem describes the structure of such extensions.
Theorem 1  [[12]]   If the set of constants C(k) is algebraically closed, Picard--Vessiot extensions R of k exist and are unique up to isomorphism.
The Galois group Gal(R/k) of R over k is the set of linear maps that are the identity on k and commute with f. As in the differential case, it can be proved to have a structure of a linear algebraic group over C(k). The set V of solutions of Equation (2) in Rn is an n-dimensional vector space over C(k) that is invariant by Gal(R/k). This yields a representation of Gal(R/k) in C(k)n.

Let f(Y)=AY and f(Y)=BY be two systems with A and B in GLn(k) and let VA and VB be the corresponding solution spaces in Picard--Vessiot extensions RA and RB. Both systems are equivalent if there is a matrix TÎGLn(k) such that B=f(T)AT-1. Then, if U is a fundamental matrix of f(Y)=AY, it follows that TU is a fundamental matrix for f(Y)=BY; in this case, one can identify the rings RA and RB, and VA and VB are isomorphic as Gal(R/k)-modules (defined as modules over the group algebra of Gal(R/k) with coefficients in C(k)). For a large class of difference fields, any system f(Y)=AY is equivalent to the companion system of a scalar equation [7].

We conclude this section with an illustration on the ring  S of germs of sequences over C.
Definition 1   Consider two elements (an)nÎN and (bn)nÎN of CN (where CÌC is a ring). We define the following equivalence relation: (xn)º(yn) if and only if (xn) and (yn) only differ by a finite number of terms. We now consider the quotient ring S=(CN/º) where addition and multiplication are defined componentwise; an element of this ring is called a germ.
Note that this gives us a natural embedding n of the rational function ring C(z) into  S, where for FÎC(z), n(F) is given as the germ of any (sn)nÎN such that sn=F(n) for sufficiently large n.
Definition 2   The shift s of  S maps n((x0,...,xn,...)) to n((x1,...,xn+1,...)).
From now on, the ring C is an algebraically closed subfield of C and k=n(C(z)).
Property 1  [[12]]   Let CÌ C be an algebraically closed field. There exists a Picard--Vessiot extension of the equation s(Y)=AY over C(z)Ì S that also lies in  S.
Example 1   Consider k=n(C(z)) and the equation s(x)=-x. The Picard--Vessiot extension R of k is the ring generated by k and the sequence s=(1,-1,1,-1,...). Note that if t=s+(1,1,...)=(2,0,2,...) then t×s(t)=0. The Picard--Vessiot extension therefore has zero divisors and cannot be a field.

2   Reducibility

The following theorem gives a criterion of reducibility for operators.
Theorem 2  [[3]]   Consider an operator LÎ Pk(f) with Picard--Vessiot extension R. The following statements are equivalent:
  1. L is reducible (i.e., L=L1 L2 in  Pk(f));
  2. the solution space V has a strict subspace W that is stable under the action of the Galois group G=Gal(R/k);
  3. the system f(X)=AL X is equivalent to a system with block upper triangular companion matrix.
We also consider the class of completely reducible operators.
Definition 3   Let lclm stand for least common left multiple. An operator LÎ Pk(f) is completely reducible if there exist L1, ..., Lk such that L=lclm(L1,...,Lk),
Beware that an irreducible operator L is completely reducible because L=lclm(L).
Property 2  [[3]]   The following statements are equivalent:
  1. L is completely reducible;
  2. the solution space V is expressible as a direct sum V=V1Å...Å Vk where Vi is a stable G-module for each i, and the corresponding operators are irreducible;
  3. the system f(X)=AX is equivalent to a system with block diagonal companion matrix where each block corresponds to an irreducible G-module.

3   Liouvillian Solutions

We begin this section by defining Liouvillian solutions of an equation in terms of interlacings of sequences and hypergeometric sequences. Next we give the expected Galois-theoretic characterization of Liouvillian solutions of a difference equation, before giving another characterization in terms of interlacings of hypergeometric solutions.

Definition 4   The interlacing of sequences x1, ..., xl of CN is the sequence (x01,x02,...,x0l,x11,...). This definition extends to interlacing of germs in a natural way.
Definition 5   Hypergeometric sequences are germs xÎ S such that s(x)=ax for some aÎ k.
Definition 6   The set L of Liouvillian sequences is the smallest subring of S such that:
  1. constants belong to  L, where it is understood that gÎ C(k) is identified to the germ (g,g,...)Î S;
  2. if x is hypergeometric, x belongs to L;
  3. if x is solution of s(x)=x+a with aÎ L, then x belongs to L;
  4. if x belongs to L, the interlacings of x with zero germs (i.e., the interlacings of x1=...=xl-1=0 and xl=x) belongs to L.
Example 2   Elements of k are hypergeometric, thus belong to  L; on the other hand, the germs (2n)nÎN and (n!)nÎN are two examples of hypergeometric, thus Liouvillian, sequences that are not in k.
Example 3  [Harmonic numbers]   If k=C(z) and x=(åj=1n 1/j)nÎN we have (1/(n+1))nÎN =n(1/(z+1))Î k and s(x)=x+(1/(n+1))nÎN. The germ n(x) thus belongs to  L.
Example 4   The sequence (0,1,0,1,...) is the interlacing of both constant sequences 0 and 1, and therefore belongs to  L.
The following theorem gives the expected Galois-theoretic characterization of Liouvillian sequences.
Theorem 3  [[7]]   A solution xÎ S of Equation (1) is Liouvillian if and only if the Galois group of any Picard--Vessiot extension of this equation is solvable.

We come to another characterization of Liouvillian sequences. Let Z be a fundamental system of s(X)=AX. Then by iteratively applying s to s(Z)=AZ we see that Z is solution of sm(Z)=PsmZ where Psm=sm-1(A)... A. Let t be the automorphism of C(z) substituting mz for z. Then t°sm=s°t; for i from 0 to m-1, the ith m-section t°si(Z) of Z satisfies the equation s(O)=(Ps,im A)O in the unknown O, where Ps,im A=t°si(Psm A). This gives the following theorem and corollary.
Theorem 4  [[7]]   Let L be an operator of order n over k. The following statements are equivalent:
  1. there is a Liouvillian solution for the equation L(y)=0;
  2. there exists an m less than or equal to n, such that the equation L(y)=0 has a solution that is the interlacing of m hypergeometric series;
  3. there exists an m such that, for all i between 0 and m-1, the equation s(y)=(Ps,im AL)(y) has an hypergeometric solution;
  4. there exist m and i, with i£ m, such that the equation s(y)=(Ps,im AL)(y) has an hypergeometric solution.
Corollary 1  [[7]]   Let L be an operator with coefficients in k. One can find operators H1, ..., Ht, R with coefficients in k such that
  1. L=RHt... H1;
  2. the solution space of each Hi is spanned by interlacings of hypergeometric sequences;
  3. any Liouvillian solution of L(y)=0 is a solution of Ht... H1(y)=0.

4   Eigenrings and their Structure

We consider the non-commutative ring A= Pk(s) and a difference operator LÎ A with Picard--Vessiot extension R. Let V be the space of solutions of L in R. We now describe isomorphisms between three classes of objects:
  1. eigenrings, that are rings that essentially contain operators that follow some special commutation relation with L;
  2. endomorphisms of V that commute with the Galois group G=Gal(R/k);
  3. A-module homomorphisms of A/AL into A/AL.
Eigenring of L
Given an operator L, the elements U+ALÎ A/AL such that there exists U'Î A satisfying LU=U'L clearly form a ring. We call it the eigenring E(L) of L. Note that E(L) is never empty: C(k) is always part of E(L).

G-endomorphisms of the solution space V
For PÎ A, consider the mapping hP of R into R defined by hP(v)=P· v for all v in R. This C(k)-linear mapping clearly commutes with G, since G commutes with s. We are interested in the situation when the mapping hP induces a linear map of EndGV, the algebra of C(k)-linear mappings of V into V that commute with G. Take v in V; we have L· v=0. Consider L·hP(v)=LP· v. This is zero if and only if P+AL belongs to E(L), for then there is P' such that LP=P'L. In this latter case, hP induces a G-endomorphism of V.

A-linear endomorphisms of A/AL
Consider the C(k)-algebra EndA(A/AL) of A-linear endomorphisms of A/AL, and l an element of this algebra. Recall that the module A/AL can be viewed as the A-module generated by any ``generic solution'' of L; the linear map l is thus completely described by the image of the generator 1+AL of A/AL. The map l is well-defined as an A-linear map if and only if the image l(1+AL)=U+AL abides by the relation
L(U+AL)=Ll(1+AL)=l ( L(1+AL) ) =l(0)=0,
which implies that there exists U' such that LU=U'L; in other words, U+AL is in the eigenring. The converse property is proved similarly.



With a closer look on the bijections above, one gets the following result.
Proposition 1   The three rings E(L), EndGV, and EndA(A/AL) are isomorphic.

The classical representation theory for semi-simple modules [6] applies to the study of the structure of eigenrings, yielding the following proposition and corollary.
Proposition 2  [[4]]   For an operator L with Galois group G and space of solutions V, there are ring isomorphisms between:
  1. the eigenring E(L);
  2. the endomorphism algebra EndGV;
  3. the set of matrices PÎ Mn(k) satisfying ALP=s(P)AL.
Proposition 3  [[4]]   Let L be a completely reducible operator with solution space V. Then V is isomorphic to a direct sum V1n1Å...Å Vlnl where no Vi and Vj are isomorphic for i¹ j; the eigenring E(L) is isomorphic to the direct sum Åi=1lMni(C(k)).
Corollary 2  [[4]]   Let L be a difference operator with eigenring E(L). Then:
  1. L is irreducible implies that E(L) is isomorphic to C(k);
  2. L is completely reducible and E(L) is isomorphic to C(k) imply that L is irreducible.

5   Algorithms

Eigenring

An algorithm to compute the eigenring of a differential operator was given by Singer [11]. A similar algorithm computes the eigenring in the difference case. The method proceeds by undetermined coefficients: an element of the eigenring of an operator L of order n is viewed as a residue U modulo L; it is thus represented by n undetermined rational function coefficients. One then performs the multiplication by L on the left, then the Euclidean division by L on the right. This yields a first-order linear difference system in the n unknowns. This system is then solved for rational function solutions by algorithms based on Abramov's algorithm [1].1

Linear Difference Equations of Order 2

We consider the search for Liouvillian solutions of linear difference operators in the case of order 2. As follows from the analysis in Section 3, the search for Liouvillian solutions reduces to searching for hypergeometric solutions of associated equations. Petkovsek gave an algorithm for this purpose [8], but with exponential complexity. Bomboy's algorithm proceeds by determining hypergeometric solutions from the computation of successive eigenrings, so as to derive the shape of the Galois group G little by little, while avoiding Petkovsek's algorithm as much as possible.

In order to help to solve for hypergeometric solutions, note that each non-trivial element U+AL of E(L) yields a right factor of L. Indeed, viewed as an element of EndGV, it necessarily has an eigenvalue l and a corresponding eigenvector v. The right gcd G of U-l and L can be expressed by a Bézout relation and satisfies G· v=0. It is therefore a non-constant right-hand factor of L.

Let x be a hypergeometric solution: there exists aÎC(z) such that s(x)=a· FPSAC/SFCA'94 (Rutgers, 1994), pp. 169--174. -- 1994. Conference proceedings. Available from http://www.fmf.uni-lj.si/~petkovsek/papers.html.

[3]
Barkatou (M. A.). -- Rational solutions of matrix difference equations: Problem of equivalence and factorisation. In Dooley (Sam) (editor), ISSAC'99 (July 29--31, 1999). pp. 277--282. -- ACM Press, 1999. Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation.

[4]
Bomboy (R.). -- Réductibilité des opérateurs aux différences finies : une approche Galois-théorique. -- Research Report n°3735, Institut National de Recherche en Informatique et en Automatique, July 1999.

[5]
Chyzak (Frédéric). -- An extension of Zeilberger's fast algorithm to general holonomic functions. Discrete Mathematics, vol. 217, n°1-3, 2000, pp. 115--134. -- Formal power series and algebraic combinatorics (Vienna, 1997).

[6]
Curtis (Charles W.) and Reiner (Irving). -- Methods of representation theory. Vol. I. -- John Wiley & Sons Inc., New York, 1990, xxiv+819p. With applications to finite groups and orders, Reprint of the 1981 original, A Wiley-Interscience Publication.

[7]
Hendriks (Peter A.) and Singer (Michael F.). -- Solving difference equations in finite terms. Journal of Symbolic Computation, vol. 27, n°3, 1999, pp. 239--259.

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

[9]
Petkovsek (Marko). -- Nested indefinite hypergeometric sums. -- 1992. Unpublished article.

[10]
Petkovsek (Marko) and Salvy (Bruno). -- Finding all hypergeometric solutions of linear differential equations. In Bronstein (Manuel) (editor), ISSAC'93. pp. 27--33. -- ACM Press, New York, 1993. Proceedings of ISSAC'93, Kief, Ukraine.

[11]
Singer (Michael F.). -- Testing reducibility of linear differential operators: a group-theoretic perspective. Applicable Algebra in Engineering, Communication and Computing, vol. 7, n°2, 1996, pp. 77--104.

[12]
van der Put (Marius) and Singer (Michael F.). -- Galois theory of difference equations. -- Springer-Verlag, Berlin, 1997, Lecture Notes in Mathematics, viii+180p.
1
Note that the same idea was used in the context of symbolic summation/integration in Chyzak's work [5].
2
This section is the result of stimulating discussions with Bruno Salvy.
3
seemingly subsumed by [2],
This document was translated from LATEX by HEVEA.