# Alternate approach to show $|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq 1$?

I am doing a question out of H. E. Rose's A Course In Number Theory (Chapter 2, problem 2) which I have been struggling with for some time. However I found a solution which strays from the way advised by the author, and I would just like some validation as to whether it is correct.

The question starts by asking to prove $\sum_{i \leq n} \mu(i) \big[ \frac{n}{i} \big] = 1$, which I have done in a method similar to the approach as seen here: Prove $\sum_{d \leq x} \mu(d)\left\lfloor \frac xd \right\rfloor = 1$

Now from this, it is asked to show $|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq 1$. Asked like this I assume the author is asking you to use a method or result from the preceding part to prove this. However my alternate route was as follows:

$-1 \leq \mu(i) \leq 1$

$\sum_{i \leq n} (-1) \leq \sum_{i \leq n} \mu(i) \leq \sum_{i \leq n} (1)$

By summing all values of $i$ from 1, upto and including $n$. Now using the fact $\sum_{i \leq n} (1) = n$;

$-n \leq \sum_{i \leq n} \mu(i) \leq n$

Taking the absolute value;

$|\sum_{i \leq n} \mu(i)| \leq n$

Now multiplying through by $\sum_{i \leq n} \frac{1}{i}$ which is strictly positive (and hence it can be taken inside the absolution), giving;

$|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq n \sum_{i \leq n} \frac{1}{i}$

From here, you can use Euler's integral theorem;

$|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq n\big(\ln(n) + \gamma +O(\frac{1}{n}) \big)$

$|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq n\ln(n) + n\gamma +O(1)$

As $n \gamma$ is constant, this can be absorbed into the $O(1)$;

$|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq n\ln(n) + O(1)$

This is where I make an assumption; $\ln(n) = o(\frac{1}{n})$ then substituting this in;

$|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq n(o(\frac{1}{n})) + O(1) = o(1)$

Thus, finally giving;

$|\sum_{i \leq n} \frac{\mu(i)}{i}| \leq 1$

Thank you.

• What is $\mu(i)$? – Gregory Grant Dec 31 '15 at 13:40
• The Mobius mu function – Declan Bays Dec 31 '15 at 13:42
• But $n\sum_{i\le n}1/i=n+n/2+\cdots n/n\ge n+1$, and not $\le 1$ before Euler's theorem in your proof. In fact, the bound is $\log(n)n$ which certainly is bigger than $1$ for $n$ large. – Dietrich Burde Dec 31 '15 at 13:47
• $\ln(n)$ is certainly not $o(\frac{1}{n})$. It's not even $O(1)$. It is, however, $o(n)$. – Wojowu Dec 31 '15 at 14:03

There are quite a few mistakes happening here.

1. You get $|\sum_{i\leq n}\mu(n)|\leq n$ and you multiply it by $\sum_{i \leq n} \frac{1}{i}$, getting on the left hand side $|\sum_{i \leq n} \frac{\mu(i)}{i}|$. You seem to be using a rule of a sort $(\sum_{i\leq n}a_n)(\sum_{i\leq n}b_n)=\sum_{i\leq n}a_nb_n$, which is not correct - the latter sum doesn't include terms like $a_1b_2$ (to be exact - it misses $a_ib_j$ for $i\neq j$).

2. $n\gamma$ is not a constant. This is a strictly increasing function of $n$. Hence it's incorrect to absorb it into $O(1)$ term.

3. This is I believe the most important: your assumption that $\ln(n)=o(\frac{1}{n}$ is very, very wrong. $\ln(n)$ is an increasing function which tends to infinity, while every function which is $o(\frac{1}{n})$ decreases to zero moderately fast.

4. In second to last equation you write $n(o(\frac{1}{n}))+O(1)=o(1)$. Left hand side of this equality is clearly $o(1)+O(1)$, but this need not be $o(1)$. Indeed, $o(1)+O(1)$ is exactly the same thing as $O(1)$.

5. After you get $|\sum_{i \leq n} \frac{\mu(i)}{i}|=o(1)$ you conclude $|\sum_{i \leq n} \frac{\mu(i)}{i}|\leq 1$. However, that the sum of $o(1)$ only tells you that the absolute value of the sum is eventually less than or equal to $1$, so this would only establish that the sum is less than or equal to $1$ _for $n$ large enough.

Lastly I wanted to ask, what is exactly the "Euler's integral theorem" you are refering to? The asymptotic you provide for $\sum_{i\leq n}\frac{1}{i}$ is correct, I'm just asking for what the theorem you refer to states.

• This really was a shot in the dark; the book I am working from seems to be going to great lengths to omit facts and explanations. I will quickly run through your amendments. The Euler integral theorem, as it is stated in the book states explicitly; $\int^{x}_{1} \frac{dt}{t} = \ln(x) + \gamma + O(\frac{1}{x})$, and later goes onto say this is equivalent to $\sum_{t \leq x} \frac{1}{t}$ – Declan Bays Dec 31 '15 at 14:37
• I've tried another approach, using the definition that $\frac{\phi(n)}{n} = \sum_{d|n} \frac{\mu(d)}{d}$. Using the Mobius inversion formula from here to get: $\frac{\mu(n)}{n} = \sum_{d|n} d \frac{\mu(d) \phi(\frac{n}{d})}{n} \implies \sum_{n\leq x} \frac{\mu(n)}{n} = \sum_{n \leq x} \sum_{d|n} d \frac{\mu(d) \phi(\frac{n}{d})}{n}$ But from here I keep getting the RHS equalling one due to the $\sum_{d|n} \mu(d) = 1 (n=1$ only). I just cant make the last step (if this is more on track?) – Declan Bays Dec 31 '15 at 16:34

Your estimate somehow arrives at the bound $n\log(n)+O(1)$ which is certainly not $\le 1$ for large $n$ - where you say, "This is where I make an assumption", it is not true.

• It's not even showing this, because of absorbing $n\gamma$ into a constant. – Wojowu Dec 31 '15 at 14:14