Periodic and finite configurations

Definitions and mathematical statement

Let $d\ge2$, let $A$ be a finite alphabet with a distinguished quiescent state $q$, and let $F:A^{\mathbb Z^d}\to A^{\mathbb Z^d}$ be a cellular automaton. Thus $F$ is continuous and commutes with all translations; quiescence means $F(q^{\mathbb Z^d})= q^{\mathbb Z^d}$. Define \[ P=\{x:\text{the translation orbit of }x\text{ is finite}\}, \qquad C=\{x:\#\{v:x_v\ne q\}<\infty\}. \] Translation equivariance gives $F(P)\subset P$, and locality and quiescence give $F(C)\subset C$. Write $F_P:P\to P$ and $F_C:C\to C$ for these restrictions.

Decide each of the following implications for arbitrary such automata: \[ F_P\text{ injective}\ \Longrightarrow\ F_C\text{ surjective}; \qquad F_C\text{ surjective}\ \Longrightarrow\ F_P\text{ surjective}; \] \[ F\text{ surjective}\ \Longrightarrow\ F_P\text{ surjective}. \] The last implication does not need a quiescent state, since it does not involve finite-support configurations.

Spatial periodicity here means periodic in all lattice directions, or equivalently fixed by a finite-index subgroup. Surjectivity of $F_P$ permits a periodic preimage with a larger spatial period than that of the target. Likewise, a finite-support preimage may occupy a larger region than its target. Injectivity and surjectivity refer to these entire sets, not to a single finite box with imposed boundary conditions. Each implication is a separate yes-or-no target.

Short English statement

Determine how injectivity and surjectivity on periodic configurations, finite-support configurations, and the full lattice constrain one another.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 4600046 (AMR-045-0046), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Boyle - Open Problems in Symbolic Dynamics (2008), Problem/Question/Conjecture 25.6. Original source indexed by AMR-045-0046. https://www.math.umd.edu/~mboyle/papers/openfinalsub3nov2007.pdf.