spider_blocked_optionvals_top_mem
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.
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.
uses
List.mem_appendhave 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
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.
uses
List.mem_appendhave 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
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.
uses
List.mem_append.mpr,Or.inl,List.mem_flatMap.mpr,List.mem_range.mpr,List.mem_map.mprsimp 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
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.
simp [spider_rho, hodd]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.
simp [spider_rho, hodd]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.
uses
spider_blocked_optionvals_top_mem_mem_flatMap,Or.inr,spider_blocked_optionvals_top_mem_rho_outward_inward_odd,if_neg,Nat.zero_xorhave 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
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.
uses
spider_blocked_optionvals_top_mem_mem_flatMap,Or.inl,spider_blocked_optionvals_top_mem_rho_inward_outward_odd,if_neg,Nat.zero_xorhave 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
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.
rcases hβ with rfl | rfl
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.
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)
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.
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.
- The base cases for r = 1 are closed automatically by Lean's decide tactic via direct computational evaluation of the definitions.
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_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