AFTD Auto-Formalizing Theoretical Domains

spider_gamma_fuel_independent

theoremverified

For every fuel at least the total number of markable edges in L plus one, the value of spider_gamma does not depend on the fuel: it equals the value at the canonical fuel (sum of leg lengths) + 1.

Statement

theorem spider_gamma_fuel_independent (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd))
    (hfuel : (L.map Prod.fst).sum + 1 ≤ fuel) :
    spider_gamma fuel s L = spider_gamma ((L.map Prod.fst).sum + 1) s L
Source
step towards spider_eventual_parity_two_three
Verified
19 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • 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_gammaThe function spider_gamma computes a natural number from a fuel parameter fuel : ℕ, a centre status s : CentreStatus, and a list of spider…
  • 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_rho_starThe function spider_rho_star takes h : ℕ and phi : SpiderLegEnd, returning h % 2 if phi = free, and h otherwise.
Used by 16

The proof, explained

The theorem establishes that the Grundy value `spider_gamma fuel s L` is independent of the recursion fuel once `fuel ≥ sum(L) + 1`, where `sum(L)` is the total length of all spider legs. The result is proved by strong induction on `sum(L)`. In the base cases where the center is free or the spider has at most one leg, `spider_gamma` evaluates non-recursively, making the fuel irrelevant. For graphs with at least two legs, every valid move either shortens or completely removes a leg, strictly decreasing the total sum of leg lengths; by the induction hypothesis, all transition values under any two sufficient fuels coincide, making the lists of game options and their minimum excluded value (mex) identical.

  1. Erasing the leg at index `idx` leaves a list whose sum of leg lengths plus the erased leg's length equals the original total sum.

    The element `L[idx]` prepended to `L.eraseIdx idx` forms a permutation of `L` via `List.getElem_cons_eraseIdx_perm`. Permutations have equal sums, and after commuting `map Prod.fst` past `eraseIdx` via `List.eraseIdx_map` and expanding the head element with `List.sum_cons` and `List.getElem_map`, linear arithmetic (`omega`) equates the sum of the erased list plus `L[idx].1` to the original sum.

    lines 3–8

    uses List.eraseIdx_map, List.sum_cons, List.getElem_map

      have hlen : idx < (L.map Prod.fst).length := by simpa using h_idx
      have hp := (L.map Prod.fst).getElem_cons_eraseIdx_perm hlen
      have hsum := hp.sum_eq
      rw [← List.eraseIdx_map]
      simp only [List.sum_cons, List.getElem_map] at hsum
      omega
  2. Completely erasing a leg with strictly positive length strictly decreases the total sum of leg lengths.

    Substituting `L[idx].1 = h` into `spider_gamma_fuel_independent_sum_eraseIdx_eq` gives `((L.eraseIdx idx).map Prod.fst).sum + h = (L.map Prod.fst).sum`. Since `h > j_zero ≥ 0`, `h` is at least 1, so linear arithmetic (`omega`) shows the erased list has strictly smaller total sum.

    lines 13–15

    uses spider_gamma_fuel_independent_sum_eraseIdx_eq

      have := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx
      rw [hh] at this
      omega
  3. Replacing a leg of length `h` with a shorter leg of length `j_zero < h` strictly decreases the total sum of leg lengths.

    Expanding the sum of the modified list using `List.map_cons` and `List.sum_cons` gives `(j_zero + 1 - 1) + ((L.eraseIdx idx).map Prod.fst).sum`. Using `spider_gamma_fuel_independent_sum_eraseIdx_eq` with `L[idx].1 = h` and the inequality `j_zero < h`, linear arithmetic (`omega`) confirms the new sum is strictly smaller than the original sum.

    lines 21–24

    uses spider_gamma_fuel_independent_sum_eraseIdx_eq, List.map_cons, List.sum_cons

      have := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx
      rw [hh] at this
      simp only [List.map_cons, List.sum_cons]
      omega
  4. By strong induction on the total sum of leg lengths n, we may assume both fuel values are positive successors.

    We perform strong induction on the sum of leg lengths $n$ via `Nat.strong_induction_on`. In the inductive step, both fuel values satisfy $\\text{fuel} \\ge n + 1 \\ge 1$, so the zero-fuel cases are ruled out as contradictory by linear arithmetic (`omega`), leaving $\\text{fuel}_1 = f_1 + 1$ and $\\text{fuel}_2 = f_2 + 1$.

    lines 31–38

    uses Nat.strong_induction_on

      induction' n using Nat.strong_induction_on with n IH
      intro L hn fuel1 fuel2 s _h1 _h2
      cases fuel1 with
      | zero => omega
      | succ f1 =>
        cases fuel2 with
        | zero => omega
        | succ f2 =>
  5. When the center is free, or when the spider has at most one leg, `spider_gamma` is independent of the fuel.

    If $s = \\text{CentreStatus.free}$, `spider_gamma` evaluates directly by folding `spider_rho_star` over $L$ (`spider_gamma.eq_def`), which does not reference fuel. If $s \\ne \\text{free}$, we match on $L$: if $L = []$, both sides evaluate to 0; if $L = [(h, \\phi)]$, both sides evaluate directly to `spider_rho` evaluated on $h$ and the orientations (`spider_gamma.eq_def`), neither of which involves fuel.

    lines 39–43

    uses spider_gamma.eq_def

          by_cases hs : s = CentreStatus.free
          · subst hs; rw [spider_gamma.eq_def, spider_gamma.eq_def]
          · match L with
            | [] => rw [spider_gamma.eq_def, spider_gamma.eq_def]
            | [(h, phi)] => rw [spider_gamma.eq_def, spider_gamma.eq_def]
  6. For spiders with at least two legs, `spider_gamma` reduces to the minimum excluded value of transition options, reducing fuel independence to equality of option lists.

    When $L = a :: b :: \\text{rest}$, $L$ is non-empty and has more than one leg. Rewriting both sides with `spider_gamma.eq_7` expresses `spider_gamma (f + 1) s L` as the minimum excluded value (`nat_mex_list`) of the options list. Congruence (`congr 1`) reduces the goal to showing that the lists of options generated under fuel $f_1$ and fuel $f_2$ are identical.

    lines 44–49

    uses spider_gamma.eq_7

            | a :: b :: rest =>
              have hL1 : (a :: b :: rest) ≠ [] := by simp
              have hL2 : ∀ h phi, (a :: b :: rest) ≠ [(h, phi)] := by intro h phi; simp
              rw [spider_gamma.eq_7 s (a :: b :: rest) f1 hs hL1 hL2]
              rw [spider_gamma.eq_7 s (a :: b :: rest) f2 hs hL1 hL2]
              congr 1
  7. Iterating over leg choices, move lengths, and endpoint orientations reduces option equality to valid moves.

    Using `List.flatMap_congr` over the legs in `L.zipIdx` (with `List.mem_zipIdx`), over move lengths $j_0 \\in \\text{range } h$ (with `List.mem_range.mp`), and `List.filterMap_congr` over endpoint directions $\\delta$, we compare options elementwise. On an invalid move, both sides produce `none`, which holds reflexively (`rfl`).

    lines 50–62

    uses List.flatMap_congr, List.mem_zipIdx, List.mem_range.mp, List.filterMap_congr

              apply List.flatMap_congr
              intro ⟨⟨h, phi⟩, idx⟩ h_mem
              have h_zip := List.mem_zipIdx h_mem
              have h_idx : idx < (a :: b :: rest).length := by simpa using h_zip.2.1
              have h_eq : (h, phi) = (a :: b :: rest)[idx] := by simpa using h_zip.2.2
              have hh : (a :: b :: rest)[idx].1 = h := by rw [← h_eq]
              apply List.flatMap_congr
              intro j_zero hj_mem
              have hj : j_zero < h := List.mem_range.mp hj_mem
              apply List.filterMap_congr
              intro delta hdelta_mem
              split_ifs with h1_cond h2_cond
              · rfl
  8. For moves shortening a leg ($j \\ge 2$), the recursive values under $f_1$ and $f_2$ agree by induction.

    When $j \\ge 2$, the move replaces leg `idx` with a shorter leg of length $j_0 = j - 1$. Lemma `spider_gamma_fuel_independent_sum_branch2_lt` proves the new sum of leg lengths is strictly less than $n$. Since $f_1$ and $f_2$ are at least the new sum plus one, the induction hypothesis `IH` applies, equating the recursive evaluations under $f_1$ and $f_2$.

    lines 63–67

    uses spider_gamma_fuel_independent_sum_branch2_lt

              · dsimp only
                have h_lt := spider_gamma_fuel_independent_sum_branch2_lt (a :: b :: rest) idx h_idx h hh j_zero hj delta
                rw [hn] at h_lt
                have h_IH := IH _ h_lt ((j_zero + 1 - 1, delta) :: (a :: b :: rest).eraseIdx idx) rfl f1 f2 s (by omega) (by omega)
                rw [h_IH]
  9. For moves completely removing a leg ($j = 1$), the recursive values under $f_1$ and $f_2$ agree by induction.

    When $j < 2$ (so $j = 1$), the leg is deleted and the center status is updated to `spider_update_centre s delta`. Lemma `spider_gamma_fuel_independent_sum_branch1_lt` proves the sum of the remaining leg lengths is strictly less than $n$. The induction hypothesis `IH` again applies to equate the recursive calls under $f_1$ and $f_2$.

    lines 68–72

    uses spider_gamma_fuel_independent_sum_branch1_lt

              · dsimp only
                have h_lt := spider_gamma_fuel_independent_sum_branch1_lt (a :: b :: rest) idx h_idx h hh j_zero hj
                rw [hn] at h_lt
                have h_IH := IH _ h_lt ((a :: b :: rest).eraseIdx idx) rfl f1 f2 (spider_update_centre s delta) (by omega) (by omega)
                rw [h_IH]
  10. For any fuel at least `sum(L) + 1`, `spider_gamma fuel s L` equals `spider_gamma (sum(L) + 1) s L`.

    The theorem specializes the auxiliary lemma `spider_gamma_fuel_independent_aux` with $n = \\text{sum}(L)$, $\\text{fuel}_1 = \\text{fuel}$, and $\\text{fuel}_2 = \\text{sum}(L) + 1$, where the fuel hypothesis for $\\text{fuel}_2$ is satisfied trivially by linear arithmetic (`omega`).

    line 78

    uses spider_gamma_fuel_independent_aux

      exact spider_gamma_fuel_independent_aux (L.map Prod.fst).sum L rfl fuel ((L.map Prod.fst).sum + 1) s hfuel (by omega)
