cycle_power_dyadic_weighted_threshold_weight_ge
Common-threshold coupling of any finite natural-weighted mixture of dyadic profiles cannot decrease total dyadic class weight.
Statement
theorem cycle_power_dyadic_weighted_threshold_weight_ge {ι : Type*} (m : ℕ) (S : Finset ι) (w : ι → ℕ) (B : ι → ℕ → Bool) : let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) ≤ (range N).sum (fun r => cycle_power_dyadic_class_weight m (fun j => decide (r < c j)))
- Source
- Standard finite common-threshold coupling, formalized as a helper for OP-205 / RT-1, arXiv:2610.15635. Used to compress whole-class linear relaxations. This does not prove the remaining shape implication and is not claimed novel or research-level.
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- bool_weighted_mixture_threshold_dominatesEvery finite natural-weighted mixture of Boolean profiles admits a common-threshold coupling with the same coordinate masses, at least the…
- 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 1
- cycle_power_dyadic_weighted_threshold_tightFor positive dyadic exponent, every common-threshold profile below total mixture mass is tight when all original profiles of the…
The proof, explained
The dyadic class weight of a profile is a positive linear combination of pairwise bit conjunctions: a boundary term at distance 2^m - 1, and dyadic block terms at distances 2^m - 2^j. By threshold coupling dominance (bool_weighted_mixture_threshold_dominates), the co-occurrence frequency of any coordinate pair under the threshold coupling bounds from above its weighted co-occurrence in the original mixture. Summing this pairwise dominance term-by-term across all pairs occurring in the definition of the dyadic class weight shows that coupling cannot decrease the total weight.
Define the total weight N, marginal counts c, and threshold profiles T, and establish coordinate-pair domination.
We introduce the total weight N = ∑_{i ∈ S} w_i, the weighted marginal counts c(j) = ∑_{i ∈ S} w_i B_i(j), and the threshold profiles T_r(j) = [r < c(j)] for r < N. By bool_weighted_mixture_threshold_dominates, threshold coupling dominates the mixture on every pair of coordinates: for all a and b, the weighted sum of conjunctions ∑_{i ∈ S} w_i (B_i(a) ∧ B_i(b)) is bounded above by the threshold sum ∑_{r < N} (T_r(a) ∧ T_r(b)).
uses
bool_weighted_mixture_threshold_dominatesdsimp only let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) let T := fun r j => decide (r < c j) have hdom := (bool_weighted_mixture_threshold_dominates S w B).2.1
The weighted sum of the boundary ("ends") terms is bounded by the threshold coupled sum.
Instantiating pairwise domination at coordinates 0 and 2^m - 1 and multiplying by 2 yields 2 ∑_{i ∈ S} w_i (B_i(0) ∧ B_i(2^m - 1)) ≤ 2 ∑_{r < N} (T_r(0) ∧ T_r(2^m - 1)). Distributing the scalar 2 inside the summations gives the desired bound for the boundary term.
uses
Nat.mul_le_mul_left,mul_sum,mul_left_commhave hends : (S.sum (fun i => w i * (2 * (B i 0 && B i (2^m-1)).toNat))) ≤ (range N).sum (fun r => 2 * (T r 0 && T r (2^m-1)).toNat) := by have h := Nat.mul_le_mul_left 2 (hdom 0 (2^m-1)) simpa only [mul_sum, T, c, N, mul_left_comm] using h
To bound the remaining dyadic terms, it suffices to prove the inequality scale-by-scale for each j < m.
Distributing the weights w_i into the summation over j and swapping the order of summation between the mixture index i ∈ S (respectively, the threshold index r) and the scale index j ∈ {0, …, m - 1} reduces the inequality to comparing the summands for each j individually.
uses
mul_sum,sum_comm,sum_le_sumhave hrest : S.sum (fun i => w i * (range m).sum (fun j => if j=0 then 0 else (range (2^j)).sum (fun a => (B i a && B i (a+2^m-2^j)).toNat))) ≤ (range N).sum (fun r => (range m).sum (fun j => if j=0 then 0 else (range (2^j)).sum (fun a => (T r a && T r (a+2^m-2^j)).toNat))) := by simp only [mul_sum] conv_lhs => rw [sum_comm] conv_rhs => rw [sum_comm] apply sum_le_sum
The inequality holds for each dyadic scale j.
We split into cases on j. When j = 0, both sides vanish. When j ≠ 0, swapping the summation over the mixture index and the offset a ∈ {0, …, 2^j - 1} allows us to apply pairwise domination to each coordinate pair (a, a + 2^m - 2^j) individually.
uses
mul_sum,sum_comm,sum_le_sumintro j hj by_cases hj0 : j=0 · simp [hj0] · simp only [hj0, ↓reduceIte, mul_sum] conv_lhs => rw [sum_comm] conv_rhs => rw [sum_comm] exact sum_le_sum (fun a ha => hdom a (a+2^m-2^j))
The total weighted dyadic class weight is bounded by the threshold coupled dyadic class weight.
Unfolding cycle_power_dyadic_class_weight decomposes the total weight into the boundary term and the dyadic block sums. Adding the boundary inequality hends and the internal blocks inequality hrest yields the result.
uses
cycle_power_dyadic_class_weight,mul_add,sum_add_distrib,add_le_addsimp only [cycle_power_dyadic_class_weight, mul_add, sum_add_distrib] exact add_le_add hends hrest
bool_weighted_mixture_threshold_dominates- For any finite weighted mixture of Boolean profiles, the threshold coupling preserves marginal frequencies and dominates the mixture's co-occurrence frequency on any coordinate pair: ∑ w_i (B_i(a) ∧ B_i(b)) ≤ ∑ (T_r(a) ∧ T_r(b)).
Nat.mul_le_mul_left- Multiplying both sides of an inequality of natural numbers by a factor on the left preserves the inequality: n ≤ m implies k * n ≤ k * m.
mul_sum- Multiplication distributes over a finite sum: a * ∑ x ∈ s, f x = ∑ x ∈ s, a * f x.
mul_left_comm- Multiplication in a commutative semigroup is left-commutative: a * (b * c) = b * (a * c).
sum_comm- Double finite summations may be interchanged: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
sum_le_sum- A finite sum of pointwise less-than-or-equal terms is less than or equal to the sum of the upper bounds: (∀ i ∈ s, f i ≤ g i) implies ∑ i ∈ s, f i ≤ ∑ i ∈ s, g i.
cycle_power_dyadic_class_weight- The dyadic class weight of a profile is defined as twice the conjunction of its boundary bits b(0) ∧ b(2^m - 1) plus the sum over scales j ∈ {1, …, m - 1} and offsets a < 2^j of the conjunctions b(a) ∧ b(a + 2^m - 2^j).
mul_add- Multiplication distributes over addition on the left: a * (b + c) = a * b + a * c.
sum_add_distrib- The sum of a termwise sum over a finite set equals the sum of the two sums: ∑ x ∈ s, (f x + g x) = ∑ x ∈ s, f x + ∑ x ∈ s, g x.
add_le_add- Addition preserves inequalities: a ≤ b and c ≤ d imply a + c ≤ b + d.
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 4000theorem cycle_power_dyadic_weighted_threshold_weight_ge {ι : Type*} (m : ℕ) (S : Finset ι) (w : ι → ℕ) (B : ι → ℕ → Bool) : let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) ≤ (range N).sum (fun r => cycle_power_dyadic_class_weight m (fun j => decide (r < c j))) := by dsimp only let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) let T := fun r j => decide (r < c j) have hdom := (bool_weighted_mixture_threshold_dominates S w B).2.1 have hends : (S.sum (fun i => w i * (2 * (B i 0 && B i (2^m-1)).toNat))) ≤ (range N).sum (fun r => 2 * (T r 0 && T r (2^m-1)).toNat) := by have h := Nat.mul_le_mul_left 2 (hdom 0 (2^m-1)) simpa only [mul_sum, T, c, N, mul_left_comm] using h have hrest : S.sum (fun i => w i * (range m).sum (fun j => if j=0 then 0 else (range (2^j)).sum (fun a => (B i a && B i (a+2^m-2^j)).toNat))) ≤ (range N).sum (fun r => (range m).sum (fun j => if j=0 then 0 else (range (2^j)).sum (fun a => (T r a && T r (a+2^m-2^j)).toNat))) := by simp only [mul_sum] conv_lhs => rw [sum_comm] conv_rhs => rw [sum_comm] apply sum_le_sum intro j hj by_cases hj0 : j=0 · simp [hj0] · simp only [hj0, ↓reduceIte, mul_sum] conv_lhs => rw [sum_comm] conv_rhs => rw [sum_comm] exact sum_le_sum (fun a ha => hdom a (a+2^m-2^j)) simp only [cycle_power_dyadic_class_weight, mul_add, sum_add_distrib] exact add_le_add hends hrest