Introduction

The importance of recurrence sequences hardly needs to be explained. Their

study is plainly of intrinsic interest and has been a central part of number theory

for many years. Moreover, these sequences appear almost everywhere in mathe-

matics and computer science. For example, the theory of power series representing

rational functions [1026], pseudo-random number generators ([935], [936], [938],

[1277]), fc-regular [76] and automatic sequences [736], and cellular automata [780].

Sequences of solutions of classes of interesting Diophantine equations form linear

recurrence sequences — see [1175], [1181], [1285], [1286]. A great variety of power

series, for example zeta-functions of algebraic varieties over finite fields [725], dy-

namical zeta functions of many dynamical systems [135], [537], [776], generating

functions coming from group theory [1110], [1111], Hilbert series in commutative

algebra [788], Poincare series [131], [287], [1110] and the like — are all known

to be rational in many interesting cases. The coefficients of the series representing

such functions are linear recurrence sequences, so many powerful results from the

present study may be applied. Linear recurrence sequences even participated in

the proof of Hilbert's Tenth Problem over Z ([786], [1319], [1320]). In the pro-

ceedings [289], the problem is resolved for many other rings. The article [998] by

Pheidas suggests using the arithmetic of bilinear recurrence sequences to settle the

still open rational case.

Recurrence sequences also appear in many parts of the mathematical sciences in

the wide sense (which includes applied mathematics and applied computer science).

For example, many systems of orthogonal polynomials, including the Tchebychev

polynomials and their finite field analogues, the Dickson polynomials, satisfy recur-

rence relations. Linear recurrence sequences are also of importance in approxima-

tion theory and cryptography and they have arisen in computer graphics [799] and

time series analysis [136].

We survey a selection of number-theoretic properties of linear recurrence se-

quences together with their direct generalizations. These include non-linear re-

currence sequences and exponential polynomials. Applications are described to

motivate the material and to show how some of the problems arise. In many sec-

tions we concentrate on particular properties of linear recurrence sequences which

are important for a variety of applications. Where we are able, we try to consider

properties that are particularly instructive in suggesting directions for future study.

Several surveys of properties of linear recurrence sequences have been given

recently; see, for example, [215], [725, Chap. 8], [822], [827], [899], [914], [1026],

[1181], [1202], [1248], [1285], [1286]. However, they do not cover as wide a range

of important features and applications as we attempt here. We have relied on these

surveys a great deal, and with them in mind, try to use the 'covering radius 1'

principle: For every result not proved here, either a direct reference or a pointer to

ix