AFTD Auto-Formalizing Theoretical Domains

spider_gamma

def

The function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider legs L : List (ℕ × SpiderLegEnd). It is defined by recursion on fuel: if fuel = 0, it returns 0. If fuel = fuel' + 1: if s = CentreStatus.free, it returns the bitwise XOR sum starting from 0 of spider_rho_star h phi for each (h, phi) in L. Otherwise, if L is empty, it returns 0; if L is a singleton [(h, phi)], it returns spider_rho h SpiderLegEnd.outward phi if s = CentreStatus.incoming, spider_rho h SpiderLegEnd.inward phi if s = CentreStatus.outgoing, and 0 if s = CentreStatus.none; if L has at least two elements, it returns nat_mex_list of options collected over each leg (h, phi) at index idx in L, with rest = L.eraseIdx idx, each integer j from 1 to h, and each direction delta in {SpiderLegEnd.inward, SpiderLegEnd.outward}: skipping when j = h, phi ≠ SpiderLegEnd.free, and delta ≠ phi; otherwise letting d = spider_rho (h - j) delta phi and taking d ^^^ spider_gamma fuel' s ((j - 1, delta) :: rest) if j ≥ 2, and d ^^^ spider_gamma fuel' (spider_update_centre s delta) rest if j = 1.

Statement

def spider_gamma (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : ℕ
Defined in
scout/2610-15145-nim-heaps-in-the-game-of-cycles-the-parity-conjecture-fails.md, Proposition 6.1
Verified
18 Oct 2026
Axioms
none listed
Built on 6
  • 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.
  • spider_update_centreThe function spider_update_centre updates centre status s given leg transition delta: if delta is inward, none maps to incoming, incoming…
  • 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…
Used by 41

Read back from the Lean

The definition spider_gamma computes a natural number recursively using a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider legs L : List (ℕ × SpiderLegEnd). The computation proceeds by matching on fuel: 1. If fuel = 0, it returns 0. 2. If fuel = fuel' + 1: - If s = .free, it returns the bitwise XOR sum (nim-sum) over all pairs (h, phi) ∈ L of spider_rho_star h phi, initialized at 0. - If s ≠ .free (i.e., s is none, incoming, or outgoing): - If L is empty ([]), it returns 0. - If L is a singleton [(h, phi)]: - If s = .incoming, it returns spider_rho h .outward phi. - If s = .outgoing, it returns spider_rho h .inward phi. - If s = .none, it returns 0. - If L contains at least two elements: It constructs a list options : List ℕ by iterating over each leg (h, phi) in L at 0-based index idx: - Let rest be L with the element at idx removed. - For each integer j from 1 to h (inclusive): - For each direction delta ∈ [.inward, .outward]: - If j = h, phi ≠ .free, and delta ≠ phi, this transition is omitted (none). - Otherwise, let d = spider_rho (h - j) delta phi: - If j ≥ 2, it appends d ^^^ spider_gamma fuel' s ((j - 1, delta) :: rest) to the options. - If j < 2 (i.e., j = 1), it appends d ^^^ spider_gamma fuel' (spider_update_centre s delta) rest to the options. Finally, it returns nat_mex_list options, the minimal excludant (mex) of options.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Grundy value Γ(s; L) of a spider state with centre status s and attached legs L. -/
def spider_gamma (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd)) : ℕ :=
  match fuel with
  | 0 => 0
  | fuel + 1 =>
    match s with
    | .free => L.foldl (fun acc p => acc ^^^ spider_rho_star p.1 p.2) 0
    | _ =>
      match L with
      | [] => 0
      | [(h, phi)] =>
        match s with
        | .incoming => spider_rho h .outward phi
        | .outgoing => spider_rho h .inward phi
        | _ => 0
      | _ =>
        let options : List ℕ :=
          L.zipIdx.flatMap (fun ⟨⟨h, phi⟩, idx⟩ =>
            let rest := L.eraseIdx idx
            (List.range h).flatMap (fun j_zero =>
              let j := j_zero + 1
              [SpiderLegEnd.inward, SpiderLegEnd.outward].filterMap (fun delta =>
                if j == h ∧ phi ≠ .free ∧ delta ≠ phi then none
                else
                  let d := spider_rho (h - j) delta phi
                  if j ≥ 2 then
                    let new_L := (j - 1, delta) :: rest
                    some (d ^^^ spider_gamma fuel s new_L)
                  else
                    let new_s := spider_update_centre s delta
                    some (d ^^^ spider_gamma fuel new_s rest)
              )
            )
          )
        nat_mex_list options
See it in the graphDiscuss this resultChallenge it