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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Certified Digit Automata for Nonlinear Two-Dimensional Cellular Automata: Kernel-Checked Proofs of OEIS Counting Conjectures in Lean 4

Alexander Ross Cohen
2 links
Zenodo (CERN European Organization for Nuclear Research)
Cellular Automata and Applications
preprint

Certified Digit Automata for Nonlinear Two-Dimensional Cellular Automata: Kernel-Checked Proofs of OEIS Counting Conjectures in Lean 4

Alexander Ross Cohen
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Cellular Automata and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Certified Digit Automata for Nonlinear Two-Dimensional Cellular Automata: Kernel-Checked Proofs of OEIS Counting Conjectures in Lean 4 — Alexander Ross Cohen · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS