Rosser–Schoenfeld's Lemma 14: the primorial bound for
ProvedTaoFivePrimes.rosser_schoenfeld_totient_lemma14additive-number-theorynumber-theoryprime-pairssieve-methodstao-five-primes
Let be positive integers, let be the primes, let be Euler's totient function, and let be the Chebyshev theta function. If
then
This is Lemma 14 of Rosser and Schoenfeld (1962), §9, p. 88, the elementary primorial bound underlying Theorem 15. Proof (as in the source): if are the distinct primes dividing , then , so ; moreover and the map is decreasing for , so . Since , the claim follows.
Formalization note: Chebyshev.theta is Mathlib's , and Nat.nth Nat.Prime m is the -st prime (zero-indexed), i.e. .
Preamble
import Mathlib.Data.Nat.Totient import Mathlib.Data.Nat.Nth import Mathlib.NumberTheory.Chebyshev
Formal statement
namespace TaoFivePrimes
theorem rosser_schoenfeld_totient_lemma14 (n m : ℕ) (hn : 1 ≤ n) (hm : 1 ≤ m)
(h : (n : ℝ) < Real.exp (Chebyshev.theta (Nat.nth Nat.Prime m))) :
(n : ℝ) / Nat.totient n ≤
∏ i ∈ Finset.range m,
(Nat.nth Nat.Prime i : ℝ) / ((Nat.nth Nat.Prime i : ℝ) - 1) := 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, §9, Lemma 14, p. 88, and pp. 88–89 for the Rosser–Walker verification; 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.