The University of East Anglia

Notation

vii

Introduction

ix

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

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

111

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.3: 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

Sequences from the on-line Encyclopedia

255

Bibliography

257

Index

309