Topological and Ergodic Theory of Symbolic Dynamics

Symbolic dynamics is essential in the study of dynamical systems of various types and is connected to many other fields such as stochastic processes, ergodic theory, representation of numbers, information and coding, etc. This graduate text introduces symbolic dynamics from a perspective of topological dynamical systems and presents a vast variety of important examples. After introducing symbolic and topological dynamics, the core of the book consists of discussions of various subshifts of positive entropy, of zero entropy, other non-shift minimal action on the Cantor set, and a study of the ergodic properties of these systems. The author presents recent developments such as spacing shifts, square-free shifts, density shifts, $\mathcal{B}$-free shifts, Bratteli-Vershik systems, enumeration scales, amorphic complexity, and a modern and complete treatment of kneading theory. Later, he provides an overview of automata and linguistic complexity (Chomsky's hierarchy). The necessary background for the book varies, but for most of it a solid knowledge of real analysis and linear algebra and first courses in probability and measure theory, metric spaces, number theory, topology, and set theory suffice. Most of the exercises have solutions in the back of the book. Cover 1 Title page 4 Contents 6 Preface 10 Chapter 1. First Examples and General Properties of Subshifts 20 1.1. Symbol Sequences and Subshifts 20 1.2. Word-Complexity 24 1.3. Transitive and Synchronized Subshifts 28 1.4. Sliding Block Codes 29 1.5. Word-Frequencies and Shift-Invariant Measures 31 1.6. Symbolic Itineraries 33 Chapter 2. Topological Dynamics 38 2.1. Basic Notions from Dynamical Systems 38 2.2. Transitive and Minimal Systems 42 2.3. Equicontinuous and Distal Systems 47 2.4. Topological Entropy 55 2.5. Mathematical Chaos 59 2.6. Transitivity and Topological Mixing 63 2.7. Shadowing and Specification 66 Chapter 3. Subshifts of Positive Entropy 70 3.1. Subshifts of Finite Type 70 3.2. Sofic Shifts 80 3.3. Coded Subshifts 84 3.4. Hereditary and Density Shifts 90 3.5. β-Shifts and β-Expansions 96 3.6. Unimodal Subshifts 107 3.7. Gap Shifts 136 3.8. Spacing Shifts 139 3.9. Power-Free Shifts 141 3.10. Dyck Shifts 147 Chapter 4. Subshifts of Zero Entropy 152 4.1. Linear Recurrence 152 4.2. Substitution Shifts 154 4.3. Sturmian Subshifts 181 4.4. Interval Exchange Transformations 199 4.5. Toeplitz Shifts 204 4.6. \cB-Free Shifts 214 4.7. Unimodal Restrictions to Critical Omega-Limit Sets 222 Chapter 5. Further Minimal Cantor Systems 236 5.1. Kakutani-Rokhlin Partitions 236 5.2. Cutting and Stacking 239 5.3. Enumeration Systems 244 5.4. Bratteli Diagrams and Vershik Maps 252 Chapter 6. Methods from Ergodic Theory 276 6.1. Ergodicity 278 6.2. Birkhoff’s Ergodic Theorem 279 6.3. Unique Ergodicity 281 6.4. Measure-Theoretic Entropy 301 6.5. Isomorphic Systems 303 6.6. Measures of Maximal Entropy 306 6.7. Mixing 314 6.8. Spectral Properties 328 6.9. Eigenvalues of Bratteli-Vershik Systems 344 Chapter 7. Automata and Linguistic Complexity 360 7.1. Automata 360 7.2. The Chomsky Hierarchy 364 7.3. Automatic Sequences and Cobham’s Theorems 376 Chapter 8. Miscellaneous Background Topics 386 8.1. Pisot and Salem Numbers 386 8.2. Continued Fractions 395 8.3. Uniformly Distributed Sequences 404 8.4. Diophantine Approximation 410 8.5. Density and Banach Density 414 8.6. The Perron-Frobenius Theorem 417 8.7. Countable Graphs and Matrices 420 Appendix. Solutions to Exercises 432 Bibliography 442 Index 470 Back Cover 481 "Symbolic dynamics is essential in the study of dynamical systems of various types and is connected to many other fields such as stochastic processes, ergodic theory, representation of numbers, information and coding, etc. This graduate text introduces symbolic dynamics from a perspective of topological dynamical systems and presents a vast variety of important examples. After introducing symbolic and topological dynamics, the core of the book consists of discussions of various subshifts of positive entropy, of zero entropy, other non-shift minimal action on the Cantor set, and a study of the ergodic properties of these systems. The author presents recent developments such as spacing shifts, square-free shifts, density shifts, B-free shifts, Bratteli-Vershik systems, enumeration scales, amorphic complexity, and a modern and complete treatment of kneading theory. Later, he provides an overview of automata and linguistic complexity (Chomsky's hierarchy). The necessary background for the book varies, but for most of it a solid knowledge of real analysis and linear algebra and first courses in probability and measure theory, metric spaces, number theory, topology, and set theory suffice. Most of the exercises have solutions in the back of the book."-- Provided by publisher