Difference between revisions of "Bertrand's postulate"

From Polymath1Wiki
Jump to: navigation, search
(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 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
+
Despite it's name, Bertrand's postulate is actually a theorem rather than a postulate:
  
For large N, the claim is a consequence of the prime number theorem, although more elementary proofs are available.
+
'''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]n \geq 2[/math], there is a prime [math]p[/math] satisfying [math]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]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]