cycle_power_dyadic_class_weight_dilate
Duplicating each membership bit of a dyadic class doubles its dyadic class weight, when the original radius is at least two.
Statement
theorem cycle_power_dyadic_class_weight_dilate (m : ℕ) (hm : 1 ≤ m) (c : ℕ → Bool) : cycle_power_dyadic_class_weight (m + 1) (fun j => c (j / 2)) = 2 * cycle_power_dyadic_class_weight m c
- 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 2
- cycle_power_sum_range_doubleA sum over the first 2n indices equals the sum over n consecutive even-odd pairs.
- 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.
- Used by 2
- cycle_power_dyadic_no_island_of_alternating_pairedUniform induction step for the no-island class shape. Let m ≥ 1 and suppose every tight, exactly dyadically covered, fully ordinarily…
- is_eventual_period_constEvery constant sequence of Booleans has eventual period 1.
The proof, explained
The theorem establishes that dilating a Boolean sequence c by duplicating each bit (replacing c(j) with c(⌊j/2⌋)) doubles its dyadic class weight when m ≥ 1. The proof writes m = k + 1 and breaks the weight into a boundary term and a double sum over dyadic scales and offsets. At scale j + 1, grouping consecutive even and odd indices (2i and 2i + 1) shows that division by 2 collapses both terms to the same original summand at scale j, extracting a factor of 2. Combining this doubled sum with the boundary term confirms that the overall weight doubles.
We can reparameterize m as k + 1 for some k ∈ ℕ.
Since 1 ≤ m, there is some k such that m = k + 1. We replace m by k + 1 throughout the goal, so the dilated dimension is m + 1 = k + 2.
uses
Nat.exists_eq_add_of_leobtain ⟨k, hk⟩ := Nat.exists_eq_add_of_le hm have hmk : m = k + 1 := by omega clear hk subst m
Powers of 2 satisfy 2^(j + 1) = 2 * 2^j for all j ∈ ℕ.
This rewrites 2^(j + 1) as 2^j * 2 using pow_succ and applies commutativity of multiplication.
uses
pow_succhave hpow (j : ℕ) : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega
Integer division by 2 maps the extremal index of the dilated class to that of the original class: (2^(k + 2) - 1) / 2 = 2^(k + 1) - 1.
Using 2^(k + 2) = 2 * 2^(k + 1) and the positivity of 2^(k + 1), integer division of the odd integer 2 * 2^(k + 1) - 1 by 2 truncates down to 2^(k + 1) - 1.
uses
Nat.two_pow_poshave hroot : (2 ^ (k + 1 + 1) - 1) / 2 = 2 ^ (k + 1) - 1 := by have hp := hpow (k + 1) have : 0 < 2 ^ (k + 1) := Nat.two_pow_pos _ omega
The scale sum for the dilated sequence reduces to a sum over shifted scales x + 1 for x ∈ {0, ..., k}.
Using sum_range_succ', the sum over scales j ∈ {0, ..., k + 1} is split into the j = 0 term and the terms j = x + 1 for x < k + 1. The j = 0 term is eliminated because the summand's if-condition explicitly evaluates to 0 at index 0.
uses
sum_range_succ',Nat.add_eq_zero_iff,one_ne_zero,and_false,add_zerohave hsum : (range (k + 1 + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (c (i / 2) && c ((i + 2 ^ (k + 1 + 1) - 2 ^ j) / 2)).toNat)) = 2 * (c 0 && c (2 ^ (k + 1) - 1)).toNat + 2 * (range (k + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat)) := by have hn : k + 1 + 1 = (k + 1) + 1 := by omega rw [hn, sum_range_succ'] simp only [Nat.add_eq_zero_iff, one_ne_zero, and_false, ↓reduceIte, add_zero]
At each scale j < k + 1, the inner sum of length 2^(j + 1) for the dilated sequence equals twice the original inner sum of length 2^j.
Using cycle_power_sum_range_double, the sum of length 2^(j + 1) is grouped into adjacent even (2i) and odd (2i + 1) pairs for i < 2^j. Because integer division by 2 satisfies 2i / 2 = i and (2i + 1) / 2 = i, and similarly (2i + 2^(k + 2) - 2^(j + 1)) / 2 = (2i + 1 + 2^(k + 2) - 2^(j + 1)) / 2 = i + 2^(k + 1) - 2^j, both terms in each pair are equal to c(i) && c(i + 2^(k + 1) - 2^j). Adding them yields 2 * (c(i) && c(i + 2^(k + 1) - 2^j)).
uses
cycle_power_sum_range_double,mul_sum,sum_congr,Nat.pow_le_pow_righthave hterm : ∀ j < k + 1, (range (2 ^ (j + 1))).sum (fun i => (c (i / 2) && c ((i + 2 ^ (k + 1 + 1) - 2 ^ (j + 1)) / 2)).toNat) = 2 * (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat) := by intro j hj rw [hpow j, cycle_power_sum_range_double, mul_sum] apply sum_congr rfl intro i hi have hjk : 2 ^ j ≤ 2 ^ (k + 1) := Nat.pow_le_pow_right (by decide) (by omega) have hp0 := hpow (k + 1) have hp1 := hpow j have hdiv0 : (2 * i + 2 ^ (k + 1 + 1) - 2 * 2 ^ j) / 2 = i + 2 ^ (k + 1) - 2 ^ j := by omega have hdiv1 : (2 * i + 1 + 2 ^ (k + 1 + 1) - 2 * 2 ^ j) / 2 = i + 2 ^ (k + 1) - 2 ^ j := by omega have hd0 : 2 * i / 2 = i := by omega have hd1 : (2 * i + 1) / 2 = i := by omega rw [hdiv0, hdiv1, hd0, hd1] omega
Summing over all scales, the dilated sum equals the sum of twice the original scale sums.
By sum_congr, we replace each dilated scale term at j + 1 by 2 times the corresponding original scale term at j.
uses
sum_congrhave ht := sum_congr (s₁ := range (k + 1)) (s₂ := range (k + 1)) rfl (fun j hj => hterm j (mem_range.mp hj))
The original conditioned scale sum over j ∈ {0, ..., k} equals the unconditioned sum over shifted scales j ∈ {1, ..., k}.
Peeling off the j = 0 term with sum_range_succ', which vanishes due to the if-condition, leaves the unconditioned sum over scales j + 1 for j < k.
uses
sum_range_succ'have hzero : (range (k + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat)) = (range k).sum (fun j => (range (2 ^ (j + 1))).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ (j + 1))).toNat)) := by rw [show k + 1 = k + 1 by omega, sum_range_succ'] simp
The unconditioned sum over all scales j ∈ {0, ..., k} splits into its j = 0 term, (c 0 && c (2^(k + 1) - 1)), plus the shifted sum over j ∈ {1, ..., k}.
Using sum_range_succ', the j = 0 term is separated. At j = 0, the inner sum has range 2^0 = 1, which evaluates solely at i = 0 to (c 0 && c (2^(k + 1) - 1)). The remaining terms are scales j + 1 for j < k.
uses
sum_range_succ',pow_zero,sum_range_one,zero_addhave hB : (range (k + 1)).sum (fun j => (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat)) = (c 0 && c (2 ^ (k + 1) - 1)).toNat + (range k).sum (fun j => (range (2 ^ (j + 1))).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ (j + 1))).toNat)) := by rw [sum_range_succ'] simp only [pow_zero, sum_range_one, zero_add] omega
The dilated scale sum equals 2 * (c 0 && c (2^(k + 1) - 1)) plus twice the original scale sum.
Factoring out the scalar 2 using mul_sum and substituting the decompositions from the previous two steps, algebraic ring simplification establishes the identity.
uses
mul_sumrw [ht, ← mul_sum, hB, hzero] ring
The dyadic class weight of the dilated sequence is twice the original dyadic class weight.
Unfolding the definition of cycle_power_dyadic_class_weight, the boundary term for the dilated sequence evaluates to 2 * (c 0 && c (2^(k + 1) - 1)) via hroot. Combining this with the formula for the scale sum established in hsum, the total weight doubles that of the original sequence.
uses
Nat.zero_divunfold cycle_power_dyadic_class_weight simp only [Nat.zero_div, hroot] rw [hsum] omega
Nat.exists_eq_add_of_le- if m ≤ n, there exists k such that n = m + k
pow_succ- for any base a and natural number n, a^(n + 1) = a^n * a
Nat.two_pow_pos- for any natural number w, 2^w > 0
sum_range_succ'- a sum over {0, ..., n} equals the sum of f(k + 1) for k < n plus f(0)
Nat.add_eq_zero_iff- the sum of two natural numbers is 0 if and only if both numbers are 0
one_ne_zero- 1 is not equal to 0
and_false- the conjunction of any proposition with False is False
add_zero- adding 0 to any element yields the element itself
cycle_power_sum_range_double- a sum over {0, ..., 2n - 1} equals the sum over {0, ..., n - 1} of paired consecutive terms f(2i) + f(2i + 1)
mul_sum- multiplication distributes over a finite sum from the left: a * ∑ i ∈ s, f i = ∑ i ∈ s, a * f i
sum_congr- two finite sums are equal if their index sets are equal and their summands agree on all elements
Nat.pow_le_pow_right- for base n > 0, if i ≤ j then n^i ≤ n^j
pow_zero- any element raised to the power 0 is 1
sum_range_one- the sum of a function over a range of length 1 is its value at 0
zero_add- zero plus any element equals that element
Nat.zero_div- 0 divided by any natural number is 0
- The arithmetic on integer division of natural numbers (such as (2 * i + 1 + 2^(k+2) - 2^(j+1)) / 2 = i + 2^(k+1) - 2^j) is discharged automatically by the omega tactic.
- The definition of cycle_power_dyadic_class_weight includes an explicit boundary term 2 * (c 0 && c (2^m - 1)) as well as a sum over scales j where j = 0 is zeroed out by an if-guard; the proof matches the j = 0 term of the dilated sum with this boundary term.
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_class_weight_dilate (m : ℕ) (hm : 1 ≤ m) (c : ℕ → Bool) : cycle_power_dyadic_class_weight (m + 1) (fun j => c (j / 2)) = 2 * cycle_power_dyadic_class_weight m c := by obtain ⟨k, hk⟩ := Nat.exists_eq_add_of_le hm have hmk : m = k + 1 := by omega clear hk subst m have hpow (j : ℕ) : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega have hroot : (2 ^ (k + 1 + 1) - 1) / 2 = 2 ^ (k + 1) - 1 := by have hp := hpow (k + 1) have : 0 < 2 ^ (k + 1) := Nat.two_pow_pos _ omega have hsum : (range (k + 1 + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (c (i / 2) && c ((i + 2 ^ (k + 1 + 1) - 2 ^ j) / 2)).toNat)) = 2 * (c 0 && c (2 ^ (k + 1) - 1)).toNat + 2 * (range (k + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat)) := by have hn : k + 1 + 1 = (k + 1) + 1 := by omega rw [hn, sum_range_succ'] simp only [Nat.add_eq_zero_iff, one_ne_zero, and_false, ↓reduceIte, add_zero] have hterm : ∀ j < k + 1, (range (2 ^ (j + 1))).sum (fun i => (c (i / 2) && c ((i + 2 ^ (k + 1 + 1) - 2 ^ (j + 1)) / 2)).toNat) = 2 * (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat) := by intro j hj rw [hpow j, cycle_power_sum_range_double, mul_sum] apply sum_congr rfl intro i hi have hjk : 2 ^ j ≤ 2 ^ (k + 1) := Nat.pow_le_pow_right (by decide) (by omega) have hp0 := hpow (k + 1) have hp1 := hpow j have hdiv0 : (2 * i + 2 ^ (k + 1 + 1) - 2 * 2 ^ j) / 2 = i + 2 ^ (k + 1) - 2 ^ j := by omega have hdiv1 : (2 * i + 1 + 2 ^ (k + 1 + 1) - 2 * 2 ^ j) / 2 = i + 2 ^ (k + 1) - 2 ^ j := by omega have hd0 : 2 * i / 2 = i := by omega have hd1 : (2 * i + 1) / 2 = i := by omega rw [hdiv0, hdiv1, hd0, hd1] omega have ht := sum_congr (s₁ := range (k + 1)) (s₂ := range (k + 1)) rfl (fun j hj => hterm j (mem_range.mp hj)) have hzero : (range (k + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat)) = (range k).sum (fun j => (range (2 ^ (j + 1))).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ (j + 1))).toNat)) := by rw [show k + 1 = k + 1 by omega, sum_range_succ'] simp have hB : (range (k + 1)).sum (fun j => (range (2 ^ j)).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ j)).toNat)) = (c 0 && c (2 ^ (k + 1) - 1)).toNat + (range k).sum (fun j => (range (2 ^ (j + 1))).sum (fun i => (c i && c (i + 2 ^ (k + 1) - 2 ^ (j + 1))).toNat)) := by rw [sum_range_succ'] simp only [pow_zero, sum_range_one, zero_add] omega rw [ht, ← mul_sum, hB, hzero] ring unfold cycle_power_dyadic_class_weight simp only [Nat.zero_div, hroot] rw [hsum] omega