4

1. DEFINITIONS AND TECHNIQUES

and a has characteristic roots

OJI,.. .

, am with multiplicities n i , . . . , n

m

respec-

tively. There are constants Aij G L, j = 0,... , n^ — 1 and i = 1,... ,772, such

that

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

m

(1.4) a(x) = Y^Mx)*?, xeN,

i=l

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)

t

. Then for every sequence a G £(/ )

there is a unique representation

1 n

(1.5) a(x) = - ^ A

i

a

i

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

m

|,