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.