Holy primes between n and 2n, Bertrand!

May 18, 2012 Leave a comment

While we’re on the Erdős binge, here’s another proof of his. Warning, this post is long. We’re going to prove that:

For every positive integer $n$ , there is always a prime $p$ such that $n<p<2n$ .

Clearly, this implies there are infinitely many primes. In fact, it’s much stronger, and says something about how quickly the prime numbers grow. There are shorter proofs than the one I’m presenting here, but they use complex analysis. This one is in some sense more elementary.

Here’s the idea. Pick an $n$ . Suppose we wanted to find a prime $p$ between $n$ and $2n$ . We could find it as a divisor of $(2n)!$ . We certainly wouldn’t find it in $n!$ . So in particular, it would be a divisor of

$\displaystyle\binom{2n}n=\frac{(2n)!}{n!n!}$ .

So the goal is to estimate these central binomial coefficients in two ways. One will give us an upper bound, and the other a lower bound. If we assume that Bertrand’s postulate is false, we’ll get that the lower bound is actually bigger than the upper bound, a contradiction.

I’ll do the more complicated one first (the upper bound). For each prime $p$ , let $e_p$ denote the exponent of $p$ in $\binom{2n}n$ . That is,

$\displaystyle\binom{2n}n=\prod_{p\le 2n}p^{e_p}$

Throughout the entire post, $p$ will always denote a prime. We’re going to break the product up into four pieces depending on the size of the primes. I’ll color code them to make it easier.

$\displaystyle\binom{2n}n=$ $\left(\displaystyle\prod_{p>0}^{p\le \sqrt{2n}}p^{e_p}\right)$ $\left(\displaystyle\prod_{p>\sqrt{2n}}^{p\le2n/3}p^{e_p}\right)$ $\left(\displaystyle\prod_{p>2n/3}^{p\le n}p^{e_p}\right)$ $\left(\displaystyle\prod_{p>n}^{p\le2n}p^{e_p}\right)$

I’m implicitly assuming here that $\sqrt{2n}<2n/3$ . This isn’t always the case. However, it is the case for $n>5$ . So for $n<5$ I’ll have to check it some other way. Not a big loss.

Yellow ( $n$ to $2n$ ):

We’re going to assume for the sake of contradiction that Bertrand’s postulate is false. That is, we’re going to assume there aren’t any primes between $n$ and $2n$ , so that the yellow product is empty. We can replace the yellow product with $1$ .

Blue ( $2n/3$ to $n$ ):

I’ve been told that Erdős thought this step was the most important in the entire proof. Suppose I had a prime $p$ such that $2n/3<p\le n$ . How many times does $p$ show up in $2n!$ ? Only twice. There’s $p$ and $2p$ . This is because $3p>3\cdot 2n/3=2n$ . But clearly $p$ shows up in $n!$ exactly once. This means that $\binom{2n}n$ can’t be divisible by any primes between $2n/3$ and $n$ , so the blue product is just $1$ .

Green ( $\sqrt{2n}$ to $2n/3$ ):

This is probably the hardest part. If $p$ is a prime such that $\sqrt{2n}<p\le 2n/3$ , then $e_p=1$ . This is just because $p^2>2n$ . So the green product is just the product of primes between $\sqrt{2n}$ and $2n/3$ . That is certainly less than all the product of all primes less than $2n/3$ , so the green product is bounded by $(2n/3)\#$ . The $\#$ is the “primorial” function. It’s like the factorial, but it is the product of just the primes less than a given number. So we want to estimate $(2n/3)\#$ . We’ll show that $k\#<4^k$ , so we can bound the green product by $4^{2n/3}$ .

The proof is done by induction. It’s obvious for $n=1$ or $n=2$ . Otherwise, if $n>2$ and even, $n\#=(n-1)\#$ which is at least $4^{n-1}$ by induction, so $n\#<4^{n-1}<4$ . If $n$ is odd, let $n=2m+1$ . Clearly

$4^m=\frac12(1+1)^{2m+1}>\binom{2m+1}m\ge\displaystyle\prod_{p>m+1}^{p<2m+1}p>\frac{(2m+1)\#}{(m+1)\#}$

Now, by induction, $(m+1)\#<4^{m+1}$ , giving us the desired result.

Red ( $0$ to $\sqrt{2n}$ ):

At this point, I’ve become bored of estimating, so I won’t try to do it well. Each prime power $p^{e_p}$ for $p<\sqrt n$ is obviously less than $2n$ , and there are at most $\sqrt{2n}$ such primes, so the red product is less than $(2n)^{\sqrt{2n}}$ .

Okay. Now for the lower bound. I claim:

$\frac{4^n}{2n+1}<\binom{2n}n$ .

This is comes from the binomial theorem in the following way:

$4^n=(1+1)^{2n}=\sum_{k=0}^{2n}\binom{2n}k$ .

Since the central binomial coefficient is the largest, for any $k$ , $\binom{2n}k\le\binom{2n}n$ . That is,

$4^n<\sum_{k=0}^{2n}\binom{2n}n=(2n+1)\binom{2n}n$

which is what we wanted.

Here’s why this is bad. The lower bound is less than the upper bound, So we have

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

Asymptotically, the lefthand side grows faster than the righthand side, so for some big enough $n$ , this will always be a contradiction. The point where this starts to be a contradiction is around where $n=500$ , so for every $n>500$ , there is always a prime between $n$ and $2n$ . For everything else, we will give a sequence of primes, each less than twice the previous. It’s a worthwhile exercise to think about how this works.

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

Filed under Number Theory

Andy Soffer