In this question, the OP asks:

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.

The answers and comments point out how to show the upper bound, but experiment shows that the growth (for any given $a$) is, in fact, linear - here is a graph for $a=1:$ How would one show this?

enter image description here

  • 1
    $\begingroup$ Morally speaking each prime $p$ contributes a factor of about $1 + (a/p^2)$ to the average of $(n/\phi(n))^a$, and the product of those factors converges by comparison with $\zeta(2)^a$. You can probably prove this by setting up the Dirichlet series for $(n/\phi(n))^a$ and showing it has a simple pole at $s=1$ and no other poles in some half-plane containing $1$. $\endgroup$ – Noam D. Elkies Sep 30 '16 at 21:19

A careful analysis of the answer to the linked question will give an asymptotic result instead of an upper bound.

  1. Write $\left( \frac{n}{\phi(n)} \right)^a$ as $\prod_{p \mid n}(1+g(p))=\sum_{d \mid n} g(d)\mu^2(d)$, where $g$ is completely multiplicative and given by $g(p)=\left(1 + \frac{1}{p-1} \right)^a - 1$. Note that $$g(p) \le \frac{2^a-1}{p-1},\quad g(d) \le \frac{\mu^2(d)}{d} (2^{a+1}-2)^{\Omega(d)}.$$

  2. The sum becomes $$\sum_{d \le x} \lfloor \frac{x}{d} \rfloor g(d)\mu^2(d) =x\sum_{d \le x} \frac{g(d)\mu^2(d)}{d} + O\left( \sum_{d\le x} g(d)\mu^2(d) \right) $$ $$\qquad =x\sum_{d} \frac{g(d)\mu^2(d)}{d} + O\left( \sum_{d\le x} g(d)\mu^2(d) \right) + O\left( x\sum_{d>x} \frac{g(d)\mu^2(d)}{d} \right).$$

  3. Finish by noting that $\sum_{d\le x} g(d)\mu^2(d)$ is $o(x)$, and that $\sum_{d>x } \frac{g(d)\mu^2(d)}{d}$ is $o(1)$ (so in particular $C(a):=\sum_{d } \frac{g(d)\mu^2(d)}{d}=\prod_{p} \left( 1+\frac{g(p)}{p}\right)$ converges): $$\Omega(d) = O(\frac{\ln d}{\ln \ln d}) \implies$$ $$\sum_{d\le x} g(d)\mu^2(d) \le \sum_{d\le x} \frac{(2^{a+1}-2)^{O(\frac{\ln d}{\ln \ln d})}}{d} =\sum_{d\le x} O_a\left( \frac{1}{\sqrt{d}} \right) = O_a(\sqrt{x}),$$ $$\sum_{d>x} \frac{g(d)\mu^2(d)}{d} \le \sum_{d>x} \frac{(2^{a+1}-2)^{O(\frac{\ln d}{\ln \ln d})}}{d^2} =\sum_{d>x} O_a\left( \frac{1}{d\sqrt{d}} \right) = O_a(\frac{1}{\sqrt{x}}).$$

See Chapter 2.4 in these notes for similar examples.

Remark: The estimate $\Omega(d) = O\left( \frac{\ln d}{\ln \ln d} \right)$ is elementary - it relies only on the Chebyshev estimates. In fact, one only needs $\Omega(d) = o(\ln d)$, which follows from the fact that $\pi(d) = o(d)$ (zero-density of primes), a classical result already due to Legendre.


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.