Bertrand's postulate

In number theory, Bertrand's postulate is a theorem stating that for any integer $n > 3$, there always exists at least one prime number $p$ with
:$n < p < 2n - 2.$
A less restrictive formulation is: for every $n > 1$, there is always at least one prime $p$ such that
:$n < p < 2n.$
Another formulation, where $p_n$ is the $n$-th prime, is: for $n \ge 1$
:$p_ < 2p_n.$

This statement was first conjectured in 1845 by Joseph Bertrand (1822–1900). Bertrand himself verified his statement for all integers $2 \le n \le 3\,000\,000$.

His conjecture was completely proved by Chebyshev (1821–1894) in 1852 and so the postulate is also called the Bertrand–Chebyshev theorem or Chebyshev's theorem. Chebyshev's theorem can also be stated as a relationship with $\pi(x)$, the prime-counting function (number of primes less than or equal to $x$):
:$\pi(x) - \pi\bigl(\tfrac\bigr) \ge 1$, for all $x \ge 2$.

Prime number theorem

The prime number theorem (PNT) implies that the number of primes up to ''x'' is roughly ''x''/ln(''x''), so if we replace ''x'' with 2''x'' then we see the number of primes up to 2''x'' is asymptotically twice the number of primes up to ''x'' (the terms ln(2''x'') and ln(''x'') are asymptotically equivalent). Therefore, the number of primes between ''n'' and 2''n'' is roughly ''n''/ln(''n'') when ''n'' is large, and so in particular there are many more primes in this interval than are guaranteed by Bertrand's postulate. So Bertrand's postulate is comparatively weaker than the PNT. But PNT is a deep theorem, while Bertrand's Postulate can be stated more memorably and proved more easily, and also makes precise claims about what happens for small values of ''n''. (In addition, Chebyshev's theorem was proved before the PNT and so has historical interest.)

The similar and still unsolved Legendre's conjecture asks whether for every ''n'' ≥ 1, there is a prime ''p'' such that ''n''² < ''p'' < (''n'' + 1)². Again we expect that there will be not just one but many primes between ''n''² and (''n'' + 1)², but in this case the PNT doesn't help: the number of primes up to ''x''² is asymptotic to ''x''²/ln(''x''²) while the number of primes up to (''x'' + 1)² is asymptotic to (''x'' + 1)²/ln((''x'' + 1)²), which is asymptotic to the estimate on primes up to ''x''². So unlike the previous case of ''x'' and 2''x'' we don't get a proof of Legendre's conjecture even for all large ''n''. Error estimates on the PNT are not (indeed, cannot be) sufficient to prove the existence of even one prime in this interval.

Generalizations

In 1919, Ramanujan (1887–1920) used properties of the Gamma function to give a simpler proof. The short paper included a generalization of the postulate, from which would later arise the concept of Ramanujan primes. Further generalizations of Ramanujan primes have also been discovered; for instance, there is a proof that

:$2p_ > p_i \text i>k \text k=\pi(p_k)=\pi(R_n)\, ,$

with ''p''_''k'' the ''k''th prime and ''R''_''n'' the ''n''th Ramanujan prime.

Other generalizations of Bertrand's postulate have been obtained using elementary methods. (In the following, ''n'' runs through the set of positive integers.) In 2006, M. El Bachraoui proved that there exists a prime between 2''n'' and 3''n''. In 1973, Denis Hanson proved that there exists a prime between 3''n'' and 4''n''. Furthermore, in 2011, Andy Loo proved that as ''n'' tends to infinity, the number of primes between 3''n'' and 4''n'' also goes to infinity, thereby generalizing Erdős' and Ramanujan's results (see the section on Erdős' theorems below). The first result is obtained with elementary methods. The second one is based on analytic bounds for the factorial function.

Sylvester's theorem

Bertrand's postulate was proposed for applications to permutation groups. Sylvester (1814–1897) generalized the weaker statement with the statement: the product of ''k'' consecutive integers greater than ''k'' is divisible by a prime greater than ''k''. Bertrand's (weaker) postulate follows from this by taking ''k'' = ''n'', and considering the ''k'' numbers ''n'' + 1, ''n'' + 2, up to and including ''n'' + ''k'' = 2''n'', where ''n'' > 1. According to Sylvester's generalization, one of these numbers has a prime factor greater than ''k''. Since all these numbers are less than 2(''k'' + 1), the number with a prime factor greater than ''k'' has only one prime factor, and thus is a prime. Note that 2''n'' is not prime, and thus indeed we now know there exists a prime ''p'' with ''n'' < ''p'' < 2''n''.

Erdős's theorems

In 1932, Erdős (1913–1996) also published a simpler proof using binomial coefficients and the Chebyshev function ''θ'', defined as:

:$\vartheta(x) = \sum_^x \ln(p)$

where ''p'' ≤ ''x'' runs over primes. See proof of Bertrand's postulate