Holy primes between n and 2n, Bertrand!

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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s