spider_gamma_root_options
The option list of the root state S(1,2,z) at fuel N+1 (with z = m+1 and N ≥ 3) is the mex of 8 explicit "head" options together with the long block (List.range m).flatMap over cuts of the leg of length z.
Statement
theorem spider_gamma_root_options (N z m : ℕ) (hz : z = m + 1) (hN : 3 ≤ N) : spider_gamma (N + 1) CentreStatus.none [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free), (z, SpiderLegEnd.free)] = nat_mex_list ([ spider_gamma N CentreStatus.incoming [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)], spider_gamma N CentreStatus.outgoing [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)], 1 ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], 1 ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], spider_gamma N CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], spider_gamma N CentreStatus.none [(1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], m ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)], m ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]] ++ (List.range m).flatMap (fun i => [(z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)], (z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]]))
- Source
- step towards spider_grundy_val_one_two
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- SpiderLegEndThe end condition of an attached leg in a spider state is either free (no arc on the leg), inward (pointing towards the centre), 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.
- spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
- spider_rhoThe function spider_rho takes h : ℕ and delta, phi : SpiderLegEnd, returning h if phi = free; if phi = inward, it returns h % 2 when delta…
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
The proof, explained
The theorem determines the normal form of the option list for the root spider state $S(1,2,z)$ with $z = m + 1$ at fuel $N+1$ by unrolling the definition of `spider_gamma`. The outer loop flatMaps over cuts of the three legs of lengths 1, 2, and $m+1$. Evaluating the cut ranges for the first two legs explicitly and splitting the range of the third leg into a complete cut and partial cuts yields the 8 explicit initial options together with the parameterized family of cuts along the third leg.
Substitute $z = m + 1$ and reduce the equality of Grundy values to equality of their underlying option lists.
The substitution `hz` replaces $z$ with $m + 1$. Applying congruence (`congr_arg`) with respect to `nat_mex_list` strips the outer minimum excluded value operator, reducing the theorem to showing that the list of options generated by `spider_gamma` equals the right-hand list. (The hypothesis `hN : 3 ≤ N` is recorded on line 17 but not needed for the expansion.)
uses
congr_arghave _ := hN subst hz apply congr_arg nat_mex_list
Unfold `spider_gamma` and expand the outer loop over the three legs of the spider.
By definition, for fuel $N + 1$ and centre status `none`, `spider_gamma` computes options by flatMapping over the indexed legs `[((1, free), 0), ((2, free), 1), ((m + 1, free), 2)]`. Rewriting with `List.flatMap_cons` and `List.flatMap_nil` decomposes this outer loop into the concatenation of three lists of moves—one per leg—and `dsimp only` simplifies pattern matching and index deletions.
uses
List.flatMap_cons,List.flatMap_nilchange List.flatMap _ [((1, SpiderLegEnd.free), 0), ((2, SpiderLegEnd.free), 1), ((m + 1, SpiderLegEnd.free), 2)] = _ rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil] dsimp only
Evaluate the cut position ranges for each leg, splitting the third leg's range into the full cut and partial cuts.
For the leg of length 1, `List.range 1` evaluates definitionally to `[0]`. For the leg of length 2, `List.range 2` evaluates to `[0, 1]`. For the leg of length $m + 1$, `List.range_succ_eq_map` splits `List.range (m + 1)` into `0` (cutting off the entire leg) followed by `List.map Nat.succ (List.range m)` (partial cuts that leave a stub on the spider).
uses
List.range_succ_eq_maphave hr1 : List.range 1 = [0] := rfl have hr2 : List.range 2 = [0, 1] := rfl rw [hr1, hr2] rw [List.range_succ_eq_map (n := m)]
Unroll the cuts for the first two legs and index partial cuts along the third leg directly over `List.range m`.
Simplifying with `List.flatMap_cons` and `List.flatMap_nil` unrolls the inner loops over cut positions for the explicit lists `[0]` and `[0, 1]`, and `List.append_nil` removes trailing nil appends. Furthermore, `List.flatMap_map` absorbs `Nat.succ` into the cut function, expressing partial cuts along the third leg directly as a `flatMap` over $i \in \text{List.range } m$.
uses
List.flatMap_cons,List.flatMap_nil,List.append_nil,List.flatMap_mapsimp only [List.flatMap_cons, List.flatMap_nil, List.append_nil, List.flatMap_map]The evaluated options match the 8 explicit head options and the parameterized cuts along the third leg. automation
Simplifying with the definitions of `spider_rho` (the Grundy value of the detached cut segment) and `spider_update_centre` (the updated centre status), along with ground arithmetic, resolves each branch: cuts of length 1 remove the leg entirely and change the centre status to incoming or outgoing, while cuts of length at least 2 retain the centre status and leave a stub of length $j - 1$. The resulting list matches the 8 leading options and the list comprehension along the third leg.
simp [spider_rho, spider_update_centre]
congr_arg- applying a function to equal arguments yields equal results ($a_1 = a_2 \implies f(a_1) = f(a_2)$)
List.flatMap_cons- flatMapping a function over `x :: xs` equals the function applied to `x` concatenated with the flatMap over `xs`
List.flatMap_nil- flatMapping any function over the empty list produces the empty list
List.range_succ_eq_map- the list `List.range (n + 1)` is equal to `0` followed by the elementwise successors of `List.range n`
List.append_nil- appending the empty list to any list leaves it unchanged
List.flatMap_map- mapping $f$ over a list and then flatMapping $g$ is equivalent to flatMapping the composition $g \circ f$ directly
- The hypothesis `hN : 3 ≤ N` is stated in the theorem and acknowledged on line 17 (`have _ := hN`), but it is not used; the algebraic equality of option lists holds formally for any fuel $N+1 \ge 1$.
- Step 5 relies on the `simp` tactic to evaluate ground arithmetic, boolean conditions, and definition unfoldings (`spider_rho`, `spider_update_centre`) across all cut positions and orientations.
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.
/-- Normal form of the root S(1,2,z) option list at fuel N+1. -/theorem spider_gamma_root_options (N z m : ℕ) (hz : z = m + 1) (hN : 3 ≤ N) : spider_gamma (N + 1) CentreStatus.none [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free), (z, SpiderLegEnd.free)] = nat_mex_list ([ spider_gamma N CentreStatus.incoming [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)], spider_gamma N CentreStatus.outgoing [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)], 1 ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], 1 ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], spider_gamma N CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], spider_gamma N CentreStatus.none [(1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)], m ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)], m ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]] ++ (List.range m).flatMap (fun i => [(z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)], (z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]])) := by have _ := hN subst hz apply congr_arg nat_mex_list change List.flatMap _ [((1, SpiderLegEnd.free), 0), ((2, SpiderLegEnd.free), 1), ((m + 1, SpiderLegEnd.free), 2)] = _ rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil] dsimp only have hr1 : List.range 1 = [0] := rfl have hr2 : List.range 2 = [0, 1] := rfl rw [hr1, hr2] rw [List.range_succ_eq_map (n := m)] simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil, List.flatMap_map] simp [spider_rho, spider_update_centre]