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.

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 |