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 , there is always a prime such that .
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 . Suppose we wanted to find a prime between and . We could find it as a divisor of . We certainly wouldn’t find it in . So in particular, it would be a divisor of
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 , let denote the exponent of in . That is,
Throughout the entire post, 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.
I’m implicitly assuming here that . This isn’t always the case. However, it is the case for . So for I’ll have to check it some other way. Not a big loss.
Yellow ( to ):
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 and , so that the yellow product is empty. We can replace the yellow product with .
Blue ( to ):
I’ve been told that Erdős thought this step was the most important in the entire proof. Suppose I had a prime such that . How many times does show up in ? Only twice. There’s and . This is because . But clearly shows up in exactly once. This means that can’t be divisible by any primes between and , so the blue product is just .
Green ( to ):
This is probably the hardest part. If is a prime such that , then . This is just because . So the green product is just the product of primes between and . That is certainly less than all the product of all primes less than , so the green product is bounded by . 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 . We’ll show that , so we can bound the green product by .
The proof is done by induction. It’s obvious for or . Otherwise, if and even, which is at least by induction, so . If is odd, let . Clearly
Now, by induction, , giving us the desired result.
Okay. Now for the lower bound. I claim:
This is comes from the binomial theorem in the following way:
Since the central binomial coefficient is the largest, for any
. That is,
which is what we wanted.
Here’s why this is bad. The lower bound is less than the upper bound, So we have
Asymptotically, the lefthand side grows faster than the righthand side, so for some big enough
, this will always be a contradiction. The point where this starts to be a contradiction is around where
, so for every
, there is always a prime between
. 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.