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

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 ([3]) 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 and Attributions

• 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.