spider_gamma_fuel_independent
For 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 the value at the canonical fuel (sum of leg lengths) + 1.
Statement
theorem spider_gamma_fuel_independent (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd))
(hfuel : (L.map Prod.fst).sum + 1 ≤ fuel) :
spider_gamma fuel s L = spider_gamma ((L.map Prod.fst).sum + 1) s L- Source
- step towards spider_eventual_parity_two_three
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- spider_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
- 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_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
- Used by 16
- spider_blocked_two_three_level_fourAt level t = 4, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 10 is at most 7.
- 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_incoming_one_outward_options_eqFor r ≥ 2, the raw options list generated by [(1, outward), (r, φ)] at fuel r + 2 with centre status incoming unfolds to the explicit list…
- spider_blocked_two_three_level_fiveAt level t = 5, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 11 is at most 7.
- spider_blocked_none_one_inward_one_outward_opts_eqFor 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…
- 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_blocked_two_three_level_five_sub_long_leg_j34With free centre, the state obtained from (none;{(5,inward),2^*,3^*}) by cutting the (5,inward) leg at j = 4 leaves a leg of length 2 with…
- spider_blocked_two_three_level_five_sub_sum_nineFour sub-states at fuel 10: the states (incoming;{(5,inward),(3,free)}) and (outgoing;{(5,inward),(3,free)}) have value 4 and 6, and the…
- 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 φ.
- spider_blocked_two_three_level_five_sub_sum_sevenThe two sub-states with free centre where a leg of length 2 with far end inward (resp. outward) is added to the free legs 2 and 3 have…
- spider_blocked_two_three_level_five_sub_incoming_two_threeWith centre incoming (resp. outgoing) and free legs of length 2 and 3, the value at fuel 10 is 3 (both).
- spider_blocked_two_three_level_five_sub_long_leg_j4Cutting the (5,inward) leg at j = 5 leaves, besides the free legs 2 and 3, a leg of length 4; at fuel 10 the value is 5 both when that…
- spider_blocked_two_three_level_five_sub_sum_eightFour sub-states at fuel 10: the two states obtained by cutting the long leg at j = 4, which add a leg of length 3 with far end inward…
- spider_eventual_parity_two_three_blocked_smallFor the configuration κ0 = (none;{2^*,3^*}), the blocked family at level t is 2 for t = 1 and 6 for t = 2, for both far ends, and it is at…
- spider_blocked_two_three_level_five_sub_sum_sixThe two sub-states with free centre, a short leg of length 1 whose far end is inward (resp. outward), and the free legs 2 and 3, have…
- spider_blocked_two_three_level_five_sub_short_legsWith centre incoming (resp. outgoing) and the legs (5,inward) and the free leg 2, the value at fuel 10 is 0 (resp. 1).
The proof, explained
The theorem establishes that the Grundy value `spider_gamma fuel s L` is independent of the recursion fuel once `fuel ≥ sum(L) + 1`, where `sum(L)` is the total length of all spider legs. The result is proved by strong induction on `sum(L)`. In the base cases where the center is free or the spider has at most one leg, `spider_gamma` evaluates non-recursively, making the fuel irrelevant. For graphs with at least two legs, every valid move either shortens or completely removes a leg, strictly decreasing the total sum of leg lengths; by the induction hypothesis, all transition values under any two sufficient fuels coincide, making the lists of game options and their minimum excluded value (mex) identical.
Erasing the leg at index `idx` leaves a list whose sum of leg lengths plus the erased leg's length equals the original total sum.
The element `L[idx]` prepended to `L.eraseIdx idx` forms a permutation of `L` via `List.getElem_cons_eraseIdx_perm`. Permutations have equal sums, and after commuting `map Prod.fst` past `eraseIdx` via `List.eraseIdx_map` and expanding the head element with `List.sum_cons` and `List.getElem_map`, linear arithmetic (`omega`) equates the sum of the erased list plus `L[idx].1` to the original sum.
uses
List.eraseIdx_map,List.sum_cons,List.getElem_maphave hlen : idx < (L.map Prod.fst).length := by simpa using h_idx have hp := (L.map Prod.fst).getElem_cons_eraseIdx_perm hlen have hsum := hp.sum_eq rw [← List.eraseIdx_map] simp only [List.sum_cons, List.getElem_map] at hsum omega
Completely erasing a leg with strictly positive length strictly decreases the total sum of leg lengths.
Substituting `L[idx].1 = h` into `spider_gamma_fuel_independent_sum_eraseIdx_eq` gives `((L.eraseIdx idx).map Prod.fst).sum + h = (L.map Prod.fst).sum`. Since `h > j_zero ≥ 0`, `h` is at least 1, so linear arithmetic (`omega`) shows the erased list has strictly smaller total sum.
uses
spider_gamma_fuel_independent_sum_eraseIdx_eqhave := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx rw [hh] at this omega
Replacing a leg of length `h` with a shorter leg of length `j_zero < h` strictly decreases the total sum of leg lengths.
Expanding the sum of the modified list using `List.map_cons` and `List.sum_cons` gives `(j_zero + 1 - 1) + ((L.eraseIdx idx).map Prod.fst).sum`. Using `spider_gamma_fuel_independent_sum_eraseIdx_eq` with `L[idx].1 = h` and the inequality `j_zero < h`, linear arithmetic (`omega`) confirms the new sum is strictly smaller than the original sum.
uses
spider_gamma_fuel_independent_sum_eraseIdx_eq,List.map_cons,List.sum_conshave := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx rw [hh] at this simp only [List.map_cons, List.sum_cons] omega
By strong induction on the total sum of leg lengths n, we may assume both fuel values are positive successors.
We perform strong induction on the sum of leg lengths $n$ via `Nat.strong_induction_on`. In the inductive step, both fuel values satisfy $\\text{fuel} \\ge n + 1 \\ge 1$, so the zero-fuel cases are ruled out as contradictory by linear arithmetic (`omega`), leaving $\\text{fuel}_1 = f_1 + 1$ and $\\text{fuel}_2 = f_2 + 1$.
uses
Nat.strong_induction_oninduction' n using Nat.strong_induction_on with n IH intro L hn fuel1 fuel2 s _h1 _h2 cases fuel1 with | zero => omega | succ f1 => cases fuel2 with | zero => omega | succ f2 =>
When the center is free, or when the spider has at most one leg, `spider_gamma` is independent of the fuel.
If $s = \\text{CentreStatus.free}$, `spider_gamma` evaluates directly by folding `spider_rho_star` over $L$ (`spider_gamma.eq_def`), which does not reference fuel. If $s \\ne \\text{free}$, we match on $L$: if $L = []$, both sides evaluate to 0; if $L = [(h, \\phi)]$, both sides evaluate directly to `spider_rho` evaluated on $h$ and the orientations (`spider_gamma.eq_def`), neither of which involves fuel.
uses
spider_gamma.eq_defby_cases hs : s = CentreStatus.free · subst hs; rw [spider_gamma.eq_def, spider_gamma.eq_def] · match L with | [] => rw [spider_gamma.eq_def, spider_gamma.eq_def] | [(h, phi)] => rw [spider_gamma.eq_def, spider_gamma.eq_def]
For spiders with at least two legs, `spider_gamma` reduces to the minimum excluded value of transition options, reducing fuel independence to equality of option lists.
When $L = a :: b :: \\text{rest}$, $L$ is non-empty and has more than one leg. Rewriting both sides with `spider_gamma.eq_7` expresses `spider_gamma (f + 1) s L` as the minimum excluded value (`nat_mex_list`) of the options list. Congruence (`congr 1`) reduces the goal to showing that the lists of options generated under fuel $f_1$ and fuel $f_2$ are identical.
uses
spider_gamma.eq_7| a :: b :: rest => have hL1 : (a :: b :: rest) ≠ [] := by simp have hL2 : ∀ h phi, (a :: b :: rest) ≠ [(h, phi)] := by intro h phi; simp rw [spider_gamma.eq_7 s (a :: b :: rest) f1 hs hL1 hL2] rw [spider_gamma.eq_7 s (a :: b :: rest) f2 hs hL1 hL2] congr 1Iterating over leg choices, move lengths, and endpoint orientations reduces option equality to valid moves.
Using `List.flatMap_congr` over the legs in `L.zipIdx` (with `List.mem_zipIdx`), over move lengths $j_0 \\in \\text{range } h$ (with `List.mem_range.mp`), and `List.filterMap_congr` over endpoint directions $\\delta$, we compare options elementwise. On an invalid move, both sides produce `none`, which holds reflexively (`rfl`).
uses
List.flatMap_congr,List.mem_zipIdx,List.mem_range.mp,List.filterMap_congrapply List.flatMap_congr intro ⟨⟨h, phi⟩, idx⟩ h_mem have h_zip := List.mem_zipIdx h_mem have h_idx : idx < (a :: b :: rest).length := by simpa using h_zip.2.1 have h_eq : (h, phi) = (a :: b :: rest)[idx] := by simpa using h_zip.2.2 have hh : (a :: b :: rest)[idx].1 = h := by rw [← h_eq] apply List.flatMap_congr intro j_zero hj_mem have hj : j_zero < h := List.mem_range.mp hj_mem apply List.filterMap_congr intro delta hdelta_mem split_ifs with h1_cond h2_cond · rfl
For moves shortening a leg ($j \\ge 2$), the recursive values under $f_1$ and $f_2$ agree by induction.
When $j \\ge 2$, the move replaces leg `idx` with a shorter leg of length $j_0 = j - 1$. Lemma `spider_gamma_fuel_independent_sum_branch2_lt` proves the new sum of leg lengths is strictly less than $n$. Since $f_1$ and $f_2$ are at least the new sum plus one, the induction hypothesis `IH` applies, equating the recursive evaluations under $f_1$ and $f_2$.
uses
spider_gamma_fuel_independent_sum_branch2_lt· dsimp only have h_lt := spider_gamma_fuel_independent_sum_branch2_lt (a :: b :: rest) idx h_idx h hh j_zero hj delta rw [hn] at h_lt have h_IH := IH _ h_lt ((j_zero + 1 - 1, delta) :: (a :: b :: rest).eraseIdx idx) rfl f1 f2 s (by omega) (by omega) rw [h_IH]
For moves completely removing a leg ($j = 1$), the recursive values under $f_1$ and $f_2$ agree by induction.
When $j < 2$ (so $j = 1$), the leg is deleted and the center status is updated to `spider_update_centre s delta`. Lemma `spider_gamma_fuel_independent_sum_branch1_lt` proves the sum of the remaining leg lengths is strictly less than $n$. The induction hypothesis `IH` again applies to equate the recursive calls under $f_1$ and $f_2$.
uses
spider_gamma_fuel_independent_sum_branch1_lt· dsimp only have h_lt := spider_gamma_fuel_independent_sum_branch1_lt (a :: b :: rest) idx h_idx h hh j_zero hj rw [hn] at h_lt have h_IH := IH _ h_lt ((a :: b :: rest).eraseIdx idx) rfl f1 f2 (spider_update_centre s delta) (by omega) (by omega) rw [h_IH]
For any fuel at least `sum(L) + 1`, `spider_gamma fuel s L` equals `spider_gamma (sum(L) + 1) s L`.
The theorem specializes the auxiliary lemma `spider_gamma_fuel_independent_aux` with $n = \\text{sum}(L)$, $\\text{fuel}_1 = \\text{fuel}$, and $\\text{fuel}_2 = \\text{sum}(L) + 1$, where the fuel hypothesis for $\\text{fuel}_2$ is satisfied trivially by linear arithmetic (`omega`).
uses
spider_gamma_fuel_independent_auxexact spider_gamma_fuel_independent_aux (L.map Prod.fst).sum L rfl fuel ((L.map Prod.fst).sum + 1) s hfuel (by omega)
List.eraseIdx_map- Erasing an element at index `idx` after mapping `f` over a list is identical to mapping `f` over the list with index `idx` erased.
List.sum_cons- The sum of a non-empty list `a :: l` equals `a` plus the sum of `l`.
List.getElem_map- The `i`-th element of `List.map f l` equals `f` applied to the `i`-th element of `l`.
spider_gamma_fuel_independent_sum_eraseIdx_eq- Erasing the element at index `idx` from `L` leaves a list whose sum of leg lengths plus `L[idx].1` equals the total sum of leg lengths of `L`.
List.map_cons- Mapping a function over `a :: l` produces `f a :: List.map f l`.
Nat.strong_induction_on- Strong induction principle on ℕ: to prove `p n` for all `n`, it suffices to show that `p n` follows from `p m` holding for all `m < n`.
spider_gamma.eq_def- The recursive unfolding definition of `spider_gamma` by case analysis on fuel, center status, and leg list.
spider_gamma.eq_7- The unfolding of `spider_gamma (fuel + 1) s L` as the mex (`nat_mex_list`) of the transition options when `s ≠ CentreStatus.free` and `L` has at least two elements.
List.flatMap_congr- Two flat-mapped lists `List.flatMap f l` and `List.flatMap g l` are equal if `f` and `g` agree on every element of `l`.
List.mem_zipIdx- An element `(x, i)` is in `xs.zipIdx` if and only if `i < xs.length` and `x = xs[i]`.
List.mem_range.mp- An element is in `List.range h` if and only if it is strictly less than `h`.
List.filterMap_congr- Two filter-mapped lists `List.filterMap f l` and `List.filterMap g l` are equal if the transformation functions agree on every element of `l`.
spider_gamma_fuel_independent_sum_branch2_lt- Replacing a leg of length `h` at `idx` with a shorter leg of length `j_zero < h` strictly decreases the total sum of leg lengths.
spider_gamma_fuel_independent_sum_branch1_lt- Completely erasing a leg of positive length `h` at `idx` strictly decreases the total sum of leg lengths.
spider_gamma_fuel_independent_aux- For any two fuel amounts both at least the total sum of leg lengths plus one, `spider_gamma` evaluates to the same value.
- The parameter `fuel` is an artifact of formal structural recursion in Lean, providing an upper bound on call depth so that `spider_gamma` can be defined; mathematically, the game terminates because each valid move strictly decreases the total length of the spider legs.
- `nat_mex_list` computes the minimum excluded non-negative integer (mex) of a list of natural numbers.
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.
lemma spider_gamma_fuel_independent_sum_eraseIdx_eq (L : List (ℕ × SpiderLegEnd)) (idx : ℕ) (h_idx : idx < L.length) : ((L.eraseIdx idx).map Prod.fst).sum + (L[idx].1) = (L.map Prod.fst).sum := by have hlen : idx < (L.map Prod.fst).length := by simpa using h_idx have hp := (L.map Prod.fst).getElem_cons_eraseIdx_perm hlen have hsum := hp.sum_eq rw [← List.eraseIdx_map] simp only [List.sum_cons, List.getElem_map] at hsum omegalemma spider_gamma_fuel_independent_sum_branch1_lt (L : List (ℕ × SpiderLegEnd)) (idx : ℕ) (h_idx : idx < L.length) (h : ℕ) (hh : L[idx].1 = h) (j_zero : ℕ) (hj : j_zero < h) : ((L.eraseIdx idx).map Prod.fst).sum < (L.map Prod.fst).sum := by have := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx rw [hh] at this omegalemma spider_gamma_fuel_independent_sum_branch2_lt (L : List (ℕ × SpiderLegEnd)) (idx : ℕ) (h_idx : idx < L.length) (h : ℕ) (hh : L[idx].1 = h) (j_zero : ℕ) (hj : j_zero < h) (delta : SpiderLegEnd) : (((j_zero + 1 - 1, delta) :: (L.eraseIdx idx)).map Prod.fst).sum < (L.map Prod.fst).sum := by have := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx rw [hh] at this simp only [List.map_cons, List.sum_cons] omegalemma spider_gamma_fuel_independent_aux (n : ℕ) : ∀ (L : List (ℕ × SpiderLegEnd)) (_ : (L.map Prod.fst).sum = n) (fuel1 fuel2 : ℕ) (s : CentreStatus) (_h1 : (L.map Prod.fst).sum + 1 ≤ fuel1) (_h2 : (L.map Prod.fst).sum + 1 ≤ fuel2), spider_gamma fuel1 s L = spider_gamma fuel2 s L := by induction' n using Nat.strong_induction_on with n IH intro L hn fuel1 fuel2 s _h1 _h2 cases fuel1 with | zero => omega | succ f1 => cases fuel2 with | zero => omega | succ f2 => by_cases hs : s = CentreStatus.free · subst hs; rw [spider_gamma.eq_def, spider_gamma.eq_def] · match L with | [] => rw [spider_gamma.eq_def, spider_gamma.eq_def] | [(h, phi)] => rw [spider_gamma.eq_def, spider_gamma.eq_def] | a :: b :: rest => have hL1 : (a :: b :: rest) ≠ [] := by simp have hL2 : ∀ h phi, (a :: b :: rest) ≠ [(h, phi)] := by intro h phi; simp rw [spider_gamma.eq_7 s (a :: b :: rest) f1 hs hL1 hL2] rw [spider_gamma.eq_7 s (a :: b :: rest) f2 hs hL1 hL2] congr 1 apply List.flatMap_congr intro ⟨⟨h, phi⟩, idx⟩ h_mem have h_zip := List.mem_zipIdx h_mem have h_idx : idx < (a :: b :: rest).length := by simpa using h_zip.2.1 have h_eq : (h, phi) = (a :: b :: rest)[idx] := by simpa using h_zip.2.2 have hh : (a :: b :: rest)[idx].1 = h := by rw [← h_eq] apply List.flatMap_congr intro j_zero hj_mem have hj : j_zero < h := List.mem_range.mp hj_mem apply List.filterMap_congr intro delta hdelta_mem split_ifs with h1_cond h2_cond · rfl · dsimp only have h_lt := spider_gamma_fuel_independent_sum_branch2_lt (a :: b :: rest) idx h_idx h hh j_zero hj delta rw [hn] at h_lt have h_IH := IH _ h_lt ((j_zero + 1 - 1, delta) :: (a :: b :: rest).eraseIdx idx) rfl f1 f2 s (by omega) (by omega) rw [h_IH] · dsimp only have h_lt := spider_gamma_fuel_independent_sum_branch1_lt (a :: b :: rest) idx h_idx h hh j_zero hj rw [hn] at h_lt have h_IH := IH _ h_lt ((a :: b :: rest).eraseIdx idx) rfl f1 f2 (spider_update_centre s delta) (by omega) (by omega) rw [h_IH]/-- spider_gamma is independent of the fuel once the fuel is at least the total leg length plus one. -/theorem spider_gamma_fuel_independent (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) (hfuel : (L.map Prod.fst).sum + 1 ≤ fuel) : spider_gamma fuel s L = spider_gamma ((L.map Prod.fst).sum + 1) s L := by exact spider_gamma_fuel_independent_aux (L.map Prod.fst).sum L rfl fuel ((L.map Prod.fst).sum + 1) s hfuel (by omega)