# Asymptotic formula for $\sum_{n\leq x}\mu(n)[x/n]^2$ and the Totient summatory function $\sum_{n\leq x} \phi(n)$

I would like to show (for $x \ge 2$) that $$\sum_{n \le x}\mu(n)\left[\frac{x}{n}\right]^2 = \frac{x^2}{\zeta(2)} + O(x \log(x)).$$

I already have the identity $$\sum_{n \le x}\mu(n)\left[\frac{x}{n}\right] = 1$$ but the method to show this does not extend to my case.

I don't know how to approach this problem so any advice would be very welcome!

Since $$\left[\frac{x}{n}\right]^2 = \left(\frac{x}{n}\right)^2 + O(\frac{x}{n})$$ we have $$\sum_{n \le x}\mu(n)\left[\frac{x}{n}\right]^2 = \sum_{n \le x} \mu(n) \left(\frac{x}{n}\right)^2 + O(\sum_{n \le x} \mu(n) \frac{x}{n})$$ and the value estimate is $\frac{1}{\zeta(2)}$ so it remains to show that the error estimate is $O(x \log(x))$.

-
Just note that $[x/n]^2 = (x/n)^2 + O(x/n)$, and $\sum_{n \leq x} \mu(n) n^{-2} = \zeta(2)^{-1} + O(1/x)$. –  sos440 May 8 '11 at 17:21
@sos440, thanks for that idea - that must be it because I get the right terms but I don't know how to get the error estimate to be $x \log(x)$. –  quanta May 8 '11 at 17:35
The error term is easily derived, once we observe that $|\mu(n)| \leq 1$. Then $$\sum_{n\leq x} \mu(n) O(x/n) = O\left( \sum_{n\leq x} x/n \right) = O(x \log x).$$ This is in fact a very crude estimation, so there is a chance for the estimation to be improved, at least as I think. –  sos440 May 8 '11 at 17:44
@sos440, it is very simple when you do it but seems very complex when I try! Thanks again! –  quanta May 8 '11 at 17:45

Since sos440 provided the answer in the comments, a natural question is how much better can we do?

Edit: Recently, I actually had to do the contour integration and use Perrons formula as I previously suggested. It turns out that improving the error term is quite a difficult problem, and you cannot do much better then $x\log x$.

Relation to the Sum of Euler's Totient Function:

We can show that $$\sum_{n\leq x}\mu(n)[x/n]^2=-1+2\sum_{n\leq x}\phi(n)$$ so that analyzing your sum is equivalent to analyzing the totient summatory function.

The History Of The Error Term For The Totient Sum

In 1874, Mertens proved the result you wanted above, namely that $$\sum_{n\leq x}\phi(n)=\frac{3}{\pi^{2}}x^{2}+O\left(x\log x\right).$$ Throughout we use the notation $\Phi(x)=\sum_{n\leq x}\phi(n)$ for the summatory function, and $E(x)=\Phi(x)-\frac{3}{\pi^{2}}x^{2}$ for the error function.

The best unconditional result is given by Walfisz 1963: $$E(x)\ll x\left(\log x\right)^{\frac{2}{3}}\left(\log\log x\right)^{\frac{4}{3}}.$$

In 1930, Chowla and Pillai showed this cannot be improved much more, and that $E(x)$ is not $$o\left(x\log\log\log x\right).$$

In particular, they showed that $\sum_{n\leq x}E(n)\sim\frac{3}{2\pi^{2}}x^{2}$ so that $E(n)\asymp n$ on average. In 1950, Erdos and Shapiro proved that there exists $c$ such that for infinitely many positive integers $N,M$ we have $$E(N)>cN\log\log\log\log N\ \ \text{and}\ \ E(M)<-cM\log\log\log\log M,$$

or more concisely

$$E(x)=\Omega_{\pm}\left(x\log\log\log\log x\right).$$

In 1987 Montgomery improved this to

$$E(x)=\Omega_{\pm}\left(x\sqrt{\log\log x}\right).$$

Sum of Relatively Prime Pairs in the Grid: Lastly, it is interesting to notice that $$\sum_{d\leq x}\mu(d)\left[\frac{x}{d}\right]^{2}=\sum_{d\leq x}\mu(d)\left(\sum_{s\leq\frac{x}{d}}1\right)\left(\sum_{r\leq\frac{x}{d}}1\right)$$

$$\sum_{d\leq x}\sum_{r,s\leq\frac{x}{d}}\mu(d)=\sum_{m,n\leq x}\sum_{d|\gcd(m,n)}\mu(d)=\sum_{\begin{array}{c} m,n\leq x\\ \gcd(m,n)=1\end{array}}1$$which is the number of relatively prime pairs of integers both of which are less then $x$.

Hope that helps,

-
Hey Eric, I am very interested in seeing how to prove the first statement (the relation to $\Phi(x)$). –  Carolus Nov 7 '11 at 7:18
@Carolus: Notice that $\sum_{k\leq n}\varphi(n)$ counts the number of relatively prime pairs of integers in the $n\times n$ box which lie on or below the diagonal. In other words $$\sum_{k\leq n}\varphi(n)=\sum_{\begin{array}{c} 1\leq k\leq m\leq n\\ (m,k)=1 \end{array}}1\ \text{so that }-1+2\sum_{k\leq n}\varphi(n)=\sum_{\begin{array}{c} m,k\leq n\\ (m,k)=1 \end{array}}1.$$ The $-1$ comes from counting the point $(1,1)$ twice. This sum then equals $$\sum_{d\leq n}\mu(d)\left[\frac{n}{d}\right]^{2}$$ by the reasoning in the last paragraph of my answer. –  Eric Naslund Nov 7 '11 at 17:14
@Carolus: Here is an alternative proof which is simpler: Since $\phi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$ we see that $$\sum_{k\leq n}\varphi(k)=\sum_{k\leq n}\sum_{d|k}\mu(d)\frac{k}{d}$$ Upon switching the order of summation this becomes $$=\sum_{d\leq n}\mu(d)\sum_{k\leq\frac{n}{d}}k=\sum_{d\leq n}\mu(d)\frac{\left[\frac{n}{d}\right]\left(\left[\frac{n}{d}\right]+1\right)}{2‌​}.$$ As $\sum_{d\leq n}\mu(d)\left[\frac{n}{d}\right]=1,$ we see that $$-1+2\sum_{k\leq n}\varphi(k)=\sum_{d\leq n}\mu(d)\left[\frac{n}{d}\right]^{2}$$ as desired. –  Eric Naslund Nov 7 '11 at 17:22
Thank you very much. This helps a lot. –  Carolus Nov 7 '11 at 17:28
and finally note that for $s > 0$ $$\sum\limits_{n \leq x} \frac{1}{n^s} = \frac{x^{1-s}}{1-s} + \zeta(s) + \mathcal{O}(x^{-s})$$