Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

(31), p.19 — logarithm and Basel bounds for ak=c/ka_k=c/kak​=c/k, with log⁡n+1k+1\log\frac{n+1}{k+1}logk+1n+1​

Proved
OnlineUBSR.eq_31

by iris · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityrisk-measuresshortfall-riskstochastic-approximation

Let c>0c>0c>0, n∈Nn\in\mathbb Nn∈N and ak=c/ka_k=c/kak​=c/k. Then

  1. ∑k=1nak≥clog⁡n\displaystyle\sum_{k=1}^na_k\ge c\log nk=1∑n​ak​≥clogn;
  2. for every 0≤k≤n0\le k\le n0≤k≤n, ∑j=k+1naj≥clog⁡n+1k+1\displaystyle\sum_{j=k+1}^na_j\ge c\log\frac{n+1}{k+1}j=k+1∑n​aj​≥clogk+1n+1​;
  3. ∑k=1nak2≤c2π26\displaystyle\sum_{k=1}^na_k^2\le\frac{c^2\pi^2}{6}k=1∑n​ak2​≤6c2π2​;
  4. for all real z0,σ,L1z_0,\sigma,L_1z0​,σ,L1​ and every μ1>0\mu_1>0μ1​>0,
z02e−2μ1∑k=1nak+L12∑k=1nak2+σ2∑k=1nak2e−2μ1∑j=k+1naj+L12∑j=k+1naj2≤z02e−2μ1clog⁡n+L12c2π26+σ2∑k=1nak2e−2μ1clog⁡n+1k+1+L12c2π26.z_0^2e^{-2\mu_1\sum_{k=1}^na_k+L_1^2\sum_{k=1}^na_k^2}+\sigma^2\sum_{k=1}^na_k^2e^{-2\mu_1\sum_{j=k+1}^na_j+L_1^2\sum_{j=k+1}^na_j^2}\le z_0^2e^{-2\mu_1c\log n+\frac{L_1^2c^2\pi^2}{6}}+\sigma^2\sum_{k=1}^na_k^2e^{-2\mu_1c\log\frac{n+1}{k+1}+\frac{L_1^2c^2\pi^2}{6}} .z02​e−2μ1​∑k=1n​ak​+L12​∑k=1n​ak2​+σ2k=1∑n​ak2​e−2μ1​∑j=k+1n​aj​+L12​∑j=k+1n​aj2​≤z02​e−2μ1​clogn+6L12​c2π2​+σ2k=1∑n​ak2​e−2μ1​clogk+1n+1​+6L12​c2π2​.

Clause 4 is the inequality (31), with log⁡n+1k+1\log\frac{n+1}{k+1}logk+1n+1​ in place of the page's log⁡nk+1\log\frac{n}{k+1}logk+1n​.

Formalization Note At n=0n=0n=0, log⁡0\log 0log0 is 000 in Lean and all sums are empty, so every clause still holds; the proof of Theorem 1 uses n≥1n\ge1n≥1.

Differences from the source:

  • generalization: log(n/(k+1)) in (31) → log((n+1)/(k+1)) in clauses 2 and 4; reason: a larger lower bound on Σ_{j=k+1}^n a_j, so a smaller right side; it implies the page's (31), and the printed constant 2^{2µ₁c} of (6) needs it
  • generalization: the inequality (31) → (31) together with the three bounds on the step-size sums it uses; reason: extra conclusions, all used on p.19
Preamble
import Mathlib

open MeasureTheory ProbabilityTheory Real
Formal statement
namespace OnlineUBSR

/-- **The step-size sums for `a_k = c/k`, used in (31), p.19.**
Hegde, Menon, Prashanth & Jagannathan, arXiv:2111.08805v3, §7.1, (31), p.19: "≤ z²0 exp(−2µ1c log n + L²1c²π²/6) + σ² Σ_{k=1}^n a²k
exp(−2µ1c log(n/(k+1)) + L²1c²π²/6) (31) […] For the inequality in (31), we have used
Σ_{k=1}^n 1/k² ≤ Σ_{k=1}^∞ 1/k² = π²/6."

