AFTD Auto-Formalizing Theoretical Domains

spider_eventual_parity_two_three_blocked_small

theoremverified

For the configuration κ0 = (none;{2^*,3^*}), the blocked family at level t is 2 for t = 1 and 6 for t = 2, for both far ends, and it is at most 7 for t = 3, 4, 5.

Statement

theorem spider_eventual_parity_two_three_blocked_small :
    spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 ∧
    spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 ∧
    spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 ∧
    spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 ∧
    (∀ t : ℕ, 3 ≤ t → t ≤ 5 →
      spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7) ∧
    (∀ t : ℕ, 3 ≤ t → t ≤ 5 →
      spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7)
Source
step towards spider_eventual_parity_two_three
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • spider_gamma_fuel_independentFor 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…
  • spider_blocked_two_three_reversalFor any fuel and leg length t, the spider gamma value with centre none and legs (t, outward), (2, free), (3, free) equals the gamma value…
  • spider_blocked_two_three_level_fourAt level t = 4, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 10 is at most 7.
  • spider_blocked_two_three_level_fiveAt level t = 5, the inward blocked family for the configuration (none; {2^*, 3^*}) at canonical fuel 11 is at most 7.
  • 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…
  • CentreStatusThe status of the central vertex in a spider state: none (no marked arcs incident), incoming (at least one incoming arc), outgoing (at…

The proof, explained

The theorem computes or bounds the Grundy values (via `spider_gamma`) for the blocked spider family κ0 = (none; {2^*, 3^*}) with leg lengths t, 2, 3 at small levels 1 ≤ t ≤ 5. For t = 1 and t = 2, the inward values are evaluated directly by finite game-tree computation (`decide`) to be 2 and 6 respectively. The outward values for t = 1 and t = 2 equal the inward values by the reversal symmetry `spider_blocked_two_three_reversal`. For t ∈ {3, 4, 5}, the inward values are bounded by 7 by case analysis on t using precomputed bounds, and the outward bounds follow immediately from the inward bounds via leg-end reversal.

  1. The Grundy value for the level t = 1 inward blocked configuration is 2. automation

    The helper lemma `spider_eventual_parity_two_three_blocked_small_level_one` computes the value of `spider_gamma` for fuel 7, centre status `none`, and legs [(1, inward), (2, free), (3, free)]. Since all arguments are concrete, Lean's decision procedure evaluates the recursive definition directly to obtain 2.

    lines 1–4

    lemma spider_eventual_parity_two_three_blocked_small_level_one :
        spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 := by
      decide
    
  2. The Grundy value for the level t = 2 inward blocked configuration is 6. automation

    The helper lemma `spider_eventual_parity_two_three_blocked_small_level_two` computes `spider_gamma` for fuel 8 and legs [(2, inward), (2, free), (3, free)]. The decision procedure evaluates the finite game tree directly to obtain 6.

    lines 5–8

    lemma spider_eventual_parity_two_three_blocked_small_level_two :
        spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 := by
      decide
    
  3. The Grundy value for the level t = 3 inward blocked configuration is at most 7. automation

    The helper lemma `spider_eventual_parity_two_three_blocked_small_level_three` computes `spider_gamma` for fuel 9 and legs [(3, inward), (2, free), (3, free)], verifying by direct evaluation that the result is at most 7.

    lines 9–12

    lemma spider_eventual_parity_two_three_blocked_small_level_three :
        spider_gamma 9 CentreStatus.none [(3, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7 := by
      decide
    
  4. At level t = 1, both inward and outward blocked configurations have Grundy value 2.

    The inward value h1 is established directly by applying the level 1 helper lemma. The outward value h1_out is obtained by rewriting with `spider_blocked_two_three_reversal`, which asserts that swapping outward for inward leaves the Grundy value invariant in this configuration, and then substituting the inward value h1 = 2.

    lines 13–26

    uses spider_eventual_parity_two_three_blocked_small_level_one, spider_blocked_two_three_reversal

    /-- The two small blocked values of the κ0 family: at levels 1 and 2 the blocked families of κ0 = (none;{2^*,3^*}) take the values 2 and 6 (paper Table 6). -/
    theorem spider_eventual_parity_two_three_blocked_small :
        spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 ∧
        spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 ∧
        spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 ∧
        spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 ∧
        (∀ t : ℕ, 3 ≤ t → t ≤ 5 →
          spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7) ∧
        (∀ t : ℕ, 3 ≤ t → t ≤ 5 →
          spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7) := by
      have h1 : spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 :=
        spider_eventual_parity_two_three_blocked_small_level_one
      have h1_out : spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 := by
        rw [spider_blocked_two_three_reversal, h1]
  5. At level t = 2, both inward and outward blocked configurations have Grundy value 6.

    The inward value h2 is given by the level 2 helper lemma. The outward value h2_out is shown to be 6 by applying `spider_blocked_two_three_reversal` to replace the outward leg end with the inward leg end and substituting the inward result h2 = 6.

    lines 27–30

    uses spider_eventual_parity_two_three_blocked_small_level_two, spider_blocked_two_three_reversal

      have h2 : spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 :=
        spider_eventual_parity_two_three_blocked_small_level_two
      have h2_out : spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 := by
        rw [spider_blocked_two_three_reversal, h2]
  6. For all t ∈ {3, 4, 5}, the Grundy value for the inward configuration is at most 7.

    Assuming 3 ≤ t ≤ 5, the proof splits into the three cases t = 3, t = 4, and t = 5 using `interval_cases`. The cases are discharged respectively by `spider_eventual_parity_two_three_blocked_small_level_three`, `spider_blocked_two_three_level_four`, and `spider_blocked_two_three_level_five`.

    lines 31–37

    uses spider_eventual_parity_two_three_blocked_small_level_three, spider_blocked_two_three_level_four, spider_blocked_two_three_level_five

      have h_in : ∀ t : ℕ, 3 ≤ t → t ≤ 5 →
          spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7 := by
        intro t ht3 ht5
        interval_cases t
        · exact spider_eventual_parity_two_three_blocked_small_level_three
        · exact spider_blocked_two_three_level_four
        · exact spider_blocked_two_three_level_five
  7. For all t ∈ {3, 4, 5}, the Grundy value for the outward configuration is at most 7.

    For any t with 3 ≤ t ≤ 5, rewriting with `spider_blocked_two_three_reversal` replaces the outward leg end with the inward leg end, reducing the goal to the inward bound already established in h_in.

    lines 38–42

    uses spider_blocked_two_three_reversal

      have h_out : ∀ t : ℕ, 3 ≤ t → t ≤ 5 →
          spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7 := by
        intro t ht3 ht5
        rw [spider_blocked_two_three_reversal]
        exact h_in t ht3 ht5
  8. The full conjunction holds.

    The six established results (the two equalities for t = 1, the two equalities for t = 2, the inward bound for 3 ≤ t ≤ 5, and the outward bound for 3 ≤ t ≤ 5) are assembled as a conjunction to finish the proof.

    line 43

      exact ⟨h1, h1_out, h2, h2_out, h_in, h_out⟩
spider_eventual_parity_two_three_blocked_small_level_one
For the configuration with legs of lengths 1, 2, 3 where the leg of length 1 is blocked inward, the Grundy value with fuel 7 and neutral centre is 2.
spider_blocked_two_three_reversal
For any fuel and leg length t, the Grundy value of the spider with legs (t, ·), (2, free), (3, free) and neutral centre is identical whether the end of leg t is outward or inward.
spider_eventual_parity_two_three_blocked_small_level_two
For the configuration with legs of lengths 2, 2, 3 where one leg of length 2 is blocked inward, the Grundy value with fuel 8 and neutral centre is 6.
spider_eventual_parity_two_three_blocked_small_level_three
For the configuration with legs of lengths 3, 2, 3 where the first leg of length 3 is blocked inward, the Grundy value with fuel 9 and neutral centre is at most 7.
spider_blocked_two_three_level_four
For the configuration with legs of lengths 4, 2, 3 where the leg of length 4 is blocked inward, the Grundy value with fuel 10 and neutral centre is at most 7.
spider_blocked_two_three_level_five
For the configuration with legs of lengths 5, 2, 3 where the leg of length 5 is blocked inward, the Grundy value with fuel 11 and neutral centre is at most 7.

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_eventual_parity_two_three_blocked_small_level_one :    spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 := by  decidelemma spider_eventual_parity_two_three_blocked_small_level_two :    spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 := by  decidelemma spider_eventual_parity_two_three_blocked_small_level_three :    spider_gamma 9 CentreStatus.none [(3, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7 := by  decide/-- The two small blocked values of the κ0 family: at levels 1 and 2 the blocked families of κ0 = (none;{2^*,3^*}) take the values 2 and 6 (paper Table 6). -/theorem spider_eventual_parity_two_three_blocked_small :    spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 ∧    spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 ∧    spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 ∧    spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 ∧    (∀ t : ℕ, 3 ≤ t → t ≤ 5 →      spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7) ∧    (∀ t : ℕ, 3 ≤ t → t ≤ 5 →      spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7) := by  have h1 : spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 :=    spider_eventual_parity_two_three_blocked_small_level_one  have h1_out : spider_gamma 7 CentreStatus.none [(1, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 2 := by    rw [spider_blocked_two_three_reversal, h1]  have h2 : spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 :=    spider_eventual_parity_two_three_blocked_small_level_two  have h2_out : spider_gamma 8 CentreStatus.none [(2, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] = 6 := by    rw [spider_blocked_two_three_reversal, h2]  have h_in : ∀ t : ℕ, 3 ≤ t → t ≤ 5 →      spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.inward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7 := by    intro t ht3 ht5    interval_cases t    · exact spider_eventual_parity_two_three_blocked_small_level_three    · exact spider_blocked_two_three_level_four    · exact spider_blocked_two_three_level_five  have h_out : ∀ t : ℕ, 3 ≤ t → t ≤ 5 →      spider_gamma (t + 6) CentreStatus.none [(t, SpiderLegEnd.outward), (2, SpiderLegEnd.free), (3, SpiderLegEnd.free)] ≤ 7 := by    intro t ht3 ht5    rw [spider_blocked_two_three_reversal]    exact h_in t ht3 ht5  exact ⟨h1, h1_out, h2, h2_out, h_in, h_out⟩
See it in the graphDiscuss this resultChallenge it