Generation by lazy and invertible cellular automata over the Klein four-group

@misc{alcalaarroyo2026generation,
  title = {{Generation by lazy and invertible cellular automata over the Klein four-group}},
  author = {Edgar Alcalá-Arroyo and Alonso Castillo-Ramirez and Haobo Ma and Wenlin Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20329},
  eprint = {2610.20329},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20329},
}

TY  - UNPB
TI  - Generation by lazy and invertible cellular automata over the Klein four-group
AU  - Edgar Alcalá-Arroyo
AU  - Alonso Castillo-Ramirez
AU  - Haobo Ma
AU  - Wenlin Zhang
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20329
UR  - https://arxiv.org/abs/2610.20329
AB  - Let G=C_2× C_2 and A={0,1}. We characterize the submonoid of CA(G;A) generated by lazy and invertible cellular automata. A cellular automaton belongs to this submonoid if and only if, whenever it maps the two free G-orbits onto the same free orbit, it maps both constant configurations and some two-point orbit to the same constant. The proof gives a factorization using elementary orbit collapses and three two-cell lazy maps. The criterion yields the cardinality 59 712 and identifies the maps missed by a weaker constant-separation invariant. Adjoining one idempotent generates the full monoid, and the generated submonoid is contained in exactly one maximal proper submonoid, of cardinality 65 024. The submonoid generated by lazy maps alone has 4 007 elements, and for both generating sets the maximum shortest-word length is six. The criterion and the cardinalities 59 712 and 4 007 are formally verified in Lean.
ER  -