AFTD Auto-Formalizing Theoretical Domains

spider_blocked_optionvals_top_mem

theoremverified

For r ≥ 1 and β inward or outward, r is in the explicit options list; moreover r-1 is in it when β = inward and r % 4 ≠ 3, and when β = outward and r % 4 ≠ 1.

Statement

theorem spider_blocked_optionvals_top_mem (r : ℕ) (hr : 1 ≤ r) (beta : SpiderLegEnd)
    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward) :
    r ∈ spider_blocked_optionvals r beta ∧
    (beta = SpiderLegEnd.inward → r % 4 ≠ 3 → r - 1 ∈ spider_blocked_optionvals r beta) ∧
    (beta = SpiderLegEnd.outward → r % 4 ≠ 1 → r - 1 ∈ spider_blocked_optionvals r beta)
Source
step towards spider_two_leg_blocked_incoming_val
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • spider_blocked_optionvalsThe explicit options list of the state (in;{(r,β),(1,free)}) at fuel r + 2 after substituting the inductive closed forms: for each cut j =…
  • spider_blocked_valThe conjectured closed form of the blocked two-leg family at incoming centre: for end condition inward it is m - 1 when m % 4 = 3 and m +…
  • 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.
  • 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 1
  • spider_blocked_optionvals_lt_memFor r ≥ 2 and β inward or outward, every k below spider_blocked_val β r occurs in the explicit options list of (in;{(r,β),(1,free)}).

The proof, explained

