AFTD Auto-Formalizing Theoretical Domains

bool_threshold_pair_sum

theoremverified

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
Used by 2

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.

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

    lines 8–9

    uses lt_min_iff

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

    lines 10–11

    uses bool_threshold_marginal_sum

      simp_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

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