AFTD Auto-Formalizing Theoretical Domains

spider_gamma_swap_two

theoremverified

The Grundy value of a two-legged spider state is invariant under swapping the two legs in the list.

Statement

theorem spider_gamma_swap_two (fuel : ℕ) (s : CentreStatus) (A B : ℕ × SpiderLegEnd) :
    spider_gamma fuel s [A, B] = spider_gamma fuel s [B, A]
Source
step towards spider_blocked_incoming_one_inward
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
  • nat_mex_list_append_commFor any two lists of natural numbers l1 and l2, nat_mex_list (l1 ++ l2) = nat_mex_list (l2 ++ l1).
  • 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.
  • 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_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…
Used by 2

The proof, explained

The Grundy value of a two-legged spider state is shown to be symmetric in the two legs by case analysis on the recursion fuel and the centre status. When the centre is free, the Grundy value is the XOR sum of the two legs' individual values, which is symmetric by the commutativity of bitwise XOR. When the centre is not free, the Grundy value is the mex of all moves available from either leg; swapping the legs simply swaps the two blocks of moves in the concatenated options list, leaving the overall mex unchanged.

  1. The Grundy value is invariant under swapping the two legs when fuel = 0.

    When the recursion fuel is 0, `spider_gamma` evaluates to 0 by definition regardless of the list of legs, so both sides are definitionally equal to 0 and the goal is solved by reflexivity (`rfl`).

    lines 4–5

      cases fuel with
      | zero => rfl
  2. When fuel = f + 1 and the centre status is free, swapping the two legs does not change the Grundy value.

    For a free centre, `spider_gamma` computes the XOR sum of `spider_rho_star` over the leg list, initialized with 0. Simplifying both sides gives 0 ^^^ ρ*(A) ^^^ ρ*(B) on the left and 0 ^^^ ρ*(B) ^^^ ρ*(A) on the right. Removing the leading zero with `Nat.zero_xor` reduces this to ρ*(A) ^^^ ρ*(B) = ρ*(B) ^^^ ρ*(A), which holds by commutativity of XOR (`Nat.xor_comm`).

    lines 6–10

    uses Nat.zero_xor, Nat.xor_comm

      | succ f =>
        cases s with
        | free =>
          dsimp [spider_gamma]
          rw [Nat.zero_xor, Nat.zero_xor, Nat.xor_comm]
  3. When fuel = f + 1 and the centre status is not free, swapping the two legs does not change the Grundy value.

    When the centre status is not free (covering `none`, `incoming`, and `outgoing`), `spider_gamma` computes the mex (`nat_mex_list`) of the combined moves available from each leg. Expanding the flat-map over the list of legs and evaluating index erasure splits the options for [A, B] into the moves on A concatenated with the moves on B, whereas for [B, A] they appear as moves on B concatenated with moves on A. Commuting the two sublists under `nat_mex_list` via `nat_mex_list_append_comm` establishes equality.

    lines 11–15

    uses List.flatMap_cons, List.flatMap_nil, List.append_nil, nat_mex_list_append_comm

        | _ =>
          dsimp [spider_gamma]
          simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil]
          dsimp [List.eraseIdx]
          rw [nat_mex_list_append_comm]
Nat.zero_xor
Bitwise exclusive-or of zero with any natural number x yields x (0 ^^^ x = x).
Nat.xor_comm
Bitwise exclusive-or on natural numbers is commutative (x ^^^ y = y ^^^ x).
List.flatMap_cons
Flat-mapping a function over a non-empty list x :: xs equals the result of the function on x concatenated with the flat-map over the tail xs.
List.flatMap_nil
Flat-mapping any function over the empty list yields the empty list.
List.append_nil
Appending the empty list to any list leaves the list unchanged (as ++ [] = as).
nat_mex_list_append_comm
The minimum excluded value (mex) of the concatenation of two lists of natural numbers is independent of the concatenation order: mex(l1 ++ l2) = mex(l2 ++ l1).

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

/-- The Grundy value of a two-legged spider state is invariant under swapping the two legs in the list. -/theorem spider_gamma_swap_two (fuel : ℕ) (s : CentreStatus) (A B : ℕ × SpiderLegEnd) :    spider_gamma fuel s [A, B] = spider_gamma fuel s [B, A] := by  cases fuel with  | zero => rfl  | succ f =>    cases s with    | free =>      dsimp [spider_gamma]      rw [Nat.zero_xor, Nat.zero_xor, Nat.xor_comm]    | _ =>      dsimp [spider_gamma]      simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil]      dsimp [List.eraseIdx]      rw [nat_mex_list_append_comm]
See it in the graphDiscuss this resultChallenge it