Cellular Automata and Groups - Errata, Additions, and Updates

T. Ceccherini-Silberstein, M. Coornaert, "Cellular automata and groups", Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010, xix + 439 pp. , ISBN: 978-3-642-14033-4 (print), 978-3-642-14034-1 (electronic).

• page 2, last but one line: replace "$p \colon \Omega \to G$" by "$p \colon \Omega \to A$".
• page 29, in Exercise 1.1: "… each pair of nonempty open subsets …" instead of "… each pair of nonempty subsets …".
• page 32, in Exercise 1.27: replace "A subshift $X \subset A^G$ is said to be irreducible if for any finite subset $\Omega$ of $G$ and any two elements $x_1, x_2 \in X$, there exist a configuration $x \in X$ and an element $g \in G$ such that $x \vert_\Omega = x_1 \vert_\Omega$ and $(gx) \vert_\Omega = x_2\vert_\Omega$. Suppose that $X \subset A^G$ is a subshift. Show that the action of $G$ on $X$ induced by the $G$-shift is topologically transitive if and only if $X$ is irreducible." by " A subshift $X \subset A^G$ is said to be topologically transitive if the shift action of $G$ on $X$ is topologically transitive. Show that a subshift $X \subset A^G$ is topologically transitive if and only if it satisfies the following condition: for any finite subset $\Omega$ of $G$ and any two configurations $x_1, x_2 \in X$, there exist a configuration $x \in X$ and an element $g \in G$ such that $x \vert_\Omega = x_1 \vert_\Omega$ and $(g x) \vert_\Omega = x_2\vert_\Omega$."
• page 33, in Exercise 1.28: replace two times "irreducible" by "topologically transitive".
• page 33, in Exercise 1.30: replace "irreducible" by "topologically transitive" and, in the hint, replace "Exercise 1.3" by "Exercise 1.27".
• page 33, in Exercise 1.31: replace "irreducible" by "topologically transitive".
• page 34, in Exercise 1.34: replace question (b) by
  "(b) Show that $X$ is topologically transitive (resp. topologically mixing, resp. strongly irreducible) if and only if $X^{[F]}$ is topologically transitive (resp. topologically mixing, resp. strongly irreducible)."
• page 35, in Exercise 1.37: replace question (b) by "(b) Show that $X$ is topologically transitive if and only the following holds: for all words $u$ and $v$ in $L(X)$, there exists a word $w \in L(X)$ such that both $u$ and $v$ are subwords of $w$."
• page 36, in Exercise 1.40: replace "irreducible" by "topologically transitive".
• page 36, Exercise 1.45 becomes:
  "Let $G$ be a group and let $A$ be a finite set. Let $\tau \colon A^G \to A^G$ be a cellular automaton and let $X \subset A^G$ be a topologically transitive (resp. topologically mixing, resp. strongly irreducible) subshift. Show that $\tau(X)$ is a topologically transitive (resp. topologically mixing, resp. strongly irreducible) subshift of $A^G$."
