I was just wondering why can't we use prime number's theorem to prove Bertrand's postulate.
We know that if we show that for all natural numbers $n>2, \pi(2n)-\pi(n)>0$ we are done.
Why can't it be proven by just showing (By using the prime number's theorem) that for every natural numbers $n>2, \frac{2n}{ln(2n)}-\frac{n}{ln(n)}>0$?

  • 3
    $\begingroup$ $\pi (n)$ is not exactly equal to $n/\ln n$, they are approximately equal. $\endgroup$
    – pritam
    May 23 '13 at 15:33
  • $\begingroup$ Is this a duplicate of this question? $\endgroup$
    – robjohn
    Jun 5 '13 at 19:13

As per user60930's answer, we have via the prime number theorem that for any $\epsilon >0 $ however small there is some $x_0$ such that for $x > x_0$ there is always a prime between x and $x(1+\epsilon).$ By letting $\epsilon = 1/k$ we get any number of impressive results (k=1 is Bertrand's postulate.) The only issue, and a very thorny one, is how big to make $x_0$ so that all subsequent intervals contain at least one prime.

Here we either have to be quite ingenious (like Chebyshev-Erdos-Ramanujan or, say, Nagura) or we have to invoke results that come from more advanced methods. To prove Bertrand's theorem even using somewhat dated (1941) results like Rosser's, valid for $x > 55$ --

$$\frac{x}{\ln x +2}< \pi(x) < \frac{x}{\ln x - 4}$$

--we are really shooting fish in a barrel.

The intervals $$(\frac{x}{\ln x +2},\frac{x}{\ln x -4})$$ and $$(\frac{2x}{\ln 2x + 2},\frac{2x}{\ln 2x - 4})$$ are mutually exclusive beyond about $ x = 44052.9$ if I have calculated correctly.

In other words, $\pi(2x)$ is trapped on an interval that is numerically higher than the interval in which $\pi(x)$ is trapped. The difference is therefore positive and so we have proven Bertrand using the PNT in the first instance but in particular an understanding of the error of the PNT acquired using more advanced methods.

Could we prove Bertrand's theorem using the PNT alone? The problem is that the PNT is an asymptotic result which does not in itself furnish any idea of its error on shorter intervals (but see last edit below). We need an ancillary indication (like Rosser) of how big numbers must be for the result to consistently obtain.

Edit: it seems worth mentioning for comparison that Pierre Dusart's (1999) result,

$$\frac{x}{\ln x}(1+\frac{0.992}{\ln x}) < \pi(x) < \frac{x}{\ln x}(1+\frac{1.2762}{\ln x})$$

is an amazing improvement and is valid for $x\geq 599.$ Rosser used about 3.5 million zeros of the zeta function to derive his estimates, while Dusart uses work of Brent showing that 1,500,000,001 zeros lie on the critical line. Not sure what to make of that last zero but Mathematica says 1,500,000,001 is prime.

Further edit: This question and answer to the same effect: no one has used the PNT (alone) to prove Bertrand's postulate.

The first two proofs of the PNT (de la Vallee Poussin, Hadamard, ca. 1896) were done by showing that zeros of the zeta function cannot lie on the line Re(s) = 1. De la Vallee Poussin's form for the relative error of the PNT came in a separate proof in 1899. So if we want to find an $x_0$ large enough to use the PNT to establish Bertrand's postulate, even for early versions of the PNT we are relying on separate theorems about the error.

It is interesting that Selberg's 'elementary' proof of the PNT, which avoids complex function theory, extends methods used by Chebyshev in proving Bertrand's postulate (1850) and later by Nagura in sharpening Bertrand to $(x,(1+1/5)x).$ We often read that the prime number theorem is "deeper" than Bertrand's postulate but the connection between Chebyshev's identity

$T(x) = \psi(x) + \psi(x/2)+\psi(x/3)+\psi(x/4)...$

used in his proof of Bertrand's postulate, and the version of the prime number theorem proved by Selberg in 1948, a connection described in detail by Edwards in Riemann's Zeta Function at 281-297, suggests that the assertion should be weighed carefully.


The reason is Prime number theorem is much deeper than Bertrand's postulate. Once you have proven PNT, you can do away with Bertrand's postulate and prove much stronger versions of it.

  1. For every integer $k$, there exists a natural number $n_k$ which depends only on $k$ such that for all $n \ge n_k$ there is always at least one prime between $kn$ and $(k+1)n$.

  2. For for every small $\epsilon$, $0 < \epsilon \le 1$, there exists an inter $n_{\epsilon}$ which depends only on $\epsilon$ such that for all $n \ge n_{\epsilon}$, there is always a prime between $n$ and $(1+\epsilon)n$.


There are three main reasons why it's usually not proved like you proposed:

  • It has been proved a few decades earlier than the prime number theorem.
  • Proving PNT is considerably harder than proving the postulate directly.
  • PNT talks about the asymptotic behaviour of $\pi(n)$ and might not reflect the reality for small numbers. Of course, one can strengthen the PNT to obtain explicit bounds on $n$-th prime valid even for small values of $n$. These can then be used to prove Bertrand's postulate too.

You need a precise estimate of the form $$c_1<\frac{\pi(n)\ln n}{n}<c_2.$$ With that you can derive $\pi(2n)>c_1\frac{2n}{\ln(2n)}>2c_1\frac{n}{\ln 2+\ln n}$. If you are lucky, you can continue$2c_1\frac n{\ln2+\ln n}>c_2\frac n{\ln n}>\pi(n)$. However, for this you better have $\frac{2c_1}{c_2} >1+\frac{\ln 2}{\ln n}$. So at least if $c_2<2c_1$, your idea works for sufficiently big $n$.

  • $\begingroup$ Can't we just say that it is true for sufficiently big $n$ without proving that $c_2<2c_1$? Because i think finding $c_2$ and $c_1$ might be hard. $\endgroup$
    – CODE
    May 23 '13 at 15:48
  • 2
    $\begingroup$ The best know unconditional estimates have been calculated by Pierre Dusart and are available here. arxiv.org/pdf/1002.0442v1.pdf $\endgroup$ May 23 '13 at 15:49

The following long-standing conjecture, due to Legendre, has a flavour similar to Bertrand's Postulate. For every $n\gt 1$, there is always a prime between $n^2$ and $(n+1)^2$.

By using the Prime Number Theorem, we can see that "usually," for large $n$, there are many primes between $n^2$ and $(n+1)^2$. However, the PNT is consistent with substantial irregularities of distribution, and is not strong enough to settle Legendre's conjecture.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.