MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

It is known that $$\sum_{p\leq x}\bigg(\frac{q}{p}\bigg)=o(\pi(x))$$for any $q$ which is not a square. Is there some references on such a character sum (summation over the moduli)?

Of course, by quadratic reciprocity law, it can be transformed to consider the following sum $$\sum_{p\leq x}\bigg(\frac{p}{q}\bigg).$$ By Perron's formula and some results of Dirichlet $L$-functions, we can of course obtain an upper bound. I want to know whether there is certain elementary proof.

share|cite|improve this question
Also true when $q=1$ ? – Luis H Gallardo Jan 11 '11 at 8:31
Sorry $q=1$ is a square ! – Luis H Gallardo Jan 11 '11 at 8:33
What are your objections to using Perron's formula? – Micah Milinovich Jan 11 '11 at 16:04
For example, to estimate the related sum $\sum_{n\leq x}\Lambda(n)\chi(n)$, Perron's formula allows us to calculate certain mean value of L-functions to obtain the upper bound of the character sum – arithboy Jan 12 '11 at 2:10
I found we can apply Dirichlet's PNT in arithmetic progressions to get an easier proof. However, this is not elementary and direct enough. – arithboy Jan 12 '11 at 2:13

Let's take the case where $q=-1$. Then your sum is the difference between the number of primes up to $x$ that are $4n+1$ and the number that are $4n-1$. I suspect that information on that difference, of the strength you require, is available only via the Prime Number Theorem for arithmetic progressions.

share|cite|improve this answer

In fact, $$\sum_{p\leq x}\left(\frac{p}{q}\right)=\sum_{a\bmod q}\left(\frac{a}{q}\right)\pi(x;q,a).$$ For sufficiently large $x$, we have $$\pi(x;q,a)=\frac{1}{\varphi(q)}(1+o(1))\pi(x),$$where the $o$ constant depends on $q$, thus $$\sum_{p\leq x}\left(\frac{p}{q}\right)=\frac{1}{\varphi(q)}\sum_{a\bmod q}\left(\frac{a}{q}\right)(1+o(1))\pi(x)=o(\pi(x)).$$

Of course, I expect a more elementary proof, which doesn't rely on the PNT in arithmetic progressions.

share|cite|improve this answer
But what makes you think such a thing is possible? The question is so close to PNT-for-AP, especially in the case $q=-1$ in the answer I posted, that it's hard to imagine an elementary solution that doesn't amount to an elementary proof of PNT-for-AP. And if what you're really after is an elementary proof of PNT-for-AP, well, then that's what you should really be asking for. – Gerry Myerson Jan 13 '11 at 11:51
Dear Myerson, I quite agree with what you have said. This problem must be related to the distribution of prime numbers, in AP for instance. However, I am looking for an alternative proof for the estimate, not relying on PNT in AP, maybe this requires certain subtle facts on primes. BTW, for the elementary proof for PNT in AP, I know there is one due to Selberg, are there any others? – arithboy Jan 13 '11 at 13:50

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.