Bertrand's postulate: Difference between revisions
New page: Bertrand's postulate asserts that for every positive integer N, there is a prime between N and 2N. Despite its name, it is actually a theorem rather than a postulate. For large N, the ... |
Added segue to proof, and statement of Chebyshev bound |
||
| Line 1: | Line 1: | ||
Bertrand's postulate | Despite it's name, Bertrand's postulate is actually a theorem rather than a postulate: | ||
For | '''Theorem (Bertrand's Postulate):''' For every integer <math>n \geq 2</math>, there is a prime <math>p</math> satisfying <math>n < p < 2n</math>. | ||
The relevance of the postulate for the [[finding primes]] problem is that it guarantees the existence of a k-digit prime for any k. Brute force search thus yields a k-digit prime after about <math>O(10^k)</math> steps; this can be considered the "trivial bound" for the problem. | The relevance of the postulate for the [[finding primes]] problem is that it guarantees the existence of a <math>k</math>-digit prime for any <math>k</math>. Brute force search thus yields a <math>k</math>-digit prime after about <math>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>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>n \geq 2</math>, | |||
<math> \prod_{p \leq n} p \leq 4^n, </math> | |||
where the product is over all primes <math>p</math> less than or equal to <math>n</math>. | |||
[TBC] | |||
Revision as of 15:57, 11 August 2009
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].
[TBC]
