I'm very confused about this bound, please give me any suggestions on how to prove it. (Note: $a \ll b$ is just a neater way to write $a = O(b)$)

I am starting with the bound $$f(n) \ll \frac{n}{\log(n)^2}\prod_{p|n}\left(1-\frac{1}{p}\right)^{-1}$$

then I don't see where $\phi$ comes from in $$\frac{n}{\log(n)^2}\prod_{p|n}\left(1-\frac{1}{p}\right)^{-1} \ll \frac{\phi(n)}{\log(n)^2}$$ I know that $\phi(n) = n \prod_{p|n}\left(1-\frac{1}{p}\right)$ but I'm confused because of the $-1$ power.

Then $$\sum_{n\le x} f(n)^2 \ll \sum_{n\le x}\frac{\phi(n)^2}{\log(n)^2}$$ but I don't understand why it's not $\log(n)^4$ even though it is permitted to replace it with a lower power in the denominator.

And finally $$\sum_{n\le x}\frac{\phi(n)^2}{\log(n)^2} \ll \frac{x^3}{\log(x)^4}$$ and I have no idea how to get that last bound at all. I tried Abel summation which didn't help and I tried using $\frac{\varphi(n)\sigma(n)}{n^2} < 1$ I've searched a lot of lecture notes and looked in Apostol and I don't see how to deduce it. One idea I had was that maybe it was a typo for $\log(x)^4$ in the denominator and they pulled that out, but that's not permitted since $n \le x$.

Thanks for any help.


It looks like there are quite a few typos throughout - as you have noticed. I also don't understand why they rewrite things in terms of the $\phi$ function at all - the bound $\prod_{p|n} \left(1-\frac{1}{p}\right)\leq 1$ seems sufficient. Anyway, I am not exactly sure what is going on here, but let me give my interpretation based on the limited information given:

I assume that the $-1$ in the exponent is incorrect, and that we should just have $$f(n)\ll \frac{n}{(\log n)^2}\prod_{p|n}\left(1-\frac{1}{p}\right).$$ From this it follows that $f(n)\ll \frac{\phi(n)}{(\log n)^2}$, and $$\sum_{n\leq x}f(n)^2 \ll \sum_{n\leq x}\frac{\phi(n)^2}{\log (n)^4},$$ where the power of $\log n$ in the denominator is $4$, not $2$. The sum on the right hand side is bounded above by $$\sum_{n\leq x} \frac{n^2}{\log (n)^4}\ll \sum_{\sqrt{x} \leq n\leq x} \frac{n^2}{\log (n)^4}.$$ On the range $\sqrt{x}\leq n\leq x$, $\log n \geq \frac{1}{2}\log x$, so the above is $$\ll \frac{1}{(\log x)^4}\sum_{\sqrt{x}\leq n\leq x} n^2 \ll \frac{x^3}{(\log x)^4}.$$ This implies that $$\sum_{n\leq x} f(n)^2 \ll \frac{x^3}{(\log x)^4}.$$

Hope that helps.

Remark: You can't hope to do better by keeping the $\phi$ function around, i.e. you can't gain another log this way, since one can prove that $$\sum_{n\leq x } \phi(n)^2 =K_1\frac{x^3}{3}(1+o(1))$$ where $$K_1=\prod_p\left(1-\frac{2}{p^2}+\frac{1}{p^3}\right)$$ is the Carefree Constant.

Remark 2: The $-1$ in the exponent doesn't actually matter, but it just seems strange in context. The bound $$f(n)\ll \frac{n}{(\log n)^2} \prod_{p|n} \left(1-\frac{1}{p}\right)^{-1}$$ still implies the bound $$\sum_{n\leq x } f(n)^2 \ll \frac{x^3}{(\log x)^4}.$$


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.