I'm trying to understand a proof of a theorem in my notes but there are multiple parts I simply can't follow , The theorem is as follows :
Let $\Phi(n)=\sum^n_{i=1}\phi(i)$, where $\phi(n)$ is the Euler phi function then $\Phi(n)=\tfrac{3n^2}{\pi}+O(n\log(n))$.
The proof goes as follows:
Note $\mu$ is the mobius function, $[\tfrac{n}{d}]$ is the integer part of n divided by , and $O$ is defined as ; given two functions $f,g$ we write $f(x)=(Og(x))$ if there exists a constant $c$ s.t. $f(x)\leq cg(x)$ for all c
$\Phi(n)=\sum^n_{i=1}\phi(i)=\sum^n_{i=1}\sum_{d|i}\tfrac{i}{d}\mu(d)$
let $\tfrac{i}{d}=d'$ so $i=dd'$, then,
$\Phi(n)=\sum_{dd'\leq n}d'\mu(d)$
$=\sum^n_{d=1}\mu(d)\sum^{[\tfrac{n}{d}]}_{d=1}d'$ ……..
=$\tfrac{1}{2}\sum^n_{d=1}\mu(d)([\tfrac{n}{d}]^2+[\tfrac{n}{d}])$……(1)
=$\tfrac{1}{2}\sum^n_{d=1}\mu(d)(\tfrac{n^2}{d^2}+O(n/d))$…….
=$\tfrac{1}{2}\sum^n_{d=1}\mu(d)\tfrac{n^2}{d^2}+\tfrac{1}{2}\sum^n_{d=1}\mu(d)O(n/d)$
=$\tfrac{n^2}{2}\sum^n_{d=1}\tfrac{\mu(d)}{d^2}+O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})$…….(2)
=$\tfrac{n^2}{2}(\sum_{d=1}^\infty\tfrac{\mu(d)}{d^2}-\sum^{\infty}_{d=n+1}\tfrac{\mu(d)}{d^2})+O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})$
Consider $O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})=O(n\sum^n_{d=1}\tfrac{1}{d})$…..(3)
$=O(n\log(n))$
so now we have $\Phi(n)=\tfrac{3n^2}{\pi}+O(n\log(n))$.
My specific questions are :
(1) How is $\sum^{[\tfrac{n}{d}]}_{d=1}d'$ equal to $\tfrac{1}{2}([\tfrac{n}{d}]^2+[\tfrac{n}{d}])$ as this equality suggests ?
(2) Why can we say that $O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})=\tfrac{1}{2}\sum^n_{d=1}\mu(d)O(n/d)$ ? It confuses me as it's only changing inside the bracket which seems to imply to me it's saying $n\sum^n_{d=1}\tfrac{\mu(d)}{d}=n/d$, but I feel it may just be a case of abusive notation?
3) Similarly why can we write this equality
Best Answer
(1) is just the usual sum: $1+2+..n=\frac{n(n+1)}{2}$ though the index of the inside sum $\sum^{[\tfrac{n}{d}]}_{d=1}d'$ should be $d'$, so the sum should actually be $\sum^{[\tfrac{n}{d}]}_{d'=1}d'$, hence maybe the confusion is due to a typo
(2) straightforward from the definition of $O$ - just absorb the constants inside:
$\tfrac{1}{2}\sum^n_{d=1}\mu(d)O(n/d)$ means a quantity $|A| \le C|\tfrac{1}{2}\sum^n_{d=1}\mu(d)(n/d)|$ for some absolute -meaning same for all $n,d$ -constant $C$, since $\frac{n}{d} >0$, while $O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})$ means a quantity $|B| \le C_1|n\sum^n_{d=1}\tfrac{\mu(d)}{d}|$ for some absolute constant $C_1$ and by taking $n$ factor in the first expression it is plain that the two are equivalent with $C=2C_1$
(3) follows from $|\mu(d)| \le 1$