A counting formula for linear self-orthogonal cellular automata
Abstract
A bipermutive local rule of diameter d over 𝔽₂ generates, through its no-boundary cellular automaton, a Latin square of order 2ᵈ⁻¹; Mariot and Mazzone call the automaton self-orthogonal when that square is orthogonal to its transpose. They determined the number LIN(d) of linear self-orthogonal cellular automata for 3 ≤ d ≤ 16, observed that the values follow 2ᵈ⁻³ until they stop doing so at d=7, reported that the sequence is not indexed in the OEIS, and asked for a counting formula. We give one. We show that LIN(d) is the number of invertible circulant matrices of order d-1 over 𝔽₂ with zero diagonal, and that LIN(d) = (1)/(2)(Psi(d-1)+μ(Xᵈ⁻¹-1)), where Psi(n) is the number of invertible circulants of order n over 𝔽₂ (OEIS A003473) and μ is the Möbius function of 𝔽₂[X], so that μ(Xⁿ-1) is 0 for even n and (-1)^(r(n)) for odd n, with r(n) the number of distinct irreducible factors of Xⁿ-1. Both halves of the identity are proved, together with the classical product formula for Psi. The closed form reproduces all fourteen published values and extends them to d=30; it also settles the shape of the data exactly, in that LIN(d)=2ᵈ⁻³ holds precisely when d-1 is a power of two or an odd prime having 2 as a primitive root, the first failure being d=7. All statements below are machine-checked in Lean 4, with one explicitly labelled exception.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
b9103da99329483c2c1cd9a215c52b5ae4fe96b657ea5acf09a16e09e703e025
Claim ledger
Stated results
soca-01known2026-08-23
Lemma 1 of the source: the Cayley table of a bipermutive CA is a Latin square, for every diameter
soca-02known2026-08-23
soCheck decides Definition 6, and a self-orthogonal square's main diagonal is a transversal
soca-03known data2026-08-23
Table 1 of arXiv:2504.09173: #BCA = 4, 16, 256, 65536 and #SOCA = 2, 4, 8, 16 at d = 3..6
soca-04known data2026-08-23
Every self-orthogonal CA of diameter at most 6 is affine (the source's #SOCA = #LIN), and the linear-only counts 1, 2, 4, 8
soca-05known data2026-08-23
d = 7: exactly 24 affine and 12 linear self-orthogonal CA, the twelve listed by polynomial, and the 2ᵈ⁻³ pattern broken
soca-06routine2026-08-23
Negative controls: bipermutivity is necessary at d = 3, Latin does not imply self-orthogonal, and the counts are sharp
soca-07known2026-08-23
The source's Figure 3 and Figure 4 reproduced: rule 150's Latin square and rule 90's symmetry
soca-08candidate2026-08-23
d = 7: #SOCA(7) = 24, and NO nonlinear self-orthogonal CA of diameter 7 exists
This ledger entry is reported in prose and is not bound to a Lean theorem.soca-09candidate2026-08-23
d = 7: 105 056 rules induce an invertible PBCA of length 6, of which 105 032 are nonlinear
This ledger entry is reported in prose and is not bound to a Lean theorem.soca-10known2026-08-23
The source's Corollary 1 as a criterion on the associated polynomial, and the shape of p_f
soca-11candidate2026-08-23
Half of A003473: at every odd diameter, #LIN(d) = Ψ(d-1)/2 (the kernel-clean content is the HALVING 2·linCount = unitCount; Ψ's value is classical, native_decide'd in a separate model, unbridged — review 2026-08-23)
soca-12known2026-08-23
The source's Lemma 6 for every t: #LIN(2ᵗ+1) = 2^(2ᵗ-2)
soca-13candidate2026-08-23
The counting formula: #LIN(d) = (A003473(d-1) + μ(Xᵈ⁻¹−1))/2, reproducing the source's whole Table 2 and extending it to d = 30
soca-14candidate2026-08-23
The source's "powers of 2" guess holds exactly at powers of two and Artin primes
soca-15routine2026-08-23
Negative controls for the criterion and the count
soca-16routine2026-08-23
The counting formula is now a theorem at every diameter: the odd half 2·A(n) = Ψ(n) + (−1)ʳ, and both halves in one statement
soca-17known2026-08-23
Xⁿ − 1 is squarefree over 𝔽₂ exactly for odd n, and its factorization interface
soca-18routine2026-08-23
Negative controls for the odd half, and a concrete value in the polynomial model
soca-19routine2026-08-23
Ψ(n), the number of units of 𝔽₂[X]/(Xⁿ−1), as a product over the irreducible factors — the classical value, formalized, so the counting formula produces numbers
soca-20known data2026-08-23
Concrete values in the polynomial model: Ψ(2), Ψ(3), Ψ(7), r(3), r(7), and the source's Table 2 at d = 3, 4, 8 — all without native_decide
soca-21routine2026-08-23
Negative controls for the product formula: every hypothesis refuted by an explicit counterexample, and the coprime/non-coprime contrast
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- The second closing open problem of *Self-Orthogonal Cellular Automata*, Luca Mariot and Federico Mazzone, arXiv:2504.09173 (AUTOMATA 2025; Springer chapter 10.1007/978-3-032-01570-9₁3; only a v1 exists, 2025-04-12), §5, verbatim:
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7