Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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))$.

share|cite|improve this question
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)$. – Sangchul Lee 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. – Sangchul Lee 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
up vote 11 down vote accepted

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,

Added: At some point, I wrote a long blog post about this, complete with a proof of Montgomery's lower bound.

share|cite|improve this answer
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

So you have \begin{align*} \sum\limits_{n \leq x} \mu(n)\biggl[\frac{x}{n}\biggr]^{2} &= \sum\limits_{n \leq x} \mu(n)\cdot\biggl(\frac{x}{n}-\biggl\{\frac{x}{n}\biggr\}\biggr)^{2} \\ &= x^{2}\sum\limits_{n \leq x }\frac{\mu(n)}{n^{2}} -2x \cdot\mathcal{O}(\log{x}) + \mathcal{O}(x) \end{align*}

To find the first sum note that: \begin{align*}x^{2} \sum\limits_{n \leq x } \frac{\mu(n)}{n^{2}} &= x^{2}\sum\limits_{n=1}^{\infty} \frac{\mu(n)}{n^{2}} - x^{2}\sum\limits_{n > x} \frac{\mu(n)}{n^{2}} \\ &= \frac{x^{2}}{\zeta(2)} + \mathcal{O}\biggl(x^{2}\sum\limits_{n >x}\frac{1}{n^{2}}\biggr) \\ &= \frac{x^{2}}{\zeta(2)} + \mathcal{O}\Biggr(x^{2}\Biggl[\sum\limits_{n=1}^{\infty} \frac{1}{n^{2}}-\sum\limits_{n \leq x } \frac{1}{n^{2}}\Biggr]\Biggr) \\ &= \frac{x^2}{\zeta(2)} + \mathcal{O}\biggl(\frac{x^{2}}{\zeta(2)} + \sum\limits_{n \leq x} \frac{1}{n^{2}}\biggr) \end{align*}

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})$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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