Character sum (${\sum }_{n\in S}\chi (n)$)

A sum of character values over a set. Arithmetic cancellation, rather than the termwise absolute-value bound, is the useful feature. A Gauss sum of a Dirichlet character is a weighted example, and the Pólya–Vinogradov inequality bounds interval sums.

For a primitive nonprincipal Dirichlet character modulo $q$, finite Fourier inversion theorem and the primitive Gauss magnitude give this bound uniformly in the interval. Bound the exponential sums by $C\Vert a/q{\Vert }^{-1}$ and sum the resulting harmonic series. The general Gauss identity follows from the prime-power identity by the Chinese remainder theorem.