Difference between revisions of "Prime Number Theorem"
(→Chebyshev's estimates) |
|||
Line 9: | Line 9: | ||
We shall start with some elementary observations due to Chebyshev. | We shall start with some elementary observations due to Chebyshev. | ||
==Chebyshev's estimates== | ==Chebyshev's estimates== | ||
− | The key observation is that <math>{2m\choose m}=\frac{(2m)!}{(m!)^2}</math> is divisible by all primes <math>p</math> satisfying <math>m<p\le 2m</math>. Indeed, every such prime appears in the numerator <math>(2m)!</math> and does not appear in the denominator <math>(m!)^2</math>. Thus, <math>\prod_{p\ | + | The key observation is that <math>{2m\choose m}=\frac{(2m)!}{(m!)^2}</math> is divisible by all primes <math>p</math> satisfying <math>m<p\le 2m</math>. Indeed, every such prime appears in the numerator <math>(2m)!</math> and does not appear in the denominator <math>(m!)^2</math>. Thus, <math>\prod_{m<p\le 2m}p\le {2m\choose m}\le 2^{2m}</math> (from now on, <math>p</math> will always stand for a prime number, so, to shorten the notation, we will not explicitly write "<math>p</math> is prime" in the descriptions of sum and product ranges). Similarly, considering <math>{2m+1\choose m}=\frac{(2m+1)!}{m!(m+1)!}</math>, we see that |
+ | <math>\prod_{m+1<p\le 2m+1}p\le {2m+1\choose m}\le 2^{2m}</math> (the last inequality holds because <math>{2m+1\choose m}={2m+1\choose m+1}</math> and <math>{2m+1\choose m}+{2m+1\choose m+1}\le 2^{2m+1}</math>). Now we are ready to prove the | ||
+ | ===Upper bound for the product of primes=== | ||
+ | ====Lemma 1==== | ||
+ | For every positive integer <math>n</math>, we have | ||
+ | <math>\prod_{p\le n}p\le 4^n</math> | ||
+ | |||
+ | ====Proof of Lemma 1==== | ||
+ | [[Induction]] on <math>n</math>. The base <math>n=1</math> is obvious. Suppose now that the statement holds for all numbers strictly less than <math>n</math>. If <math>n=2m</math> is even, then | ||
+ | |||
+ | <math>\prod_{p\le n}p=\left(\prod_{p\le m}p\right)\cdot \left(\prod_{m<p\le 2m}p\right)\le | ||
+ | 4^m 2^{2m}=4^{2m}=4^n. | ||
+ | </math> | ||
+ | |||
+ | If <math>n=2m+1</math> is odd, then | ||
+ | |||
+ | <math>\prod_{p\le n}p=\left(\prod_{p\le m+1}p\right)\cdot \left(\prod_{m+1<p\le 2m+1}p\right)\le | ||
+ | 4^{m+1} 2^{2m}=4^{2m+1}=4^n. | ||
+ | </math> | ||
+ | ---- | ||
+ | From this lemma we can easily derive the | ||
+ | ===Upper bound for the number of primes=== | ||
+ | ====Lemma 2==== | ||
+ | <math>\pi(n)\le 4\frac n{\ln n}</math> for large <math>n</math> | ||
+ | |||
+ | ====Proof of Lemma 2==== | ||
+ | Rewrite the inequality of Lemma 1 as <math>\sum_{p\le n}\ln p\le n\ln 4</math>. It follows that | ||
+ | <math>\frac 12\ln n(\pi(n)-\pi(\sqrt n))\le \sum_{\sqrt n<p<n}\ln p\le n\ln 4</math>. | ||
+ | But then <math>\pi(n)\le 2\ln 4\frac{n}{\ln n}+\pi(\sqrt n)\le 2\ln 4\,\frac{n}{\ln n}+\sqrt n< 4\frac{n}{\ln n}</math> for large <math>n</math>. | ||
+ | ---- | ||
+ | Now let us turn to elementary lower bounds. They are actually not required for the proof of the prime number theorem outlined below, but they may be of some independent interest, especially to those who haven't taken advanced courses in analysis by this moment and may be unable to go through the entire proof yet. We have already seen that |
Revision as of 10:46, 27 June 2006
This article is a stub. Help us out by expanding it.
Contents
Introduction
The aim of this article is to present the proof of the prime number theorem that says that the number of primes not exceeding is approximately or, more precisely, that
Unfortunately, all known proofs of the prime number theorem are quite involved and require knowledge of some college level material.
We shall start with some elementary observations due to Chebyshev.
Chebyshev's estimates
The key observation is that is divisible by all primes satisfying . Indeed, every such prime appears in the numerator and does not appear in the denominator . Thus, (from now on, will always stand for a prime number, so, to shorten the notation, we will not explicitly write " is prime" in the descriptions of sum and product ranges). Similarly, considering , we see that (the last inequality holds because and ). Now we are ready to prove the
Upper bound for the product of primes
Lemma 1
For every positive integer , we have
Proof of Lemma 1
Induction on . The base is obvious. Suppose now that the statement holds for all numbers strictly less than . If is even, then
If is odd, then
From this lemma we can easily derive the
Upper bound for the number of primes
Lemma 2
for large
Proof of Lemma 2
Rewrite the inequality of Lemma 1 as . It follows that . But then for large .
Now let us turn to elementary lower bounds. They are actually not required for the proof of the prime number theorem outlined below, but they may be of some independent interest, especially to those who haven't taken advanced courses in analysis by this moment and may be unable to go through the entire proof yet. We have already seen that