$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 7.3: Getting Closer to the Proof of the Prime Number Theorem

• • Contributed by Wissam Raji
• Associate Professor and the Chairman (Mathematics) at American University of Beirut
$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

We know prove a theorem that is related to the defined functions above. Keep in mind that the prime number theorem is given as follows: $\lim_{x \rightarrow \infty} \frac{\pi(x)logx}{x}=1.$ We now state equivalent forms of the prime number theorem.

The following relations are equivalent $\label{3} \lim_{x\rightarrow \infty}\frac{\pi(x)\log x}{x}=1$ $\label{4} \lim_{x\rightarrow \infty} \frac{\theta(x)}{x}= 1$ $\label{5} \lim_{x\rightarrow \infty} \frac{\psi(x)}{x}= 1.$

We have proved in Theorem 86 that $$(\ref{4})$$ and $$(\ref{5})$$ are equivalent, so if we show that $$(\ref{3})$$ and $$(\ref{4})$$ are equivalent, the proof will follow. Notice that using the integral representations of the functions in Theorem 85, we obtain $\frac{\theta(x)}{x}=\frac{\pi(x)\log x}{x}-\frac{1}{x}\int_ {2}^{x}\frac{\pi(t)}{t}dt$ and $\frac{\pi(x)\log x}{x}=\frac{\theta(x)}{x}+\frac{\log x}{x}\int_{2}^x\frac{\theta(t)}{t\log^2t}dt.$ Now to prove that () implies $$(\ref{4})$$, we need to prove that $\lim_{x\rightarrow \infty}\frac{1}{x}\int_ {2}^{x}\frac{\pi(t)}{t}dt=0.$ Notice also that $$(\ref{3})$$ implies that $$\frac{\pi(t)}{t}=O\left(\frac{1}{\log t}\right)$$ for $$t\geq 2$$ and thus we have $\frac{1}{x}\int_ {2}^{x}\frac{\pi(t)}{t}dt=O\left(\frac{1}{x}\int_2^x\frac{dt}{\log t}\right)$ Now once you show that (Exercise 1) $\int_2^x\frac{dt}{\log t}\leq \frac{\sqrt{x}}{\log 2}+\frac{x-\sqrt{x}}{\log \sqrt{x}},$ then $$(\ref{3})$$ implies $$(\ref{4})$$ will follow. We still need to show that $$(\ref{4})$$ implies $$(\ref{3})$$ and thus we have to show that $\lim_{x\rightarrow \infty}\frac{\log x}{x}\int_{2}^x \frac{\theta(t)dt}{t\log^2t}=0.$ Notice that $$\theta(x)=O(x)$$ and hence $\frac{\log x}{x}\int_{2}^x \frac{\theta(t)dt}{t\log^2t}=O\left(\frac{\log x}{x}\int_2^x\frac{dt}{\log^2t}\right).$ Now once again we show that (Exercise 2) $\int_2^x\frac{dt}{\log^2t}\leq \frac{\sqrt{x}}{\log^22}+\frac{x-\sqrt{x}}{\log^2\sqrt{x}}$ then $$(\ref{4})$$ implies $$(\ref{3})$$ will follow.

Define $l_1=\liminf_{x\rightarrow \infty}\frac{\pi(x)}{x/log x}, \ \ \ \ \ L_1=\limsup_{x\rightarrow \infty}\frac{\pi(x)}{x/log x},$ $l_2=\liminf_{x\rightarrow \infty}\frac{\theta(x)}{x}, \ \ \ \ \ L_2=\limsup_{x\rightarrow \infty}\frac{\theta(x)}{x},$ and $l_3=\liminf_{x\rightarrow \infty}\frac{\psi(x)}{x}, \ \ \ \ \ L_3=\limsup_{x\rightarrow \infty}\frac{\psi(x)}{x},$ then $$l_1=l_2=l_3$$ and $$L_1=L_2=L_3$$.

Notice that $\psi(x)=\theta(x)+\theta(x^{1/2})+ \theta(x^{1/3})+...\theta(x^{1/m})\geq \theta(x)$ where $$m\leq log_2x$$

Also, $\psi(x)=\sum_{p\leq x}\left[\frac{\log x}{\log p}\right]\log p\leq \sum_{p\leq x}\frac{\log x}{\log p} \log p= \log x\pi(x).$ Thus we have $\theta(x)\leq \psi(x)\leq \pi(x)\log x$ As a result, we have $\frac{\theta(x)}{x}\leq \frac{\psi(x)}{x}\leq \frac{\pi(x)}{x/\log x}$ and we get that $$L_2\leq L_3\leq L_1$$. We still need to prove that $$L_1 \leq L_2$$.

Let $$\alpha$$ be a real number where $$0<\alpha<1$$, we have \begin{aligned} \theta(x)&=&\sum_{p\leq x}\log p\geq \sum_{x^{\alpha}\leq p\leq x}\log p\\ &>& \sum_{x^{\alpha}\leq p\leq x}\alpha \log x \ \ \ (\log p>\alpha \log x)\\ &=&\alpha log x\{\pi(x)-\pi(x^{\alpha})\}\end{aligned} However, $$\pi(x^{\alpha})\leq x^{\alpha}$$. Hence $\theta(x)>\alpha \log x\{\pi(x)-x^{\alpha}\}$ As a result, $\frac{\theta(x)}{x} > \frac{\alpha \pi(x)}{x/ \log x}- \alpha x^{\alpha-1}\log x$ Since $$\lim_{x\rightarrow \infty}\alpha \log x/x^{1-\alpha}=0$$, then $L_2\geq \alpha \limsup_{x\rightarrow \infty}\frac{\pi(x)}{x/\log x}$ As a result, we get that $L_2\geq \alpha L_1$ As $$\alpha \rightarrow 1$$, we get $$L_2\geq L_1$$.

