1.1. MAIN DEFINITIONS AND PRINCIPAL PROPERTIE S

5

are called dominating roots.

A sequence with a unique dominating root is often relatively easy to deal with.

Thus, many results below are stated for such sequences only. Boyd [143] demon-

strates that a unique dominating root is present for a wide class of irreducible

characteristic polynomials.

1.1.9. Nondegeneracy. The linear recurrence sequence (1.1) is degenerate if

it has a pair of distinct roots whose ratio is a root of unity. Conversely, if af ^ ex*,

1 2 j f rri, x = 1, 2 . . . , it is non-degenerate. Over infinite fields this definition

determines an important class of sequences. Furthermore, the study of arbitrary

linear recurrence sequences can effectively be reduced to that of non-degenerate

linear recurrence sequences in the following sense.

THEOREM 1.2. Let a denote a linear recurrence sequence of order n over an

algebraic number field K of degree d over Q. Then there is a constant

MM \ J

e x p (2™(31°g™)1/2)

»/d = 1, and

such that for some M M(d, n) each subsequence (a(Mx + £)) is either identically

zero, or is non-degenerate.

This theorem is essentially a combination of results of [87] (for d = 1) and

of [1083] (for d 2). The proof is based on a bound for the least common multiple

of periods of roots of unity in K (the period of a root of unity p is the least £ £ N

with pl = 1). See [1365] for some improvements and algorithmic applications of

those results. Schmidt [1149] provides an upper bound on the number of such

arithmetic progressions which depends only on n.

1.1.10. Arithmetic sub-progressions. The following useful observation is

related to the previous result. The Skolem-Mahler-Lech Theorem, of which more

below, is a particularly important application.

THEOREM 1.3. Any subsequence (a(kx + t)), k e N, £ G Z+ of a linear re-

currence sequence a of order n is a linear recurrence sequence of order at most

n.

This statement is clear for a generalized power sum of the form (1.2); a linear

recurrence sequence of order n is a generalized power sum of order n over any

commutative ring [1012], [1295]. The converse of Theorem 1.3 does not hold in

such generality but is true in characteristic zero. In that case it is a non-trivial

result that an arithmetic progression (more precisely, a finite number of interwoven

arithmetic progressions) is essentially the only subsequence of indices upon which

a non-degenerate linear recurrence sequence is again a linear recurrence sequence.

THEOREM

1.4. Let a denote a non-degenerate linear recurrence sequence over

a field of characteristic zero, and let (xh) denote an arbitrary sequence of distinct

natural numbers. If (a(xh)) is a linear recurrence sequence then there is an integer

d 1 and certain remainders r$ £ {0,1,... , d— 1} so that with at most finitely many

exceptions the sequence (xh) is the monotonically increasing sequence of integers of

the shape dx + r^.

This deep theorem follows from the work on sums of 5-units; see Sections 1.5

and 2.1.