bool_threshold_marginal_sum
A finite threshold membership sum equals the smaller of its range length and its capacity.
Statement
theorem bool_threshold_marginal_sum (N c : ℕ) : (range N).sum (fun r => (decide (r < c)).toNat) = min N c
- 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- Used by 2
- bool_threshold_pair_sumTwo Boolean threshold coordinates have joint membership sum equal to the minimum of the range length and both capacities.
- 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 identity is proved by induction on N. In the base case N = 0, the sum is empty and both sides equal 0. In the inductive step, splitting off the term at index N and invoking the induction hypothesis reduces the claim to min N c + [N < c] = min (N + 1) c. A case analysis on whether N < c then shows that both sides increase by 1 when N < c, and both sides stay equal to c when N ≥ c.
The identity holds in the base case N = 0.
We proceed by induction on N. When N = 0, the sum is taken over the empty range, which evaluates to 0, and min 0 c = 0. Simplification directly closes the goal.
induction N with | zero => simp
In the inductive step for N + 1, the goal reduces to showing min N c + (decide (N < c)).toNat = min (N + 1) c.
For the successor step, sum_range_succ splits the sum over range (N + 1) into the sum over range N plus the boundary term at index N. Rewriting with the induction hypothesis ih replaces the sum over range N with min N c.
uses
sum_range_succ| succ N ih => rw [sum_range_succ, ih]The identity holds in the case where N < c.
We divide into cases on whether N < c. When N < c, the decision is true by decide_true, which converts to 1 by Bool.toNat_true. Since N < c implies both N ≤ c and N + 1 ≤ c, rewriting with Nat.min_eq_left (justified by linear arithmetic via omega) simplifies both min N c + 1 and min (N + 1) c to N + 1.
uses
decide_true,Bool.toNat_true,Nat.min_eq_leftby_cases h : N < c · simp only [h, decide_true, Bool.toNat_true] rw [Nat.min_eq_left (by omega), Nat.min_eq_left (by omega)]
The identity holds in the case where N ≥ c, completing the induction.
When ¬(N < c), the decision evaluates to false by decide_false, which converts to 0 by Bool.toNat_false, and adding zero leaves min N c by add_zero. Since c ≤ N and c ≤ N + 1, rewriting with Nat.min_eq_right on both sides (again justified by omega) reduces both min N c and min (N + 1) c to c.
uses
decide_false,Bool.toNat_false,add_zero,Nat.min_eq_right· simp only [h, decide_false, Bool.toNat_false, add_zero] rw [Nat.min_eq_right (by omega), Nat.min_eq_right (by omega)]
sum_range_succ- The sum of a sequence over the range 0 to n equals the sum over 0 to n - 1 plus the nth term.
decide_true- The boolean decision of a true proposition is true.
Bool.toNat_true- The natural number value of the boolean true is 1.
Nat.min_eq_left- If a ≤ b, then min a b = a.
decide_false- The boolean decision of a false proposition is false.
Bool.toNat_false- The natural number value of the boolean false is 0.
add_zero- Adding zero to any element leaves it unchanged (a + 0 = a).
Nat.min_eq_right- If b ≤ a, then min a b = b.
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_marginal_sum (N c : ℕ) : (range N).sum (fun r => (decide (r < c)).toNat) = min N c := by induction N with | zero => simp | succ N ih => rw [sum_range_succ, ih] by_cases h : N < c · simp only [h, decide_true, Bool.toNat_true] rw [Nat.min_eq_left (by omega), Nat.min_eq_left (by omega)] · simp only [h, decide_false, Bool.toNat_false, add_zero] rw [Nat.min_eq_right (by omega), Nat.min_eq_right (by omega)]