This unique book provides a self-contained exposition of the theory of cellular automata on groups and explores its deep connections with recent developments in geometric and combinatorial group theory, amenability, symbolic dynamics, the algebraic theory of group rings, and other branches of mathematics and theoretical computer science. The topics treated include the Garden of Eden theorem for amenable groups, the Gromov–Weiss surjunctivity theorem, and the solution of the Kaplansky conjecture on the stable finiteness of group rings for sofic groups.
Entirely self-contained and now in its second edition, the volume includes 10 appendices and more than 600 exercises, the solutions of which are presented in the companion book Exercises in Cellular Automata and Groups (2023) by the same authors. It will appeal to a large audience, including specialists and newcomers to the field.
Author(s): Tullio Ceccherini-Silberstein , Michel Coornaert
Series: Springer Monographs in Mathematics
Edition: 2
Publisher: Springer Nature Switzerland
Year: 2024
Language: English
Pages: 556
City: Cham
Tags: Cellular Automata, Symbolic Dynamics, Group Theory, Garden of Eden Theorem
Preface to the Second Edition
Preface
Contents
Notation
1 Cellular Automata
1.1 The Configuration Set and the Shift Action
1.2 The Prodiscrete Topology
1.3 Periodic Configurations
1.4 Cellular Automata
1.5 Minimal Memory
1.6 Cellular Automata over Quotient Groups
1.7 Induction and Restriction of Cellular Automata
1.8 Cellular Automata with Finite Alphabets
1.9 The Prodiscrete Uniform Structure
1.10 Invertible Cellular Automata
Notes
Exercises
Untitled
2 Residually Finite Groups
2.1 Definition and First Examples
2.2 Stability Properties of Residually Finite Groups
2.3 Residual Finiteness of Free Groups
2.4 Hopfian Groups
2.5 Automorphism Groups of Residually Finite Groups
2.6 Examples of Finitely Generated Groups Which Are Not Residually Finite
2.7 Dynamical Characterization of Residual Finiteness
Notes
Exercises
3 Surjunctive Groups
3.1 Definition
3.2 Stability Properties of Surjunctive Groups
3.3 Surjunctivity of Locally Residually Finite Groups
3.4 Marked Groups
3.5 Expansive Actions on Uniform Spaces
3.6 Gromov's Injectivity Lemma
3.7 Closedness of Marked Surjunctive Groups
Notes
Exercises
4 Amenable Groups
4.1 Measures and Means
4.2 Properties of the Set of Means
4.3 Measures and Means on Groups
4.4 Definition of Amenability
4.5 Stability Properties of Amenable Groups
4.6 Solvable Groups
4.7 The Følner Conditions
4.8 Paradoxical Decompositions
4.9 The Theorems of Tarski and Følner
4.10 The Fixed Point Property
Notes
Exercises
5 The Garden of Eden Theorem
5.1 Garden of Eden Configurations and Garden of Eden Patterns
5.2 Pre-injective Maps
5.3 Statement of the Garden of Eden Theorem
5.4 Interiors, Closures, and Boundaries
5.5 Mutually Erasable Patterns
5.6 Tilings
5.7 Entropy
5.8 Proof of the Garden of Eden Theorem
5.9 Surjunctivity of Locally Residually Amenable Groups
5.10 A Surjective but Not Pre-injective Cellular Automaton over F2
5.11 A Pre-injective but Not Surjective Cellular Automaton over F2
5.12 A Characterization of Amenability in Terms of Cellular Automata
5.13 Garden of Eden Patterns for Life
Notes
Exercises
6 Finitely Generated Groups
6.1 The Word Metric
6.2 Labeled Graphs
6.3 Cayley Graphs
6.4 Growth Functions and Growth Types
6.5 The Growth Rate
6.6 Growth of Subgroups and Quotients
6.7 A Finitely Generated Metabelian Group with Exponential Growth
6.8 Growth of Finitely Generated Nilpotent Groups
6.9 The Grigorchuk Group and Its Growth
6.10 The Følner Condition for Finitely Generated Groups
6.11 Amenability of Groups of Subexponential Growth
6.12 The Theorems of Kesten and Day
6.13 Uniform Embeddings and Quasi-Isometries
6.14 Quasi-Isometric Embeddings
Notes
Exercises
7 Local Embeddability and Sofic Groups
7.1 Local Embeddability
7.2 Local Embeddability and Ultraproducts
7.3 LEF-Groups and LEA-Groups
7.4 The Hamming Metric
7.5 Sofic Groups
7.6 Sofic Groups and Metric Ultraproducts of Finite Symmetric Groups
7.7 A Characterization of Finitely Generated Sofic Groups
7.8 Surjunctivity of Sofic Groups
Notes
Exercises
8 Linear Cellular Automata
8.1 The Algebra of Linear Cellular Automata
8.2 Configurations with Finite Support
8.3 Restriction and Induction of Linear Cellular Automata
8.4 Group Rings and Group Algebras
8.5 Group Ring Representation of Linear Cellular Automata
8.6 Modules Over a Group Ring
8.7 Matrix Representation of Linear Cellular Automata
8.8 The Closed Image Property
8.9 The Garden of Eden Theorem for Linear Cellular Automata
8.10 Pre-injective But Not Surjective Linear Cellular Automata
8.11 Surjective But Not Pre-injective Linear Cellular Automata
8.12 Invertible Linear Cellular Automata
8.13 Pre-injectivity and Surjectivity of the Discrete Laplacian
8.14 Linear Surjunctivity
8.15 Stable Finiteness of Group Algebras
8.16 Zero-Divisors in Group Algebras and Pre-injectivity of One-Dimensional Linear Cellular Automata
8.17 A Characterization of Amenability in Terms of Linear Cellular Automata
Notes
Exercises
A Nets and the Tychonoff Product Theorem
A.1 Directed Sets
A.2 Nets in Topological Spaces
A.3 Initial Topology
A.4 Product Topology
A.5 The Tychonoff Product Theorem
Notes
B Uniform Structures
B.1 Uniform Spaces
B.2 Uniformly Continuous Maps
B.3 Product of Uniform Spaces
B.4 The Hausdorff-Bourbaki Uniform Structure on Subsets
Notes
C Symmetric Groups
C.1 The Symmetric Group
C.2 Permutations with Finite Support
C.3 Conjugacy Classes in Sym0(X)
C.4 The Alternating Group
D Free Groups
D.1 Concatenation of Words
D.2 Definition and Construction of Free Groups
D.3 Reduced Forms
D.4 Presentations of Groups
D.5 The Klein Ping-Pong Theorem
E Inductive Limits and Projective Limits of Groups
E.1 Inductive Limits of Groups
E.2 Projective Limits of Groups
F The Banach-Alaoglu Theorem
F.1 Topological Vector Spaces
F.2 The Weak-* Topology
F.3 The Banach-Alaoglu Theorem
G The Markov-Kakutani Fixed Point Theorem
G.1 Statement of the Theorem
G.2 Proof of the Theorem
Notes
H The Hall Harem Theorem
H.1 Bipartite Graphs
H.2 Matchings
H.3 The Hall Marriage Theorem
H.4 The Hall Harem Theorem
Notes
I Complements of Functional Analysis
I.1 The Baire Theorem
I.2 The Open Mapping Theorem
I.3 Spectra of Linear Maps
I.4 Uniform Convexity
J Ultrafilters
J.1 Filters and Ultrafilters
J.2 Limits Along Filters
Notes
Open Problems
Comments
References
List of Symbols
Index
