relation, and it has the same initial values as does a. A minor modification of this
remark yields the identity
a(x 4- h) = 2_, a{h + i)^i{x), h,x£7j±.
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
are found, particularly for F of positive characteristic.
1.1.6. Generalized power sums. A generalized power sum is a finite expo-
nential sum
(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
) =
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
]J(E - ca)^ =En- SlEn~l sn^E - sn .
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
f(X) = l[(X-air;
Previous Page Next Page