Difference between revisions of "Bertrand's postulate"

From Polymath1Wiki
Jump to: navigation, search
(Improved overview, more details of proof added)
Line 1: Line 1:
 
Despite its name, Bertrand's postulate is actually a theorem rather than a postulate:
 
Despite its 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 < p < 2n</math>.
+
'''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 <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.
+
The relevance of Bertrand's postulate to the [http://michaelnielsen.org/polymath1/index.php?title=Finding_primes 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.
+
Bertrand's postulate 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 of independent interest, due to Chebyshev.
+
Our strategy is to analyse the prime factorization of the binomial coefficient <math>{2n \choose n}</math>.  What we'll discover is that for primes <math>p \leq n</math>, the corresponding prime power in the prime factorization of <math>{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>p \leq n</math>, the product can't possibly be as big as <math>{2n \choose n}</math>.  And that means that there must be primes in the range <math>n</math> to <math>2n</math> which appear to the prime factorization.
  
'''Lemma (Chebyshev bound):''' For integers <math>n \geq 2</math>,
+
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>n</math>, due to Chebyshev.
  
<math>   \prod_{p \leq n} p \leq 4^n, </math>
+
{'''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>.''
  
where the product is over all primes <math>p</math> less than or equal to <math>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>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>\pi(n)</math> is the number of primes less than or equal to <math>n</math>, then <math>\pi(n)! \leq \prod_{p \leq n} p</math>, simply because the <math>k</math>th prime must be at least <math>k</math>.  Combining this observation with Chebyshev's bound gives <math>\pi(n)! \leq 4^n</math>. Taking logarithms of both sides, and applying [http://en.wikipedia.org/wiki/Stirling's_approximation Stirling's  approximation], we see that up to constant factors and small corrections, we have <math>\pi(n) \ln \pi(n) \leq n</math>.  This, in turn, implies that, up to constant factors and small corrections, <math>\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 [http://en.wikipedia.org/wiki/Prime_number_theorem prime  number theorem] tells us that <math>\pi(n) \approx n / \ln n</math>, as <math>n</math> becomes large.
  
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>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>\pi(n)</math> is the number of primes less than or equal to <math>n</math>, then <math>\pi(n)! \leq \prod_{p \leq n} p</math>, simply because the <math>k</math>th prime must be at least <math>k</math>.  Combining this observation with Chebyshev's bound gives <math>\pi(n)! \leq 4^n</math>. Taking logarithms of both sides, and applying [http://en.wikipedia.org/wiki/Stirling's_approximation Stirling's approximation], we see that up to constant factors and small corrections, we have <math>  \pi(n) \ln \pi(n) \leq n. </math>  This, in turn, implies that up to constant factors and small corrections, <math>\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 [http://en.wikipedia.org/wiki/Prime_number_theorem prime number theorem] tells us that <math>\pi(n) \approx n / \ln n</math>, as <math>n</math> becomes large.
+
'''Proof of Chebyshev's bound:''' We will induct on <math>n</math>. The case when <math>n=2</math> is obviously true.  Furthermore, if we assume the result when <math>n</math> is odd, it follows immediately for <math>n+1</math>, since the left-hand side is not affected by incrementing <math>n</math>.  So we can suppose <math>n = 2m</math> is even and try to prove the result for <math>2m+1</math>.  What we'll aim to show is that:
 
+
'''Proof:''' We will prove Chebyshev's bound by inducting on <math>n</math>. The case when <math>n=2</math> is obviously true.  Furthermore, if we assume the result when <math>n</math> is odd, it follows immediately for <math>n+1</math>, since the left-hand side is not affected by incrementing <math>n</math>.  So we can suppose <math>n = 2m</math> is even and try to prove the result for <math>2m+1</math>.  What we'll aim to show is that:
+
  
 
<math>  (*) \prod_{m+1 < p \leq 2m+1} p \leq 4^m </math>
 
<math>  (*) \prod_{m+1 < p \leq 2m+1} p \leq 4^m </math>
Line 27: Line 25:
 
The proof is completed by noting that <math>{2m+1 \choose m}</math> appears twice in the binomial expansion of <math>(1+1)^{2m+1}</math>, and thus <math>{2m+1 \choose  m} \leq 4^m</math>.  '''QED'''
 
The proof is completed by noting that <math>{2m+1 \choose m}</math> appears twice in the binomial expansion of <math>(1+1)^{2m+1}</math>, and thus <math>{2m+1 \choose  m} \leq 4^m</math>.  '''QED'''
  
