sum_range_sq_add_ge
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$.
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.
induction m with | zero => simp
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$.
uses
Finset.sum_range_succ| succ m ih => rw [Finset.sum_range_succ, ih] push_cast ringIt 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`.
uses
sum_range_sq_add_ge_eqrw [sum_range_sq_add_ge_eq]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.
uses
Nat.cast_nonneg,sq_nonneg,mul_nonneghave 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.
- In the inductive step of `sum_range_sq_add_ge_eq`, the verification of the polynomial identity in $m$ and $t$ is discharged automatically by the `ring` tactic after pushing casts.
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.
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