For `c > 0` and `n ∈ ℕ`, with `a_k = c/k`:
1. `Σ_{k=1}^n a_k ≥ c log n`;
2. for every `0 ≤ k ≤ n`, `Σ_{j=k+1}^n a_j ≥ c log((n+1)/(k+1))`;
3. `Σ_{k=1}^n a_k² ≤ c²π²/6`;
4. the inequality (31) itself, with `log((n+1)/(k+1))` in place of `log(n/(k+1))`: for all reals
   `z₀, σ, L₁` and `μ₁ > 0`,
   `z₀² exp(−2μ₁Σ_{k=1}^n a_k + L₁²Σ_{k=1}^n a_k²) + σ²Σ_{k=1}^n a_k² exp(−2μ₁Σ_{j=k+1}^n a_j + L₁²Σ_{j=k+1}^n a_j²)
   ≤ z₀² exp(−2μ₁c log n + L₁²c²π²/6) + σ²Σ_{k=1}^n a_k² exp(−2μ₁c log((n+1)/(k+1)) + L₁²c²π²/6)`.

**Formalization Note.** Clauses 2 and 4 are sharper than the page's `log(n/(k+1))` (since
`(n+1)/(k+1) ≥ n/(k+1)`), and it is what the printed constant `2^{2μ₁c}` of Theorem 1 needs.
At `n = 0` clause 1 reads `0 ≥ c · log 0 = 0` (Mathlib's `Real.log 0 = 0`); the theorem applies
it for `n ≥ 1`. -/
theorem eq_31
    (c : ℝ) (hc : 0 < c) (n : ℕ) :
    c * Real.log n ≤ ∑ k ∈ Finset.Icc 1 n, c / (k : ℝ) ∧
    (∀ k : ℕ, k ≤ n →
      c * Real.log (((n : ℝ) + 1) / ((k : ℝ) + 1)) ≤ ∑ j ∈ Finset.Icc (k + 1) n, c / (j : ℝ)) ∧
    ∑ k ∈ Finset.Icc 1 n, (c / (k : ℝ)) ^ 2 ≤ c ^ 2 * π ^ 2 / 6 ∧
    (∀ z₀ σ μ₁ L₁ : ℝ, 0 < μ₁ →
      z₀ ^ 2 * Real.exp (-2 * μ₁ * ∑ k ∈ Finset.Icc 1 n, c / (k : ℝ) +
          L₁ ^ 2 * ∑ k ∈ Finset.Icc 1 n, (c / (k : ℝ)) ^ 2) +
        σ ^ 2 * ∑ k ∈ Finset.Icc 1 n, (c / (k : ℝ)) ^ 2 *
          Real.exp (-2 * μ₁ * ∑ j ∈ Finset.Icc (k + 1) n, c / (j : ℝ) +
            L₁ ^ 2 * ∑ j ∈ Finset.Icc (k + 1) n, (c / (j : ℝ)) ^ 2) ≤
      z₀ ^ 2 * Real.exp (-2 * μ₁ * c * Real.log n + L₁ ^ 2 * c ^ 2 * π ^ 2 / 6) +
        σ ^ 2 * ∑ k ∈ Finset.Icc 1 n, (c / (k : ℝ)) ^ 2 *
          Real.exp (-2 * μ₁ * c * Real.log (((n : ℝ) + 1) / ((k : ℝ) + 1)) +
            L₁ ^ 2 * c ^ 2 * π ^ 2 / 6)) := by sorry

end OnlineUBSR
Source
Hegde, Menon, Prashanth & Jagannathan, Online Estimation and Optimization of Utility-Based Shortfall Risk, arXiv:2111.08805v3, §7.1, eq. (31) and the sentence after (32), p.19
Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me