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
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.
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.
Previous Page Next Page