AFTD Auto-Formalizing Theoretical Domains

run_grundy_aux_eq_run_grundy

theoremverified

For any natural numbers n and k with k + 1 ≤ n, and any boundary conditions α and β, run_grundy_aux n k α β equals run_grundy k α β.

Statement

theorem run_grundy_aux_eq_run_grundy (n k : ℕ) (α β : RunBoundary) (hn : k + 1 ≤ n) :
    run_grundy_aux n k α β = run_grundy k α β
Source
scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md:430
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • 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.
  • 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…
  • RunBoundaryThe boundary condition at an end of a path segment in the Game of Arrows is either free (denoted *), blocked inward (denoted →), or…
  • 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, δ})…
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
Used by 1
  • run_grundy_stepFor every k > 0 and boundary conditions α and β, the Grundy value run_grundy k α β is the minimum excluded value of the nim-sums of the…

Read back from the Lean

For all natural numbers n and k, and for all boundary conditions α, β : RunBoundary, if k + 1 ≤ n, then run_grundy_aux n k α β equals run_grundy k α β.

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 theorem states that the auxiliary Grundy function `run_grundy_aux n k α β` stabilizes and equals `run_grundy k α β` whenever the depth bound satisfies n ≥ k + 1. The proof proceeds by strong induction on the depth bound n, with the base case n = 0 being vacuously true. In the inductive step for k > 0, unfolding the definitions reduces equality to showing that `run_grundy_aux` at depth m and at depth k agree on all sub-run lengths strictly less than k, which follows because each resulting sub-run satisfies the induction hypothesis at both depth bounds.

  1. At successor depth n + 1, `run_grundy_aux (n + 1) k α β` unfolds to 0 if k = 0, and otherwise to the mex of the option list evaluated using `run_grundy_aux n`.

    By definition, `run_grundy_aux` at depth n + 1 is computed via well-founded bounded recursion (`Nat.brecOn.go` using the step functional `run_grundy_aux._f`). Rewriting with its definitional expansion shows that when k = 0 the value is 0, and when k > 0 it evaluates the minimum excluded value (`nat_mex_list`) of the option list generated using the depth-n Grundy function.

    lines 10–14

    uses run_grundy_aux._f, Nat.brecOn.go

    lemma run_grundy_aux_eq_run_grundy_aux_succ_eq (n k : ℕ) (α β : RunBoundary) :
        run_grundy_aux (n+1) k α β =
          if k = 0 then 0 else nat_mex_list (run_grundy_aux_eq_run_grundy_opt_list k (run_grundy_aux n) α β) := by
      rw [show run_grundy_aux (n+1) k α β = run_grundy_aux._f (n+1) ⟨run_grundy_aux n, (Nat.brecOn.go n run_grundy_aux._f).2⟩ k α β from rfl]
      rfl
  2. To show that two Grundy candidate functions γ and γ' yield identical option lists for runs of length k, it suffices to show that they produce the same option at each cut position and for each boundary choice.

    Unfolding `run_grundy_aux_eq_run_grundy_opt_list` shows that the option list is generated by flat-mapping over indices `idx < k` via `List.flatMap` and filter-mapping over candidate boundaries δ via `List.filterMap`. Applying the congruence lemmas `List.flatMap_congr` and `List.filterMap_congr` reduces equality of the full option lists to pointwise equality of the option generated at each position and boundary choice.

    lines 17–24

    uses List.flatMap_congr, List.filterMap_congr

    lemma run_grundy_aux_eq_run_grundy_opt_list_congr (k : ℕ) (γ γ' : ℕ → RunBoundary → RunBoundary → ℕ) (α β : RunBoundary)
        (h : ∀ i, i < k → ∀ δ ε, γ i δ ε = γ' i δ ε) :
        run_grundy_aux_eq_run_grundy_opt_list k γ α β = run_grundy_aux_eq_run_grundy_opt_list k γ' α β := by
      unfold run_grundy_aux_eq_run_grundy_opt_list
      apply List.flatMap_congr
      intro idx hidx
      apply List.filterMap_congr
      intro δ hδ
  3. For any cut position j = idx + 1 ≤ k and candidate boundary δ, the options under γ and γ' coincide because all resulting sub-runs have length strictly less than k.

    A move at position j = idx + 1 splits the run of length k into two sub-runs of lengths j - 1 = idx and k - j = k - (idx + 1). Both lengths are strictly less than k (the latter verified by linear arithmetic). By hypothesis h, γ and γ' agree on all lengths strictly smaller than k, so both sub-run values match. A case split on whether the move is legal shows that both options evaluate to `some (...)` with equal nim-sums when legal, and both evaluate to `none` when illegal.

    lines 25–32

      have hidx' : idx < k := by simpa using hidx
      have hj2 : k - (idx + 1) < k := by omega
      have h1 := h idx hidx' α δ
      have h2 := h (k - (idx + 1)) hj2 δ β
      by_cases hc : run_move_legal k α β (idx + 1) δ = true
      · simp [hc, h1, h2]
      · simp [hc]
    
  4. We set up strong induction on the depth bound n; the base case n = 0 is vacuously true.

    We proceed by strong induction on n using `Nat.strongRecOn`, with induction hypothesis that the result holds for all depths strictly smaller than n. In the base case n = 0, the assumption k + 1 ≤ 0 is impossible for any natural number k, which closes the goal by linear arithmetic (`omega`).

    lines 34–40

    uses Nat.strongRecOn

    lemma run_grundy_aux_eq_run_grundy_aux_strong (n : ℕ) :
        ∀ (k : ℕ) (α β : RunBoundary), k + 1 ≤ n → run_grundy_aux n k α β = run_grundy k α β := by
      induction n using Nat.strongRecOn with
      | _ n ih =>
        intro k α β hn
        cases n with
        | zero => omega
  5. At successor depth n = m + 1 with k = 0, both `run_grundy_aux (m + 1) 0 α β` and `run_grundy 0 α β` equal 0.

    For k = 0, the unfolding lemma `run_grundy_aux_eq_run_grundy_aux_succ_eq` simplifies `run_grundy_aux (m + 1) 0 α β` to 0. Similarly, `run_grundy 0 α β` is definitionally `run_grundy_aux 1 0 α β`, which also simplifies to 0 by the same lemma. Both sides equal 0, so they are equal.

    lines 41–50

    uses run_grundy_aux_eq_run_grundy_aux_succ_eq

        | succ m =>
          cases k with
          | zero =>
            have h1 : run_grundy_aux (m+1) 0 α β = 0 := by
              rw [run_grundy_aux_eq_run_grundy_aux_succ_eq]; simp
            have h2 : run_grundy 0 α β = 0 := by
              rw [show run_grundy 0 α β = run_grundy_aux ((0:ℕ)+1) 0 α β from rfl, run_grundy_aux_eq_run_grundy_aux_succ_eq]
              simp
            rw [h1, h2]
          | succ k' =>
  6. For k = k' + 1 > 0, showing `run_grundy_aux (m + 1) (k' + 1) α β = run_grundy (k' + 1) α β` reduces to showing that `run_grundy_aux m` and `run_grundy_aux (k' + 1)` agree on all lengths i < k' + 1.

    Using the successor unfolding lemma `run_grundy_aux_eq_run_grundy_aux_succ_eq` and the definition of `run_grundy (k' + 1) α β` as `run_grundy_aux (k' + 2) (k' + 1) α β`, both sides unfold to the `nat_mex_list` of the option list at length k' + 1, parameterized by `run_grundy_aux m` and `run_grundy_aux (k' + 1)` respectively (the k = 0 branch being eliminated by `Nat.succ_ne_zero` and `if_false`). By congruence of `nat_mex_list` (`congrArg`) and the congruence lemma `run_grundy_aux_eq_run_grundy_opt_list_congr`, it suffices to verify that `run_grundy_aux m` and `run_grundy_aux (k' + 1)` agree on all lengths i < k' + 1.

    lines 51–56

    uses run_grundy_aux_eq_run_grundy_aux_succ_eq, Nat.succ_ne_zero, if_false, congrArg, run_grundy_aux_eq_run_grundy_opt_list_congr

            rw [run_grundy_aux_eq_run_grundy_aux_succ_eq m (k'+1) α β]
            rw [show run_grundy (k'+1) α β = run_grundy_aux (k'+1+1) (k'+1) α β from rfl]
            rw [run_grundy_aux_eq_run_grundy_aux_succ_eq (k'+1) (k'+1) α β]
            simp only [Nat.succ_ne_zero, if_false]
            apply congrArg nat_mex_list
            apply run_grundy_aux_eq_run_grundy_opt_list_congr
  7. For each sub-run length i < k' + 1, both `run_grundy_aux m` and `run_grundy_aux (k' + 1)` evaluate to `run_grundy i`.

    Because i < k' + 1, we have i + 1 ≤ k' + 1 ≤ m. Since m < m + 1 and i + 1 ≤ m, the strong induction hypothesis at depth m shows `run_grundy_aux m i δ ε = run_grundy i δ ε`. Likewise, since k' + 1 < m + 1 (from k' + 2 ≤ m + 1) and i + 1 ≤ k' + 1, the induction hypothesis at depth k' + 1 gives `run_grundy_aux (k' + 1) i δ ε = run_grundy i δ ε`. Both values equal `run_grundy i δ ε`, completing the induction step.

    lines 57–62

            intro i hi δ ε
            have hi1 : i + 1 ≤ k' + 1 := by omega
            have h1 : run_grundy_aux m i δ ε = run_grundy i δ ε := ih m (by omega) i δ ε (by omega)
            have h2 : run_grundy_aux (k'+1) i δ ε = run_grundy i δ ε := ih (k'+1) (by omega) i δ ε hi1
            rw [h1, h2]
    
  8. For all n, k with k + 1 ≤ n and any boundary conditions α, β, `run_grundy_aux n k α β = run_grundy k α β`.

    The main theorem is an immediate application of the strong induction result `run_grundy_aux_eq_run_grundy_aux_strong`.

    lines 64–65

    uses run_grundy_aux_eq_run_grundy_aux_strong

    theorem run_grundy_aux_eq_run_grundy (n k : ℕ) (α β : RunBoundary) (hn : k + 1 ≤ n) :
        run_grundy_aux n k α β = run_grundy k α β := run_grundy_aux_eq_run_grundy_aux_strong n k α β hn
run_grundy_aux._f
The underlying functional used in the bounded recursion (`Nat.brecOn`) definition of `run_grundy_aux`.
Nat.brecOn.go
The internal evaluation function for bounded recursion on natural numbers, computing the current value and the history of previous values.
List.flatMap_congr
Two flat-mapped lists are equal if the mapping functions agree on every element of the input list.
List.filterMap_congr
Two filter-mapped lists are equal if the filtering functions agree on every element of the input list.
Nat.strongRecOn
The strong induction principle for natural numbers: a property holds for all n if it holds for n whenever it holds for all m < n.
run_grundy_aux_eq_run_grundy_aux_succ_eq
Unfolds `run_grundy_aux (n + 1) k α β` to 0 when k = 0, and to the mex of the option list computed using `run_grundy_aux n` when k > 0.
Nat.succ_ne_zero
The successor of any natural number is not zero.
if_false
An if-then-else expression whose condition is false reduces to its else branch.
congrArg
Applying a function to equal inputs yields equal outputs.
run_grundy_aux_eq_run_grundy_opt_list_congr
Two Grundy functions that agree on all sub-run lengths i < k produce identical move option lists for runs of length k.
run_grundy_aux_eq_run_grundy_aux_strong
For all n and k, if k + 1 ≤ n, then `run_grundy_aux n k α β = run_grundy k α β`.

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 option list of a run of length k, parameterized by a Grundy function γ.def run_grundy_aux_eq_run_grundy_opt_list (k : ℕ) (γ : ℕ → RunBoundary → RunBoundary → ℕ) (α β : RunBoundary) : List ℕ :=  (List.range k).flatMap fun idx =>    let j := idx + 1    ([RunBoundary.blocked_in, RunBoundary.blocked_out].filterMap fun δ =>      if run_move_legal k α β j δ = true then        some (γ (j - 1) α δ ^^^ γ (k - j) δ β) else none)-- One-step unfolding of run_grundy_aux at a successor depth.lemma run_grundy_aux_eq_run_grundy_aux_succ_eq (n k : ℕ) (α β : RunBoundary) :    run_grundy_aux (n+1) k α β =      if k = 0 then 0 else nat_mex_list (run_grundy_aux_eq_run_grundy_opt_list k (run_grundy_aux n) α β) := by  rw [show run_grundy_aux (n+1) k α β = run_grundy_aux._f (n+1) ⟨run_grundy_aux n, (Nat.brecOn.go n run_grundy_aux._f).2⟩ k α β from rfl]  rfl-- The option list only depends on the values of γ at indices below k.lemma run_grundy_aux_eq_run_grundy_opt_list_congr (k : ℕ) (γ γ' : ℕ → RunBoundary → RunBoundary → ℕ) (α β : RunBoundary)    (h : ∀ i, i < k → ∀ δ ε, γ i δ ε = γ' i δ ε) :    run_grundy_aux_eq_run_grundy_opt_list k γ α β = run_grundy_aux_eq_run_grundy_opt_list k γ' α β := by  unfold run_grundy_aux_eq_run_grundy_opt_list  apply List.flatMap_congr  intro idx hidx  apply List.filterMap_congr  intro δ hδ  have hidx' : idx < k := by simpa using hidx  have hj2 : k - (idx + 1) < k := by omega  have h1 := h idx hidx' α δ  have h2 := h (k - (idx + 1)) hj2 δ β  by_cases hc : run_move_legal k α β (idx + 1) δ = true  · simp [hc, h1, h2]  · simp [hc]-- Strong induction: run_grundy_aux n k agrees with run_grundy k once the depth bound exceeds k.lemma run_grundy_aux_eq_run_grundy_aux_strong (n : ℕ) :    ∀ (k : ℕ) (α β : RunBoundary), k + 1 ≤ n → run_grundy_aux n k α β = run_grundy k α β := by  induction n using Nat.strongRecOn with  | _ n ih =>    intro k α β hn    cases n with    | zero => omega    | succ m =>      cases k with      | zero =>        have h1 : run_grundy_aux (m+1) 0 α β = 0 := by          rw [run_grundy_aux_eq_run_grundy_aux_succ_eq]; simp        have h2 : run_grundy 0 α β = 0 := by          rw [show run_grundy 0 α β = run_grundy_aux ((0:ℕ)+1) 0 α β from rfl, run_grundy_aux_eq_run_grundy_aux_succ_eq]          simp        rw [h1, h2]      | succ k' =>        rw [run_grundy_aux_eq_run_grundy_aux_succ_eq m (k'+1) α β]        rw [show run_grundy (k'+1) α β = run_grundy_aux (k'+1+1) (k'+1) α β from rfl]        rw [run_grundy_aux_eq_run_grundy_aux_succ_eq (k'+1) (k'+1) α β]        simp only [Nat.succ_ne_zero, if_false]        apply congrArg nat_mex_list        apply run_grundy_aux_eq_run_grundy_opt_list_congr        intro i hi δ ε        have hi1 : i + 1 ≤ k' + 1 := by omega        have h1 : run_grundy_aux m i δ ε = run_grundy i δ ε := ih m (by omega) i δ ε (by omega)        have h2 : run_grundy_aux (k'+1) i δ ε = run_grundy i δ ε := ih (k'+1) (by omega) i δ ε hi1        rw [h1, h2]/-- The auxiliary Grundy value run_grundy_aux n k α β equals run_grundy k α β for all n ≥ k + 1. -/theorem run_grundy_aux_eq_run_grundy (n k : ℕ) (α β : RunBoundary) (hn : k + 1 ≤ n) :    run_grundy_aux n k α β = run_grundy k α β := run_grundy_aux_eq_run_grundy_aux_strong n k α β hn
See it in the graphDiscuss this resultChallenge it