AFTD Auto-Formalizing Theoretical Domains

spider_gamma_root_options

theoremverified

The option list of the root state S(1,2,z) at fuel N+1 (with z = m+1 and N ≥ 3) is the mex of 8 explicit "head" options together with the long block (List.range m).flatMap over cuts of the leg of length z.

Statement

theorem spider_gamma_root_options (N z m : ℕ) (hz : z = m + 1) (hN : 3 ≤ N) :
    spider_gamma (N + 1) CentreStatus.none
        [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free), (z, SpiderLegEnd.free)] =
      nat_mex_list
        ([ spider_gamma N CentreStatus.incoming [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)],
           spider_gamma N CentreStatus.outgoing [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)],
           1 ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],
           1 ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],
           spider_gamma N CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],
           spider_gamma N CentreStatus.none [(1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],
           m ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)],
           m ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]] ++
         (List.range m).flatMap (fun i =>
           [(z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)],
            (z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]]))
Source
step towards spider_grundy_val_one_two
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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…
  • 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_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…

The proof, explained

The theorem determines the normal form of the option list for the root spider state $S(1,2,z)$ with $z = m + 1$ at fuel $N+1$ by unrolling the definition of `spider_gamma`. The outer loop flatMaps over cuts of the three legs of lengths 1, 2, and $m+1$. Evaluating the cut ranges for the first two legs explicitly and splitting the range of the third leg into a complete cut and partial cuts yields the 8 explicit initial options together with the parameterized family of cuts along the third leg.

  1. Substitute $z = m + 1$ and reduce the equality of Grundy values to equality of their underlying option lists.

    The substitution `hz` replaces $z$ with $m + 1$. Applying congruence (`congr_arg`) with respect to `nat_mex_list` strips the outer minimum excluded value operator, reducing the theorem to showing that the list of options generated by `spider_gamma` equals the right-hand list. (The hypothesis `hN : 3 ≤ N` is recorded on line 17 but not needed for the expansion.)

    lines 17–19

    uses congr_arg

      have _ := hN
      subst hz
      apply congr_arg nat_mex_list
  2. Unfold `spider_gamma` and expand the outer loop over the three legs of the spider.

    By definition, for fuel $N + 1$ and centre status `none`, `spider_gamma` computes options by flatMapping over the indexed legs `[((1, free), 0), ((2, free), 1), ((m + 1, free), 2)]`. Rewriting with `List.flatMap_cons` and `List.flatMap_nil` decomposes this outer loop into the concatenation of three lists of moves—one per leg—and `dsimp only` simplifies pattern matching and index deletions.

    lines 20–23

    uses List.flatMap_cons, List.flatMap_nil

      change
        List.flatMap _ [((1, SpiderLegEnd.free), 0), ((2, SpiderLegEnd.free), 1), ((m + 1, SpiderLegEnd.free), 2)] = _
      rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil]
      dsimp only
  3. Evaluate the cut position ranges for each leg, splitting the third leg's range into the full cut and partial cuts.

    For the leg of length 1, `List.range 1` evaluates definitionally to `[0]`. For the leg of length 2, `List.range 2` evaluates to `[0, 1]`. For the leg of length $m + 1$, `List.range_succ_eq_map` splits `List.range (m + 1)` into `0` (cutting off the entire leg) followed by `List.map Nat.succ (List.range m)` (partial cuts that leave a stub on the spider).

    lines 24–27

    uses List.range_succ_eq_map

      have hr1 : List.range 1 = [0] := rfl
      have hr2 : List.range 2 = [0, 1] := rfl
      rw [hr1, hr2]
      rw [List.range_succ_eq_map (n := m)]
  4. Unroll the cuts for the first two legs and index partial cuts along the third leg directly over `List.range m`.

    Simplifying with `List.flatMap_cons` and `List.flatMap_nil` unrolls the inner loops over cut positions for the explicit lists `[0]` and `[0, 1]`, and `List.append_nil` removes trailing nil appends. Furthermore, `List.flatMap_map` absorbs `Nat.succ` into the cut function, expressing partial cuts along the third leg directly as a `flatMap` over $i \in \text{List.range } m$.

    line 28

    uses List.flatMap_cons, List.flatMap_nil, List.append_nil, List.flatMap_map

      simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil, List.flatMap_map]
  5. The evaluated options match the 8 explicit head options and the parameterized cuts along the third leg. automation

    Simplifying with the definitions of `spider_rho` (the Grundy value of the detached cut segment) and `spider_update_centre` (the updated centre status), along with ground arithmetic, resolves each branch: cuts of length 1 remove the leg entirely and change the centre status to incoming or outgoing, while cuts of length at least 2 retain the centre status and leave a stub of length $j - 1$. The resulting list matches the 8 leading options and the list comprehension along the third leg.

    line 29

      simp [spider_rho, spider_update_centre]
congr_arg
applying a function to equal arguments yields equal results ($a_1 = a_2 \implies f(a_1) = f(a_2)$)
List.flatMap_cons
flatMapping a function over `x :: xs` equals the function applied to `x` concatenated with the flatMap over `xs`
List.flatMap_nil
flatMapping any function over the empty list produces the empty list
List.range_succ_eq_map
the list `List.range (n + 1)` is equal to `0` followed by the elementwise successors of `List.range n`
List.append_nil
appending the empty list to any list leaves it unchanged
List.flatMap_map
mapping $f$ over a list and then flatMapping $g$ is equivalent to flatMapping the composition $g \circ f$ directly

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

/-- Normal form of the root S(1,2,z) option list at fuel N+1. -/theorem spider_gamma_root_options (N z m : ℕ) (hz : z = m + 1) (hN : 3 ≤ N) :    spider_gamma (N + 1) CentreStatus.none        [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free), (z, SpiderLegEnd.free)] =      nat_mex_list        ([ spider_gamma N CentreStatus.incoming [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)],           spider_gamma N CentreStatus.outgoing [(2, SpiderLegEnd.free), (z, SpiderLegEnd.free)],           1 ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],           1 ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],           spider_gamma N CentreStatus.none [(1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],           spider_gamma N CentreStatus.none [(1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (z, SpiderLegEnd.free)],           m ^^^ spider_gamma N CentreStatus.incoming [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)],           m ^^^ spider_gamma N CentreStatus.outgoing [(1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]] ++         (List.range m).flatMap (fun i =>           [(z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.inward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)],            (z - (i + 2)) ^^^ spider_gamma N CentreStatus.none [(i + 1, SpiderLegEnd.outward), (1, SpiderLegEnd.free), (2, SpiderLegEnd.free)]])) := by  have _ := hN  subst hz  apply congr_arg nat_mex_list  change    List.flatMap _ [((1, SpiderLegEnd.free), 0), ((2, SpiderLegEnd.free), 1), ((m + 1, SpiderLegEnd.free), 2)] = _  rw [List.flatMap_cons, List.flatMap_cons, List.flatMap_cons, List.flatMap_nil]  dsimp only  have hr1 : List.range 1 = [0] := rfl  have hr2 : List.range 2 = [0, 1] := rfl  rw [hr1, hr2]  rw [List.range_succ_eq_map (n := m)]  simp only [List.flatMap_cons, List.flatMap_nil, List.append_nil, List.flatMap_map]  simp [spider_rho, spider_update_centre]
See it in the graphDiscuss this resultChallenge it