exists_le_div_of_sum_le
If T ≥ 1 and a sequence of real numbers D_1, ..., D_T has sum at most C, then there exists an index r ∈ {1, ..., T} such that D_r ≤ C / T.
Statement
theorem exists_le_div_of_sum_le {T : ℕ} (hT : 0 < T) (D : ℕ → ℝ) (C : ℝ) (hD : ∑ t ∈ Finset.Icc 1 T, D t ≤ C) : ∃ r ∈ Finset.Icc 1 T, D r ≤ C / T- Source
- arXiv:2610.31489, Lemma 4.1
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For any positive natural number $T$, any function $D : \mathbb{N} \to \mathbb{R}$, and any real number $C$, if the sum $\sum_{t=1}^T D(t) \le C$ (summing over $t \in [1, T]$), then there exists a natural number $r \in [1, T]$ such that $D(r) \le C / T$.
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 proceeds by contradiction. If no term in $D_1, \dots, D_T$ were at most $C / T$, then every term would strictly exceed $C / T$. Summing this strict inequality over the nonempty index set $\{1, \dots, T\}$ would imply that the total sum strictly exceeds $T \cdot (C / T) = C$, which directly contradicts the hypothesis that the sum is at most $C$.
Assume for contradiction that $D_r > C / T$ for all $r \in \{1, \dots, T\}$.
We assume the negation of the existential statement and push the negation through the quantifier, obtaining the universal hypothesis that every term $D_r$ in the interval $\{1, \dots, T\}$ strictly exceeds the average $C / T$.
by_contra h push Not at h
The interval $\{1, \dots, T\}$ is nonempty.
Since $T > 0$, the integer $1$ satisfies $1 \le 1 \le T$, so $1 \in \{1, \dots, T\}$, providing an explicit witness that the index set is nonempty.
uses
Finset.mem_Icchave hnonempty : (Finset.Icc 1 T).Nonempty := ⟨1, by simp only [Finset.mem_Icc]; omega⟩
$\sum_{t=1}^T (C / T) < \sum_{t=1}^T D_t$.
Because the index set $\{1, \dots, T\}$ is nonempty and $C / T < D_t$ holds at every index by the contradiction assumption, the sum of $C / T$ over the interval is strictly less than the sum of the $D_t$ terms.
uses
Finset.sum_lt_sum_of_nonemptyhave hlt : ∑ t ∈ Finset.Icc 1 T, (C / T) < ∑ t ∈ Finset.Icc 1 T, D t := by apply Finset.sum_lt_sum_of_nonempty hnonempty intro i hi exact h i hi
$T \cdot (C / T) < \sum_{t=1}^T D_t$.
Summing the constant $C / T$ over $\{1, \dots, T\}$ equals the size of the set times $C / T$. The interval has size $T + 1 - 1 = T$, so substituting this gives $T \cdot (C / T) < \sum_{t=1}^T D_t$.
uses
Finset.sum_const,Nat.card_Icc,nsmul_eq_mulrw [Finset.sum_const, Nat.card_Icc, nsmul_eq_mul] at hlt have hcard : T + 1 - 1 = T := by omega rw [hcard] at hlt
$T \cdot (C / T) = C$.
Since $T > 0$ as a natural number, $T \neq 0$ in $\mathbb{R}$, which allows the factor $T$ to cancel with the denominator in $C / T$.
have hTne : (T : ℝ) ≠ 0 := by exact_mod_cast hT.ne' have hmul : (T : ℝ) * (C / T) = C := by field_simp
A contradiction is reached, completing the proof.
Combining $C = T \cdot (C / T) < \sum_{t=1}^T D_t$ with the hypothesis $\sum_{t=1}^T D_t \le C$ produces $C < C$, an impossible inequality. Linear real arithmetic closes the goal.
linarith
Finset.mem_Icc- An element belongs to the closed discrete interval $\{a, \dots, b\}$ if and only if $a \le x$ and $x \le b$.
Finset.sum_lt_sum_of_nonempty- If a finite set is nonempty and a function $f$ is strictly less than $g$ at every element, then the sum of $f$ over the set is strictly less than the sum of $g$.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set multiplied by that constant.
Nat.card_Icc- The cardinality of the closed interval of natural numbers $\{a, \dots, b\}$ is $b + 1 - a$.
nsmul_eq_mul- Multiplication of a ring element by a natural number (repeated addition) equals the product with the natural number cast into the ring.
- Formal bookkeeping is needed to convert between natural numbers and reals: the cardinality of $\{1, \dots, T\}$ appears initially as $T + 1 - 1$ before simplifying to $T$, and $T$ must be verified to be non-zero in $\mathbb{R}$ before simplifying $T \cdot (C / T) = 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
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.
/-- An average bound implies existence of an element bounded by the average. -/theorem exists_le_div_of_sum_le {T : ℕ} (hT : 0 < T) (D : ℕ → ℝ) (C : ℝ) (hD : ∑ t ∈ Finset.Icc 1 T, D t ≤ C) : ∃ r ∈ Finset.Icc 1 T, D r ≤ C / T := by by_contra h push Not at h have hnonempty : (Finset.Icc 1 T).Nonempty := ⟨1, by simp only [Finset.mem_Icc]; omega⟩ have hlt : ∑ t ∈ Finset.Icc 1 T, (C / T) < ∑ t ∈ Finset.Icc 1 T, D t := by apply Finset.sum_lt_sum_of_nonempty hnonempty intro i hi exact h i hi rw [Finset.sum_const, Nat.card_Icc, nsmul_eq_mul] at hlt have hcard : T + 1 - 1 = T := by omega rw [hcard] at hlt have hTne : (T : ℝ) ≠ 0 := by exact_mod_cast hT.ne' have hmul : (T : ℝ) * (C / T) = C := by field_simp linarith