MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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,


share|cite|improve this question
up vote 6 down vote accepted

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

share|cite|improve this answer
One needs to be careful here. I think this is a valid proof that $\phi_\chi(n)/n \ll_\chi \sqrt{\log\log n}$; however, the implicit constant will depend upon $\chi$. Given $n$, one can find a Dirichlet character $\chi$ such that all the small primes $p$ have $\chi(p)=-1$. The resulting construction shows that no bound better than $\phi_\chi(n)/n \ll \log\log n$ can hold uniformly over $n$ and $\chi$. – Greg Martin Dec 3 '11 at 8:18
(Also I don't understand what you mean by "the values of $\chi(d)$ are symmetric about the imaginary axis". If $\chi$ is a cubic character then its values are $-\frac12\pm\frac{\sqrt{3}}2i$ and $1$, which does not have that symmetry; the same is true of any odd-order character.) – Greg Martin Dec 3 '11 at 8:20
I agree with your first comment- I thought about that before I went to sleep last night and I think you are correct. I believe what you claim, but would you mind explaining how to construct a Dirichlet character with the property you mention? – Alan Haynes Dec 3 '11 at 9:19
@Greg Your second comment is relevant but not as crucial. Certainly if you have an odd character then what I said about the symmetry is true. Otherwise you can still argue the same way- the worst case scenario is to have as many −1's as possible, but by orthogonality this can be at most 1/2 of the residue classes. I'll edit this to make it (hopefully) correct. Thanks for your comments, it is a fun problem. – Alan Haynes Dec 3 '11 at 9:26

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.