The theorem establishes that for any leg length r ≥ 1, r is always an available option value for both inward and outward legs, and r - 1 is also available provided r avoids a specific residue class modulo 4 (3 for inward, 1 for outward). The value r is available because it occurs as the trailing element ρ*(r, β) = r of the options list. The value r - 1 is obtained for r ≥ 2 from the flat-mapped portion of the options list by choosing index idx = r - 2 and the opposite leg orientation δ; this choice makes the height difference 1, yielding a transition cost ρ(1, δ, β) = 0 and evaluating the blocked value to (r - 2) + 1 = r - 1 precisely when the forbidden residue is avoided. The remaining base cases at r = 1 are resolved directly by computation or vacuous implication.

  1. For any r, r belongs to the option values list for an inward leg.

    The definition of spider_blocked_optionvals ends with the trailing element spider_rho_star r inward. By definition of spider_rho_star, this evaluates to r, so rewriting by this identity shows r ∈ spider_blocked_optionvals r inward.

    lines 3–6

    uses List.mem_append

      have hmem : spider_rho_star r SpiderLegEnd.inward ∈ spider_blocked_optionvals r SpiderLegEnd.inward := by
        simp [spider_blocked_optionvals, List.mem_append]
      have hval : spider_rho_star r SpiderLegEnd.inward = r := rfl
      rwa [hval] at hmem
  2. For any r, r belongs to the option values list for an outward leg.

    Similarly, spider_rho_star r outward is the final element of spider_blocked_optionvals r outward, and evaluates definitionally to r, establishing membership.

    lines 10–13

    uses List.mem_append

      have hmem : spider_rho_star r SpiderLegEnd.outward ∈ spider_blocked_optionvals r SpiderLegEnd.outward := by
        simp [spider_blocked_optionvals, List.mem_append]
      have hval : spider_rho_star r SpiderLegEnd.outward = r := rfl
      rwa [hval] at hmem
  3. Any value obtained by choosing an index idx < r - 1 and a non-free leg end δ belongs to spider_blocked_optionvals r beta.

    Unfolding the definition of spider_blocked_optionvals shows that the first component is a flatMap over List.range (r - 1). Since idx < r - 1, idx is in the range, and since δ is either inward or outward, it is in the list [inward, outward], so the corresponding XOR sum is in the list.

    lines 19–24

    uses List.mem_append.mpr, Or.inl, List.mem_flatMap.mpr, List.mem_range.mpr, List.mem_map.mpr

      simp only [spider_blocked_optionvals]
      refine List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inl ?_)))
      refine List.mem_flatMap.mpr ⟨idx, List.mem_range.mpr hidx, ?_⟩
      refine List.mem_map.mpr ⟨delta, ?_, ?_⟩
      · rcases hδ with rfl | rfl <;> simp
      · simp
  4. When h is odd, the transition value ρ(h, outward, inward) is 0.

    By definition of spider_rho for an inward leg, the value when transitioning from outward can only be 1 if h ≥ 2 and h is even; since h % 2 = 1, it simplifies to 0.

    line 28

      simp [spider_rho, hodd]
  5. When h is odd, the transition value ρ(h, inward, outward) is 0.

    Symmetrically, spider_rho for an outward leg transitioning from inward evaluates to 0 whenever h is odd.

    line 32

      simp [spider_rho, hodd]
  6. For r ≥ 2 with r % 4 ≠ 3, r - 1 belongs to the option values list for an inward leg.

    We instantiate the flatMap membership lemma with idx = r - 2 (which is strictly less than r - 1 because r ≥ 2) and δ = outward. The transition argument is r - (r - 2 + 1) = 1, which is odd, giving ρ(1, outward, inward) = 0. The hypothesis r % 4 ≠ 3 implies (r - 2) % 4 ≠ 1, so spider_blocked_val outward (r - 2) selects the else branch (r - 2) + 1 = r - 1. Since 0 ⊕ (r - 1) = r - 1, we conclude r - 1 is in the list.

    lines 36–49

    uses spider_blocked_optionvals_top_mem_mem_flatMap, Or.inr, spider_blocked_optionvals_top_mem_rho_outward_inward_odd, if_neg, Nat.zero_xor

      have hidx : r - 2 < r - 1 := by omega
      have hmem := spider_blocked_optionvals_top_mem_mem_flatMap r (r - 2) SpiderLegEnd.inward
        SpiderLegEnd.outward hidx (Or.inr rfl)
      have hh : r - (r - 2 + 1) = 1 := by omega
      have hrho : spider_rho (r - (r - 2 + 1)) SpiderLegEnd.outward SpiderLegEnd.inward = 0 := by
        rw [hh]
        exact spider_blocked_optionvals_top_mem_rho_outward_inward_odd 1 (by decide)
      have hmod' : (r - 2) % 4 ≠ 1 := by omega
      have hval : spider_blocked_val SpiderLegEnd.outward (r - 2) = r - 1 := by
        simp only [spider_blocked_val]
        rw [if_neg hmod']
        omega
      rw [hrho, hval, Nat.zero_xor] at hmem
      exact hmem
  7. For r ≥ 2 with r % 4 ≠ 1, r - 1 belongs to the option values list for an outward leg.

    We instantiate the flatMap membership lemma with idx = r - 2 and δ = inward. Here r - (r - 2 + 1) = 1 gives ρ(1, inward, outward) = 0. The hypothesis r % 4 ≠ 1 implies (r - 2) % 4 ≠ 3, so spider_blocked_val inward (r - 2) evaluates to (r - 2) + 1 = r - 1. Since 0 ⊕ (r - 1) = r - 1, r - 1 is in the list.

    lines 53–66

    uses spider_blocked_optionvals_top_mem_mem_flatMap, Or.inl, spider_blocked_optionvals_top_mem_rho_inward_outward_odd, if_neg, Nat.zero_xor

      have hidx : r - 2 < r - 1 := by omega
      have hmem := spider_blocked_optionvals_top_mem_mem_flatMap r (r - 2) SpiderLegEnd.outward
        SpiderLegEnd.inward hidx (Or.inl rfl)
      have hh : r - (r - 2 + 1) = 1 := by omega
      have hrho : spider_rho (r - (r - 2 + 1)) SpiderLegEnd.inward SpiderLegEnd.outward = 0 := by
        rw [hh]
        exact spider_blocked_optionvals_top_mem_rho_inward_outward_odd 1 (by decide)
      have hmod' : (r - 2) % 4 ≠ 3 := by omega
      have hval : spider_blocked_val SpiderLegEnd.inward (r - 2) = r - 1 := by
        simp only [spider_blocked_val]
        rw [if_neg hmod']
        omega
      rw [hrho, hval, Nat.zero_xor] at hmem
      exact hmem
  8. We split the proof of the theorem into two cases depending on whether β is inward or outward.

    Hypothesis hβ states that β = inward ∨ β = outward. Deconstructing this disjunction gives two cases to consider.

    line 74

      rcases hβ with rfl | rfl
  9. When β = inward, r is always an option value, and r - 1 is an option value whenever r % 4 ≠ 3.

    The first claim r ∈ spider_blocked_optionvals r inward is provided by spider_blocked_optionvals_top_mem_last_inward. For the second claim, assuming r % 4 ≠ 3, we case-split on r < 2 versus r ≥ 2: if r < 2, then r = 1 since r ≥ 1, and 1 - 1 = 0 is checked directly by decide; if r ≥ 2, the claim follows from spider_blocked_optionvals_top_mem_inward_pred. The third conjunct is vacuously true because inward = outward is false.

    lines 75–83

    uses spider_blocked_optionvals_top_mem_last_inward, Nat.lt_or_ge, spider_blocked_optionvals_top_mem_inward_pred

      · refine ⟨spider_blocked_optionvals_top_mem_last_inward r, ?_, ?_⟩
        · intro _ hmod
          rcases Nat.lt_or_ge r 2 with h2 | h2
          · have h1 : r = 1 := by omega
            subst h1
            decide
          · exact spider_blocked_optionvals_top_mem_inward_pred r h2 hmod
        · intro h
          exact absurd h (by decide)
  10. When β = outward, r is always an option value, and r - 1 is an option value whenever r % 4 ≠ 1.

    The first claim r ∈ spider_blocked_optionvals r outward holds by spider_blocked_optionvals_top_mem_last_outward. The second conjunct is vacuously true since outward = inward is false. For the third conjunct, assuming r % 4 ≠ 1, we split on r < 2 versus r ≥ 2: if r < 2, then r = 1, which contradicts r % 4 ≠ 1 since 1 % 4 = 1; if r ≥ 2, the claim follows from spider_blocked_optionvals_top_mem_outward_pred.

    lines 84–92

    uses spider_blocked_optionvals_top_mem_last_outward, Nat.lt_or_ge, spider_blocked_optionvals_top_mem_outward_pred

      · refine ⟨spider_blocked_optionvals_top_mem_last_outward r, ?_, ?_⟩
        · intro h
          exact absurd h (by decide)
        · intro _ hmod
          rcases Nat.lt_or_ge r 2 with h2 | h2
          · have h1 : r = 1 := by omega
            subst h1
            exact absurd (by decide : (1 : ℕ) % 4 = 1) hmod
          · exact spider_blocked_optionvals_top_mem_outward_pred r h2 hmod
List.mem_append
An element belongs to the concatenation of two lists if and only if it belongs to the first list or the second list.
List.mem_append.mpr
If an element belongs to either of two lists, it belongs to their concatenation.
Or.inl
Given a proof of the left proposition, produces a proof of the disjunction.
Or.inr
Given a proof of the right proposition, produces a proof of the disjunction.
List.mem_flatMap.mpr
An element belongs to a flat-mapped list if it belongs to the list produced by applying the mapping function to some element of the original list.
List.mem_range.mpr
A natural number k belongs to List.range n whenever k < n.
List.mem_map.mpr
An element belongs to the image of a list under a function if it equals the function applied to some element of that list.
spider_blocked_optionvals_top_mem_mem_flatMap
For any index idx < r - 1 and non-free leg end δ, the XOR sum ρ(r - (idx + 1), δ, β) ⊕ spider_blocked_val(δ, idx) belongs to spider_blocked_optionvals(r, β).
spider_blocked_optionvals_top_mem_rho_outward_inward_odd
If h is odd, the transition value ρ(h, outward, inward) is 0.
spider_blocked_optionvals_top_mem_rho_inward_outward_odd
If h is odd, the transition value ρ(h, inward, outward) is 0.
if_neg
An if-then-else expression evaluates to the else branch when the condition is false.
Nat.zero_xor
Bitwise XOR of 0 with any natural number x yields x (0 ⊕ x = x).
spider_blocked_optionvals_top_mem_last_inward
The leg length r is always an element of spider_blocked_optionvals(r, inward).
spider_blocked_optionvals_top_mem_last_outward
The leg length r is always an element of spider_blocked_optionvals(r, outward).
spider_blocked_optionvals_top_mem_inward_pred
For r ≥ 2, if r % 4 ≠ 3, then r - 1 is an element of spider_blocked_optionvals(r, inward).
spider_blocked_optionvals_top_mem_outward_pred
For r ≥ 2, if r % 4 ≠ 1, then r - 1 is an element of spider_blocked_optionvals(r, outward).
Nat.lt_or_ge
For any natural numbers n and m, either n < m or n ≥ m.

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_blocked_optionvals_top_mem_last_inward (r : ℕ) :    r ∈ spider_blocked_optionvals r SpiderLegEnd.inward := by  have hmem : spider_rho_star r SpiderLegEnd.inward ∈ spider_blocked_optionvals r SpiderLegEnd.inward := by    simp [spider_blocked_optionvals, List.mem_append]  have hval : spider_rho_star r SpiderLegEnd.inward = r := rfl  rwa [hval] at hmemlemma spider_blocked_optionvals_top_mem_last_outward (r : ℕ) :    r ∈ spider_blocked_optionvals r SpiderLegEnd.outward := by  have hmem : spider_rho_star r SpiderLegEnd.outward ∈ spider_blocked_optionvals r SpiderLegEnd.outward := by    simp [spider_blocked_optionvals, List.mem_append]  have hval : spider_rho_star r SpiderLegEnd.outward = r := rfl  rwa [hval] at hmemlemma spider_blocked_optionvals_top_mem_mem_flatMap (r idx : ℕ) (beta delta : SpiderLegEnd)    (hidx : idx < r - 1) (hδ : delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward) :    spider_rho (r - (idx + 1)) delta beta ^^^ spider_blocked_val delta idx ∈      spider_blocked_optionvals r beta := by  simp only [spider_blocked_optionvals]  refine List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inl ?_)))  refine List.mem_flatMap.mpr ⟨idx, List.mem_range.mpr hidx, ?_⟩  refine List.mem_map.mpr ⟨delta, ?_, ?_⟩  · rcases hδ with rfl | rfl <;> simp  · simplemma spider_blocked_optionvals_top_mem_rho_outward_inward_odd (h : ℕ) (hodd : h % 2 = 1) :    spider_rho h SpiderLegEnd.outward SpiderLegEnd.inward = 0 := by  simp [spider_rho, hodd]lemma spider_blocked_optionvals_top_mem_rho_inward_outward_odd (h : ℕ) (hodd : h % 2 = 1) :    spider_rho h SpiderLegEnd.inward SpiderLegEnd.outward = 0 := by  simp [spider_rho, hodd]lemma spider_blocked_optionvals_top_mem_inward_pred (r : ℕ) (hr2 : 2 ≤ r) (hmod : r % 4 ≠ 3) :    r - 1 ∈ spider_blocked_optionvals r SpiderLegEnd.inward := by  have hidx : r - 2 < r - 1 := by omega  have hmem := spider_blocked_optionvals_top_mem_mem_flatMap r (r - 2) SpiderLegEnd.inward    SpiderLegEnd.outward hidx (Or.inr rfl)  have hh : r - (r - 2 + 1) = 1 := by omega  have hrho : spider_rho (r - (r - 2 + 1)) SpiderLegEnd.outward SpiderLegEnd.inward = 0 := by    rw [hh]    exact spider_blocked_optionvals_top_mem_rho_outward_inward_odd 1 (by decide)  have hmod' : (r - 2) % 4 ≠ 1 := by omega  have hval : spider_blocked_val SpiderLegEnd.outward (r - 2) = r - 1 := by    simp only [spider_blocked_val]    rw [if_neg hmod']    omega  rw [hrho, hval, Nat.zero_xor] at hmem  exact hmemlemma spider_blocked_optionvals_top_mem_outward_pred (r : ℕ) (hr2 : 2 ≤ r) (hmod : r % 4 ≠ 1) :    r - 1 ∈ spider_blocked_optionvals r SpiderLegEnd.outward := by  have hidx : r - 2 < r - 1 := by omega  have hmem := spider_blocked_optionvals_top_mem_mem_flatMap r (r - 2) SpiderLegEnd.outward    SpiderLegEnd.inward hidx (Or.inl rfl)  have hh : r - (r - 2 + 1) = 1 := by omega  have hrho : spider_rho (r - (r - 2 + 1)) SpiderLegEnd.inward SpiderLegEnd.outward = 0 := by    rw [hh]    exact spider_blocked_optionvals_top_mem_rho_inward_outward_odd 1 (by decide)  have hmod' : (r - 2) % 4 ≠ 3 := by omega  have hval : spider_blocked_val SpiderLegEnd.inward (r - 2) = r - 1 := by    simp only [spider_blocked_val]    rw [if_neg hmod']    omega  rw [hrho, hval, Nat.zero_xor] at hmem  exact hmem/-- Coverage of the top values: r is always an option, and r-1 is an option outside the special residue class. -/theorem spider_blocked_optionvals_top_mem (r : ℕ) (hr : 1 ≤ r) (beta : SpiderLegEnd)    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward) :    r ∈ spider_blocked_optionvals r beta ∧    (beta = SpiderLegEnd.inward → r % 4 ≠ 3 → r - 1 ∈ spider_blocked_optionvals r beta) ∧    (beta = SpiderLegEnd.outward → r % 4 ≠ 1 → r - 1 ∈ spider_blocked_optionvals r beta) := by  rcases hβ with rfl | rfl  · refine ⟨spider_blocked_optionvals_top_mem_last_inward r, ?_, ?_⟩    · intro _ hmod      rcases Nat.lt_or_ge r 2 with h2 | h2      · have h1 : r = 1 := by omega        subst h1        decide      · exact spider_blocked_optionvals_top_mem_inward_pred r h2 hmod    · intro h      exact absurd h (by decide)  · refine ⟨spider_blocked_optionvals_top_mem_last_outward r, ?_, ?_⟩    · intro h      exact absurd h (by decide)    · intro _ hmod      rcases Nat.lt_or_ge r 2 with h2 | h2      · have h1 : r = 1 := by omega        subst h1        exact absurd (by decide : (1 : ℕ) % 4 = 1) hmod      · exact spider_blocked_optionvals_top_mem_outward_pred r h2 hmod
See it in the graphDiscuss this resultChallenge it