Non-trivial bound on $\sum_{k=0}^{N-1} \sum_{n=1}^N \frac{\mu(n+k)}{n}$ 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?
 A: 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}\,.$$
