Proofs of Bertrand's Postulate

What is Bertrand's Postulate?

Joseph Bertrand stated that, for every $n>1$, there is a prime between $n$ and $2n$. That is, for $n>1$, there is a $p$ with $n<p<2n$. You can see some examples for small values of $n$ that the conjecture holds. Chebyshev proved it around $1850$, but his proof was analytic. Later, Ramanujan also provided a short proof of the theorem but he used Gamma function to do that. Paul Erdős was the first one (to my knowledge) to provide an elementary proof of this theorem, using only properties of binomial coefficients (one of the reasons why the author likes Erdős so much).

We can also write it in some other forms. For example: for a real number $x$, let $\pi(x)$ be the number of primes less than or equal to $x$. Then, Bertrand's theorem says, $\pi(2x)-\pi(x)\geq1$ for $x>1$.

(Actually, the Prime Number Theorem asserts that in fact $\pi(x)$ is quite close to $\frac{x}{\ln x}$, and so $\pi(2x)-\pi(x)>0$ becomes immediately clear for $x$ large enough. However, this proof approach is quite overkill.)

The proof of Bertrand's Postulate

We will use sum and product notation, the floor function, and logarithms. In this explanation, I will write the reasoning somewhat tersely, so you would understand the structure of the proof and the intuition behind it. If you don't understand a step, try to check it yourself.

Erdős considered the binomial coefficient $\binom{2n}{n}$ and its prime factorization $\displaystyle\prod_{p\le 2n}p^{\alpha_p}$.

From here, we know that

$$\alpha_p=\sum_{i=1}^{\left\lfloor \log_p(2n)\right\rfloor}\left( \left\lfloor \frac{2n}{p^i} \right\rfloor-2\left\lfloor \frac{n}{p^i} \right\rfloor \right).$$

Look more closely at these terms. Since they are all of the form $\lfloor 2x \rfloor -2\lfloor x\rfloor$, it is easy to check that their value is $0$ or $1$. This means that

$$\alpha_p\le \log_p(2n).$$

Knowing that $\alpha_p\le \log_p(2n)$ tells us a lot about the $\alpha_p$'s. In fact, we have $\alpha_p\in\{0,1\}$ if $\alpha_p<2$, i.e., if $p>\sqrt{2n}$. Moreover, $$\sqrt{2n}<p\le 2n\quad\implies\quad \alpha_p=\left\lfloor \frac{2n}{p} \right\rfloor -2\left \lfloor \frac{n}{p}\right\rfloor.$$

Based on this, our last important remark is that if $p$ satisfies $(\sqrt{2n}<)\frac{2n}3<p\le n$, then $\alpha_p=2-2=0$. Hence, there are no prime divisors $p$ of $\binom{2n}{n}$ with $\frac{2n}{3}<p\le n$.

These preliminary investigations are enough to give estimates for the prime factorization to tackle the theorem. We cut up the product into four bits:

$$\binom{2n}{n}=\underbrace{\prod_{p\le \sqrt{2n}}p^{\alpha_p}}_{=A}\cdot \underbrace{\prod_{\sqrt{2n}<p\le \frac{2n}{3}}p^{\alpha_p}}_{=B}\cdot \underbrace{\prod_{\frac{2n}{3}<p\le n}p^{\alpha_p}}_{=C}\cdot \underbrace{\prod_{n<p\le 2n}p^{\alpha_p}}_{=D}.$$

Firstly, since $\alpha_p\le \log_p(2n)$, we have $p^{\alpha_p}\le 2n$. As $A$ has at most $\sqrt{2n}-1$ prime factors, we may write $$A\le (2n)^{\sqrt{2n}-1}.$$

Secondly, as $\alpha_p\le 1$ for $p>\sqrt{2n}$, we may estimate $B$ like this: $$B\le \prod_{p\le \frac{2n}{3}}p<4^{\frac{2n}{3}}.$$ Wait, what? OK, here, the first estimate is clear: we just added a bunch more prime divisors (even when we included all the primes $p\le \sqrt{2n}$, those didn't increase the product by too much). But the second?

Haha, this is the focal point of the proof: Erdős' great result was that for all reals $x\ge 2$, we have $$\prod_{p\le x}p<4^x.$$ I'll call this claim $(*)$ and prove it later.

Let's move forward: we also showed that $\alpha_p=0$ for $\frac{2n}{3}<p\le n$, hence $C=1$. Furthermore, if we supposed that there is no prime between $n$ and $2n$, then we'd have $D=1$ as well.

All this yields $$\binom{2n}{n}<(2n)^{\sqrt{2n}-1}\cdot 4^{\frac{2n}{3}}\cdot 1\cdot 1.$$

Combining this with the bound $\binom{2n}{n}\ge \frac{2^{2n}}{2n}$, we get that if there is no prime $p$ with $n<p\le 2n$, then

$$\frac{2^{2n}}{2n}<(2n)^{\sqrt{2n}-1}\cdot 4^{\frac{2n}{3}},$$ $$\frac{2^{2n}}{2^{2\cdot \frac{2n}3}}<(2n)^{\sqrt{2n}},$$

(taking $\sqrt{2n}$-th roots:)

$$2^{\sqrt{2n}/3}<2n.$$

Darn, this isn't a contradiction! However, this inequality doesn't seem to be true for large $n$ - already for $n=450$, the reverse holds, because $\sqrt{2\cdot 450}=30$ and $2^{10}>2\cdot 450$. One can show that it remains false for $n\ge 450$ (see the practice problems). So we have reached a contradiction for $n\ge 450$, and it remains to verify that there is a prime between $n$ and $2n$ for $n<450$. This is a piece of cake, as one of the following primes does the trick:

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

It only remains to prove Erdős' estimate $(*)$.

Clearly, it suffices to prove $(*)$ for integers, because if it holds for $\lfloor x\rfloor$, then it holds for $x$ as well:

$$\prod_{p\le x}p=\prod_{p\le \lfloor x\rfloor}p<4^{\lfloor x\rfloor }\le 4^x.$$

We employ a tricky inductive method. Our base case is $x=2$ and $x=3$: $2<4^2$ and $2\cdot 3<4^3$ indeed. Suppose $(*)$ holds for $x=2,3,\dots,n-1$, and now we wish to prove it for $n$ ($n\ge 4$). Now if $n\ge 4$ is an integer, it may be written as $n=2k-1$ or as $n=2k$, where $k\ge 2$ is an integer smaller than $n$.

The idea is that since each prime $p$ with $k<p\le 2k-1$ divides the numerator of $\binom{2k-1}k=\frac{(2k-1)!}{k!\cdot (k-1)!}$ but not the denominator, we may write $\prod_{k<p\le 2k-1}p\mid \binom{2k-1}k$, thus

$$\prod_{k<p\le 2k-1}p\le \binom{2k-1}{k}<\frac{2^{2k-1}}{2}=4^{k-1}$$

for $n=2k-1$ and similarly, we get

$$\prod_{k<p\le 2k}p\le \binom{2k}{k}<2^{2k}=4^k$$

for $n=2k$. Multiplying this with the induction hypothesis

$$\prod_{p\le k}p<4^k$$

yields the inequality $(*)$ in the case $x=n$.

Prove that for $x\ge 2$, we have

$$\prod_{p\le x}p<4^{x-1}.$$

Prove that the inequality $2^{\sqrt{2n}/3}> 2n$ holds for $n\ge 450$.

(Hint: $2n$ is between two square numbers - $k^2\le 2n<(k+1)^2$ where $k\ge 30$.)