AFTD Auto-Formalizing Theoretical Domains

spider_gamma_reversal

theoremverified

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

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.

  1. `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.

    lines 1–4

    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
    
  2. 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`.

    lines 5–13

    uses List.foldl_cons, spider_gamma_reversal_rho_star

    lemma 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 _
    
  3. 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`).

    lines 14–27

    uses not_iff_not, spider_gamma_reversal_leg_end_inj

    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]
    
  4. `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.

    lines 28–31

    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
    
  5. 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.

    lines 32–36

    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
    
  6. 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.

    lines 37–70

    uses spider_gamma_reversal_leg_end_ne, spider_gamma_reversal_leg_end_ne_free, spider_gamma_reversal_rho, spider_gamma_reversal_update_centre

    theorem 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]
    
  7. 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`.

    lines 71–84

    uses List.filterMap_map, List.filterMap_reverse, List.reverse_perm

    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 _
    
  8. 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.

    lines 85–132

    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_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.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
    
  9. 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`.

    lines 133–151

    uses nat_mex_list.loop.eq_def, spider_gamma_reversal_nat_mex_list_loop_congr

    lemma 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
    
  10. 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`.

    lines 152–207

    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_rho

    theorem 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
    
  11. 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`.

    lines 208–217

    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.

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

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