Bertrand’s Postulate – a BOOK proof

I really enjoyed reading Erdos’s proof of Bertrand’s postulate in “Proofs from THE BOOK”, so I shall attempt writing out here in order to make sure I understand it properly.

Bertrand’s Postulate

For any $n>0$ , there exists a prime number $p$ such that

$\boxed{n < p \leq 2n}$

Proof

The main idea of the proof is estimating the binomial coefficient $2n\choose n$ by using the prime numbers in its factorization. If it were the case that no prime existed between $n$ and $2n$ , then we will see that our bound will enforce $n$ to be small. How small we shall see. But we will end up proving that the statement holds for $n<k$ for some $k>0$ , using a certain clever trick. To get there though, we first have to work on some bounding.

PART 1: THE “BIG” PRIMES IN $\,2n \choose n$

First, let $p\geq 2$ be a prime. By Legendre’s formula, we know that the largest power of $p$ dividing $2n\choose n$ is given by:

$v_p\left(2n\choose n\right) = v_p\left(\frac{(2n)!}{(n!)^2}\right) = \sum\limits_{k\geq 1}\left(\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor\right)$

Each summand is at most one since,

$\left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor < \frac{2n}{p^k}-2\left(\frac{n}{p^k}-1\right) = 2$

Furthermore, if $p^k > 2n$ , then the summand is equal to zero. Thus,

$v_p\left(2n\choose n\right) \leq \max\,\{r\colon p^r \leq 2n\}$

This inequality yields some very useful facts:

The largest power of $p$ that divides $2n\choose n$ is not larger than $2n$ .
Primes $p > \sqrt{2n}$ appear at most once in $2n \choose n$ .

Now, primes $p$ such that $\,\frac{2}{3}n < p \leq n$ cannot divide $2n\choose n$ . $3p > 2n$ so $2p > 2n-p$ . And $p \leq n$ , so $2p > n$ . Thus, in $\frac{(2n)!}{(n!)^2}$ , we have $p$ appearing only once in the numerator and twice in the denominator.

PART 2: BOUNDING $\, 2n\choose n$

First some background on the binomial coefficients. We know the following properties:

$\sum\limits_{k=0}^{n} {n\choose k} = 2^n$
${n \choose k} = {n \choose n-k}$
${n \choose k} = \frac{n-k+1}{k}{n\choose k-1}$ . Using this and (2) we can prove that:
$1 = {n\choose 0} < {n \choose 1} <\cdots< {n \choose \lfloor n/2 \rfloor} = {n \choose \lceil n/2 \rceil} >\cdots> {n \choose n-1} > {n \choose n} = 1$ (unimodal sequence)

From (1) we know that for all $k$ it is true that ${n \choose k} \leq 2^n$ . From (4) we know that ${n \choose \lfloor n/2 \rfloor} \geq \frac{2^n}{n}$ , since the largest element in a sequence is greater than or equal to the average of the sequence. Now we can infer that

$\boxed{{2n \choose n} \geq \frac{4^n}{2n}}$

So we have now (CRUX MOVE):

$\boxed{\frac{4^n}{2n} \leq {2n \choose n} \leq \prod\limits_{p\leq \sqrt{2n}}{2n}\cdot\prod\limits_{\sqrt{2n} < p \leq \frac{2}{3}n}p\cdot\prod\limits_{n<p\leq 2n}p}$

To make sure you understand why this holds, be able to answer the following:

Why do we take primes only up to $2n$ ?
Why do we not take any primes between $\frac{2}{3}n$ and $n$ ?
Why is the exponent of each prime 1?

Now we have:

$4^n \leq (2n)^{1+\sqrt{2n}}\cdot \prod\limits_{\sqrt{2n}<p\leq\frac{2}{3}n}p\cdot\prod\limits_{n<p\leq 2n}p$

Let’s assume, for the sake of contradiction, that there are no primes between $n$ and $2n$ . Then the inequality above becomes:

$4^n \leq (2n)^{1+\sqrt{2n}}\cdot \prod\limits_{\sqrt{2n}<p\leq\frac{2}{3}n}p$

We shall show that for this to hold, $n$ must be small enough that we will actually be able to prove Bertrand’s postulate for such $n$ .

First we need the following lemma:

LEMMA

For all reals $x\geq 2$ , we have that

$\boxed{\prod\limits_{p\leq x}p \leq 4^{x-1}}$

Proof

Let $q$ be the largest prime with $q\leq x$ . Then $\prod\limits_{p\leq x}p = \prod\limits_{p \leq q}p$ and $4^{q-1} \leq 4^{x-1}$ , so it suffices to prove our statement for $x = q$ prime. For $q=2$ the result is trivial and so we consider odd primes $q = 2m+1$ .

Then we inductively compute:

$\prod\limits_{p \leq 2m+1}p = \prod\limits_{p \leq m+1}p \cdot \prod\limits_{m+1 < p \leq 2m+1}p \leq 4^m{{2m+1}\choose m} \leq 4^m 2^{2m} = 4^{2m}$

There are a few parts to this computation:

$\prod\limits_{p \leq m+1}p \leq 4^m$ holds by induction.
$\prod\limits_{m+1 < p \leq 2m+1}p \leq {{2m+1}\choose m}$ comes from the observation that ${{2m+1}\choose m} = \frac{(2m+1)!}{m!(m+1)!}$ is an integer, where the primes we consider are all factors of the denominator but not of the numerator.
Finally, ${{2m+1}\choose m} \leq 2^{2m}$ form the properties (1) and (2) of the binomial coefficient presented above.

PART 3: GETTING THE CONTRADICTION

The last Lemma we proved as well as the inequality above yield that:

$4^n \leq (2n)^{1+\sqrt{2n}}4^{\frac{2}{3}n} \Leftrightarrow 4^{\frac{1}{3}n} \leq (2n)^{1+\sqrt{2n}}$

With some clever algebra we can see that this fails to hold for large $n$ . First, we know by induction that if $a\geq 2$ , then $a+1 < 2^a$ . So:

$2n = \left(\sqrt[6]{2n}\right)^6 < \left(\lfloor\sqrt[6]{2n}\rfloor + 1\right)^6 < 2^{6\lfloor\sqrt[6]{2n}\rfloor} \leq 2^{6\sqrt[6]{2n}}$

Now:

$2^{2n} \leq (2n)^{3\left(1+\sqrt{2n}\right)} < 2^{\sqrt[6]{2n}\left(18+18\sqrt{2n}\right)} \overset{n\geq 50}{<} 2^{20\sqrt[6]{2n}\sqrt{2n}}= 2^{20(2n)^{2/3}}$

So we get $(2n)^{1/3} < 20$ and thus $n < 4000$ . This is a contradiction because we can easily show Bertrand’s postulate to hold for $n < 4000$ . An impressive trick to establish this right away is due to Landau:

It suffices to check that the sequence

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

consists of prime number where each is smaller than twice the previous one. Thus every interval $\{y\colon n < y \leq 2n\}$ with $n \leq 4000$ contains one of these 14 primes and our proof concludes.

Themistoklis Haris

themisharis@gmail.com

Bertrand’s Postulate – a BOOK proof