Recurrence sequences

Includes index

Includes bibliography (p. 257-308) and references.

Chapter 1. Definitions and Techniques 1 1.1. Main Definitions and Principal Properties 1 1.2. p-adic Analysis 12 1.3. Linear Forms in Logarithms 15 1.4. Diophantine Approximation and Roth's Theorem 17 1.5. Sums of S-Units 19 Chapter 2. Zeros, Multiplicity and Growth 25 2.1. The Skolem-Mahler-Lech Theorem 25 2.2. Multiplicity of a Linear Recurrence Sequence 26 2.3. Finding the Zeros of Linear Recurrence Sequences 31 2.4. Growth of Linear Recurrence Sequences 31 2.5. Further Equations in Linear Recurrence Sequences 37 Chapter 3. Periodicity 45 3.1. Periodic Structure 45 3.2. Restricted Periods and Artin's Conjecture 49 3.3. Problems Related to Artin's Conjecture 52 3.4. The Collatz Sequence 61 Chapter 4. Operations on Power Series and Linear Recurrence Sequences 65 4.1. Hadamard Operations and their Inverses 65 4.2. Shrinking Recurrence Sequences 71 4.3. Transcendence Theory and Recurrence Sequences 72 Chapter 5. Character Sums and Solutions of Congruences 75 5.1. Bounds for Character Sums 75 5.2. Bounds for other Character Sums 83 5.3. Character Sums in Characteristic Zero 85 5.4. Bounds for the Number of Solutions of Congruences 86 Chapter 6. Arithmetic Structure of Recurrence Sequences 93 6.1. Prime Values of Linear Recurrence Sequences 93 6.2. Prime Divisors of Recurrence Sequences 95 6.3. Primitive Divisors and the Index of Entry 103 6.4. Arithmetic Functions on Linear Recurrence Sequences 109 6.5. Powers in Recurrence Sequences 113 Chapter 7. Distribution in Finite Fields and Residue Rings 117 7.1. Distribution in Finite Fields 117 7.2. Distribution in Residue Rings 119 Chapter 8. Distribution Modulo 1 and Matrix Exponential Functions 127 8.1. Main Definitions and Metric Results 127 8.2. Explicit Constructions 130 8.3. Other Problems 134 Chapter 9. Applications to Other Sequences 139 9.1. Algebraic and Exponential Polynomials 139 9.2. Linear Recurrence Sequences and Continued Fractions 145 9.3. Combinatorial Sequences 150 9.4. Solutions of Diophantine Equations 157 Chapter 10. Elliptic Divisibility Sequences 163 10.1. Elliptic Divisibility Sequences 163 10.2. Periodicity 164 10.3. Elliptic Curves 165 10.4. Growth Rates 167 10.5. Primes in Elliptic Divisibility Sequences 169 10.6. Open Problems 174 Chapter 11. Sequences Arising in Graph Theory and Dynamics 177 11.1. Perfect Matchings and Recurrence Sequences 177 11.2. Sequences arising in Dynamical Systems 179 Chapter 12. Finite Fields and Algebraic Number Fields 191 12.1. Bases and other Special Elements of Fields 191 12.2. Euclidean Algebraic Number Fields 196 12.3. Cyclotomic Fields and Gaussian Periods 202 12.4. Questions of Kodama and Robinson 205 Chapter 13. Pseudo-Random Number Generators 211 13.1. Uniformly Distributed Pseudo-Random Numbers 211 13.2. Pseudo-Random Number Generators in Cryptography 220 Chapter 14. Computer Science and Coding Theory 231 14.1. Finite Automata and Power Series 231 14.2. Algorithms and Cryptography 241 14.3. Coding Theory 247

Recurrent sequences are of great intrinsic interest and have been a central part of number theory for many years. Moreover, these sequences appear almost everywhere in mathematics and computer science. This book surveys the modern theory of linear recurrence sequences and their generalizations. Particular emphasis is placed on the dramatic impact that sophisticated methods from Diophantine analysis and transcendence theory have had on the subject. Related work on bilinear recurrences and an emerging connection between recurrences and graph theory are covered. Applications and links to other areas of mathematics, including combinatorics, dynamical systems and cryptography, and to computer science are described.