Recurrence sequences. (English) Zbl 1033.11006

Mathematical Surveys and Monographs 104. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3387-1/hbk). xiii, 318 p. (2003).
This monograph gives a very broad and up to date encyclopaedic overview of both the theory and applications of recurrence sequences. The authors consider mainly sequences over the rationals and over the ring of residue classes modulo an integer. The emphasis is on linear recurrence sequences, but also much attention has been paid to other types of recurrence sequences, for instance sequences generated by finite automata. The book contains an enormous amount of facts and results of which clearly not all proofs have been included. The authors have followed the policy to give proofs or sketches of proofs of the prototypical results, providing convenient references for the proofs that have not been included. At the end of the book, there is a bibliography with 1382 items.
We give a short overview of the topics that have been treated: techniques from \(p\)-adic analysis and Diophantine approximation; zeros and growth properties of linear recurrence sequences over the integers; periodicity properties of recurrence sequences over residue class rings and Artin’s conjecture; operations on power series and linear recurrence sequences; character sum estimates and bounds on the number of zeros of recurrence sequences over residue class rings; arithmetic properies of recurrence sequences (e.g., occurrence of prime divisors or powers in the terms of a recurrence sequence); distribution of recurrence sequences in finite fields and residue class rings; uniform distribution properties of real recurrence sequences; elliptic divisibility sequences; sequences arising in graph theory and dynamics; connections with algebraic number theory (e.g., the construction of normal bases and results on Gaussian periods); pseudo-random number generators; connections to computer science (e.g., sequences generated by finite automata), coding theory and cryptography.


11B37 Recurrences
11-02 Research exposition (monographs, survey articles) pertaining to number theory
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
11G05 Elliptic curves over global fields
11T23 Exponential sums
33B10 Exponential and trigonometric functions
11J71 Distribution modulo one
11K45 Pseudo-random numbers; Monte Carlo methods
11B85 Automata sequences
37B15 Dynamical aspects of cellular automata
94A60 Cryptography