# Polya-Vinogradov inequality over non-consecutive integers

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

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

• 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$. – Erick Wong Aug 4 at 7:09
• Erick Wong // What is 'orthogonality relations'? – LWW Aug 4 at 7:12
• 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. – Greg Martin Aug 4 at 7:50
• Martin // Thank you, Martin. Could you let me know the reason why the equation hold, or any reference? – LWW Aug 4 at 8:18
• Martin // Now I understand. Thank you. – LWW Aug 4 at 10:21