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.