1.1. MAIN DEFINITIONS AND PRINCIPAL PROPERTIE S

3

relation, and it has the same initial values as does a. A minor modification of this

remark yields the identity

n

a(x 4- h) = 2_, a{h + i)^i{x), h,x£7j±.

i=l

1.1.5. Linear recurrence sequences of finite length. For a field F and

constants m, n, 0 2ra n + 1, Elkies [340] studies the subset Hm of F n + 1 of

sequences (x(0),... , x(n)) satisfying some linear recurrence of degree m. Results on

the geometry of the set i7

m

are found, particularly for F of positive characteristic.

1.1.6. Generalized power sums. A generalized power sum is a finite expo-

nential sum

m

(1.2) a(x) = Y^ Ai{x)*h xeZ+

2 = 1

with polynomial coefficients A{. Write degAi = n2; — 1 and set Y^iLi ni = n- The

ai (presumed distinct) are the characteristic roots of the sum a(x), the positive

integers ni are their multiplicities, and the Ai are the coefficients.

To understand the connection between generalized power sums and linear re-

currence sequences, define an operator E on sequences by (E(a)) (x) = a(x + 1),

so that (writing informally) (E — a)(x

n - 1

a

x

) =

A(xn"1)ax,

where the difference

operator A is defined by (A(a)) (x) = a(x + 1) - a(x). Since A n (x n _ 1 ) = 0 and E

is linear, the sum (1.2) is annihilated by the operator

m

]J(E - ca)^ =En- SlEn~l sn^E - sn .

i=l

That is, the sequence a satisfies the recurrence relation (1.1). Notice that the

characteristic roots o^ and that the coefficients Ai are elements of some extension

ring of the coefficient ring 1Z. In particular, the sequence of traces of powers of

algebraic numbers a, with # £ IK, where [K : Q] = d,

a(h) = TK/Q($ah), /iGZ+,

is a linear recurrence sequence satisfying a recurrence relation over Q of order at

most d, and with characteristic polynomial the minimal polynomial of a over Q.

This simple observation is used below in a variety of contexts.

Conversely, assume first that the characteristic polynomial of the recurrence

relation (1.1) has no repeated roots. Then every linear recurrence sequence satis-

fying (1.1) is a generalized power sum with constant coefficients. If / has repeated

roots the matter is a bit more complicated in characteristic p j^ 0: A recurrence

relation with characteristic roots of multiplicity exceeding p cannot have its general

solution given by a generalized power sum. However, apart from this subtlety —

and in any case for linear recurrence sequences defined over fields of characteristic

zero — we shall see below that linear recurrence sequences are given by generalized

power sums.

Assume that the coefficient ring 1Z is a field F, and let L denote the splitting

field of the minimal polynomial / over F. Over L the polynomial factorizes as

m

f(X) = l[(X-air;

1=1