AFTD Auto-Formalizing Theoretical Domains

run_grundy_zero

theoremverified

For any boundary conditions α and β, a run of length 0 in the Game of Arrows has Grundy value 0.

Statement

theorem run_grundy_zero (α β : RunBoundary) :
    run_grundy 0 α β = 0
Source
scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md:441
Verified
21 Oct 2026
Axioms
Quot.soundpropext
Built on 5
  • run_grundy_auxThe auxiliary Grundy value function for a run of length k with boundary conditions α and β in the Game of Arrows, computed by recursion up…
  • run_move_legalIn a run of length k with boundary conditions α and β, orienting edge j in direction δ is legal if and only if (j ≠ 1 or α ∈ {free, δ})…
  • run_grundyThe Grundy value of a run of length k with boundary conditions α and β in the Game of Arrows, defined using depth bound k + 1.
  • RunBoundaryThe boundary condition at an end of a path segment in the Game of Arrows is either free (denoted *), blocked inward (denoted →), or…
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.

Read back from the Lean

For all boundary conditions α and β of type RunBoundary, run_grundy 0 α β equals 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof unfolds the definition of `run_grundy` for a run of length 0, reducing the goal to evaluating `run_grundy_aux 1 0 α β`. By the definitional equation of `run_grundy_aux`, when the run length is 0, no moves are available and the function immediately evaluates to 0. The simplification tactic applies these two definitions to reduce both sides to 0 and completes the proof.

  1. $\mathrm{run\_grundy}\,0\,\alpha\,\beta = 0$

    Unfolding the definition of $\mathrm{run\_grundy}$ rewrites $\mathrm{run\_grundy}\,0\,\alpha\,\beta$ to $\mathrm{run\_grundy\_aux}\,1\,0\,\alpha\,\beta$. Applying the defining equation $\mathrm{run\_grundy\_aux.eq\_def}$ evaluates the outer match on $n = 1$ and triggers the $k = 0$ branch, which immediately yields $0$. The simplifier reduces the equality to $0 = 0$ and closes the goal.

    line 4

    uses run_grundy, run_grundy_aux.eq_def

      simp [run_grundy, run_grundy_aux.eq_def]
run_grundy
Defines the Grundy value of a run of length $k$ with boundary conditions $\alpha$ and $\beta$ as $\mathrm{run\_grundy\_aux}\,(k + 1)\,k\,\alpha\,\beta$.
run_grundy_aux.eq_def
The defining equation for $\mathrm{run\_grundy\_aux}$, stating that $\mathrm{run\_grundy\_aux}\,n\,k\,\alpha\,\beta$ evaluates to $0$ when $n = 0$ or $k = 0$, and otherwise recursively computes the mex of the values of all legal moves.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The Grundy value of an empty run (length 0) is 0 for all boundary conditions. -/theorem run_grundy_zero (α β : RunBoundary) :    run_grundy 0 α β = 0 := by  simp [run_grundy, run_grundy_aux.eq_def]
See it in the graphDiscuss this resultChallenge it