Finite-ring obstructions for quadratic binary radius-two cellular automata
Abstract
We study one-dimensional binary cellular automata with a five-slot radius-two local rule of exact algebraic-normal-form degree two, acting on periodic rings of length n. We prove that every such rule is non-injective whenever 4 | n and n >= 8. The proof begins with the four-cell collapse, where the two extreme formal slots coincide. A structural classification of the resulting four-variable maps separates the 65,472 exactly quadratic rules into 63,456 rules with an immediate ring-four collision and 2,016 exceptional lifts. The latter split into layers of sizes 480 and 1,536. Their remaining finite obligations are represented by 136 parameter-region constructions and 768 per-lift records, respectively. Each certificate supplies differentiating closed walks of lengths 8 and 12 with a common pair-graph base vertex. Concatenation then gives lengths 8a + 12b, which are exactly the multiples of four from eight onward. The load-bearing finite certificate core therefore contains 904 = 136 + 768 independently replayable objects checked by standalone, non-searching programs. The complete checker CLIs additionally reconstruct expected populations and execute coverage, complement, and regression/guard checks; 904 is not a count of total checker operations. Periodic extension also yields full-shift non-injectivity; that consequence is used here only as a corollary.
Related
- Elementary cellular automata: spectral properties of Koopman operator for finite periodic realizations
- Gardens of Eden and amenability on cellular automata
- Quadratic Hubbard trees, automata, and ray connections
- Random Cellular Automata and deBruijn Graphs
- When do lazy and invertible cellular automata generate all cellular automata?
BibTeX
@misc{fu2026finitering,
title = {{Finite-ring obstructions for quadratic binary radius-two cellular automata}},
author = {Houqiao Fu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35921},
eprint = {2609.35921},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35921},
}
RIS
TY - UNPB
TI - Finite-ring obstructions for quadratic binary radius-two cellular automata
AU - Houqiao Fu
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35921
UR - https://arxiv.org/abs/2609.35921
AB - We study one-dimensional binary cellular automata with a five-slot radius-two local rule of exact algebraic-normal-form degree two, acting on periodic rings of length n. We prove that every such rule is non-injective whenever 4 | n and n >= 8. The proof begins with the four-cell collapse, where the two extreme formal slots coincide. A structural classification of the resulting four-variable maps separates the 65,472 exactly quadratic rules into 63,456 rules with an immediate ring-four collision and 2,016 exceptional lifts. The latter split into layers of sizes 480 and 1,536. Their remaining finite obligations are represented by 136 parameter-region constructions and 768 per-lift records, respectively. Each certificate supplies differentiating closed walks of lengths 8 and 12 with a common pair-graph base vertex. Concatenation then gives lengths 8a + 12b, which are exactly the multiples of four from eight onward. The load-bearing finite certificate core therefore contains 904 = 136 + 768 independently replayable objects checked by standalone, non-searching programs. The complete checker CLIs additionally reconstruct expected populations and execute coverage, complement, and regression/guard checks; 904 is not a count of total checker operations. Periodic extension also yields full-shift non-injectivity; that consequence is used here only as a corollary.
ER -