| 1. | Lecture 1 |
| 2. | Lecture 2 |
| 3. | Lecture 3 |
| 4. | Lecture 4 |
| 5. | Lecture 5 |
| 6. | Lecture 6 |
| 7. | Lecture 7 |
| 8. | Lecture 8 |
| 9. | Lecture 9 |
| 10. | Lecture 10 |
| 11. | Lecture 11 |
| 12. | Lecture 12 |
| 13. | Lecture 13 |
Proposition. Let \(x \geqslant 1\) be a real number and \(f, g\) be two arithmetic functions. Then \[\sum_{n \in[x]}(\: f \star g)(n)=\sum_{d \in [x]} f(d) \sum_{k \in [x / d]} g(k).\] Here we use the convention \([x]:=\mathbb Z\cap(0, x]:=\{1, \ldots, \lfloor x\rfloor\}\) for any \(x\in\mathbb R_+\).
Proof.
Observe that \[\begin{aligned} \sum_{n \in[x]}(\: f \star g)(n)=\sum_{n \in [x]} \sum_{d \mid n} f(d) g(n / d)= \sum_{d \in [x]} f(d) \sum_{\substack{n \in [x] \\ d \mid n}} g(n / d). \end{aligned}\]
Making the change of variable \(n=k d\) in the inner sum and noticing that \(n \in [x]\) and \(d \mid n\) is equivalent to \(k \in [x / d]\), we finally obtain \[\begin{aligned} \sum_{n \in[x]}(\: f \star g)(n)=\sum_{d \in [x]} f(d) \sum_{k \in [x / d]} g(k). \qquad\end{aligned}\qquad\blacksquare\]
$$\tag*{$\blacksquare$}$$
Since \(\tau=\mathbf{1} \star \mathbf{1}\), then by the previous proposition and the easy equality \(\lfloor x\rfloor=x+ O(1)\) we obtain \[\sum_{n \in [x]} \tau(n)=\sum_{d \in [x]} \sum_{k \in [x / d]} 1=\sum_{d \in [x]}\bigg\lfloor \frac{x}{d}\bigg\rfloor =x \sum_{d \in [x]} \frac{1}{d}+O(x)=x \log x+O(x).\] We shall see later how to improve on this result.
Since \(\sigma=\mathbf{1} \star {\rm Id}\), then by the previous proposition we have \[\sum_{n \in [x]} \sigma(n)=\sum_{d \in [x]} \sum_{k \in [x / d]} k =\frac{1}{2} \sum_{d \in[x]}\bigg\lfloor \frac{x}{d}\bigg\rfloor\bigg(\bigg\lfloor\frac{x}{d}\bigg\rfloor+1\bigg)\] and using \(\lfloor x\rfloor =x+O(1)\), we obtain \[\sum_{n \in [x]} \sigma(n)=\frac{x^{2}}{2} \sum_{d \in [x]} \frac{1}{d^{2}}+O\bigg(x \sum_{d \in[x]} \frac{1}{d}\bigg).\] Since \(\sum_{d \in [x]} \frac{1}{d^{2}}=\sum_{d=1}^{\infty} \frac{1}{d^{2}}-\sum_{d>x} \frac{1}{d^{2}}=\zeta(2)+O\left(\frac{1}{x}\right)\), we conclude
\[\sum_{n \in [x]} \sigma(n)=\frac{x^{2} \pi^2}{12}+O(x \log x).\]
Since \(\varphi=\mu \star {\rm Id}\), then by the previous proposition we have \[\sum_{n \in [x]} \varphi(n)=\sum_{d \in [x]}\mu(d) \sum_{k \in [x / d]} k =\frac{1}{2} \sum_{d \in[x]}\mu(d)\bigg\lfloor \frac{x}{d}\bigg\rfloor\bigg(\bigg\lfloor\frac{x}{d}\bigg\rfloor+1\bigg)\] and using \(\lfloor x\rfloor =x+O(1)\), we obtain \[\sum_{n \in [x]} \varphi(n)=\frac{x^{2}}{2} \sum_{d \in [x]} \frac{\mu(d)}{d^{2}}+O\bigg(x \sum_{d \in[x]} \frac{1}{d}\bigg).\] Since \(\sum_{d \in [x]} \frac{\mu(d)}{d^{2}}=\sum_{d=1}^{\infty} \frac{\mu(d)}{d^{2}}-\sum_{d>x} \frac{\mu(d)}{d^{2}}=\zeta(2)^{-1}+O\left(\frac{1}{x}\right)\), we conclude
\[\sum_{n \in [x]} \varphi(n)=\frac{3x^{2} }{\pi^2}+O(x \log x).\]
Since \(\mu \star \mathbf{1}=\delta\), by the previous proposition we obtain \[1=\sum_{n \in[x]}(\mu \star \mathbf{1})(n)=\sum_{d \in [x]} \mu(d) \sum_{k \in [x / d]} 1 =\sum_{d \in [x]} \mu(d)\bigg\lfloor\frac{x}{d}\bigg\rfloor,\] which is a very important identity.
Using this identity we obtain that \[N \sum_{n \in [N]} \frac{\mu(n)}{n}=\sum_{n \in [N]} \mu(n)\bigg\lfloor\frac{N}{n}\bigg\rfloor +\sum_{n \in[N]} \mu(n)\bigg\{\frac{N}{n}\bigg\}=1+\sum_{n \in [N-1]} \mu(n)\bigg\{\frac{N}{n}\bigg\}\] so that \[\bigg|\sum_{n \in[N]} \frac{\mu(n)}{n}\bigg| \leqslant \frac{1}{N}\bigg(1+\sum_{n \in[N-1]} \mu(n)\bigg\{\frac{N}{n}\bigg\}\bigg) \leqslant \frac{1+N-1}{N}=1.\]
Proposition 2 (Dirichlet hyperbola principle). Let \(1 \leqslant T \leqslant x\) be real numbers and \(f,g\) be two arithmetic functions. Then \[\begin{aligned} \sum_{n \in [x]}(\: f \star g)(n)= & \sum_{n \in [T]} f(n) \sum_{k \in [x / n]} g(k) +\sum_{k \in [x / T]} g(k) \sum_{n \in [x / k]} f(n) \\ & -\sum_{n \in [T]} f(n) \sum_{k \in [x / T]} g(k) . \end{aligned}\]
Proof. Splitting the sum of the right-hand side of of the proposition gives \[\sum_{n \in [x]}(\: f \star g)(n)=\sum_{d \in [T]} f(d) \sum_{k \in [x / d]} g(k) +\sum_{T<d \leqslant x} f(d) \sum_{k \in [x / d]} g(k),\] and \[\begin{aligned} \sum_{T<d \leqslant x} f(d) \sum_{k \in [x / d]} g(k) & =\sum_{k \in [x / T]} g(k) \sum_{T<d \leqslant x / k} f(d) \\ & =\sum_{k \in [x / T]} g(k)\bigg(\sum_{d \in [x / k]} f(d)-\sum_{d \in [T]} f(d)\bigg). \qquad\end{aligned}\qquad\blacksquare\]$$\tag*{$\blacksquare$}$$
For \(x\in\mathbb R_+\) sufficiently large, we have \[\sum_{n \in [x]} \tau(n)=x(\log x+2 \gamma-1)+O(\sqrt{x}).\]
Proof.
Since \(\tau={\bf 1}\star {\bf
1}\), by the previous proposition with \(T=\sqrt{x}\) and the estimate \(\lfloor x\rfloor=x+O(1)\) we obtain \[\begin{aligned}
\sum_{n \in [x]}
\tau(n)&=2\sum_{m\in[\sqrt{x}]}\bigg\lfloor\frac{x}{m}\bigg\rfloor-\big\lfloor\sqrt{x}\big\rfloor^2\\
& =2 x \sum_{m \in [\sqrt{x}]}
\frac{1}{m}+O(\sqrt{x})-(\sqrt{x}+O(1))^{2} \\
& =2 x\left(\log \sqrt{x}+\gamma+O\big(x^{-1 /
2}\big)\right)-x+O(\sqrt{x}) \\
& =x \log x+x(2 \gamma-1)+O(\sqrt{x}). \qquad\end{aligned}\]
$$\tag*{$\blacksquare$}$$
The von Mangoldt function \(\Lambda\) is defined by \[\Lambda(n):= \begin{cases}\log p, & \text { if } n=p^{k} \text { for some prime } p \text { and } k \in \mathbb{Z}_+, \\ 0, & \text { otherwise }\end{cases}.\]
The first Chebyshev function \(\vartheta\) is defined for \(x \geqslant 2\) by \[\vartheta(x):=\sum_{p \in\mathbb P_{\le x}} \log p,\] while it is convenient to set \(\vartheta(x):=0\) for \(0<x<2\), where \(\mathbb P_{\le x}:=\{p\in\mathbb P: p\le x\}=\mathbb P\cap[0, x]\).
The second Chebyshev function \(\psi\) is defined for \(x \geqslant 2\) by \[\psi(x):=\sum_{n \in[x]} \Lambda(n),\] while it is convenient to set \(\psi(x):=0\) for \(0<x<2\).
The prime counting function \(\pi\) is defined by \[\pi(x):=\sum_{p \in\mathbb P_{\le x}} 1=\#\mathbb P_{\le x},\] while it is convenient to set \(\pi(x):=0\) for \(0<x<2\).
For \(x \geq 2\) we have \[\vartheta(x)=\pi(x) \log x-\int_{2}^{x} \pi(t) \frac{dt}{t},\] and \[\pi(x)=\frac{\vartheta(x)}{\log x}+\int_{2}^{x} \frac{\vartheta(t)}{t \log ^{2} t} d t.\]
Proof.
We have \[\pi(x)=\sum_{p \in \mathbb P_{\le x}} 1=\sum_{1<n \leq x} {\bf 1}_{\mathbb P}(n),\] and \[\vartheta(x)=\sum_{p \in \mathbb P_{\le x}} \log p=\sum_{1<n \leq x} {\bf 1}_{\mathbb P}(n) \log n.\]
If \(x, y\in \mathbb R_+\) with \(\lfloor y\rfloor<\lfloor x\rfloor\), and \(g\in C^1([y, x])\), then we know \[\sum_{y<n \leq x} f(n) g(n)=F(x) g(x)-F(y) g(y)-\int_{y}^{x} F(t) g^{\prime}(t) d t\] where \(F(t):=\sum_{1\le n \leq x} f(n).\)
$$\tag*{$\blacksquare$}$$
Taking \(f(n)={\bf 1}_{\mathbb P}(n)\) and \(g(x)=\log x\) with \(y=1\) we obtain \[\vartheta(x)=\sum_{1<n \leq x} {\bf 1}_{\mathbb P}(n) \log n=\pi(x) \log x-\pi(1) \log 1-\int_{1}^{x} \pi(t)\frac{dt}{t},\] which proves the first identity since \(\pi(t)=0\) for \(t<2\).
Next, let \(f(n)={\bf 1}_{\mathbb P}(n) \log n\) and \(g(x)=1 / \log x\) and write \[\pi(x)=\sum_{3 / 2<n \leq x} f(n) \frac{1}{\log n}, \quad \vartheta(x)=\sum_{1<n \leq x} f(n)\]
Using the summation by parts formula with \(y=3 / 2\) we obtain \[\pi(x)=\frac{\vartheta(x)}{\log x}-\frac{\vartheta(3 / 2)}{\log 3 / 2}+\int_{3 / 2}^{x} \frac{\vartheta(t)}{t \log ^{2} t} d t\] which proves the second identity, since \(\vartheta(t)=0\) if \(t<2\). $$\tag*{$\blacksquare$}$$
For all \(x\in\mathbb R_+\), we have \[\vartheta(x) \leqslant \psi(x) \leqslant \vartheta(x)+\pi(\sqrt{x}) \log x.\]
For all \(x \geqslant 2\) and all \(a>1\), we have \[\frac{\vartheta(x)}{\log x} \leqslant \pi(x) \leqslant \frac{a \vartheta(x)}{\log x}+\pi\big(x^{1 / a}\big).\]
Proof of (i).
One may suppose \(x \geqslant 2\). We first have \[\psi(x)-\vartheta(x)=\sum_{p^{k} \leqslant x} \log p-\sum_{p \leqslant x} \log p =\sum_{p \leqslant \sqrt{x}} \sum_{k=2}^{\lfloor\frac{\log x}{\log p}\rfloor} \log p,\] so that \[\psi(x) \geqslant \vartheta(x).\]
$$\tag*{$\blacksquare$}$$
On the other hand, we have \[\begin{aligned} \psi(x)-\vartheta(x) & =\sum_{p \leqslant \sqrt{x}} \sum_{k=2}^{\lfloor\frac{\log x}{\log p}\rfloor} \log p \leqslant \sum_{p \leqslant \sqrt{x}} \log p\bigg\lfloor\frac{\log x}{\log p}\bigg\rfloor \leqslant \sum_{p \leqslant \sqrt{x}} \log x \\ & =\pi(\sqrt{x}) \log x. \qquad\end{aligned}\qquad\blacksquare\]
Proof of (ii). We have \[\pi(x)=\sum_{p \leqslant x} 1=\sum_{p \leqslant x} \frac{\log p}{\log p} \geqslant \frac{1}{\log x} \sum_{p \leqslant x} \log p=\frac{\vartheta(x)}{\log x}.\]
For \(2 \leqslant T<x\), we also have \[\pi(x)=\sum_{p \leqslant T} 1+\sum_{T<p \leqslant x} 1=\pi(T)+\sum_{T<p \leqslant x} \frac{\log p}{\log p} \leqslant \pi(T)+\frac{\vartheta(x)}{\log T}.\] and the choice of \(T=x^{1 / a}\) implies the asserted estimate.$$\tag*{$\blacksquare$}$$
The following relations are logically equivalent: \[\lim _{x \rightarrow \infty} \frac{\pi(x) \log x}{x}=1. \tag{A}\] \[\lim _{x \rightarrow \infty} \frac{\vartheta(x)}{x}=1. \tag{B}\] \[\lim _{x \rightarrow \infty} \frac{\psi(x)}{x}=1. \tag{C}\]
Proof.
We know that \[\frac{\vartheta(x)}{x} \leqslant \frac{\psi(x)}{x} \leqslant \frac{\vartheta(x)}{x}+\frac{\pi(\sqrt{x}) \log x}{x}.\]
Also \[\lim_{x\to \infty}\frac{\pi(\sqrt{x}) \log x}{x}=0\]
Hence the equivalence between (B) and (C) follows.
$$\tag*{$\blacksquare$}$$
For every \(a>1\) know that \[\frac{\vartheta(x)}{x} \leqslant \frac{\pi(x)\log x}{x} \leqslant \frac{a \vartheta(x)}{x}+\frac{\pi\big(x^{1 / a}\big)\log x}{x}.\]
For every \(a>1\) we also know that \[\lim_{x\to \infty}\frac{\pi\big(x^{1 / a}\big)\log x}{x}=0.\]
Then \[\lim_{x\to \infty}\frac{\vartheta(x)}{x} \leqslant \lim_{x\to \infty}\frac{\pi(x)\log x}{x} \leqslant\lim_{x\to \infty} \frac{a \vartheta(x)}{x}.\]
Since \(a>1\) is arbitrary, we obtain equivalence between (A) and (B).
This completes the proof of the theorem. $$\tag*{$\blacksquare$}$$
For all \(x \geqslant 1\), we have \[\vartheta(x) \leqslant x \log 4.\]
Proof.
We first prove by induction that, for all \(n\in\mathbb Z_+\), we have \[\vartheta(n) \leqslant n \log 4.\]
This inequality is clearly true for \(n \in[3]\). If \(n \geqslant 4\) is even, we have \[\vartheta(n)=\vartheta(n-1) \leqslant (n-1)\log 4<n\log 4^{n}.\]
Suppose now that \(n \geqslant 5\) is odd and set \(n=2 m+1\) with \(m\in\mathbb Z_+\). The idea is to use the fact that the product \[\prod_{m+1<p \leqslant 2 m+1} p\] divides the binomial coefficient \(\binom{2 m+1}{m}\).
To see this, observe that \(p\in\mathbb P\) such that \(m+1<p \leqslant 2m+1\) divides \((2m+1)!\) because of \(p \leqslant 2 m+1\), but does not divide \(m!(m+1)!\) because of \(p>m+1\), so that \[\prod_{m+1<p \leqslant 2 m+1} p \quad \text { divides } \quad (2 m+1)!=m!(m+1)!\binom{ 2 m+1}{m}\] and since the product is coprime to \(m!(m+1)!\) the claim follows.
Taking logarithms, we then obtain \[\vartheta(2 m+1)-\vartheta(m+1)=\sum_{m+1<p \leqslant 2 m+1} \log p \leqslant \log \binom{2 m+1}{m}.\]
Using Stirling’s formula we have \(\binom{2 m+1}{m}\le \frac{2m+1}{m+1}\frac{4^m}{\sqrt{\pi m}}\le 4^m\), thus \[\vartheta(2 m+1)\le m\log 4+\vartheta(m+1)\le m\log 4+ (m+1)\log 4=(2m+1)\log 4,\] where we have used the induction hypothesis applied to \(\vartheta(m+1)\).
The lemma follows from \[\vartheta(x)=\vartheta(\lfloor x\rfloor) \le \lfloor x\rfloor \log 4 \leqslant x \log 4.\]
The proof is complete.$$\tag*{$\blacksquare$}$$
For all \(x \geqslant 1537\), we have \[\vartheta(x)>\frac{x}{\log 4}.\]
Proof.
We first notice that the function \(f\) defined by \[f(x)=\lfloor x\rfloor -\bigg\lfloor\frac{x}{2}\bigg\rfloor-\bigg\lfloor\frac{x}{3}\bigg\rfloor-\bigg\lfloor\frac{x}{5}\bigg\rfloor +\bigg\lfloor\frac{x}{30}\bigg\rfloor,\] is periodic of period \(30\), since \(\lfloor x+n\rfloor =\lfloor x \rfloor+n\) for any \(n\in\mathbb Z\).
Moreover, for \(x \notin \mathbb{Z}\), we have \[f(30-x)=1-f(x),\] since \(\lfloor -x \rfloor=-\lfloor x \rfloor-1\) for \(x \notin \mathbb{Z}\).
An inspection of its values when \(x \in[1,15)\) allows us to infer that \(f(x)\) only takes the values \(0\) or \(1\) if \(x \notin \mathbb{Z}\).
Since \(f\) is continuous on the right, we also have \(f(x)=0\) or \(1\) when \(x \in \mathbb{Z}\). By periodicity, we infer that \(f(x)=0\) or \(1\) for all \(x \in \mathbb{R}\).
Hence we obtain \[\begin{aligned} \psi(x) \geqslant & \sum_{n \leqslant x} \Lambda(n) f\left(\frac{x}{n}\right) = \sum_{n \leqslant x} \Lambda(n)\left(\bigg\lfloor\frac{x}{n}\bigg\rfloor -\bigg\lfloor\frac{x}{2n}\bigg\rfloor-\bigg\lfloor\frac{x}{3n}\bigg\rfloor-\bigg\lfloor\frac{x}{5n}\bigg\rfloor +\bigg\lfloor\frac{x}{30n}\bigg\rfloor\right) \\ = & \sum_{n \leqslant x} \Lambda(n)\bigg\lfloor\frac{x}{n}\bigg\rfloor-\sum_{n \leqslant x / 2} \Lambda(n)\bigg\lfloor\frac{x}{2n}\bigg\rfloor-\sum_{n \leqslant x / 3} \Lambda(n)\bigg\lfloor\frac{x}{3n}\bigg\rfloor\\ & -\sum_{n \leqslant x / 5} \Lambda(n)\bigg\lfloor\frac{x}{5n}\bigg\rfloor+\sum_{n \leqslant x / 30} \Lambda(n)\bigg\lfloor\frac{x}{30n}\bigg\rfloor, \end{aligned}\] where we used the fact that \(\lfloor x / k n\rfloor=0\) whenever \(n>x / k\) for \(k \in\{2,3,5,30\}\).
By a simplified form of Striling’s formula we know for all \(x\ge 1\) that \[\sum_{n\in[x]}\log n=x\log x-x+1+R(x), \quad \text{ where } \quad 0\le R(x)\le \log x.\]
Since \(\Lambda\star{\bf 1}=\log\), then we conclude that \[\begin{aligned} \sum_{n\in[x]}\log n=\sum_{n\in[x]}\sum_{d\mid n}\Lambda(d)=\sum_{d\in[x]}\Lambda(d)\sum_{k\in[x/d]}=\sum_{d\in[x]}\Lambda(d)\bigg\lfloor\frac{x}{d}\bigg\rfloor. \end{aligned}\]
Hence for \(x\ge 1\), we have \[\sum_{d\in[x]}\Lambda(d)\bigg\lfloor\frac{x}{d}\bigg\rfloor=x\log x-x+1+R(x), \quad \text{ where } \quad 0\le R(x)\le \log x.\]
Inserting this bounds to the previous formula we obtain \[\begin{aligned} \psi(x) \geqslant & x \log x-x+1-\left(\frac{x}{2} \log \frac{x}{2}-\frac{x}{2}+1+\log \frac{x}{2}\right) \\ & -\left(\frac{x}{3} \log \frac{x}{3}-\frac{x}{3}+1+\log \frac{x}{3}\right)-\left(\frac{x}{5} \log \frac{x}{5}-\frac{x}{5}+1+\log \frac{x}{5}\right) \\ & +\left(\frac{x}{30} \log \frac{x}{30}-\frac{x}{30}+1\right) \\ = & x \log \left(2^{7 / 15} 3^{3 / 10} 5^{1 / 6}\right)-3 \log x+\log 30-1 . \end{aligned}\]
Using the estimate \(\psi(x)\le \vartheta(x)+\pi(\sqrt{x})\log x\) we obtain the desired lower bound \[\vartheta(x)\ge x \log \left(2^{7 / 15} 3^{3 / 10} 5^{1 / 6}\right)-(\sqrt{x}+3) \log x\ge \frac{x}{\log 4},\] whenever \(x\in\mathbb R_+\) is sufficiently large. This completes the proof.$$\tag*{$\blacksquare$}$$
Note that \[\log \left(2^{7 / 15} 3^{3 / 10} 5^{1 / 6}\right) \approx 0.92129 \ldots,\] which is a very good lower bound. It was sufficient to allow Chebyshev to prove Bertrand’s famous postulate.
Let \(n\in\mathbb Z_+\). Then the interval \((n, 2n]\) contains a prime number.
Proof.
We check numerically the result for \(n \in[768]\) and we suppose \(n \geqslant 769\).
Using Chebyshev’s upper and lower bounds we deduce \[\sum_{n<p \leqslant 2 n} \log p=\vartheta(2 n)-\vartheta(n)>n\left(\frac{2}{\log 4}-\log 4\right)>0.\]
This shows that \((n, 2n]\cap \mathbb P\neq \varnothing\), which implies the desired result.
$$\tag*{$\blacksquare$}$$
For all \(x \geqslant 5\), we have \[\frac{1}{\log 4} \frac{x}{\log x}<\pi(x)<\left(2+\frac{1}{\log 4}\right) \frac{x}{\log x}.\]
Proof.
For all integers \(n \in\{5, \ldots, 1537\}\) one can verify that \[\frac{1}{\log 4} \frac{n+1}{\log n}<\pi(n)<\left(2+\frac{1}{\log 4}\right) \frac{n}{\log (n+1)}\] which implies the desired inequalities for all \(x \in[5,1537]\).
Suppose that \(x \geqslant 1537\). Using the upper bound for \(\pi(x)\) with \(a=3 / 2\) we obtain \[\pi(x) \le \frac{3\vartheta(x)}{2\log x}+\pi(x^{2/3})\le \frac{3 x \log 4}{2 \log x}+x^{2 / 3}.\]
The inequality \(\log x<3 e^{-1.55} x^{1 / 3}\), valid for all \(x \geqslant 1537\), implies that \[\pi(x)<\frac{3 x \log 4}{2 \log x}+\frac{3 e^{-1.55} x}{\log x}<\left(2+\frac{1}{\log 4}\right) \frac{x}{\log x},\] as required.
$$\tag*{$\blacksquare$}$$
For all \(x \geqslant 25\), we have \[\begin{aligned} & \psi(x)<\vartheta(x)+\left(4+\frac{1}{\log 2}\right) \sqrt{x}, \\ & \pi(x)<\frac{3}{2 \log x}\left(\vartheta(x)+\left(2+\frac{1}{\log 4}\right) x^{2 / 3}\right). \end{aligned}\]
For all \(x \geqslant 1\), we have \[\psi(x)<2 x.\]
Let \(p_{n}\) be the nth prime number. Then, for all integers \(n \geqslant 3\), we have \[\frac{1}{2}n \log n<p_{n}<2 n \log n.\] The lower bound for \(p_n\) immediately implies that \[\sum_{p\in\mathbb P}\frac{1}{p}=\sum_{n\in\mathbb Z_+}\frac{1}{p_n}=\infty.\]
Proof of (i) and (ii).
We know that \[\vartheta(x) \leqslant \psi(x) \leqslant \vartheta(x)+\pi(\sqrt{x}) \log x.\]
From the previous theorem \[\pi(x)<\left(2+\frac{1}{\log 4}\right)\frac{x}{\log x}.\]
Hence \[\psi(x) \leqslant \vartheta(x)+\pi(\sqrt{x}) \log x\le \vartheta(x)+ 2\left(2+\frac{1}{\log 4}\right) \sqrt{x}.\]
The inequality \(\psi(x)<2x\) is first numerically checked for all integers \(n \in[1,100]\) and for \(x>100\) we invoke the previous bound.
We know that \[\frac{\vartheta(x)}{\log x} \leqslant \pi(x) \leqslant \frac{3 \vartheta(x)}{2\log x}+\pi\big(x^{2/3}\big)\]
Again by the previous theorem we conclude that \[\pi(x)<\frac{3}{2 \log x}\left(\vartheta(x)+\left(2+\frac{1}{\log 4}\right) x^{2 / 3}\right). \]
$$\tag*{$\blacksquare$}$$
Proof of (iii).
We first check the inequalities for \(n \in\{3, \ldots, 337\}\). Suppose \(n \geqslant 338\) so that \(p_{n} \geqslant 2273\). The proof rests on the fact that \(\pi\left(p_{n}\right)=n\).
For the lower bound, we use the second upper bound of (i) above, the inequality \(x^{2 / 3}<x / 13\) valid for all \(x \geqslant 2273\) and the trivial inequality \(p_{n}>n\), which imply the desired lower bound \[n=\pi\left(p_{n}\right)<\frac{3 p_{n}}{2 \log p_{n}}\left\{\log 4+\frac{1}{13}\left(2+\frac{1}{\log 4}\right)\right\}<\frac{2 p_{n}}{\log p_{n}}<\frac{2 p_{n}}{\log n}.\]
For the upper bound, we use the inequality \(\frac{\log x}{x^{1-\log 2}}<\frac{1}{\log 4}\) valid for all \(x \geqslant 2273\) (applied with \(x=p_{n}\)), and the lower bound for \(\pi(x)\) giving
\[\frac{\log p_{n}}{p_{n}^{1-\log 2}}<\frac{1}{\log 4}<\frac{\pi\left(p_{n}\right) \log p_{n}}{p_{n}}=\frac{n \log p_{n}}{p_{n}}\]
Hence \(p_{n}<n^{1 / \log 2}\), and \(\log p_{n}<\frac{\log n}{\log 2}\). Thus, the upper bound follows \[n=\pi\left(p_{n}\right)>\frac{1}{\log 4} \frac{p_{n}}{\log p_{n}}>\frac{p_{n}}{2 \log n}. \]
$$\tag*{$\blacksquare$}$$
For all \(x \geqslant 2\), we have \[\sum_{p \leqslant x} \frac{\log p}{p}=\log x+O(1).\]
Proof.
We first notice that \[\sum_{d \leqslant x} \frac{\Lambda(d)}{d}=\sum_{p \leqslant x} \frac{\log p}{p}+\sum_{\substack{p^{k} \leqslant x \\ k \geqslant 2}} \frac{\log p}{p^{k}}.\]
The second sum is \[\sum_{\substack{p^{k} \leqslant x \\ k \geqslant 2}} \frac{\log p}{p^{k}}\leqslant \sum_{p \leqslant \sqrt{x}} \log p \sum_{k=2}^{\infty} \frac{1}{p^{k}}=\sum_{p \leqslant \sqrt{x}} \frac{\log p}{p(p-1)}=O(1).\]
$$\tag*{$\blacksquare$}$$
We have proved that \[\sum_{p \leqslant x} \frac{\log p}{p}=\sum_{d \leqslant x} \frac{\Lambda(d)}{d}+O(1).\]
We know that for \(x\ge 1\), we have \[\sum_{d\in[x]}\Lambda(d)\bigg\lfloor\frac{x}{d}\bigg\rfloor=x\log x-x+1+R(x), \quad \text{ where } \quad 0\le R(x)\le \log x.\]
Hence, we have \[x\log x+O(x)=\sum_{d\in[x]}\Lambda(d)\bigg\lfloor\frac{x}{d}\bigg\rfloor= x\sum_{d\in[x]}\frac{\Lambda(d)}{d}+O(\psi(x)).\]
Since \(\psi(x)<2x\), we obtain \[x\sum_{d\in[x]}\frac{\Lambda(d)}{d}=x\log x+O(x)\]
Therefore the desired conclusion follows \[\sum_{d \leqslant x} \frac{\Lambda(d)}{d}=\log x+O(1). \qquad \tag*{$\blacksquare$}\]
There exists a constant \(B\in\mathbb R_+\) such that for all \(x\ge 2\) we have \[\sum_{p \leq x} \frac{1}{p}=\log \log x+B+O\left(\frac{1}{\log x}\right).\]
Proof.
We can write \[\sum_{p \leq x} \frac{1}{p}=\sum_{p \leq x} \frac{\log p}{p} \frac{1}{\log p}=\sum_{2 \leq n \leq x} f(n) g(n),\] where \(f(n)= {\bf 1}_{\mathbb P}(n)\frac{\log n}{n}\) and \(g(t)=\frac{1}{\log t}\)
Let \[F(t)=\sum_{n \leq t} f(n)=\sum_{p \leq t} \frac{\log p}{p}.\]
Then \(F(t)=0\) for \(t<2\). By the first Mertens theorem we have \[F(t)=\log t+r(t), \quad \text { where } \quad r(t)=O(1).\]
Therefore, the integral \(\int_{2}^{\infty} \frac{r(t)}{t(\log t)^{2}} d t\) converges absolutely, and \[\int_{x}^{\infty} \frac{r(t) d t}{t(\log t)^{2}}=O\left(\frac{1}{\log x}\right) .\]
By partial summation, we obtain \[\begin{aligned} \sum_{p \leq x} \frac{1}{p}= & \sum_{n \leq x} f(n) g(n) = F(x) g(x)-\int_{2}^{x} F(t) g^{\prime}(t) d t \\ = & \frac{\log x+r(x)}{\log x}+\int_{2}^{x} \frac{\log t+r(t)}{t(\log t)^{2}} d t \\ = & 1+O\left(\frac{1}{\log x}\right)+\int_{2}^{x} \frac{d t}{t \log t} +\int_{2}^{x} \frac{r(t)}{t(\log t)^{2}} d t \\ = & \log \log x+1-\log \log 2+\int_{2}^{\infty} \frac{r(t)}{t(\log t)^{2}} d t -\int_{x}^{\infty} \frac{r(t)}{t(\log t)^{2}} d t+O\left(\frac{1}{\log x}\right) \\ =& \log \log x+B+O\left(\frac{1}{\log x}\right), \end{aligned}\] where \[B=1-\log \log 2+\int_{2}^{\infty} \frac{r(t)}{t(\log t)^{2}} d t. \qquad \tag*{$\blacksquare$}\]
For all \(x \geqslant e\), we have \[\prod_{p \leqslant x}\left(1-\frac{1}{p}\right)=\frac{e^{-\gamma}}{\log x}\left(1+O\left(\frac{1}{\log x}\right)\right).\]
Remark: (Exercise). In the second Mertens theorem one can show that \[B:=\gamma+\sum_{p\in\mathbb P}\bigg(\log \left(1-\frac{1}{p}\right)+\frac{1}{p}\bigg)\approx 0.2614972128 \ldots,\] which is called the Mertens constant. We will use this fact below.
Proof.
We have \[\begin{aligned} \log \prod_{p \leqslant x}\left(1-\frac{1}{p}\right)^{-1}&=\sum_{p \leqslant x} \log \left(1-\frac{1}{p}\right)^{-1}\\ &=\sum_{p \leqslant x} \frac{1}{p}+\sum_{p \leqslant x}\left(\log \left(1-\frac{1}{p}\right)^{-1}-\frac{1}{p}\right). \end{aligned}\]
Using the Taylor series expansion we conclude that \[\log \left(1-\frac{1}{p}\right)^{-1}-\frac{1}{p} \leqslant \frac{1}{2 p(p-1)} \leqslant \frac{1}{p^{2}}.\]
By the last bound we have \(\sum_{p>x} \frac{1}{p^{2}} = O\left(\frac{1}{x}\right).\)
By the second Mertens theorem we may write \[\begin{aligned} \log \prod_{p \leqslant x}\left(1-\frac{1}{p}\right)^{-1} & =\sum_{p \leqslant x} \frac{1}{p}-\sum_{p\in\mathbb P}\bigg(\log \left(1-\frac{1}{p}\right)+\frac{1}{p}\bigg)+O\left(\frac{1}{x}\right) \\ & =\log \log x+\gamma+O\left(\frac{1}{\log x}\right). \end{aligned}\]
Using \(e^{h}=1+O(h)\) for all \(h \to 0\) finally gives \[\prod_{p \leqslant x}\left(1-\frac{1}{p}\right)^{-1}=e^{\gamma} \log x\bigg(1+O\left(\frac{1}{\log x}\right)\bigg),\] which is easily seen to be equivalent to the desired formula. $$\tag*{$\blacksquare$}$$
Let \(\varepsilon>0\) be given. Then there exists an \(N_{\varepsilon}\in\mathbb Z_+\) such that \[\varphi(n) \geq(1-\varepsilon) \frac{e^{-\gamma} n}{\log \log n} \quad \text { for all } \quad n \geq N_{\varepsilon}.\]
Proof.
Take any \(n>1\) and write \[\frac{\varphi(n)}{n}=\prod_{p \mid n}\left(1-\frac{1}{p}\right)=P_{1}(n) P_{2}(n),\] where
\[P_{1}(n)=\prod_{\substack{p \mid n \\ p \leq \log n}}\left(1-\frac{1}{p}\right), \quad \text { and } \quad P_{2}(n)=\prod_{\substack{p \mid n \\ p>\log n}}\left(1-\frac{1}{p}\right) .\]
Then \[P_{2}(n)>\prod_{\substack{p \mid n \\ p>\log n}}\left(1-\frac{1}{\log n}\right)=\left(1-\frac{1}{\log n}\right)^{f(n)},\] where \(f(n)\) is the number of primes which divide \(n\) and exceed \(\log n\).
Since \[n \geq \prod_{p \mid n} p>\prod_{\substack{p \mid n \\ p>\log n}} p \geq(\log n)^{f(n)}\] we find \(\log n>f(n) \log \log n\), so \(f(n)<\log n / \log \log n\).
Since \(1-(1 / \log n)\) \(<1\), we obtain \[P_{2}(n)>\left(1-\frac{1}{\log n}\right)^{\log n / \log \log n} =\left(\bigg(1-\frac{1}{\log n}\bigg)^{\log n}\right)^{1 / \log \log n}.\]
Now \(\lim_{u\to\infty}\big(1-\frac{1}{u}\big)^{u} = e^{-1}\), so we can conclude that \[P_{2}(n)>1+o(1) \quad \text { as } \quad n \rightarrow \infty.\]
Therefore, there exists \(N_{\varepsilon}\in\mathbb Z_+\) such that for every \(n \geq N(\varepsilon)\) we have \[\begin{aligned} \frac{\varphi(n)}{n} & =P_{1}(n) P_{2}(n)>(1+o(1)) \prod_{\substack{p \mid n \\ p \leq \log n}}\left(1-\frac{1}{p}\right)\\ &\geq(1+o(1)) \prod_{p \leq \log n}\left(1-\frac{1}{p}\right) =(1+o(1)) \frac{e^{-\gamma}}{\log \log n} \geq(1-\varepsilon) \frac{e^{-\gamma}}{\log \log n}. \end{aligned}\]
This completes the proof. $$\tag*{$\blacksquare$}$$
Let \(\varepsilon>0\) be given. Then there exists an \(N_{\varepsilon}\in\mathbb Z_+\) such that \[\tau(n)<2^{(1+\varepsilon)\frac{ \log n}{\log \log n}}=n^{\frac{(1+\varepsilon) \log 2}{\log \log n}} \quad \text { for all } \quad n \geq N_{\varepsilon}.\] In particular, for every \(\delta>0\), we obtain \[\tau(n)=o\left(n^{\delta}\right).\]
Proof.
Write \(n=p_{1}^{a_{i}} \cdots p_{k}^{a_{k}}\), so that \(\tau(n)=\prod_{i=1}^{k}\left(a_{i}+1\right)\).
We split the product into two parts, separating those prime divisors \(<f(n)\) from those \(\geq f(n)\), where \(f(n)\) will be specified later.
Then \(\tau(n)=P_{1}(n) P_{2}(n)\) where \[\begin{aligned} P_{1}(n)&=\prod_{p_{i}<f(n)}\left(a_{i}+1\right),\\ P_{2}(n)&=\prod_{p_{i} \geq f(n)}\left(a_{i}+1\right). \end{aligned}\]
In the product \(P_{2}(n)\) we use the inequality \((a+1) \leq 2^{a}\) to obtain \(P_{2}(n) \leq\) \(2^{S(n)}\), where \[S(n)=\sum_{\substack{i=1 \\ p_{i} \geq f(n)}}^{k} a_{i} .\]
Now \[n=\prod_{i=1}^{k} p_{i}^{a_{i}} \geq \prod_{p_{i} \geq f(n)} p_{i}^{a_{i}} \geq \prod_{p_{i} \geq f(n)} f(n)^{a_{i}}=f(n)^{S(n)},\] hence \[\log n \geq S(n) \log f(n) \quad \iff \quad S(n) \leq \frac{\log n}{\log f(n)}.\]
This gives us \[P_{2}(n) \leq 2^{\log n / \log f(n)}.\]
To estimate \(P_{1}(n)\) we write \[P_{1}(n)=\exp \left\{\sum_{p_{i}<f(n)} \log \left(a_{i}+1\right)\right\}\]
We have \(n \geq p_{i}^{a_{i}} \geq 2^{a_{i}}\), hence \[\log n \geq a_{i} \log 2 \quad \iff \quad a_{i} \leq \log n / \log 2.\]
Therefore, for sufficiently large \(n\in\mathbb Z_+\), we have \[1+a_{i} \leq 1+\frac{\log n}{\log 2}<(\log n)^{2}\]
Thus \(n \geq N_0\) for some \(N_0\in\mathbb Z_+\) implies \[\log \left(1+a_{i}\right)<\log (\log n)^{2}=2 \log \log n.\]
This gives us \[P_{1}(n)<\exp \bigg(2 \log \log n \sum_{p_{i}<f(n)} 1\bigg) \leq \exp (2 \pi(\: f(n))\log \log n).\]
Setting \(c=6 / \log 2\) and using \(\pi(x)<3 x / \log x\), we obtain \[P_{1}(n)<\exp \bigg(\frac{6 f(n) \log \log n}{\log f(n)}\bigg)=2^{\frac{c f(n) \log \log n}{\log f(n)}}.\]
Then we deduce \(\tau(n)=P_{1}(n) P_{2}(n)<\) \(2^{g(n)}\), where \[g(n)=\frac{\log n+c f(n) \log \log n}{\log f(n)}=\frac{\log n}{\log \log n} \frac{1+\frac{cf(n) \log \log n}{\log n}}{\frac{\log f(n)}{\log \log n}}.\]
Now we choose \(f(n)\) to make \(f(n) \log \log n / \log n \rightarrow 0\) and also to make \(\log f(n) / \log \log n \rightarrow 1\) as \(n \rightarrow \infty\). For this it suffices to take \[f(n)=\frac{\log n}{(\log \log n)^{2}} .\]
Therefore, there exists \(N_{\varepsilon}\in\mathbb Z_+\) such that for every \(n \geq N(\varepsilon)\) we have \[g(n)=\frac{\log n}{\log \log n} \frac{1+o(1)}{1+o(1)}=\frac{\log n}{\log \log n}(1+o(1))<(1+\varepsilon) \frac{\log n}{\log \log n}.\]
This proves the theorem.$$\tag*{$\blacksquare$}$$