# Prove $\sum\limits_{n\leq x} \frac{n}{\phi(n)} =O(x)$

There is a second part of the problem posted in Proving $\frac{\sigma(n)}{n} < \frac{n}{\varphi(n)} < \frac{\pi^{2}}{6} \frac{\sigma(n)}{n}$, from Apostol's book, but I can't figure it out. It asks the reader to prove that if $x \geq 2$ then $\sum\limits_{n\leq x} \frac{n}{\phi(n)} = O(x)$, where the right hand side of the equation uses the Big-O notation. I've tried using the prior result, but I always end up with $O(x^2)$ . Any insights?

-
You can improve on your $\mathcal{O}(x^2)$ bound to $\mathcal{O}(x^{1.5})$ by making use of the fact that $\phi(n) \geq \sqrt{n}$ for $n > 6$ –  user17762 Nov 22 '11 at 20:45

We can actually prove the slightly stronger $$\sum_{n\leq x}\frac{n}{\phi (n)}=\frac{315}{2\pi^4}\zeta(3)x +O\left(\log x\right).$$

Idea: Notice that $\frac{n}{\phi(n)}$ is very close in some sense to $1$. So if we write it as $1*f$ for some $f$, and this $f$ should be very small. The following lemma, which is one of the first was you might see to sum under the hyperbola, then tells us exactly how to deal with this situation:

If $(1*f)(n)=\sum_{d|n}f(d)$ denotes Dirichlet convolution, then $$\sum_{n\leq x} (1*f)(n)=\sum_{n\leq x}\sum_{d|n}f(d)=\sum_{d\leq x} f(d)\left[\frac{x}{d}\right]$$ and using $[z]=z+O(1)$ this is $$=x\sum_{d\leq x} \frac{f(d)}{d}+O\left(\sum_{d\leq x} |f(d)|\right).$$

Since we need only look at prime powers, we need $f$ to satisfy $$(1*f)(p^k)=1+f(p)+\cdots+f(p^k)=\frac{p^k}{\phi(p^k)}=\frac{p}{p-1}.$$ This is constant with respect to $k$, so we take $f(p^k)=0$ for $k\geq 2$, and then $f(p)=\frac{1}{p-1}$. This can be rewritten for all $n$ as $f(n)=\frac{\mu(n)^2}{\phi(n)}$. Hence, using the above we see that $$\sum_{n\leq x}\frac{n}{\phi (n)}=x\sum_{d\leq x} \frac{\mu(d)^2}{d\phi(d)}+O\left(\sum_{d\leq x}\frac{\mu(d)^2}{\phi(d)}\right).$$

The big-O term term is bounded by $\log (x)$, and the infinite series $\sum_{d=1}^\infty \frac{\mu(d)^2}{d\phi(d)}$ converges absolutely. Playing around with the Euler product, we can actually find that this equals $\frac{\zeta(2)\zeta(3)}{\zeta(6)}=\frac{315}{2\pi^4}\zeta(3)$. Extending the series up to $x$ all the way to infinitely creates an error of the form $\frac{\log \log x}{x}$ which is negligible. Hence we conclude

$$\sum_{n\leq x}\frac{n}{\phi (n)}=\frac{315}{2\pi^4}\zeta(3)x +O\left(\log x\right).$$

Remark: You are looking at the mean value of a multiplicative function. For functions "close" to one, there is a simple generalization of the above, but much can be said about general bounded functions, even those which are not close to $1$. Of course this is more difficult, as the mean value of $\mu(n)$ is related to the prime number theorem, but there is much interesting work. Specifically Halasz's theorem tells us exactly when the mean value can be large. Granville and Soundararajan have developed this, and used it as an alternative starting point for proving theorems in analytic number theory.

Edit: To evaluate the series $$\sum_{d=1}^\infty \frac{\mu(d)^2}{d\phi(d)},$$ we may first note that since the summand is a multiplicative funciton, and since everything converges nicely, we can write this as an Euler product $$\sum_{d=1}^{\infty}\frac{\mu(d)^{2}}{d\phi(d)}=\prod_{p}\left(1+\frac{\mu(p)^{2}}{p\phi(p)}+\frac{\mu(p^{2})^{2}}{p^{2}\phi(p^{2})}+\cdots\right).$$ This equals $$\prod_{p}\left(1+\frac{1}{p\left(p-1\right)}\right)=\prod_{p}\left(\frac{p^{2}-p+1}{p\left(p-1\right)}\right).$$ Recalling the factorization $p^{3}+1=\left(p^{2}-p+1\right)\left(p+1\right),$ multiply to and bottom by $p+1$ to get a $p^3+1$ term on top. Since we hope to rewrite things in terms of the zeta function, multiply top and bottom by $p^{3}-1$ as well. We then get $$\prod_{p}\left(\frac{p^{3}+1}{p(p^{2}-1)}\cdot\frac{p^{3}-1}{p^{3}-1}\right)=\prod_{p}\left(1-\frac{1}{p^{6}}\right)\prod_{p}\left(1-\frac{1}{p^{3}}\right)^{-1}\prod_{p}\left(1-\frac{1}{p^{2}}\right)^{-1},$$ which equals $\frac{\zeta(2)\zeta(3)}{\zeta(6)}.$

-
Thanks Eric, that was very helpful! I still have trouble though, trying to prove that the series $\sum \frac{\mu^2 (d)}{d\phi(d)}$ converges absolutely. I know it is much smaller than the series $\sum 1/n$, but how can you prove convergence? –  Jane Roston Nov 23 '11 at 12:36
You can use what Sivaram mentioned, the fact that $\phi(n)>\sqrt{n}$. This means that $\frac{\mu(d)^2}{d\phi(d)}<\frac{1}{d^{3/2}}$. Using this bound throughout, you still get the final answer, but the error will be size $\sqrt{x}$. (To get the near optimal $\log x$, a little more needs to be done) –  Eric Naslund Nov 23 '11 at 12:49
@EricNaslund Thanks for these wonderful useful comments. I have posted some additional ideas regarding these types of problems at this link. –  Marko Riedel Nov 10 '12 at 5:14

@ Jane

The following might be what Apostol had in mind:

Considering conjugate divisors we may write $$\frac{\sigma(n)}{n}=\sum_{c|n}\frac{1}{c}$$ and hence $$\sum_{n \leq x}\frac{\sigma(n)}{n}=\sum_{c \leq x}\frac{1}{c}\left[\frac{x}{c}\right]\leq x \zeta(2)$$ so that $$\sum_{n\leq x} \frac{n}{\phi(n)} \leq \zeta(2)^2 x$$ It should be noted that the mean of $\frac{\phi(n)}{n}$ always stays close to some constant when considered over any reasonably large set of numbers.

-

if you prove that $\phi(d) \gg \frac{d}{\log d}$ then the convergence of the series is easy to see. The stronger $\phi(d) \gg \frac{d}{\log \log d}$ can be proved using the Chebyshev's estimates $\frac{x}{\log x}\ll \pi(x) \ll \frac{x}{\log x}$. A one line proof can be given from these estimates for the first inequality as follows : Every prime below $d$ is coprime to $d$ or divides $d$ and hence $\pi(d)-\omega(d) \leq \phi(d)$ from which it follows that $\frac{d}{\log d} +O(\log d) \ll \phi(d)$ which is what you want. The estimate $\omega(d) \ll \log d$ can be obtained by taking logarithms in $2^{\omega(d)}\leq d.$

-