AFTD Auto-Formalizing Theoretical Domains

sum_ballot_weight_min_eq

theoremverified

For natural numbers $d$ and $j$ with $1 \le d$ and $j \le d$, the sum $\sum_{s \in \text{range}(\min(d-j, d-1) + 1)} \text{ballot\_weight}(2d - 1, s)$ equals $\binom{2d-1}{d-j}$.

Statement

theorem sum_ballot_weight_min_eq (d j : ℕ) (hd : 1 ≤ d) (hj : j ≤ d) :
    ∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), ballot_weight (2 * d - 1) s =
      (2 * d - 1).choose (d - j)
Source
arXiv:2611.06860 "Largest Sperner families with bounded VC-dimension", Lemma 2.5
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • ballot_weightThe function ballot_weight taking two natural numbers $p$ and $k$ and returning the natural number defined as: if $k = 0$ then…
  • sum_ballot_weight_eqFor natural numbers $d$ and $a$ with $a \le d - 1$, the sum $\sum_{s \in \text{range}(a + 1)} \text{ballot\_weight}(2d - 1, s)$ equals…
Used by 1

Read back from the Lean

For all natural numbers $d$ and $j$, if $1 \le d$ and $j \le d$, then the sum of ballot_weight (2 * d - 1) s over $s \in \{0, \dots, \min(d - j, d - 1)\}$ is equal to $\binom{2d - 1}{d - j}$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof splits into cases based on whether $j = 0$ or $j > 0$. When $j > 0$, the minimum $\min(d - j, d - 1)$ is simply $d - j$, and the summation identity `sum_ballot_weight_eq` directly evaluates the sum to $\binom{2d - 1}{d - j}$. When $j = 0$, the minimum is $d - 1$, evaluating the sum to $\binom{2d - 1}{d - 1}$, which matches the goal $\binom{2d - 1}{d}$ by the symmetry of binomial coefficients.

  1. We split the proof into two cases: $j = 0$ and $j > 0$.

    Using `Nat.eq_zero_or_pos`, any natural number $j$ is either zero or strictly positive.

    line 5

    uses Nat.eq_zero_or_pos

      rcases Nat.eq_zero_or_pos j with rfl | hjpos
  2. When $j = 0$, the sum simplifies to $\binom{2d - 1}{d - 1}$.

    Since $d \ge 1$, we have $d - 1 < d - 0 = d$, so $\min(d - 0, d - 1) = d - 1$. Replacing the upper limit by $d - 1$ and applying `sum_ballot_weight_eq` with $a = d - 1$ (noting $d - 1 \le d - 1$ by `le_rfl`) evaluates the sum to $\binom{2d - 1}{d - 1}$.

    lines 6–7

    uses sum_ballot_weight_eq, le_rfl

      · have hmin : min (d - 0) (d - 1) = d - 1 := by omega
        rw [hmin, sum_ballot_weight_eq d (d - 1) le_rfl]
  3. $\binom{2d - 1}{d - 1} = \binom{2d - 1}{d - 0}$, completing the $j = 0$ case.

    Because $d \ge 1$, we have $d \le 2d - 1$. The symmetry identity for binomial coefficients (`Nat.choose_symm`) gives $\binom{2d - 1}{(2d - 1) - d} = \binom{2d - 1}{d}$. Since $(2d - 1) - d = d - 1$ and $d - 0 = d$ by `Nat.sub_zero`, this shows that the left-hand value $\binom{2d - 1}{d - 1}$ equals the target $\binom{2d - 1}{d - 0}$.

    lines 8–11

    uses Nat.choose_symm, Nat.sub_zero

        have hsymm := Nat.choose_symm (by omega : d ≤ 2 * d - 1)
        have : 2 * d - 1 - d = d - 1 := by omega
        rw [this] at hsymm
        rw [Nat.sub_zero, ← hsymm]
  4. When $j > 0$, the sum evaluates directly to $\binom{2d - 1}{d - j}$.

    Because $j \ge 1$, we have $d - j \le d - 1$, which makes $\min(d - j, d - 1) = d - j$. Rewriting the minimum to $d - j$ and applying the summation identity `sum_ballot_weight_eq` for $a = d - j$ yields the right-hand side $\binom{2d - 1}{d - j}$.

    lines 12–13

    uses sum_ballot_weight_eq

      · have hmin : min (d - j) (d - 1) = d - j := by omega
        rw [hmin, sum_ballot_weight_eq d (d - j) (by omega)]
Nat.eq_zero_or_pos
A natural number is either 0 or strictly positive: $n = 0 \lor n > 0$.
sum_ballot_weight_eq
For $a \le d - 1$, the sum of ballot weights $\sum_{s=0}^a \text{ballot\_weight}(2d - 1, s)$ equals $\binom{2d - 1}{a}$.
le_rfl
Reflexivity of $\le$: $a \le a$ for any element in a preorder.
Nat.choose_symm
Symmetry of binomial coefficients: if $k \le n$, then $\binom{n}{n - k} = \binom{n}{k}$.
Nat.sub_zero
Subtracting zero from a natural number leaves it unchanged: $n - 0 = n$.

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

/-- Sum of ballot weights up to min(d - j, d - 1) equals (2d - 1).choose (d - j). -/theorem sum_ballot_weight_min_eq (d j : ℕ) (hd : 1 ≤ d) (hj : j ≤ d) :    ∑ s ∈ Finset.range (min (d - j) (d - 1) + 1), ballot_weight (2 * d - 1) s =      (2 * d - 1).choose (d - j) := by  rcases Nat.eq_zero_or_pos j with rfl | hjpos  · have hmin : min (d - 0) (d - 1) = d - 1 := by omega    rw [hmin, sum_ballot_weight_eq d (d - 1) le_rfl]    have hsymm := Nat.choose_symm (by omega : d ≤ 2 * d - 1)    have : 2 * d - 1 - d = d - 1 := by omega    rw [this] at hsymm    rw [Nat.sub_zero, ← hsymm]  · have hmin : min (d - j) (d - 1) = d - j := by omega    rw [hmin, sum_ballot_weight_eq d (d - j) (by omega)]
See it in the graphDiscuss this resultChallenge it