Macquarie University ResearchOnline
Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/75128
51 Visitors
55 Hits
0 Downloads
- Title
- Recurrence sequences
- Related
- Mathematical surveys and monographs Vol. 104
- Publisher
- Rhode Island, USA : American Mathematical Society
- Date
- 2003
- FoR/RFCD Code(s)
- 010100 Pure Mathematics
- Author/Creator
- Everest, Graham
- Author/Creator
- van der Poorten, Alf
- Author/Creator
- Shparlinski, Igor
- Author/Creator
- Ward, Thomas
- Description
- Recurrence 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 are described, including combinatorics, dynamical systems and cryptography, and computer science.
- Description
- Machine derived contents note: 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 -- 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 -- Sequences from the on-line Encyclopedia 255 -- Bibliography 257 -- Index 309.
- Subject Keyword
- 010100 Pure Mathematics
- Subject Keyword
- Recurrent sequences (Mathematics)
- Resource Type
- book
- Organisation
- Macquarie University. Dept. of Computing
- Organisation
- Macquarie University. Dept. of Mathematics
- Identifier
- http://hdl.handle.net/1959.14/75128
- Identifier
- ISBN:0821833871
- Identifier
- ISSN:0076-5376
- Identifier
- mq-rm-2003018720
- Language
- eng
Copyright Macquarie University | Privacy Statement | Accessibility Information
ABN 90 952 801 237 | CRICOS Provider No 00002J