Difference between revisions of "Prime Number Theorem"
Line 68: | Line 68: | ||
==Von Mangoldt function and reformulation of the prime number theorem== | ==Von Mangoldt function and reformulation of the prime number theorem== | ||
− | For a positive integer <math>n</math>, define <math>\Lambda(n)=\ | + | For a positive integer <math>n</math>, define <math>\Lambda(n)=\ln p</math> if <math>n</math> is a pure positive integer power of a prime <math>p</math> and <math>\Lambda(n)=0</math> otherwise (so <math>\Lambda(2)=\Lambda(4)=\Lambda(8)=\dots=\ln 2</math>, <math>\Lambda(3)=\Lambda(9)=\Lambda(27)=\dots=\ln 3</math> and so on. Let <math>\psi(x)=\sum_{n\le x}\Lambda(n)</math> |
====Lemma 5==== | ====Lemma 5==== | ||
The prime number theorem is equivalent to <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>. | The prime number theorem is equivalent to <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>. | ||
====Proof of Lemma 5==== | ====Proof of Lemma 5==== | ||
+ | Note that for <math>x\ge 1</math>, we have <math>\psi(x)=\sum_{p\le x}\lfloor \log_p x\rfloor\ln p</math>. Since <math>\lfloor \log_p x\rfloor\ln p\le \ln x</math>, we immediately get <math>\psi(x)\le \pi(x)\ln x</math>. Let now <math>\alpha<1</math>. For <math>x^\alpha<p\le x</math>, we have <math>\ln p\ge \alpha \ln x</math> and, therefore, <math>\psi(x)\ge \sum_{x^\alpha<p\le x}\ln p\ge \alpha[\pi(x)-\pi(x^\alpha)]\ln x</math>, which can be rewritten as <math>\pi(x)\ln x\le \frac 1{\alpha}\psi(x)+ | ||
+ | \pi(x^\alpha)\ln x\le \frac 1{\alpha}\psi(x)+ | ||
+ | x^\alpha\ln x</math>. Thus, | ||
+ | <math>\psi(x)\le \pi(x)\ln x\le \frac 1{\alpha}\psi(x)+ | ||
+ | x^\alpha\ln x</math>.</math> | ||
+ | Assume now that we know that <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>. | ||
+ | Dividing by <math>x</math> and passing to the limit as <math>x\to+\infty</math>, we get | ||
+ | <math>1\le\liminf_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le \limsup_{x\to+\infty}\frac{\pi(x)\ln x}{x}\le\frac 1\alpha\,.</math> | ||
+ | Since it is true for all <math>\alpha<1</math>, we conclude that | ||
+ | <math>\lim_{x\to+\infty}\frac{\pi(x)\ln x}{x}=1</math>. This proves one half of the statement of the lemma (and this is the only half we'll need). The proof of the other half is similar and left to the reader as an exercise. | ||
+ | |||
+ | ==Connection with Riemann [[zeta function]]== | ||
+ | Write <math>\zeta</math>-function as the Euler product <math>\zeta(s)=\prod_p (1-p^{-s})^{-1}</math> and take minus logarithmic derivative of both sides. We'll get the formula | ||
+ | |||
+ | <math>-\frac{\zeta'(s)}{\zeta(s)}=\sum_p\frac {p^{-s}\ln p}{1-p^{-s}}=\sum_p\sum_{k\ge 1}\frac{\ln p}{p^{ks}}=\sum_{n\ge 1}\frac {\Lambda(n)}{n^s}=\int_0^\infty \frac{d\psi(x)}{x^s} | ||
+ | =s\int_{0}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}</math> | ||
+ | |||
+ | valid for <math>\Re s>1</math>. | ||
''To be continued'' | ''To be continued'' |
Revision as of 09:24, 29 June 2006
This article is a stub. Help us out by expanding it.
Contents
- 1 Introduction
- 2 Chebyshev's estimates
- 3 Von Mangoldt function and reformulation of the prime number theorem
- 4 Connection with Riemann zeta function
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.
Lower bound for the product of primes
Lemma 3
.
Proof of Lemma 3
The idea is again to investigate the prime factorization of
. We shall give the proof for odd
(the case of even
is similar). Recall that the power in which a prime number
appears in the prime factorization of
equals
(see factorial for the proof).
Therefore, the power in which
appears in the prime factorization of
equals
Note that each term in the last sum does not exceed
and the number of non-zero terms does not exceed
, which is
for all
.
Hence
.
On the other hand, is the largest of the
binomial coefficients whose sum is
. Thus,
whence the estimate of the lemma.
Lower bound for the number of primes
Lemma 4
for large
Proof of Lemma 2
Rewrite the inequality of Lemma 3 as for large
.
But the left hand side does not exceed
whence the lemma.
We haven't proved the prime number theorem yet, but we showed that
for all sufficiently large
. For many readers it is probably a good idea to stop here and to proceed to Bertrand's postulate. The material below this point requires good knowledge of analysis and is, probably, accessible to college students only.
Von Mangoldt function and reformulation of the prime number theorem
For a positive integer , define
if
is a pure positive integer power of a prime
and
otherwise (so
,
and so on. Let
Lemma 5
The prime number theorem is equivalent to .
Proof of Lemma 5
Note that for , we have
. Since
, we immediately get
. Let now
. For
, we have
and, therefore,
, which can be rewritten as
. Thus,
.</math>
Assume now that we know that .
Dividing by
and passing to the limit as
, we get
Since it is true for all , we conclude that
. This proves one half of the statement of the lemma (and this is the only half we'll need). The proof of the other half is similar and left to the reader as an exercise.
Connection with Riemann zeta function
Write -function as the Euler product
and take minus logarithmic derivative of both sides. We'll get the formula
valid for .
To be continued