Certified Digit Automata for Nonlinear Two-Dimensional Cellular Automata: Kernel-Checked Proofs of OEIS Counting Conjectures in Lean 4
Many entries of the On-Line Encyclopedia of Integer Sequences (OEIS) count the ON cells of two-dimensional outer-totalistic cellular automata with the von Neumann neighborhood, started from one ON cell and sampled at stages 2^n − 1. Their closed forms, and claims that other rules give the same counts, were found by fitting computed terms and were unproved. This paper proves them in the Lean 4 proof assistant. For each rule, a finite automaton reading the binary digits of the space and time coordinates is guessed from simulation. Two Boolean certificates, checked by the Lean kernel, show that it reproduces the evolution. A general theorem, proved once, turns them into a statement about every cell of the plane at every stage. A third certificate gives the closed form through a linear recurrence. Applied to 50 OEIS entries, the method proves all 50 closed forms, shows that 122 further rules have the same counts, and settles nine relations between entries and a parity relation among three rules. It also identifies errors in seven entries. For Rule 750 (A169707), whose space-time diagram appears not to be automatic, the count at stages 2^n − 1 stated by Sloane is proved by a direct induction in Lean. All results build with Lean 4.35.0 and Mathlib on one shared set of definitions and use only the standard axioms. The Lean sources are at https://github.com/OtherMindset/congress-lean (directory lake/). The work was carried out by AI agents under the author’s direction; the paper describes this use of AI tools.
Authors
- Alexander Ross Cohen (ORCID: https://orcid.org/0009-0006-2755-8313)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-20
- DOI
- https://doi.org/10.5281/zenodo.24384894
- Primary Topic
- Cellular Automata and Applications
- Type
- preprint