Cellular Automata and Groups

In this chapter we introduce the notion of a cellular automaton. We fix a group and an arbitrary set which will be called the alphabet. A configuration is defined as being a map from the group into the alphabet. Thus, a configuration is a way of attaching an element of the alphabet to each element of the group. There is a natural action of the group on the set of configurations which is called the shift action (see Sect. 1.1). A cellular automaton is a self-mapping of the set of configurations defined from a system of local rules commuting with the shift (see Definition 1.4.1). We equip the configuration set with the prodiscrete topology, that is, the topology of pointwise convergence associated with the discrete topology on the alphabet (see Sect. 1.2). It turns out that every cellular automaton is continuous with respect to the prodiscrete topology (Proposition 1.4.8) and commutes with the shift (Proposition 1.4.4). Conversely, when the alphabet is finite, every continuous self-mapping of the configuration space which commutes with the shift is a cellular automaton (Theorem 1.8.1). Another important fact in the finite alphabet case is that every bijective cellular automaton is invertible, in the sense that its inverse map is also a cellular automaton (Theorem 1.10.2). We give examples showing that, when the alphabet is infinite, a continuous self-mapping of the configuration space which commutes with the shift may fail to be a cellular automaton and a bijective cellular automaton may fail to be invertible. In Sect. 1.9, we introduce the prodiscrete uniform structure on the configuration space. We show that a self-mapping of the configuration space is a cellular automaton if and only if it is uniformly continuous and commutes with the shift (Theorem 1.9.1).

This chapter is devoted to the study of residually finite groups, which form a class of groups of special importance in several branches of mathematics. As their name suggests it, residually finite groups generalize finite groups. They are defined as being the groups whose elements can be distinguished after taking finite quotients (see Sect. 2.1). There are many other equivalent definitions. For example, a group is residually finite if and only if it can be embedded into the direct product of a family of finite groups (Corollary 2.2.6). The class of residually finite groups is closed under taking subgroups and taking projective limits. It contains in particular all finite groups, all finitely generated abelian groups, and all free groups (Theorem 2.3.1). Every finitely generated residually finite group is Hopfian (Theorem 2.4.3) and the automorphism group of a finitely generated residually finite group is itself residually finite (Theorem 2.5.1). Examples of finitely generated groups which are not residually finite are presented in Sect. 2.6. The following dynamical characterization of residually finite groups is given in Sect. 2.7: a group is residually finite if and only if there is a Hausdorff topological space on which the group acts continuously and faithfully with a dense subset of points with finite orbit.

Surjunctive groups are defined in Sect. 3.1 as being the groups on which all injective cellular automata with finite alphabet are surjective. In Sect. 3.2 it is shown that every subgroup of a surjunctive group is a surjunctive group and that every locally surjunctive group is surjunctive. Every locally residually finite group is surjunctive (Corollary 3.3.6). The class of locally residually finite groups is quite large and includes in particular all finite groups, all abelian groups, and all free groups (a still wider class of surjunctive groups, namely the class of sofic groups, will be described in Chap. 7). In Sect. 3.4, given an arbitrary group Γ, we introduce a natural topology on the set of its quotient groups. In Sect. 3.7, it is shown that the set of surjunctive quotients is closed in the space of all quotients of Γ.

This chapter is devoted to the class of amenable groups. This is a class of groups which plays an important role in many areas of mathematics such as ergodic theory, harmonic analysis, representation theory, dynamical systems, geometric group theory, probability theory and statistics. As residually finite groups, amenable groups generalize finite groups but there are residually finite groups which are not amenable and there are amenable groups which are not residually finite. An amenable group is a group whose subsets admit an invariant finitely additive probability measure (see Sect. 4.4). The class of amenable groups contains in particular all finite groups, all abelian groups and, more generally, all solvable groups (Theorem 4.6.3). It is closed under the operations of taking subgroups, taking quotients, taking extensions, and taking inductive limits (Sect. 4.5). The notion of a Følner net, roughly speaking, a net of almost invariant finite subsets of a group, is introduced in Sect. 4.7. Paradoxical decompositions are defined in Sect. 4.8. The Følner-Tarski theorem (Theorem 4.9.1) asserts that amenability, existence of a Følner net, and non-existence of a paradoxical decomposition are three equivalent conditions for groups. Another characterization of amenable groups is given in Sect. 4.10: a group is amenable if and only if every continuous affine action of the group on a nonempty compact convex subset of a Hausdorff topological vector space admits a fixed point (Corollary 4.10.2).

