AFTD Auto-Formalizing Theoretical Domains

bool_threshold_marginal_sum

theoremverified

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.

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

    lines 7–8

      induction N with
      | zero => simp
  2. 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.

    lines 9–10

    uses sum_range_succ

      | succ N ih =>
        rw [sum_range_succ, ih]
  3. 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.

    lines 11–13

    uses decide_true, Bool.toNat_true, Nat.min_eq_left

        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)]
  4. 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.

    lines 14–15

    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

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