# Simple Divisor Summation Inequality (with Moebius function)

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

$$\frac{\phi(n)}{n}=\sum_{d|n}\frac{\mu(d)}{d}$$

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.

Thanks!

-

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

-

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.

-
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! –  TaxxiDriver Nov 9 '13 at 15:19
@TaxxiDriver: Terry Tao's argument and Algin's argument are essentially the same. –  y zhao Nov 9 '13 at 15:26
@y zhao Oh, I was just afraid there are some unfamiliar notations. I'll check it up. –  TaxxiDriver Nov 9 '13 at 15:47