Pólya-Vinogradov Inequality

Let $\chi$ be a nonprincipal character (mod $q$). Then

$$\sum_{n=M+1}^{M+N} \chi(n)\ll \sqrt{q}\,\ln q,$$

where $\ll$ indicates Much Less than.

References

Davenport, H. ``The Pólya-Vinogradov Inequality.'' Ch. 23 in Multiplicative Number Theory, 2nd ed. New York: Springer-Verlag, pp. 135-138, 1980.

Pólya, G. ``Über die Verteilung der quadratischen Reste und Nichtreste.'' Nachr. Königl. Gesell. Wissensch. Göttingen, Math.-Phys. Klasse, 21-29, 1918.