AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_class_weight_le

theoremverified

For every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.

Statement

theorem cycle_power_dyadic_class_weight_le (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) :
    cycle_power_dyadic_class_weight m b ≤
      (Finset.range (2 ^ m)).sum (fun i => (b i).toNat)
Source
Uniform route for OP-205 and RT-1, arXiv:2610.15635 Section 3. Existing k=3,7,15 weight certificates suggest this dyadic tree. The sparse distance graph is obtained recursively by attaching one leaf to every vertex; tight classes are connected subtrees containing the distinguished endpoint edge.
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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 55

The proof, explained

The theorem is proved by induction on the scale m = k + 1. For the step from scale k + 1 to scale k + 2, a lifted sequence of length 2^(k+1) is constructed by discarding the two middle blocks of length 2^k and concatenating the first and fourth blocks. The dyadic weight at scale k + 2 decomposes into the weight of the lifted sequence plus a cross-block correlation term; by the induction hypothesis and blockwise bounding, the lifted weight accounts for the first and fourth blocks while the cross-block terms are bounded by the second and third blocks, totaling at most the sum over the entire scale 2^(k+2).

  1. For any booleans x and y, (x ∧ y).toNat ≤ x.toNat.

    Checked by case exhaustion over the four possible boolean combinations of x and y.

    line 7

      cases x <;> cases y <;> decide
  2. For any booleans x and y, (x ∧ y).toNat ≤ y.toNat.

    Checked by case exhaustion over the four possible boolean combinations of x and y.

    line 10

      cases x <;> cases y <;> decide
  3. The sum of f over range 4L decomposes into the sum of four blocks of length L, starting at 0, L, 2L, and 3L.

    Partitioning 4L as L + (L + (L + L)) and applying sum_range_add three times breaks the sum into four intervals of length L. Presburger arithmetic simplifies the offset indices L + (L + x) = 2L + x and L + (L + (L + x)) = 3L + x.

    lines 18–26

    uses sum_range_add

      have h4 : 4 * L = L + (L + (L + L)) := by omega
      rw [h4]
      rw [sum_range_add, sum_range_add, sum_range_add]
      have h2 : (fun x => f (L + (L + x))) = (fun x => f (2 * L + x)) := by
        funext x; congr 1; omega
      have h3 : (fun x => f (L + (L + (L + x)))) = (fun x => f (3 * L + x)) := by
        funext x; congr 1; omega
      rw [h2, h3]
      omega
  4. The lifted sequence matches b at the boundaries: b_lift(0) = b(0) and b_lift(2^(k+1) - 1) = b(2^(k+2) - 1).

    At index 0, since 0 < 2^k, the definition of cycle_power_dyadic_b_lift takes the first branch giving b(0). At the right boundary 2^(k+1) - 1, the index is at least 2^k, so it shifts by 2^(k+1), giving index (2^(k+1) - 1) + 2^(k+1) = 2^(k+2) - 1.

    lines 32–43

    uses pow_succ', mul_comm, Nat.two_pow_pos, if_pos, Nat.one_le_two_pow, if_neg, not_lt_of_ge

      have hk1 : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm]
      have hk2 : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ', mul_comm]
      have hpos : 0 < 2 ^ k := Nat.two_pow_pos k
      have h_b0 : cycle_power_dyadic_b_lift k b 0 = b 0 := by
        dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hpos]
      have h_last : cycle_power_dyadic_b_lift k b (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by
        dsimp [cycle_power_dyadic_b_lift]
        have hge : 2 ^ k ≤ 2 ^ (k + 1) - 1 := by
          have : 1 ≤ 2 ^ k := Nat.one_le_two_pow; omega
        rw [if_neg (not_lt_of_ge hge)]
        congr 1
        have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow; omega
  5. The dyadic class weight at scale k + 2 isolates the top scale term as the cross-block sum over range 2^(k+1).

    Unfolding cycle_power_dyadic_class_weight and separating the j = k + 1 term using sum_range_succ yields the remaining sum for j ≤ k plus the top scale term. Since k + 1 ≠ 0, the top scale conditional reduces to the cross-block sum with offset 2^(k+2) - 2^(k+1) = 2^(k+1).

    lines 44–55

    uses sum_range_succ, if_neg, Nat.succ_ne_zero

      unfold cycle_power_dyadic_class_weight
      rw [sum_range_succ]
      have h_last_term : (if k + 1 = 0 then 0
          else ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 2) - 2 ^ (k + 1))).toNat) =
          ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat := by
        rw [if_neg (Nat.succ_ne_zero k)]
        congr 1
        ext i
        congr 2
        congr 1
        omega
      rw [h_last_term]
  6. For each scale j ≤ k, the dyadic weight terms of b match those of the lifted sequence.

    For j = 0 both terms are zero. For 0 < j ≤ k and i < 2^j ≤ 2^k, the first index i < 2^k so the lift equals b(i). The second index i + 2^(k+1) - 2^j is at least 2^k, so the lift shifts it by 2^(k+1) to i + 2^(k+2) - 2^j, exactly matching the term for b.

    lines 56–82

    uses sum_congr, mem_range, Nat.lt_succ_iff.mp, Nat.pow_le_pow_right, lt_of_lt_of_le, if_pos, if_neg, not_lt_of_ge

      have h_sum_eq :
          (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (b i && b (i + 2 ^ (k + 2) - 2 ^ j)).toNat) =
          (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (cycle_power_dyadic_b_lift k b i && cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j)).toNat) := by
        apply sum_congr rfl
        intro j hj
        simp only [mem_range] at hj
        have hj_le : j ≤ k := Nat.lt_succ_iff.mp hj
        split_ifs with hj0
        · rfl
        · apply sum_congr rfl
          intro i hi
          simp only [mem_range] at hi
          have hi_lt : i < 2 ^ k := by
            have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le
            exact lt_of_lt_of_le hi this
          have h1 : cycle_power_dyadic_b_lift k b i = b i := by
            dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hi_lt]
          have hge : 2 ^ k ≤ i + 2 ^ (k + 1) - 2 ^ j := by
            have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le
            omega
          have h2 : cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j) = b (i + 2 ^ (k + 2) - 2 ^ j) := by
            dsimp [cycle_power_dyadic_b_lift]
            rw [if_neg (not_lt_of_ge hge)]
            congr 1
            have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le
            omega
          rw [h1, h2]
  7. The dyadic class weight at scale k + 2 equals the class weight of the lifted sequence at scale k + 1 plus the cross-block sum over range 2^(k+1).

    Substituting the boundary evaluations and the term-by-term equality of the sums for j ≤ k into the unfolded class weight expression completes the recurrence relation.

    lines 83–84

      rw [h_b0, h_last, h_sum_eq]
      omega
  8. Setting L = 2^k, the range 2^(k+1) splits into two blocks of length L for both the lifted sum and the cross-block sum.

    Expressing 2^(k+1) = L + L and 2^(k+2) = 4L via power and multiplication lemmas, sum_range_add decomposes both the lifted sum and the cross-block sum into two sums over range L.

    lines 90–100

    uses pow_succ', two_mul, pow_add, mul_comm, sum_range_add

      let L := 2 ^ k
      have hk1 : 2 ^ (k + 1) = L + L := by
        show 2 ^ (k + 1) = 2 ^ k + 2 ^ k
        rw [pow_succ', two_mul]
      have hk2 : 2 ^ (k + 2) = 4 * L := by
        show 2 ^ (k + 2) = 4 * 2 ^ k
        calc 2 ^ (k + 2) = 2 ^ k * 2 ^ 2 := pow_add 2 k 2
        _ = 2 ^ k * 4 := rfl
        _ = 4 * 2 ^ k := mul_comm _ _
      rw [hk1]
      rw [sum_range_add, sum_range_add]
  9. The two blocks of the lifted sequence equal block 0 and block 3 of b, respectively.

    On [0, L), the lift index satisfies i < 2^k, so the lift equals b(i). On [L, 2L), the index L + i ≥ 2^k, so the lift shifts by 2^(k+1) = 2L, resulting in b(3L + i).

    lines 101–116

    uses sum_congr, mem_range, if_pos, if_neg, not_lt_of_ge, pow_succ', mul_comm

      have h_lift1 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b i).toNat) = ∑ i ∈ range L, (b i).toNat := by
        apply sum_congr rfl
        intro i hi
        simp only [mem_range] at hi
        dsimp [cycle_power_dyadic_b_lift, L] at *
        rw [if_pos hi]
      have h_lift2 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b (L + i)).toNat) = ∑ i ∈ range L, (b (3 * L + i)).toNat := by
        apply sum_congr rfl
        intro i hi
        dsimp [cycle_power_dyadic_b_lift]
        have hge : 2 ^ k ≤ L + i := by dsimp [L]; omega
        rw [if_neg (not_lt_of_ge hge)]
        congr 2
        have : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm]
        dsimp [L]
        omega
  10. The two halves of the cross-block sum are bounded by block 2 and block 1 of b, respectively.

    Using pointwise boolean inequalities (x ∧ y).toNat ≤ y.toNat and (x ∧ y).toNat ≤ x.toNat, the first cross block (b(i) ∧ b(2L+i)).toNat is bounded by b(2L+i).toNat (block 2), and the second cross block (b(L+i) ∧ b(3L+i)).toNat is bounded by b(L+i).toNat (block 1).

    lines 117–126

    uses sum_le_sum, cycle_power_dyadic_bool_and_toNat_le_right, cycle_power_dyadic_bool_and_toNat_le_left

      have h_cross1 : (∑ i ∈ range L, (b i && b (i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (2 * L + i)).toNat := by
        apply sum_le_sum
        intro i hi
        have : i + (L + L) = 2 * L + i := by omega
        rw [this]
        exact cycle_power_dyadic_bool_and_toNat_le_right (b i) (b (2 * L + i))
      have h_cross2 : (∑ i ∈ range L, (b (L + i) && b (L + i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (L + i)).toNat := by
        apply sum_le_sum
        intro i hi
        exact cycle_power_dyadic_bool_and_toNat_le_left (b (L + i)) (b (L + i + (L + L)))
  11. The lifted sequence sum plus the cross-block sum is at most the total sum of b over range 2^(k+2).

    Combining the evaluations of the lifted blocks (blocks 0 and 3) with the bounds on the cross blocks (blocks 2 and 1) gives the sum of all four length-L blocks, which equals the total sum over range 4L = 2^(k+2) by cycle_power_dyadic_sum_range_four_blocks.

    lines 127–130

    uses cycle_power_dyadic_sum_range_four_blocks

      rw [h_lift1, h_lift2]
      rw [hk2]
      rw [cycle_power_dyadic_sum_range_four_blocks]
      omega
  12. For k = 0, the dyadic class weight at scale 1 is at most the number of selected positions in range 2.

    At scale 1, the weight simplifies to 2 * (b(0) ∧ b(1)).toNat, while the range sum is b(0).toNat + b(1).toNat. Exhaustive boolean evaluation confirms the inequality 2(b_0 ∧ b_1) ≤ b_0 + b_1 in all four cases.

    lines 135–142

    uses sum_range_one, ite_true, add_zero, sum_range_succ

      induction k generalizing b with
      | zero =>
        unfold cycle_power_dyadic_class_weight
        rw [sum_range_one]
        simp only [ite_true, add_zero]
        norm_num
        rw [sum_range_succ, sum_range_one]
        cases b 0 <;> cases b 1 <;> decide
  13. If the weight bound holds at scale k + 1, it also holds at scale k + 2.

    By the recurrence cycle_power_dyadic_class_weight_succ, the weight at scale k + 2 splits into the lifted weight at scale k + 1 plus the cross term. The induction hypothesis bounds the lifted weight by the sum of the lifted sequence, and cycle_power_dyadic_sum_lift_and_cross_le bounds that sum plus the cross term by the sum of b over range 2^(k+2).

    lines 143–145

    uses cycle_power_dyadic_class_weight_succ, le_trans, add_le_add_left, cycle_power_dyadic_sum_lift_and_cross_le

      | succ k ih =>
        rw [cycle_power_dyadic_class_weight_succ]
        exact le_trans (add_le_add_left (ih (cycle_power_dyadic_b_lift k b)) _) (cycle_power_dyadic_sum_lift_and_cross_le k b)
  14. For every m ≥ 1, the dyadic class weight at scale m is at most the number of selected positions in range 2^m.

    Writing m = (m - 1) + 1 via Nat.sub_add_cancel, the result follows immediately from the inductive lemma cycle_power_dyadic_class_weight_le_aux with k = m - 1.

    lines 150–152

    uses Nat.sub_add_cancel, cycle_power_dyadic_class_weight_le_aux

      have h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm
      rw [h]
      exact cycle_power_dyadic_class_weight_le_aux (m - 1) b
sum_range_add
A sum over range n + m splits into a sum over range n and an offset sum over range m.
pow_succ'
Powers satisfy a ^ (n + 1) = a * a ^ n.
mul_comm
Multiplication is commutative.
Nat.two_pow_pos
Powers of 2 are strictly positive: 0 < 2 ^ w.
if_pos
An if-then-else expression evaluates to the then-branch when the condition holds.
Nat.one_le_two_pow
Every power of two is at least 1: 1 ≤ 2 ^ n.
if_neg
An if-then-else expression evaluates to the else-branch when the condition is false.
not_lt_of_ge
If a ≤ b, then b is not strictly less than a.
sum_range_succ
A sum over range n + 1 equals the sum over range n plus the n-th term.
Nat.succ_ne_zero
The successor of a natural number is never zero: n + 1 ≠ 0.
sum_congr
Sums of pointwise equal functions over equal sets are equal.
mem_range
A natural number m belongs to range n if and only if m < n.
Nat.lt_succ_iff.mp
If j < k + 1, then j ≤ k.
Nat.pow_le_pow_right
Exponentiation with a positive base is non-decreasing in the exponent: if i ≤ j then n ^ i ≤ n ^ j.
lt_of_lt_of_le
If a < b and b ≤ c, then a < c.
two_mul
Multiplying by 2 equals adding to oneself: 2 * n = n + n.
pow_add
Exponents add under multiplication: a ^ (m + n) = a ^ m * a ^ n.
sum_le_sum
If f(i) ≤ g(i) pointwise on a finite set, then the sum of f is at most the sum of g.
cycle_power_dyadic_bool_and_toNat_le_right
For booleans x and y, (x ∧ y).toNat ≤ y.toNat.
cycle_power_dyadic_bool_and_toNat_le_left
For booleans x and y, (x ∧ y).toNat ≤ x.toNat.
cycle_power_dyadic_sum_range_four_blocks
The sum of f over range 4L decomposes into four blocks of length L starting at 0, L, 2L, and 3L.
sum_range_one
A sum over range 1 equals the evaluation at 0.
ite_true
An if-then-else with condition True evaluates to the first branch.
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a.
cycle_power_dyadic_class_weight_succ
The dyadic class weight at scale k + 2 equals the class weight of the lifted sequence at scale k + 1 plus the cross-block sum over range 2 ^ (k + 1).
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
add_le_add_left
Adding a common term to both sides preserves inequality: if b ≤ c then b + a ≤ c + a.
cycle_power_dyadic_sum_lift_and_cross_le
The sum of the lifted sequence plus the cross-block sum on range 2 ^ (k + 1) is at most the total sum of b on range 2 ^ (k + 2).
Nat.sub_add_cancel
If m ≤ n, then (n - m) + m = n.
cycle_power_dyadic_class_weight_le_aux
For every natural number k, the dyadic class weight at scale k + 1 is at most the sum of b over range 2 ^ (k + 1).

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 Finsetdef cycle_power_dyadic_b_lift (k : ℕ) (b : ℕ → Bool) : ℕ → Bool :=  fun x => if x < 2 ^ k then b x else b (x + 2 ^ (k + 1))lemma cycle_power_dyadic_bool_and_toNat_le_left (x y : Bool) : (x && y).toNat ≤ x.toNat := by  cases x <;> cases y <;> decidelemma cycle_power_dyadic_bool_and_toNat_le_right (x y : Bool) : (x && y).toNat ≤ y.toNat := by  cases x <;> cases y <;> decidelemma cycle_power_dyadic_sum_range_four_blocks (L : ℕ) (f : ℕ → ℕ) :    ∑ i ∈ range (4 * L), f i =      (∑ i ∈ range L, f i) +      (∑ i ∈ range L, f (L + i)) +      (∑ i ∈ range L, f (2 * L + i)) +      (∑ i ∈ range L, f (3 * L + i)) := by  have h4 : 4 * L = L + (L + (L + L)) := by omega  rw [h4]  rw [sum_range_add, sum_range_add, sum_range_add]  have h2 : (fun x => f (L + (L + x))) = (fun x => f (2 * L + x)) := by    funext x; congr 1; omega  have h3 : (fun x => f (L + (L + (L + x)))) = (fun x => f (3 * L + x)) := by    funext x; congr 1; omega  rw [h2, h3]  omegalemma cycle_power_dyadic_class_weight_succ (k : ℕ) (b : ℕ → Bool) :    cycle_power_dyadic_class_weight (k + 2) b =      cycle_power_dyadic_class_weight (k + 1) (cycle_power_dyadic_b_lift k b) +        ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat := by  have hk1 : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm]  have hk2 : 2 ^ (k + 2) = 2 * 2 ^ (k + 1) := by rw [pow_succ', mul_comm]  have hpos : 0 < 2 ^ k := Nat.two_pow_pos k  have h_b0 : cycle_power_dyadic_b_lift k b 0 = b 0 := by    dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hpos]  have h_last : cycle_power_dyadic_b_lift k b (2 ^ (k + 1) - 1) = b (2 ^ (k + 2) - 1) := by    dsimp [cycle_power_dyadic_b_lift]    have hge : 2 ^ k ≤ 2 ^ (k + 1) - 1 := by      have : 1 ≤ 2 ^ k := Nat.one_le_two_pow; omega    rw [if_neg (not_lt_of_ge hge)]    congr 1    have : 1 ≤ 2 ^ (k + 1) := Nat.one_le_two_pow; omega  unfold cycle_power_dyadic_class_weight  rw [sum_range_succ]  have h_last_term : (if k + 1 = 0 then 0      else ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 2) - 2 ^ (k + 1))).toNat) =      ∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat := by    rw [if_neg (Nat.succ_ne_zero k)]    congr 1    ext i    congr 2    congr 1    omega  rw [h_last_term]  have h_sum_eq :      (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (b i && b (i + 2 ^ (k + 2) - 2 ^ j)).toNat) =      (∑ j ∈ range (k + 1), if j = 0 then 0 else ∑ i ∈ range (2 ^ j), (cycle_power_dyadic_b_lift k b i && cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j)).toNat) := by    apply sum_congr rfl    intro j hj    simp only [mem_range] at hj    have hj_le : j ≤ k := Nat.lt_succ_iff.mp hj    split_ifs with hj0    · rfl    · apply sum_congr rfl      intro i hi      simp only [mem_range] at hi      have hi_lt : i < 2 ^ k := by        have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le        exact lt_of_lt_of_le hi this      have h1 : cycle_power_dyadic_b_lift k b i = b i := by        dsimp [cycle_power_dyadic_b_lift]; rw [if_pos hi_lt]      have hge : 2 ^ k ≤ i + 2 ^ (k + 1) - 2 ^ j := by        have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le        omega      have h2 : cycle_power_dyadic_b_lift k b (i + 2 ^ (k + 1) - 2 ^ j) = b (i + 2 ^ (k + 2) - 2 ^ j) := by        dsimp [cycle_power_dyadic_b_lift]        rw [if_neg (not_lt_of_ge hge)]        congr 1        have : 2 ^ j ≤ 2 ^ k := Nat.pow_le_pow_right (by decide) hj_le        omega      rw [h1, h2]  rw [h_b0, h_last, h_sum_eq]  omegalemma cycle_power_dyadic_sum_lift_and_cross_le (k : ℕ) (b : ℕ → Bool) :    (∑ i ∈ range (2 ^ (k + 1)), (cycle_power_dyadic_b_lift k b i).toNat) +      (∑ i ∈ range (2 ^ (k + 1)), (b i && b (i + 2 ^ (k + 1))).toNat) ≤    ∑ i ∈ range (2 ^ (k + 2)), (b i).toNat := by  let L := 2 ^ k  have hk1 : 2 ^ (k + 1) = L + L := by    show 2 ^ (k + 1) = 2 ^ k + 2 ^ k    rw [pow_succ', two_mul]  have hk2 : 2 ^ (k + 2) = 4 * L := by    show 2 ^ (k + 2) = 4 * 2 ^ k    calc 2 ^ (k + 2) = 2 ^ k * 2 ^ 2 := pow_add 2 k 2    _ = 2 ^ k * 4 := rfl    _ = 4 * 2 ^ k := mul_comm _ _  rw [hk1]  rw [sum_range_add, sum_range_add]  have h_lift1 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b i).toNat) = ∑ i ∈ range L, (b i).toNat := by    apply sum_congr rfl    intro i hi    simp only [mem_range] at hi    dsimp [cycle_power_dyadic_b_lift, L] at *    rw [if_pos hi]  have h_lift2 : (∑ i ∈ range L, (cycle_power_dyadic_b_lift k b (L + i)).toNat) = ∑ i ∈ range L, (b (3 * L + i)).toNat := by    apply sum_congr rfl    intro i hi    dsimp [cycle_power_dyadic_b_lift]    have hge : 2 ^ k ≤ L + i := by dsimp [L]; omega    rw [if_neg (not_lt_of_ge hge)]    congr 2    have : 2 ^ (k + 1) = 2 * 2 ^ k := by rw [pow_succ', mul_comm]    dsimp [L]    omega  have h_cross1 : (∑ i ∈ range L, (b i && b (i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (2 * L + i)).toNat := by    apply sum_le_sum    intro i hi    have : i + (L + L) = 2 * L + i := by omega    rw [this]    exact cycle_power_dyadic_bool_and_toNat_le_right (b i) (b (2 * L + i))  have h_cross2 : (∑ i ∈ range L, (b (L + i) && b (L + i + (L + L))).toNat) ≤ ∑ i ∈ range L, (b (L + i)).toNat := by    apply sum_le_sum    intro i hi    exact cycle_power_dyadic_bool_and_toNat_le_left (b (L + i)) (b (L + i + (L + L)))  rw [h_lift1, h_lift2]  rw [hk2]  rw [cycle_power_dyadic_sum_range_four_blocks]  omegalemma cycle_power_dyadic_class_weight_le_aux (k : ℕ) (b : ℕ → Bool) :    cycle_power_dyadic_class_weight (k + 1) b ≤      (Finset.range (2 ^ (k + 1))).sum (fun i => (b i).toNat) := by  induction k generalizing b with  | zero =>    unfold cycle_power_dyadic_class_weight    rw [sum_range_one]    simp only [ite_true, add_zero]    norm_num    rw [sum_range_succ, sum_range_one]    cases b 0 <;> cases b 1 <;> decide  | succ k ih =>    rw [cycle_power_dyadic_class_weight_succ]    exact le_trans (add_le_add_left (ih (cycle_power_dyadic_b_lift k b)) _) (cycle_power_dyadic_sum_lift_and_cross_le k b)theorem cycle_power_dyadic_class_weight_le (m : ℕ) (hm : 1 ≤ m) (b : ℕ → Bool) :    cycle_power_dyadic_class_weight m b ≤      (Finset.range (2 ^ m)).sum (fun i => (b i).toNat) := by  have h : m = (m - 1) + 1 := (Nat.sub_add_cancel hm).symm  rw [h]  exact cycle_power_dyadic_class_weight_le_aux (m - 1) b
See it in the graphDiscuss this resultChallenge it