Tullio CeccheriniSilberstein
Michel Coornaert
Cellular Automata and Groups  Errata, Additions, and Updates
T. CeccheriniSilberstein, M. Coornaert,
"Cellular
automata and groups", Springer Monographs in Mathematics,
SpringerVerlag, Berlin, 2010, xix + 439 pp. , ISBN:
9783642140334 (print), 9783642140341 (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 "nonHopfian" 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 lowercase 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 12:
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 (OP9) has been answered positively by Laurent Bartholdi and David Kielak in [BK].
 page 418:
Problem (OP14) 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] CeccheriniSilberstein, T., Coornaert, M.:
On a characterization of locally finite groups in terms of linear cellular
automata,
J. Cell. Autom. 6 (2011), no. 23, 207213.

page 422, reference update:
[CeC10] CeccheriniSilberstein, T., Coornaert, M.: Expansive
actions on uniform spaces and surjunctive maps,
Bull. Math. Sci. 1 (2011), no. 1, 7998.

page 422, reference update:
[CeC11]
CeccheriniSilberstein, T., Coornaert, M.: On
the reversibility and the closed image property of linear cellular
automata,
Theoret. Comput. Sci. 412 (2011), no. 45, 300306.

page 423, reference update:
[Cor]
Cornulier, Y.:
A sofic group away from amenable groups,
Math. Ann. 350 (2011), no. 2, 269275.

page 425, misspelling in [KLM],
"Kropholler".
Many thanks to Philip Dowerk, Yonatan Gutman, Xuan Kien Phung, Paul Schupp,
Zoran Šunić for corrections and comments.
If you have any additional corrections or comments,
please send them to us by email.
Last Update: November 1st, 2019