Tullio Ceccherini-Silberstein
Michel Coornaert

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 "irreducible" by "weakly irreducible".
• page 33, in Exercise 1.28, replace "irreducible" by "weakly irreducible".
• page 33, in Exercise 1.30, replace "irreducible" by "weakly irreducible" and, in the hint, replace "Exercise 1.3" by "Exercise 1.27".
• page 33, Exercise 1.31 becomes: "Let $G$ be a group and let $A$ be a set. 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$, $(gx)\vert_\Omega = x_2\vert_\Omega$, and $\Omega \cap g^{-1}\Omega = \varnothing$. Note that every irreducible subshift $X \subset A^G$ is weakly irreducible.
One says that a subshift $X \subset A^G$ is topologically mixing if the action of $G$ on $X$ induced by the $G$-shift is topologically mixing (cf. Exercise 1.1).
(a) Let $X \subset A^G$ be a subshift. Show that $X$ is topologically mixing if and only if for any finite subset $\Omega$ of $G$ and any two configurations $x_1, x_2 \in X$, there exists a finite subset $F \subset G$ such that, for all $g \in G \setminus F$, there exists a configuration $x \in X$ satisfying $x\vert_\Omega = x_1\vert_\Omega$ and $(gx)\vert_\Omega = x_2\vert_\Omega$.
(b) Show that if $G$ is infinite then every topologically mixing subshift $X \subset A^G$ is irreducible (and therefore weakly irreducible)."
• page 34, in Exercise 1.32, replace "$\Omega_2\delta$" by "$\delta\Omega_2$".
• page 34, in Exercise 1.34, replace question (b) by
"(b) Show that $X$ is weakly irreducible (resp. irreducible, resp. topologically mixing, resp. strongly irreducible) if and only if $X^{[F]}$ is weakly irreducible (resp. irreducible, resp. topologically mixing, resp. strongly irreducible)."
• page 35, in Exercise 1.37, replace question (b) by "(b) Show that $X$ is weakly irreducible if and only if for every pair of words $u$ and $v$ in $L(X)$, there exist words $w,u',v',u'',v'' \in A^*$ such that one of the following conditions is satisfied: (i) $uwv \in L(X)$; (ii) $vwu \in L(X)$; (iii) $u = u'w$, $v= wv'$ and $u'wv' \in L(X)$; or (iv) $v=v''w$, $u=wu''$ and $v''wu'' \in L(X)$.
(b') Show that $X$ is irreducible if and only if for every pair of words $u$ and $v$ in $L(X)$, there exists a word $w \in A^*$ such that $uwv \in L(X)$."
and add the following question: "(e) Let $A = \{0,1\}$ and consider the subshift of finite type $X \subset A^{\mathbb{Z}}$ defined by $X = X_{10} = \{x \in A^{{\mathbb Z}} : (x(n),x(n+1)) \neq (1,0) \text{ for all } n \in {\mathbb Z}\}$. Show that $X$ is weakly irreducible but not irreducible."
• 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 weakly irreducible (resp. irreducible, resp. topologically mixing, resp. strongly irreducible) subshift. Show that $\tau(X)$ is a weakly irreducible (resp. irreducible, resp. topologically mixing, resp. strongly irreducible) subshift of $A^G$.
• page 54, in Exercise 2.14: replace "non-Hopfian" by "Hopfian".
• 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 277, line 6, "… is injective by (7.44) …".
• 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 David Kielak in [BK].
• page 418: Problem (OP-14) has been answered positively by Laurent Bartholdi in [Bar2].
• 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, arXiv:1605.09133, to appear in Journal of the European Mathematical Society.
• 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".
Many thanks to Philip Dowerk, Yonatan Gutman, Xuan Kien Phung, Paul Schupp, Zoran Šunić for corrections and comments.