bool_threshold_pair_sum
Two Boolean threshold coordinates have joint membership sum equal to the minimum of the range length and both capacities.
Statement
theorem bool_threshold_pair_sum (N a b : ℕ) : (range N).sum (fun r => (decide (r < a) && decide (r < b)).toNat) = min N (min a b)
- 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_marginal_sumA finite threshold membership sum equals the smaller of its range length and its capacity.
- Used by 2
- bool_weighted_mixture_threshold_implication_pair_eqThe common-threshold coupling preserves a pair mass exactly whenever selection of the first coordinate implies selection of the second in…
- 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…
The proof, explained
The proof establishes that a number r satisfies r < a and r < b simultaneously if and only if r < min a b, so the conjunction of the two Boolean threshold indicators is equivalent to the single indicator for r < min a b. Rewriting the summand using this identity reduces the joint sum to the marginal threshold sum for min a b. The theorem then follows immediately by applying bool_threshold_marginal_sum.
For any natural number r, the Boolean conjunction (decide (r < a) && decide (r < b)) equals decide (r < min a b).
We establish the helper identity hb by case analysis on whether r < a and whether r < b. In all four cases, simplification with lt_min_iff verifies that the conjunction of the two threshold conditions is identical to the condition r < min a b.
uses
lt_min_iffhave hb (r : ℕ) : (decide (r < a) && decide (r < b)) = decide (r < min a b) := by by_cases ha : r < a <;> by_cases hb : r < b <;> simp [ha, hb, lt_min_iff]
The joint threshold sum equals min N (min a b).
Rewriting the summand using hb transforms the joint sum into the single-threshold sum ∑ r ∈ range N, (decide (r < min a b)).toNat. Applying bool_threshold_marginal_sum with threshold min a b then evaluates this sum directly to min N (min a b).
uses
bool_threshold_marginal_sumsimp_rw [hb] exact bool_threshold_marginal_sum N (min a b)
lt_min_iff- An element is strictly less than the minimum of two elements if and only if it is strictly less than both: a < min b c ↔ a < b ∧ a < c.
bool_threshold_marginal_sum- The sum of the Boolean threshold indicator (decide (r < c)).toNat over r in {0, ..., N - 1} equals min N 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_threshold_pair_sum (N a b : ℕ) : (range N).sum (fun r => (decide (r < a) && decide (r < b)).toNat) = min N (min a b) := by have hb (r : ℕ) : (decide (r < a) && decide (r < b)) = decide (r < min a b) := by by_cases ha : r < a <;> by_cases hb : r < b <;> simp [ha, hb, lt_min_iff] simp_rw [hb] exact bool_threshold_marginal_sum N (min a b)