# How to obtain an upper bound for $\sum_{x < X} \frac{\mu^2(x) \tau_k(x)}{\phi(x)}$?

Let $$\mu$$ be the Mobius function, $$\tau_k(x)$$ the number of ways to write $$x$$ as a product of $$k$$ natural numbers and $$\phi$$ the Euler totient function. I would like to obtain an upper bound for $$\sum_{x < X} \frac{\mu^2(x) \tau_k(x)}{\phi(x)}.$$ In the paper I am reading, this is bounded by $$\ll (\log X)^k$$ without explanation. I would greatly appreciate any explanation. Thank you.

ps I can see that $$\sum_{x< X} \frac{\mu^2(x)}{\phi(x)} \ll \log X$$ so I think I just have to bound $$\tau_k(x)$$...

• Could you tell us what R is? – Sylvain JULIEN Jul 21 '19 at 16:49
• typo, fixed. thanks – Takeshi Gouda Jul 21 '19 at 16:57
• Hint: $\displaystyle \sum_{x < X} \tau_2(x) \sim X \log X$. – Stanley Yao Xiao Jul 21 '19 at 22:39
• Note that a plan of bounding $\tau_k(x)$ pointwise isn't going to give a good enough bound, because there's no pointwise bound of the form $\tau_k(x) \ll (\log x)^A$ (even for $k=2$). – Greg Martin Jul 22 '19 at 2:28
• @GregMartin that's good to know. thank you. – Takeshi Gouda Jul 22 '19 at 10:57

We can obtain an explicit upper bound using the identity (where $$p$$ is restricted to primes) $$\frac{n}{\phi(n)}=\prod_{p\mid n}\left(1+\frac{1}{p-1}\right)=\sum_{d\mid n}\frac{\mu^2(d)}{\phi(d)}.$$ For $$X\geq 1$$, the above identity implies that \begin{align*}\sum_{n\leq X}\frac{\tau_k(n)}{\phi(n)} &=\sum_{n\leq X}\frac{\tau_k(n)}{n}\sum_{d\mid n}\frac{\mu^2(d)}{\phi(d)}\\ &=\sum_{d\leq X}\frac{\mu^2(d)}{\phi(d)} \sum_{m\leq X/d}\frac{\tau_k(dm)}{dm}\\ &\leq\sum_{d\leq X}\frac{\mu^2(d)\tau_k(d)}{d\phi(d)} \sum_{m\leq X/d}\frac{\tau_k(m)}{m}\\ &<\left(\sum_{d=1}^\infty\frac{\mu^2(d)\tau_k(d)}{d\phi(d)}\right) \left(\sum_{m\leq X}\frac{\tau_k(m)}{m}\right). \end{align*} On the right hand side, \begin{align*}\sum_{d=1}^\infty\frac{\mu^2(d)\tau_k(d)}{d\phi(d)} &=\prod_p\left(1+\frac{k}{p(p-1)}\right)\\ &\leq\prod_p\left(1+\frac{1}{p(p-1)}\right)^k\\ &=\left(\prod_p\frac{1-p^{-6}}{(1-p^{-2})(1-p^{-3})}\right)^k\\ &=\left(\frac{\zeta(2)\zeta(3)}{\zeta(6)}\right)^k, \end{align*} while it is straightforward that $$\sum_{m\leq X}\frac{\tau_k(m)}{m}\leq \left(\sum_{m\leq X}\frac{1}{m}\right)^k\leq (1+\log X)^k.$$ We conclude that $$\sum_{n\leq X}\frac{\tau_k(n)}{\phi(n)}<\left(\frac{\zeta(2)\zeta(3)}{\zeta(6)}\right)^k(1+\log X)^k.$$
• In the first identity are you assuming that $n$ is square-free? – Takeshi Gouda Jul 23 '19 at 13:53
• @TakeshiGouda: I am not assuming that $n$ is square-free. The identity holds for all $n$. – GH from MO Jul 23 '19 at 15:06
One should always consider Rankin's method: for $$\varepsilon>0$$, $$\sum_{n\le x} \frac{\mu^2(n)\tau_k(n)}{\phi(n)} \le \sum_{n=1} ^\infty \frac{\mu^2(n)\tau_k(n)}{\phi(n)} \frac{x^\varepsilon}{n^\varepsilon} = x^\varepsilon \prod_p \bigg( 1 + \frac k{(p-1)p^\varepsilon} \bigg),$$ assuming $$\varepsilon$$ is chosen so that the series/product converges. To show that the right-hand side is $$\ll(\log x)^k$$, it suffices to prove that $$\varepsilon \log x + \sum_p \log\bigg( 1 + \frac k{(p-1)p^\varepsilon} \bigg) \le k\log\log x+O(1).$$ We note that \begin{align*} \varepsilon \log x + \sum_p \log\bigg( 1 + \frac k{(p-1)p^\varepsilon} \bigg) &\le \varepsilon \log x + \sum_p \frac k{(p-1)p^\varepsilon} \\ &\le \varepsilon \log x + \sum_p \frac k{p\cdot p^\varepsilon} + O\bigg( \sum_p \frac1{p^2\cdot p^\varepsilon} \bigg), \end{align*} and the sum in the error is $$O(1)$$ uniformly for $$\varepsilon\ge0$$; therefore it suffices to show that $$\varepsilon \log x + \sum_p \frac k{p\cdot p^\varepsilon} \le k\log\log x+O(1).$$ If we choose for example $$\varepsilon = 1/\log x$$, the left-hand side is bounded above by \begin{align*} 1 + &\sum_{p\le x} \frac kp + \sum_{j=0}^\infty \sum_{x^{2^j} < p \le x^{2^{j+1}}} \frac k{p\cdot (x^{2^j})^{1/\log x}} \\ &= k\log\log x+O(1) + k\sum_{j=1}^\infty \frac1{e^{2^j}} \sum_{x^{2^j} < p \le x^{2^{j+1}}} \frac1p \\ &= k\log\log x+O(1) + k\sum_{j=1}^\infty \frac1{e^{2^j}} \bigg( \log\log x^{2^{j+1}} - \log \log x^{2^j} + O\bigg( \frac1{\log x^{2^j}} \bigg) \bigg) \\ &= k\log\log x+O(1) + k\sum_{j=1}^\infty \frac1{e^{2^j}} \bigg( \log 2 + O\bigg( \frac1{2^j\log x} \bigg) \bigg) \\ &= k\log\log x+O(1) \end{align*} as needed.