The Beauty of Primes 2: A Proof of Bertrand's Postulate

素数之美2：Bertrand假设的证明 苏剑林 · 2014-08-09 · Mathematics prime number number theory

With the foundation of $\prod\limits_{p\leq n}p < 4^{n-1}$ from the previous post, we're actually already quite close to a proof of Bertrand's postulate. The proof of Bertrand's postulate rests on a careful examination of the prime factor multiplicities in the binomial coefficient $C_n^{2n}$. In this post, we'll first derive a lower-bound formula for a product of primes, and use it to prove a slightly weaker version of Bertrand's postulate. Finally, with a simple trick, we'll push our proof all the way to Bertrand's postulate itself.

Prime factors of binomial coefficients

First, let's examine the multiplicity of the prime factor $p$ in $n!$. The result is a formula known as Legendre's theorem:

The multiplicity of the prime factor $p$ in $n$ is exactly $\sum\limits_{k\geq 1}\left\lfloor\frac{n}{p^k}\right\rfloor$.

The proof is simple: since $n!=1\times 2\times 3\times 4\times \dots \times n$, every $p$ numbers there's a multiple of $p$, every $p^2$ numbers there's a multiple of $p^2$, every $p^3$ numbers there's a multiple of $p^3$, and so on—each additional power contributes one more factor of $p$. So we simply sum up all these interval counts. Note that although the sum is written in an infinite form, only finitely many terms are nonzero. more

Next, we use the above formula to examine the multiplicity of the prime factor $p$ in $C_{n}^{2n}=\frac{(2n)!}{n! n!}$. Since this is just a matter of dividing factorials, the multiplicity of the prime factor $p$ in $C_n^{2n}$ is

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

Notice that the term inside the brackets is at most 1, 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$. So, letting the multiplicity of $p$ in $C_n^{2n}$ be $\nu_p$, we get

$$\nu_p \leq \max \{r,p^r \leq 2n\}$$

This tells us that in $C_n^{2n}$, the multiplicity of any prime factor greater than $\sqrt{2n}$ is at most 1, while the multiplicity of any prime factor less than or equal to $\sqrt{2n}$ is at most 2n, and there are at most $\sqrt{2n}$ primes less than or equal to $\sqrt{2n}$. So we have the formula

$$C_{n}^{2n} \leq (2n)^{\sqrt{2n}}\prod\limits_{\sqrt{2n} < p\leq 2n}p$$

Next, we prove $C_{n}^{2n} >\frac{4^n}{2n}$. In fact this inequality is quite weak, since by the string formula we have $C_{n}^{2n} \sim\frac{4^n}{\sqrt{\pi n}}$, so proving this inequality isn't difficult—we leave it to the reader. Using this inequality, we further obtain

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

If our only goal is proving Bertrand's postulate, we could jump directly to the "Bertrand's postulate" section below. Here, though, let's simply first establish

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

Note that the denominator $(2n)^{1+\sqrt{2n}}$ grows more slowly than the factorial of any $a^n , a>1$. This gives us a (fairly weak) estimate of a lower bound for a product of primes.

The weak Bertrand postulate

A proposition slightly weaker than Bertrand's postulate is:

For any $\varepsilon > 0$, there exists $N(\varepsilon) > 0$ such that for all $ n > N(\varepsilon)$，在$(1-\varepsilon)n$到$2n$, there exists a prime between them.

What we've established above is already enough to prove this claim. Suppose there is no prime between $(1-\varepsilon)n$ and $2n$. Then

$$\prod\limits_{p\leq 2n}p=\prod\limits_{p\leq (1-\varepsilon)n}p$$

By $\prod\limits_{p\leq n}p < 4^{n-1}$, we have

$$\prod\limits_{p\leq 2n}p < 4^{(1-\varepsilon)n-1}$$

Combining this with the result of this post, we get

$$4^{(1-\varepsilon)n-1} > \frac{4^n}{(2n)^{1+\sqrt{2n}}}$$

which is

$$(2n)^{1+\sqrt{2n}} > 4^{\varepsilon n+1}$$

As noted earlier, $(2n)^{1+\sqrt{2n}}$ grows more slowly than the factorial of any $a^n , a>1$, so for sufficiently large n, the above inequality leads to a contradiction. Hence, for sufficiently large n, there is at least one prime between $(1-\varepsilon)n$ and $2n$.

Bertrand's postulate

Now we're just one step away from proving Bertrand's postulate. We need to examine the prime factors of $C_n^{2n}$ more carefully. We find that $C_n^{2n}$ has no prime factors that are $\frac{2n}{3} < p \leq n$! The proof is quite simple: since $C_{n}^{2n}=\frac{(2n)!}{n! n!}$, and $3p > 2n$ tells us that the numerator $(2n)!$ contains exactly $p$ and $2p$, while $p \leq n$ tells us that the denominator $(n!)^2$ contains only the prime factor $p^2$—so after cancelling numerator and denominator, the multiplicity is 0. This gives us

$$C_{n}^{2n} \leq (2n)^{\sqrt{2n}}\prod\limits_{\sqrt{2n} < p\leq \frac{2n}{3}}p\times \prod\limits_{n < p\leq 2n}p$$

Substituting $C_{n}^{2n} >\frac{4^n}{2n}$ and $\prod\limits_{p\leq n}p < 4^{n-1}$ into the above, we get

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

If there is no prime between $n$ and $2n$, then the last term equals 1, and so

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

This inequality leads to a contradiction once $n > 4000$. Therefore, for $ n > 4000$, Bertrand's postulate holds.

For the remaining cases, consider the following list of primes:

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

For any n not exceeding 4000, n must fall between two consecutive entries of this list (or coincide with one of them). This ensures that between n and 2n there is necessarily one of these listed primes, so Bertrand's postulate also holds for n up to 4000.

The proof above is collected in Proofs from THE BOOK, and it establishes a purely elementary upper bound on prime gaps. In fact, this bound can be improved further, but the techniques required become considerably more sophisticated. One still-unsolved conjecture asks whether, for any $n$, there is always a prime between $n^2$ and $(n+1)^2$—this has so far neither been proven nor disproven.