AFTD Auto-Formalizing Theoretical Domains

bool_weighted_mixture_threshold_dominates

theoremverified

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

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.

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

    lines 15–21

    uses sum_le_sum

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

    lines 22–29

    uses sum_le_sum

      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
  3. 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).

    lines 30–33

    uses bool_threshold_marginal_sum, min_eq_right

      constructor
      · intro j
        rw [bool_threshold_marginal_sum]
        exact min_eq_right (hbound j)
  4. 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.

    lines 34–39

    uses bool_threshold_pair_sum, le_min

      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)
  5. 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.

    lines 40–48

    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

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