Lower bound 19 <= R for reversible binary 2D Moore rules (disproof of R = 18)
ProvedReversibleCA.nineteen_le_Rcellular-automatacombinatoricsreversibility
There exist at least 19 pairwise distinct reversible binary 2D cellular automata on the 3x3 Moore neighborhood, disproving the conjecture R = 18.
Preamble
import Lean
Formal statement
namespace ReversibleCA
def Coord : Type := Int × Int
def Config : Type := Coord → Bool
def Bijective {α β : Type} (f : α → β) : Prop := (∀ x y, f x = f y → x = y) ∧ (∀ y, ∃ x, f x = y)
def Nbhd : Type := Fin 3 × Fin 3
deriving BEq, DecidableEq
def LocalRule : Type := (Nbhd → Bool) → Bool
def globalMap (f : LocalRule) (c : Config) : Config :=
fun z => f (fun ⟨i, j⟩ => c (z.1 + (i.val - 1 : Int), z.2 + (j.val - 1 : Int)))
def IsReversible (f : LocalRule) : Prop := Bijective (globalMap f)
theorem nineteen_le_R :
∃ L : List LocalRule, 19 ≤ L.length ∧ L.Pairwise (· ≠ ·) ∧ ∀ f ∈ L, IsReversible f := by sorry
end ReversibleCARead-back
What the Lean code literally says, in plain math · claude-3-5-sonnet-20241022
The theorem asserts that there exists a list L of local rules of length at least 19 such that all rules in L are pairwise distinct and every rule in L has a bijective global map on Z^2.
Human review
Confirmed by the mission captain (proposal self-audit).