Return to 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 to address Greg's first comment below: This bound is not uniform in $\chi$. Perhaps in general it is not possible to do better than $\log\log n$. Therefore this is not the complete answer to the problem!

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$.

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.

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 to address Greg's first comment below: This bound is not uniform in $\chi$. Perhaps in general it is not possible to do better than $\log\log n$. Therefore this is not the complete answer to the problem!

I think the answer (up to a multiplicative constant) 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}.$$ The values of $\chi (d)$ are symmetric about the imaginary axis so the worst thing that could happen here 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 the final calculation then I can provide them, but from your example it looks like you already understand how that part of the argument works.

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.