[Math] simple way to prove Bertrand’s postulate from the prime number theorem

analytic-number-theoryprime numbers

Is there a simple way to prove Bertrand's postulate from the prime number theorem?

The prime number theorem immediately implies Bertrand's postulate for sufficiently large $n$, but it fails to establish a base case (the linked proof on Wikipedia explicitly gives the base case $n \ge 468$). In the other direction, Bertrand's postulate yields $\pi(n) \ge \log_2(n)$ which seemingly adds little beyond Euclid's theorem to any proof of PNT. Is the prime number theorem really "stronger" than Bertrand's postulate, in the sense that assuming the former can simplify a proof of the latter? What lemmas are needed in addition to PNT for a more concise proof of Bertrand's postulate?

EDIT: I am specifically referring to this version of PNT:

$\pi(x) \sim \frac{x}{\log x}$

Best Answer

I'm not sure if it's what you're looking for, but the proof of Bertrand's postulate is somewhat related to the proof of Chebyshev's theorem, which says that $\pi(x) = \Theta(x/\log x)$; both proofs rely on careful estimation of the central binomial coefficients $\binom{2n}{n}$.

To prove Chebyshev's theorem, one can start by finding the estimate

$$ \frac{2^{2n}}{2n+1} < \binom{2n}{n} < 2^{2n}, \tag{1} $$

then using it to conclude that $\vartheta(x)/x < 4\log 2$ and hence

$$ \limsup_{x \to \infty} \frac{\pi(x)}{x/\log x} = \limsup_{x \to \infty} \frac{\vartheta(x)}{x} \leq 4 \log 2, $$

and $\psi(x)/x > (x-2)\log 2/x - \log(x+1)/x$ and hence

$$ \liminf_{x \to \infty} \frac{\pi(x)}{x/\log x} = \liminf_{x \to \infty} \frac{\psi(x)}{x} \geq \log 2, $$

where $\vartheta$ and $\psi$ are Chebyshev's functions.

To prove Bertrand's postulate, one can improve the estimate in $(1)$ to

$$ \frac{2^{2n}}{2\sqrt{n}} < \binom{2n}{n} < \frac{2^{2n}}{\sqrt{2 n}}, \tag{2} $$

which can be used to show that

$$ \vartheta(2n) - \vartheta(n) > \left(\frac{2n}{3}-1\right)\log 2-\left(\frac{\sqrt{2n}+1}{2}\right)\log 2 > 0$$

for $n \geq 2^6$. This is exactly Bertrand's postulate for $n \geq 2^6$. The remaining cases are checked by hand.

My reference for these proofs is Chandrasekharan's Introduction to Analytic Number Theory.

Related Question