AFTD Auto-Formalizing Theoretical Domains

sum_range_sq_add_ge

theoremverified

For any natural number m and any real number t, the sum of (t + k)^2 for k from 0 to m - 1 is at least (1/12) m (m^2 - 1).

Statement

theorem sum_range_sq_add_ge (m : ℕ) (t : ℝ) :
    (1 / 12 : ℝ) * (m : ℝ) * ((m : ℝ) ^ 2 - 1) ≤ ∑ k ∈ Finset.range m, (t + (k : ℝ)) ^ 2
Source
arXiv:2611.04644, Lemma A.4 proof step 2
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • isotropic_intersection_size_boundLet A ⊂ ℝ^d be a finite, non-empty set in isotropic position (so that ∑_{a ∈ A} a = 0 and ∑_{a ∈ A} (a · u)^2 = |A| ‖u‖^2 for all u ∈…

Read back from the Lean

For all natural numbers $m$ and all real numbers $t$, $$\frac{1}{12} m (m^2 - 1) \le \sum_{k=0}^{m-1} (t + k)^2$$ (where the sum is over $k \in \{0, \dots, m-1\}$, which is $0$ if $m = 0$).

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 first establishes an exact algebraic identity by induction on $m$: the sum $\sum_{k=0}^{m-1} (t+k)^2$ equals $m\left(t + \frac{m-1}{2}\right)^2 + \frac{1}{12}m(m^2-1)$. Because $m \ge 0$ and any real square is non-negative, the leading term $m\left(t + \frac{m-1}{2}\right)^2$ is non-negative. Dropping this non-negative term yields the minimum value $\frac{1}{12}m(m^2-1)$, achieved at $t = -(m-1)/2$.

  1. For the base case $m = 0$, both sides of the identity in `sum_range_sq_add_ge_eq` are equal to $0$.

    We proceed by induction on $m$. When $m = 0$, the sum on the left-hand side is over the empty range and evaluates to $0$, and substituting $m = 0$ into the right-hand side also gives $0$, which `simp` verifies.

    lines 4–5

      induction m with
      | zero => simp
  2. Assuming the identity holds for $m$, it holds for $m + 1$.

    In the inductive step, `Finset.sum_range_succ` separates the final term $(t + m)^2$ from the sum up to $m + 1$. Substituting the induction hypothesis for the sum up to $m$, casting integers to real numbers via `push_cast`, and simplifying polynomials with `ring` establishes the identity for $m + 1$.

    lines 6–9

    uses Finset.sum_range_succ

      | succ m ih =>
        rw [Finset.sum_range_succ, ih]
        push_cast
        ring
  3. It suffices to show that $\frac{1}{12}m(m^2 - 1) \le m\left(t + \frac{m-1}{2}\right)^2 + \frac{1}{12}m(m^2 - 1)$.

    We rewrite the sum on the right-hand side of the inequality using the exact identity `sum_range_sq_add_ge_eq`.

    line 14

    uses sum_range_sq_add_ge_eq

      rw [sum_range_sq_add_ge_eq]
  4. The quadratic term $m\left(t + \frac{m-1}{2}\right)^2$ is non-negative, which completes the proof.

    Since $m \ge 0$ (by `Nat.cast_nonneg`) and any real square is non-negative (by `sq_nonneg`), their product $m\left(t + \frac{m-1}{2}\right)^2$ is non-negative by `mul_nonneg`. Linear arithmetic (`linarith`) then immediately deduces the desired lower bound.

    lines 15–18

    uses Nat.cast_nonneg, sq_nonneg, mul_nonneg

      have h1 : 0 ≤ (m : ℝ) := Nat.cast_nonneg m
      have h2 : 0 ≤ (t + ((m : ℝ) - 1) / 2) ^ 2 := sq_nonneg _
      have h3 : 0 ≤ (m : ℝ) * (t + ((m : ℝ) - 1) / 2) ^ 2 := mul_nonneg h1 h2
      linarith
Finset.sum_range_succ
Splits a sum over $\{0, \dots, n\}$ into the sum over $\{0, \dots, n - 1\}$ plus the final term at $n$.
sum_range_sq_add_ge_eq
For any natural number $m$ and real number $t$, the sum $\sum_{k=0}^{m-1} (t + k)^2$ equals $m(t + (m-1)/2)^2 + \frac{1}{12}m(m^2-1)$.
Nat.cast_nonneg
The canonical embedding of any natural number into an ordered semiring is non-negative.
sq_nonneg
The square of any element in a linearly ordered semiring is non-negative.
mul_nonneg
The product of two non-negative elements is non-negative.

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

lemma sum_range_sq_add_ge_eq (m : ℕ) (t : ℝ) :    ∑ k ∈ Finset.range m, (t + (k : ℝ)) ^ 2 =    (m : ℝ) * (t + ((m : ℝ) - 1) / 2) ^ 2 + (1 / 12 : ℝ) * (m : ℝ) * ((m : ℝ) ^ 2 - 1) := by  induction m with  | zero => simp  | succ m ih =>    rw [Finset.sum_range_succ, ih]    push_cast    ring/-- The sum of squared deviations along an arithmetic progression of length m is minimized at -(m-1)/2 with value (1/12) m (m^2 - 1). -/theorem sum_range_sq_add_ge (m : ℕ) (t : ℝ) :    (1 / 12 : ℝ) * (m : ℝ) * ((m : ℝ) ^ 2 - 1) ≤ ∑ k ∈ Finset.range m, (t + (k : ℝ)) ^ 2 := by  rw [sum_range_sq_add_ge_eq]  have h1 : 0 ≤ (m : ℝ) := Nat.cast_nonneg m  have h2 : 0 ≤ (t + ((m : ℝ) - 1) / 2) ^ 2 := sq_nonneg _  have h3 : 0 ≤ (m : ℝ) * (t + ((m : ℝ) - 1) / 2) ^ 2 := mul_nonneg h1 h2  linarith
See it in the graphDiscuss this resultChallenge it