AFTD Auto-Formalizing Theoretical Domains

cycle_power_dyadic_int_weight_le_card

theoremverified

For a finite integer set of diameter at most 2^m-1, weight its endpoint-distance pairs by two and its other dyadic long-distance pairs by one. The total weight is at most its size, uniformly in m.

Statement

theorem cycle_power_dyadic_int_weight_le_card
    (m : ℕ) (hm : 1 ≤ m) (S : Finset ℤ)
    (hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ ((2 ^ m - 1 : ℕ) : ℤ)) :
    (∑ e ∈ S,
      (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +
        (Finset.range m).sum (fun j => if j = 0 then 0 else
          if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0))) ≤ S.card
Source
Uniform graph-to-class-model bridge for OP-205 / RT-1 following arXiv:2610.15635. Transfers the proved Boolean dyadic-tree weight certificate to finite integer sets; no research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_dyadic_class_weight_leFor every power-of-two arc length, the dyadic weighted number of selected pairs is at most the number of selected positions.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 3

The proof, explained

The proof shifts the integer set S by its minimum element c = min S to place it in the interval [c, c + 2^m - 1], encoding membership with a boolean sequence b(i) = [i + c ∈ S]. A general counting lemma shows via the translation bijection i ↦ i + c that the number of pairs in S at any given distance d equals the boolean convolution sum of b at shift d. Under this correspondence, the total dyadic long-distance weight of S coincides with the dyadic class weight of b, and |S| equals the Hamming weight of b. The theorem then follows from cycle_power_dyadic_class_weight_le, which establishes the required inequality for binary words.

  1. The sum of indicators ∑_{e ∈ S} [e + d ∈ S] and the boolean sum ∑_{i < N - d} (b(i) && b(i + d)) equal the cardinalities of their respective satisfying subsets.

    Using `Finset.card_filter`, the left-hand sum of if-then-else terms is expressed as the size of {e ∈ S | e + d ∈ S}. Similarly, the right-hand sum of boolean conjunctions is rewritten as the size of {i < N - d | b(i) && b(i + d) = true}. By symmetry, it suffices to prove these two sets have equal size.

    lines 7–18

    uses Finset.card_filter, Finset.sum_congr, Eq.symm

      classical
      have hleft : (∑ e ∈ S, (if e + (d : ℤ) ∈ S then 1 else 0))
          = (S.filter (fun e => e + (d : ℤ) ∈ S)).card := by
        rw [Finset.card_filter]
      have hright : (Finset.range (N - d)).sum (fun i => (b i && b (i + d)).toNat)
          = ((Finset.range (N - d)).filter (fun i => (b i && b (i + d)) = true)).card := by
        rw [Finset.card_filter]
        apply Finset.sum_congr rfl
        intro i hi
        cases b i <;> cases b (i + d) <;> simp
      rw [hleft, hright]
      apply Eq.symm
  2. The shift map i ↦ i + c sends each index satisfying b(i) && b(i + d) = true into the set {e ∈ S | e + d ∈ S}.

    We establish the cardinality equality via `Finset.card_bij` using the map i ↦ i + c. If i < N - d satisfies b(i) = true and b(i + d) = true, then by the definition of b, both i + c ∈ S and (i + d) + c ∈ S. Since (i + c) + d = (i + d) + c, setting e = i + c yields e ∈ S and e + d ∈ S.

    lines 19–27

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_range, Bool.and_eq_true

      refine Finset.card_bij (fun i hi => (i : ℤ) + c) ?_ ?_ ?_
      · intro i hi
        simp only [Finset.mem_filter, Finset.mem_range, Bool.and_eq_true] at hi ⊢
        obtain ⟨hiN, hp, hq⟩ := hi
        have hbi : ((i:ℤ) + c) ∈ S := (hb i).mp hp
        have hb2 : (((i + d : ℕ) : ℤ) + c) ∈ S := (hb (i + d)).mp hq
        refine ⟨hbi, ?_⟩
        have heq : (i : ℤ) + c + (d : ℤ) = ((i + d : ℕ) : ℤ) + c := by push_cast; ring
        rw [heq]; exact hb2
  3. The map i ↦ i + c is injective.

    If i₁ + c = i₂ + c in ℤ, subtracting c gives i₁ = i₂, confirming injectivity.

    lines 28–30

      · intro i1 hi1 i2 hi2 heq
        have hZ : (i1 : ℤ) = (i2 : ℤ) := by linarith
        exact_mod_cast hZ
  4. The map i ↦ i + c is surjective onto {e ∈ S | e + d ∈ S}.

    Given e ∈ S with e + d ∈ S, the lower bound c ≤ e ensures e - c ≥ 0, giving an index i = (e - c).toNat. The upper bound e + d ≤ c + (N - 1) implies i < N - d. Furthermore, i + c = e ∈ S implies b(i) = true, and (i + d) + c = e + d ∈ S implies b(i + d) = true. Thus i belongs to the domain and maps to e.

    lines 31–55

    uses Finset.mem_filter, Finset.mem_range, Bool.and_eq_true, Int.toNat_of_nonneg, Int.toNat_lt, Nat.cast_sub

      · intro e he
        simp only [Finset.mem_filter] at he
        obtain ⟨heS, hedS⟩ := he
        have hce : 0 ≤ e - c := by linarith [hmin e heS]
        refine ⟨(e - c).toNat, ?_, ?_⟩
        · simp only [Finset.mem_filter, Finset.mem_range, Bool.and_eq_true]
          have hcast : (((e - c).toNat : ℕ) : ℤ) = e - c := Int.toNat_of_nonneg hce
          have hlt : (e - c).toNat < N - d := by
            rw [Int.toNat_lt hce, Nat.cast_sub hd]
            have hb' := hbound (e + (d : ℤ)) hedS
            have hN1 : ((N - 1 : ℕ) : ℤ) = (N:ℤ) - 1 := by
              rw [Nat.cast_sub hN]; norm_num
            rw [hN1] at hb'
            linarith
          refine ⟨hlt, ?_, ?_⟩
          · rw [hb]
            have : (((e - c).toNat : ℕ) : ℤ) + c = e := by rw [hcast]; ring
            exact this.symm ▸ heS
          · rw [hb]
            have hid : ((((e - c).toNat + d : ℕ)) : ℤ) + c = e + d := by
              push_cast; rw [hcast]; ring
            exact hid.symm ▸ hedS
        · show (((e - c).toNat : ℕ) : ℤ) + c = e
          have hcast : (((e - c).toNat : ℕ) : ℤ) = e - c := Int.toNat_of_nonneg hce
          rw [hcast]; ring
  5. The inequality holds trivially when S is empty. automation

    When S = ∅, the sum over S is empty (evaluating to 0) and the cardinality of S is 0, so the inequality 0 ≤ 0 is closed immediately by simplification.

    lines 64–66

      classical
      rcases S.eq_empty_or_nonempty with rfl | hS
      · simp
  6. When S is nonempty, let c = min S and encode membership in S via a boolean sequence b on [c, c + 2^m - 1].

    Setting c = S.min', we have c ∈ S and c ≤ x for all x ∈ S. By the diameter bound |x - c| ≤ 2^m - 1, every x ∈ S satisfies x ≤ c + (2^m - 1). The boolean predicate b(i) = decide (i + c ∈ S) then satisfies b(i) = true ↔ i + c ∈ S.

    lines 67–79

    uses Nat.one_le_two_pow, S.min'_mem, Finset.min'_le, abs_le

      have hN : 1 ≤ 2^m := Nat.one_le_two_pow
      set c : ℤ := S.min' hS with hcdef
      have hc : c ∈ S := by rw [hcdef]; exact S.min'_mem hS
      have hmin : ∀ x ∈ S, c ≤ x := by
        intro x hx; rw [hcdef]; exact Finset.min'_le S x hx
      have hbound : ∀ x ∈ S, x ≤ c + ((2^m - 1 : ℕ) : ℤ) := by
        intro x hx
        have h := hdiam x hx c hc
        rw [abs_le] at h
        linarith [h.2]
      set b : ℕ → Bool := fun i => decide (((i:ℤ) + c) ∈ S) with hbdef
      have hb : ∀ i, b i = true ↔ ((i:ℤ) + c) ∈ S := by
        intro i; simp [hbdef]
  7. The total weighted sum decomposes into an endpoint distance term and a double sum over dyadic shifts.

    Distributing the summation over the sum of terms, pulling out the constant factor 2, and swapping the order of summation over e ∈ S and j ∈ range m expresses the LHS as 2 ∑_{e ∈ S} [e + (2^m - 1) ∈ S] + ∑_{j < m} ∑_{e ∈ S} [j ≠ 0] [e + (2^m - 2^j) ∈ S].

    lines 80–87

    uses Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_comm

      have hstep :
          (∑ e ∈ S, (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +
            (Finset.range m).sum (fun j => if j = 0 then 0 else
              if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0)))
          = 2 * (∑ e ∈ S, (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0))
            + ∑ j ∈ Finset.range m, ∑ e ∈ S,
                (if j = 0 then 0 else if e + ((2^m - 2^j : ℕ):ℤ) ∈ S then 1 else 0) := by
        rw [Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_comm]
  8. The endpoint distance sum equals the single boolean product (b(0) && b(2^m - 1)).toNat.

    Applying the counting lemma with N = 2^m and shift d = 2^m - 1, the range length is N - d = 2^m - (2^m - 1) = 1. A sum over range 1 reduces to its only term at i = 0, which is (b(0) && b(2^m - 1)).toNat.

    lines 88–94

    uses cycle_power_dyadic_int_weight_le_card_count, Nat.sub_le, Nat.sub_sub_self, Finset.sum_range_one

      have hA : (∑ e ∈ S, (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0))
          = (b 0 && b (2^m - 1)).toNat := by
        have h := cycle_power_dyadic_int_weight_le_card_count (2^m) (2^m - 1) S c b hN (Nat.sub_le _ _) hb hmin hbound
        rw [h]
        have hsub : 2^m - (2^m - 1) = 1 := Nat.sub_sub_self hN
        rw [hsub, Finset.sum_range_one]
        simp
  9. For each scale j < m, the sum over e ∈ S of dyadic shift indicators equals the boolean correlation sum over range 2^j.

    For j = 0 the term is 0 by definition. For 0 < j < m, the counting lemma with N = 2^m and shift d = 2^m - 2^j yields a sum of length N - d = 2^m - (2^m - 2^j) = 2^j, precisely ∑_{i < 2^j} (b(i) && b(i + 2^m - 2^j)).toNat.

    lines 95–104

    uses if_false, Nat.pow_le_pow_right, le_of_lt, Finset.mem_range.mp, cycle_power_dyadic_int_weight_le_card_count, Nat.sub_le, Nat.sub_sub_self

      have hJ : ∀ j ∈ Finset.range m,
          (∑ e ∈ S, (if j = 0 then 0 else if e + ((2^m - 2^j : ℕ):ℤ) ∈ S then 1 else 0))
          = (if j = 0 then 0 else ∑ i ∈ Finset.range (2^j), (b i && b (i + (2^m - 2^j))).toNat) := by
        intro j hj
        by_cases hj0 : j = 0
        · subst hj0; simp
        · simp only [hj0, if_false]
          have hle : 2^j ≤ 2^m := Nat.pow_le_pow_right (by norm_num) (le_of_lt (Finset.mem_range.mp hj))
          have h := cycle_power_dyadic_int_weight_le_card_count (2^m) (2^m - 2^j) S c b hN (Nat.sub_le _ _) hb hmin hbound
          rw [h, Nat.sub_sub_self hle]
  10. The total weighted sum on S equals the dyadic class weight cycle_power_dyadic_class_weight m b.

    Substituting the evaluations of the endpoint distance term and each dyadic shift term into the decomposed sum matches the definition of cycle_power_dyadic_class_weight m b. Associativity of subtraction rewrites the index offset i + 2^m - 2^j into i + (2^m - 2^j).

    lines 105–121

    uses Finset.sum_congr, if_false, Nat.add_sub_assoc, Nat.pow_le_pow_right, le_of_lt, Finset.mem_range.mp

      have hEq :
          (∑ e ∈ S, (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +
            (Finset.range m).sum (fun j => if j = 0 then 0 else
              if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0)))
          = cycle_power_dyadic_class_weight m b := by
        rw [hstep, hA]
        unfold cycle_power_dyadic_class_weight
        congr 1
        apply Finset.sum_congr rfl
        intro j hj
        rw [hJ j hj]
        by_cases hj0 : j = 0
        · simp [hj0]
        · simp only [hj0, if_false]
          apply Finset.sum_congr rfl
          intro i hi
          rw [← Nat.add_sub_assoc (Nat.pow_le_pow_right (by norm_num) (le_of_lt (Finset.mem_range.mp hj)))]
  11. The cardinality of S equals the Hamming weight ∑_{i < 2^m} (b(i)).toNat.

    Applying the counting lemma with N = 2^m and shift d = 0, the sum over S becomes ∑_{e ∈ S} 1 = |S|, while the index sum becomes ∑_{i < 2^m} (b(i) && b(i)).toNat = ∑_{i < 2^m} (b(i)).toNat.

    lines 122–130

    uses cycle_power_dyadic_int_weight_le_card_count, Nat.zero_le, Nat.sub_zero, Nat.cast_zero, add_zero, Finset.sum_congr

      have hcard : (∑ i ∈ Finset.range (2^m), (b i).toNat) = S.card := by
        have h := cycle_power_dyadic_int_weight_le_card_count (2^m) 0 S c b hN (Nat.zero_le _) hb hmin hbound
        simp only [Nat.sub_zero, Nat.cast_zero, add_zero] at h
        have hS1 : (∑ e ∈ S, (if e ∈ S then 1 else 0)) = S.card := by simp
        have hb' : (∑ i ∈ Finset.range (2^m), (b i && b i).toNat)
            = ∑ i ∈ Finset.range (2^m), (b i).toNat := by
          apply Finset.sum_congr rfl; intro i hi; cases b i <;> rfl
        rw [hS1, hb'] at h
        exact h.symm
  12. The total dyadic weight of S is at most |S|.

    By the chain of relations, the weighted sum equals cycle_power_dyadic_class_weight m b, which is at most ∑_{i < 2^m} (b(i)).toNat by cycle_power_dyadic_class_weight_le, which in turn equals |S|.

    lines 131–137

    uses cycle_power_dyadic_class_weight_le

      calc
        (∑ e ∈ S, (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +
            (Finset.range m).sum (fun j => if j = 0 then 0 else
              if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0)))
            = cycle_power_dyadic_class_weight m b := hEq
        _ ≤ ∑ i ∈ Finset.range (2^m), (b i).toNat := cycle_power_dyadic_class_weight_le m hm b
        _ = S.card := hcard
Finset.card_filter
The number of elements in a finite set satisfying a predicate equals the sum over the set of the indicator of that predicate.
Finset.sum_congr
Two finite sums are equal if their index sets are equal and their summands agree on every element.
Eq.symm
Equality is symmetric: if a = b, then b = a.
Finset.card_bij
Two finite sets have the same cardinality if there is a bijection between them.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filter condition.
Finset.mem_range
A natural number belongs to the range {0, ..., n-1} if and only if it is strictly less than n.
Bool.and_eq_true
The boolean AND of two booleans is true if and only if both are true.
Int.toNat_of_nonneg
For any non-negative integer, converting it to a natural number and back preserves its value.
Int.toNat_lt
For a non-negative integer z, z.toNat < n is equivalent to z < n.
Nat.cast_sub
Casting the difference of natural numbers m ≤ n to an additive group with one equals the difference of their casts.
Nat.one_le_two_pow
For any natural number n, 2^n is at least 1.
S.min'_mem
The minimum element of a non-empty finite set belongs to the set.
Finset.min'_le
The minimum element of a finite set is less than or equal to any element in the set.
abs_le
The absolute value |a| is at most b if and only if -b ≤ a ≤ b.
Finset.sum_add_distrib
The sum of a sum over a finite set equals the sum of the individual sums.
Finset.mul_sum
Multiplication distributes over a finite sum.
Finset.sum_comm
The order of summation in a double finite sum can be interchanged.
cycle_power_dyadic_int_weight_le_card_count
For an integer subset S ⊆ [c, c + N - 1] and its indicator b(i) = [i + c ∈ S], the number of pairs (e, e + d) in S equals the sum of b(i) && b(i + d) for i < N - d.
Nat.sub_le
Subtracting a natural number from n yields at most n.
Nat.sub_sub_self
For natural numbers with m ≤ n, n - (n - m) = m.
Finset.sum_range_one
A sum over the singleton range {0} evaluates to the summand at 0.
if_false
An if-then-else whose condition is false evaluates to the else branch.
Nat.pow_le_pow_right
For a base n > 0, n^i ≤ n^j whenever i ≤ j.
le_of_lt
A strict inequality a < b implies a ≤ b.
Finset.mem_range.mp
If m belongs to the range {0, ..., n-1}, then m < n.
Nat.add_sub_assoc
For natural numbers with k ≤ m, (n + m) - k = n + (m - k).
Nat.zero_le
Zero is less than or equal to any natural number.
Nat.sub_zero
Subtracting zero from a natural number leaves it unchanged.
Nat.cast_zero
The cast of the natural number 0 is 0.
add_zero
Adding zero to any element yields that element.
cycle_power_dyadic_class_weight_le
For any boolean sequence b and m ≥ 1, its dyadic class weight is bounded by its Hamming weight on range 2^m.

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

private lemma cycle_power_dyadic_int_weight_le_card_count (N d : ℕ) (S : Finset ℤ) (c : ℤ) (b : ℕ → Bool)    (hN : 1 ≤ N) (hd : d ≤ N)    (hb : ∀ i, b i = true ↔ ((i:ℤ) + c) ∈ S)    (hmin : ∀ x ∈ S, c ≤ x) (hbound : ∀ x ∈ S, x ≤ c + ((N - 1 : ℕ) : ℤ)) :    (∑ e ∈ S, (if e + (d : ℤ) ∈ S then 1 else 0)) =      (Finset.range (N - d)).sum (fun i => (b i && b (i + d)).toNat) := by  classical  have hleft : (∑ e ∈ S, (if e + (d : ℤ) ∈ S then 1 else 0))      = (S.filter (fun e => e + (d : ℤ) ∈ S)).card := by    rw [Finset.card_filter]  have hright : (Finset.range (N - d)).sum (fun i => (b i && b (i + d)).toNat)      = ((Finset.range (N - d)).filter (fun i => (b i && b (i + d)) = true)).card := by    rw [Finset.card_filter]    apply Finset.sum_congr rfl    intro i hi    cases b i <;> cases b (i + d) <;> simp  rw [hleft, hright]  apply Eq.symm  refine Finset.card_bij (fun i hi => (i : ℤ) + c) ?_ ?_ ?_  · intro i hi    simp only [Finset.mem_filter, Finset.mem_range, Bool.and_eq_true] at hi ⊢    obtain ⟨hiN, hp, hq⟩ := hi    have hbi : ((i:ℤ) + c) ∈ S := (hb i).mp hp    have hb2 : (((i + d : ℕ) : ℤ) + c) ∈ S := (hb (i + d)).mp hq    refine ⟨hbi, ?_⟩    have heq : (i : ℤ) + c + (d : ℤ) = ((i + d : ℕ) : ℤ) + c := by push_cast; ring    rw [heq]; exact hb2  · intro i1 hi1 i2 hi2 heq    have hZ : (i1 : ℤ) = (i2 : ℤ) := by linarith    exact_mod_cast hZ  · intro e he    simp only [Finset.mem_filter] at he    obtain ⟨heS, hedS⟩ := he    have hce : 0 ≤ e - c := by linarith [hmin e heS]    refine ⟨(e - c).toNat, ?_, ?_⟩    · simp only [Finset.mem_filter, Finset.mem_range, Bool.and_eq_true]      have hcast : (((e - c).toNat : ℕ) : ℤ) = e - c := Int.toNat_of_nonneg hce      have hlt : (e - c).toNat < N - d := by        rw [Int.toNat_lt hce, Nat.cast_sub hd]        have hb' := hbound (e + (d : ℤ)) hedS        have hN1 : ((N - 1 : ℕ) : ℤ) = (N:ℤ) - 1 := by          rw [Nat.cast_sub hN]; norm_num        rw [hN1] at hb'        linarith      refine ⟨hlt, ?_, ?_⟩      · rw [hb]        have : (((e - c).toNat : ℕ) : ℤ) + c = e := by rw [hcast]; ring        exact this.symm ▸ heS      · rw [hb]        have hid : ((((e - c).toNat + d : ℕ)) : ℤ) + c = e + d := by          push_cast; rw [hcast]; ring        exact hid.symm ▸ hedS    · show (((e - c).toNat : ℕ) : ℤ) + c = e      have hcast : (((e - c).toNat : ℕ) : ℤ) = e - c := Int.toNat_of_nonneg hce      rw [hcast]; ringtheorem cycle_power_dyadic_int_weight_le_card    (m : ℕ) (hm : 1 ≤ m) (S : Finset ℤ)    (hdiam : ∀ a ∈ S, ∀ b ∈ S, |a - b| ≤ ((2 ^ m - 1 : ℕ) : ℤ)) :    (∑ e ∈ S,      (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +        (Finset.range m).sum (fun j => if j = 0 then 0 else          if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0))) ≤ S.card := by  classical  rcases S.eq_empty_or_nonempty with rfl | hS  · simp  have hN : 1 ≤ 2^m := Nat.one_le_two_pow  set c : ℤ := S.min' hS with hcdef  have hc : c ∈ S := by rw [hcdef]; exact S.min'_mem hS  have hmin : ∀ x ∈ S, c ≤ x := by    intro x hx; rw [hcdef]; exact Finset.min'_le S x hx  have hbound : ∀ x ∈ S, x ≤ c + ((2^m - 1 : ℕ) : ℤ) := by    intro x hx    have h := hdiam x hx c hc    rw [abs_le] at h    linarith [h.2]  set b : ℕ → Bool := fun i => decide (((i:ℤ) + c) ∈ S) with hbdef  have hb : ∀ i, b i = true ↔ ((i:ℤ) + c) ∈ S := by    intro i; simp [hbdef]  have hstep :      (∑ e ∈ S, (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +        (Finset.range m).sum (fun j => if j = 0 then 0 else          if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0)))      = 2 * (∑ e ∈ S, (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0))        + ∑ j ∈ Finset.range m, ∑ e ∈ S,            (if j = 0 then 0 else if e + ((2^m - 2^j : ℕ):ℤ) ∈ S then 1 else 0) := by    rw [Finset.sum_add_distrib, Finset.mul_sum, Finset.sum_comm]  have hA : (∑ e ∈ S, (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0))      = (b 0 && b (2^m - 1)).toNat := by    have h := cycle_power_dyadic_int_weight_le_card_count (2^m) (2^m - 1) S c b hN (Nat.sub_le _ _) hb hmin hbound    rw [h]    have hsub : 2^m - (2^m - 1) = 1 := Nat.sub_sub_self hN    rw [hsub, Finset.sum_range_one]    simp  have hJ : ∀ j ∈ Finset.range m,      (∑ e ∈ S, (if j = 0 then 0 else if e + ((2^m - 2^j : ℕ):ℤ) ∈ S then 1 else 0))      = (if j = 0 then 0 else ∑ i ∈ Finset.range (2^j), (b i && b (i + (2^m - 2^j))).toNat) := by    intro j hj    by_cases hj0 : j = 0    · subst hj0; simp    · simp only [hj0, if_false]      have hle : 2^j ≤ 2^m := Nat.pow_le_pow_right (by norm_num) (le_of_lt (Finset.mem_range.mp hj))      have h := cycle_power_dyadic_int_weight_le_card_count (2^m) (2^m - 2^j) S c b hN (Nat.sub_le _ _) hb hmin hbound      rw [h, Nat.sub_sub_self hle]  have hEq :      (∑ e ∈ S, (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +        (Finset.range m).sum (fun j => if j = 0 then 0 else          if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0)))      = cycle_power_dyadic_class_weight m b := by    rw [hstep, hA]    unfold cycle_power_dyadic_class_weight    congr 1    apply Finset.sum_congr rfl    intro j hj    rw [hJ j hj]    by_cases hj0 : j = 0    · simp [hj0]    · simp only [hj0, if_false]      apply Finset.sum_congr rfl      intro i hi      rw [← Nat.add_sub_assoc (Nat.pow_le_pow_right (by norm_num) (le_of_lt (Finset.mem_range.mp hj)))]  have hcard : (∑ i ∈ Finset.range (2^m), (b i).toNat) = S.card := by    have h := cycle_power_dyadic_int_weight_le_card_count (2^m) 0 S c b hN (Nat.zero_le _) hb hmin hbound    simp only [Nat.sub_zero, Nat.cast_zero, add_zero] at h    have hS1 : (∑ e ∈ S, (if e ∈ S then 1 else 0)) = S.card := by simp    have hb' : (∑ i ∈ Finset.range (2^m), (b i && b i).toNat)        = ∑ i ∈ Finset.range (2^m), (b i).toNat := by      apply Finset.sum_congr rfl; intro i hi; cases b i <;> rfl    rw [hS1, hb'] at h    exact h.symm  calc    (∑ e ∈ S, (2 * (if e + ((2 ^ m - 1 : ℕ) : ℤ) ∈ S then 1 else 0) +        (Finset.range m).sum (fun j => if j = 0 then 0 else          if e + ((2 ^ m - 2 ^ j : ℕ) : ℤ) ∈ S then 1 else 0)))        = cycle_power_dyadic_class_weight m b := hEq    _ ≤ ∑ i ∈ Finset.range (2^m), (b i).toNat := cycle_power_dyadic_class_weight_le m hm b    _ = S.card := hcard
See it in the graphDiscuss this resultChallenge it