AFTD Auto-Formalizing Theoretical Domains

run_grundy_step

theoremverified

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.

  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.

    lines 12–15

    uses run_grundy, run_grundy_aux.eq_2, if_neg

      rw [run_grundy]
      rw [run_grundy_aux.eq_2]
      rw [if_neg (by omega : ¬ k = 0)]
      dsimp only
  2. 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]`.

    lines 16–21

    uses congrArg, List.flatMap_congr, List.mem_range, List.filterMap_congr

      apply congrArg nat_mex_list
      apply List.flatMap_congr
      intro idx hidx
      simp only [List.mem_range] at hidx
      apply List.filterMap_congr
      intro δ _
  3. 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.

    lines 22–26

    uses run_grundy_aux_eq_run_grundy

      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]
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 α β`.

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

/-- 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]
See it in the graphDiscuss this resultChallenge it