There are two main ideas in this proof, and it's worth dwelling on them briefly; it's perhaps also instructive to spend some time thinking about variants of these ideas, and how that might impact the proof.  The first idea is that there should be a relationship between products of primes and factorials, e.g.,
+
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>  \prod_{m+1 < p \leq 2m+1} p \leq {2m+1 \choose m}. </math>
 
<math>  \prod_{m+1 < p \leq 2m+1} p \leq {2m+1 \choose m}. </math>
  
The second idea is that there should be a relationship between combinatorial coefficients like <math>{2m+1 \choose m}</math> and exponentials with fixed bases, e.g., <math>{2m+1 \choose m} \leq 4^m</math>.  Once these two ideas are firmly in mind, the proof is obvious.
+
The second is that there should be a relationship between combinatorial coefficients like <math>{2m+1 \choose m}</math> and exponentials with fixed bases, e.g., <math>{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>{2n \choose n}</math>, telling us that <math>{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>p</math> be a prime, and define <math>r(p,n)</math> to be  the largest number such that <math>p^{r(p,n)}</math> divides <math>{2n \choose n}</math>.  Then <math>p^{r(p,n)} \leq 2n</math>.  There are two special cases where we can  make stronger statements: (1) when <math>p \geq \sqrt{n}</math>, then <math>r(p,n)</math>  is <math>1</math> or <math>0</math>; (2) when <math>2n/3 < p \leq n</math>, then <math>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>{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>n < p < 2n</math>.  The Chebyshev bound will be used to show that.
 +
 
 +
'''Proof:''' To prove the lemma, first note that the prime power of <math>p</math> in the factorization of <math>n!</math> is given by <math>\sum_{j=1}^{\infty} \lfloor n / p^j \rfloor</math>.  As a result, <math>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>0</math> or <math>1</math>, and they are always <math>0</math> when <math>j \geq \log_p (2n)</math>, whence <math>r(p,n) \leq \log_p (2n)</math>, which gives the main result. 
 +
 
 +
In the special case of (1), <math>p \geq \sqrt{n}</math>, simply observe that all but the first term in the sum vanishes, and so <math>r(p,n) = \lfloor 2n/ p \rfloor - 2 \lfloor n/p \rfloor</math>, which is either zero or one, according to whether <math>\lfloor 2n/p \rfloor</math> is even or odd. 
  
In the light of these comments, it's perhaps not surprising that the idea underlying the proof of Bertrand's postulate is to show that the binomial coefficient <math>{2n \choose n}</math> ''must'' have a prime factor <math>p</math> such that <math>n < p < 2n</math>.  Before we get to that, we'll prove a useful fact about the prime factorization of <math>{2n \choose n}</math>.  In particular, our second lemma tells us that <math>{2n \choose n}</math> has a rather special prime factorization which only involves low powers.
+
In the special case of (2), <math>2n/3 < p \leq n</math>, observe again that only the first term in the sum is vanishing, <math>r(p,n) = \lfloor 2n/p \rfloor - 2 \lfloor n/p \rfloor</math>.  But in this case <math>\lfloor 2n/p \rfloor</math> is guaranteed to be <math>2</math> (even), and so <math>r(p,n) = 0</math>. '''QED'''
  
'''Lemma:''' Let <math>p</math> be a prime, and define <math>r(p,n)</math> to be the largest number such that <math>p^{r(p,n)}</math> divides <math>{2n \choose n}</math>.  Then <math>p^{r(p,n)} \leq 2n</math>.
+
The proof of Bertrand's postulate is now straightforward.
  
This is the essential insight underlying Bertrand's postulate: because we can guarantee that the powers are low, <math>{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>n < p < 2n</math>.
+
'''Proof of Bertrand's postulate:''' For a contradiction, suppose there are no primes satisfying <math>n < p < 2n</math>.  In light of case (2) of the last lemma, we can assume that all the prime factors in <math>{2n   \choose n}</math> satisfy <math>p \leq 2n/3</math>.  We split the prime factorizing of <math>{2n \choose n}</math> up into the cases where <math>p < \sqrt{n}</math> and where <math>\sqrt{n} \leq p \leq 2n/3</math>. Applying the last lemma we obtain:
  
'''Proof:''' To prove this, observe that the prime power of <math>p</math> in the factorization of <math>n!</math> is given by <math>\sum_{j=1}^{\infty} \lfloor n / p^j \rfloor</math>.  As a result, <math>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>0</math> or <math>1</math>, and they are always <math>0</math> when <math>j \geq \log_p (2n)</math>, whence <math>r(p,n) \leq \log_p (2n)</math>, which gives the result. '''QED'''
+
<math>   {2n \choose n} \leq \prod_{p < \sqrt{n}} (2n) \prod_{\sqrt{n} \leq p \leq 2n/3} p </math>
  
As a corollary of the proof of the lemma, we see that when the prime <math>p</math> is sufficiently large, <math>p \geq \sqrt{n}</math>, then only a single term in the sum for <math>r(p,n)</math> survives, <math>r(p,n) = \lfloor 2n / p \rfloor - 2 \lfloor n / p \rfloor</math>.  This corollary perhaps appears somewhat unmotivated now, but will be useful in a moment.
+
We can bound the first product by noting that there are no more than <math>\sqrt{n}</math> primes of size less than <math>\sqrt{n}</math>, and bound the second product using Chebyshev's bound:
  
We now have all the elements in place to make a proof of Bertrand's postulate straightforward.
+
<math>  {2n \choose n} \leq (2n)^{\sqrt n} 4^{2n/3}. </math>
  
'''Proof of Bertrand's postulate:''' To be added: the proof is not difficult, given the ideas above, but is a bit detailed and tedious.
+
'''Proof still needs to be completed.'''

Revision as of 06:05, 14 August 2009

Despite its 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 Bertrand's postulate to 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.

Bertrand's postulate 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 strategy is to analyse the prime factorization of the binomial coefficient [math]{2n \choose n}[/math]. What we'll discover is that for primes [math]p \leq n[/math], the corresponding prime power in the prime factorization of [math]{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]p \leq n[/math], the product can't possibly be as big as [math]{2n \choose n}[/math]. And that means that there must be primes in the range [math]n[/math] to [math]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]n[/math], 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].

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]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]\pi(n)[/math] is the number of primes less than or equal to [math]n[/math], then [math]\pi(n)! \leq \prod_{p \leq n} p[/math], simply because the [math]k[/math]th prime must be at least [math]k[/math]. Combining this observation with Chebyshev's bound gives [math]\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]\pi(n) \ln \pi(n) \leq n[/math]. This, in turn, implies that, up to constant factors and small corrections, [math]\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]\pi(n) \approx n / \ln n[/math], as [math]n[/math] becomes large.

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

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

If we can prove this, then multiplying by the inequality [math]\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]p[/math] satisfying [math]m+1 \lt p \leq 2m+1[/math] must divide [math]{2m+1 \choose m}[/math], since [math]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]{2m+1 \choose m}[/math], and so we have

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