The Garden of Eden Theorem gives a necessary and sufficient condition for the surjectivity of a cellular automaton with finite alphabet over an amenable group. It states that such an automaton is surjective if and only if it is pre-injective. As the name suggests it, pre-injectivity is a weaker notion than injectivity. It means that any two configurations which have the same image under the automaton must be equal if they coincide outside a finite subset of the underlying group (see Sect. 5.2). We shall establish the Garden of Eden theorem in Sect. 5.8 by showing that both the surjectivity and the pre-injectivity are equivalent to the maximality of the entropy of the image of the cellular automaton. The entropy of a set of configurations with respect to a Følner net of an amenable group is defined in Sect. 5.7. Another important tool in the proof of the Garden of Eden theorem is a notion of tiling for groups introduced in Sect. 5.6. The Garden of Eden theorem is used in Sect. 5.9 to prove that every residually amenable (and hence every amenable) group is surjunctive. In Sect. 5.10 and Sect. 5.11, we give simple examples showing that both implications in the Garden of Eden theorem become false over a free group of rank two. In Sect. 5.12 it is shown that a group G is amenable if and only if every surjective cellular automaton with finite alphabet over G is pre-injective. This last result gives a characterization of amenability in terms of cellular automata.

This chapter is devoted to the growth and amenability of finitely generated groups. The choice of a finite symmetric generating subset for a finitely generated group defines a word metric on the group and a labelled graph, which is called a Cayley graph. The associated growth function counts the number of group elements in a ball of radius n with respect to the word metric. We define a notion of equivalence for such growth functions and observe that the growth functions associated with different finite symmetric generating subsets are in the same equivalence class (Corollary 6.4.5). This equivalence class is called the growth type of the group. The notions of polynomial, subexponential and exponential growth are introduced in Sect. 6.5. In Sect. 6.7 we give an example of a finitely generated metabelian group with exponential growth. We prove that finitely generated nilpotent groups have polynomial growth (Theorem 6.8.1). In Sect. 6.9 we consider the Grigorchuk group. It is shown that it is an infinite periodic (Theorem 6.9.8), residually finite (Corollary 6.9.5) finitely generated group of intermediate growth (Theorem 6.9.17). In the subsequent section, we show that every finitely generated group of subexponential growth is amenable (Theorem 6.11.2). In Sect. 6.12 we prove the Kesten-Day characterization of amenability (Theorem 6.12.9) which asserts that a group with a finite (not necessarily symmetric) generating subset is amenable if and only if 0 is in the ℓ ²-spectrum of the associated Laplacian. Finally, in Sect. 6.13 we consider the notion of quasi-isometry for not necessarily countable groups and we show that amenability is a quasi-isometry invariant (Theorem 6.13.23).

In this chapter we study the notions of local embeddability and soficity for groups. Roughly speaking, a group is locally embeddable into a given class of groups provided that the multiplicative table of any finite subset of the group is the same as the multiplicative table of a subset of some group in the class (cf. Definition 7.1.3). In Sect. 7.1 we discuss several stability properties of local embeddability. Subgroups of locally embeddable groups are locally embeddable (Proposition 7.1.7). Moreover, as the name suggests, local embeddability is a local property, that is, a group is locally embeddable into a class of groups if and only if all its finitely generated subgroups are locally embeddable into the class (Proposition 7.1.8). When the class is closed under finite direct products, the class of groups which are locally embeddable in the class is closed under (possibly infinite) direct products (Proposition 7.1.10). We also show that a marked group which is a limit of groups belonging to a given class is locally embeddable into this class (Theorem 7.1.16). Conversely, we prove that if the given class is closed under taking subgroups and the marking group is free, then any marked group which is locally embeddable is a limit of marked groups which are in the class (Theorem 7.1.19). If \(\mathcal {C}\) is a class of groups which is closed under finite direct products, then every group which is residually \(\mathcal {C}\) is locally embeddable into \(\mathcal {C}\) (Corollary 7.1.14). Conversely, under the hypothesis that \(\mathcal {C}\) is closed under taking subgroups, every finitely presented group which is locally embeddable into \(\mathcal {C}\) is residually  \(\mathcal {C}\) (Corollary 7.1.21).

In Sect. 7.2 we present a characterization of local embeddability in terms of ultraproducts: a group is locally embeddable into \(\mathcal {C}\) if and only if it can be embedded into an ultraproduct of a family of groups in \(\mathcal {C}\) .

Section 7.3 is devoted to LEF and LEA-groups. A group is called LEF (resp. LEA) if it is locally embeddable into the class of finite (resp. amenable) groups. As the class of finite (resp. amenable) groups is closed under taking subgroups and taking finite direct products, all the results obtained in the previous section can be applied. This implies in particular that every locally residually finite (resp. locally residually amenable) group is LEF (resp. LEA). We give an example of a finitely generated amenable group which is LEF but not residually finite (Proposition 7.3.9). This group is not finitely presentable since every finitely presented LEF-group is residually finite.

The Hamming metric, which is a bi-invariant metric on the symmetric group of a finite set, is introduced in Sect. 7.4.

In Sect. 7.5 we define the class of sofic groups. These groups are the groups admitting local approximations by finite symmetric groups equipped with their Hamming metric. Subgroups and direct products of sofic groups are sofic. Every LEA-group is sofic (Corollary 7.5.11). In particular, residually amenable groups, and therefore amenable groups and residually finite groups, are sofic. A group is sofic if and only if it can be embedded into an ultraproduct of a family of finite symmetric groups equipped with their Hamming metrics (Theorem 7.6.6). In Sect. 7.7 we give a characterization of finitely generated sofic groups in terms of their Cayley graphs. More precisely, we show that a finitely generated group G with a finite symmetric generating subset S⊂G is sofic if and only if, for every integer r≥0 and every ε>0, there exists a finite S-labeled graph Q such that there is a proportion of at least 1−ε of vertices q∈Q such that the ball of radius r centered at q in Q is isomorphic, as a labeled graph, to a ball of radius r in the Cayley graph of G associated with S (Theorem 7.7.1). The last section of this chapter is devoted to the proof of the surjunctivity of sofic groups (Theorem 7.8.1).

