spider_gamma_reversal
For every fuel, centre status s and leg list L, the value of the spider state (s;L) equals the value of the state obtained by exchanging incoming and outgoing in the centre status and in every far end of L.
Statement
theorem spider_gamma_reversal (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))
- Source
- step towards spider_eventual_parity_two_three
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- spider_reverse_leg_endThe reversal of a spider leg end: free is fixed, inward and outward are exchanged.
- spider_reverse_centre_statusThe reversal of a centre status: none and free are fixed, incoming and outgoing are exchanged.
- 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 3
- spider_blocked_two_three_reversalFor any fuel and leg length t, the spider gamma value with centre none and legs (t, outward), (2, free), (3, free) equals the gamma value…
- 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_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 φ.
The proof, explained
The theorem establishes that the Sprague-Grundy value `spider_gamma` of a spider position is invariant under simultaneously reversing the inward and outward orientations of the centre status and every leg endpoint. The proof proceeds by induction on `fuel`. Base cases with a free centre or at most one leg reduce directly to the reflectional symmetries of the elementary Grundy functions `spider_rho_star` and `spider_rho`. For general configurations, every move in the reversed position produces the same Grundy value as the corresponding move in the original position, so the lists of reachable options are permutations of each other. Because the minimal excluded value (`nat_mex_list`) is invariant under list permutations, the Grundy values of the original and reversed positions coincide.
`spider_rho_star` is invariant under reversing the leg end orientation.
By definition, `spider_rho_star h phi` is `h % 2` when `phi = SpiderLegEnd.free` and `h` otherwise. Because `spider_reverse_leg_end` swaps `inward` and `outward` while fixing `free`, `spider_rho_star` evaluates definitionally to the same quantity in all three cases.
lemma spider_gamma_reversal_rho_star (h : ℕ) (phi : SpiderLegEnd) : spider_rho_star h (spider_reverse_leg_end phi) = spider_rho_star h phi := by cases phi <;> rfl
Reversing leg ends preserves the XOR sum of `spider_rho_star` folded over any leg list.
By induction on the leg list `L`. The empty list is trivial. For `head :: tail`, we unfold `List.foldl_cons` on both sides and substitute `spider_gamma_reversal_rho_star` on `head`, ensuring that the accumulators match before invoking the induction hypothesis on `tail`.
uses
List.foldl_cons,spider_gamma_reversal_rho_starlemma spider_gamma_reversal_free_foldl (L : List (ℕ × SpiderLegEnd)) (acc : ℕ) : List.foldl (fun acc p => acc ^^^ spider_rho_star p.1 (spider_reverse_leg_end p.2)) acc L = List.foldl (fun acc p => acc ^^^ spider_rho_star p.1 p.2) acc L := by induction L generalizing acc with | nil => rfl | cons head tail ih => rw [List.foldl_cons, List.foldl_cons, spider_gamma_reversal_rho_star] exact ih _
Reversing leg ends is an injective involution that preserves distinctness and non-freeness. automation
Injectivity (`spider_gamma_reversal_leg_end_inj`) is verified by exhausting all 9 constructor pairs for `(a, b)` with `decide`. Rewriting by `not_iff_not` shows that reversal preserves distinctness (`spider_gamma_reversal_leg_end_ne`), and case analysis with simplification proves that an orientation is not `free` if and only if its reversal is not `free` (`spider_gamma_reversal_leg_end_ne_free`).
uses
not_iff_not,spider_gamma_reversal_leg_end_injlemma spider_gamma_reversal_leg_end_inj (a b : SpiderLegEnd) : spider_reverse_leg_end a = spider_reverse_leg_end b ↔ a = b := by constructor · intro h; cases a <;> cases b <;> revert h <;> decide · intro h; rw [h] lemma spider_gamma_reversal_leg_end_ne (a b : SpiderLegEnd) : spider_reverse_leg_end a ≠ spider_reverse_leg_end b ↔ a ≠ b := by rw [not_iff_not, spider_gamma_reversal_leg_end_inj] lemma spider_gamma_reversal_leg_end_ne_free (x : SpiderLegEnd) : spider_reverse_leg_end x ≠ SpiderLegEnd.free ↔ x ≠ SpiderLegEnd.free := by cases x <;> simp [spider_reverse_leg_end]
`spider_rho` is invariant under simultaneously reversing both leg endpoints.
The value `spider_rho h delta phi` depends only on whether `phi` is `free`, and if not, whether `delta` and `phi` share the same orientation. Since `spider_reverse_leg_end` is a bijection, `delta = phi` holds if and only if their reversals are equal, so case exhaustion over all 9 pairs evaluates definitionally to the same result.
lemma spider_gamma_reversal_rho (h : ℕ) (delta phi : SpiderLegEnd) : spider_rho h (spider_reverse_leg_end delta) (spider_reverse_leg_end phi) = spider_rho h delta phi := by cases delta <;> cases phi <;> rfl
Updating the centre status commutes with reversing orientations.
Exhaustive case analysis on the 4 centre statuses and 3 leg end orientations confirms definitionally that updating a reversed centre with a reversed leg end yields the reversal of the original updated centre.
lemma spider_gamma_reversal_update_centre (s : CentreStatus) (delta : SpiderLegEnd) : spider_update_centre (spider_reverse_centre_status s) (spider_reverse_leg_end delta) = spider_reverse_centre_status (spider_update_centre s delta) := by cases s <;> cases delta <;> rfl
Under the induction hypothesis on fuel, each transition option in the reversed position produces the same outcome as in the original position.
We rewrite the move conditions and weights using `spider_gamma_reversal_leg_end_ne_free`, `spider_gamma_reversal_leg_end_ne`, and `spider_gamma_reversal_rho`. Splitting on the case conditions, an illegal move returns `none` on both sides. If the remaining leg length satisfies `j ≥ 2`, the move creates a new shortened leg, and the induction hypothesis `ih` applies to `(j - 1, delta) :: rest`. If `j < 2`, the leg merges into the centre, and rewriting by `spider_gamma_reversal_update_centre` allows `ih` to match the two options.
uses
spider_gamma_reversal_leg_end_ne,spider_gamma_reversal_leg_end_ne_free,spider_gamma_reversal_rho,spider_gamma_reversal_update_centretheorem spider_gamma_reversal_filterMap_option_eq (fuel : ℕ) (ih : ∀ (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)), spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))) (s : CentreStatus) (rest : List (ℕ × SpiderLegEnd)) (h j : ℕ) (phi delta : SpiderLegEnd) : (if (j == h) = true ∧ spider_reverse_leg_end phi ≠ SpiderLegEnd.free ∧ spider_reverse_leg_end delta ≠ spider_reverse_leg_end phi then Option.none else have d := spider_rho (h - j) (spider_reverse_leg_end delta) (spider_reverse_leg_end phi); if j ≥ 2 then have new_L := (j - 1, spider_reverse_leg_end delta) :: rest.map (fun p => (p.1, spider_reverse_leg_end p.2)); some (d ^^^ spider_gamma fuel (spider_reverse_centre_status s) new_L) else have new_s := spider_update_centre (spider_reverse_centre_status s) (spider_reverse_leg_end delta); some (d ^^^ spider_gamma fuel new_s (rest.map (fun p => (p.1, spider_reverse_leg_end p.2))))) = (if (j == h) = true ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then Option.none else have d := spider_rho (h - j) delta phi; if j ≥ 2 then have new_L := (j - 1, delta) :: rest; some (d ^^^ spider_gamma fuel s new_L) else have new_s := spider_update_centre s delta; some (d ^^^ spider_gamma fuel new_s rest)) := by simp only [spider_gamma_reversal_leg_end_ne_free, spider_gamma_reversal_leg_end_ne, spider_gamma_reversal_rho] split_ifs with hc hj · rfl · rw [ih s ((j - 1, delta) :: rest)] rfl · rw [spider_gamma_reversal_update_centre] rw [ih (spider_update_centre s delta) rest]
Filter-mapping functions related by orientation reversal over `[inward, outward]` produces permuted lists.
Applying `spider_reverse_leg_end` to `[inward, outward]` yields `[outward, inward]`, which is the reverse of `[inward, outward]`. Using `List.filterMap_map` and the relation `G ∘ spider_reverse_leg_end = F`, this simplifies to `([inward, outward].filterMap F).reverse`, which is a permutation of the original by `List.reverse_perm`.
uses
List.filterMap_map,List.filterMap_reverse,List.reverse_permlemma spider_gamma_reversal_filterMap_two_perm (F G : SpiderLegEnd → Option ℕ) (h_rev : ∀ delta, G (spider_reverse_leg_end delta) = F delta) : ([SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap G).Perm ([SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap F) := by have h1 : [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap G = ([SpiderLegEnd.outward, SpiderLegEnd.inward].map spider_reverse_leg_end).filterMap G := by rfl rw [h1, List.filterMap_map] have hcomp : (G ∘ spider_reverse_leg_end) = F := by funext d; exact h_rev d rw [hcomp] have h2 : [SpiderLegEnd.outward, SpiderLegEnd.inward] = [SpiderLegEnd.inward, SpiderLegEnd.outward].reverse := rfl rw [h2, List.filterMap_reverse] exact List.reverse_perm _
The list of all move options available in the reversed state is a permutation of the options in the original state.
We unfold `spider_gamma_reversal_options`. Mapping reversal over `L` commutes with indexing by `List.zipIdx_map`. Using `List.Perm.flatMap_left`, we distribute the permutation across all legs, commute leg deletion with `List.eraseIdx_map`, distribute across all cut points `j`, and finally apply `spider_gamma_reversal_filterMap_two_perm` combined with `spider_gamma_reversal_filterMap_option_eq` to show that the options generated for `delta ∈ [inward, outward]` are permuted.
uses
List.eraseIdx_map,List.flatMap_map,List.Perm.flatMap_left,List.zipIdx_map,spider_gamma_reversal_filterMap_option_eq,spider_gamma_reversal_filterMap_two_permdef spider_gamma_reversal_options (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : List ℕ := List.flatMap (fun x => match x with | ((h, phi), idx) => have rest := L.eraseIdx idx; List.flatMap (fun j_zero => have j := j_zero + 1; List.filterMap (fun delta => if (j == h) = true ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then Option.none else have d := spider_rho (h - j) delta phi; if j ≥ 2 then have new_L := (j - 1, delta) :: rest; some (d ^^^ spider_gamma fuel s new_L) else have new_s := spider_update_centre s delta; some (d ^^^ spider_gamma fuel new_s rest)) [SpiderLegEnd.inward, SpiderLegEnd.outward]) (List.range h)) L.zipIdx lemma spider_gamma_reversal_options_perm (fuel : ℕ) (ih : ∀ (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)), spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : (spider_gamma_reversal_options fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))).Perm (spider_gamma_reversal_options fuel s L) := by unfold spider_gamma_reversal_options have hzip : (L.map (fun p => (p.1, spider_reverse_leg_end p.2))).zipIdx = L.zipIdx.map (fun ((h, phi), idx) => ((h, spider_reverse_leg_end phi), idx)) := by rw [List.zipIdx_map] rfl rw [hzip, List.flatMap_map] apply List.Perm.flatMap_left intro ⟨⟨h, phi⟩, idx⟩ hmem dsimp only rw [List.eraseIdx_map] apply List.Perm.flatMap_left intro j_zero hjmem apply spider_gamma_reversal_filterMap_two_perm intro delta exact spider_gamma_reversal_filterMap_option_eq fuel ih s (L.eraseIdx idx) h (j_zero + 1) phi delta
The minimal excluded value function `nat_mex_list` is invariant under list permutation. automation
First, induction on fuel in `spider_gamma_reversal_nat_mex_list_loop_congr` shows that the loop evaluating the mex depends only on list membership `x ∈ l`. Since a permutation preserves both length (`h.length_eq`) and element membership (`h.mem_iff`), `nat_mex_list` computes the exact same value on `l1` and `l2`.
uses
nat_mex_list.loop.eq_def,spider_gamma_reversal_nat_mex_list_loop_congrlemma spider_gamma_reversal_nat_mex_list_loop_congr {l1 l2 : List ℕ} (hmem : ∀ x, x ∈ l1 ↔ x ∈ l2) (fuel : ℕ) (n : ℕ) : nat_mex_list.loop l1 n fuel = nat_mex_list.loop l2 n fuel := by induction fuel generalizing n with | zero => rw [nat_mex_list.loop.eq_def, nat_mex_list.loop.eq_def] | succ fuel ih => rw [nat_mex_list.loop.eq_def, nat_mex_list.loop.eq_def] by_cases hn : n ∈ l1 · have hn2 : n ∈ l2 := (hmem n).mp hn simp [hn, hn2, ih] · have hn2 : n ∉ l2 := fun h => hn ((hmem n).mpr h) simp [hn, hn2] lemma spider_gamma_reversal_nat_mex_list_eq_of_perm {l1 l2 : List ℕ} (h : l1.Perm l2) : nat_mex_list l1 = nat_mex_list l2 := by unfold nat_mex_list rw [h.length_eq] exact spider_gamma_reversal_nat_mex_list_loop_congr (fun _ => h.mem_iff) (l2.length + 1) 0
The inductive step for `spider_gamma` holds for fuel + 1.
We unfold `spider_gamma` via `spider_gamma.eq_def` and case-split on `s`: when `s` is `none`, `incoming`, or `outgoing`, positions with at most one leg simplify by definition or by `spider_gamma_reversal_rho`, while positions with at least two legs match because their options are permutations (`spider_gamma_reversal_options_perm`) and mex is permutation-invariant (`spider_gamma_reversal_nat_mex_list_eq_of_perm`). When `s = free`, the value is an XOR sum over `L`, which is invariant by `List.foldl_map` and `spider_gamma_reversal_free_foldl`.
uses
List.foldl_map,spider_gamma.eq_def,spider_gamma_reversal_free_foldl,spider_gamma_reversal_nat_mex_list_eq_of_perm,spider_gamma_reversal_options_perm,spider_gamma_reversal_rhotheorem spider_gamma_reversal_step (fuel : ℕ) (ih : ∀ (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)), spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : spider_gamma (fuel + 1) s L = spider_gamma (fuel + 1) (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2))) := by cases s · cases L with | nil => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p1 tl => cases tl with | nil => rcases p1 with ⟨h, phi⟩ rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p2 rest => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] exact (spider_gamma_reversal_nat_mex_list_eq_of_perm (spider_gamma_reversal_options_perm fuel ih CentreStatus.none (p1 :: p2 :: rest))).symm · cases L with | nil => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p1 tl => cases tl with | nil => rcases p1 with ⟨h, phi⟩ rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] have := (spider_gamma_reversal_rho h SpiderLegEnd.outward phi).symm exact this | cons p2 rest => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] exact (spider_gamma_reversal_nat_mex_list_eq_of_perm (spider_gamma_reversal_options_perm fuel ih CentreStatus.incoming (p1 :: p2 :: rest))).symm · cases L with | nil => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p1 tl => cases tl with | nil => rcases p1 with ⟨h, phi⟩ rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] have := (spider_gamma_reversal_rho h SpiderLegEnd.inward phi).symm exact this | cons p2 rest => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] exact (spider_gamma_reversal_nat_mex_list_eq_of_perm (spider_gamma_reversal_options_perm fuel ih CentreStatus.outgoing (p1 :: p2 :: rest))).symm · rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp [spider_reverse_centre_status] rw [List.foldl_map] exact (spider_gamma_reversal_free_foldl L 0).symm
The reversal theorem `spider_gamma_reversal` holds for all fuel, centre statuses, and leg lists.
By induction on `fuel`. When `fuel = 0`, both sides vanish by `spider_gamma.eq_1`. In the inductive step `fuel + 1`, we directly apply `spider_gamma_reversal_step` with the induction hypothesis `ih`.
uses
spider_gamma.eq_1,spider_gamma_reversal_step/-- Reversing the centre status and every far end leaves the Grundy value unchanged (paper Lemma 8.3). -/ theorem spider_gamma_reversal (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2))) := by induction fuel generalizing s L with | zero => rw [spider_gamma.eq_1, spider_gamma.eq_1] | succ fuel ih => exact spider_gamma_reversal_step fuel ih s L
List.foldl_cons- Folding over `a :: l` with accumulator `b` evaluates to folding over `l` with updated accumulator `f b a`.
List.foldl_map- Folding over a mapped list equals folding the composed operation over the original list.
List.filterMap_map- Applying `filterMap g` to a mapped list `List.map f l` equals `List.filterMap (g ∘ f) l`.
List.filterMap_reverse- Filter-mapping over a reversed list yields the reverse of the filter-mapped list.
List.reverse_perm- Any list is a permutation of its list reversal.
List.zipIdx_map- Zipping indices into a mapped list is equivalent to mapping the element transformation over the zipped original list.
List.flatMap_map- Flat-mapping `g` over `List.map f l` equals flat-mapping `g ∘ f` over `l`.
List.Perm.flatMap_left- If `f a` is a permutation of `g a` for each `a ∈ l`, then flat-mapping `f` over `l` is a permutation of flat-mapping `g` over `l`.
List.eraseIdx_map- Erasing the element at index `n` commutes with mapping a function over the list.
nat_mex_list.loop.eq_def- The defining recurrence of `nat_mex_list.loop`, checking membership at each candidate natural number.
not_iff_not- Two propositions are equivalent if and only if their negations are equivalent.
spider_gamma.eq_1- With zero fuel, `spider_gamma` evaluates to 0.
spider_gamma.eq_def- The defining equation of `spider_gamma`, unfolding its evaluation by cases on fuel, centre status, and leg configuration.
spider_gamma_reversal_free_foldl- When the centre is free, reversing leg ends preserves the XOR sum of `spider_rho_star` values.
spider_gamma_reversal_filterMap_option_eq- Assuming the reversal induction hypothesis for lower fuel, each individual move option under reversed parameters produces the exact same Grundy value as the original move.
spider_gamma_reversal_filterMap_two_perm- If a function on reversed leg ends agrees with another function, filtering and mapping them over `[inward, outward]` produces mutually permuted lists.
spider_gamma_reversal_leg_end_inj- Reversing a leg end orientation is an injective operation.
spider_gamma_reversal_leg_end_ne- Two leg ends are distinct if and only if their reversals are distinct.
spider_gamma_reversal_leg_end_ne_free- A leg end is not `free` if and only if its reversal is not `free`.
spider_gamma_reversal_nat_mex_list_loop_congr- The search loop for the minimal excluded value depends only on the elements present in the list, not their order.
spider_gamma_reversal_nat_mex_list_eq_of_perm- Two lists that are permutations of each other have the same minimal excluded value (`nat_mex_list`).
spider_gamma_reversal_options_perm- The list of all legal move options from the reversed state is a permutation of the options from the original state.
spider_gamma_reversal_rho- The atomic Grundy function `spider_rho` is invariant under reversing both endpoints simultaneously.
spider_gamma_reversal_rho_star- The detached leg Grundy function `spider_rho_star` is invariant under reversing the leg's end orientation.
spider_gamma_reversal_step- If `spider_gamma` is invariant under reversal at fuel `n`, it is also invariant under reversal at fuel `n + 1`.
spider_gamma_reversal_update_centre- Updating a reversed centre status by a reversed leg end gives the reversal of the updated centre status.
- The parameter `fuel` is an artifact of the formalization to ensure well-founded recursion for `spider_gamma`; in classical game theory, termination is guaranteed by the finite depth of the game tree.
- Step 3 uses the `decide` tactic to exhaustively verify all pairs of `SpiderLegEnd` constructors by boolean computation.
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_reversal_rho_star (h : ℕ) (phi : SpiderLegEnd) : spider_rho_star h (spider_reverse_leg_end phi) = spider_rho_star h phi := by cases phi <;> rfllemma spider_gamma_reversal_free_foldl (L : List (ℕ × SpiderLegEnd)) (acc : ℕ) : List.foldl (fun acc p => acc ^^^ spider_rho_star p.1 (spider_reverse_leg_end p.2)) acc L = List.foldl (fun acc p => acc ^^^ spider_rho_star p.1 p.2) acc L := by induction L generalizing acc with | nil => rfl | cons head tail ih => rw [List.foldl_cons, List.foldl_cons, spider_gamma_reversal_rho_star] exact ih _lemma spider_gamma_reversal_leg_end_inj (a b : SpiderLegEnd) : spider_reverse_leg_end a = spider_reverse_leg_end b ↔ a = b := by constructor · intro h; cases a <;> cases b <;> revert h <;> decide · intro h; rw [h]lemma spider_gamma_reversal_leg_end_ne (a b : SpiderLegEnd) : spider_reverse_leg_end a ≠ spider_reverse_leg_end b ↔ a ≠ b := by rw [not_iff_not, spider_gamma_reversal_leg_end_inj]lemma spider_gamma_reversal_leg_end_ne_free (x : SpiderLegEnd) : spider_reverse_leg_end x ≠ SpiderLegEnd.free ↔ x ≠ SpiderLegEnd.free := by cases x <;> simp [spider_reverse_leg_end]lemma spider_gamma_reversal_rho (h : ℕ) (delta phi : SpiderLegEnd) : spider_rho h (spider_reverse_leg_end delta) (spider_reverse_leg_end phi) = spider_rho h delta phi := by cases delta <;> cases phi <;> rfllemma spider_gamma_reversal_update_centre (s : CentreStatus) (delta : SpiderLegEnd) : spider_update_centre (spider_reverse_centre_status s) (spider_reverse_leg_end delta) = spider_reverse_centre_status (spider_update_centre s delta) := by cases s <;> cases delta <;> rfltheorem spider_gamma_reversal_filterMap_option_eq (fuel : ℕ) (ih : ∀ (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)), spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))) (s : CentreStatus) (rest : List (ℕ × SpiderLegEnd)) (h j : ℕ) (phi delta : SpiderLegEnd) : (if (j == h) = true ∧ spider_reverse_leg_end phi ≠ SpiderLegEnd.free ∧ spider_reverse_leg_end delta ≠ spider_reverse_leg_end phi then Option.none else have d := spider_rho (h - j) (spider_reverse_leg_end delta) (spider_reverse_leg_end phi); if j ≥ 2 then have new_L := (j - 1, spider_reverse_leg_end delta) :: rest.map (fun p => (p.1, spider_reverse_leg_end p.2)); some (d ^^^ spider_gamma fuel (spider_reverse_centre_status s) new_L) else have new_s := spider_update_centre (spider_reverse_centre_status s) (spider_reverse_leg_end delta); some (d ^^^ spider_gamma fuel new_s (rest.map (fun p => (p.1, spider_reverse_leg_end p.2))))) = (if (j == h) = true ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then Option.none else have d := spider_rho (h - j) delta phi; if j ≥ 2 then have new_L := (j - 1, delta) :: rest; some (d ^^^ spider_gamma fuel s new_L) else have new_s := spider_update_centre s delta; some (d ^^^ spider_gamma fuel new_s rest)) := by simp only [spider_gamma_reversal_leg_end_ne_free, spider_gamma_reversal_leg_end_ne, spider_gamma_reversal_rho] split_ifs with hc hj · rfl · rw [ih s ((j - 1, delta) :: rest)] rfl · rw [spider_gamma_reversal_update_centre] rw [ih (spider_update_centre s delta) rest]lemma spider_gamma_reversal_filterMap_two_perm (F G : SpiderLegEnd → Option ℕ) (h_rev : ∀ delta, G (spider_reverse_leg_end delta) = F delta) : ([SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap G).Perm ([SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap F) := by have h1 : [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap G = ([SpiderLegEnd.outward, SpiderLegEnd.inward].map spider_reverse_leg_end).filterMap G := by rfl rw [h1, List.filterMap_map] have hcomp : (G ∘ spider_reverse_leg_end) = F := by funext d; exact h_rev d rw [hcomp] have h2 : [SpiderLegEnd.outward, SpiderLegEnd.inward] = [SpiderLegEnd.inward, SpiderLegEnd.outward].reverse := rfl rw [h2, List.filterMap_reverse] exact List.reverse_perm _def spider_gamma_reversal_options (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : List ℕ := List.flatMap (fun x => match x with | ((h, phi), idx) => have rest := L.eraseIdx idx; List.flatMap (fun j_zero => have j := j_zero + 1; List.filterMap (fun delta => if (j == h) = true ∧ phi ≠ SpiderLegEnd.free ∧ delta ≠ phi then Option.none else have d := spider_rho (h - j) delta phi; if j ≥ 2 then have new_L := (j - 1, delta) :: rest; some (d ^^^ spider_gamma fuel s new_L) else have new_s := spider_update_centre s delta; some (d ^^^ spider_gamma fuel new_s rest)) [SpiderLegEnd.inward, SpiderLegEnd.outward]) (List.range h)) L.zipIdxlemma spider_gamma_reversal_options_perm (fuel : ℕ) (ih : ∀ (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)), spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : (spider_gamma_reversal_options fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))).Perm (spider_gamma_reversal_options fuel s L) := by unfold spider_gamma_reversal_options have hzip : (L.map (fun p => (p.1, spider_reverse_leg_end p.2))).zipIdx = L.zipIdx.map (fun ((h, phi), idx) => ((h, spider_reverse_leg_end phi), idx)) := by rw [List.zipIdx_map] rfl rw [hzip, List.flatMap_map] apply List.Perm.flatMap_left intro ⟨⟨h, phi⟩, idx⟩ hmem dsimp only rw [List.eraseIdx_map] apply List.Perm.flatMap_left intro j_zero hjmem apply spider_gamma_reversal_filterMap_two_perm intro delta exact spider_gamma_reversal_filterMap_option_eq fuel ih s (L.eraseIdx idx) h (j_zero + 1) phi deltalemma spider_gamma_reversal_nat_mex_list_loop_congr {l1 l2 : List ℕ} (hmem : ∀ x, x ∈ l1 ↔ x ∈ l2) (fuel : ℕ) (n : ℕ) : nat_mex_list.loop l1 n fuel = nat_mex_list.loop l2 n fuel := by induction fuel generalizing n with | zero => rw [nat_mex_list.loop.eq_def, nat_mex_list.loop.eq_def] | succ fuel ih => rw [nat_mex_list.loop.eq_def, nat_mex_list.loop.eq_def] by_cases hn : n ∈ l1 · have hn2 : n ∈ l2 := (hmem n).mp hn simp [hn, hn2, ih] · have hn2 : n ∉ l2 := fun h => hn ((hmem n).mpr h) simp [hn, hn2]lemma spider_gamma_reversal_nat_mex_list_eq_of_perm {l1 l2 : List ℕ} (h : l1.Perm l2) : nat_mex_list l1 = nat_mex_list l2 := by unfold nat_mex_list rw [h.length_eq] exact spider_gamma_reversal_nat_mex_list_loop_congr (fun _ => h.mem_iff) (l2.length + 1) 0theorem spider_gamma_reversal_step (fuel : ℕ) (ih : ∀ (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)), spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2)))) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : spider_gamma (fuel + 1) s L = spider_gamma (fuel + 1) (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2))) := by cases s · cases L with | nil => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p1 tl => cases tl with | nil => rcases p1 with ⟨h, phi⟩ rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p2 rest => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] exact (spider_gamma_reversal_nat_mex_list_eq_of_perm (spider_gamma_reversal_options_perm fuel ih CentreStatus.none (p1 :: p2 :: rest))).symm · cases L with | nil => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p1 tl => cases tl with | nil => rcases p1 with ⟨h, phi⟩ rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] have := (spider_gamma_reversal_rho h SpiderLegEnd.outward phi).symm exact this | cons p2 rest => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] exact (spider_gamma_reversal_nat_mex_list_eq_of_perm (spider_gamma_reversal_options_perm fuel ih CentreStatus.incoming (p1 :: p2 :: rest))).symm · cases L with | nil => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def]; rfl | cons p1 tl => cases tl with | nil => rcases p1 with ⟨h, phi⟩ rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] have := (spider_gamma_reversal_rho h SpiderLegEnd.inward phi).symm exact this | cons p2 rest => rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp only [spider_reverse_centre_status] exact (spider_gamma_reversal_nat_mex_list_eq_of_perm (spider_gamma_reversal_options_perm fuel ih CentreStatus.outgoing (p1 :: p2 :: rest))).symm · rw [spider_gamma.eq_def]; rw [spider_gamma.eq_def] dsimp [spider_reverse_centre_status] rw [List.foldl_map] exact (spider_gamma_reversal_free_foldl L 0).symm/-- Reversing the centre status and every far end leaves the Grundy value unchanged (paper Lemma 8.3). -/theorem spider_gamma_reversal (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : spider_gamma fuel s L = spider_gamma fuel (spider_reverse_centre_status s) (L.map (fun p => (p.1, spider_reverse_leg_end p.2))) := by induction fuel generalizing s L with | zero => rw [spider_gamma.eq_1, spider_gamma.eq_1] | succ fuel ih => exact spider_gamma_reversal_step fuel ih s L