x INTRODUCTION
an easily available survey in which it can be found is given. For all results, we try
to recall the original version, some essential intermediate improvements, and up
to the authors' limited knowledge the best current form of the result.
Details of the scope of this book are clear from the table of contents. In Chap-
ters 1 to 8, general results concerning linear recurrence sequences are presented.
The topics include various estimates for the number of solutions of equations, in-
equalities and congruences involving linear recurrence sequences. Also, there are
estimates for exponential sums involving linear recurrence sequences as well as
results on the behaviour of arithmetic functions on values of linear recurrence se-
quences. In Chapters 9 to 14, a selection of applications are given, together with
a study of some special sequences. In some cases, applications require only the
straightforward use of results from the earlier chapters. In other cases the tech-
nique, or even just the spirit, of the results are used. It seems almost magical that,
in many applications, linear recurrence sequences show up from several quite unre-
lated directions. A chapter on elliptic divisibility sequences is included to point out
the beginning of an area of development analogous to linear recurrence sequences,
but with interesting geometric and Diophantine methods coming to the fore. A
chapter is also included to highlight an emerging overlap between combinatorial
dynamics and the theory of linear recurrence sequences.
Although objects are considered over different rings, the emphasis is on the
conventional case of the integers. A linear recurrence sequence over the integers
can often be considered as the trace of an exponential function over an algebraic
number field. The coordinates of matrix exponential functions satisfy linear recur-
rence relations. Such examples suggest that a single exponential only seems to be
less general than a linear recurrence sequence. Of course that is not quite true, but
in many important cases links between linear recurrence sequences and exponen-
tial functions in algebraic extensions really do play a crucial role. Michalev and
Nechaev [827] give a survey of possible extensions of the theory of linear recurrence
sequences to a wide class of rings and modules.
For previously known results, complete proofs are generally not given unless
they are very short or illuminating. The underlying ideas and connections with
other results are discussed briefly. Filling the gaps in these arguments may be
considered a useful (substantial) exercise. Several of the results are new; for these
complete proofs are given.
Some number-theoretic and algebraic background is assumed. In the text, we
try to motivate the use of deeper results. A brief survey of the background material
follows. First, some basic results from the theory of finite fields and from algebraic
number theory will be used. These can be found in [725] and [909], respectively.
Also standard results on the distribution of prime numbers, in particular the Prime
Number Theorem n(x) ~ x/lnx, will be used. All such results can easily be found
in [1049], and in many other textbooks. Much stronger results are known, though
these subtleties will not matter here. The following well-known consequences of the
Prime Number Theorem,
k (f(k) kj Log log /c, v(k) C Log kj Log log k
and
P{k) i/(fc) Log i/(fc), Q(k) exp ((1 + o(l))i/(fc))
will also be needed.
Previous Page Next Page