• page 40, in the proof of Proposition 2.2.2: replace "$\phi' = \pi \circ \phi$" by "$\phi' = \phi \circ \pi$".
• page 54, in Exercise 2.14: replace "non-Hopfian" by "Hopfian".
• page 77, line 5: replace the sentence "It is closed under the operations of taking subgroups, taking quotients, taking extensions, and taking inductive limits (Sect. 4.5)." by the sentence "It is closed under the operations of taking subgroups, taking quotients, taking extensions, taking direct sums, and taking inductive limits (Sect. 4.5)."
• page 87, in Example 4.5.3.(b): replace "The group $\rm{SL}(n,\mathbb{Z})$ is not amenable for $n \geq 2$. Indeed, as we have seen in Lemma 2.3.2, the subgroup of $\rm{SL}(2,\mathbb{Z})$ generated by the matrices" by " The group $\rm{SL}_2(\mathbb{Z})$ is not amenable. Indeed, as we have seen in Lemma 2.3.2, the subgroup of $\rm{SL}_2(\mathbb{Z})$ generated by the matrices".
• page 89: replace the last sentence by "In the next proposition, we show that the class of amenable groups is closed under taking extensions."
• page 93, in Example 4.6.2.(d): replace " The group $D^1(\rm{Aff}(\mathbb{K}))$ is the group of translations $x \mapsto x + b$, $b \in \mathbb{K}$." by "In the case when $\mathbb{K}$ has two elements, i.e., $\mathbb{K} = \{0,1\}$, then $\rm{Aff}(\mathbb{K})$ is cyclic of order $2$ and therefore abelian. Suppose now that $\mathbb{K}$ has more than two elements. Then the group $D^1(\rm{Aff}(\mathbb{K}))$ is the group of translations $x \mapsto x + b$, $b \in \mathbb{K}$."
• page 107, in Exercise 4.5: replace "a normal subgroup " by "an abelian normal subgroup".
• page 109, line 14, in Exercise 4.23: "… where $ F_n$ consists …" instead of "… where ${\mathcal F}_n$ consists …".
• page 112, line 10: replace "$p \colon \Omega \to G$" by "$p \colon \Omega \to A$".
• page 116, just before Examples 5.4.1: add the following: "Observe that $G \setminus \Omega^{-E} = \{g \in G : gE \not\subset \Omega \} = \{g \in G : gE \cap (G \setminus \Omega) \not= \varnothing \}$, so that $\partial_E(\Omega)$ consists of all $g \in G$ such that the set $g E$ meets both $\Omega$ and $G \setminus \Omega$."
• page 130, line 5: replace "$\tau(z_1)$ and $\tau(z_2)$" by "$\tau(z_1) = \tau(z_2)$".
• page 140, in Exercise 5.4: replace "Let $G = \mathbb{Z}$, $A = \{0,1\}$ and let $\tau \colon A^G \to A^G$ be the majority action" by "Let $G = \mathbb{Z}$, $A = \{0,1\}$, $S = \{-1,0,1\}$ and let $\tau \colon A^G \to A^G$ be the associated majority action".
• page 140, in Exercise 5.7: replace "Let $G$ a group" by "Let $G$ be a group".
• page 141, in Exercise 5.10: replace \[ \sum_{s \in S} y(s) = 4 {\rm \ and \ } y((0,0)) = 1, \] by \[ \sum_{s \in S} y(s) = 4 {\rm \ and \ } y(1_G) = 1, \]
• page 151: a better title for Chapter 6 is "Finitely generated groups".
• page 197, in the proof of Lemma 6.12.3: replace "$I - M^{(2)}_{S \cup \{1_G\}} = (1 - \alpha)(I - M^{(2)}_S)$" by "$I - M^{(2)}_{S \cup \{1_G\}} = \alpha(I - M^{(2)}_S)$".
• page 200, in the proof of Lemma 6.12.8: replace "we have $(A_i \setminus A_ig^{-1}) \cap (A_j \setminus A_jg^{-1}) =\varnothing$" by "we have $(A_i \setminus A_ig^{-1}) \cap (A_jg^{-1} \setminus A_j) = \varnothing$".
• page 202, in the proof of Theorem 6.12.9: replace \[ \begin{split} \|(I- M_S^{(2)})x\|_2 & = \|x - \frac{1}{|S|} \sum_{s \in S} T_s^{(2)} x\|_2\\ & = \frac{1}{|S|} \|\sum_{s \in S}(x - T_s^{(2)} x)\|_2\\ & \leq \frac{1}{|S|} \sum_{s \in S}\|x - T_s^{(2)} x\|_2\\ & = \frac{1}{|S| \cdot \sqrt{|F|}} \sum_{s \in S}\|\chi_{F} - T_s^{(2)} \chi_{F}\|_2\\ \text{(by Lemma 6.12.6(iii))} \ & = \frac{1}{|S| \cdot \sqrt{|F|}} \sum_{s \in S} 2 |F \setminus F s|^{\frac{1}{2}}\\ & = \frac{1}{|S|} \sum_{s \in S} 2 \left(\frac{|F \setminus F s|}{|F|}\right)^{\frac{1}{2}}\\ & = \frac{2}{|F|^{\frac{1}{2}}} \varepsilon^{\frac{1}{2}}\\ & < \varepsilon. \end{split} \] by \[ \begin{split} \|(I- M_S^{(2)})x\|_2 & = \|x - \frac{1}{|S|} \sum_{s \in S} T_s^{(2)} x\|_2\\ & = \frac{1}{|S|} \|\sum_{s \in S}(x - T_s^{(2)} x)\|_2\\ & \leq \frac{1}{|S|} \sum_{s \in S}\|x - T_s^{(2)} x\|_2\\ & = \frac{1}{|S| \cdot \sqrt{|F|}} \sum_{s \in S}\|\chi_{F} - T_s^{(2)} \chi_{F}\|_2\\ \text{(by Lemma 6.12.6(iii))} \ & = \frac{1}{|S| \cdot \sqrt{|F|}} \sum_{s \in S} \left(2|F \setminus F s|\right)^{\frac{1}{2}}\\ & = \frac{1}{|S|} \sum_{s \in S} \left(\frac{2|F \setminus F s|}{|F|}\right)^{\frac{1}{2}}\\ & < \varepsilon. \end{split} \]
• page 202, in the proof of Theorem 6.12.9: replace "Thus, by virtue of the implication (e) $\Rightarrow$ (c) in Proposition 6.12.2" by "Thus, by virtue of the implication (e) $\Rightarrow$ (d) in Proposition 6.12.2".
• page 203, in the proof of Theorem 6.12.9: replace \[ \mu(\Omega_s) < \frac{1}{\vert S \vert} \quad \text{ for all } s \in S, \] by \[ \mu(\Omega_s) \leq \frac{1}{2\vert S \vert} < \frac{1}{\vert S \vert} \quad \text{ for all } s \in S, \]
• page 204, in Definition 6.13.1, Definition 6.13.2, and Example 6.13.3: replace "quasi-isometric embedding" by "uniform embedding".
• page 205, in Remark 6.13.4, Proposition 6.13.5, Proof of Proposition 6.13.5, and Corollary 6.13.6: replace "quasi-isometric embedding" by "uniform embedding".
• page 206, in Proof of Corollary 6.13.6, Proof of Proposition 6.13.7: replace "quasi-isometric embedding" by "uniform embedding".
• page 207, in Proof of Proposition 6.13.8, Proof of Proposition 6.13.11: replace "quasi-isometric embedding" by "uniform embedding".
• page 207: suppress "In the two following propositions we characterize quasi-isometric embeddings and quasi-isometries for finitely generated groups in terms of the word metrics associated with finite symmetric generating subsets of the groups.".
• page 207: Proposition 6.13.12 must be suppressed.
• page 209, in Proposition 6.13.13: replace "isometric embedding" by "uniform embedding".
• page 209: Proposition 6.13.14 must be suppresssed.
• page 222, in Exercise 6.18.(g): replace "$\Phi_n(i_1,i_2,\ldots,i_n) = i_1 + 2i_2 + 4i_3 + \cdots + 2^{n-1}i_n$" by "$\Phi_n(i_1,i_2,\ldots,i_n) = i_n + 2i_{n-1} + 4i_{n-2} + \cdots + 2^{n-1}i_1$".
• page 222, in Exercise 6.19: replace "$\Psi_3 \colon G \to \rm{Sym}(8)$" by "$\Psi_3 \colon G \to \rm{Sym}(\Sigma^3)$".
• page 223, Exercise 6.22.(d) in the Hint: replace "$f_{\lambda_1} \sim f_{\lambda_2}$" by "$\varphi_{\lambda_1} \sim \varphi_{\lambda_2}$".
• page 232, in Exercise 6.58.(c): replace $\tau(X) \subset X$ by $\sigma(X) \subset X$.
• page 277, line 6: "… is injective by (7.44) …".
• page 278, in Exercise 7.4: replace "into the class of finite cyclic groups" by "into the class of finite abelian groups".
• page 280, in Exercise 7.15.(c): replace \[ d_F(\alpha,\beta) = \frac{1}{\vert F \vert}{\rm Tr}(\lambda(\alpha^{-1}\beta)) \] by \[ d_F(\alpha,\beta) = 1 - \frac{1}{\vert F \vert}{\rm Tr}(\lambda(\alpha^{-1}\beta)). \]
• page 295, in Proposition 8.5.1.(ii): replace "$\alpha(g)(v) = \tau_\alpha(c_v)(g)$ for all $v \in V$ and $g \in G$;" by "$\alpha(g)(v) = \tau_\alpha(c_v)(g^{-1})$ for all $v \in V$ and $g \in G$;"
• page 303, line 7 must start with a lower-case letter: "since $u$ …" instead of "Since $u$ …"
• page 310: Proposition 8.9.5 is, as stated and proved, correct. However, we later need, in Lemma 8.9.10, a slightly stronger version of it, namely the following. "Let $X$ be a vector subspace of $V^G$. Suppose that there exist finite subsets $E$ and $E'$ of $G$ and an $(E,E')$-tiling $T \subset G$ such that $\pi_{gE} \subsetneqq V^{gE}$ for all $g \in T$. Then one has $\text{mdim}_{{\mathcal F}}(X) < \dim(V)$.'' Then the proof goes as follows: " For each $j \in J$, let us define, as in Proposition 5.6.4, the subset $T_j \subset T$ by $T_j = T \cap F_j^{-E} = \{g \in T: gE \subset F_j\}$ and set \[ F_j^* = F_j \setminus \coprod_{g \in T_j} gE. \] We thus have… " and the proof continues verbatim as in page 311 from line 6, namely, with equation (8.20).
• page 318, line 16: Replace "Consider the linear map $\nu \colon V^T \to V$ defined by $\nu(z) = \widetilde{\tau}^{-1}(\widetilde{z})(1_G)$, where $\widetilde{z} \in V^G$ is any configuration extending the pattern $z \in V^T$." by "Let $Y' \subset V^T$ be a supplementary vector space of $Y_T$ in $V^T$, so that $V^T = Y_T \oplus Y'$, and denote by $\pi \colon V^T \to Y_T$ the corresponding linear projection. Consider the linear map $\nu \colon V^T \to V$ defined by $\nu(z) = \widetilde{\tau}^{-1}(\widetilde{z})(1_G)$, where $\widetilde{z} \in Y$ is any configuration extending the pattern $\pi(z) \in Y_T$, for all $z \in V^T$."
• page 335, last line: "In the same way as for entropy…" instead of "As for entropy…".
• page 336, lines 1-2: One can replace the limsup in (8.18) by lim provided one assumes that $X$ is $G$-invariant.
• page 353, the last two lines should be: "Note that this condition is equivalent to the fact that $(f \times f)^{-1}(W)$ is an entourage of $X$ for each entourage $W$ of $Y$.".
• page 417: Problem (OP-9) has been answered positively by Laurent Bartholdi and Dawid Kielak in [BK].
• page 418: Problems (OP-13) and (OP-14) have been answered positively by Laurent Bartholdi in [Bar2].
• page 418, mispelling in (Op-15) and (OP-16): "Kaplansky".
• page 418, comment (OP-1), line 6: misspelling in "Grigorchuk".
• page 419, line 3: replace "(OP-6)" by "(OP-7)".
• page 421: replace "[Bar]" by "[Bar1]".
• page 421, additional reference:
  [Bar2] Bartholdi, L.: Cellular automata, duality and sofic groups, New York J. Math. 23 (2017), 1417–1425.
