Recurrence sequences. (English) Zbl 1033.11006

Everest, Graham; van der Poorten, Alf; Shparlinski, Igor; Ward, Thomas

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.

Reviewer: Jan-Hendrik Evertse (Leiden)

MSC:

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

Keywords:

recurrence sequences; applications of recurrence sequences; finite automata; cryptography