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

Show that

$$\left| \sum_{k=1}^{n} \frac {\mu(k)}{k} \right| \le 1 $$

where $\mu$ is Moebius function and n is a positive integer.

The hard thing here is that the sum is not directly divisor sum; it's just a normal summation. What I know is that when $F(n)=\sum_{d|n}f(d)$,

$$\sum_{k=1}^N F(k)=\sum_{k=1}^N f(k)\left[\frac{N}{k}\right]$$

But it was hardly useful since the given inequality doesn't contain the Guass function, so it became really complicated(and I'm not very confident in using the doulbe-summation). One thing I also know is that


I also tried to use this using Moebius Inversion Formula, but it also became quite complicated. For example, we can derive that

$$\frac{\mu(k)}{k}=\sum_{d|k}\frac{\phi(d)}{d} \mu \left(\frac{k}{d}\right)$$

I couldn't make it more compact. So by substitution, we get

$$\sum_{k=1}^{n} \frac {\mu(k)}{k}=\sum_{k=1}^{n}\sum_{d\mid k}\frac{\phi(d)}{d} \mu \left(\frac{k}{d}\right)$$

If it were not for the $k$ in the right term of Moebius function, we could use the first lemma I'd written down, but we can't. So I'm just stuck.

Could anybody help me solving this problem? It would be really grateful if someone could also give me general methods to tackle divisor-sum problems since I'm having a difficult time in changing the order of doulbe-summations.


share|cite|improve this question
up vote 11 down vote accepted

Let $e(k)=\sum_{d|k}\mu(d)$ and $s(n)=\sum_{k=1}^{n}e(k)$ , Then we have $$s(n)=\sum_{k=1}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor$$ and $$\left|\sum_{k=1}^n\mu(k)\left\lfloor\frac{n}{k}\right\rfloor-n\sum_{k=1}^n\frac{\mu(k)}{k}\right|\leq\sum_{k=1}^n|\mu(k)|\left|\left\lfloor\frac{n}{k}\right\rfloor-\frac{n}{k}\right|\leq\sum_{k=1}^{n-1}|\mu(k)|\leq n-1$$ Hence, $$\left|n\sum_{k=1}^n\frac{\mu(k)}{k}\right|\leq(n-1)+|s(n)|=(n-1)+1=n$$ and $$\left|\sum_{k=1}^n\frac{\mu(k)}{k}\right|\leq1.$$

share|cite|improve this answer

Here is a wonderful note of Terence Tao.

A remark on partial sums involving the Möbius function

Take a closer look at the second page, and you will get want you want.

share|cite|improve this answer
Sorry, but I'm just learning elementary number theory, so couldn't understand the stuff perfectly. I just downloaded it and when I become acquainted in this field more, I'll definitely have a look at it. Thanks! – Taxxi Nov 9 '13 at 15:19
@TaxxiDriver: Terry Tao's argument and Algin's argument are essentially the same. – y zh Nov 9 '13 at 15:26
@y zhao Oh, I was just afraid there are some unfamiliar notations. I'll check it up. – Taxxi Nov 9 '13 at 15:47

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.