Character sum

In mathematics, a character sum is a sum

of values of a Dirichlet character χ modulo N, taken over a given range of values of n. Such sums are basic in a number of questions, for example in the distribution of quadratic residues, and in particular in the classical question of finding an upper bound for the least quadratic non-residue modulo N. Character sums are often closely linked to exponential sums by the Gauss sums (this is like a finite Mellin transform).

Assume χ is a nonprincipal Dirichlet character to the modulus N.

The sum taken over all residue classes mod N is then zero. This means that the cases of interest will be sums ${\displaystyle \Sigma }$ over relatively short ranges, of length R < N say,

A fundamental improvement on the trivial estimate ${\displaystyle \Sigma =O(N)}$ is the Pólya–Vinogradov inequality (George Pólya, I. M. Vinogradov, independently in 1918), stating in big O notation that

...
Wikipedia