and a has characteristic roots
OJI,.. .
, am with multiplicities n i , . . . , n
tively. There are constants Aij G L, j = 0,... , n^ 1 and i = 1,... ,772, such
m rii 1 / 1 ' _ A
(1.3) a(x) = ^ ^ ^ r + ^ Maf, xGN .
If F has characteristic zero then (1.3) can be rewritten in the form
(1.4) a(x) = Y^Mx)*?, xeN,
with polynomials A{(X) G L[X] of degrees deg Ai n; 1, z = 1,... , m. Moreover,
if the characteristic p of the field is at least max{ni,... , nm} then (1.4) holds in any
event; in particular we obtain an exponential polynomial if the minimal polynomial
/ is square-free, so that the Ai all are constant, or if the characteristic p is at least
as great as the order n.
If / is the characteristic polynomial of a, then each polynomial Ai has degree
precisely rii 1, i = 1,... , m.
1.1.7. Groups of recurrence sequences. Again we restrict attention to
the case of no repeated roots; thus / is a monic square-free polynomial over a
field F of characteristic zero. Here it is convenient to consider two-sided sequences.
Several authors have considered the following group structure defined on £(/) , more
precisely on equivalence classes of sequences. Two sequences a and b from £(/ ) are
equivalent if for some A G F* and £ G Z, \a(x + £) = b(x) for all x G Z. That is, two
sequences are equivalent if they differ by a shift and multiplication by a non-zero
constant. Let G(f) denote the set of equivalence classes.
A group structure on G(f) may be defined as follows. In place of the repre-
sentation (1.4), consider the (n x n) Vandermonde matrix W (a} - 1 ). _,• Write
A for its determinant, and Aj for the determinant of the matrix obtained from W
by replacing its j-th column with (0,... ,0, l)
. Then for every sequence a G £(/ )
there is a unique representation
1 n
(1.5) a(x) = - ^ A
a f .
2 = 1
Write a - [ai,... , an] in this case, and define the product of two sequences a -
[ai,... , an] and b -+ [61,... , bn] to be the sequence c ^ [aibi,... , anbn]. Define
the product of two classes to be the product of their representatives; this product
is well-defined by [61, Lemma 5.3.2] and makes G(f) an abelian group. Ballot [61]
provides a detailed analysis and gives applications of the group structure to the
study of divisors of linear recurrence sequences. For more background on these
groups in the binary case, see [689], [690]. For / having exactly one double root,
Ballot [62] gives a meaningful generalization of the group G(f)-
1.1.8. Dominating roots. For sequences over normed fields and in par-
ticular over C it is convenient to order the characteristic roots as
| « l | •• \dm\-
The r roots of maximum norm
ai | = = \ar\ |a
r +
i | |a
Previous Page Next Page