List.eraseIdx_map
Erasing an element at index `idx` after mapping `f` over a list is identical to mapping `f` over the list with index `idx` erased.
List.sum_cons
The sum of a non-empty list `a :: l` equals `a` plus the sum of `l`.
List.getElem_map
The `i`-th element of `List.map f l` equals `f` applied to the `i`-th element of `l`.
spider_gamma_fuel_independent_sum_eraseIdx_eq
Erasing the element at index `idx` from `L` leaves a list whose sum of leg lengths plus `L[idx].1` equals the total sum of leg lengths of `L`.
List.map_cons
Mapping a function over `a :: l` produces `f a :: List.map f l`.
Nat.strong_induction_on
Strong induction principle on ℕ: to prove `p n` for all `n`, it suffices to show that `p n` follows from `p m` holding for all `m < n`.
spider_gamma.eq_def
The recursive unfolding definition of `spider_gamma` by case analysis on fuel, center status, and leg list.
spider_gamma.eq_7
The unfolding of `spider_gamma (fuel + 1) s L` as the mex (`nat_mex_list`) of the transition options when `s ≠ CentreStatus.free` and `L` has at least two elements.
List.flatMap_congr
Two flat-mapped lists `List.flatMap f l` and `List.flatMap g l` are equal if `f` and `g` agree on every element of `l`.
List.mem_zipIdx
An element `(x, i)` is in `xs.zipIdx` if and only if `i < xs.length` and `x = xs[i]`.
List.mem_range.mp
An element is in `List.range h` if and only if it is strictly less than `h`.
List.filterMap_congr
Two filter-mapped lists `List.filterMap f l` and `List.filterMap g l` are equal if the transformation functions agree on every element of `l`.
spider_gamma_fuel_independent_sum_branch2_lt
Replacing a leg of length `h` at `idx` with a shorter leg of length `j_zero < h` strictly decreases the total sum of leg lengths.
spider_gamma_fuel_independent_sum_branch1_lt
Completely erasing a leg of positive length `h` at `idx` strictly decreases the total sum of leg lengths.
spider_gamma_fuel_independent_aux
For any two fuel amounts both at least the total sum of leg lengths plus one, `spider_gamma` evaluates to the same value.

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

