AFTD Auto-Formalizing Theoretical Domains

exists_le_div_of_sum_le

theoremverified

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

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

    lines 3–4

      by_contra h
      push Not at h
  2. 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.

    line 5

    uses Finset.mem_Icc

      have hnonempty : (Finset.Icc 1 T).Nonempty := ⟨1, by simp only [Finset.mem_Icc]; omega⟩
  3. $\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.

    lines 6–9

    uses Finset.sum_lt_sum_of_nonempty

      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
  4. $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$.

    lines 10–12

    uses Finset.sum_const, Nat.card_Icc, nsmul_eq_mul

      rw [Finset.sum_const, Nat.card_Icc, nsmul_eq_mul] at hlt
      have hcard : T + 1 - 1 = T := by omega
      rw [hcard] at hlt
  5. $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$.

    lines 13–14

      have hTne : (T : ℝ) ≠ 0 := by exact_mod_cast hT.ne'
      have hmul : (T : ℝ) * (C / T) = C := by field_simp
  6. 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.

    line 15

      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.

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

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