cycle_power_dyadic_tight_class_internal_neighbour
Every selected nonendpoint offset of a tight dyadic class has a selected incident dyadic edge at some positive rank below its exponent.
Statement
theorem cycle_power_dyadic_tight_class_internal_neighbour (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight m b = (range (2^m)).sum (fun i => (b i).toNat)) (a : ℕ) (ha₀ : 0 < a) (haD : a < 2^m-1) (hba : b a = true) : ∃ j, 1 ≤ j ∧ j < m ∧ ∃ i < 2^j, b i = true ∧ b (i+2^m-2^j) = true ∧ (a = i ∨ a = i+2^m-2^j)
- Source
- Uniform full-root-gap and current-scale fullness reduction for OP-205 / RT-1 following arXiv:2610.15635. The reusable finite ordered-cover classification formalizes the deficiency-one structure described in arXiv:1103.3693 Corollary 2.5.6. Explicit full-class or middle-fullness hypotheses remain structural assumptions where used; optimal original counts have not been shown to imply them. No graph covering value or research advance is claimed.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- cycle_power_dyadic_class_weightThe weighted number of pairs in a dyadic arc: the endpoint pair has weight two, and distances 2^m-2^j for 1≤j<m have weight one.
- cycle_power_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
- Used by 1
- cycle_power_dyadic_two_full_roots_overlap_emptyIn a tight exact dyadic model, an interior class between full roots zero and g, with g at most the radius, cannot select a vertex in the…
The proof, explained
The proof proceeds by contradiction: suppose an internal selected offset a (with 0 < a < 2^m - 1 and b(a) = true) has no selected incident dyadic partner at any rank 1 ≤ j < m. Modifying b to c by setting c(a) = false preserves the boundary values and leaves every active dyadic pair product unchanged, because any pair incident to a must already have had its other endpoint deselected. Consequently, the dyadic class weight of c is unchanged, while its total number of selected vertices decreases by 1. Since b was tight, this forces weight(c) = sum(c) + 1, contradicting the universal upper bound weight(c) ≤ sum(c).
Assume for contradiction that no dyadic edge incident to a is selected, and define a modified configuration c that deselects a.
We argue by contradiction (by_contra hn), assuming that no rank 1 ≤ j < m and offset i < 2^j have both endpoints selected with a being one of the endpoints. We define c to be identical to b everywhere except at a, where c(a) is set to false.
classical by_contra hn let c : ℕ → Bool := fun i => if i = a then false else b i
The configuration c agrees with b at the endpoints 0 and 2^m - 1.
Because a is an internal offset satisfying 0 < a < 2^m - 1, a is neither 0 nor 2^m - 1. Thus the modification at a does not affect the values at 0 and 2^m - 1, so c(0) = b(0) and c(2^m - 1) = b(2^m - 1).
uses
if_neg,ne_of_gthave he₀ : c 0 = b 0 := by have hne : (0 : ℕ) ≠ a := by omega simp only [c, if_neg hne] have he₁ : c (2^m-1) = b (2^m-1) := by simp [c, ne_of_gt haD]
For every rank 1 ≤ j < m and offset i < 2^j, the dyadic pair product in c equals the dyadic pair product in b.
We consider whether either endpoint of the dyadic pair (i, i + 2^m - 2^j) equals a. If i = a, then since b(a) = true, the contradiction hypothesis requires the other endpoint to have b(i + 2^m - 2^j) = false, so both conjunctions are false. Symmetrically, if the upper endpoint equals a, the lower endpoint must have b(i) = false, so both conjunctions are again false. If neither endpoint is a, then c agrees with b at both endpoints. In all cases, c(i) && c(i + 2^m - 2^j) = b(i) && b(i + 2^m - 2^j).
uses
Bool.eq_false_iff.mpr,Or.inl,Or.inr,Bool.false_and,Bool.and_false,if_pos,if_neghave hpairs : ∀ j, 1 ≤ j → j < m → ∀ i < 2^j, (c i && c (i+2^m-2^j)) = (b i && b (i+2^m-2^j)) := by intro j hj hjm i hi by_cases hia : i = a · have hbi : b i = true := hia.symm ▸ hba have hhigh : b (i+2^m-2^j) = false := by apply Bool.eq_false_iff.mpr intro hbhi exact hn ⟨j, hj, hjm, i, hi, hbi, hbhi, Or.inl hia.symm⟩ have hne : i+2^m-2^j ≠ a := by intro h have := h.symm ▸ hba rw [hhigh] at this contradiction simp only [c, if_pos hia, if_neg hne, hhigh, Bool.false_and, Bool.and_false] · by_cases hhigha : i+2^m-2^j = a · have hbhi : b (i+2^m-2^j) = true := hhigha.symm ▸ hba have hlow : b i = false := by apply Bool.eq_false_iff.mpr intro hbi exact hn ⟨j, hj, hjm, i, hi, hbi, hbhi, Or.inr hhigha.symm⟩ simp only [c, if_neg hia, if_pos hhigha, hlow, Bool.false_and] · simp only [c, if_neg hia, if_neg hhigha]
The dyadic class weight of c equals the dyadic class weight of b.
Unfolding the definition of cycle_power_dyadic_class_weight, the boundary term depends only on the values at 0 and 2^m - 1, which are identical for c and b. In the double sum, the rank j = 0 term is 0, and for each j ≥ 1 the inner sum matches term-by-term by the pair equality established in the previous step.
uses
sum_congr,if_pos,if_neg,mem_range.mphave hweight : cycle_power_dyadic_class_weight m c = cycle_power_dyadic_class_weight m b := by unfold cycle_power_dyadic_class_weight rw [he₀, he₁] congr 1 apply sum_congr rfl intro j hj by_cases hj₀ : j = 0 · simp only [if_pos hj₀] · simp only [if_neg hj₀] apply sum_congr rfl intro i hi rw [hpairs j (by omega) (mem_range.mp hj) i (mem_range.mp hi)]
The total number of selected vertices in c is exactly one less than in b.
Pointwise, c(i).toNat + 1 = b(i).toNat when i = a (since c(a) = 0 and b(a) = 1) and c(i).toNat = b(i).toNat when i ≠ a. Summing this relation over all i < 2^m isolates the single non-zero indicator at a ∈ range(2^m), yielding that the vertex sum for c plus 1 equals the vertex sum for b.
uses
if_neg,add_zero,sum_congr,sum_add_distrib,sum_ite_eq',mem_range.mpr,if_truehave hpoint (i : ℕ) : (c i).toNat + (if i = a then 1 else 0) = (b i).toNat := by by_cases hi : i = a · subst i simp [c, hba] · simp only [c, if_neg hi, add_zero] have hsum : (range (2^m)).sum (fun i => (c i).toNat) + 1 = (range (2^m)).sum (fun i => (b i).toNat) := by have hs := sum_congr rfl (fun i (hi : i ∈ range (2^m)) => hpoint i) simpa only [sum_add_distrib, sum_ite_eq', mem_range.mpr (by omega : a < 2^m), if_true] using hs
A contradiction is reached, completing the proof. automation
By the general upper bound cycle_power_dyadic_class_weight_le, the weight of c is at most its vertex sum. But the tightness hypothesis for b, together with weight invariance and the sum decrease, implies weight(c) = weight(b) = sum(b) = sum(c) + 1. Hence sum(c) + 1 ≤ sum(c), which is impossible. Linear integer arithmetic closes the goal.
uses
cycle_power_dyadic_class_weight_lehave hle := cycle_power_dyadic_class_weight_le m hm c omega
if_neg- An if-then-else expression simplifies to its second branch when the condition is false.
ne_of_gt- In a strict order, if b < a then a ≠ b.
Bool.eq_false_iff.mpr- A boolean variable that is not true must be false.
Or.inl- A disjunction P ∨ Q holds if the left disjunct P holds.
Or.inr- A disjunction P ∨ Q holds if the right disjunct Q holds.
Bool.false_and- The boolean conjunction false && b is false.
Bool.and_false- The boolean conjunction b && false is false.
if_pos- An if-then-else expression simplifies to its first branch when the condition is true.
sum_congr- Two finite sums over the same set are equal if their summands agree at every element.
mem_range.mp- If x is in range(n), then x < n.
add_zero- Adding zero to any element leaves it unchanged (a + 0 = a).
sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of the individual sums.
sum_ite_eq'- Summing a function that is non-zero only at a single element a over a finite set s yields b(a) if a ∈ s, and 0 otherwise.
mem_range.mpr- If x < n, then x is in range(n).
if_true- An if-then-else with condition True evaluates to the first branch.
cycle_power_dyadic_class_weight_le- For any m ≥ 1 and boolean configuration b, the dyadic class weight of b is at most the total count of true values in b.
- Linear integer arithmetic (`omega`) closes the final contradiction by comparing the weight equality and the vertex sum decrease against the general upper bound.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem cycle_power_dyadic_tight_class_internal_neighbour (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight m b = (range (2^m)).sum (fun i => (b i).toNat)) (a : ℕ) (ha₀ : 0 < a) (haD : a < 2^m-1) (hba : b a = true) : ∃ j, 1 ≤ j ∧ j < m ∧ ∃ i < 2^j, b i = true ∧ b (i+2^m-2^j) = true ∧ (a = i ∨ a = i+2^m-2^j) := by classical by_contra hn let c : ℕ → Bool := fun i => if i = a then false else b i have he₀ : c 0 = b 0 := by have hne : (0 : ℕ) ≠ a := by omega simp only [c, if_neg hne] have he₁ : c (2^m-1) = b (2^m-1) := by simp [c, ne_of_gt haD] have hpairs : ∀ j, 1 ≤ j → j < m → ∀ i < 2^j, (c i && c (i+2^m-2^j)) = (b i && b (i+2^m-2^j)) := by intro j hj hjm i hi by_cases hia : i = a · have hbi : b i = true := hia.symm ▸ hba have hhigh : b (i+2^m-2^j) = false := by apply Bool.eq_false_iff.mpr intro hbhi exact hn ⟨j, hj, hjm, i, hi, hbi, hbhi, Or.inl hia.symm⟩ have hne : i+2^m-2^j ≠ a := by intro h have := h.symm ▸ hba rw [hhigh] at this contradiction simp only [c, if_pos hia, if_neg hne, hhigh, Bool.false_and, Bool.and_false] · by_cases hhigha : i+2^m-2^j = a · have hbhi : b (i+2^m-2^j) = true := hhigha.symm ▸ hba have hlow : b i = false := by apply Bool.eq_false_iff.mpr intro hbi exact hn ⟨j, hj, hjm, i, hi, hbi, hbhi, Or.inr hhigha.symm⟩ simp only [c, if_neg hia, if_pos hhigha, hlow, Bool.false_and] · simp only [c, if_neg hia, if_neg hhigha] have hweight : cycle_power_dyadic_class_weight m c = cycle_power_dyadic_class_weight m b := by unfold cycle_power_dyadic_class_weight rw [he₀, he₁] congr 1 apply sum_congr rfl intro j hj by_cases hj₀ : j = 0 · simp only [if_pos hj₀] · simp only [if_neg hj₀] apply sum_congr rfl intro i hi rw [hpairs j (by omega) (mem_range.mp hj) i (mem_range.mp hi)] have hpoint (i : ℕ) : (c i).toNat + (if i = a then 1 else 0) = (b i).toNat := by by_cases hi : i = a · subst i simp [c, hba] · simp only [c, if_neg hi, add_zero] have hsum : (range (2^m)).sum (fun i => (c i).toNat) + 1 = (range (2^m)).sum (fun i => (b i).toNat) := by have hs := sum_congr rfl (fun i (hi : i ∈ range (2^m)) => hpoint i) simpa only [sum_add_distrib, sum_ite_eq', mem_range.mpr (by omega : a < 2^m), if_true] using hs have hle := cycle_power_dyadic_class_weight_le m hm c omega