Bertrand-Chebyshev Theorem

From ProofWiki
Jump to: navigation, search

Theorem

For all $n \in \N_{>0}$, there exists a prime number $p$ with $n < p \le 2 n$.


Proof

We will first prove the theorem for the case $n \le 2047$.

Consider the following sequence of prime numbers:

$2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503$

Each prime number is smaller than twice the previous one.

Hence every interval $\{ x: n < x \le 2 n \}$, with $n \le 2047$, contains one of these prime numbers.


Lemma 1

For all $n \in \N$:

$\dbinom {2 n} n \ge \dfrac {2^{2 n}} {2 n + 1}$

where $\dbinom {2 n} n$ denotes a binomial coefficient.


Lemma 2

For all $m \in \N$:

$\displaystyle \prod_{p \mathop \le m} p \le 2^{2 m}$

where the product is taken over all prime numbers $p \le m$.


Lemma 3

If $p$ is a prime number and $p^k \mathrel \backslash \dbinom {2 n} n$, then $p^k \le 2 n$.


In particular, if $p > \sqrt{2 n}$, then $p$ appears at most once in $\dbinom {2 n} n$.

For $n \ge 3$, there is no prime factor $p$ with $\dfrac 2 3 n < p \le n$, for such a prime number divides $n!$ exactly once and $\left({2 n}\right)!$ exactly twice.

Therefore, by Lemma 1:

$\displaystyle \frac {2^{2 n} } {2 n + 1} \le \binom {2 n} n \le \prod_{p \mathop \le \sqrt{2 n}} 2 n \prod_{\sqrt{2 n} \mathop < p \mathop \le \frac 2 3 n} p \prod_{n \mathop < p \mathop \le 2 n} p$

for $n \ge 3$.

Now assume there is no prime number $p$ with $n < p \le 2 n$.

Then we have:

\(\displaystyle \frac {2^{2 n} } {2 n + 1}\) \(\le\) \(\displaystyle \prod_{p \mathop \le \sqrt{2 n} } 2 n \prod_{\sqrt{2 n} \mathop < p \mathop \le \frac 2 3 n} p\)
\(\displaystyle \) \(\le\) \(\displaystyle \left({2 n}\right)^{\sqrt{2 n} } \prod_{p \mathop \le \frac 2 3 n} p\)
\(\displaystyle \) \(\le\) \(\displaystyle \left({2 n}\right)^{\sqrt{2 n} } 2^{\frac 4 3 n}\) by Lemma 2

This is a contradiction if $n$ is large enough.

Indeed, we have:

$2^{\frac 2 3 n} \le \left({2 n + 1}\right) \left({2 n}\right)^{\sqrt {2 n}}$

Now:

$2 n + 1 \le \left({2 n}\right)^2 \le \left({2 n}\right)^{\frac 1 3 \sqrt{2 n}}$

for $n \ge 18$.

So:

$2^{2 n} \le \left({2 n}\right)^{4 \sqrt{2 n}}$

Put $r = \sqrt{2 n}$.

Then:

$2^{r^2} \le r^{8 r}$

or equivalently:

$2^r \le r^8$

This fails when $r = 2^6 = 64$.

It fails thereafter, since $2^r$ increases faster than $r^8$.

So our proof works if:

$n \ge 2^{11} = 2048$

and the examples show it is true for smaller $n$.

$\blacksquare$


Also known as

The Bertrand-Chebyshev theorem is also known as Bertrand's postulate or Bertrand's conjecture.


Source of Name

This entry was named for Joseph Louis François Bertrand and Pafnuty Lvovich Chebyshev.


Historical Note

The Bertrand-Chebyshev Theorem was first postulated by Bertrand in $1845$. He verified it for $n < 3 \, 000 \, 000$.

It became known as Bertrand's Postulate.

The first proof was given by Chebyshev in $1850$ as a by-product of his work attempting to prove the Prime Number Theorem.

After this point, it no longer being a postulate, Bertrand's Postulate was referred to as the Bertrand-Chebyshev Theorem.


In $1919$, Srinivasa Ramanujan gave a simpler proof based on the Gamma function.


In $1932$, Paul Erdős gave an even simpler proof based on basic properties of binomial coefficients. That proof is the one which is presented here.


Sources