AFTD Auto-Formalizing Theoretical Domains

spider_gamma_rotate_three_short_legs

theoremverified

For 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 the front to the back of the list.

Statement

theorem spider_gamma_rotate_three_short_legs (fuel : ℕ) (s : CentreStatus) (p : ℕ × SpiderLegEnd) :
    spider_gamma fuel s [p, (1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] =
      spider_gamma fuel s [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), p]
Source
step towards spider_blocked_none_one_inward_one_outward
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
  • spider_gamma_swap_twoThe Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.
  • nat_mex_list_append_commFor any two lists of natural numbers l1 and l2, nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
  • nat_mex_listThe minimum excluded value (mex) of a finite list of natural numbers is the least non-negative integer not in the list.
  • 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_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
  • 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…
  • spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
Used by 3

The proof, explained

The theorem is proved by case analysis on the recursion fuel and the centre status. When fuel is zero, both sides vanish definitionally. When the centre is free, the value is a bitwise XOR sum of the legs, which is invariant under rotating the list because XOR is associative and commutative. For any non-free centre status, the value is the mex of all leg reductions; commutativity of mex list concatenation reorders the options from the left-hand side to match the right-hand side, and the two-leg symmetry lemma (`spider_gamma_swap_two`) establishes that the corresponding sub-lists of moves are identical.

  1. The identity holds when fuel is zero.

    When fuel is 0, the definition of `spider_gamma` returns 0 regardless of the centre status and the leg list. Both sides are definitionally 0, so the goal holds by reflexivity (`rfl`).

    lines 5–6

      cases fuel with
      | zero => rfl
  2. When fuel is non-zero and the centre status is free, the value is unchanged by moving p to the back.

    When the centre is free, `spider_gamma` unfolds to the cumulative bitwise XOR of `spider_rho_star` across all legs in the list, starting from 0. Rewriting with `Nat.zero_xor` removes the initial 0 from both sides. The resulting expressions are XOR sums of the same three terms in different orders, so associativity and commutativity of XOR (`ac_rfl`) closes the goal.

    lines 7–12

    uses Nat.zero_xor

      | succ f =>
        cases s with
        | free =>
          dsimp [spider_gamma]
          rw [Nat.zero_xor, Nat.zero_xor]
          ac_rfl
  3. For non-free centre statuses, the game values expand into the mex of the legal moves from each leg.

    For the remaining centre statuses (`none`, `incoming`, and `outgoing`), `spider_gamma` evaluates to `nat_mex_list` of all legal reductions. Unfolding `spider_gamma` and simplifying the list operations (`flatMap`, `filterMap`, `range 1`, and index erasures) decomposes the options on the left into moves on $p$, moves on $(1, \text{inward})$, and moves on $(1, \text{outward})$, and on the right into moves on $(1, \text{inward})$, $(1, \text{outward})$, and $p$.

    lines 13–17

    uses List.flatMap_cons, List.flatMap_nil, List.append_nil, List.range_one, List.filterMap_cons, List.filterMap_nil, List.eraseIdx_cons_zero, List.eraseIdx_cons_succ

        | none | incoming | outgoing =>
          dsimp [spider_gamma]
          simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil,
                     List.range_one, List.filterMap_cons, List.filterMap_nil,
                     List.eraseIdx_cons_zero, List.eraseIdx_cons_succ]
  4. The list of move options on the left can be reordered to match the leg order of the right-hand side.

    On the left-hand side, the candidate moves are grouped as $M_p ++ (M_{\text{in}} ++ M_{\text{out}})$. Because `nat_mex_list` is invariant under swapping concatenated lists (`nat_mex_list_append_comm`), this equals the mex of $(M_{\text{in}} ++ M_{\text{out}}) ++ M_p$. Reassociating with `List.append_assoc` produces $M_{\text{in}} ++ (M_{\text{out}} ++ M_p)$, matching the grouping on the right-hand side.

    line 18

    uses nat_mex_list_append_comm, List.append_assoc

          rw [nat_mex_list_append_comm, List.append_assoc]
  5. Each corresponding block of move options is identical, completing the non-free cases.

    Applying congruence (`congr 1`) strips `nat_mex_list` and splits the concatenation into subgoals for each leg. For moves on $(1, \text{inward})$, removing this leg leaves remaining legs $[p, (1, \text{outward})]$ on the left and $[(1, \text{outward}), p]$ on the right; these have identical values by two-leg symmetry (`spider_gamma_swap_two`), which `simp` resolves. Next, `congr 1` splits the remaining list: moves on $(1, \text{outward})$ leave $[p, (1, \text{inward})]$ versus $[(1, \text{inward}), p]$, again solved by `simp [spider_gamma_swap_two]`. Finally, moves on $p$ leave $[(1, \text{inward}), (1, \text{outward})]$ on both sides, which are definitionally equal and discharged automatically.

    lines 19–23

    uses spider_gamma_swap_two

          congr 1
          congr 1
          · simp [spider_gamma_swap_two]
          · congr 1
            · simp [spider_gamma_swap_two]
Nat.zero_xor
XORing 0 with any natural number leaves it unchanged: 0 ^^^ x = x.
List.flatMap_cons
Mapping a list-valued function over a non-empty list and flattening concatenates the image of the head with the flattened tail: flatMap f (x :: xs) = f x ++ flatMap f xs.
List.flatMap_nil
Mapping and flattening over an empty list produces an empty list: flatMap f [] = [].
List.append_nil
Appending the empty list to any list leaves the list unchanged: as ++ [] = as.
List.range_one
The range of length 1 contains only 0: List.range 1 = [0].
List.filterMap_cons
Applying filterMap to a non-empty list applies the function to the head and prepends the result if it is 'some': filterMap f (a :: l) = match f a with | none => filterMap f l | some b => b :: filterMap f l.
List.filterMap_nil
Applying filterMap to an empty list produces an empty list: filterMap f [] = [].
List.eraseIdx_cons_zero
Erasing the element at index 0 of a non-empty list removes its head: (a :: as).eraseIdx 0 = as.
List.eraseIdx_cons_succ
Erasing index i + 1 of a non-empty list preserves the head and erases index i from the tail: (a :: as).eraseIdx (i + 1) = a :: as.eraseIdx i.
nat_mex_list_append_comm
The minimum excluded value (mex) of the concatenation of two lists of natural numbers does not depend on the order of the lists: nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
List.append_assoc
List concatenation is associative: (as ++ bs) ++ cs = as ++ (bs ++ cs).
spider_gamma_swap_two
For a two-leg spider, the game value is invariant under swapping the two legs: spider_gamma fuel s [A, B] = spider_gamma fuel s [B, 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

/-- Moving the front leg of {p,1^in,1^out} to the back leaves the value unchanged. -/theorem spider_gamma_rotate_three_short_legs (fuel : ℕ) (s : CentreStatus) (p : ℕ × SpiderLegEnd) :    spider_gamma fuel s [p, (1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward)] =      spider_gamma fuel s [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.outward), p] := by  cases fuel with  | zero => rfl  | succ f =>    cases s with    | free =>      dsimp [spider_gamma]      rw [Nat.zero_xor, Nat.zero_xor]      ac_rfl    | none | incoming | outgoing =>      dsimp [spider_gamma]      simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil,                 List.range_one, List.filterMap_cons, List.filterMap_nil,                 List.eraseIdx_cons_zero, List.eraseIdx_cons_succ]      rw [nat_mex_list_append_comm, List.append_assoc]      congr 1      congr 1      · simp [spider_gamma_swap_two]      · congr 1        · simp [spider_gamma_swap_two]
See it in the graphDiscuss this resultChallenge it