Rosser–Schoenfeld upper bound for
OpenIntMul.HvdH.rosser_schoenfeld_theta_upperinteger-multiplicationnumber-theory
Let be Chebyshev's function (sum over primes , natural logarithm). For every real ,
This is the upper half of Rosser–Schoenfeld's Theorem 4 (which states it on a wider range of ), restricted to the range in which Harvey–van der Hoeven quote it in the proof of their Lemma 5.1. Together with the matching lower bound it gives IntMul.HvdH.rosser_schoenfeld_thm4.
Formalization note: Chebyshev.theta is Mathlib's on ; since , and no junk values arise. The inequality is strict.
Preamble
import Mathlib
Formal statement
namespace IntMul.HvdH
theorem rosser_schoenfeld_theta_upper (y : ℝ) (hy : 563 ≤ y) :
Chebyshev.theta y < y + y / (2 * Real.log y) := by sorry
end IntMul.HvdHSource
J. B. Rosser, L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94, Theorem 4, p. 70 (upper bound for θ), https://doi.org/10.1215/ijm/1255631807; as quoted in D. Harvey, J. van der Hoeven, Integer multiplication in time O(n log n), Ann. of Math. 193 (2021), proof of Lemma 5.1, p. 38–39 ([39, Thm. 4]).