Proving that $$l_1=l_2=l_3$$ is left as an exercise.

We now present an inequality due to Chebyshev about $$\pi(x)$$.

There exist constants $$a<A$$ such that $a\frac{x}{\log x}<\pi(x)<A\frac{x}{\log x}$ for sufficiently large $$x$$.

Put $l=\liminf_{x\rightarrow \infty}\frac{\pi(x)}{x/\log x}, \ \ \ \ \ L=\limsup_{x\rightarrow \infty}\frac{\pi(x)}{x/\log x},$ It will be sufficient to prove that $$L\leq 4 \log 2$$ and $$l\geq \log 2$$. Thus by Theorem 2, we have to prove that $\label{1} \limsup_{x\rightarrow \infty}\frac{\theta(x)}{x}\leq 4 \log 2$ and $\label{2} \liminf_{x\rightarrow \infty}\frac{\psi(x)}{x}\geq \log 2$ To prove ($$\ref{1}$$), notice that $N=C(2n,n)=\frac{(n+1)(n+2)...(n+n)}{n!}<2^{2n}<(2n+1)N$ Suppose now that $$p$$ is a prime such that $$n<p<2n$$ and hence $$p\mid N$$. As a result, we have $$N \geq \prod_{n<p<2n}p$$. We get $N\geq \theta(2n)-\theta(n).$ Since $$N<2^{2n}$$, we get that $$\theta(2n)-\theta(n)<2n\log 2$$. Put $$n=1,2,2^2,...,2^{m-1}$$ where $$m$$ is a positive integer. We get that $\theta(2^m)<2^{m-1}\log 2.$ Let $$x>1$$ and choose $$m$$ such that $$2^{m-1}\leq x\leq 2^m$$, we get that $\theta(x)\leq \theta(2^m)\leq 2^{m+1}\log 2 \leq 4x\log 2$ and we get $$(\ref{1})$$ for all $$x$$.

We now prove $$(\ref{2})$$. Notice that by Lemma 9, we have that the highest power of a prime $$p$$ dividing $$N=\frac{(2n)!}{(n!)^2}$$ is given by $s_p=\sum_{i=1 1}^{\mu_p}\left\{\left[\frac{2n}{p^i}\right]-2\left[\frac{n}{p^i}\right]\right\}.$ where $$\mu_p=\left[\frac{\log 2n}{\log p}\right]$$. Thus we have $$N=\prod_{p\leq 2n}p^{s_p}$$. If $$x$$ is a positive integer then $[2x]-2[x]<2,$ It means that $$[2x]-2[x]$$ is $$0$$ or $$1$$. Thus $$s_p\leq \mu_p$$ and we get $N\leq \prod_{p\leq e2n}p^{\mu_p}.$ Notice as well that $\psi(2n)=\sum_{p\leq 2n}\left[\frac{\log 2n}{\log p}\right]\log p=\sum_{p\leq 2n}\mu_p \log p.$ Hence we get $\log N \leq \psi(2n).$ Using the fact that $$2^{2n}<(2n+1)N$$, we can see that $\psi(2n)>2n \log 2-\log (2n+1).$ Let $$x>2$$ and put $$n=\left[\frac{x}{2}\right]\geq 1$$. Thus $$\frac{x}{2}-1<n<\frac{x}{2}$$ and we get $$2n \leq x$$. So we get \begin{aligned} \psi(x)&\geq &\psi(2n)>2n \log 2- \log (2n+1)\\&>&(x-2)\log 2- \log (x+1).\end{aligned} As a result, we get $\liminf_{x\rightarrow \infty}\frac{\psi(x)}{x}\geq \log 2.$

Exercises

1. Show that $$l_1=l_2=l_3$$ in Theorem 88.

2. Show that $\int_2^x\frac{dt}{\log t}\leq \frac{\sqrt{x}}{\log 2}+\frac{x-\sqrt{x}}{\log \sqrt{x}},$

3. Show that $\int_2^x\frac{dt}{\log^2t}\leq \frac{\sqrt{x}}{\log^22}+\frac{x-\sqrt{x}}{\log^2\sqrt{x}}$

4. Show that $N=C(2n,n)=\frac{(n+1)(n+2)...(n+n)}{n!}<2^{2n}<(2n+1)N$

5. Show that $$\frac{2^{2n}}{2\sqrt{n}}<N=C(2n,n)< \frac{2^{2n}}{\sqrt{2n}}$$.
Hint: For one side of the inequality, write $\frac{N}{2^n}=\frac{(2n)!}{2^{2n}(n!)^2}=\frac{1.3.5....(2n-1)}{2.4.6....(2n)}.\frac{2.4.6.....(2n)}{2.4.6...(2n)},$ then show that $1>(2n+1).\frac{N^2}{2^{4n}}>2n.\frac{N^2}{2^{4n}}.$ The other side of the inequality will follow with similar arithmetic techniques as the first inequality.

## Contributors

• Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.