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"

(→‎Connection with Riemann zeta function)
m (proofreading)
Line 1: Line 1:
 
{{stub}}
 
{{stub}}
 
==Introduction==
 
==Introduction==
−
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
+
The aim of this article is to present the proof of the '''prime number theorem''', which 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
  
 
<math>\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.</math>
 
<math>\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.</math>
Line 14: Line 14:
 
====Lemma 1====
 
====Lemma 1====
 
For every positive integer <math>n</math>, we have
 
For every positive integer <math>n</math>, we have
−
<math>\prod_{p\le n}p\le 4^n</math>
+
<math>\prod_{p\le n}p\le 4^n</math>.
  
 
====Proof of Lemma 1====
 
====Proof of Lemma 1====
Line 39: Line 39:
 
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>.
 
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.  
+
Now, let us turn to elementary lower bounds. They are 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 and may be unable to go through the entire proof yet.  
 
===Lower bound for the product of primes===
 
===Lower bound for the product of primes===
 
====Lemma 3====
 
====Lemma 3====
Line 47: Line 47:
 
The idea is again to investigate the [[prime factorization]] of  
 
The idea is again to investigate the [[prime factorization]] of  
 
<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).
 
<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).
−
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>.
+
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>.
 
Hence  
 
Hence  
  
Line 59: Line 59:
 
====Proof of Lemma 2====
 
====Proof of Lemma 2====
 
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>.  
 
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 left hand side does not exceed <math>\pi(n)\ln n</math> whence the lemma.
  
 
----
 
----
 
We haven't proved the prime number theorem yet, but we showed that  
 
We haven't proved the prime number theorem yet, but we showed that  
 
<math>\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}</math>
 
<math>\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}</math>
−
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.
+
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.
  
 
==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)=\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>  
+
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>.
Line 77: Line 77:
  
 
<math>\psi(x)\le \pi(x)\ln x\le  \frac 1{\alpha}\psi(x)+
 
<math>\psi(x)\le \pi(x)\ln x\le  \frac 1{\alpha}\psi(x)+
−
x^\alpha\ln x</math>.</math>
+
x^\alpha\ln x</math>.
 
   
 
   
 
Assume now that we know that <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>.
 
Assume now that we know that <math>\lim_{x\to+\infty}\frac{\psi(x)}{x}=1</math>.
Line 93: Line 93:
 
=s\int_{1}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}</math>
 
=s\int_{1}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}</math>
  
−
if <math>\Re s>1</math>
+
if <math>\Re s>1</math>.
  
 
Let now <math>\xi(t)=\frac{\psi(e^t)}{e^t}-1</math>. Then, making the change of variable <math>x=e^t</math> in the last integral, we get
 
Let now <math>\xi(t)=\frac{\psi(e^t)}{e^t}-1</math>. Then, making the change of variable <math>x=e^t</math> in the last integral, we get
Line 100: Line 100:
 
for all <math>s</math> with <math>\Re s>1</math>.
 
for all <math>s</math> with <math>\Re s>1</math>.
  
−
Since the <math>\zeta</math>-function has a simple pole at <math>s=1</math> and no zeroes on the line <math>\Re s=1</math>, the right hand side represents a function [[analytic]] in some domain containing the closed half-plane <math>\{s\in\mathbb C\,:\,\Re s\ge 1\}</math>
+
Since the <math>\zeta</math>-function has a simple pole at <math>s=1</math> and no zeroes on the line <math>\Re s=1</math>, the right hand side represents a function [[analytic]] in some domain containing the closed half-plane <math>\{s\in\mathbb C\,:\,\Re s\ge 1\}</math>.
  
 
==End of proof==
 
==End of proof==

Revision as of 14:41, 6 July 2006

This article is a stub. Help us out by expanding it.

Introduction

The aim of this article is to present the proof of the prime number theorem, which says that the number $\pi(n)$ of primes not exceeding $n$ is approximately $\frac n{\ln n}$, or, more precisely, that

$\lim_{n\to\infty}\frac {\pi(n)\ln n}{n}=1.$

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 ${2m\choose m}=\frac{(2m)!}{(m!)^2}$ is divisible by all primes $p$ satisfying $m<p\le 2m$. Indeed, every such prime appears in the numerator $(2m)!$ and does not appear in the denominator $(m!)^2$. Thus, $\prod_{m<p\le 2m}p\le {2m\choose m}\le 2^{2m}$ (from now on, $p$ will always stand for a prime number, so, to shorten the notation, we will not explicitly write "$p$ is prime" in the descriptions of sum and product ranges). Similarly, considering ${2m+1\choose m}=\frac{(2m+1)!}{m!(m+1)!}$, we see that $\prod_{m+1<p\le 2m+1}p\le {2m+1\choose m}\le 2^{2m}$ (the last inequality holds because ${2m+1\choose m}={2m+1\choose m+1}$ and ${2m+1\choose m}+{2m+1\choose m+1}\le 2^{2m+1}$). Now we are ready to prove the

Upper bound for the product of primes

Lemma 1

For every positive integer $n$, we have $\prod_{p\le n}p\le 4^n$.

Proof of Lemma 1

Induction on $n$. The base $n=1$ is obvious. Suppose now that the statement holds for all numbers strictly less than $n$. If $n=2m$ is even, then

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

If $n=2m+1$ is odd, then

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

From this lemma we can easily derive the

Upper bound for the number of primes

Lemma 2

$\pi(n)\le 4\frac n{\ln n}$ for large $n$

Proof of Lemma 2

Rewrite the inequality of Lemma 1 as $\sum_{p\le n}\ln p\le n\ln 4$. It follows that $\frac 12\ln n(\pi(n)-\pi(\sqrt n))\le \sum_{\sqrt n<p<n}\ln p\le n\ln 4$. But then $\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}$ for large $n$.

