bool_weighted_mixture_threshold_dominates
Every finite natural-weighted mixture of Boolean profiles admits a common-threshold coupling with the same coordinate masses, at least the old mass on every selected pair, and every original pointwise Boolean implication preserved.
Statement
theorem bool_weighted_mixture_threshold_dominates {ι κ : Type*} (S : Finset ι) (w : ι → ℕ) (B : ι → κ → Bool) : 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) (∀ j, (range N).sum (fun r => (T r j).toNat) = c j) ∧ (∀ a b, S.sum (fun i => w i * (B i a && B i b).toNat) ≤ (range N).sum (fun r => (T r a && T r b).toNat)) ∧ (∀ a b, (∀ i ∈ S, B i a = true → B i b = true) → ∀ r, T r a = true → T r b = true)
- 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_threshold_marginal_sumA finite threshold membership sum equals the smaller of its range length and its capacity.
- bool_threshold_pair_sumTwo Boolean threshold coordinates have joint membership sum equal to the minimum of the range length and both capacities.
- Used by 2
- 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_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 proof constructs a deterministic threshold coupling T(r, j) = [r < c(j)] for thresholds r ∈ {0, ..., N - 1}, where N is the total weight and c(j) is the marginal count of coordinate j. Because each coordinate count satisfies c(j) ≤ N, the threshold marginal sum min(N, c(j)) matches c(j) exactly. Pairwise joint counts are dominated because the threshold coupling achieves the maximum possible joint mass min(N, min(c(a), c(b))), which bounds the original joint sum. Finally, if coordinate a implies coordinate b on all support profiles, then c(a) ≤ c(b), ensuring that any threshold satisfied by a is also satisfied by b.
Each coordinate's weighted count c(j) is bounded by the total weight N.
We define the total weight N = ∑_{i ∈ S} w(i) and the coordinate marginal weight c(j) = ∑_{i ∈ S} w(i) * B(i, j). To establish c(j) ≤ N (named hbound), we apply sum_le_sum to compare terms pointwise: for each i ∈ S, the term w(i) * B(i, j) is at most w(i) because B(i, j) is either true (giving w(i) * 1 ≤ w(i)) or false (giving 0 ≤ w(i)).
uses
sum_le_sumdsimp only let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) have hbound (j : κ) : c j ≤ N := by apply sum_le_sum intro i hi cases B i j <;> simp
The joint weighted count of any pair of coordinates is bounded by each coordinate's marginal count.
For any coordinates a and b, the joint sum ∑_{i ∈ S} w(i) * (B(i, a) ∧ B(i, b)) is at most c(a) (named hpairL) and at most c(b) (named hpairR). Both bounds are proved via sum_le_sum by checking the pointwise inequality w(i) * (B(i, a) ∧ B(i, b)) ≤ w(i) * B(i, ·) through case analysis on the Boolean profile values.
uses
sum_le_sumhave hpairL (a b : κ) : S.sum (fun i => w i * (B i a && B i b).toNat) ≤ c a := by apply sum_le_sum intro i hi cases B i a <;> cases B i b <;> simp have hpairR (a b : κ) : S.sum (fun i => w i * (B i a && B i b).toNat) ≤ c b := by apply sum_le_sum intro i hi cases B i a <;> cases B i b <;> simp
The threshold coupling preserves each coordinate's marginal count: ∑_{r=0}^{N-1} T(r, j) = c(j).
For a given coordinate j, bool_threshold_marginal_sum rewrites the sum of indicators [r < c(j)] over r ∈ [0, N) as min(N, c(j)). Because c(j) ≤ N by hbound, min_eq_right evaluates this minimum directly to c(j).
uses
bool_threshold_marginal_sum,min_eq_rightconstructor · intro j rw [bool_threshold_marginal_sum] exact min_eq_right (hbound j)
The threshold coupling's joint count for any pair of coordinates dominates that of the original mixture.
By bool_threshold_pair_sum, the threshold coupling's pairwise sum over r ∈ [0, N) equals min(N, min(c(a), c(b))). Applying le_min reduces dominating this minimum to showing the original joint sum is at most N and at most min(c(a), c(b)). The first inequality follows by transitivity from hpairL and hbound (c(a) ≤ N), and the second follows by applying le_min to hpairL and hpairR.
uses
bool_threshold_pair_sum,le_minconstructor · intro a b rw [bool_threshold_pair_sum] apply le_min · exact (hpairL a b).trans (hbound a) · exact le_min (hpairL a b) (hpairR a b)
Any pointwise Boolean implication valid across all profiles in S is preserved by the threshold coupling for every threshold r.
Suppose B(i, a) = true implies B(i, b) = true for all i ∈ S, and let r be a threshold with T(r, a) = true. First, sum_le_sum establishes c(a) ≤ c(b): if B(i, a) is false then 0 ≤ w(i) * B(i, b), and if true then B(i, b) = true as well, giving identical terms. Simplifying the Boolean decisions with decide_eq_true_eq translates T(r, a) = true to r < c(a). Finally, lt_of_lt_of_le combines r < c(a) with c(a) ≤ c(b) to conclude r < c(b), which means T(r, b) = true.
uses
sum_le_sum,decide_eq_true_eq,lt_of_lt_of_le· intro a b hab r hr have hle : c a ≤ c b := by apply sum_le_sum intro i hi cases ha : B i a · simp [ha] · simp [ha, hab i hi ha] simp only [decide_eq_true_eq] at hr ⊢ exact lt_of_lt_of_le hr hle
sum_le_sum- A sum of pointwise smaller values over a finite set is less than or equal to the sum of the larger values.
bool_threshold_marginal_sum- The sum over r ∈ [0, N) of the Boolean indicator [r < c] equals min(N, c).
min_eq_right- If b ≤ a, then min(a, b) = b.
bool_threshold_pair_sum- The sum over r ∈ [0, N) of the joint indicator [r < a ∧ r < b] equals min(N, min(a, b)).
le_min- If c ≤ a and c ≤ b, then c ≤ min(a, b).
decide_eq_true_eq- The Boolean decision of a proposition p is true if and only if p holds.
lt_of_lt_of_le- In a preorder, if a < b and b ≤ c, then a < c.
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 bool_weighted_mixture_threshold_dominates {ι κ : Type*} (S : Finset ι) (w : ι → ℕ) (B : ι → κ → Bool) : 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) (∀ j, (range N).sum (fun r => (T r j).toNat) = c j) ∧ (∀ a b, S.sum (fun i => w i * (B i a && B i b).toNat) ≤ (range N).sum (fun r => (T r a && T r b).toNat)) ∧ (∀ a b, (∀ i ∈ S, B i a = true → B i b = true) → ∀ r, T r a = true → T r b = true) := by dsimp only let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) have hbound (j : κ) : c j ≤ N := by apply sum_le_sum intro i hi cases B i j <;> simp have hpairL (a b : κ) : S.sum (fun i => w i * (B i a && B i b).toNat) ≤ c a := by apply sum_le_sum intro i hi cases B i a <;> cases B i b <;> simp have hpairR (a b : κ) : S.sum (fun i => w i * (B i a && B i b).toNat) ≤ c b := by apply sum_le_sum intro i hi cases B i a <;> cases B i b <;> simp constructor · intro j rw [bool_threshold_marginal_sum] exact min_eq_right (hbound j) constructor · intro a b rw [bool_threshold_pair_sum] apply le_min · exact (hpairL a b).trans (hbound a) · exact le_min (hpairL a b) (hpairR a b) · intro a b hab r hr have hle : c a ≤ c b := by apply sum_le_sum intro i hi cases ha : B i a · simp [ha] · simp [ha, hab i hi ha] simp only [decide_eq_true_eq] at hr ⊢ exact lt_of_lt_of_le hr hle