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)$...

  • $\begingroup$ Could you tell us what R is? $\endgroup$ – Sylvain JULIEN Jul 21 '19 at 16:49
  • $\begingroup$ typo, fixed. thanks $\endgroup$ – Takeshi Gouda Jul 21 '19 at 16:57
  • $\begingroup$ Hint: $\displaystyle \sum_{x < X} \tau_2(x) \sim X \log X$. $\endgroup$ – Stanley Yao Xiao Jul 21 '19 at 22:39
  • 1
    $\begingroup$ 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$). $\endgroup$ – Greg Martin Jul 22 '19 at 2:28
  • $\begingroup$ @GregMartin that's good to know. thank you. $\endgroup$ – 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.$$

P.S. Of course many other approaches are available and an asymptotic formula can also be proved. My goal was to give a fully explicit upper bound.

  • $\begingroup$ In the first identity are you assuming that $n$ is square-free? $\endgroup$ – Takeshi Gouda Jul 23 '19 at 13:53
  • $\begingroup$ @TakeshiGouda: I am not assuming that $n$ is square-free. The identity holds for all $n$. $\endgroup$ – GH from MO Jul 23 '19 at 15:06
  • 1
    $\begingroup$ Thank you, I get it now $\endgroup$ – Takeshi Gouda Jul 23 '19 at 16:09

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.


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.