spider_blocked_optionvals_low_mem
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.
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.
uses
List.mem_append_left,List.mem_flatMap.mpr,List.mem_range.mpr,List.mem_map.mprunfold 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⟩
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.
uses
Or.inr,Or.inlrcases hβ with rfl | rfl · exact ⟨SpiderLegEnd.outward, Or.inr rfl, by simp⟩ · exact ⟨SpiderLegEnd.inward, Or.inl rfl, by simp⟩
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.
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]
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.
rcases hβ with rfl | rfl <;> simp [spider_rho]
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.
rcases hβ with rfl | rfl <;> rcases hδ with rfl | rfl <;> simp_all [spider_rho]
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.
rcases hβ with rfl | rfl <;> rcases hδ with rfl | rfl <;> simp_all [spider_rho]
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.
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_oddobtain ⟨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
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.
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
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.
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
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.
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.
- Linear arithmetic inequalities and parity conditions (such as the index bound idx < r - 1 and the parity of r - (idx + 1)) are verified automatically by omega throughout the proof.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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