AFTD Auto-Formalizing Theoretical Domains

spider_blocked_optionvals_low_mem

theoremverified

For r ≥ 2, β inward or outward, and k + 2 ≤ r, the number k occurs in the explicit options list of (in;{(r,β),(1,free)}).

Statement

theorem spider_blocked_optionvals_low_mem (r k : ℕ) (hr : 2 ≤ r) (beta : SpiderLegEnd)
    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward) (hk : k + 2 ≤ r) :
    k ∈ 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

To show that any integer k with k + 2 ≤ r occurs in the explicit options list of the blocked leg, the proof realizes k as an interior cut value at an even index idx = 2c < r - 1. Because idx is even, the local cut value is always odd (2c + 1), meaning that XORing with 1 subtracts 1 to yield 2c, while XORing with 0 leaves 2c + 1 unchanged. By performing a four-way case split on the parities of k and r, one chooses either the matching leg end delta = beta or the opposite leg end delta ≠ beta so that the remaining leg length evaluates spider_rho to 1 or 0 as needed to produce k.

  1. Any interior cut at index idx < r - 1 with boundary condition delta ∈ {inward, outward} yields a value in spider_blocked_optionvals r beta.

    Unfolding the definition of spider_blocked_optionvals, its first component is a flat-map over all cut indices idx in [0, r - 2) of a map over [inward, outward]. Given idx < r - 1 and delta ∈ {inward, outward}, this combination is an element of that initial sublist.

    lines 5–10

    uses List.mem_append_left, List.mem_flatMap.mpr, List.mem_range.mpr, List.mem_map.mpr

      unfold spider_blocked_optionvals
      refine List.mem_append_left _ (List.mem_append_left _ ?_)
      refine List.mem_flatMap.mpr ⟨idx, List.mem_range.mpr hidx, ?_⟩
      rcases hδ with rfl | rfl
      · exact List.mem_map.mpr ⟨_, by simp, rfl⟩
      · exact List.mem_map.mpr ⟨_, by simp, rfl⟩
  2. For any non-free boundary condition beta, there exists an alternate non-free boundary condition delta distinct from beta.

    By cases on beta: if beta is inward, delta is outward; if beta is outward, delta is inward.

    lines 15–17

    uses Or.inr, Or.inl

      rcases hβ with rfl | rfl
      · exact ⟨SpiderLegEnd.outward, Or.inr rfl, by simp⟩
      · exact ⟨SpiderLegEnd.inward, Or.inl rfl, by simp⟩
  3. For any leg end delta and any even natural number m, spider_blocked_val delta m = m + 1.

    An even number m cannot be congruent to 1 or 3 modulo 4. By definition, spider_blocked_val modifies m + 1 only when m % 4 = 3 (for inward) or m % 4 = 1 (for outward and free); since both conditions fail for even m, it returns m + 1 in every case.

    lines 21–26

      have h3 : m % 4 ≠ 3 := by obtain ⟨k, rfl⟩ := hm; omega
      have h1 : m % 4 ≠ 1 := by obtain ⟨k, rfl⟩ := hm; omega
      cases delta with
      | free => simpa [spider_blocked_val] using h1
      | inward => simp [spider_blocked_val, h3]
      | outward => simp [spider_blocked_val, h1]
  4. When both boundary conditions agree on beta ∈ {inward, outward}, spider_rho h beta beta = h % 2.

    Evaluating the definition of spider_rho when both boundary arguments are identical and non-free simplifies directly to h % 2.

    line 31

      rcases hβ with rfl | rfl <;> simp [spider_rho]
  5. When delta ≠ beta are distinct non-free leg ends and h is odd, spider_rho h delta beta = 0.

    Evaluating spider_rho when delta ≠ beta and h is odd satisfies neither the diagonal equality case nor the condition that h is even and at least 2, giving 0.

    line 37

      rcases hβ with rfl | rfl <;> rcases hδ with rfl | rfl <;> simp_all [spider_rho]
  6. When delta ≠ beta are distinct non-free leg ends, h is even, and h ≥ 2, spider_rho h delta beta = 1.

    Evaluating spider_rho when delta ≠ beta and h is even with h ≥ 2 satisfies the branch condition h ≥ 2 ∧ h % 2 = 0, giving 1.

    line 43

      rcases hβ with rfl | rfl <;> rcases hδ with rfl | rfl <;> simp_all [spider_rho]
  7. When k is even and r is even, k ∈ spider_blocked_optionvals r beta.

    Write k = 2c and r = 2b. Choosing cut index idx = 2c and boundary condition delta = beta, linear arithmetic confirms idx < r - 1 since 2c + 2 ≤ 2b. The remaining length h = 2b - (2c + 1) is odd, so rho(h, beta, beta) = 1. Since 2c is even, the blocked value is 2c + 1. Because 2c + 1 is odd, XORing with 1 subtracts 1, yielding (2c + 1) ^^^ 1 = 2c = k.

    lines 49–60

    uses Nat.even_or_odd, spider_blocked_optionvals_low_mem_mem_of_idx, spider_blocked_optionvals_low_mem_rho_self, spider_blocked_optionvals_low_mem_val_even, Nat.xor_comm, Nat.xor_one_of_odd

      obtain ⟨c, rfl⟩ | ⟨c, rfl⟩ := Nat.even_or_odd k
      · obtain ⟨b, rfl⟩ | ⟨b, rfl⟩ := Nat.even_or_odd r
        · have hidx : c + c < b + b - 1 := by omega
          have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (b + b) (c + c) beta beta hidx hβ
          have hval : spider_rho (b + b - (c + c + 1)) beta beta ^^^ spider_blocked_val beta (c + c)
              = c + c := by
            have hodd : (b + b - (c + c + 1)) % 2 = 1 := by omega
            rw [spider_blocked_optionvals_low_mem_rho_self _ _ hβ, hodd,
              spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩,
              Nat.xor_comm, Nat.xor_one_of_odd ⟨c, by omega⟩]
            omega
          rwa [hval] at hmem
  8. When k is even and r is odd, k ∈ spider_blocked_optionvals r beta.

    Write k = 2c and r = 2b + 1. Choosing cut index idx = 2c and the alternate boundary condition delta ≠ beta, linear arithmetic gives idx < r - 1. The remaining length h = (2b + 1) - (2c + 1) = 2(b - c) is even and at least 2, so rho(h, delta, beta) = 1. XORing with the blocked value 2c + 1 again subtracts 1, giving (2c + 1) ^^^ 1 = 2c = k.

    lines 61–72

    uses spider_blocked_optionvals_low_mem_exists_other, spider_blocked_optionvals_low_mem_mem_of_idx, spider_blocked_optionvals_low_mem_rho_other_even, spider_blocked_optionvals_low_mem_val_even, Nat.xor_comm, Nat.xor_one_of_odd

        · obtain ⟨delta, hδ, hne⟩ := spider_blocked_optionvals_low_mem_exists_other beta hβ
          have hidx : c + c < 2 * b + 1 - 1 := by omega
          have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (2 * b + 1) (c + c) beta delta hidx hδ
          have hval : spider_rho (2 * b + 1 - (c + c + 1)) delta beta
              ^^^ spider_blocked_val delta (c + c) = c + c := by
            have heven : (2 * b + 1 - (c + c + 1)) % 2 = 0 := by omega
            have hge : 2 ≤ 2 * b + 1 - (c + c + 1) := by omega
            rw [spider_blocked_optionvals_low_mem_rho_other_even _ _ _ hβ hδ hne heven hge,
              spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩,
              Nat.xor_comm, Nat.xor_one_of_odd ⟨c, by omega⟩]
            omega
          rwa [hval] at hmem
  9. When k is odd and r is even, k ∈ spider_blocked_optionvals r beta.

    Write k = 2c + 1 and r = 2b. Choosing cut index idx = 2c and the alternate boundary condition delta ≠ beta, the remaining length h = 2b - (2c + 1) is odd, so rho(h, delta, beta) = 0. Since 2c is even, the blocked value is 2c + 1. XORing with 0 preserves 2c + 1, so 0 ^^^ (2c + 1) = 2c + 1 = k.

    lines 73–83

    uses Nat.even_or_odd, spider_blocked_optionvals_low_mem_exists_other, spider_blocked_optionvals_low_mem_mem_of_idx, spider_blocked_optionvals_low_mem_rho_other_odd, spider_blocked_optionvals_low_mem_val_even, Nat.zero_xor

      · obtain ⟨b, rfl⟩ | ⟨b, rfl⟩ := Nat.even_or_odd r
        · obtain ⟨delta, hδ, hne⟩ := spider_blocked_optionvals_low_mem_exists_other beta hβ
          have hidx : c + c < b + b - 1 := by omega
          have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (b + b) (c + c) beta delta hidx hδ
          have hval : spider_rho (b + b - (c + c + 1)) delta beta
              ^^^ spider_blocked_val delta (c + c) = 2 * c + 1 := by
            have hodd : (b + b - (c + c + 1)) % 2 = 1 := by omega
            rw [spider_blocked_optionvals_low_mem_rho_other_odd _ _ _ hβ hδ hne hodd,
              spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩, Nat.zero_xor]
            omega
          rwa [hval] at hmem
  10. When k is odd and r is odd, k ∈ spider_blocked_optionvals r beta, completing the proof.

    Write k = 2c + 1 and r = 2b + 1. Choosing cut index idx = 2c and matching boundary condition delta = beta, the remaining length h = (2b + 1) - (2c + 1) is even, so rho(h, beta, beta) = h % 2 = 0. XORing 0 with the blocked value 2c + 1 gives 2c + 1 = k, which completes the final parity case.

    lines 84–92

    uses spider_blocked_optionvals_low_mem_mem_of_idx, spider_blocked_optionvals_low_mem_rho_self, spider_blocked_optionvals_low_mem_val_even, Nat.zero_xor

        · have hidx : c + c < 2 * b + 1 - 1 := by omega
          have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (2 * b + 1) (c + c) beta beta hidx hβ
          have hval : spider_rho (2 * b + 1 - (c + c + 1)) beta beta
              ^^^ spider_blocked_val beta (c + c) = 2 * c + 1 := by
            have heven : (2 * b + 1 - (c + c + 1)) % 2 = 0 := by omega
            rw [spider_blocked_optionvals_low_mem_rho_self _ _ hβ, heven,
              spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩, Nat.zero_xor]
            omega
          rwa [hval] at hmem
