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


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'$ ……..






Consider $O(n\sum^n_{d=1}\tfrac{\mu(d)}{d})=O(n\sum^n_{d=1}\tfrac{1}{d})$.....(3)


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


(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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.