Diagonal Bases and Diagonal Periods of Elementary Cellular Automata
In the authors' words
Which cellular-automaton diagonal families form bases in every finite window? For canonical polynomial lifts of elementary rules, two truth-table bits determine triangularity, and units on the matrix diagonal determine invertibility. Exactly 24 rules give universal binary bases; all remain universal over every modulus. Among triangular binary coordinate maps, the Pascal transform is uniquely characterized by converting OR convolution into pointwise multiplication, while increment becomes strict prefix summation. Explicit inverses and coordinate comparisons distinguish sparsity from evaluation cost. A Rule 30 polynomial construction gives Fibonacci bounds on interpolation order and prime-modulus periods. Exact additive periods anchor a finite census modulo two and three. These results separate all-window basis classification from optimization of a representation and from period patterns observed in finite windows.
Appeared: Wednesday, September 23. arXiv. Preprint with a published version.
Published version: 10.5281/zenodo.22747701
Authors' comment: 44 pages, 9 figures