In this chapter we study linear cellular automata, namely cellular automata whose alphabet is a vector space and which are linear with respect to the induced vector space structure on the set of configurations. If the alphabet vector space and the underlying group are fixed, the set of linear cellular automata is a subalgebra of the endomorphism algebra of the configuration space (Proposition 8.1.4). An important property of linear cellular automata is that the image of a finitely supported configuration by a linear cellular automaton also has finite support (Proposition 8.2.3). Moreover, a linear cellular automaton is entirely determined by its restriction to the space of finitely-supported configurations (Proposition 8.2.4) and it is pre-injective if and only if this restriction is injective (Proposition 8.2.5). The algebra of linear cellular automata is naturally isomorphic to the group algebra of the underlying group with coefficients in the endomorphism algebra of the alphabet vector space (Theorem 8.5.2). Linear cellular automata may be also regarded as endomorphisms of the space of finitely-supported configurations, viewed as a module over the group algebra of the underlying group with coefficients in the ground field (Proposition 8.7.5). This representation of linear cellular automata is always one-to-one and, when the alphabet vector space is finite-dimensional, it is also onto (Theorem 8.7.6). The image of a linear cellular automaton is closed in the space of configurations for the prodiscrete topology, provided that the alphabet is finite dimensional (Theorem 8.8.1). We exhibit an example showing that if one drops the finite dimensionality of the alphabet, then the image of a linear cellular automaton may fail to be closed. In Sect. 8.9 we prove a linear version of the Garden of Eden theorem. For the proof, we introduce the mean dimension of a vector subspace of the configuration space. We show that for a linear cellular automaton with finite-dimensional alphabet, both pre-injectivity and surjectivity are equivalent to the maximality of the mean dimension of the image of the cellular automaton (Theorem 8.9.6). We exhibit two examples of linear cellular automata with finite-dimensional alphabet over the free group of rank two, one which is pre-injective but not surjective, and one which is surjective but not pre-injective. This shows that the linear version of the Garden of Eden theorem fails to hold for groups containing nonabelian free subgroups (see Sects. 8.10 and 8.11). Provided the alphabet is finite dimensional, the inverse of every bijective linear cellular automaton is also a linear cellular automaton (Corollary 8.12.2). In Sect. 8.13 we study the pre-injectivity and surjectivity of the discrete Laplacian over the real numbers and prove a Garden of Eden type theorem (Theorem 8.13.2) for such linear cellular automata with no amenability assumptions on the underlying group. As an application, we deduce a characterization of locally finite groups in terms of real linear cellular automata (Corollary 8.13.4). In Sect. 8.14 we define linear surjunctivity and prove that all sofic groups are linearly surjunctive (Theorem 8.14.4). The notion of stable finiteness for rings is introduced in Sect. 8.15. A stably finite ring is a ring for which one-sided invertible square matrices are also two-sided invertible. It is shown that linear surjunctivity is equivalent to stable finiteness of the associated group algebra (Corollary 8.15.6). As a consequence, we deduce that group algebras of sofic groups are stably finite for any ground field (Corollary 8.15.8). In the last section, we prove that the absence of zero-divisors in the group algebra of an arbitrary group is equivalent to the fact that every non-identically-zero linear cellular automaton with one-dimensional alphabet is pre-injective (Corollary 8.16.12).

We recall that in this book all rings are assumed to be associative (but not necessarily commutative) with a unity element, and that a field is a nonzero commutative ring in which each nonzero element is invertible.

Appendix A gives a quick overview of a few fundamental notions and results of topology (nets, compactness, product topology, and the Tychonoff product theorem).

Appendix B is devoted to André Weil’s theory of uniform spaces. It includes also a detailed exposition of the Hausdorff-Bourbaki uniform structure on subsets of a uniform space.

In Appendix C, we establish some basic properties of symmetric groups and prove the simplicity of the alternating groups.

The definition and the construction of free groups are given in Appendix D. The proof of Klein’s ping-pong lemma is also included there.

In Appendix E we shortly describe the constructions of inductive and projective limits of groups.

Appendix F treats topological vector spaces, the weak-∗ topology, and the Banach-Alaoglu theorem.

The proof of the Markov-Kakutani fixed point theorem is presented in Appendix G.

In Appendix H, of a pure graph-theoretical and combinatorial flavour, we consider bipartite graphs and their matchings. We prove Hall’s marriage theorem and its harem version which plays a key role in the proof of Tarski’s theorem on amenability.

The Baire theorem, the open mapping theorem, as well as other complements of functional analysis including uniform convexity are treated in Appendix I.

The Appendix J deals with the notions of filters and ultrafilters.