AFTD Auto-Formalizing Theoretical Domains

bool_weighted_mixture_threshold_implication_pair_eq

theoremverified

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.

  1. $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$.

    lines 12–19

    uses sum_le_sum

      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]
  2. $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.

    lines 20–23

    uses sum_le_sum

      have hbound : c a ≤ S.sum w := by
        apply sum_le_sum
        intro i hi
        cases B i a <;> simp
  3. 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)$.

    lines 24–25

    uses bool_threshold_pair_sum, min_eq_left, min_eq_right

      rw [bool_threshold_pair_sum]
      rw [min_eq_left hle, min_eq_right hbound]
  4. $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)$.

    lines 26–30

    uses sum_congr

      apply 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

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]
See it in the graphDiscuss this resultChallenge it