Eigenring and Reducibility of Difference Equations
Café Project, INRIA Sophia-Antipolis
March 6, 2000
[summary by Frédéric Chyzak and Pierre
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).
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  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 .
We review in Section 1 the basic notions of Galois
theory for difference equations, following the presentation
of . 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
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
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
More generally, we will consider systems of difference equations
of the form
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 []
If the set of constants C(k) is algebraically closed,
Picard--Vessiot extensions R of k exist and are unique up to
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
We conclude this section with an illustration on the ring S of
germs of sequences over C.
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.
The shift s of S maps
From now on, the ring C is an algebraically closed subfield of C
Property 1 []
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.
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
The following theorem gives a criterion of reducibility for operators.
Theorem 2 []
Consider an operator LÎ Pk(f) with Picard--Vessiot
extension R. The following statements are equivalent:
We also consider the class of completely reducible
L is reducible (i.e., L=L1 L2 in Pk(f));
- the solution space V has a strict subspace W that is stable
under the action of the Galois group G=Gal(R/k);
- the system f(X)=AL X is equivalent to a system with
block upper triangular companion matrix.
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
Property 2 []
The following statements are equivalent:
L is completely reducible;
- 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;
- the system f(X)=AX is equivalent to a system with
block diagonal companion matrix where each block corresponds to an
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.
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.
Hypergeometric sequences are germs xÎ S such that
s(x)=ax for some aÎ k.
The set L of
Liouvillian sequences is the smallest
subring of S such that:
constants belong to L, where it is understood that
gÎ C(k) is identified to the germ
- if x is hypergeometric, x belongs to L;
- if x is solution of s(x)=x+a with aÎ L,
then x belongs to L;
- 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.
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
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.
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 []
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
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 []
Let L be an operator of order n over k.
The following statements are equivalent:
there is a Liouvillian solution for the equation L(y)=0;
- 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;
- there exists an m such that, for all i between 0 and m-1,
the equation s(y)=(Ps,im AL)(y) has an
- there exist m and i, with i£ m, such that the equation
s(y)=(Ps,im AL)(y) has an hypergeometric solution.
Corollary 1 []
Let L be an operator with coefficients in k. One can find
operators H1, ..., Ht, R with coefficients in k such that
- the solution space of each Hi is spanned by interlacings of
- any Liouvillian solution of L(y)=0 is a solution of Ht...
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:
eigenrings, that are rings that essentially contain operators
that follow some special commutation relation with L;
- endomorphisms of V that commute with the Galois
- 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
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
With a closer look on the bijections above, one gets the following result.
The three rings E(L), EndGV, and EndA(A/AL) are isomorphic.
The classical representation theory for semi-simple
modules  applies to the study of the structure of
eigenrings, yielding the following proposition and corollary.
Proposition 2 []
For an operator L with Galois group G and space of solutions V,
there are ring isomorphisms between:
the eigenring E(L);
- the endomorphism algebra EndGV;
- the set of matrices PÎ Mn(k) satisfying
Proposition 3 []
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
Corollary 2 []
Let L be a difference operator with eigenring E(L). Then:
L is irreducible implies that E(L) is isomorphic to C(k);
- L is completely reducible and E(L) is isomorphic to C(k)
imply that L is irreducible.
An algorithm to compute the eigenring of a differential operator was
given by Singer . 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
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 , 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