List.mem_append_left
If an element belongs to a list as, it belongs to the concatenation as ++ bs.
List.mem_flatMap.mpr
An element belongs to the flat-mapping of a function over a list if it belongs to the function's value at some element of the list.
List.mem_range.mpr
A natural number belongs to List.range n if and only if it is strictly less than n.
List.mem_map.mpr
An element y belongs to List.map f xs if y = f x for some x in xs.
Or.inr
A disjunction holds if its right disjunct holds.
Or.inl
A disjunction holds if its left disjunct holds.
Nat.even_or_odd
Every natural number is either even or odd.
spider_blocked_optionvals_low_mem_mem_of_idx
For any cut index idx < r - 1 and boundary condition delta in {inward, outward}, the resulting interior cut value belongs to the blocked leg's options list.
spider_blocked_optionvals_low_mem_exists_other
For any boundary condition beta in {inward, outward}, there exists a distinct boundary condition delta in {inward, outward}.
spider_blocked_optionvals_low_mem_val_even
For any leg end delta and any even natural number m, val(delta, m) = m + 1.
spider_blocked_optionvals_low_mem_rho_self
When both boundary conditions agree and are non-free, rho(h, beta, beta) = h mod 2.
spider_blocked_optionvals_low_mem_rho_other_odd
When delta and beta are distinct non-free leg ends and h is odd, rho(h, delta, beta) = 0.
spider_blocked_optionvals_low_mem_rho_other_even
When delta and beta are distinct non-free leg ends, h is even, and h ≥ 2, rho(h, delta, beta) = 1.
Nat.xor_comm
Bitwise XOR on natural numbers is commutative.
Nat.xor_one_of_odd
For any odd natural number n, bitwise XOR with 1 subtracts 1: n ^^^ 1 = n - 1.
Nat.zero_xor
Bitwise XOR with 0 is the identity: 0 ^^^ x = x.

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_low_mem_mem_of_idx (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  unfold spider_blocked_optionvals  refine List.mem_append_left _ (List.mem_append_left _ ?_)  refine List.mem_flatMap.mpr ⟨idx, List.mem_range.mpr hidx, ?_⟩  rcases hδ with rfl | rfl  · exact List.mem_map.mpr ⟨_, by simp, rfl⟩  · exact List.mem_map.mpr ⟨_, by simp, rfl⟩lemma spider_blocked_optionvals_low_mem_exists_other (beta : SpiderLegEnd)    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward) :    ∃ delta, (delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward) ∧ delta ≠ beta := by  rcases hβ with rfl | rfl  · exact ⟨SpiderLegEnd.outward, Or.inr rfl, by simp⟩  · exact ⟨SpiderLegEnd.inward, Or.inl rfl, by simp⟩lemma spider_blocked_optionvals_low_mem_val_even (delta : SpiderLegEnd) (m : ℕ)    (hm : Even m) : spider_blocked_val delta m = m + 1 := by  have h3 : m % 4 ≠ 3 := by obtain ⟨k, rfl⟩ := hm; omega  have h1 : m % 4 ≠ 1 := by obtain ⟨k, rfl⟩ := hm; omega  cases delta with  | free => simpa [spider_blocked_val] using h1  | inward => simp [spider_blocked_val, h3]  | outward => simp [spider_blocked_val, h1]lemma spider_blocked_optionvals_low_mem_rho_self (h : ℕ) (beta : SpiderLegEnd)    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward) :    spider_rho h beta beta = h % 2 := by  rcases hβ with rfl | rfl <;> simp [spider_rho]lemma spider_blocked_optionvals_low_mem_rho_other_odd (h : ℕ) (delta beta : SpiderLegEnd)    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward)    (hδ : delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward) (hne : delta ≠ beta)    (hodd : h % 2 = 1) : spider_rho h delta beta = 0 := by  rcases hβ with rfl | rfl <;> rcases hδ with rfl | rfl <;> simp_all [spider_rho]lemma spider_blocked_optionvals_low_mem_rho_other_even (h : ℕ) (delta beta : SpiderLegEnd)    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward)    (hδ : delta = SpiderLegEnd.inward ∨ delta = SpiderLegEnd.outward) (hne : delta ≠ beta)    (heven : h % 2 = 0) (hge : 2 ≤ h) : spider_rho h delta beta = 1 := by  rcases hβ with rfl | rfl <;> rcases hδ with rfl | rfl <;> simp_all [spider_rho]/-- Coverage of the lower part [0, r-2] by the interior cuts of the blocked leg. -/theorem spider_blocked_optionvals_low_mem (r k : ℕ) (hr : 2 ≤ r) (beta : SpiderLegEnd)    (hβ : beta = SpiderLegEnd.inward ∨ beta = SpiderLegEnd.outward) (hk : k + 2 ≤ r) :    k ∈ spider_blocked_optionvals r beta := by  obtain ⟨c, rfl⟩ | ⟨c, rfl⟩ := Nat.even_or_odd k  · obtain ⟨b, rfl⟩ | ⟨b, rfl⟩ := Nat.even_or_odd r    · have hidx : c + c < b + b - 1 := by omega      have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (b + b) (c + c) beta beta hidx hβ      have hval : spider_rho (b + b - (c + c + 1)) beta beta ^^^ spider_blocked_val beta (c + c)          = c + c := by        have hodd : (b + b - (c + c + 1)) % 2 = 1 := by omega        rw [spider_blocked_optionvals_low_mem_rho_self _ _ hβ, hodd,          spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩,          Nat.xor_comm, Nat.xor_one_of_odd ⟨c, by omega⟩]        omega      rwa [hval] at hmem    · obtain ⟨delta, hδ, hne⟩ := spider_blocked_optionvals_low_mem_exists_other beta hβ      have hidx : c + c < 2 * b + 1 - 1 := by omega      have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (2 * b + 1) (c + c) beta delta hidx hδ      have hval : spider_rho (2 * b + 1 - (c + c + 1)) delta beta          ^^^ spider_blocked_val delta (c + c) = c + c := by        have heven : (2 * b + 1 - (c + c + 1)) % 2 = 0 := by omega        have hge : 2 ≤ 2 * b + 1 - (c + c + 1) := by omega        rw [spider_blocked_optionvals_low_mem_rho_other_even _ _ _ hβ hδ hne heven hge,          spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩,          Nat.xor_comm, Nat.xor_one_of_odd ⟨c, by omega⟩]        omega      rwa [hval] at hmem  · obtain ⟨b, rfl⟩ | ⟨b, rfl⟩ := Nat.even_or_odd r    · obtain ⟨delta, hδ, hne⟩ := spider_blocked_optionvals_low_mem_exists_other beta hβ      have hidx : c + c < b + b - 1 := by omega      have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (b + b) (c + c) beta delta hidx hδ      have hval : spider_rho (b + b - (c + c + 1)) delta beta          ^^^ spider_blocked_val delta (c + c) = 2 * c + 1 := by        have hodd : (b + b - (c + c + 1)) % 2 = 1 := by omega        rw [spider_blocked_optionvals_low_mem_rho_other_odd _ _ _ hβ hδ hne hodd,          spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩, Nat.zero_xor]        omega      rwa [hval] at hmem    · have hidx : c + c < 2 * b + 1 - 1 := by omega      have hmem := spider_blocked_optionvals_low_mem_mem_of_idx (2 * b + 1) (c + c) beta beta hidx hβ      have hval : spider_rho (2 * b + 1 - (c + c + 1)) beta beta          ^^^ spider_blocked_val beta (c + c) = 2 * c + 1 := by        have heven : (2 * b + 1 - (c + c + 1)) % 2 = 0 := by omega        rw [spider_blocked_optionvals_low_mem_rho_self _ _ hβ, heven,          spider_blocked_optionvals_low_mem_val_even _ _ ⟨c, rfl⟩, Nat.zero_xor]        omega      rwa [hval] at hmem
See it in the graphDiscuss this resultChallenge it