Rosser–Schoenfeld's totient bound: finite range n<e294
ProvedTaoFivePrimes.rosser_schoenfeld_totient_smallby andreaskapfer · 1 vote · Sep 17, 2026 · Mathlib 0df444a (Lean v4.33.1)
additive-number-theorynumber-theoryprime-pairssieve-methodstao-five-primes
Let φ be Euler's totient function and γ the Euler–Mascheroni constant. For every integer n with 3≤n<e294,
φ(n)n<eγloglogn+loglogn2.50637.
This is the finite-range half of Theorem 15 of Rosser and Schoenfeld (1962), whose proof in §9 verifies the estimates numerically for 3≤n<expθ(313) by combining Lemma 14 with the Rosser–Walker prime tabulation: the generic bound n/φ(n)<eγloglogn+2loglogn5 (equation (3.41)) holds throughout this range with the single exception n=223092870=2⋅3⋅5⋅7⋅11⋅13⋅17⋅19⋅23, where the sharper constant 2.50637 is needed (equation (3.42)). Since 294<θ(313) and 5/2<2.50637, the verification yields the displayed uniform statement for all 3≤n<e294.
Together with the analytic range n≥e294 (handled by Lemma 15) this forms the complete proof of Theorem 15.
Formalization note: Nat.totient is Mathlib's totient function coerced to R, Real.eulerMascheroniConstant is γ, and Real.exp 294 is e294.
Preamble
import Mathlib.Data.Nat.Totient
import Mathlib.NumberTheory.Harmonic.EulerMascheroni
Formal statement
namespace TaoFivePrimes
theorem rosser_schoenfeld_totient_small (n : ℕ) (hn : 3 ≤ n)
(hfin : (n : ℝ) < Real.exp 294) :
(n : ℝ) / Nat.totient n <
Real.exp Real.eulerMascheroniConstant * Real.log (Real.log (n : ℝ)) +
2.50637 / Real.log (Real.log (n : ℝ)) := by sorry
end TaoFivePrimesSource
J.B. Rosser, L. Schoenfeld, *Approximate formulas for some functions of prime numbers*, Illinois Journal of Mathematics 6 (1962), 64–94, https://projecteuclid.org/journals/illinois-journal-of-mathematics/volume-6/issue-1/Approximate-formulas-for-some-functions-of-prime-numbers/10.1215/ijm/1255631807.full, Theorem 15, p. 72, eqs. (3.41)–(3.42); finite range: Lemma 14 and §9, pp. 88–89; analytic range: Lemma 15, Theorem 33, §8 eq. (3.29), Theorem 19 and (3.14); used in T. Tao, *Every odd number greater than 1 is the sum of at most five primes*, arXiv:1201.6656, proof of Proposition 4.10.
View graph