Prove that for given $a>0$ there exists $C(a)$ depending on $a$ such that $$\sum_{n\leq x}\Big(\frac{n}{\phi{(n)}}\Big)^a\leq C(a)x$$where $\phi(n)$ denotes Euler totient function.

  • 1
    $\begingroup$ Hint: When you have a sum of the form $\sum_{n \le x} f(n)$, it is often useful to express $f$ (or bound it from above) as $g * 1$ (Dirichlet convolution). This replaces your sum with $\sum_{n \le x} g(n) \lfloor \frac{x}{n} \rfloor$. If $g$ is non-negative, an upper bound is $x O(\sum_{n \le x} \frac{g(n)}{n})$, so you need to establish convergence of $\sum \frac{g(n)}{n}$. For this, try Dirichlet's convergence test. $\endgroup$ – Ofir Gorodetsky Sep 19 '16 at 12:34
  • 2
    $\begingroup$ Is this research-related? $\endgroup$ – Ofir Gorodetsky Sep 19 '16 at 13:33
  • $\begingroup$ @OfirGorodetsky: yes this question proposed by well-known mathematician prof. M Ram Murthy in the problem section of a six monthly journal "mathstudent" published by Indian Mathematical society. The link you can visit: indianmathsociety.org.in $\endgroup$ – Subhash Chand Bhoria Sep 19 '16 at 14:16
  • $\begingroup$ You can also brute-force it fairly easily by estimating the number of integers up to $n$ for which $n/\varphi(n)>t$. They should be divisible by long products of primes and you can get the bound just by looking at how many primes between $A$ and $2A$ should be there, though I don't think I can fit the corresponding argument into the comment box :-) $\endgroup$ – fedja Sep 19 '16 at 14:43
  1. Show that $$\left( \frac{n}{\phi(n)} \right)^a =\prod_{p \mid n} \left(1 + \frac{1}{p-1} \right)^a \le \prod_{p \mid n} \left(1 + \frac{C}{p} \right) = \sum_{d \mid n} \frac{\mu(d)^2}{d} C^{\Omega(d)}$$ for some explicitly computable constant $C$ depending on $a$.

  2. Bound your sum from above by $$\sum_{d \le x} \lfloor \frac{x}{d} \rfloor \left(\frac{\mu(d)^2}{d} C^{\Omega(d)} \right) \le x\sum_{d \le x} \frac{C^{\Omega(d) }}{d^2}. $$

  3. Finish by noting that $\Omega(d) = O(\frac{\ln d}{\ln \ln d})$ to conclude that $C^{\Omega(d)}$ grows slower than any power of $d$, hence $$\sum_{d\ge 1} \frac{C^{\Omega(d) }}{d^2} < \infty.$$


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.