Eigenring and Reducibility of Difference Equations
Raphaël Bomboy
Café Project, INRIA SophiaAntipolis
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)=
f^{m}(
y)+
a_{m1}f^{m1}(
y)+...+
a_{0} y=0,
(1)
where the a_{i}'s are in k and
L=f^{m}+a_{m1}f^{m1}+...+a_{0} 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
noncommutative ring P_{k}(f). Equation (1)
can be transformed into the system f(Y)=A_{L} Y, where f is
applied componentwise to the vector Y and
A_{L}= 
æ ç ç ç ç ç è 
0 
1 
0 
... 
0 
0 
0 
1 
... 
0 
· · · 
· · · 
· · · 
· · · 
· · · 
a_{0} 
a_{1} 
... 
... 
(a_{m}1) 

ö ÷ ÷ ÷ ÷ ÷ ø 

.

One sees that y is a solution of L(y)=0 if and only if
(y,f(y),...,f^{m1}(y))^{T} is a solution of
f(Y)=A_{L} Y.
More generally, we will consider systems of difference equations
of the form
for an element A of GL_{n}(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=(u_{i,j})ÎGL_{n}(R) such that f(U)=AU
where f maps componentwise to matrices. A difference ring
extension R of k is called a PicardVessiot extension
of k for Equation (2) if R is a simple
difference ring (the only finvariants ideals are (0) and R)
and R=k[u_{1,1},...,u_{n,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,
PicardVessiot 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 R^{n} is an ndimensional 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
GL_{n}(k) and let V_{A} and V_{B} be the corresponding solution
spaces in PicardVessiot extensions R_{A} and R_{B}. Both systems
are equivalent if there is a matrix TÎGL_{n}(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 R_{A} and
R_{B}, and V_{A} and V_{B} 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 (a_{n})_{nÎ}_{N} and (b_{n})_{nÎ}_{N}
of C^{N} (where CÌC is a ring). We define the following
equivalence relation: (x_{n})º(y_{n}) if and only if (x_{n}) and
(y_{n}) only differ by a finite number of terms. We now consider the
quotient ring S=(C^{N}/º) 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 (s_{n})_{nÎ}_{N} such that s_{n}=F(n) for
sufficiently large n.
Definition 2
The shift s of S maps
n((x_{0},...,x_{n},...)) to
n((x_{1},...,x_{n+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
PicardVessiot 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 PicardVessiot 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
PicardVessiot 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Î P_{k}(f) with PicardVessiot
extension R. The following statements are equivalent:

L is reducible (i.e., L=L_{1} L_{2} in P_{k}(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)=A_{L} 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Î P_{k}(f) is completely reducible if there exist L_{1},
..., L_{k} such that L=lclm(L_{1},...,L_{k}),
Beware that an irreducible operator L is completely reducible
because L=lclm(L).
Property 2 [[3]]
The following statements are equivalent:

L is completely reducible;
 the solution space V is expressible as a direct sum
V=V_{1}Å...Å V_{k} where V_{i} is a stable Gmodule 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
irreducible Gmodule.
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
Galoistheoretic 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 x^{1}, ..., x^{l} of C^{N}
is the sequence (x_{0}^{1},x_{0}^{2},...,x_{0}^{l},x_{1}^{1},...). 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:

constants belong to L, where it is understood that
gÎ C(k) is identified to the germ
(g,g,...)Î S;
 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 x^{1}=...=x^{l1}=0
and x^{l}=x) belongs to L.
Example 2
Elements of k are hypergeometric, thus belong to L; on the other
hand, the germs (2^{n})_{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=1}^{n} 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 Galoistheoretic
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 PicardVessiot
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
s^{m}(Z)=P_{s}^{m}Z where
P_{s}^{m}=s^{m1}(A)... A. Let t be the
automorphism of C(z) substituting mz for z. Then
t°s^{m}=s°t; for i from 0 to m1, the
ith msection t°s^{i}(Z) of Z satisfies the equation
s(O)=(P_{s,i}^{m} A)O in the unknown O, where
P_{s,i}^{m} A=t°s^{i}(P_{s}^{m} 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:

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 m1,
the equation s(y)=(P_{s,i}^{m} A_{L})(y) has an
hypergeometric solution;
 there exist m and i, with i£ m, such that the equation
s(y)=(P_{s,i}^{m} A_{L})(y) has an hypergeometric solution.
Corollary 1 [[7]]
Let L be an operator with coefficients in k. One can find
operators H_{1}, ..., H_{t}, R with coefficients in k such that

L=RH_{t}... H_{1};
 the solution space of each H_{i} is spanned by interlacings of
hypergeometric sequences;
 any Liouvillian solution of L(y)=0 is a solution of H_{t}...
H_{1}(y)=0.
4 Eigenrings and their Structure
We consider the noncommutative ring A= P_{k}(s) and a
difference operator LÎ A with PicardVessiot 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
group G=Gal(R/k);
 Amodule 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).
Gendomorphisms of the solution space V
For PÎ A, consider the mapping h_{P} of R into R defined by
h_{P}(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 h_{P} induces a linear
map of End_{G}V, 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·h_{P}(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, h_{P} induces a
Gendomorphism of V.
Alinear endomorphisms of A/AL
Consider the C(k)algebra End_{A}(A/AL) of Alinear endomorphisms
of A/AL, and l an element of this algebra. Recall that the
module A/AL can be viewed as the Amodule 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 welldefined as an Alinear 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), End_{G}V, and End_{A}(A/AL) are isomorphic.
The classical representation theory for semisimple
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:

the eigenring E(L);
 the endomorphism algebra End_{G}V;
 the set of matrices PÎ M_{n}(k) satisfying
A_{L}P=s(P)A_{L}.
Proposition 3 [[4]]
Let L be a completely reducible operator with solution space V.
Then V is isomorphic to a direct sum V_{1}^{n}_{1}Å...Å
V_{l}^{n}_{l} where no V_{i} and V_{j} are isomorphic for i¹ j; the
eigenring E(L) is isomorphic to the direct sum
Å_{i=1}^{l}M_{n}_{i}(C(k)).
Corollary 2 [[4]]
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.
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 firstorder
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
nontrivial element U+AL of E(L) yields a right factor of L.
Indeed, viewed as an element of End_{G}V, it necessarily has an
eigenvalue l and a corresponding eigenvector v. The right
gcd G of Ul and L can be expressed by a Bézout relation
and satisfies G· v=0. It is therefore a nonconstant righthand
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. 169174. 
1994. Conference proceedings. Available from
http://www.fmf.unilj.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
2931, 1999). pp. 277282. 
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 Galoisthé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°13,
2000, pp. 115134. 
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 WileyInterscience 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. 239259.
[8]
Petkovsek (Marko). 
Hypergeometric solutions of linear recurrences with polynomial
coefficients. Journal of Symbolic Computation, vol. 14, n°23,
1992, pp. 243264.
[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. 2733. 
ACM Press, New York, 1993. Proceedings of ISSAC'93,
Kief, Ukraine.
[11]
Singer (Michael F.). 
Testing reducibility of linear differential operators: a
grouptheoretic perspective. Applicable Algebra in Engineering,
Communication and Computing, vol. 7, n°2, 1996,
pp. 77104.
[12]
van der Put (Marius) and Singer (Michael F.). 
Galois theory of difference equations. 
SpringerVerlag, 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 L^{A}T_{E}X by
H^{E}V^{E}A.