1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is $\mu(i)$? $\endgroup$ – Gregory Grant Dec 31 '15 at 13:40
  • $\begingroup$ The Mobius mu function $\endgroup$ – Declan Bays Dec 31 '15 at 13:42
  • $\begingroup$ 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. $\endgroup$ – Dietrich Burde Dec 31 '15 at 13:47
  • $\begingroup$ $\ln(n)$ is certainly not $o(\frac{1}{n})$. It's not even $O(1)$. It is, however, $o(n)$. $\endgroup$ – Wojowu Dec 31 '15 at 14:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – Declan Bays Dec 31 '15 at 14:37
  • $\begingroup$ 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?) $\endgroup$ – Declan Bays Dec 31 '15 at 16:34
0
$\begingroup$

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.

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

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.