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 GorodetskySep 19, 2016 at 12:34
-
2$\begingroup$ Is this research-related? $\endgroup$– Ofir GorodetskySep 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$– Subhash Chand BhoriaSep 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$– fedjaSep 19, 2016 at 14:43
1 Answer
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$.
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}. $$
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.$$