bool_weighted_mixture_threshold_implication_pair_eq
The common-threshold coupling preserves a pair mass exactly whenever selection of the first coordinate implies selection of the second in every original profile.
Statement
theorem bool_weighted_mixture_threshold_implication_pair_eq {ι κ : Type*} (S : Finset ι) (w : ι → ℕ) (B : ι → κ → Bool) (a b : κ) (hab : ∀ i ∈ S, B i a = true → B i b = true) : let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) (range N).sum (fun r => (decide (r < c a) && decide (r < c b)).toNat) = S.sum (fun i => w i * (B i a && B i b).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 1
- bool_threshold_pair_sumTwo Boolean threshold coordinates have joint membership sum equal to the minimum of the range length and both capacities.
The proof, explained
The common-threshold coupling sum $\sum_{r < N} \mathbf{1}_{r < c(a) \land r < c(b)}$ evaluates to $\min(N, \min(c(a), c(b)))$ by `bool_threshold_pair_sum`. Since coordinate $a$ implies coordinate $b$ in every profile ($B(i, a) \implies B(i, b)$), the profile-weighted count satisfies $c(a) \le c(b) \le N$, which simplifies the nested minimum directly to $c(a)$. Finally, the same pointwise implication means that $B(i, a) \land B(i, b) = B(i, a)$ for every profile, so $c(a)$ equals the weighted sum of the pair conjunction termwise.
$c(a) \le c(b)$, where $c(j) = \sum_{i \in S} w(i) \cdot (B(i, j))_{\mathbb{N}}$
We define $c(j)$ as the weighted total of profiles where coordinate $j$ is true. To establish $c(a) \le c(b)$, we apply `sum_le_sum` to compare the sums profile by profile. For each profile $i \in S$, if $B(i, a) = \text{false}$, the left term is $0$, which is at most $w(i) \cdot (B(i, b))_{\mathbb{N}}$. If $B(i, a) = \text{true}$, the implication hypothesis $hab$ ensures that $B(i, b) = \text{true}$ as well, so both terms equal $w(i) \cdot 1$.
uses
sum_le_sumdsimp only let c := fun j => S.sum (fun i => w i * (B i j).toNat) 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]
$c(a) \le \sum_{i \in S} w(i)$
We bound $c(a)$ from above by the total profile weight $N = \sum_{i \in S} w(i)$ via `sum_le_sum`. For each profile $i \in S$, since the indicator $(B(i, a))_{\mathbb{N}}$ is at most $1$, the term $w(i) \cdot (B(i, a))_{\mathbb{N}}$ is at most $w(i)$ whether $B(i, a)$ is true or false.
uses
sum_le_sumhave hbound : c a ≤ S.sum w := by apply sum_le_sum intro i hi cases B i a <;> simp
The threshold coupling sum $\sum_{r < N} \mathbf{1}_{r < c(a) \land r < c(b)}$ simplifies to $c(a)$
By `bool_threshold_pair_sum`, the left-hand sum simplifies to $\min(N, \min(c(a), c(b)))$. Since $c(a) \le c(b)$, `min_eq_left` reduces the inner minimum to $c(a)$. Then, since $c(a) \le N$, `min_eq_right` reduces $\min(N, c(a))$ to $c(a)$.
uses
bool_threshold_pair_sum,min_eq_left,min_eq_rightrw [bool_threshold_pair_sum] rw [min_eq_left hle, min_eq_right hbound]
$c(a) = \sum_{i \in S} w(i) \cdot (B(i, a) \land B(i, b))_{\mathbb{N}}$, completing the proof
Using `sum_congr`, we reduce the equality between $c(a) = \sum_{i \in S} w(i) \cdot (B(i, a))_{\mathbb{N}}$ and $\sum_{i \in S} w(i) \cdot (B(i, a) \land B(i, b))_{\mathbb{N}}$ to showing that their terms agree profile by profile. For any profile $i \in S$, if $B(i, a) = \text{false}$, both sides evaluate to $0$. If $B(i, a) = \text{true}$, then the hypothesis $hab$ gives $B(i, b) = \text{true}$, so the boolean conjunction $B(i, a) \land B(i, b)$ is true and both terms equal $w(i)$.
uses
sum_congrapply sum_congr rfl intro i hi cases ha : B i a · simp [ha] · simp [ha, hab i hi ha]
sum_le_sum- If $f(i) \le g(i)$ for all $i \in s$, then $\sum_{i \in s} f(i) \le \sum_{i \in s} g(i)$.
bool_threshold_pair_sum- For non-negative integers $N, a, b$, the sum of pair threshold indicators $\sum_{r < N} \mathbf{1}_{r < a \land r < b}$ equals $\min(N, \min(a, b))$.
min_eq_left- If $a \le b$, then $\min(a, b) = a$.
min_eq_right- If $b \le a$, then $\min(a, b) = b$.
sum_congr- Two sums are equal if their index sets are equal and their summands agree on every element of the index set.
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_implication_pair_eq {ι κ : Type*} (S : Finset ι) (w : ι → ℕ) (B : ι → κ → Bool) (a b : κ) (hab : ∀ i ∈ S, B i a = true → B i b = true) : let N := S.sum w let c := fun j => S.sum (fun i => w i * (B i j).toNat) (range N).sum (fun r => (decide (r < c a) && decide (r < c b)).toNat) = S.sum (fun i => w i * (B i a && B i b).toNat) := by dsimp only let c := fun j => S.sum (fun i => w i * (B i j).toNat) 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] have hbound : c a ≤ S.sum w := by apply sum_le_sum intro i hi cases B i a <;> simp rw [bool_threshold_pair_sum] rw [min_eq_left hle, min_eq_right hbound] apply sum_congr rfl intro i hi cases ha : B i a · simp [ha] · simp [ha, hab i hi ha]