Bertrand's postulate

Despite it's 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 the postulate for 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.

This result 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 proof of Bertrand's postulate starts with a result independent interest, 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: We will prove Chebyshev's bound by inducting 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