Bertrand's postulate - Revision history

WikiSysop: Added final part of proof, corrected many small errors

2009-08-18T13:59:56Z

Added final part of proof, corrected many small errors

WikiSysop at 15:01, 14 August 2009

2009-08-14T15:01:14Z

← Older revision		Revision as of 08:01, 14 August 2009
Line 11:		Line 11:
	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.		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>.''		'''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 [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.

WikiSysop: Improved overview, more details of proof added

2009-08-14T14:05:38Z

Improved overview, more details of proof added

Show changes

WikiSysop at 00:18, 12 August 2009

2009-08-12T00:18:42Z

← Older revision		Revision as of 17:18, 11 August 2009
Line 1:		Line 1:
	Despite ~~it's~~ 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>.

WikiSysop at 00:08, 12 August 2009

2009-08-12T00:08:35Z

← Older revision		Revision as of 17:08, 11 August 2009
Line 7:		Line 7:
	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.		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.		Our proof of Bertrand's postulate starts with a result of independent interest, due to Chebyshev.

	'''Lemma (Chebyshev bound):''' For integers <math>n \geq 2</math>,		'''Lemma (Chebyshev bound):''' For integers <math>n \geq 2</math>,

WikiSysop: Added lemma showing that prime powers are not large in combinatorial coefficients

2009-08-12T00:07:57Z

Added lemma showing that prime powers are not large in combinatorial coefficients

← Older revision		Revision as of 17:07, 11 August 2009
Line 26:		Line 26:

	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.,

			<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.

			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.

			'''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>.

			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:''' 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'''

			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 now have all the elements in place to make a proof of Bertrand's postulate straightforward.

			'''Proof of Bertrand's postulate:''' To be added: the proof is not difficult, given the ideas above, but is a bit detailed and tedious.

WikiSysop: Added proof of Chebyshev bound

2009-08-12T00:04:18Z

Added proof of Chebyshev bound

← Older revision		Revision as of 17:04, 11 August 2009
Line 16:		Line 16:

	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:''' 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>

			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 < 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 < 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'''

WikiSysop: Added a brief discussion of the Chebyshev bound

2009-08-12T00:02:21Z

Added a brief discussion of the Chebyshev bound

← Older revision		Revision as of 17:02, 11 August 2009
Line 15:		Line 15:
	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.
	[~~TBC~~]

WikiSysop: Added segue to proof, and statement of Chebyshev bound

2009-08-11T23:57:54Z

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.

Teorth: 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 ...

2009-08-06T17:35:47Z

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 ...

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 claim is a consequence of the prime number theorem, although more elementary proofs are available.

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.