spider_blocked_none_one_inward_one_outward_opts_eq
For r ≥ 2, φ ≠ free, and assuming the closed form for all smaller levels, the mex of the raw option list equals the mex of the explicit closed-form list spider_none_one_inward_one_outward_opts r φ.
Statement
theorem spider_blocked_none_one_inward_one_outward_opts_eq (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free)
(ih : ∀ r' < r, 1 ≤ r' → ∀ φ' : SpiderLegEnd, φ' ≠ SpiderLegEnd.free →
spider_gamma (r' + 3) CentreStatus.none
[(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r', φ')] = r') :
nat_mex_list (spider_none_one_inward_one_outward_raw_opts r φ) =
nat_mex_list (spider_none_one_inward_one_outward_opts r φ)- Source
- step towards spider_blocked_none_one_inward_one_outward
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- spider_none_one_inward_one_outward_raw_optsThe raw option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after one unfolding step, in the exact order the recursion…
- spider_none_one_inward_one_outward_optsThe explicit closed-form option list of the state (none;{(1,inward),(1,outward),(r,φ)}) after substituting the sub-state values: the two…
- spider_blocked_incoming_one_outwardFor the configuration κ₂ = (in;{(1,outward)}), the blocked family V^φ_κ₂(r) equals r xor 1 for every r ≥ 1 and both φ.
- spider_blocked_outgoing_one_inwardFor the mirror configuration (out;{(1,inward)}), the blocked family at level r equals r xor 1 for every r ≥ 1 and both far ends φ.
- spider_two_leg_short_short_zeroAt any fuel at least 3, the two-leg state with centre incoming and legs (1,inward),(1,outward) has value 0, and likewise with centre…
- spider_rho_zero_sameFor any non-free spider leg end φ, spider_rho 0 φ φ = 0.
- spider_gamma_rotate_three_short_legsFor any leg p, centre status and fuel, the value of (s;{p,1^in,1^out}) equals the value of (s;{1^in,1^out,p}): the leg p may be moved from…
- spider_gamma_fuel_independentFor every fuel at least the total number of markable edges in L plus one, the value of spider_gamma does not depend on the fuel: it equals…
- 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_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- 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…
- CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…
- Used by 1
- spider_blocked_none_one_inward_one_outwardFor the configuration κ₁ = (none;{(1,inward),(1,outward)}), the blocked family V^φ_κ₁(r) equals r for every r ≥ 1 and both φ.
The proof, explained
The theorem shows that the minimum excluded value (mex) of the raw option list for the spider state with two short legs of length 1 (one inward, one outward) and one leg of length r ≥ 2 equals the mex of its simplified closed-form list. The argument proves that the raw and closed-form option lists are actually identical term-by-term. Both lists are split into three parts—a four-element prefix, a flatMap over indices i < r - 2, and a final singleton—and each part is simplified using prior lemmas on blocked states, fuel independence, and the induction hypothesis for smaller leg lengths.
The initial four options in the raw list evaluate to [r ^^^ 1, r ^^^ 1, spider_rho (r - 1) SpiderLegEnd.inward φ, spider_rho (r - 1) SpiderLegEnd.outward φ].
Each of the four initial options is simplified separately. By spider_blocked_incoming_one_outward and spider_blocked_outgoing_one_inward, the first two options evaluate to r ⊕ 1. By spider_two_leg_short_short_zero, the sub-game on the two short legs [(1, inward), (1, outward)] evaluates to 0 for both incoming and outgoing center statuses. Bitwise XOR with 0 simplifies via Nat.xor_zero, reducing the third and fourth options to the rho component values. Substituting these four results establishes the equality for the four-element head of the list.
uses
spider_blocked_incoming_one_outward,spider_blocked_outgoing_one_inward,spider_two_leg_short_short_zero,Nat.xor_zerohave h1 : spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)] = r ^^^ 1 := spider_blocked_incoming_one_outward r (by omega) φ hφ have h2 : spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (r, φ)] = r ^^^ 1 := spider_blocked_outgoing_one_inward r (by omega) φ hφ have hshort := spider_two_leg_short_short_zero (r + 2) (by omega) have h3 : spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = spider_rho (r - 1) SpiderLegEnd.inward φ := by rw [hshort.1, Nat.xor_zero] have h4 : spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = spider_rho (r - 1) SpiderLegEnd.outward φ := by rw [hshort.2, Nat.xor_zero] have hhead : [spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)], spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (r, φ)], spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)], spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)]] = [r ^^^ 1, r ^^^ 1, spider_rho (r - 1) SpiderLegEnd.inward φ, spider_rho (r - 1) SpiderLegEnd.outward φ] := by simp only [h1, h2, h3, h4]
The flatMap over List.range (r - 2) in the raw option list equals the corresponding intermediate list where the gamma terms are replaced by i + 1.
Using List.flatMap_congr, we consider an arbitrary index i < r - 2 (via List.mem_range). For each i, the sub-game on legs [(1, inward), (1, outward), (i + 1, inward)] has total leg length plus one equal to (i + 1) + 3. By spider_gamma_fuel_independent, evaluating with fuel r + 2 yields the same result as with fuel (i + 1) + 3. Since 1 ≤ i + 1 < r, the induction hypothesis ih applies and evaluates this sub-game to i + 1. The symmetric argument holds for the outward choice (i + 1, outward). Substituting both values completes the simplification of the flatMap.
uses
List.flatMap_congr,List.mem_range,spider_gamma_fuel_independenthave hmid : List.flatMap (fun i => [spider_rho (r - 2 - i) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.inward)], spider_rho (r - 2 - i) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.outward)]]) (List.range (r - 2)) = List.flatMap (fun i => [spider_rho (r - 2 - i) SpiderLegEnd.inward φ ^^^ i + 1, spider_rho (r - 2 - i) SpiderLegEnd.outward φ ^^^ i + 1]) (List.range (r - 2)) := by apply List.flatMap_congr intro i hi simp only [List.mem_range] at hi have hin : spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.inward)] = i + 1 := by rw [spider_gamma_fuel_independent (r + 2) CentreStatus.none _ (by simp; omega)] rw [show (([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.inward)].map Prod.fst).sum + 1) = (i+1)+3 from by simp; omega] exact ih (i + 1) (by omega) (by omega) _ (by simp) have hout : spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.outward)] = i + 1 := by rw [spider_gamma_fuel_independent (r + 2) CentreStatus.none _ (by simp; omega)] rw [show (([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.outward)].map Prod.fst).sum + 1) = (i+1)+3 from by simp; omega] exact ih (i + 1) (by omega) (by omega) _ (by simp) simp only [hin, hout]
The final singleton list [spider_rho 0 φ φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, inward), (1, outward), (r - 1, φ)]] equals [r - 1].
Since φ ≠ free, spider_rho_zero_same gives spider_rho 0 φ φ = 0, and the bitwise XOR with 0 vanishes by Nat.zero_xor. The remaining sub-game has fuel r + 2 = (r - 1) + 3 on legs of lengths 1, 1, and r - 1. Since r ≥ 2 implies 1 ≤ r - 1 < r, applying the induction hypothesis ih with length r - 1 evaluates this sub-game to r - 1.
uses
spider_rho_zero_same,Nat.zero_xorhave htail : [spider_rho 0 φ φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r - 1, φ)]] = [r - 1] := by simp only [spider_rho_zero_same φ hφ, Nat.zero_xor] rw [show r + 2 = (r - 1) + 3 from by omega] rw [ih (r - 1) (by omega) (by omega) φ hφ]
The mex of the raw option list equals the mex of the closed-form option list.
By congr_arg, it suffices to show that the raw option list itself equals the closed-form option list. Both option lists are defined as the concatenation of their head (four elements), middle (flatMap over i < r - 2), and tail (singleton). Rewriting with the equalities proved for each of these three components (hhead, hmid, and htail) demonstrates that the lists are identical.
uses
congr_argapply congr_arg nat_mex_list simp only [spider_none_one_inward_one_outward_raw_opts, spider_none_one_inward_one_outward_opts] rw [hhead, hmid, htail]
spider_blocked_incoming_one_outward- In a spider position with incoming center status and legs of length 1 (outward) and r (with non-free end φ), the Sprague-Grundy value is r ⊕ 1 for r ≥ 1.
spider_blocked_outgoing_one_inward- In a spider position with outgoing center status and legs of length 1 (inward) and r (with non-free end φ), the Sprague-Grundy value is r ⊕ 1 for r ≥ 1.
spider_two_leg_short_short_zero- For a spider with two legs of length 1 (one inward and one outward), the Sprague-Grundy value is 0 whether the center is incoming or outgoing, provided fuel is at least 3.
Nat.xor_zero- Bitwise XOR of any natural number with 0 equals the number itself (x ⊕ 0 = x).
List.flatMap_congr- Two flatMap operations over the same list produce identical lists if their mapping functions agree on every element of the input list.
List.mem_range- A natural number m is in List.range n if and only if m < n.
spider_gamma_fuel_independent- The game value spider_gamma is independent of excess fuel: when fuel is at least the sum of leg lengths plus 1, the value equals that evaluated with exactly the sum of leg lengths plus 1.
spider_rho_zero_same- For any non-free leg end φ, the base component value ρ(0, φ, φ) on a leg of length 0 with matching ends is 0.
Nat.zero_xor- Bitwise XOR of 0 with any natural number equals the number itself (0 ⊕ x = x).
congr_arg- Applying a function to equal arguments yields equal results (if a₁ = a₂, then f(a₁) = f(a₂)).
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.
/-- Substituting all sub-state values in the raw option list yields the closed-form option list. -/theorem spider_blocked_none_one_inward_one_outward_opts_eq (r : ℕ) (hr : 2 ≤ r) (φ : SpiderLegEnd) (hφ : φ ≠ SpiderLegEnd.free) (ih : ∀ r' < r, 1 ≤ r' → ∀ φ' : SpiderLegEnd, φ' ≠ SpiderLegEnd.free → spider_gamma (r' + 3) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r', φ')] = r') : nat_mex_list (spider_none_one_inward_one_outward_raw_opts r φ) = nat_mex_list (spider_none_one_inward_one_outward_opts r φ) := by have h1 : spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)] = r ^^^ 1 := spider_blocked_incoming_one_outward r (by omega) φ hφ have h2 : spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (r, φ)] = r ^^^ 1 := spider_blocked_outgoing_one_inward r (by omega) φ hφ have hshort := spider_two_leg_short_short_zero (r + 2) (by omega) have h3 : spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = spider_rho (r - 1) SpiderLegEnd.inward φ := by rw [hshort.1, Nat.xor_zero] have h4 : spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] = spider_rho (r - 1) SpiderLegEnd.outward φ := by rw [hshort.2, Nat.xor_zero] have hhead : [spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.outward), (r, φ)], spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (r, φ)], spider_rho (r - 1) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.incoming [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)], spider_rho (r - 1) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.outgoing [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)]] = [r ^^^ 1, r ^^^ 1, spider_rho (r - 1) SpiderLegEnd.inward φ, spider_rho (r - 1) SpiderLegEnd.outward φ] := by simp only [h1, h2, h3, h4] have hmid : List.flatMap (fun i => [spider_rho (r - 2 - i) SpiderLegEnd.inward φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.inward)], spider_rho (r - 2 - i) SpiderLegEnd.outward φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.outward)]]) (List.range (r - 2)) = List.flatMap (fun i => [spider_rho (r - 2 - i) SpiderLegEnd.inward φ ^^^ i + 1, spider_rho (r - 2 - i) SpiderLegEnd.outward φ ^^^ i + 1]) (List.range (r - 2)) := by apply List.flatMap_congr intro i hi simp only [List.mem_range] at hi have hin : spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.inward)] = i + 1 := by rw [spider_gamma_fuel_independent (r + 2) CentreStatus.none _ (by simp; omega)] rw [show (([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.inward)].map Prod.fst).sum + 1) = (i+1)+3 from by simp; omega] exact ih (i + 1) (by omega) (by omega) _ (by simp) have hout : spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.outward)] = i + 1 := by rw [spider_gamma_fuel_independent (r + 2) CentreStatus.none _ (by simp; omega)] rw [show (([(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (i + 1, SpiderLegEnd.outward)].map Prod.fst).sum + 1) = (i+1)+3 from by simp; omega] exact ih (i + 1) (by omega) (by omega) _ (by simp) simp only [hin, hout] have htail : [spider_rho 0 φ φ ^^^ spider_gamma (r + 2) CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), (r - 1, φ)]] = [r - 1] := by simp only [spider_rho_zero_same φ hφ, Nat.zero_xor] rw [show r + 2 = (r - 1) + 3 from by omega] rw [ih (r - 1) (by omega) (by omega) φ hφ] apply congr_arg nat_mex_list simp only [spider_none_one_inward_one_outward_raw_opts, spider_none_one_inward_one_outward_opts] rw [hhead, hmid, htail]