cycle_power_dyadic_class_weight_parity_split
For any Boolean class b and m >= 1, with D = 2^(m+1): the dyadic class weight of b at exponent m+1, plus [b_0 and b_(D-2)] plus [b_1 and b_(D-1)], equals 2[b_0 and b_(D-1)] plus the weights at exponent m of its even half i -> b_(2i) and of its odd half i -> b_(2i+1). (The even dyadic distances D - 2^j, j >= 1, split by parity into the halves' distances 2^m - 2^(j-1).)
Statement
theorem cycle_power_dyadic_class_weight_parity_split (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) : cycle_power_dyadic_class_weight (m + 1) b + (b 0 && b (2 ^ (m + 1) - 2)).toNat + (b 1 && b (2 ^ (m + 1) - 1)).toNat = 2 * (b 0 && b (2 ^ (m + 1) - 1)).toNat + cycle_power_dyadic_class_weight m (fun i => b (2 * i)) + cycle_power_dyadic_class_weight m (fun i => b (2 * i + 1))
- Source
- Helper for RT-1 (OP-205, arXiv:2610.15635): rungs of cycle_power_dyadic_alternating_half_model (the even and odd halves of the bit-1 classes of an alternating endpoint-only dyadic model form a model one exponent lower)
- Verified
- 07 Nov 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_sum_range_doubleA sum over the first 2n indices equals the sum over n consecutive even-odd pairs.
- Used by 1
- cycle_power_dyadic_alternating_half_tightIn a tight, exactly dyadically covered model at exponent m+1 (m >= 1) with alternating bit 1, for every class with bit 1 both its even…
The proof, explained
The proof decomposes the dyadic class weight at exponent $m+1$ by splitting the inner summation over $2^{j+1}$ terms into even and odd indices for each scale $j < m$. The even terms correspond to dyadic correlations within the even half sequence $i \mapsto b(2i)$, and the odd terms correspond to dyadic correlations within the odd half sequence $i \mapsto b(2i+1)$. Explicitly evaluating the scale $j=0$ terms and the boundary terms, the algebraic sum of the weights of the two halves recombines to match the total weight at exponent $m+1$ along with the required boundary adjustments.
Establish basic power-of-two identities and define the even and odd component sums $PE(j)$ and $PO(j)$.
We prove that $2^{j+1} = 2 \cdot 2^j$ via `pow_succ` and linear arithmetic, deduce $2^{m+1} = 2 \cdot 2^m$, and observe that $2^m > 0$ by `Nat.two_pow_pos`. We then define $PE(j)$ and $PO(j)$ as the sums of length $2^j$ at dyadic distance $2^m - 2^j$ for the even subsequence $i \mapsto b(2i)$ and the odd subsequence $i \mapsto b(2i+1)$, respectively.
uses
pow_succ,Nat.two_pow_poshave hpow (j : ℕ) : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega have hD := hpow m have hm0 : 0 < 2 ^ m := Nat.two_pow_pos m let PE : ℕ → ℕ := fun j => (range (2 ^ j)).sum (fun i => (b (2 * i) && b (2 * (i + 2 ^ m - 2 ^ j))).toNat) let PO : ℕ → ℕ := fun j => (range (2 ^ j)).sum (fun i => (b (2 * i + 1) && b (2 * (i + 2 ^ m - 2 ^ j) + 1)).toNat)
The double summation in the weight at exponent $m+1$ decomposes into $\sum_{j=0}^{m-1} (PE(j) + PO(j))$.
The definition of `cycle_power_dyadic_class_weight` at exponent $m+1$ sums over $j \in \{0, \dots, m\}$, with the $j=0$ term vanishing. Using `sum_range_succ'`, we shift the index $j \mapsto j+1$ over $j \in \{0, \dots, m-1\}$. For each $j < m$, the inner sum runs over $2^{j+1} = 2 \cdot 2^j$ terms. Using `cycle_power_sum_range_double`, this sum splits into even indices $2i$ and odd indices $2i+1$ for $i < 2^j$. Presburger arithmetic (`omega`) simplifies the shifted arguments to $2(i + 2^m - 2^j)$ and $2(i + 2^m - 2^j) + 1$, matching the definitions of $PE(j)$ and $PO(j)$.
uses
sum_range_succ',sum_congr,Nat.pow_le_pow_right,le_of_lt,cycle_power_sum_range_double,sum_add_distribhave hL : (range (m + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (b i && b (i + 2 ^ (m + 1) - 2 ^ j)).toNat)) = (range m).sum (fun j => PE j + PO j) := by rw [sum_range_succ'] simp only [Nat.add_eq_zero_iff, one_ne_zero, and_false, ↓reduceIte, add_zero] apply sum_congr rfl intro j hj have hjm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (le_of_lt (mem_range.mp hj)) rw [hpow j, cycle_power_sum_range_double, ← sum_add_distrib] apply sum_congr rfl intro i hi have hi' := mem_range.mp hi have e0 : 2 * i + 2 ^ (m + 1) - 2 * 2 ^ j = 2 * (i + 2 ^ m - 2 ^ j) := by omega have e1 : 2 * i + 1 + 2 ^ (m + 1) - 2 * 2 ^ j = 2 * (i + 2 ^ m - 2 ^ j) + 1 := by omega rw [e0, e1]
For any sequence $P$, $\sum_{j=0}^{m-1} P(j) = P(0) + \sum_{j=0}^{m-1} (\text{if } j = 0 \text{ then } 0 \text{ else } P(j))$.
Since $m \ge 1$, we write $m = k+1$. Peeling off the initial $j=0$ term from both sums using `sum_range_succ'` and evaluating the conditional at $j=0$, both expressions reduce to $P(0) + \sum_{k < k} P(k+1)$, which `ring` simplifies.
uses
sum_range_succ'have hR : ∀ P : ℕ → ℕ, (range m).sum P = P 0 + (range m).sum (fun j => if j = 0 then 0 else P j) := by intro P obtain ⟨k, rfl⟩ : ∃ k, m = k + 1 := ⟨m - 1, by omega⟩ rw [sum_range_succ', sum_range_succ'] simp only [Nat.add_eq_zero_iff, one_ne_zero, and_false, ↓reduceIte, add_zero] ring
The weight of the even half $i \mapsto b(2i)$ at exponent $m$ equals $2 [b_0 \land b_{2^{m+1}-2}] + \sum_{j=0}^{m-1} (\text{if } j = 0 \text{ then } 0 \text{ else } PE(j))$.
Unfolding the definition of `cycle_power_dyadic_class_weight` at exponent $m$ for the even sequence $i \mapsto b(2i)$, the boundary term is $2 [b(0) \land b(2(2^m - 1))]$. Since $2(2^m - 1) = 2^{m+1} - 2$, this becomes $2 [b_0 \land b_{2^{m+1}-2}]$. The remaining sum over $j$ matches the definition of $PE(j)$ when $j > 0$.
uses
Nat.mul_zerohave hE : cycle_power_dyadic_class_weight m (fun i => b (2 * i)) = 2 * (b 0 && b (2 ^ (m + 1) - 2)).toNat + (range m).sum (fun j => if j = 0 then 0 else PE j) := by unfold cycle_power_dyadic_class_weight have : 2 * (2 ^ m - 1) = 2 ^ (m + 1) - 2 := by omega simp only [Nat.mul_zero, this] rfl
The weight of the odd half $i \mapsto b(2i+1)$ at exponent $m$ equals $2 [b_1 \land b_{2^{m+1}-1}] + \sum_{j=0}^{m-1} (\text{if } j = 0 \text{ then } 0 \text{ else } PO(j))$.
Unfolding the weight at exponent $m$ for the odd sequence $i \mapsto b(2i+1)$, the boundary term is $2 [b(1) \land b(2(2^m - 1) + 1)] = 2 [b_1 \land b_{2^{m+1}-1}]$ because $2(2^m - 1) + 1 = 2^{m+1} - 1$. The remaining sum matches $PO(j)$ for $j > 0$.
uses
Nat.mul_zero,Nat.zero_addhave hO : cycle_power_dyadic_class_weight m (fun i => b (2 * i + 1)) = 2 * (b 1 && b (2 ^ (m + 1) - 1)).toNat + (range m).sum (fun j => if j = 0 then 0 else PO j) := by unfold cycle_power_dyadic_class_weight have : 2 * (2 ^ m - 1) + 1 = 2 ^ (m + 1) - 1 := by omega simp only [Nat.mul_zero, Nat.zero_add, this] rfl
$PE(0) = [b_0 \land b_{2^{m+1}-2}]$.
Specializing $PE(j)$ to $j = 0$, the range has $2^0 = 1$ term at $i = 0$. Simplifying with `pow_zero` and `sum_range_one`, the argument evaluates to $2(0 + 2^m - 2^0) = 2(2^m - 1) = 2^{m+1} - 2$.
uses
pow_zero,sum_range_one,Nat.mul_zero,Nat.zero_addhave hE0 : PE 0 = (b 0 && b (2 ^ (m + 1) - 2)).toNat := by simp only [PE, pow_zero, sum_range_one, Nat.mul_zero, Nat.zero_add] have : 2 * (2 ^ m - 1) = 2 ^ (m + 1) - 2 := by omega rw [this]
$PO(0) = [b_1 \land b_{2^{m+1}-1}]$.
Specializing $PO(j)$ to $j = 0$, the range has $2^0 = 1$ term at $i = 0$. Simplifying with `pow_zero` and `sum_range_one`, the argument evaluates to $2(0 + 2^m - 2^0) + 1 = 2(2^m - 1) + 1 = 2^{m+1} - 1$.
uses
pow_zero,sum_range_one,Nat.mul_zero,Nat.zero_addhave hO0 : PO 0 = (b 1 && b (2 ^ (m + 1) - 1)).toNat := by simp only [PO, pow_zero, sum_range_one, Nat.mul_zero, Nat.zero_add] have : 2 * (2 ^ m - 1) + 1 = 2 ^ (m + 1) - 1 := by omega rw [this]
The weight of $b$ at exponent $m+1$ equals $2 [b_0 \land b_{2^{m+1}-1}] + \sum_{j=0}^{m-1} (PE(j) + PO(j))$.
Unfolding `cycle_power_dyadic_class_weight` at exponent $m+1$ and substituting the decomposition $hL$ replaces the double summation with $\sum_{j=0}^{m-1} (PE(j) + PO(j))$.
have hW : cycle_power_dyadic_class_weight (m + 1) b = 2 * (b 0 && b (2 ^ (m + 1) - 1)).toNat + (range m).sum (fun j => PE j + PO j) := by unfold cycle_power_dyadic_class_weight rw [hL]
The main equality holds. automation
We substitute the representations of the weight at exponent $m+1$ and the weights of the two halves. Distributing the sum with `sum_add_distrib`, separating the $j=0$ terms using $hR$, and substituting the values of $PE(0)$ and $PO(0)$, both sides reduce to the same polynomial expression in the component terms, which `ring` closes.
uses
sum_add_distribrw [hW, hE, hO, sum_add_distrib, hR PE, hR PO, hE0, hO0] ring
pow_succ- For any element $a$ in a monoid, $a^{n+1} = a^n \cdot a$.
Nat.two_pow_pos- For any natural number $w$, $2^w > 0$.
sum_range_succ'- Splits off the first term ($k=0$) from a sum over $\{0, \dots, n\}$ and shifts the remaining indices by 1: $\sum_{k=0}^n f(k) = \sum_{k=0}^{n-1} f(k+1) + f(0)$.
sum_congr- If two index sets are equal and the summands are pointwise equal on the set, then their sums are equal.
Nat.pow_le_pow_right- Powers with base $n > 0$ are monotonic in the exponent: if $i \le j$, then $n^i \le n^j$.
le_of_lt- A strict inequality implies the corresponding non-strict inequality: if $a < b$, then $a \le b$.
cycle_power_sum_range_double- A sum of $2n$ terms splits into the sum of its even and odd index terms: $\sum_{i=0}^{2n-1} f(i) = \sum_{i=0}^{n-1} (f(2i) + f(2i+1))$.
sum_add_distrib- The sum of a pointwise sum of two functions equals the sum of their individual sums: $\sum (f(x) + g(x)) = \sum f(x) + \sum g(x)$.
Nat.mul_zero- Multiplication of any natural number by zero yields zero: $n \cdot 0 = 0$.
Nat.zero_add- Zero added to any natural number is that number: $0 + n = n$.
pow_zero- Any element raised to the power 0 equals 1: $a^0 = 1$.
sum_range_one- A sum over the singleton range $\{0\}$ equals the value at 0: $\sum_{k \in \mathrm{range}(1)} f(k) = f(0)$.
- Several index arithmetic steps involving powers of two (such as $2i + 2^{m+1} - 2^{j+1} = 2(i + 2^m - 2^j)$) and the final algebraic rearrangement are discharged by Lean's Presburger arithmetic (`omega`) and ring solver (`ring`).
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.
theorem cycle_power_dyadic_class_weight_parity_split (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) : cycle_power_dyadic_class_weight (m + 1) b + (b 0 && b (2 ^ (m + 1) - 2)).toNat + (b 1 && b (2 ^ (m + 1) - 1)).toNat = 2 * (b 0 && b (2 ^ (m + 1) - 1)).toNat + cycle_power_dyadic_class_weight m (fun i => b (2 * i)) + cycle_power_dyadic_class_weight m (fun i => b (2 * i + 1)) := open Finset in by have hpow (j : ℕ) : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega have hD := hpow m have hm0 : 0 < 2 ^ m := Nat.two_pow_pos m let PE : ℕ → ℕ := fun j => (range (2 ^ j)).sum (fun i => (b (2 * i) && b (2 * (i + 2 ^ m - 2 ^ j))).toNat) let PO : ℕ → ℕ := fun j => (range (2 ^ j)).sum (fun i => (b (2 * i + 1) && b (2 * (i + 2 ^ m - 2 ^ j) + 1)).toNat) have hL : (range (m + 1)).sum (fun j => if j = 0 then 0 else (range (2 ^ j)).sum (fun i => (b i && b (i + 2 ^ (m + 1) - 2 ^ j)).toNat)) = (range m).sum (fun j => PE j + PO j) := by rw [sum_range_succ'] simp only [Nat.add_eq_zero_iff, one_ne_zero, and_false, ↓reduceIte, add_zero] apply sum_congr rfl intro j hj have hjm : 2 ^ j ≤ 2 ^ m := Nat.pow_le_pow_right (by decide) (le_of_lt (mem_range.mp hj)) rw [hpow j, cycle_power_sum_range_double, ← sum_add_distrib] apply sum_congr rfl intro i hi have hi' := mem_range.mp hi have e0 : 2 * i + 2 ^ (m + 1) - 2 * 2 ^ j = 2 * (i + 2 ^ m - 2 ^ j) := by omega have e1 : 2 * i + 1 + 2 ^ (m + 1) - 2 * 2 ^ j = 2 * (i + 2 ^ m - 2 ^ j) + 1 := by omega rw [e0, e1] have hR : ∀ P : ℕ → ℕ, (range m).sum P = P 0 + (range m).sum (fun j => if j = 0 then 0 else P j) := by intro P obtain ⟨k, rfl⟩ : ∃ k, m = k + 1 := ⟨m - 1, by omega⟩ rw [sum_range_succ', sum_range_succ'] simp only [Nat.add_eq_zero_iff, one_ne_zero, and_false, ↓reduceIte, add_zero] ring have hE : cycle_power_dyadic_class_weight m (fun i => b (2 * i)) = 2 * (b 0 && b (2 ^ (m + 1) - 2)).toNat + (range m).sum (fun j => if j = 0 then 0 else PE j) := by unfold cycle_power_dyadic_class_weight have : 2 * (2 ^ m - 1) = 2 ^ (m + 1) - 2 := by omega simp only [Nat.mul_zero, this] rfl have hO : cycle_power_dyadic_class_weight m (fun i => b (2 * i + 1)) = 2 * (b 1 && b (2 ^ (m + 1) - 1)).toNat + (range m).sum (fun j => if j = 0 then 0 else PO j) := by unfold cycle_power_dyadic_class_weight have : 2 * (2 ^ m - 1) + 1 = 2 ^ (m + 1) - 1 := by omega simp only [Nat.mul_zero, Nat.zero_add, this] rfl have hE0 : PE 0 = (b 0 && b (2 ^ (m + 1) - 2)).toNat := by simp only [PE, pow_zero, sum_range_one, Nat.mul_zero, Nat.zero_add] have : 2 * (2 ^ m - 1) = 2 ^ (m + 1) - 2 := by omega rw [this] have hO0 : PO 0 = (b 1 && b (2 ^ (m + 1) - 1)).toNat := by simp only [PO, pow_zero, sum_range_one, Nat.mul_zero, Nat.zero_add] have : 2 * (2 ^ m - 1) + 1 = 2 ^ (m + 1) - 1 := by omega rw [this] have hW : cycle_power_dyadic_class_weight (m + 1) b = 2 * (b 0 && b (2 ^ (m + 1) - 1)).toNat + (range m).sum (fun j => PE j + PO j) := by unfold cycle_power_dyadic_class_weight rw [hL] rw [hW, hE, hO, sum_add_distrib, hR PE, hR PO, hE0, hO0] ring