AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_parity_split

theoremverified

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
Used by 1

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.

  1. 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.

    lines 7–12

    uses pow_succ, Nat.two_pow_pos

      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)
  2. 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)$.

    lines 13–27

    uses sum_range_succ', sum_congr, Nat.pow_le_pow_right, le_of_lt, cycle_power_sum_range_double, sum_add_distrib

      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]
  3. 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.

    lines 28–33

    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
  4. 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$.

    lines 34–39

    uses Nat.mul_zero

      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
  5. 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$.

    lines 40–45

    uses Nat.mul_zero, Nat.zero_add

      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
  6. $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$.

    lines 46–49

    uses pow_zero, sum_range_one, Nat.mul_zero, Nat.zero_add

      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]
  7. $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$.

    lines 50–53

    uses pow_zero, sum_range_one, Nat.mul_zero, Nat.zero_add

      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]
  8. 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))$.

    lines 54–57

      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]
  9. 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.

    lines 58–59

    uses sum_add_distrib

      rw [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)$.

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

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
See it in the graphDiscuss this resultChallenge it