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.