Non-trivial bound on $\sum_{k=0}^{N-1} \sum_{n=1}^N \frac{\mu(n+k)}{n}$

Question

In view of the fact that the Möbius function $\mu(n)$ has absolute value not greater than $1$. We can see that there is an easy estimate: $$\sum_{k=0}^{N-1} \sum_{n=1}^N \frac{\mu(n+k)}{n} = O(N\log N)$$ But I also know that it is relatively easy to show that for all $N \in \mathbb{N}$ we have $$\Bigg|\sum_{n=1}^N \frac{\mu(n)}{n}\Bigg| \leq 1$$ So, I find it reasonable that there may be some elementary way of showing that our sum is at least $o(N\log N)$. Is there a an elementary (not involving PNT or RH) way of showing this fact?

Answer 1

It is rather unlikely that there is an easy way of showing $$\sum_{k = 0}^{N-1}\sum_{n = 1}^{N} \frac{\mu(n+k)}{n} = o(N\log N)\,. \tag{$\ast$}$$ To estimate the sum, group terms according to $m = n + k$. For $m = N + r$, $1 \leqslant r \leqslant N-1$, the part of the sum is $$\mu(N + r) \sum_{n = r+1}^{N} \frac{1}{n}\,.$$ We estimate this using $\lvert \mu(m)\rvert \leqslant 1$ and obtain the bound $$\Biggl\lvert\sum_{r = 1}^{N-1} \mu(n+r)\sum_{n = r+1}^{N}\frac{1}{n}\Biggr\rvert \leqslant \sum_{r = 1}^{N-1} \sum_{n = r+1}^{N} \frac{1}{n} = \sum_{n = 2}^{N} \frac{n-1}{n} < N$$ for the part with $m > N$.

For $m \leqslant N$ the part of the sum is $$\sum_{m = 1}^{N}\mu(m) \sum_{n = 1}^{m} \frac{1}{n} = \sum_{\mu = 1}^{N} \mu(m)\bigl(\log m + O(1)\bigr) = \sum_{m = 1}^{N}\mu(m)\log m + O(N)\,,$$ thus overall we have $$\sum_{k = 0}^{N-1} \sum_{n = 1}^{N}\frac{\mu(n+k)}{n} = \sum_{m = 1}^{N}\mu(m)\log m + O(N)\,.$$ It is well-known (and easy to see via summation by parts) that $$\sum_{m = 1}^{N}\mu(m) \log m = o(N\log N)$$ is equivalent to $$M(N) = \sum_{m = 1}^{N} \mu(m) = o(N)\,, \tag{${\ast}\ast$}$$ which in turn is well-known to be an equivalent form of the prime number theorem.

Thus proving $(\ast)$ is actually proving the PNT. And conversely, $(\ast)$ can be easily obtained from the PNT (very straightforwardly from the form $(\ast\ast)$).

Using known bounds, or bounds implied by the Riemann hypothesis, for $M(x)$ one obtains corresponding bounds for $$\sum_{k = 0}^{N-1}\sum_{n = 1}^{N} \frac{\mu(n+k)}{n} = \sum_{n = 1}^{N} \frac{M(n + N - 1) - M(n-1)}{n}\,.$$