Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Prime Number Theorem"
(→‎The Bounded Integral)
 
(11 intermediate revisions by 7 users not shown)
Line 1: Line 1:
−
{{stub}}
+
The '''Prime Number Theorem''' (PNT) is one of the most
−
==Introduction==
+
celebrated results in [[analytic number theory]].  Indeed, it is
−
The aim of this article is to present the proof of the '''prime number theorem''' that says that the number <math>\pi(n)</math> of [[prime]]s not exceeding <math>n</math> is approximately <math>\frac n{\ln n}</math> or, more precisely, that
+
possibly the most famous major result in all of number theory, with
 +
the exception of [[Fermat's Last Theorem]].  (Fortunately, the proof
 +
is easier, though still non-trivial!)  It gives an
 +
asymptotic formula for the distribution of the [[prime number]]s;
 +
specifically, it states that the functions <math>\pi(x)</math> and <math>x/\log x</math>
 +
are [[asymptotically equivalent]], where <math>\pi(x)</math> is the number
 +
of primes less than or equal to <math>x</math>.  In other words, it states
 +
that
 +
<cmath> \lim_{x\to \infty} \frac{\pi(x) \log x}{x} = 1 . </cmath>
  
−
<math>\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.</math>
+
== History ==
  
−
Unfortunately, all known proofs of the prime number theorem are quite involved and require knowledge of some college level material.
+
=== First Conjectures ===
  
−
We shall start with some elementary observations due to Chebyshev.
+
Gauss conjectured the theorem as early as 1793, in terms of the
−
==Chebyshev's estimates==
+
[[logarithmic integral]], which is asymptotically equivalent
−
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
+
to <math>x / \log x</math>. Legendre conjectured in 1798 that for some
−
<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
+
constants <math>A</math> and <math>B</math>,
−
===Upper bound for the product of primes===
+
<cmath> \pi(x) \sim \frac{x}{A \log x - B} . </cmath>
−
====Lemma 1====
+
In 1808 he refined his conjecture to
−
For every positive integer <math>n</math>, we have
+
<cmath> \pi(x) = \frac{x}{\log x - A(x)} , </cmath>
−
<math>\prod_{p\le n}p\le 4^n</math>
+
with <math>A(x)</math> tending to some constant number around 1.08366.
 +
(In fact, <math>A(x)</math> does not seem to tend to this value, but its
 +
actual asymptotic behavior is apparently unknown.)
  
−
====Proof of Lemma 1====
+
=== Early Results ===
−
[[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
+
In 1850, Chebyshev proved that for sufficiently large <math>x</math>,
−
4^m 2^{2m}=4^{2m}=4^n.
+
there existed reals <math>A, B</math> such that
−
</math>
+
<cmath> A < \frac{\pi(x) \log x}{x} < B , </cmath>
 +
and he was able to give
 +
<cmath> A = \frac{\log 2}{2} + \frac{\log 3}{3} + \frac{\log 5}{5}
 +
- \frac{\log 30}{30} \approx 0.921292 , </cmath>
 +
and <math>B = \frac{6A}{5} \approx 1.10555</math>.
  
−
If <math>n=2m+1</math> is odd, then
+
In 1859, Riemann established the relation between the distribution
 +
of the zeros of the [[Riemann zeta function]] and the distribution
 +
of the prime numbers; in this same paper, he posed the
 +
[[Riemann Hypothesis]], namely that the zeta function's nontrivial
 +
zeros all lie on the line <math>\Re z = 1/2</math>.  To this day,
 +
it remains unsolved.
  
−
<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
+
In 1892, Sylvester was able to improve Chebyshev's bounds
−
4^{m+1} 2^{2m}=4^{2m+1}=4^n.
+
with <math>A = .956</math>, <math>B=1.045</math>.  However, his methods did not
−
</math>
+
seem likely to yield better bounds.
−
----
 
−
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====
+
=== Proof and Refinement ===
−
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.
 
−
===Lower bound for the product of primes===
 
−
====Lemma 3====
 
−
<math>\prod_{p\le n}p\ge \frac{2^{n}}{(n+1)\cdot n^{\sqrt{n}}}</math>.
 
  
−
====Proof of Lemma 3====
+
Finally, in 1896, Jacques Hadamard and Charles-Jean de la
−
The idea is again to investigate the [[prime factorization]] of
+
ValÎée Poussin independently proved that the zeta function
−
<math>{n\choose \lfloor \frac n2 \rfloor}</math>. We shall give the proof for odd <math>n=2m+1</math> (the case of even <math>n</math> is similar). Recall that the power in which a prime number <math>p</math> appears in the prime factorization of <math>\ell!</math> equals <math>\left\lfloor \frac \ell{p}\right\rfloor+\left\lfloor \frac \ell{p^2}\right\rfloor+\left\lfloor \frac \ell{p^3}\right\rfloor+\dots</math> (see [[factorial]] for the proof).
+
has no zeros on the line <math>\Re s = 1</math>, and from this deduced
−
Therefore, the power in which <math>p</math> appears in the prime factorization of <math>{n\choose m}</math> equals <math>\sum_{k\ge 1}\left(\left\lfloor \frac n{p^k}\right\rfloor-\left\lfloor \frac m{p^k}\right\rfloor-\left\lfloor \frac {m+1}{p^k}\right\rfloor\right)</math> Note that each term in the last sum does not exceed <math>1</math> and the number of non-zero terms does not exceed <math>\left\lfloor {\log_p n}\right\rfloor</math>, which is <math>1</math> for all <math>\sqrt n<p\le n</math>.
+
the prime number theorem.  Their proofs were somewhat long;
−
Hence
+
[http://archive.numdam.org/ARCHIVE/BSMF/BSMF_1896__24_/BSMF_1896__24__199_1/BSMF_1896__24__199_1.pdf Hadamard's paper]
 +
was some 20 pages long.  De la Vallée Poussin's proof that
 +
<math>\zeta(1+ri)</math> has no zeros was about 25 pages long; Hadamard's
 +
proof was essentially the modern version, though de la Vallée
 +
Poussin and Mertens later simplified it.  The proof that this
 +
statement implied the prime number theorem remained long for
 +
some time.
  
−
<math>{n\choose m}\le \left(\prod_{\sqrt n<p\le n}p\right)\cdot\left(\prod_{p\le \sqrt n}p^{\lfloor\log_p n\rfloor}\right)\le \left(\prod_{p\le n}p\right)\cdot n^{\pi(\sqrt n)}\le n^{\sqrt n}\cdot \prod_{p\le n}p</math>.
+
In 1948, Alte Selberg and Paul Erd&#337;s simultaneously
 +
found "elementary" proofs of the prime number theorem.  Unfortunately,
 +
these proofs are still much longer than the shortest proofs
 +
of today that use complex analysis.
  
−
On the other hand, <math>{n\choose m}</math> is the largest of the <math>n+1</math> binomial coefficients whose sum is <math>2^n</math>. Thus, <math>{n\choose m}\ge \frac{2^n}{(n+1)}</math> whence the estimate of the lemma.
+
Finally, in 1980, D.J. Newman found a
−
===Lower bound for the number of primes===
+
[[Newman's Tauberian Theorem | theorem]] with a short proof
−
====Lemma 4====
+
that provided a much simpler link between the zeta function
−
<math>\pi(n)\ge \frac 12\,\frac n{\ln n}</math> for large <math>n</math>
+
and the prime number theorem. This is essentially the proof
 +
given here.
  
−
====Proof of Lemma 2====
+
== Outline ==
−
Rewrite the inequality of Lemma 3 as <math>\sum_{p\le n}\ln p\ge n\ln 2-\ln(n+1)-\sqrt n\,\ln n > \frac 12 n</math> for large <math>n</math>.
 
−
But the left hand side does not exceed <math>\pi(n)\ln n</math> whence the lemma.
 
  
−
----
+
The major results are the fact that the Riemann zeta function
−
We haven't proved the prime number theorem yet, but we showed that  
+
has no zeros on the line <math>\Re s = 1</math>, and the Tauberian theorem
−
<math>\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}</math>
+
due to Newman. The rest of the theorem's proof is comparatively
−
for all sufficiently large <math>n</math>. 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.
+
straightforward, though still non-trivial.  We do not prove
 +
those results in this article, but instead refer to their
 +
proofs [[Riemann zeta function#Zeros of the Zeta Function| here]]
 +
and [[Newman's Tauberian Theorem]].
  
−
==Von Mangoldt function and reformulation of the prime number theorem==
+
== Proof ==
  
−
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>
+
We use the [[Riemann zeta function]], which is defined as
−
====Lemma 5====
+
<cmath> \zeta(s) = \sum_{n\ge 1} \frac{1}{n^s} =  
−
The prime number theorem is equivalent to <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>.
+
\prod_{p \text{ prime}} ( 1 - p^{-s} )^{-1} . </cmath>
−
====Proof of Lemma 5====
+
This function has an analytic continuation to the entire
−
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)+
+
complex plane except <math>s= 1</math>, where it has a simple pole of
−
\pi(x^\alpha)\ln x\le \frac 1{\alpha}\psi(x)+
+
residue 1.
−
x^\alpha\ln x</math>. Thus,
 
  
−
<math>\psi(x)\le \pi(x)\ln x\le  \frac 1{\alpha}\psi(x)+
+
We define
−
x^\alpha\ln x</math>.</math>  
+
<cmath> \phi(s) = \sum_{p} \frac{\log p}{p^s} . </cmath>
−
+
As discussed [[Riemann zeta function#Zeros of the Zeta Function | here]],
−
Assume now that we know that <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>.
+
the function <math>\phi(s)</math> extends to the set <math>\Re s > 1/2</math> by the
−
Dividing by <math>x</math> and passing to the limit as <math>x\to+\infty</math>, we get
+
relation
 +
<cmath> \phi(s) = - \frac{\zeta'(s)}{\zeta(s)} - \sum_p \frac{\log p}{
 +
p^s (p^s- 1)} . </cmath>
  
−
<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>
+
Thus we may define the function
 +
<cmath> g(z) = \frac{\phi(z+1)}{z+1} - \frac{1}{z} . </cmath>
 +
Since
 +
[[Riemann_zeta_function#Zeros_of_the_Zeta_Function| <math>\zeta(s)</math> has no zeros on the line <math>\Re s =1</math>]],
 +
the function <math>g(z)</math> is holomorphic on the set <math>\Re z \ge 0</math>.
  
−
Since it is true for all <math>\alpha<1</math>, we conclude that
+
=== The Bounded Integral ===
−
<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]]==
+
'''Theorem 1.''' The integral
−
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
+
<cmath> \int\limits_1^{\infty} \frac{\vartheta(x) - x}{x^2} dx </cmath>
 +
converges to <math>g(0)</math>.
  
−
<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}
+
''Proof.'' We rely on a
−
=s\int_{0}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}</math>
+
[[Newman's Tauberian Theorem | tauberian theorem due to Newman]].
  
−
valid for <math>\Re s>1</math>.
+
Let <math>x = e^t</math>.  We note that
−
''To be continued''
+
<cmath> \int\limits_1^{e^T} \frac{\vartheta(x) -x}{x^2} dx =
 +
\int\limits_0^T [\vartheta(e^t)e^{-t} - 1 ]dt. </cmath>
 +
 
 +
Now, for <math>\Re s > 1</math>,
 +
<cmath>\begin{align*}
 +
\int\limits_0^\infty [ \vartheta(e^t)e^{-t(s+1)}- e^{-st} ] dt
 +
&= \int\limits_1^\infty \left[ \frac{\vartheta(x)}{x^{s+2}}
 +
- \frac{1}{x^{s+1}} \right] dx \\
 +
&= \sum_{k=0}^{\infty} \int\limits_{p_k}^{p_{k+1}} \frac{\vartheta(x)}
 +
{x^{s+2}} - \frac{1}{s} \\
 +
&= \sum_{k=0}^{\infty} \vartheta(p_k) \int\limits_{p_k}^{p_{k+1}}
 +
\frac{dx}{x^{s+2}} - \frac{1}{s}\\
 +
&= \frac{1}{s+1}\sum_{k=0}^\infty \vartheta(p_k) (1/p_k^{s+1} -
 +
1/p_{k+1}^{s+1}) - \frac{1}{s} .
 +
\end{align*} </cmath>
 +
Now, by the [[Abel Summation Technique]], we have
 +
<cmath> \begin{align*}
 +
\sum_{k=0}^\infty \vartheta(p_k)(1/p_k^{s+1} - 1/p_{k+1}^{s+1})
 +
&= \sum_{k=0}^\infty \sum_{i=0}^k \log p_i (1/p_k^{s+1} - 1/p_{k+1}^{s+1}) \\
 +
&= \sum_{k=0}^{\infty} \frac{\log p_k}{p_k^{s+1}} \\
 +
&= \phi(s+1). \end{align*} </cmath>
 +
Thus for <math>\Re s >1</math> (for the integral),
 +
<cmath> \int_0^\infty [\vartheta(e^t)e^{-t} -1 ]e^{-st} dt =
 +
\frac{\phi(s+1)}{s+1} - \frac{1}{s} = g(s). </cmath>
 +
Now, by a
 +
[[Chebyshev theta function#Estimates of the function | theorem due to Chebyshev]],
 +
the function <math>\vartheta(x)/x - 1</math> is bounded above (by 1).
 +
The function <math>f(t) = \vartheta(e^t)e^{-t} -1</math> thus satisfies
 +
the conditions of [[Newman's Tauberian Theorem]], and the
 +
result follows.  <math>\blacksquare</math>
 +
 
 +
=== End of Proof ===
 +
 
 +
The rest of the theorem is more simple.
 +
 
 +
'''Theorem 2.'''  The functions <math>\vartheta(x)</math> and <math>x</math> are
 +
asymptotically equivalent.
 +
 
 +
''Proof.'' Suppose that <math>\lambda \ge 1</math> is a number
 +
such that there are infinitely many <math>x</math> for which
 +
<math>\vartheta(x) \ge \lambda x </math>.  Then for all such <math>x</math>,
 +
<cmath>
 +
\begin{align*}
 +
\int\limits_x^{\lambda{x}} \frac{\vartheta(t) -t}{t^2} dt&\ge \int\limits_x^{\lambda{x}} \frac{\lambda x - t}{t^2}dt \\
 +
&= \lambda x \left( \frac{1}{x} - \frac{1}{\lambda x} \right)- \left(\log (\lambda x) - \log x\right) \\
 +
&= \lambda -1 - \log \lambda .
 +
\end{align*}
 +
</cmath>
 +
Now, <math>d(x-1 - \log x)/dx = 1 - 1/x</math>; it follows that
 +
<cmath> \lambda - 1 - \log \lambda \ge 0 , </cmath>
 +
with equality exactly when <math>\lambda =1</math>.  But by theorem 1,
 +
this quantity must equal 0 in absolute value, so <math>\lambda = 1</math>.
 +
 
 +
Analogously, suppose that <math>\lambda \le 1</math> is a number
 +
such that there are infinitely many <math>x</math> for which
 +
<math>\vartheta(x) \le \lambda x</math>. Then for any such <math>x</math>,
 +
<cmath>
 +
\begin{align*}
 +
\int\limits_{\lambda x}^x \frac{\vartheta{x} - t}{t^2}dt
 +
\le \int\limits_{\lambda x}^x \frac{\lambda x -t}{t^2}dt
 +
&= \lambda x \left( \frac{1}{x} - \frac{1}{\lambda x} \right)
 +
- ( \log x - \log(\lambda x) ) \\
 +
&= 1 - \lambda + \log \lambda \le 0.
 +
\end{align*}
 +
</cmath>
 +
Again, by theorem 1, this quantity must equal zero in absolute
 +
value; it follows that <math>\lambda = 1</math>.
 +
 
 +
If follows that <math>\limsup \vartheta(x)/x = \liminf \vartheta(x)/x =1</math>.
 +
<math>\blacksquare</math>
 +
 
 +
'''Theorem 3 (Prime Number Theorem).''' The functions <math>\pi(x)\log x</math>
 +
and <math>x</math> are asymptotically equivalent.
 +
 
 +
''Proof.''  We note that
 +
<cmath> \vartheta(x) = \sum_{p \le x} \log p \le \sum_{p\le x} \log x
 +
= \pi(x) \log x . </cmath>
 +
Since <math>\vartheta(x) \sim x</math>, it follows that
 +
<cmath> \liminf \frac{\pi(x) \log x}{x} \ge 1. </cmath>
 +
 
 +
On the other hand, for any <math>\epsilon > 0</math>,
 +
<cmath>\begin{align*}
 +
\vartheta(x) = \sum_{p\le x} \log p \ge
 +
\sum_{x^{1-\epsilon} \le p \le x} \log p
 +
&\ge \sum_{x^{1-\epsilon}\le p \le x} (1-\epsilon) \log x \\
 +
&\ge (1-\epsilon) \log x ( \pi(x) - x^{1-\epsilon} ) ,
 +
\end{align*}
 +
</cmath>
 +
so
 +
<cmath> \pi(x) \log x \le \frac{\vartheta(x)}{1-\epsilon} + x^{1-\epsilon}\log x
 +
= x \left( \frac{\vartheta(x)}{(1-\epsilon)x} +
 +
\frac{\log x}{x^\epsilon} \right) . </cmath>
 +
Again, since <math>\vartheta(x) \sim x</math>, it follows that for
 +
any <math>\epsilon > 0</math>,
 +
<cmath> \limsup \frac{\pi(x) \log x}{x} \le \limsup
 +
\left(\frac{1}{1-\epsilon} + \frac{\log x}{x^\epsilon} \right)
 +
= \frac{1}{1 -\epsilon} . </cmath>
 +
Thus
 +
<cmath> \limsup \frac{\pi(x)\log x}{x} \le 1 .</cmath>
 +
Therefore
 +
<cmath> \lim_{x\to \infty} \frac{\pi(x)\log x}{x} = 1. \qquad  \blacksquare </cmath>
 +
 
 +
== Bibliography ==
 +
 
 +
* Koch, Helmut (trans. David Kramer), ''Number Theory: Algebraic Numbers and Functions'', AMS Graduate Studies in Mathematics 2000, ISBN 0-8218-2054-0.
 +
* [http://mathdl.maa.org/images/upload_library/22/Chauvenet/Zagier.pdf Newman's modern proof], as given by Don Zagier in ''The American Mathematical Monthly'' in 1997.
 +
* [http://www.math.oregonstate.edu/~flahive/Winter2009/newmanPNT.pdf Newman's original proof], from ''The American Mathematical Monthly'' 1980
 +
* [http://www.ift.uni.wroc.pl/~mwolf/Selberg.pdf Seltberg's elementary proof]
 +
* [http://www.pnas.org/content/35/7/374.full.pdf Erd&#337;s's elementary proof]
 +
* [http://archive.numdam.org/ARCHIVE/BSMF/BSMF_1896__24_/BSMF_1896__24__199_1/BSMF_1896__24__199_1.pdf Hadamard's 1896 paper]
 +
* [http://oregonstate.edu/~peterseb/misc/docs/pnt2.pdf Prime number theorem notes], containing historical discussion
 +
* [http://www.math.columbia.edu/~goldfeld/ErdosSelbergDispute.pdf A discussion] of the elementary proofs of the theorem by Selberg and Erd&#337;s
 +
 
 +
== See also ==
 +
 
 +
* [[Riemann zeta function]]
 +
* [[Newman's Tauberian Theorem]]
 +
* [[Riemann Hypothesis]]
 +
* [[Bertrand's Postulate]]
 +
 
 +
[[Category:Number theory]]
 +
[[Category:Analytic number theory]]
 +
[[Category:Complex analysis]]

Latest revision as of 18:52, 21 October 2023

The Prime Number Theorem (PNT) is one of the most celebrated results in analytic number theory. Indeed, it is possibly the most famous major result in all of number theory, with the exception of Fermat's Last Theorem. (Fortunately, the proof is easier, though still non-trivial!) It gives an asymptotic formula for the distribution of the prime numbers; specifically, it states that the functions $\pi(x)$ and $x/\log x$ are asymptotically equivalent, where $\pi(x)$ is the number of primes less than or equal to $x$. In other words, it states that \[\lim_{x\to \infty} \frac{\pi(x) \log x}{x} = 1 .\]

History

First Conjectures

Gauss conjectured the theorem as early as 1793, in terms of the logarithmic integral, which is asymptotically equivalent to $x / \log x$. Legendre conjectured in 1798 that for some constants $A$ and $B$, \[\pi(x) \sim \frac{x}{A \log x - B} .\] In 1808 he refined his conjecture to \[\pi(x) = \frac{x}{\log x - A(x)} ,\] with $A(x)$ tending to some constant number around 1.08366. (In fact, $A(x)$ does not seem to tend to this value, but its actual asymptotic behavior is apparently unknown.)

Early Results

In 1850, Chebyshev proved that for sufficiently large $x$, there existed reals $A, B$ such that \[A < \frac{\pi(x) \log x}{x} < B ,\] and he was able to give \[A = \frac{\log 2}{2} + \frac{\log 3}{3} + \frac{\log 5}{5} - \frac{\log 30}{30} \approx 0.921292 ,\] and $B = \frac{6A}{5} \approx 1.10555$.

In 1859, Riemann established the relation between the distribution of the zeros of the Riemann zeta function and the distribution of the prime numbers; in this same paper, he posed the Riemann Hypothesis, namely that the zeta function's nontrivial zeros all lie on the line $\Re z = 1/2$. To this day, it remains unsolved.

In 1892, Sylvester was able to improve Chebyshev's bounds with $A = .956$, $B=1.045$. However, his methods did not seem likely to yield better bounds.

Proof and Refinement

Finally, in 1896, Jacques Hadamard and Charles-Jean de la ValÎée Poussin independently proved that the zeta function has no zeros on the line $\Re s = 1$, and from this deduced the prime number theorem. Their proofs were somewhat long; Hadamard's paper was some 20 pages long. De la Vallée Poussin's proof that $\zeta(1+ri)$ has no zeros was about 25 pages long; Hadamard's proof was essentially the modern version, though de la Vallée Poussin and Mertens later simplified it. The proof that this statement implied the prime number theorem remained long for some time.

In 1948, Alte Selberg and Paul Erdős simultaneously found "elementary" proofs of the prime number theorem. Unfortunately, these proofs are still much longer than the shortest proofs of today that use complex analysis.

Finally, in 1980, D.J. Newman found a theorem with a short proof that provided a much simpler link between the zeta function and the prime number theorem. This is essentially the proof given here.

Outline

The major results are the fact that the Riemann zeta function has no zeros on the line $\Re s = 1$, and the Tauberian theorem due to Newman. The rest of the theorem's proof is comparatively straightforward, though still non-trivial. We do not prove those results in this article, but instead refer to their proofs here and Newman's Tauberian Theorem.

Proof

We use the Riemann zeta function, which is defined as \[\zeta(s) = \sum_{n\ge 1} \frac{1}{n^s} = \prod_{p \text{ prime}} ( 1 - p^{-s} )^{-1} .\] This function has an analytic continuation to the entire complex plane except $s= 1$, where it has a simple pole of residue 1.

We define \[\phi(s) = \sum_{p} \frac{\log p}{p^s} .\] As discussed here, the function $\phi(s)$ extends to the set $\Re s > 1/2$ by the relation \[\phi(s) = - \frac{\zeta'(s)}{\zeta(s)} - \sum_p \frac{\log p}{ p^s (p^s- 1)} .\]

Thus we may define the function \[g(z) = \frac{\phi(z+1)}{z+1} - \frac{1}{z} .\] Since $\zeta(s)$ has no zeros on the line $\Re s =1$, the function $g(z)$ is holomorphic on the set $\Re z \ge 0$.

The Bounded Integral

Theorem 1. The integral \[\int\limits_1^{\infty} \frac{\vartheta(x) - x}{x^2} dx\] converges to $g(0)$.

Proof. We rely on a tauberian theorem due to Newman.

Let $x = e^t$. We note that \[\int\limits_1^{e^T} \frac{\vartheta(x) -x}{x^2} dx = \int\limits_0^T [\vartheta(e^t)e^{-t} - 1 ]dt.\]

Now, for $\Re s > 1$, \begin{align*} \int\limits_0^\infty [ \vartheta(e^t)e^{-t(s+1)}- e^{-st} ] dt &= \int\limits_1^\infty \left[ \frac{\vartheta(x)}{x^{s+2}} - \frac{1}{x^{s+1}} \right] dx \\ &= \sum_{k=0}^{\infty} \int\limits_{p_k}^{p_{k+1}} \frac{\vartheta(x)} {x^{s+2}} - \frac{1}{s} \\ &= \sum_{k=0}^{\infty} \vartheta(p_k) \int\limits_{p_k}^{p_{k+1}} \frac{dx}{x^{s+2}} - \frac{1}{s}\\ &= \frac{1}{s+1}\sum_{k=0}^\infty \vartheta(p_k) (1/p_k^{s+1} - 1/p_{k+1}^{s+1}) - \frac{1}{s} . \end{align*} Now, by the Abel Summation Technique, we have \begin{align*} \sum_{k=0}^\infty \vartheta(p_k)(1/p_k^{s+1} - 1/p_{k+1}^{s+1}) &= \sum_{k=0}^\infty \sum_{i=0}^k \log p_i (1/p_k^{s+1} - 1/p_{k+1}^{s+1}) \\ &= \sum_{k=0}^{\infty} \frac{\log p_k}{p_k^{s+1}} \\ &= \phi(s+1). \end{align*} Thus for $\Re s >1$ (for the integral), \[\int_0^\infty [\vartheta(e^t)e^{-t} -1 ]e^{-st} dt = \frac{\phi(s+1)}{s+1} - \frac{1}{s} = g(s).\] Now, by a theorem due to Chebyshev, the function $\vartheta(x)/x - 1$ is bounded above (by 1). The function $f(t) = \vartheta(e^t)e^{-t} -1$ thus satisfies the conditions of Newman's Tauberian Theorem, and the result follows. $\blacksquare$

End of Proof

The rest of the theorem is more simple.

Theorem 2. The functions $\vartheta(x)$ and $x$ are asymptotically equivalent.

Proof. Suppose that $\lambda \ge 1$ is a number such that there are infinitely many $x$ for which $\vartheta(x) \ge \lambda x$. Then for all such $x$, \begin{align*} \int\limits_x^{\lambda{x}} \frac{\vartheta(t) -t}{t^2} dt&\ge \int\limits_x^{\lambda{x}} \frac{\lambda x - t}{t^2}dt \\ &= \lambda x \left( \frac{1}{x} - \frac{1}{\lambda x} \right)- \left(\log (\lambda x) - \log x\right) \\ &= \lambda -1 - \log \lambda . \end{align*} Now, $d(x-1 - \log x)/dx = 1 - 1/x$; it follows that \[\lambda - 1 - \log \lambda \ge 0 ,\] with equality exactly when $\lambda =1$. But by theorem 1, this quantity must equal 0 in absolute value, so $\lambda = 1$.

Analogously, suppose that $\lambda \le 1$ is a number such that there are infinitely many $x$ for which $\vartheta(x) \le \lambda x$. Then for any such $x$, \begin{align*} \int\limits_{\lambda x}^x \frac{\vartheta{x} - t}{t^2}dt \le \int\limits_{\lambda x}^x \frac{\lambda x -t}{t^2}dt &= \lambda x \left( \frac{1}{x} - \frac{1}{\lambda x} \right) - ( \log x - \log(\lambda x) ) \\ &= 1 - \lambda + \log \lambda \le 0. \end{align*} Again, by theorem 1, this quantity must equal zero in absolute value; it follows that $\lambda = 1$.

If follows that $\limsup \vartheta(x)/x = \liminf \vartheta(x)/x =1$. $\blacksquare$

Theorem 3 (Prime Number Theorem). The functions $\pi(x)\log x$ and $x$ are asymptotically equivalent.

Proof. We note that \[\vartheta(x) = \sum_{p \le x} \log p \le \sum_{p\le x} \log x = \pi(x) \log x .\] Since $\vartheta(x) \sim x$, it follows that \[\liminf \frac{\pi(x) \log x}{x} \ge 1.\]

On the other hand, for any $\epsilon > 0$, \begin{align*} \vartheta(x) = \sum_{p\le x} \log p \ge \sum_{x^{1-\epsilon} \le p \le x} \log p &\ge \sum_{x^{1-\epsilon}\le p \le x} (1-\epsilon) \log x \\ &\ge (1-\epsilon) \log x ( \pi(x) - x^{1-\epsilon} ) , \end{align*} so \[\pi(x) \log x \le \frac{\vartheta(x)}{1-\epsilon} + x^{1-\epsilon}\log x = x \left( \frac{\vartheta(x)}{(1-\epsilon)x} + \frac{\log x}{x^\epsilon} \right) .\] Again, since $\vartheta(x) \sim x$, it follows that for any $\epsilon > 0$, \[\limsup \frac{\pi(x) \log x}{x} \le \limsup \left(\frac{1}{1-\epsilon} + \frac{\log x}{x^\epsilon} \right) = \frac{1}{1 -\epsilon} .\] Thus \[\limsup \frac{\pi(x)\log x}{x} \le 1 .\] Therefore \[\lim_{x\to \infty} \frac{\pi(x)\log x}{x} = 1. \qquad \blacksquare\]

Bibliography

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Prime_Number_Theorem&oldid=199951"