run_grundy_step
For every k > 0 and boundary conditions α and β, the Grundy value run_grundy k α β is the minimum excluded value of the nim-sums of the Grundy values of the two sub-runs over all legal moves on edges 1 ≤ j ≤ k and orientations δ.
Statement
theorem run_grundy_step (k : ℕ) (α β : RunBoundary) (hk : 0 < k) : run_grundy k α β = nat_mex_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 δ then some (run_grundy (j - 1) α δ ^^^ run_grundy (k - j) δ β) else none)
- Source
- scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md:419
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_aux_eq_run_grundyFor any natural numbers n and k with k + 1 ≤ n, and any boundary conditions α and β, run_grundy_aux n k α β equals run_grundy k α β.
- 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.
- RunBoundaryThe boundary condition at an end of a path segment in the Game of Arrows is either free (denoted *), blocked inward (denoted →), or…
- 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…
Read back from the Lean
For every natural number k and every pair of boundary values α, β : RunBoundary, if 0 < k, then run_grundy k α β equals the minimum excluded natural number (nat_mex_list) of the list formed by taking, for each idx in [0, ..., k - 1] (letting j = idx + 1) and each δ in [RunBoundary.blocked_in, RunBoundary.blocked_out], the bitwise XOR (^^^) of run_grundy (j - 1) α δ and run_grundy (k - j) δ β whenever run_move_legal k α β j δ evaluates to true (and omitting it otherwise).
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 establishes the Sprague-Grundy recurrence for a run of length k > 0, equating its Grundy value to the minimum excluded value (mex) of the nim-sums of the two sub-runs across all legal moves. The proof unfolds `run_grundy k α β` into its fuel-bounded definition `run_grundy_aux (k + 1) k α β`, discards the base case k = 0 using k > 0, and penetrates the nested list comprehensions via list congruence lemmas. Finally, it applies `run_grundy_aux_eq_run_grundy` to replace the recursive calls using fuel k with `run_grundy`, which is valid because both sub-runs have length at most k - 1.
`run_grundy k α β` equals the mex of the nim-sums of sub-runs evaluated with fuel k by `run_grundy_aux`.
By definition (`run_grundy`), `run_grundy k α β` expands to `run_grundy_aux (k + 1) k α β`. Unfolding the recursive definition of `run_grundy_aux` with successor fuel (`run_grundy_aux.eq_2`) yields an `if k = 0 then 0 else ...` expression. Since k > 0, linear arithmetic (`omega`) establishes `¬ k = 0`, so `if_neg` simplifies the expression to the `else` branch, which computes the mex over all legal moves with recursive calls evaluated using fuel k.
uses
run_grundy,run_grundy_aux.eq_2,if_negrw [run_grundy] rw [run_grundy_aux.eq_2] rw [if_neg (by omega : ¬ k = 0)] dsimp only
It suffices to show that for each index `idx < k` and boundary orientation `δ`, the move evaluation using fuel k in `run_grundy_aux` equals the one using `run_grundy`.
By function congruence (`congrArg nat_mex_list`), it suffices to show that the lists of move outcomes are identical. Using list congruence lemmas (`List.flatMap_congr` and `List.filterMap_congr`), this reduces to pointwise equality for each index `idx` in `List.range k` (where `List.mem_range` rewrites the membership condition to `idx < k`) and each orientation `δ` in `[blocked_in, blocked_out]`.
uses
congrArg,List.flatMap_congr,List.mem_range,List.filterMap_congrapply congrArg nat_mex_list apply List.flatMap_congr intro idx hidx simp only [List.mem_range] at hidx apply List.filterMap_congr intro δ _
The sub-run Grundy values computed with fuel k match the true `run_grundy` values, completing the proof.
A move at index `idx` (representing edge `j = idx + 1`) divides the run into a left sub-run of length `(idx + 1) - 1 = idx` and a right sub-run of length `k - (idx + 1)`. Since `idx < k`, both sub-run lengths L satisfy `L + 1 ≤ k` by linear arithmetic (`omega`). Thus, by `run_grundy_aux_eq_run_grundy`, fuel k is sufficient for both sub-games, establishing `h1` and `h2`. Rewriting the sub-run terms with `h1` and `h2` makes both sides of the equality identical.
uses
run_grundy_aux_eq_run_grundyhave h1 : run_grundy_aux k (idx + 1 - 1) α δ = run_grundy (idx + 1 - 1) α δ := by rw [run_grundy_aux_eq_run_grundy _ _ _ _ (by omega)] have h2 : run_grundy_aux k (k - (idx + 1)) δ β = run_grundy (k - (idx + 1)) δ β := by rw [run_grundy_aux_eq_run_grundy _ _ _ _ (by omega)] rw [h1, h2]
run_grundy- The definition equating `run_grundy k α β` with `run_grundy_aux (k + 1) k α β`.
run_grundy_aux.eq_2- The recurrence equation for `run_grundy_aux (n + 1) k α β`: it returns 0 when k = 0, and otherwise computes the mex of the nim-sums of sub-run values evaluated with fuel n.
if_neg- An `if-then-else` expression evaluates to its `else` branch when the condition is false.
congrArg- If two arguments are equal, applying the same function to each produces equal values.
List.flatMap_congr- Two `flatMap` calls over the same list produce identical results if their transformation functions agree on every element in the list.
List.mem_range- A natural number m belongs to `List.range n` if and only if m < n.
List.filterMap_congr- Two `filterMap` calls over the same list are equal if their mapping functions agree on every element in the list.
run_grundy_aux_eq_run_grundy- If the fuel n satisfies k + 1 ≤ n, then `run_grundy_aux n k α β = run_grundy k α β`.
- The auxiliary function `run_grundy_aux` and its fuel parameter are formal artifacts ensuring termination in Lean; on paper, `run_grundy` is defined directly by well-founded recursion on the length k.
- The three arithmetic conditions (`¬ k = 0`, `idx + 1 - 1 + 1 ≤ k`, and `k - (idx + 1) + 1 ≤ k`) are dispatched automatically by `omega`.
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.
/-- Sprague-Grundy recurrence for the Grundy value of a run of length k > 0. -/theorem run_grundy_step (k : ℕ) (α β : RunBoundary) (hk : 0 < k) : run_grundy k α β = nat_mex_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 δ then some (run_grundy (j - 1) α δ ^^^ run_grundy (k - j) δ β) else none) := by rw [run_grundy] rw [run_grundy_aux.eq_2] rw [if_neg (by omega : ¬ k = 0)] dsimp only apply congrArg nat_mex_list apply List.flatMap_congr intro idx hidx simp only [List.mem_range] at hidx apply List.filterMap_congr intro δ _ have h1 : run_grundy_aux k (idx + 1 - 1) α δ = run_grundy (idx + 1 - 1) α δ := by rw [run_grundy_aux_eq_run_grundy _ _ _ _ (by omega)] have h2 : run_grundy_aux k (k - (idx + 1)) δ β = run_grundy (k - (idx + 1)) δ β := by rw [run_grundy_aux_eq_run_grundy _ _ _ _ (by omega)] rw [h1, h2]