Difference between revisions of "Prime Number Theorem"
(→The Bounded Integral) |
|||
(11 intermediate revisions by 7 users not shown) | |||
Line 1: | Line 1: | ||
− | + | 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 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> | ||
− | + | == History == | |
− | + | === First Conjectures === | |
− | + | Gauss conjectured the theorem as early as 1793, in terms of the | |
− | + | [[logarithmic integral]], which is asymptotically equivalent | |
− | + | to <math>x / \log x</math>. Legendre conjectured in 1798 that for some | |
− | <math> | + | constants <math>A</math> and <math>B</math>, |
− | + | <cmath> \pi(x) \sim \frac{x}{A \log x - B} . </cmath> | |
− | + | In 1808 he refined his conjecture to | |
− | + | <cmath> \pi(x) = \frac{x}{\log x - A(x)} , </cmath> | |
− | + | 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.) | ||
− | ==== | + | === Early Results === |
− | |||
− | <math>\ | + | In 1850, Chebyshev proved that for sufficiently large <math>x</math>, |
− | + | 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>. | ||
− | + | 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> | + | In 1892, Sylvester was able to improve Chebyshev's bounds |
− | + | with <math>A = .956</math>, <math>B=1.045</math>. However, his methods did not | |
− | </math> | + | seem likely to yield better bounds. |
− | |||
− | |||
− | |||
− | |||
− | <math> | ||
− | + | === Proof and Refinement === | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | Finally, in 1896, Jacques Hadamard and Charles-Jean de la | |
− | + | ValÎée Poussin independently proved that the zeta function | |
− | <math> | + | has no zeros on the line <math>\Re s = 1</math>, and from this deduced |
− | + | the prime number theorem. Their proofs were somewhat long; | |
− | + | [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. | ||
− | + | 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 | |
− | + | [[Newman's Tauberian Theorem | 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 <math>\Re s = 1</math>, and the Tauberian theorem | |
− | <math>\ | + | 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 [[Riemann zeta function#Zeros of the Zeta Function| here]] | ||
+ | and [[Newman's Tauberian Theorem]]. | ||
− | == | + | == Proof == |
− | + | We use the [[Riemann zeta function]], which is defined as | |
− | + | <cmath> \zeta(s) = \sum_{n\ge 1} \frac{1}{n^s} = | |
− | + | \prod_{p \text{ prime}} ( 1 - p^{-s} )^{-1} . </cmath> | |
− | + | This function has an analytic continuation to the entire | |
− | + | complex plane except <math>s= 1</math>, where it has a simple pole of | |
− | + | residue 1. | |
− | |||
− | < | + | We define |
− | + | <cmath> \phi(s) = \sum_{p} \frac{\log p}{p^s} . </cmath> | |
− | + | As discussed [[Riemann zeta function#Zeros of the Zeta Function | here]], | |
− | + | the function <math>\phi(s)</math> extends to the set <math>\Re s > 1/2</math> by the | |
− | + | relation | |
+ | <cmath> \phi(s) = - \frac{\zeta'(s)}{\zeta(s)} - \sum_p \frac{\log p}{ | ||
+ | p^s (p^s- 1)} . </cmath> | ||
− | < | + | 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>. | ||
− | + | === The Bounded Integral === | |
− | |||
− | + | '''Theorem 1.''' The integral | |
− | + | <cmath> \int\limits_1^{\infty} \frac{\vartheta(x) - x}{x^2} dx </cmath> | |
+ | converges to <math>g(0)</math>. | ||
− | + | ''Proof.'' We rely on a | |
− | + | [[Newman's Tauberian Theorem | tauberian theorem due to Newman]]. | |
− | + | Let <math>x = e^t</math>. We note that | |
− | '' | + | <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ő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ő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 19: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 and
are asymptotically equivalent, where
is the number
of primes less than or equal to
. In other words, it states
that
Contents
History
First Conjectures
Gauss conjectured the theorem as early as 1793, in terms of the
logarithmic integral, which is asymptotically equivalent
to . Legendre conjectured in 1798 that for some
constants
and
,
In 1808 he refined his conjecture to
with
tending to some constant number around 1.08366.
(In fact,
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 ,
there existed reals
such that
and he was able to give
and
.
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 . To this day,
it remains unsolved.
In 1892, Sylvester was able to improve Chebyshev's bounds
with ,
. 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 , 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
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 , 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
This function has an analytic continuation to the entire
complex plane except
, where it has a simple pole of
residue 1.
We define
As discussed here,
the function
extends to the set
by the
relation
Thus we may define the function
Since
has no zeros on the line
,
the function
is holomorphic on the set
.
The Bounded Integral
Theorem 1. The integral
converges to
.
Proof. We rely on a tauberian theorem due to Newman.
Let . We note that
Now, for ,
Now, by the Abel Summation Technique, we have
Thus for
(for the integral),
Now, by a
theorem due to Chebyshev,
the function
is bounded above (by 1).
The function
thus satisfies
the conditions of Newman's Tauberian Theorem, and the
result follows.
End of Proof
The rest of the theorem is more simple.
Theorem 2. The functions and
are
asymptotically equivalent.
Proof. Suppose that is a number
such that there are infinitely many
for which
. Then for all such
,
Now,
; it follows that
with equality exactly when
. But by theorem 1,
this quantity must equal 0 in absolute value, so
.
Analogously, suppose that is a number
such that there are infinitely many
for which
. Then for any such
,
Again, by theorem 1, this quantity must equal zero in absolute
value; it follows that
.
If follows that .
Theorem 3 (Prime Number Theorem). The functions
and
are asymptotically equivalent.
Proof. We note that
Since
, it follows that
On the other hand, for any ,
so
Again, since
, it follows that for
any
,
Thus
Therefore
Bibliography
- Koch, Helmut (trans. David Kramer), Number Theory: Algebraic Numbers and Functions, AMS Graduate Studies in Mathematics 2000, ISBN 0-8218-2054-0.
- Newman's modern proof, as given by Don Zagier in The American Mathematical Monthly in 1997.
- Newman's original proof, from The American Mathematical Monthly 1980
- Seltberg's elementary proof
- Erdős's elementary proof
- Hadamard's 1896 paper
- Prime number theorem notes, containing historical discussion
- A discussion of the elementary proofs of the theorem by Selberg and Erdős