Surjunctivity of linear cellular automata over finite fields
Follow the latest progress by email.
For a finite field K of odd characteristic, does there exist a finitely generated group G with torsion and a linear cellular automaton on the full configuration space K^G that is injective but not surjective?
Why it matters and what counts as progress
Why it matters: It tests Gottschalk’s universal surjunctivity principle through a linear cellular automaton over an odd-characteristic field.
What counts as progress: Construct an injective nonsurjective cellular automaton on the full configuration space, or establish surjunctivity under new group assumptions.
How the problem developed
- 2006 · Equivalence [1]
Tullio Ceccherini-Silberstein and Michel Coornaert Related injective-to-surjective behavior of linear cellular automata to direct finiteness of matrix group algebras, giving an algebraic route to studying linear surjunctivity.
- 26 Sept 2026 · Counterexample [2]
OpenAI Reported a finite-field example in odd characteristic with an injective, non-surjective linear cellular automaton on all configurations, refuting universal surjunctivity.
AI contribution
A Counterexample to Kaplansky's Direct-Finiteness Conjecture in Odd Characteristic
For a finite field K of odd characteristic and a finitely generated group G with torsion, the construction gives a linear cellular automaton on all K^G configurations that is injective but not surjective.
Sources
- Ceccherini-Silberstein and Coornaert, Linear cellular automata: Garden of Eden theorem, L-surjunctivity and group rings
- OpenAI, A Counterexample to Kaplansky’s Direct-Finiteness Conjecture in Odd Characteristic
- A Counterexample to Kaplansky's Direct-Finiteness Conjecture in Odd Characteristic
- Odd-characteristic Lean theorem
- Formalization scope
- Companion direct-finiteness background
Website timeline
Publication dates and editorial changes.
OpenAI reports an odd-characteristic counterexample to surjunctivity