Skip to main content
3 of 5
Minor touch-ups and clarification
Alan Haynes
  • 1.7k
  • 12
  • 23

Up to a multiplicative constant the answer is what you discovered, $f(n)=\sqrt{\log\log n}$. Obviously you can assume that $\chi$ is not a principal character since in that case you get something less than $1$. Then after writing $$\sum_{d|n}\frac{\mu (d)\chi(d)}{d}=\prod_{p|n}\left(1-\frac{\chi (p)}{p}\right)$$and taking the logarithm of the RHS the problem boils down to finding an upper bound for the real part of the sum $$\sum_{p|n}\frac{-\chi (p)}{p}.$$ Note that only the real part of this expression is important to us, since we are going to exponentiate in the end to get back to the original problem (i.e. we are only interested in bounding the modulus of the resulting complex number).

Since $\chi$ is not principal, the values of $\chi (d)$ are symmetric about the imaginary axis. Therefore the worst thing that could happen in the previous sum is to have half of the values equal to $-1$ (e.g. use the Legendre symbol modulo some prime $q$) and then suppose that $n$ is a product of all primes up to some point which fall in the residue classes $d$ for which $\chi (d)=-1$. By Dirichlet's Theorem this accounts for half of the primes, evenly distributed in the various residue classes, and translating everything back to the original formulation gives the upper bound $\sqrt{\log\log n}$. If you want to see the details of how to carry out this final calculation then I can provide them, but from your example it looks like you already understand how that part of the argument works.

Alan Haynes
  • 1.7k
  • 12
  • 23