Easy (?) estimation about prime powers

Question

Let $N_k$ be some integers with $\sum_{k\mid n}kN_k=p^n$. How can I prove $$\frac{p^n}{n}-\frac{2p^{n/2}}{n}\leq N_n?$$

Answer 1

Use Mobius inversion to see that $$ nN_n = \sum_{d \mid n} \mu(d)p^{n/d}.$$

The leading terms are $p^n - p^{n/2}$, where the second term only appears if $n \mid 2$. The rest of the terms are $\pm p^m$, where $m \leq n/3$. The number of such terms is

$$\sum_{d \mid n} \lvert \mu(d) \rvert = 2^\omega,$$

where $\omega$ is the number of distinct prime factors of $n$. (Actually, we've accounted for one of the terms, so we have one or two fewer. If $p_1, \ldots, p_\omega$ are the $\omega$ distinct prime factors, then we see that $2^\omega \leq p_1p_2\ldots p_\omega\leq n$. Left equality can only occur if the only prime appearing is $2$, in which case the first two terms we wrote above is exact. Let's exclude that case. Right equality occurs if no prime is repeated in the factorization of $n$.

So the total contribution from the remaining terms is bounded above by $2^\omega p^{n/3} \leq np^{n/3}$.

So we have shown that

$$\lvert nN_n - p^n\rvert < p^{n/2} + np^{n/3},$$

or alternately that

$$N_n = p^n +E$$

where the error $E$ has $-\dfrac{p^{n/2}}{n}$ if $2 \mid n$, and is otherwise at most $p^{n/3}$ in size. Unfortunately, I see now that I was a bit lax, as this shows that

$$N_n \geq p^n - \frac{p^{n/2}}{n} -p^{n/3},$$

and it is not true for small primes $p$ and small $n$ that $p^{n/3} < \frac{p^{n/2}}{2}$ (though it it true if either $n$ or $p$ is not small). So instead, take this as a beginning argument and optimize it.