Notes on "Surjective Two-Neighbor Cellular Automata on Prime Alphabets"
A simpler proof that such CA are always permutive
Reading Hedlund after writing the paper, I realized that there is an easier (completely trivial) way to extract the result about permutivitity from Hedlund's 1969 paper; at the time of writing we seem to have missed Section 17. Here's a proof. Theorems below refer to that paper.
- To any function \(F : S^n \to S\) on any alphabet \(S\) and \(n \in \mathbb{N}\), we associate integers \(L(F)\), \(M(F)\), \(R(F)\) in some way (\(L\) and \(R\) are Welch numbers).
- By Theorem 14.9, we always have \( L(F)M(F)R(F) = S^{n-1} \) if the cellular automaton with local rule \(F\) is surjective
- Thus if \(n = 2\) and \(|S|\) is prime and \(F\) defines a surjective CA, either \(L(F) = 1\) or \(R(F) = 1\) (or both).
- By Theorem 17.1, if \(L(F) = 1\), then \(F\) is permutive in the first coordinate. A symmetric claim holds for \(R(F)\) and the last coordinate.
- Thus if \(n = 2\) and \(|S|\) is prime and \(F\) defines a surjective CA, \(F\) has a permutive coordinate.
Solutions to open cases and an open question
In the paper, doing manual constructions we found the binary case difficult. But computers are way smarter than us, and indeed there exist non-closing surjective binary CA with radius 5:
- Soon after presenting the paper, Enrico Formenti mentioned that they had found such examples by non-exhaustive search.
- In January 2016, we did some exhaustive searches with Jarkko Kari, and in particular listed the binary
We only list CA that fix \(1^{\mathbb{Z}}\), and the other half is obtained by composing with a flip. I think images of nbhds are listed in ascending order of numerical value, except R6 was accidentally reversed in the course of optimization.
- Emmanuel Jeandel has independently listed all (non-permutive) binary surjective CA of nbhd size 6, subsuming our work. There are apparently around 70 million surjective non-permutive CA among the \(2^{2^6} \approx 1.8 \cdot 10^{19}\) nbhd 6 CA. We haven't cross-checked our lists with his.
- Is it possible to list reversible nbhd size 7 CA exhaustively?
Last update: 8.9.2017