8
$\begingroup$

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}$

$\endgroup$
4
  • 6
    $\begingroup$ The bare statement of PNT is unlikely to be of any help. For a version of PNT to be useful, it is the remainder term that is crucial. $\endgroup$
    – André Nicolas
    Commented May 15, 2012 at 4:40
  • $\begingroup$ Is there some way (shorter than a proof of PNT) to reverse-engineer the term from the bare statement and thereby prove Bertrand's postulate? $\endgroup$
    – Dan Brumleve
    Commented May 15, 2012 at 4:44
  • $\begingroup$ @Dan: I doubt it. If the remainder term is allowed to be arbitrarily bad the "sufficiently large" can be arbitrarily high... the bare PNT is an asymptotic statement after all. $\endgroup$
    – Qiaochu Yuan
    Commented May 15, 2012 at 4:48
  • $\begingroup$ I'm totally willing to accept an answer to the effect that no such way is known. Another lead that I'm intending to investigate is Chebyshev's proof of Bertrand's postulate (Chebyshev's theorem really since he was the first to prove it). $\endgroup$
    – Dan Brumleve
    Commented May 15, 2012 at 5:29

1 Answer 1

Reset to default
8
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This looks like a much easier way to prove Bertrand's postulate from scratch, but how does it rely on PNT? $\endgroup$
    – Dan Brumleve
    Commented May 15, 2012 at 5:38
  • $\begingroup$ @Dan: Antonio isn't claiming that this uses PNT but rather that this uses ideas related to a proof of Chebyshev's theorem. $\endgroup$
    – Qiaochu Yuan
    Commented May 15, 2012 at 5:42
  • $\begingroup$ @Qiaochu, yes but I am specifically asking for a proof which is improved by the assumption of PNT (or else a believable statement that no such proof is known, or is impossible.) $\endgroup$
    – Dan Brumleve
    Commented May 15, 2012 at 5:47
  • 2
    $\begingroup$ @Dan, as Qiaochu said, it doesn't rely on the PNT. Chebyshev's theorem can be thought of as a "weak" PNT, since it gets the asymptotic order right but doesn't find the ideal constants for the big-$\Theta$. My only goal was to show that the proofs of Chebyshev's theorem and Bertrand's postulate here both grow from the same nut: estimating the central binomial coefficients. Hopefully you find this relevant, though I agree it doesn't directly answer your question. $\endgroup$
    – Antonio Vargas
    Commented May 15, 2012 at 5:50
  • $\begingroup$ Indeed it is very relevant. $\endgroup$
    – Dan Brumleve
    Commented May 15, 2012 at 6:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .