spider_gamma_rotate_three_short_legs
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
- 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_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_none_one_inward_one_outward_raw_opts_eqFor r ≥ 2 and φ ≠ free, the value of (none;{(1,inward),(1,outward),(r,φ)}) at fuel r+3 is the mex of the raw option list…
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.
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`).
cases fuel with | zero => rfl
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.
uses
Nat.zero_xor| succ f => cases s with | free => dsimp [spider_gamma] rw [Nat.zero_xor, Nat.zero_xor] ac_rflFor 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$.
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]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.
uses
nat_mex_list_append_comm,List.append_assocrw [nat_mex_list_append_comm, List.append_assoc]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.
uses
spider_gamma_swap_twocongr 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].
- The parameter `fuel : ℕ` is an artifact of formalization in Lean, used as a recursion termination fuel for `spider_gamma`, with no counterpart in the mathematical definition of the game.
- The three non-free centre statuses (`none`, `incoming`, and `outgoing`) are handled simultaneously by a single match arm (`| none | incoming | outgoing =>`) because their game values are computed by the same general mex rule over candidate moves.
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.
/-- 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]