run_grundy_aux_eq_run_grundy
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.
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.
uses
run_grundy_aux._f,Nat.brecOn.golemma 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
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.
uses
List.flatMap_congr,List.filterMap_congrlemma 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δ
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.
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]
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`).
uses
Nat.strongRecOnlemma 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
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.
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' =>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.
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_congrrw [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
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.
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]
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`.
uses
run_grundy_aux_eq_run_grundy_aux_strongtheorem 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 α β`.
- The definition `run_grundy_aux` is implemented via bounded recursion (`Nat.brecOn`), which requires an explicit unfolding lemma (`run_grundy_aux_eq_run_grundy_aux_succ_eq`) to expose the successor step equation.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
-- 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