This post is motivated by the ongoing Polymath Project “finding primes”, an open source mathematics project whose aim (roughly speaking) is to find an efficient algorithm to deterministically generate a prime number of at least [tex]k[/tex] digits. The post isn’t a contribution to the ongoing research discussion, but rather describes background material I wanted to understand better: a proof of a mathematical theorem known as Bertrand’s Postulate, a simple result from the 19th century about how frequently prime numbers occur. It’s being cross-posted to the Polymath wiki. The post requires some familiarity with elementary number theory.
Despite its name, Bertrand’s postulate is a theorem, not an example of what we’d ordinarily call a postulate in mathematics. Here’s what it says:
Theorem (Bertrand’s Postulate): For every integer [tex]n \geq 2[/tex], there is a prime [tex]p[/tex] satisfying [tex]n < p < 2n[/tex].
Bertrand’s postulate is relevant to the finding primes problem because it guarantees the existence of a [tex]k[/tex]-digit prime for any [tex]k[/tex]. Brute force search thus yields a [tex]k[/tex]-digit prime after about [tex]O(10^k)[/tex] steps; this can be considered the “trivial bound” for the problem.
Bertrand’s postulate was apparently first proved by Chebyshev. For large [tex]n[/tex], the claim follows as a consequence of the prime number theorem. We will give an elementary proof due to Erdos.
Our strategy is to analyse the prime factorization of the binomial coefficient [tex]{2n \choose n}[/tex]. What we’ll discover is that for primes [tex]p \leq n[/tex], the corresponding prime power in the prime factorization of [tex]{2n \choose n}[/tex] is never very big. In fact, we can guarantee that those powers are quite small – much smaller than what one might a priori believe could be the case. What we’ll find as a consequence is that when we take the product of all the prime powers for [tex]p \leq n[/tex], the product can’t possibly be as big as [tex]{2n \choose n}[/tex]. And that means that there must be primes in the range [tex]n < p < 2n[/tex] which appear in the prime factorization of [tex]{2n \choose n}[/tex].
Rather than prove Bertrand's postulate directly, we'll first prove two results of independent interest. The first is a bound on the product of all primes less than [tex]n[/tex], due to Chebyshev.
Lemma (Chebyshev bound): For integers [tex]n \geq 2[/tex], [tex]\prod_{p \leq n} p \leq 4^n[/tex], where the product is over all primes [tex]p[/tex] less than or equal to [tex]n[/tex].
The Chebyshev bound tells us that primes can’t occur too frequently (for example, with constant density) in the positive integers, for if they did, the product of primes on the left would rise much faster than [tex]4^n[/tex]. Although it’s not needed for a proof of Bertrand’s postulate, insight can be gained by expressing this idea in a simple quantitative way. Observe that if [tex]\pi(n)[/tex] is the number of primes less than or equal to [tex]n[/tex], then [tex]\pi(n)! \leq \prod_{p \leq n} p[/tex], simply because the [tex]k[/tex]th prime must be at least [tex]k[/tex]. Combining this observation with Chebyshev’s bound gives [tex]\pi(n)! \leq 4^n[/tex]. Taking logarithms of both sides, and applying Stirling’s approximation, we see that up to constant factors and small corrections, we have [tex]\pi(n) \ln \pi(n) \leq n[/tex]. This, in turn, implies that, up to constant factors and small corrections, [tex]\pi(n) \leq n \ln \ln n / \ln n[/tex]. Roughly speaking, the prime numbers are at most logarithmically dense in the positive integers. In fact, the prime number theorem tells us that [tex]\pi(n) \approx n / \ln n[/tex], as [tex]n[/tex] becomes large.
Proof of Chebyshev’s bound: We will induct on [tex]n[/tex]. The case when [tex]n=2[/tex] is obviously true. Furthermore, if we assume the result when [tex]n[/tex] is odd, it follows immediately for [tex]n+1[/tex], since the left-hand side is not affected by incrementing [tex]n[/tex]. So we assume the result is true up to some even number, [tex]n = 2m[/tex], and try to prove the result for [tex]2m+1[/tex]. What we’ll aim to show is that:
[tex] (*) \prod_{m+1 < p \leq 2m+1} p \leq 4^m [/tex]
If we can prove this, then multiplying by the inequality [tex]\prod_{p \leq m+1} p \leq 4^{m+1}[/tex] (which is true by the inductive hypothesis) will give us the desired result. To prove (*), note that every prime [tex]p[/tex] satisfying [tex]m+1 < p \leq 2m+1[/tex] must divide [tex]{2m+1 \choose m}[/tex], since [tex]p[/tex] appears in the numerator, but not the denominator. Furthermore, the uniqueness of prime factorization means that the product of all such primes must also divide [tex]{2m+1 \choose m}[/tex], and so we have
[tex] \prod_{m+1 < p \leq 2m+1} p \leq {2m+1 \choose m}. [/tex]
The proof is completed by noting that [tex]{2m+1 \choose m}[/tex] appears twice in the binomial expansion of [tex](1+1)^{2m+1}[/tex], and thus [tex]{2m+1 \choose m} \leq 4^m[/tex]. QED
There are two main ideas in our proof of Chebyshev’s bound, and it’s worth pausing to appreciate them. The first idea is that there should be a relationship between products of primes and factorials, e.g.,
[tex] \prod_{m+1 < p \leq 2m+1} p \leq {2m+1 \choose m}. [/tex]
The second is that there should be a relationship between combinatorial coefficients like [tex]{2m+1 \choose m}[/tex] and exponentials with fixed bases, e.g., [tex]{2m+1 \choose m} \leq 4^m[/tex]. Once these two ideas are firmly in mind, the proof of the Chebyshev bound is obvious.
The second lemma used in our proof of Bertrand's postulate is a useful fact about the prime factorization of [tex]{2n \choose n}[/tex], telling us that [tex]{2n \choose n}[/tex] has a rather special prime factorization which only involves low powers. After the main statement of the lemma we will single out two special cases where the proof can be used to make statements that are a little stronger than the main statement. These cases are included explicitly only because they are useful later. Note that although they complicate the statement of the lemma somewhat, they are trivial consequences of the proof of the main statement in the lemma.
Lemma: Let [tex]p[/tex] be a prime, and define [tex]r(p,n)[/tex] to be the largest number such that [tex]p^{r(p,n)}[/tex] divides [tex]{2n \choose n}[/tex]. Then [tex]p^{r(p,n)} \leq 2n[/tex]. There are two special cases where we can make stronger statements: (1) if [tex]p > \sqrt{2n}[/tex], then [tex]r(p,n)[/tex] is [tex]1[/tex] or [tex]0[/tex]; (2) if [tex]2n/3 < p \leq n[/tex], then [tex]r(p,n) = 0[/tex].
This lemma contains the essential insight underlying Bertrand’s postulate, and that we explained earlier: because we can guarantee that the prime powers are low, [tex]{2n \choose n}[/tex] must have many prime factors. A careful accounting using the Chebyshev bound will show that we simply don’t have enough if one of those prime factors isn’t in the range [tex]n < p < 2n[/tex].
Proof: To prove the lemma, first note that the prime power of [tex]p[/tex] in the factorization of [tex]n![/tex] is given by [tex]\sum_{j=1}^{\infty} \lfloor n / p^j \rfloor[/tex]. As a result, [tex]r(p,n) = \sum_{j=1}^\infty ( \lfloor 2n / p^j \rfloor – 2 \lfloor n / p^j \rfloor)[/tex]. All terms in this sum are either [tex]0[/tex] or [tex]1[/tex], depending on whether [tex]\lfloor 2n/p^j \rfloor[/tex] is even or odd, and they are always [tex]0[/tex] when [tex]j > \log_p (2n)[/tex], whence [tex]r(p,n) \leq \log_p (2n)[/tex], which gives the main result.
In the special case of (1), [tex]p > \sqrt{2n}[/tex], simply observe that all but the first term in the sum vanishes, and so [tex]r(p,n) = \lfloor 2n/ p \rfloor – 2 \lfloor n/p \rfloor[/tex], which is either [tex]0[/tex] or [tex]1[/tex], according to whether [tex]\lfloor 2n/p \rfloor[/tex] is even or odd.
In the special case of (2), [tex]2n/3 < p \leq n[/tex], observe again that all but the first term in the sum vanishes, and so [tex]r(p,n) = \lfloor 2n/p \rfloor - 2 \lfloor n/p \rfloor[/tex]. But for any such value of [tex]p[/tex] we see that [tex]\lfloor 2n/p \rfloor[/tex] is equal to [tex]2[/tex], which is even, and so [tex]r(p,n) = 0[/tex]. QED
The proof of Bertrand’s postulate is now straightforward.
Proof of Bertrand’s postulate: For a contradiction, suppose there are no primes satisfying [tex]n < p < 2n[/tex]. In light of case (2) of the last lemma, we can assume that all the prime factors in [tex]{2n \choose n}[/tex] satisfy [tex]p \leq 2n/3[/tex]. We split the prime factorizing of [tex]{2n \choose n}[/tex] up into the cases where [tex]p \leq \sqrt{2n}[/tex] and where [tex]\sqrt{2n} < p \leq 2n/3[/tex]. Applying the last lemma we obtain:
[tex] {2n \choose n} \leq \prod_{p \leq \sqrt{2n}} (2n) \prod_{\sqrt{2n} < p \leq 2n/3} p [/tex]
We can bound the first product by noting that there are no more than [tex]\sqrt{2n}[/tex] primes of size at most [tex]\sqrt{2n}[/tex], and bound the second product using Chebyshev's bound:
[tex] {2n \choose n} \leq (2n)^{\sqrt 2n} 4^{2n/3}. [/tex]
Observing that [tex]{2n \choose n}[/tex] is the largest of the [tex]2n+1[/tex] terms in the binomial expansion of [tex](1+1)^{2n}=4^n[/tex], we see that
[tex] \frac{4^n}{2n+1} \leq {2n \choose n} [/tex]
Combinining the last two inequalities and rearranging a little gives
[tex] 4^{n/3} \leq (2n+1)(2n)^{\sqrt 2n}. [/tex]
The left-hand side rises much faster than the right, and so this inequality can only be true over some finite set of [tex]n[/tex]. It should be straightforward to convince yourself that it fails for [tex]n > 2048[/tex], for example, and thus we must have [tex]n \leq 2048[/tex]. In fact, we can do quite a bit better than [tex]n \leq 2048[/tex] with a bit more work, but the bound suffices for our purposes. What we have now shown is that our initial assumption – no prime in the range [tex]n < p < 2n[/tex] - can only possibly hold when [tex]n \leq 2048[/tex]. But it's easily seen that the assumption is also false in that range, just by considering the sequence of primes [tex]2,3,5,7,13,23,43,83,163,317,631,1259[/tex], and [tex]2503[/tex]. Each prime in the sequence is less than twice its predecessor, and so there must be a prime between [tex]n[/tex] and [tex]2n[/tex] for any [tex]n \leq 2048[/tex]. QED