Bertrand's postulate

Despite its name, Bertrand's postulate is actually a theorem rather than a postulate:

Theorem (Bertrand's Postulate): For every integer [math]\displaystyle{ n \geq 2 }[/math], there is a prime [math]\displaystyle{ p }[/math] satisfying [math]\displaystyle{ n \lt p \lt 2n }[/math].

The relevance of Bertrand's postulate to the finding primes problem is that it guarantees the existence of a [math]\displaystyle{ k }[/math]-digit prime for any [math]\displaystyle{ k }[/math]. Brute force search thus yields a [math]\displaystyle{ k }[/math]-digit prime after about [math]\displaystyle{ O(10^k) }[/math] steps; this can be considered the "trivial bound" for the problem.

Bertrand's postulate was apparently first proved by Chebyshev. For large [math]\displaystyle{ n }[/math], 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 [math]\displaystyle{ {2n \choose n} }[/math]. What we'll discover is that for primes [math]\displaystyle{ p \leq n }[/math], the corresponding prime power in the prime factorization of [math]\displaystyle{ {2n \choose n} }[/math] is never very big. In fact, we can guarantee that those powers are quite small - much smaller than 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 [math]\displaystyle{ p \leq n }[/math], the product can't possibly be as big as [math]\displaystyle{ {2n \choose n} }[/math]. And that means that there must be primes in the range [math]\displaystyle{ n }[/math] to [math]\displaystyle{ 2n }[/math] which appear to the prime factorization.

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 [math]\displaystyle{ n }[/math], due to Chebyshev.

{Lemma (Chebyshev bound): For integers [math]\displaystyle{ n \geq 2 }[/math], [math]\displaystyle{ \prod_{p \leq n} p \leq 4^n }[/math], where the product is over all primes [math]\displaystyle{ p }[/math] less than or equal to [math]\displaystyle{ n }[/math].

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 [math]\displaystyle{ 4^n }[/math]. Although it's not needed for a proof of Bertrand's postulate, there is insight to be gained in expressing this idea in a simple quantitative way. Observe that if [math]\displaystyle{ \pi(n) }[/math] is the number of primes less than or equal to [math]\displaystyle{ n }[/math], then [math]\displaystyle{ \pi(n)! \leq \prod_{p \leq n} p }[/math], simply because the [math]\displaystyle{ k }[/math]th prime must be at least [math]\displaystyle{ k }[/math]. Combining this observation with Chebyshev's bound gives [math]\displaystyle{ \pi(n)! \leq 4^n }[/math]. Taking logarithms of both sides, and applying Stirling's approximation, we see that up to constant factors and small corrections, we have [math]\displaystyle{ \pi(n) \ln \pi(n) \leq n }[/math]. This, in turn, implies that, up to constant factors and small corrections, [math]\displaystyle{ \pi(n) \leq n \ln \ln n / \ln n }[/math]. Roughly speaking, the prime numbers are at most logarithmically dense in the positive integers. In fact, the prime number theorem tells us that [math]\displaystyle{ \pi(n) \approx n / \ln n }[/math], as [math]\displaystyle{ n }[/math] becomes large.

Proof of Chebyshev's bound: We will induct on [math]\displaystyle{ n }[/math]. The case when [math]\displaystyle{ n=2 }[/math] is obviously true. Furthermore, if we assume the result when [math]\displaystyle{ n }[/math] is odd, it follows immediately for [math]\displaystyle{ n+1 }[/math], since the left-hand side is not affected by incrementing [math]\displaystyle{ n }[/math]. So we can suppose [math]\displaystyle{ n = 2m }[/math] is even and try to prove the result for [math]\displaystyle{ 2m+1 }[/math]. What we'll aim to show is that:

[math]\displaystyle{ (*) \prod_{m+1 \lt p \leq 2m+1} p \leq 4^m }[/math]

If we can prove this, then multiplying by the inequality [math]\displaystyle{ \prod_{p \leq m+1} p \leq 4^{m+1} }[/math] (which is true by the inductive hypothesis) will give us the desired result. To prove (*), note that every prime [math]\displaystyle{ p }[/math] satisfying [math]\displaystyle{ m+1 \lt p \leq 2m+1 }[/math] must divide [math]\displaystyle{ {2m+1 \choose m} }[/math], since [math]\displaystyle{ p }[/math] 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 [math]\displaystyle{ {2m+1 \choose m} }[/math], and so we have

[math]\displaystyle{ \prod_{m+1 \lt p \leq 2m+1} p \leq {2m+1 \choose m}. }[/math]

The proof is completed by noting that [math]\displaystyle{ {2m+1 \choose m} }[/math] appears twice in the binomial expansion of [math]\displaystyle{ (1+1)^{2m+1} }[/math], and thus [math]\displaystyle{ {2m+1 \choose m} \leq 4^m }[/math]. QED

There are two main ideas in this proof, 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.,

[math]\displaystyle{ \prod_{m+1 \lt p \leq 2m+1} p \leq {2m+1 \choose m}. }[/math]

The second is that there should be a relationship between combinatorial coefficients like [math]\displaystyle{ {2m+1 \choose m} }[/math] and exponentials with fixed bases, e.g., [math]\displaystyle{ {2m+1 \choose m} \leq 4^m }[/math]. 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 [math]\displaystyle{ {2n \choose n} }[/math], telling us that [math]\displaystyle{ {2n \choose n} }[/math] 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 complictae the statement of the lemma, they are trivial consequences of the proof of the main statement in the lemma.

Lemma: Let [math]\displaystyle{ p }[/math] be a prime, and define [math]\displaystyle{ r(p,n) }[/math] to be the largest number such that [math]\displaystyle{ p^{r(p,n)} }[/math] divides [math]\displaystyle{ {2n \choose n} }[/math]. Then [math]\displaystyle{ p^{r(p,n)} \leq 2n }[/math]. There are two special cases where we can make stronger statements: (1) when [math]\displaystyle{ p \geq \sqrt{n} }[/math], then [math]\displaystyle{ r(p,n) }[/math] is [math]\displaystyle{ 1 }[/math] or [math]\displaystyle{ 0 }[/math]; (2) when [math]\displaystyle{ 2n/3 \lt p \leq n }[/math], then [math]\displaystyle{ r(p,n) = 0 }[/math].

This lemma contains within it the essential insight underlying Bertrand's postulate, and that we explained earlier: because we can guarantee that the powers are low, [math]\displaystyle{ {2n \choose n} }[/math] must have many prime factors, and a careful accounting will show that we simply don't have enough if one of them isn't in the range [math]\displaystyle{ n \lt p \lt 2n }[/math]. The Chebyshev bound will be used to show that.

Proof: To prove the lemma, first note that the prime power of [math]\displaystyle{ p }[/math] in the factorization of [math]\displaystyle{ n! }[/math] is given by [math]\displaystyle{ \sum_{j=1}^{\infty} \lfloor n / p^j \rfloor }[/math]. As a result, [math]\displaystyle{ r(p,n) = \sum_{j=1}^\infty ( \lfloor 2n / p^j \rfloor - 2 \lfloor n / p^j \rfloor) }[/math]. All terms in this sum are either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math], and they are always [math]\displaystyle{ 0 }[/math] when [math]\displaystyle{ j \geq \log_p (2n) }[/math], whence [math]\displaystyle{ r(p,n) \leq \log_p (2n) }[/math], which gives the main result.

In the special case of (1), [math]\displaystyle{ p \geq \sqrt{n} }[/math], simply observe that all but the first term in the sum vanishes, and so [math]\displaystyle{ r(p,n) = \lfloor 2n/ p \rfloor - 2 \lfloor n/p \rfloor }[/math], which is either zero or one, according to whether [math]\displaystyle{ \lfloor 2n/p \rfloor }[/math] is even or odd.

In the special case of (2), [math]\displaystyle{ 2n/3 \lt p \leq n }[/math], observe again that only the first term in the sum is vanishing, [math]\displaystyle{ r(p,n) = \lfloor 2n/p \rfloor - 2 \lfloor n/p \rfloor }[/math]. But in this case [math]\displaystyle{ \lfloor 2n/p \rfloor }[/math] is guaranteed to be [math]\displaystyle{ 2 }[/math] (even), and so [math]\displaystyle{ r(p,n) = 0 }[/math]. QED

The proof of Bertrand's postulate is now straightforward.

Proof of Bertrand's postulate: For a contradiction, suppose there are no primes satisfying [math]\displaystyle{ n \lt p \lt 2n }[/math]. In light of case (2) of the last lemma, we can assume that all the prime factors in [math]\displaystyle{ {2n \choose n} }[/math] satisfy [math]\displaystyle{ p \leq 2n/3 }[/math]. We split the prime factorizing of [math]\displaystyle{ {2n \choose n} }[/math] up into the cases where [math]\displaystyle{ p \lt \sqrt{n} }[/math] and where [math]\displaystyle{ \sqrt{n} \leq p \leq 2n/3 }[/math]. Applying the last lemma we obtain:

[math]\displaystyle{ {2n \choose n} \leq \prod_{p \lt \sqrt{n}} (2n) \prod_{\sqrt{n} \leq p \leq 2n/3} p }[/math]

We can bound the first product by noting that there are no more than [math]\displaystyle{ \sqrt{n} }[/math] primes of size less than [math]\displaystyle{ \sqrt{n} }[/math], and bound the second product using Chebyshev's bound:

[math]\displaystyle{ {2n \choose n} \leq (2n)^{\sqrt n} 4^{2n/3}. }[/math]

Proof still needs to be completed.