Let $N$ and $a$ be positive integers. Consider the Kronecker symbol $\left( \frac{n}{m} \right)$, which is a character modulo $m$. I have seen it several times that 'by Polya-Vinogradov inequality', we have $$ \sum_{0<n\leq Y, n \equiv a (N)} \left(\frac{n}{m}\right) \ll \sqrt m \log m. $$

However, the sum is not over consecutive integers, so I think this is not a trivial fact. How can I prove this?

  • $\begingroup$ Is the implied constant supposed to be independent of $N$? If so, then it seems like you have a problem with $m=N$. If not, then it seems like you can get a bound of size something like $N^{3/2} \sqrt m \log m$ by using orthogonality relations to select $a \pmod N$. $\endgroup$ – Erick Wong Aug 4 at 7:09
  • $\begingroup$ Erick Wong // What is 'orthogonality relations'? $\endgroup$ – LWW Aug 4 at 7:12
  • 1
    $\begingroup$ Erick is suggesting writing $$\sum_{\substack{n\le y \\ n\equiv a\pmod N}} \bigg( \frac nm \bigg) = \frac1{\phi(N)} \sum_{\chi\pmod N} \overline\chi(a) \sum_{n\le y} \chi(n) \bigg( \frac nm \bigg);$$ the inner sum is a character sum (of a character modulo $mN$) over an interval. $\endgroup$ – Greg Martin Aug 4 at 7:50
  • $\begingroup$ Martin // Thank you, Martin. Could you let me know the reason why the equation hold, or any reference? $\endgroup$ – LWW Aug 4 at 8:18
  • $\begingroup$ Martin // Now I understand. Thank you. $\endgroup$ – LWW Aug 4 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.