cycle_power_dyadic_weighted_threshold_tight
For positive dyadic exponent, every common-threshold profile below total mixture mass is tight when all original profiles of the natural-weighted finite mixture are tight.
Statement
theorem cycle_power_dyadic_weighted_threshold_tight {ι : Type*} (m : ℕ) (hm : 1 ≤ m) (S : Finset ι) (w : ι → ℕ) (B : ι → ℕ → Bool) (htight : ∀ i ∈ S, cycle_power_dyadic_class_weight m (B i) = (range (2^m)).sum (fun a => (B i a).toNat)) : let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) ∀ r < N, cycle_power_dyadic_class_weight m (fun j => decide (r < c j)) = (range (2^m)).sum (fun a => (decide (r < c a)).toNat)
- 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 4
- 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_weighted_threshold_weight_geCommon-threshold coupling of any finite natural-weighted mixture of dyadic profiles cannot decrease total dyadic class weight.
- 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.
The proof, explained
The proof establishes that every common-threshold profile $T_r$ below the total mixture weight $N$ is tight by a squeezing contradiction argument. Marginal preservation shows that the total cardinality of all threshold profiles equals the weighted cardinality of the original profiles, which equals the total weighted class weight because all original profiles are tight. A general threshold bound then ensures that this total cardinality is at most the total class weight of the threshold profiles. Since each individual threshold profile's class weight cannot exceed its cardinality, any profile failing to be tight would force the sum of class weights to be strictly less than the sum of cardinalities, producing a contradiction.
Set up notation for the mixture mass, column counts, and threshold profiles, restating the goal in terms of threshold profiles $T_r$.
We introduce abbreviations for the total mixture mass $N = \sum_{i \in S} w_i$, column counts $c(j) = \sum_{i \in S} w_i B_i(j)$, and threshold indicator profiles $T_r(j) = [r < c(j)]$. The target statement is that for every threshold $r < N$, the profile $T_r$ is tight, meaning its dyadic cycle-power class weight equals its cardinality $\sum_{a < 2^m} T_r(a)$.
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) change ∀ r < N, cycle_power_dyadic_class_weight m (T r) = (range (2^m)).sum (fun a => (T r a).toNat)
The total size of the threshold profiles equals the weighted total size of the original profiles: $\sum_{r < N} |T_r| = \sum_{i \in S} w_i |B_i|$.
By marginal preservation (`bool_weighted_mixture_threshold_dominates`), summing threshold indicators over all $r < N$ yields the column count: $\sum_{r < N} T_r(a) = c(a)$. Exchanging the order of summation (`sum_comm`) transforms the total threshold size $\sum_{r < N} \sum_{a < 2^m} T_r(a)$ into $\sum_{a < 2^m} c(a)$. Substituting the definition of $c(a)$, swapping sums again (`sum_comm`), and distributing the weights (`mul_sum`) yields the weighted sum of original profile sizes $\sum_{i \in S} w_i \sum_{a < 2^m} B_i(a)$.
uses
bool_weighted_mixture_threshold_dominates,sum_comm,mul_sumhave hmargin := (bool_weighted_mixture_threshold_dominates S w B).1 have hcard : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by rw [sum_comm] simp_rw [show ∀ a, (range N).sum (fun r => (T r a).toNat) = c a from hmargin] dsimp only [c] rw [sum_comm] simp only [mul_sum]
The weighted class weight of the mixture is at most the total threshold class weight, and equals the weighted sum of original sizes.
By `cycle_power_dyadic_weighted_threshold_weight_ge`, the total threshold class weight upper-bounds the weighted original class weight: $\sum_{i \in S} w_i \mathrm{weight}(B_i) \le \sum_{r < N} \mathrm{weight}(T_r)$. Furthermore, because each original profile $B_i$ is tight by hypothesis (`htight`), we have $\mathrm{weight}(B_i) = |B_i|$, so by congruence (`sum_congr`, `congrArg`) the weighted sum of original class weights equals the weighted sum of their sizes.
uses
cycle_power_dyadic_weighted_threshold_weight_ge,sum_congr,congrArghave hW := cycle_power_dyadic_weighted_threshold_weight_ge m S w B have hOld : S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by exact sum_congr rfl (fun i hi => congrArg (fun z => w i * z) (htight i hi))
The total cardinality of all threshold profiles is at most their total class weight: $\sum_{r < N} |T_r| \le \sum_{r < N} \mathrm{weight}(T_r)$.
We chain the equalities and inequality established in the preceding steps: the sum of threshold sizes equals the weighted sum of original sizes, which equals the weighted sum of original class weights, which is bounded above by the sum of threshold class weights.
have hTotal : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) ≤ (range N).sum (fun r => cycle_power_dyadic_class_weight m (T r)) := by calc _ = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := hcard _ = S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) := hOld.symm _ ≤ _ := hW
If any threshold profile $T_r$ (for $r < N$) were not tight, its class weight would be strictly less than its cardinality.
Fix $r < N$. For any profile, its class weight is at most its cardinality by `cycle_power_dyadic_class_weight_le`. Assuming for contradiction that $T_r$ is not tight, the weight cannot equal the cardinality, so linear arithmetic (`omega`) deduces that the strict inequality $\mathrm{weight}(T_r) < |T_r|$ must hold.
uses
cycle_power_dyadic_class_weight_leintro r hr have hle := cycle_power_dyadic_class_weight_le m hm (T r) by_contra hne have hlt : cycle_power_dyadic_class_weight m (T r) < (range (2^m)).sum (fun a => (T r a).toNat) := by omega
Every threshold profile $T_r$ for $r < N$ is tight.
Summing the pointwise weak bounds $\mathrm{weight}(T_q) \le |T_q|$ across all $q < N$ together with the strict inequality $\mathrm{weight}(T_r) < |T_r|$ at index $r \in \mathrm{range}(N)$ (`mem_range`) via `sum_lt_sum` yields a strict inequality on total sums: $\sum_{q < N} \mathrm{weight}(T_q) < \sum_{q < N} |T_q|$. This contradicts the aggregate lower bound $\sum_{r < N} |T_r| \le \sum_{r < N} \mathrm{weight}(T_r)$ established earlier. Linear arithmetic (`omega`) closes the contradiction.
uses
sum_lt_sum,cycle_power_dyadic_class_weight_le,mem_rangehave hs := sum_lt_sum (fun q (_ : q ∈ range N) => cycle_power_dyadic_class_weight_le m hm (T q)) ⟨r, mem_range.mpr hr, hlt⟩ omega
bool_weighted_mixture_threshold_dominates- For a weighted mixture of boolean profiles, the threshold profiles preserve marginal column sums, dominate pairwise intersections, and preserve subset inclusions.
sum_comm- Swapping the order of two finite summations preserves the sum: $\sum_x \sum_y f(x, y) = \sum_y \sum_x f(x, y)$.
mul_sum- Multiplication distributes over a finite sum: $a \cdot \sum_i f(i) = \sum_i a \cdot f(i)$.
cycle_power_dyadic_weighted_threshold_weight_ge- The weighted sum of dyadic cycle-power class weights of the constituent profiles is bounded above by the sum of class weights of the threshold profiles.
sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element of the index set.
congrArg- Equal inputs to a function yield equal outputs ($a_1 = a_2 \implies f(a_1) = f(a_2)$).
cycle_power_dyadic_class_weight_le- For dyadic exponent $m \ge 1$, the dyadic cycle-power class weight of a boolean profile is bounded above by its cardinality (number of true entries).
sum_lt_sum- If $f(i) \le g(i)$ for all elements of a finite set and $f(i) < g(i)$ for at least one element, then the sum of $f$ is strictly less than the sum of $g$.
mem_range- A natural number $m$ belongs to `Finset.range n` if and only if $m < n$.
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_tight {ι : Type*} (m : ℕ) (hm : 1 ≤ m) (S : Finset ι) (w : ι → ℕ) (B : ι → ℕ → Bool) (htight : ∀ i ∈ S, cycle_power_dyadic_class_weight m (B i) = (range (2^m)).sum (fun a => (B i a).toNat)) : let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) ∀ r < N, cycle_power_dyadic_class_weight m (fun j => decide (r < c j)) = (range (2^m)).sum (fun a => (decide (r < c a)).toNat) := 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) change ∀ r < N, cycle_power_dyadic_class_weight m (T r) = (range (2^m)).sum (fun a => (T r a).toNat) have hmargin := (bool_weighted_mixture_threshold_dominates S w B).1 have hcard : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by rw [sum_comm] simp_rw [show ∀ a, (range N).sum (fun r => (T r a).toNat) = c a from hmargin] dsimp only [c] rw [sum_comm] simp only [mul_sum] have hW := cycle_power_dyadic_weighted_threshold_weight_ge m S w B have hOld : S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := by exact sum_congr rfl (fun i hi => congrArg (fun z => w i * z) (htight i hi)) have hTotal : (range N).sum (fun r => (range (2^m)).sum (fun a => (T r a).toNat)) ≤ (range N).sum (fun r => cycle_power_dyadic_class_weight m (T r)) := by calc _ = S.sum (fun i => w i * (range (2^m)).sum (fun a => (B i a).toNat)) := hcard _ = S.sum (fun i => w i * cycle_power_dyadic_class_weight m (B i)) := hOld.symm _ ≤ _ := hW intro r hr have hle := cycle_power_dyadic_class_weight_le m hm (T r) by_contra hne have hlt : cycle_power_dyadic_class_weight m (T r) < (range (2^m)).sum (fun a => (T r a).toNat) := by omega have hs := sum_lt_sum (fun q (_ : q ∈ range N) => cycle_power_dyadic_class_weight_le m hm (T q)) ⟨r, mem_range.mpr hr, hlt⟩ omega