cycle_power_dyadic_class_weight_eq_of_sum_eq
If the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every residue.
Statement
theorem cycle_power_dyadic_class_weight_eq_of_sum_eq (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (b : ZMod n → ℕ → Bool) (hsum : (∑ p : ZMod n, cycle_power_dyadic_class_weight m (b p)) = ∑ p : ZMod n, (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat)) : ∀ p : ZMod n, cycle_power_dyadic_class_weight m (b p) = (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat)
- Source
- step towards simple_graph_cycle_power_dyadic_cover_class_model
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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.
- 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 2
- cycle_power_dyadic_zmod_model_tight_of_countsFor a positive exponent m, nonzero natural period n, and Boolean profiles indexed by ZMod n, exact dyadic edge-owner sums of one and…
- 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…
The proof, explained
The proof proceeds by contradiction. Since each residue's dyadic class weight is individually at most its count of active bits, a failure of equality at any residue would make the weight strictly smaller there. Summing over all residues would then force the total dyadic class weight to be strictly less than the total active count, contradicting the hypothesis that the two sums are equal.
For an arbitrary residue p, the dyadic class weight is bounded above by the active bit count.
Fix a residue p ∈ ℤ/nℤ. By `cycle_power_dyadic_class_weight_le`, the dyadic class weight of b(p) is at most the sum of (b(p, a)).toNat over a ∈ {0, …, 2^m - 1}.
uses
cycle_power_dyadic_class_weight_leintro p have hle := cycle_power_dyadic_class_weight_le m hm (b p)
If equality fails at residue p, the dyadic class weight at p is strictly less than the active bit count.
Assume for contradiction that equality does not hold at p. Since the dyadic class weight is bounded above by the active count, non-equality forces it to be strictly smaller, which linear arithmetic (`omega`) verifies.
by_contra hne have hlt : cycle_power_dyadic_class_weight m (b p) < (Finset.range (2^m)).sum (fun a => (b p a).toNat) := by omega
The total sum of dyadic class weights over all residues is strictly less than the total sum of active counts.
By `sum_lt_sum`, because the weak inequality holds for all residues q via `cycle_power_dyadic_class_weight_le` and the strict inequality holds at p (which belongs to the universe of residues by `mem_univ`), summing over all residues in ℤ/nℤ produces a strict inequality between the total sums.
uses
sum_lt_sum,cycle_power_dyadic_class_weight_le,mem_univhave hslt := sum_lt_sum (fun q _ => cycle_power_dyadic_class_weight_le m hm (b q)) ⟨p, mem_univ _, hlt⟩
Contradiction.
The strict inequality between the total sums directly contradicts the hypothesis `hsum` asserting that they are equal. Linear integer arithmetic (`omega`) identifies this contradiction and concludes the proof.
omega
cycle_power_dyadic_class_weight_le- For any m ≥ 1 and boolean sequence b, the dyadic class weight of b is at most the sum of the active bits over indices 0 ≤ i < 2^m.
sum_lt_sum- A finite sum of terms is strictly less than another if the summands satisfy a pointwise weak inequality everywhere and a strict inequality at at least one element of the index set.
mem_univ- Every element of a finite type belongs to the universal finite set univ.
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.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000/-- If the total sum of dyadic class weights over all residues equals the total sum of active counts, then pointwise equality holds for every residue. -/theorem cycle_power_dyadic_class_weight_eq_of_sum_eq (m n : ℕ) [NeZero n] (hm : 1 ≤ m) (b : ZMod n → ℕ → Bool) (hsum : (∑ p : ZMod n, cycle_power_dyadic_class_weight m (b p)) = ∑ p : ZMod n, (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat)) : ∀ p : ZMod n, cycle_power_dyadic_class_weight m (b p) = (Finset.range (2 ^ m)).sum (fun a => (b p a).toNat) := by intro p have hle := cycle_power_dyadic_class_weight_le m hm (b p) by_contra hne have hlt : cycle_power_dyadic_class_weight m (b p) < (Finset.range (2^m)).sum (fun a => (b p a).toNat) := by omega have hslt := sum_lt_sum (fun q _ => cycle_power_dyadic_class_weight_le m hm (b q)) ⟨p, mem_univ _, hlt⟩ omega