• page 421, additional reference:
  [BK] Bartholdi L., Kielak D.: Amenability of groups is characterized by Myhill's Theorem, J. Eur. Math. Soc., 21 (2019), no. 10, 3191-3197.
• page 422, reference update:
  [CeC9] Ceccherini-Silberstein, T., Coornaert, M.: On a characterization of locally finite groups in terms of linear cellular automata, J. Cell. Autom. 6 (2011), no. 2-3, 207-213.
• page 422, reference update:
  [CeC10] Ceccherini-Silberstein, T., Coornaert, M.: Expansive actions on uniform spaces and surjunctive maps, Bull. Math. Sci. 1 (2011), no. 1, 79-98.
• page 422, reference update:
  [CeC11] Ceccherini-Silberstein, T., Coornaert, M.: On the reversibility and the closed image property of linear cellular automata, Theoret. Comput. Sci. 412 (2011), no. 4-5, 300-306.
• page 423, reference update:
  [Cor] Cornulier, Y.: A sofic group away from amenable groups, Math. Ann. 350 (2011), no. 2, 269-275.
• page 425, misspelling in [KLM]:
  "Kropholler".
• page 427, reference update:
  [PeK] Pestov, V.G., Kwiatkowska, A.: An introduction to hyperlinear and sofic groups, in Appalachian set theory 2006--2012, vol. 406 of London Math. Soc. Lecture Note Ser., pp. 145-185, Cambridge Univ. Press, Cambridge (2013).

Last Update: October 8, 2024