Now, let us turn to elementary lower bounds. They are 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 and may be unable to go through the entire proof yet.

Lower bound for the product of primes

Lemma 3

$\prod_{p\le n}p\ge \frac{2^{n}}{(n+1)\cdot n^{\sqrt{n}}}$.

Proof of Lemma 3

The idea is again to investigate the prime factorization of ${n\choose \lfloor \frac n2 \rfloor}$. We shall give the proof for odd $n=2m+1$ (the case of even $n$ is similar). Recall that the power in which a prime number $p$ appears in the prime factorization of $\ell!$ equals $\left\lfloor \frac \ell{p}\right\rfloor+\left\lfloor \frac \ell{p^2}\right\rfloor+\left\lfloor \frac \ell{p^3}\right\rfloor+\dots$ (see factorial for the proof). Therefore, the power in which $p$ appears in the prime factorization of ${n\choose m}$ equals $\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)$. Note that each term in the last sum does not exceed $1$ and the number of non-zero terms does not exceed $\left\lfloor {\log_p n}\right\rfloor$, which is $1$ for all $\sqrt n<p\le n$. Hence

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

On the other hand, ${n\choose m}$ is the largest of the $n+1$ binomial coefficients whose sum is $2^n$. Thus, ${n\choose m}\ge \frac{2^n}{(n+1)}$ whence the estimate of the lemma.

Lower bound for the number of primes

Lemma 4

$\pi(n)\ge \frac 12\,\frac n{\ln n}$ for large $n$

Proof of Lemma 2

Rewrite the inequality of Lemma 3 as $\sum_{p\le n}\ln p\ge n\ln 2-\ln(n+1)-\sqrt n\,\ln n > \frac 12 n$ for large $n$. The left hand side does not exceed $\pi(n)\ln n$ whence the lemma.

We haven't proved the prime number theorem yet, but we showed that $\frac 12\,\frac n{\ln n}\le \pi(n)\le 4\,\frac n{\ln n}$ for all sufficiently large $n$. 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 $n$, define $\Lambda(n)=\ln p$ if $n$ is a pure positive integer power of a prime $p$ and $\Lambda(n)=0$ otherwise (so $\Lambda(2)=\Lambda(4)=\Lambda(8)=\dots=\ln 2$, $\Lambda(3)=\Lambda(9)=\Lambda(27)=\dots=\ln 3$ and so on.) Let $\psi(x)=\sum_{n\le x}\Lambda(n)$

Lemma 5

The prime number theorem is equivalent to $\lim_{x\to+\infty}\frac{\psi(x)}{x}=1$.

Proof of Lemma 5

Note that for $x\ge 1$, we have $\psi(x)=\sum_{p\le x}\lfloor \log_p x\rfloor\ln p$. Since $\lfloor \log_p x\rfloor\ln p\le \ln x$, we immediately get $\psi(x)\le \pi(x)\ln x$. Let now $\alpha<1$. For $x^\alpha<p\le x$, we have $\ln p\ge \alpha \ln x$ and, therefore, $\psi(x)\ge \sum_{x^\alpha<p\le x}\ln p\ge \alpha[\pi(x)-\pi(x^\alpha)]\ln x$, which can be rewritten as $\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$. Thus,

$\psi(x)\le \pi(x)\ln x\le \frac 1{\alpha}\psi(x)+ x^\alpha\ln x$.

Assume now that we know that $\lim_{x\to+\infty}\frac{\psi(x)}{x}=1$. Dividing by $x$ and passing to the limit as $x\to+\infty$, we get

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

Since it is true for all $\alpha<1$, we conclude that $\lim_{x\to+\infty}\frac{\pi(x)\ln x}{x}=1$. 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 $\zeta$-function as the Euler product $\zeta(s)=\prod_p (1-p^{-s})^{-1}$ and take minus logarithmic derivative of both sides. We'll get the formula

$-\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_1^\infty \frac{d\psi(x)}{x^s} =s\int_{1}^\infty\frac{\psi(x)}{x^s}\,\frac{dx}{x}$

if $\Re s>1$.

Let now $\xi(t)=\frac{\psi(e^t)}{e^t}-1$. Then, making the change of variable $x=e^t$ in the last integral, we get

$\int_{0}^\infty \xi(t)e^{-(s-1)t}\,dt=-\frac{\zeta'(s)}{s\zeta(s)}-\frac 1{s-1}$ for all $s$ with $\Re s>1$.

Since the $\zeta$-function has a simple pole at $s=1$ and no zeroes on the line $\Re s=1$, the right hand side represents a function analytic in some domain containing the closed half-plane $\{s\in\mathbb C\,:\,\Re s\ge 1\}$.

End of proof

By the Chebyshev's estimates, we have $-1\le\xi(t)\le 3$ for large $t$, so $\xi(t)$ is bounded and we can apply Newman's Tauberian Theorem and conclude that $\int_0^\infty \xi(t)\,dt$ converges.

Now note that $\xi(t)$ cannot decrease fast. More precisely,

$\xi(t')-\xi(t) =\frac{\psi(e^{t'})}{e^{t'}}-\frac{\psi(e^{t})}{e^{t}}\ge \frac{\psi(e^{t})}{e^{t'}}-\frac{\psi(e^{t})}{e^{t}} =\frac{\psi(e^{t})}{e^{t}}(e^{t-t'}-1)\ge -\frac{\psi(e^{t})}{e^{t}}(t'-t)\ge -C(t'-t)$

for all $t'>t$ with some absolute constant $C<+\infty$. The last step is to show that, together with convergence of the integral $\int_0^\infty \xi(t)\,dt$, this condition implies that $\xi(t)\to 0$ as $\displaystyle t\to +\infty$.

To be continued

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