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