Let $\phi(n)$ be the Euler totient function and let $2\leq k\in\mathbb{N}$. For $m\in\mathbb{N}$, are there any known results, upper bounds (tighter than just removing the coprimality) or approximations for the following sum ? $$\sum_{n\leq m, gcd(n,m)=1}\frac{\phi(n)}{n^k} $$

Any ideas how to approximate it or how to get rid of coprime in the summation?


  • If you are familiar with the sum in the case of all n (whether or not coprime to m), you can handle the coprime terms by looking at the sum over multiples of each prime. I touch upon this in my answer, but since I am not familiar with the case of all n, you might get further than I using this subsum and inclusion exclusion approach involving multiples of various primes p dividing m . Except for $k=2$, I would not bother with inclusion exclusion. Gerhard "Many Coprimes And Little Time" Paseman, 2018.12.06. – Gerhard Paseman Dec 6 at 17:50

For rough estimation, you can lower bound the sum by replacing the summary set by all primes less than $m$. (The number of primes dividing $m$ tossed in are outweighed by the numbers coprime to m. For the large terms contributed by the small prime divisors of m, you can recorrect this estimate later for those.) When doing this, you look at sums of the form $ (p-1)/p^k$ over all primes $p \lt m$. These sums converge for all $k\gt 2$, and you know you have a finite nonzero lower bound. When $k=2$ you get a lower bound of $O(\log\log m)$ by Mertens or Euler.

Continuing with rough estimates, majorize each term by $n^{k-1}$ and sum over all $n \lt m$. I call this sum the full sum. For $k\gt 2$ and any $m$ you have the full sum bounded above by $C=\zeta(k-1)$, or use calculus to get $C - \Omega(m^{2-k})$. When $k=2$ you get an upper bound of $O(\log m)$. After this, you should ask yourself just how good a bound you need.

Since $\phi(n)$ differs from $n$ by at most a multiplicative factor of $D\log\log n$, for $m$ not too small the sum over all $n \lt m$ of $\phi(n)/n^k$ will differ at most from the full sum involving $n^{1-k}$ by the multiplicative factor $D\log\log m$. All that is left is to consider the terms where $n$ is not coprime to $m$ and see that their contribution to the full sum aren't too large.

However, one can approach this by looking at the sum over the set of $n$ which are less than $m$ and are multiples of some small prime $p$. This is essentially the full sum up to $m/p$ times $(p - \epsilon)/p^k$ as $\phi(pn)=(p - \delta)\phi(n)$ where $\delta$ is 0 or 1 depending on if $p$ divides $n$. Now for $k \gt 2$, one can just add these estimates together to find a relatively small error and get that your sum is close to the full sum. For $k=2$, one might use the sums over multiples of square free factors of m and use inclusion-exclusion to get something a little messier, but still arrive at the conclusion that the full sum is a good approximation to your sum for all but a very thin set of numbers $m$.

If your real question is about your sum when $k=2$ and $m$ belongs to this thin set of numbers having many small prime factors, I suggest looking at research involving asymptotic for the full sum of terms of $\phi(n)/n$. In this case I can't tell when the sum is more like $\log\log m$ or more like $\log m$.

Gerhard "Simple Simplifying By Ignoring Symbols" Paseman, 2018.12.06.

  • Thanks man! It helped a lot! Actually my question is not about $k=2$, it is even more for $k\geq 3$. But I am afraid that it is also more about how much the sum close to the full sum.. :) – user552099 Dec 6 at 19:11
  • If k is 3 or greater, find the smallest prime p not dividing m and use 1 + (p-1)/p^k. The actual sum won't be much larger. Gerhard "Who Really Needs The Tails?" Paseman, 2018.12.06. – Gerhard Paseman Dec 6 at 20:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.