Errata for "Groups and monoids of cellular automata"

The version of Theorem 20 in reference [FF96] says closed subgroup, in the periodic point topology, which is presumably a serious restriction, and which I missed due to misunderstanding the construction.

This means Corollary 2 does not work, and really I do not know if one can state anything of this form. This invalidates much of what is said about coded systems in the paper.

Theorem 16 is, I think, true, but in the reference the group is generated by powers of 5/2, not 2/5.

Other statements are correct to the best of my knowledge.


Here is a simple example of a subshift with dense periodic points, where the shift group is not closed. Consider the periodic points \( x_p = (10^{p-1}20^{p-1})^{\mathbb{Z}} \) where \(p\) ranges over the odd primes. Then the orbit closure of these points contains also the orbits \(...0000...\), \(...0001000...\) and \(...0002000...\). The shift generates a copy of \(\mathbb{Z}\), but this subgroup is not closed, as the symbol permutation \(\pi = (0)(1 \; 2)\) is in its closure: For any \(p_1, \ldots, p_n\), by the general Chinese remainder theorem there exists \(k\) such that \(k \equiv p_i \bmod 2p_i\) for all \(1 \leq i \leq n\) if and only if \( p_i \equiv p_j \bmod \mathrm{gcd}(2p_i, 2p_j) = 2 \) for all \(1 \leq i < j \leq n\), and thus \(\sigma^k(x_{p_i}) = \pi(x_{p_i})\) for all \(1 \leq i \leq n\). For the necessary and sufficient condition of CRT see [Ore, O. (1952). The General Chinese Remainder Theorem. The American Mathematical Monthly, 59(6), 365-370. doi:10.2307/2306804].

As another example, consider the points \(y_p = (10^{p-1})^{\mathbb{Z}}\) instead. With the same idea, we see that in fact any finite number of these orbits can be permuted arbitrarily so in fact the closure of the shift is the whole automorphism group, which is isomorphic to \({\mathbb{Z}} \times \bigoplus_p {\mathbb{Z}}/p{\mathbb{Z}}\).

I prove Conjecture 1 and Conjecture 2 in "A note on subgroups of automorphism groups of full shifts".

Last update: 26.4.2018