Show that $\Phi(n) = \phi(1) +\phi(2) + \dots + \phi(n) =\frac{n^2}{2 \zeta(2)}+O(n \log n)$

Question

Set $\Phi(n) = \phi(1) + \phi(2) + \cdots + \phi(n)$. I want to understand why $$ \Phi(n) = \frac{n^2}{2\zeta(2)} + O(n\log n). $$

I am going to show the proof that I have, and I would be very grateful if someone could help me to express this in terms of big $O$ notation. Thank you.

Using the formula $$ \phi(n)=n \sum_{d \mid n} \frac{\mu(d)}{d}, $$ we have \begin{align*} \Phi(n) = \phi(1) +\phi(2) + \phi(3) + \dots + \phi(n) & =\sum_{m=1}^n \left(m \sum_{d \mid m} \frac{\mu(d)}{d}\right) = \sum_{m=1}^n \left(\sum_{dd^{\prime}=m} d^{\prime} \mu(d) \right)\\ &=\sum_{d d^{\prime} \leqslant n} d^{\prime} \mu(d) =\sum_{d=1}^n \left(\mu(d) \sum_{d^{\prime}=1}^{[n / d]} d^{\prime}\right) \\ &=\sum_{d=1}^n \mu(d)\left(\dfrac{\left[\frac{n}{d}\right]^2+\left[\frac{n}{d}\right]}{2}\right)\\ &=\dfrac{1}{2}\sum_{d=1}^n \mu(d)\left(\left[\frac{n}{d}\right]^2+\left[\frac{n}{d}\right]\right)\\ &=\dfrac{1}{2}\sum_{d=1}^n \mu(d)\left[\frac{n}{d}\right]^2+\dfrac{1}{2}\sum_{d=1}^n \mu(d)\left[\frac{n}{d}\right] \end{align*}

Remember the definition. Writing the integer part $\left[x\right]$ = $x - \{x\}$, where $\{x\}$ is the fractional part, we obtain. \begin{align*} &=\dfrac{1}{2}\sum_{d=1}^n \mu(d)\left[\frac{n}{d}\right]^2 + \dfrac{1}{2}\\ &=\dfrac{1}{2}\sum_{d=1}^n \mu(d)\left(\dfrac{n^2}{d^2} + O(\dfrac{n}{d}) \right) + \dfrac{1}{2}\\ &= \dfrac{1}{2}\sum_{d=1}^n \mu(d)\left(\dfrac{n^2}{d^2}\right) + \dfrac{1}{2}\sum_{d=1}^n \mu(d)O(\dfrac{n}{d}) + \dfrac{1}{2}\\ &=\dfrac{1}{2}\sum_{d=1}^n \mu(d)\left(\dfrac{n^2}{d^2}\right) + O(n \sum_{d=1}^n \dfrac{1}{d}) + \dfrac{1}{2}\\ &=\dfrac{n^2}{2}\sum_{d=1}^n \dfrac{\mu(d)}{d^2} + O(n \log n) + \dfrac{1}{2}\\ &=\dfrac{n^2}{2}\sum_{d=1}^\infty \dfrac{\mu(d)}{d^2} + O\left(n^2 \sum_{d=n+1}^\infty \dfrac{\mu(d)}{d^2} \right)+ O(n \log n) + \dfrac{1}{2}\\ &=\dfrac{n^2}{2 \zeta(2)} + O(n) + O(n \log n) + \dfrac{1}{2} \end{align*}

I can't understand how I can express these terms in Big O, that is, I don't understand how it works.

Below is the demonstration of the book that I used, but I want to better explain each step, so I did the above.

https://www.chrishenson.net/static/article_files/zeta/hardy_intro.pdf Theorem 330

I hope someone can help me, thank you very much

Answer 1

We have to explain why $$ \frac{n^2}{2 \zeta(2)} + O(n) + O(n \log n) = \frac{3 n^2}{\pi^2} + O(n \log n). $$ The fractions are the easy part, if we know that $\zeta(2) = \pi^2/6.$ It remains to show that the $O(n)$ can be collapsed into the $O(n \log n)$ and disappear.

The big-$O$ notation $O(F(n))$ stands for some function of $n$, which we don't care to elaborate upon, that is eventually dominated by a multiple of $F(n)$. The equation above should be understood as asserting that we have some functions $f$ and $g$ which are in $O(n)$ and $O(n \log n)$ respectively, and that no matter what they happen to be, $f(n) + g(n)$ is in $O(n \log n)$. The use of the equals sign is a bit unfortunate in hiding the quantifiers, and being overly symmetric, but there it is.

Expanding, we have $f$ and $g$ such that there exist $M_1$, $M_2$, $n_1$, $n_2$ with

• $f(n) \le M_1 n$ whenever $n \ge n_1$, and
• $g(n) \le M_2 n \log n$ whenever $n \ge n_2$.

We would like to show that $f(n) + g(n)$ is in $O(n \log n)$, so we have to find $M_3$ and $n_3$ such that whenever $n \ge n_3$, we have $f(n) + g(n) \le M_3 n \log n$. I assert that we can pick $M_3 = M_1 + M_2$ and $n_3 = \max(n_1, n_2)$. For if $n \ge n_3$, then the two conditions above for $f$ and $g$ are satisfied, and we can add to obtain $$ f(n) + g(n) \le M_1 n + M_2 n \log n. $$ As $n$ is always at least $1$ in this context, we have $M_1 n \le M_1 n \log n$. Then $$ M_1 n + M_2 n \log n \le (M_1 + M_2) n \log n $$ as required.