4
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

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.