2
$\begingroup$

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.

$\endgroup$
4
  • 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$ Sep 19, 2016 at 12:34
  • 2
    $\begingroup$ Is this research-related? $\endgroup$ Sep 19, 2016 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$ Sep 19, 2016 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, 2016 at 14:43

1 Answer 1

3
$\begingroup$
  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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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