cycle_power_dyadic_int_weight_le_card
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 3
- simple_graph_cycle_power_dyadic_layer_weight_leIn any clique labelling of a cycle power with dyadic bandwidth 2^m-1 and n at least three times the bandwidth plus one, the total layer…
- simple_graph_cycle_power_dyadic_cover_class_modelEvery optimal dyadic cycle-power equivalence cover admits a faithful periodic integer class model with the original rooted classes and…
- simple_graph_cycle_power_dyadic_cover_class_spanningEvery label class of an optimal m+1-layer cover at dyadic bandwidth is spanned by an endpoint-distance pair: each vertex lies in a class…
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.
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.
uses
Finset.card_filter,Finset.sum_congr,Eq.symmclassical 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
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.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_range,Bool.and_eq_truerefine 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
The map i ↦ i + c is injective.
If i₁ + c = i₂ + c in ℤ, subtracting c gives i₁ = i₂, confirming injectivity.
· intro i1 hi1 i2 hi2 heq have hZ : (i1 : ℤ) = (i2 : ℤ) := by linarith exact_mod_cast hZ
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.
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
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.
classical rcases S.eq_empty_or_nonempty with rfl | hS · simp
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.
uses
Nat.one_le_two_pow,S.min'_mem,Finset.min'_le,abs_lehave 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]
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].
uses
Finset.sum_add_distrib,Finset.mul_sum,Finset.sum_commhave 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]
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.
uses
cycle_power_dyadic_int_weight_le_card_count,Nat.sub_le,Nat.sub_sub_self,Finset.sum_range_onehave 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
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.
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_selfhave 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]
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).
uses
Finset.sum_congr,if_false,Nat.add_sub_assoc,Nat.pow_le_pow_right,le_of_lt,Finset.mem_range.mphave 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)))]
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.
uses
cycle_power_dyadic_int_weight_le_card_count,Nat.zero_le,Nat.sub_zero,Nat.cast_zero,add_zero,Finset.sum_congrhave 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
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|.
uses
cycle_power_dyadic_class_weight_lecalc (∑ 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.
- The proof reduces the integer set inequality to an abstract bound on boolean strings (`cycle_power_dyadic_class_weight_le`) via the indicator sequence $b(i) = [i + \min S \in S]$.
- The lemma `cycle_power_dyadic_int_weight_le_card_count` establishes the connection between integer shift pair counts and boolean convolutions via the bijection $i \mapsto i + \min S$.
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.
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