lemma spider_gamma_fuel_independent_sum_eraseIdx_eq (L : List (ℕ × SpiderLegEnd)) (idx : ℕ) (h_idx : idx < L.length) :    ((L.eraseIdx idx).map Prod.fst).sum + (L[idx].1) = (L.map Prod.fst).sum := by  have hlen : idx < (L.map Prod.fst).length := by simpa using h_idx  have hp := (L.map Prod.fst).getElem_cons_eraseIdx_perm hlen  have hsum := hp.sum_eq  rw [← List.eraseIdx_map]  simp only [List.sum_cons, List.getElem_map] at hsum  omegalemma spider_gamma_fuel_independent_sum_branch1_lt (L : List (ℕ × SpiderLegEnd)) (idx : ℕ) (h_idx : idx < L.length)    (h : ℕ) (hh : L[idx].1 = h) (j_zero : ℕ) (hj : j_zero < h) :    ((L.eraseIdx idx).map Prod.fst).sum < (L.map Prod.fst).sum := by  have := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx  rw [hh] at this  omegalemma spider_gamma_fuel_independent_sum_branch2_lt (L : List (ℕ × SpiderLegEnd)) (idx : ℕ) (h_idx : idx < L.length)    (h : ℕ) (hh : L[idx].1 = h) (j_zero : ℕ) (hj : j_zero < h)    (delta : SpiderLegEnd) :    (((j_zero + 1 - 1, delta) :: (L.eraseIdx idx)).map Prod.fst).sum < (L.map Prod.fst).sum := by  have := spider_gamma_fuel_independent_sum_eraseIdx_eq L idx h_idx  rw [hh] at this  simp only [List.map_cons, List.sum_cons]  omegalemma spider_gamma_fuel_independent_aux (n : ℕ) :    ∀ (L : List (ℕ × SpiderLegEnd)) (_ : (L.map Prod.fst).sum = n)      (fuel1 fuel2 : ℕ) (s : CentreStatus)      (_h1 : (L.map Prod.fst).sum + 1 ≤ fuel1) (_h2 : (L.map Prod.fst).sum + 1 ≤ fuel2),      spider_gamma fuel1 s L = spider_gamma fuel2 s L := by  induction' n using Nat.strong_induction_on with n IH  intro L hn fuel1 fuel2 s _h1 _h2  cases fuel1 with  | zero => omega  | succ f1 =>    cases fuel2 with    | zero => omega    | succ f2 =>      by_cases hs : s = CentreStatus.free      · subst hs; rw [spider_gamma.eq_def, spider_gamma.eq_def]      · match L with        | [] => rw [spider_gamma.eq_def, spider_gamma.eq_def]        | [(h, phi)] => rw [spider_gamma.eq_def, spider_gamma.eq_def]        | a :: b :: rest =>          have hL1 : (a :: b :: rest) ≠ [] := by simp          have hL2 : ∀ h phi, (a :: b :: rest) ≠ [(h, phi)] := by intro h phi; simp          rw [spider_gamma.eq_7 s (a :: b :: rest) f1 hs hL1 hL2]          rw [spider_gamma.eq_7 s (a :: b :: rest) f2 hs hL1 hL2]          congr 1          apply List.flatMap_congr          intro ⟨⟨h, phi⟩, idx⟩ h_mem          have h_zip := List.mem_zipIdx h_mem          have h_idx : idx < (a :: b :: rest).length := by simpa using h_zip.2.1          have h_eq : (h, phi) = (a :: b :: rest)[idx] := by simpa using h_zip.2.2          have hh : (a :: b :: rest)[idx].1 = h := by rw [← h_eq]          apply List.flatMap_congr          intro j_zero hj_mem          have hj : j_zero < h := List.mem_range.mp hj_mem          apply List.filterMap_congr          intro delta hdelta_mem          split_ifs with h1_cond h2_cond          · rfl          · dsimp only            have h_lt := spider_gamma_fuel_independent_sum_branch2_lt (a :: b :: rest) idx h_idx h hh j_zero hj delta            rw [hn] at h_lt            have h_IH := IH _ h_lt ((j_zero + 1 - 1, delta) :: (a :: b :: rest).eraseIdx idx) rfl f1 f2 s (by omega) (by omega)            rw [h_IH]          · dsimp only            have h_lt := spider_gamma_fuel_independent_sum_branch1_lt (a :: b :: rest) idx h_idx h hh j_zero hj            rw [hn] at h_lt            have h_IH := IH _ h_lt ((a :: b :: rest).eraseIdx idx) rfl f1 f2 (spider_update_centre s delta) (by omega) (by omega)            rw [h_IH]/-- spider_gamma is independent of the fuel once the fuel is at least the total leg length plus one. -/theorem spider_gamma_fuel_independent (fuel : ℕ) (s : CentreStatus) (L : List (ℕ × SpiderLegEnd))    (hfuel : (L.map Prod.fst).sum + 1 ≤ fuel) :    spider_gamma fuel s L = spider_gamma ((L.map Prod.fst).sum + 1) s L := by  exact spider_gamma_fuel_independent_aux (L.map Prod.fst).sum L rfl fuel ((L.map Prod.fst).sum + 1) s hfuel (by omega)
See it in the graphDiscuss this resultChallenge it