The proof is completed by noting that [math]{2m+1 \choose m}[/math] appears twice in the binomial expansion of [math](1+1)^{2m+1}[/math], and thus [math]{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] \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]{2m+1 \choose m}[/math] and exponentials with fixed bases, e.g., [math]{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]{2n \choose n}[/math], telling us that [math]{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]p[/math] be a prime, and define [math]r(p,n)[/math] to be the largest number such that [math]p^{r(p,n)}[/math] divides [math]{2n \choose n}[/math]. Then [math]p^{r(p,n)} \leq 2n[/math]. There are two special cases where we can make stronger statements: (1) when [math]p \geq \sqrt{n}[/math], then [math]r(p,n)[/math] is [math]1[/math] or [math]0[/math]; (2) when [math]2n/3 \lt p \leq n[/math], then [math]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]{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]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]p[/math] in the factorization of [math]n![/math] is given by [math]\sum_{j=1}^{\infty} \lfloor n / p^j \rfloor[/math]. As a result, [math]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]0[/math] or [math]1[/math], and they are always [math]0[/math] when [math]j \geq \log_p (2n)[/math], whence [math]r(p,n) \leq \log_p (2n)[/math], which gives the main result.

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

In the special case of (2), [math]2n/3 \lt p \leq n[/math], observe again that only the first term in the sum is vanishing, [math]r(p,n) = \lfloor 2n/p \rfloor - 2 \lfloor n/p \rfloor[/math]. But in this case [math]\lfloor 2n/p \rfloor[/math] is guaranteed to be [math]2[/math] (even), and so [math]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]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]{2n \choose n}[/math] satisfy [math]p \leq 2n/3[/math]. We split the prime factorizing of [math]{2n \choose n}[/math] up into the cases where [math]p \lt \sqrt{n}[/math] and where [math]\sqrt{n} \leq p \leq 2n/3[/math]. Applying the last lemma we obtain:

[math] {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]\sqrt{n}[/math] primes of size less than [math]\sqrt{n}[/math], and bound the second product using Chebyshev's bound:

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

Proof still needs to be completed.