Let $\chi$ be a Dirichlet character, and define $\phi_\chi (n)$ so that it satisfies $$\sum_{n=1}^\infty \phi_\chi (n)n^{-s}=\frac{\zeta(s-1)}{L(s,\chi)}.$$
In other words
$$\phi_{\chi}(n)=\sum_{d|n}\mu\left(\frac{n}{d}\right)\chi\left(\frac{n}{d}\right)d=\left(\text{Id}*\mu\chi\right)(n).$$
My question is, how large can $\phi_\chi(n)$ be? More precisely, what is the smallest function $f$ such that for all $n$ and $\chi$ $$\frac{\phi_{\chi}(n)}{n}=\sum_{d|n}\frac{\mu(d)\chi(d)}{d}\ll f(n).$$
It is not hard to see that $\frac{\phi_{\chi}(n)}{n}\ll \log n$ for all $n$ so $f\ll \log n$. For Euler's $\phi$ function, the first term is the main contributor, as $\phi(n)\leq n$ we know that $\frac{\phi(n)}{n}\leq 1$ for all $n$. Since $\chi$ has norm $1$, and the sums $\sum_{n\leq x}\mu(n)\chi(n)$ are small, we might
conjecture that $\frac{\phi_\chi (n)}{n}\leq 1$.
However this is not so. We can find a character such that $\mu$ and $\chi$ function have a lot of correlation, enough to make the sum of size $\sqrt{\log\log n}$. This is outlined by the following construction:
Let $n$ be the product of all primes $p=3+4k$ where $p\leq M$, and let $\chi$ be the unique quadratic character modulo $4$. Then choose whether or not to remove the prime $3$ from this product as to force the equivalence $n\equiv 1 \pmod{4}$. For each divisor $d$ of $n$, if $\omega(d)$ is even, then $d\equiv 1\pmod{4}$ so that $\chi(d)\mu(d)=1$, and if $\omega(d)$ is odd, then $d\equiv 3\pmod{4}$ so that $\chi(d)\mu(d)=1$ yet again. This means that $$\frac{\phi_\chi (n)}{n}=\sum_{d|n} \frac{1}{d}\gg \sqrt{\log M}\gg\sqrt{\log \log n}.$$ The second last $\gg$ follows from the fact that if $A$ is the set of integers composed only of primes congruent to $3$ modulo $4$, then $\sum_{n\leq M,\ n\in A} \frac{1}{n}=\sqrt{\log M}$, and the last $\gg$ follows from the fact that $\log n =\theta(M;4,3)$.
Any references to papers which might deal with this sort of sum is greatly appreciated,
Thanks,
Best Answer
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 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$. Keep in mind that you can't have more than $1/2$ of the values equal to $-1$, because of the orthogonality relations.
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.
Final note: As Greg pointed out below this bound is not uniform in $\chi$. The best bound in general is $\log\log n$, which is achieved by letting $n$ run through the sequence of primorials and simultaneously letting $\chi_n$ run through a sequence of characters which take the value $-1$ at all primes dividing $n$.