cycle_power_dyadic_tight_class_middle_parent
Equality in the uniform dyadic class weight bound forces each selected middle-quarter position to have its matched outer-quarter parent selected.
Statement
theorem cycle_power_dyadic_tight_class_middle_parent (k : ℕ) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight (k + 2) b = (range (2 ^ (k + 2))).sum (fun i => (b i).toNat)) : (∀ a, 2 ^ k ≤ a → a < 2 ^ (k + 1) → b a = true → b (a + 2 ^ (k + 1)) = true) ∧ (∀ a, 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k → b a = true → b (a - 2 ^ (k + 1)) = true)
- Source
- Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635, Section 3. These conditional class-system and pruning lemmas do not establish the unresolved graph covering bound. The earlier fixed-radius helpers handle radii eight and sixteen; this session works with arbitrary dyadic radii. No research advance is claimed.
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- cycle_power_dyadic_tight_class_pruneDeleting a tight dyadic class's middle two quarters and compressing the remaining outer quarters preserves equality between its dyadic…
- Used by 9
- cycle_power_dyadic_prune_single_distance_coverDeleting and compressing the middle quarters preserves coverage at one fixed distance d below the new radius, using only original coverage…
- cycle_power_dyadic_no_island_no_long_prefixConditional shape-model half-width theorem: a class with an initial selected interval extending strictly beyond half the radius cannot…
- cycle_power_dyadic_neighbour_pair_count_top_boundThe largest neighbour pair count of a tight rooted class is controlled by its middle-quarter leaves and the two central bits.
- cycle_power_dyadic_half_owner_order_of_middle_full_pruneIf selected middle bits force full prunes and the retained outer quarters are monotone toward the endpoints, then coverage only at the…
- cycle_power_dyadic_no_island_middle_imp_full_pruneIf a tight dyadic two-interval class contains any middle-quarter vertex, deleting the middle two quarters leaves a full smaller class.…
- cycle_power_dyadic_half_monotone_of_middle_full_pruneOne uniform induction step: if all middle marks have full prunes and both retained outer quarters are monotone toward their endpoints,…
- cycle_power_dyadic_prune_coverDeleting each tight dyadic class's middle two quarters and compressing its outer quarters preserves coverage of all distances smaller than…
- cycle_power_dyadic_prune_count_balanceTight dyadic classes with constant active count t+1 and exact half-distance coverage satisfy the exact pruning balance…
- cycle_power_dyadic_tight_class_parentEquality in the dyadic class weight bound forces all rooted-tree parent implications at every smaller dyadic scale, uniformly in the arc…
The proof, explained
With L = 2^k, the domain of length 4L splits into four quarters of size L. By pruning tightness down one dimension and applying the dyadic class weight recurrence, the total weight identity forces the sum of all cross-terms b(i) ∧ b(i + 2L) to equal the sum of b over the two middle quarters [L, 2L) and [2L, 3L). Because each cross term is bounded above by the corresponding middle-quarter term, this sum equality forces pointwise equality everywhere. Consequently, if b is true at any middle-quarter index, its matched parent in the corresponding outer quarter must also be true.
Express the intermediate scale 2^(k+1) and full scale 2^(k+2) in terms of the quarter-block length L = 2^k.
Defining L = 2^k, arithmetic of powers of two shows 2^(k+1) = 2L = L + L and 2^(k+2) = 4L.
uses
pow_succ,pow_addlet L := 2 ^ k have hH : 2 ^ (k + 1) = L + L := by dsimp [L]; rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 4 * L := by dsimp [L]; rw [pow_add]; norm_num; omega
The sum of the lifted bit-vector over [0, 2L) equals the sum of b over the first quarter [0, L) plus the fourth quarter [3L, 4L).
Decomposing the range 2L into two blocks of length L via sum_range_add, the lifted bit-vector cycle_power_dyadic_b_lift evaluates to b(i) on the first block i < L (since i < 2^k), and evaluates to b((L + i) + 2L) = b(3L + i) on the second block L + i (since L + i ≥ 2^k).
uses
sum_range_add,sum_congr,if_pos,if_neghave hlift : (range (2 ^ (k + 1))).sum (fun i => (cycle_power_dyadic_b_lift k b i).toNat) = (range L).sum (fun i => (b i).toNat) + (range L).sum (fun i => (b (3 * L + i)).toNat) := by rw [hH, sum_range_add] congr 1 · apply sum_congr rfl intro i hi dsimp [cycle_power_dyadic_b_lift] rw [if_pos (show i < 2 ^ k from mem_range.mp hi)] · apply sum_congr rfl intro i hi dsimp [cycle_power_dyadic_b_lift] rw [if_neg (show ¬L + i < 2 ^ k by dsimp [L]; omega)] have he : L + i + 2 ^ (k + 1) = 3 * L + i := by omega rw [he]
The sum of the cross terms b(i) ∧ b(i + 2L) over i < 2L splits into the sum over the first quarter and the sum over the second quarter.
Splitting the range 2L into [0, L) and [L, 2L) using sum_range_add, the terms on the second block become b(L + i) ∧ b(L + i + 2L) = b(L + i) ∧ b(3L + i).
uses
sum_range_add,sum_congrhave hcross : (range (2 ^ (k + 1))).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) = (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) + (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) := by rw [hH, sum_range_add] congr 1 apply sum_congr rfl intro i hi have he : L + i + (L + L) = 3 * L + i := by omega rw [he]
The sum of b over the full domain [0, 4L) decomposes into the sum over the four quarter blocks of length L.
Rewriting 2^(k+2) as 4L and invoking cycle_power_dyadic_sum_range_four_blocks splits the sum over range (4 * L) into the four consecutive blocks starting at 0, L, 2L, and 3L.
uses
cycle_power_dyadic_sum_range_four_blockshave hfull : (range (2 ^ (k + 2))).sum (fun i => (b i).toNat) = (range L).sum (fun i => (b i).toNat) + (range L).sum (fun i => (b (L + i)).toNat) + (range L).sum (fun i => (b (2 * L + i)).toNat) + (range L).sum (fun i => (b (3 * L + i)).toNat) := by rw [hD] exact cycle_power_dyadic_sum_range_four_blocks L (fun i => (b i).toNat)
The sum of the two cross-term blocks equals the sum of b over the two middle quarters [L, 2L) and [2L, 3L).
Tightness at scale k + 2 transfers to tightness of the lift at scale k + 1 by cycle_power_dyadic_tight_class_prune, and the weight recurrence cycle_power_dyadic_class_weight_succ equates the total weight to the lifted weight plus the cross-term sum. Subtracting the lifted sum (quarters 0 and 3) from the full sum (quarters 0, 1, 2, 3) leaves the cross terms equal to the sum of quarters 1 and 2.
uses
cycle_power_dyadic_tight_class_prune,cycle_power_dyadic_class_weight_succhave hsmall := cycle_power_dyadic_tight_class_prune k b htight have hsplit := cycle_power_dyadic_class_weight_succ k b have hsum : (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) + (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) = (range L).sum (fun i => (b (2 * L + i)).toNat) + (range L).sum (fun i => (b (L + i)).toNat) := by omega
Each cross-term block sum is bounded above by the corresponding middle-quarter block sum.
Pointwise, (b(i) ∧ b(2L + i)) ≤ b(2L + i) and (b(L + i) ∧ b(3L + i)) ≤ b(L + i) by the basic bounds on boolean conjunction. Summing over range L via sum_le_sum bounds each cross-term block sum by its respective middle-quarter block sum.
uses
cycle_power_dyadic_bool_and_toNat_le_right,cycle_power_dyadic_bool_and_toNat_le_left,sum_le_sumhave hle0 : ∀ i ∈ range L, (b i && b (i + 2 ^ (k + 1))).toNat ≤ (b (2 * L + i)).toNat := by intro i hi have he : i + 2 ^ (k + 1) = 2 * L + i := by omega rw [he] exact cycle_power_dyadic_bool_and_toNat_le_right _ _ have hle1 : ∀ i ∈ range L, (b (L + i) && b (3 * L + i)).toNat ≤ (b (L + i)).toNat := by intro i hi exact cycle_power_dyadic_bool_and_toNat_le_left _ _ have hs0 := sum_le_sum hle0 have hs1 := sum_le_sum hle1
Both block-level inequalities are equalities, which implies pointwise equality for every index i < L.
Since the sum of the two cross-term blocks equals the sum of the two middle-quarter blocks, neither individual inequality can be strict; both block sums must equal their upper bounds. By sum_eq_sum_iff_of_le, equality of sums with pointwise inequalities forces pointwise equality: (b(i) ∧ b(2L + i)) = b(2L + i) and (b(L + i) ∧ b(3L + i)) = b(L + i) for every i < L.
uses
sum_eq_sum_iff_of_lehave he0 : (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) = (range L).sum (fun i => (b (2 * L + i)).toNat) := by omega have he1 : (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) = (range L).sum (fun i => (b (L + i)).toNat) := by omega have heq0 := (sum_eq_sum_iff_of_le hle0).mp he0 have heq1 := (sum_eq_sum_iff_of_le hle1).mp he1
For boolean values, if a conjunction equals one of its operands and that operand is true, the other operand must also be true.
Two truth-table facts are recorded: if (a ∧ b) = b and b = true, then a = true; and if (a ∧ b) = a and a = true, then b = true. Both are verified by finite case checking.
have hbool0 : ∀ a b : Bool, (a && b).toNat = b.toNat → b = true → a = true := by decide have hbool1 : ∀ a b : Bool, (a && b).toNat = a.toNat → a = true → b = true := by decide
Any selected position in the second quarter [L, 2L) forces its matched parent in the fourth quarter [3L, 4L) to be selected.
Given a ∈ [L, 2L) with b(a) = true, set i = a - L < L. The pointwise equality on the second block gives b(a) ∧ b(a + 2L) = b(a). Since b(a) = true, the boolean implication forces b(a + 2L) = true.
constructor · intro a ha0 ha1 hab have hi : a - L < L := by omega have he := heq1 (a - L) (mem_range.mpr hi) have hei : L + (a - L) = a := by omega have hep : 3 * L + (a - L) = a + 2 ^ (k + 1) := by omega rw [hei, hep] at he exact hbool1 _ _ he hab
Any selected position in the third quarter [2L, 3L) forces its matched parent in the first quarter [0, L) to be selected.
Given a ∈ [2L, 3L) with b(a) = true, set i = a - 2L < L. The pointwise equality on the first block gives b(a - 2L) ∧ b(a) = b(a). Since b(a) = true, the boolean implication forces b(a - 2L) = true.
· intro a ha0 ha1 hab have hi : a - 2 ^ (k + 1) < L := by omega have he := heq0 (a - 2 ^ (k + 1)) (mem_range.mpr hi) have hei : a - 2 ^ (k + 1) + 2 ^ (k + 1) = a := by omega have hep : 2 * L + (a - 2 ^ (k + 1)) = a := by omega rw [hei, hep] at he exact hbool0 _ _ he hab
pow_succ- For any element a of a monoid, a^(n + 1) = a^n * a.
pow_add- For any element a of a monoid, a^(m + n) = a^m * a^n.
sum_range_add- The sum of a function over Finset.range (n + m) splits into the sum over Finset.range n plus the sum of the shifted function over Finset.range m.
sum_congr- Two finite sums over equal index sets are equal if their terms agree at every index in the set.
if_pos- An if-then-else expression evaluates to its then branch when the condition is true.
if_neg- An if-then-else expression evaluates to its else branch when the condition is false.
cycle_power_dyadic_sum_range_four_blocks- A sum over Finset.range (4 * L) decomposes into the sum of four consecutive blocks of length L.
cycle_power_dyadic_tight_class_prune- Tightness of the dyadic class weight bound at scale k + 2 implies tightness for the lifted bit-vector at scale k + 1.
cycle_power_dyadic_class_weight_succ- The dyadic class weight at scale k + 2 equals the weight of its lift at scale k + 1 plus the sum of cross-term conjunctions b(i) ∧ b(i + 2^(k+1)) over i < 2^(k+1).
cycle_power_dyadic_bool_and_toNat_le_right- The natural number value of a boolean conjunction x ∧ y is at most the natural number value of y.
cycle_power_dyadic_bool_and_toNat_le_left- The natural number value of a boolean conjunction x ∧ y is at most the natural number value of x.
sum_le_sum- If f(i) ≤ g(i) pointwise for all i in a finite set s, then the sum of f over s is at most the sum of g over s.
sum_eq_sum_iff_of_le- Given f(i) ≤ g(i) pointwise for all i in a finite set s, the sum of f over s equals the sum of g over s if and only if f(i) = g(i) holds pointwise for all i ∈ s.
- The cancellation from the weight recurrence and pruning to deduce equality between cross-term sums and middle-quarter block sums (lines 50–54 and 67–72) is handled by linear arithmetic automation (`omega`).
- The truth-table implications for boolean conjunctions (lines 75–76) are dispatched automatically by finite case exhaustion (`decide`).
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 Finsettheorem cycle_power_dyadic_tight_class_middle_parent (k : ℕ) (b : ℕ → Bool) (htight : cycle_power_dyadic_class_weight (k + 2) b = (range (2 ^ (k + 2))).sum (fun i => (b i).toNat)) : (∀ a, 2 ^ k ≤ a → a < 2 ^ (k + 1) → b a = true → b (a + 2 ^ (k + 1)) = true) ∧ (∀ a, 2 ^ (k + 1) ≤ a → a < 3 * 2 ^ k → b a = true → b (a - 2 ^ (k + 1)) = true) := by let L := 2 ^ k have hH : 2 ^ (k + 1) = L + L := by dsimp [L]; rw [pow_succ]; omega have hD : 2 ^ (k + 2) = 4 * L := by dsimp [L]; rw [pow_add]; norm_num; omega have hlift : (range (2 ^ (k + 1))).sum (fun i => (cycle_power_dyadic_b_lift k b i).toNat) = (range L).sum (fun i => (b i).toNat) + (range L).sum (fun i => (b (3 * L + i)).toNat) := by rw [hH, sum_range_add] congr 1 · apply sum_congr rfl intro i hi dsimp [cycle_power_dyadic_b_lift] rw [if_pos (show i < 2 ^ k from mem_range.mp hi)] · apply sum_congr rfl intro i hi dsimp [cycle_power_dyadic_b_lift] rw [if_neg (show ¬L + i < 2 ^ k by dsimp [L]; omega)] have he : L + i + 2 ^ (k + 1) = 3 * L + i := by omega rw [he] have hcross : (range (2 ^ (k + 1))).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) = (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) + (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) := by rw [hH, sum_range_add] congr 1 apply sum_congr rfl intro i hi have he : L + i + (L + L) = 3 * L + i := by omega rw [he] have hfull : (range (2 ^ (k + 2))).sum (fun i => (b i).toNat) = (range L).sum (fun i => (b i).toNat) + (range L).sum (fun i => (b (L + i)).toNat) + (range L).sum (fun i => (b (2 * L + i)).toNat) + (range L).sum (fun i => (b (3 * L + i)).toNat) := by rw [hD] exact cycle_power_dyadic_sum_range_four_blocks L (fun i => (b i).toNat) have hsmall := cycle_power_dyadic_tight_class_prune k b htight have hsplit := cycle_power_dyadic_class_weight_succ k b have hsum : (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) + (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) = (range L).sum (fun i => (b (2 * L + i)).toNat) + (range L).sum (fun i => (b (L + i)).toNat) := by omega have hle0 : ∀ i ∈ range L, (b i && b (i + 2 ^ (k + 1))).toNat ≤ (b (2 * L + i)).toNat := by intro i hi have he : i + 2 ^ (k + 1) = 2 * L + i := by omega rw [he] exact cycle_power_dyadic_bool_and_toNat_le_right _ _ have hle1 : ∀ i ∈ range L, (b (L + i) && b (3 * L + i)).toNat ≤ (b (L + i)).toNat := by intro i hi exact cycle_power_dyadic_bool_and_toNat_le_left _ _ have hs0 := sum_le_sum hle0 have hs1 := sum_le_sum hle1 have he0 : (range L).sum (fun i => (b i && b (i + 2 ^ (k + 1))).toNat) = (range L).sum (fun i => (b (2 * L + i)).toNat) := by omega have he1 : (range L).sum (fun i => (b (L + i) && b (3 * L + i)).toNat) = (range L).sum (fun i => (b (L + i)).toNat) := by omega have heq0 := (sum_eq_sum_iff_of_le hle0).mp he0 have heq1 := (sum_eq_sum_iff_of_le hle1).mp he1 have hbool0 : ∀ a b : Bool, (a && b).toNat = b.toNat → b = true → a = true := by decide have hbool1 : ∀ a b : Bool, (a && b).toNat = a.toNat → a = true → b = true := by decide constructor · intro a ha0 ha1 hab have hi : a - L < L := by omega have he := heq1 (a - L) (mem_range.mpr hi) have hei : L + (a - L) = a := by omega have hep : 3 * L + (a - L) = a + 2 ^ (k + 1) := by omega rw [hei, hep] at he exact hbool1 _ _ he hab · intro a ha0 ha1 hab have hi : a - 2 ^ (k + 1) < L := by omega have he := heq0 (a - 2 ^ (k + 1)) (mem_range.mpr hi) have hei : a - 2 ^ (k + 1) + 2 ^ (k + 1) = a := by omega have hep : 2 * L + (a - 2 ^ (k + 1)) = a := by omega rw [hei, hep] at he exact hbool0 _ _ he hab