AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_dilate

theoremverified

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

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.

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

    lines 7–10

    uses Nat.exists_eq_add_of_le

      obtain ⟨k, hk⟩ := Nat.exists_eq_add_of_le hm
      have hmk : m = k + 1 := by omega
      clear hk
      subst m
  2. 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.

    line 11

    uses pow_succ

      have hpow (j : ℕ) : 2 ^ (j + 1) = 2 * 2 ^ j := by rw [pow_succ]; omega
  3. 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.

    lines 12–15

    uses Nat.two_pow_pos

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

    lines 16–25

    uses sum_range_succ', Nat.add_eq_zero_iff, one_ne_zero, and_false, add_zero

      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]
  5. 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)).

    lines 26–45

    uses cycle_power_sum_range_double, mul_sum, sum_congr, Nat.pow_le_pow_right

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

    line 46

    uses sum_congr

        have ht := sum_congr (s₁ := range (k + 1)) (s₂ := range (k + 1)) rfl (fun j hj => hterm j (mem_range.mp hj))
  7. 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.

    lines 47–54

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

    lines 55–64

    uses sum_range_succ', pow_zero, sum_range_one, zero_add

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

    lines 65–66

    uses mul_sum

        rw [ht, ← mul_sum, hB, hzero]
        ring
  10. 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.

    lines 67–70

    uses Nat.zero_div

      unfold 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

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

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