character sum

In mathematics, a character sum is a sum $\sum \chi(n)$ 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 non-principal Dirichlet character to the modulus N.

Sums over ranges

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

: $M \le n < M + R.$

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

: $\Sigma = O(\sqrt{N}\log N).$

Assuming the generalized Riemann hypothesis, Hugh Montgomery and R. C. Vaughan have shown{{sfn|Montgomery|Vaughan|1977}} that there is the further improvement

: $\Sigma = O(\sqrt{N}\log\log N).$

Summing polynomials

Another significant type of character sum is that formed by

: $\sum \chi(F(n))$

for some function F, generally a polynomial. A classical result is the case of a quadratic, for example,

: $F(n) = n(n + 1)$

and χ a Legendre symbol. Here the sum can be evaluated (as −1), a result that is connected to the local zeta-function of a conic section.

More generally, such sums for the Jacobi symbol relate to local zeta-functions of elliptic curves and hyperelliptic curves; this means that by means of André Weil's results, for N = p a prime number, there are non-trivial bounds

: $O(\sqrt{p}).$

The constant implicit in the notation is linear in the genus of the curve in question, and so (Legendre symbol or hyperelliptic case) can be taken as the degree of F. (More general results, for other values of N, can be obtained starting from there.)

Weil's results also led to the Burgess bound,{{sfn|Burgess|1957}} applying to give non-trivial results beyond Pólya–Vinogradov, for R a power of N greater than 1/4.

Assume the modulus N is a prime.

: $\begin{align}
\Sigma & \ll p^{1/2} \log p , \\[6pt]
\Sigma & \ll 2 R^{1/2} p^{3/16} \log p , \\[6pt]
\Sigma & \ll r R^{1-1/r} p^{(r+1)/4r^2} (\log p)^{1/2r}
\end{align}$

for any integer r ≥ 3.{{sfn|Montgomery|Vaughan|2007|loc=p. 315}}

Notes

References

{{cite journal | last=Pólya |first=George | authorlink=George Pólya | title=Ueber die Verteilung der quadratischen Reste und Nichtreste | journal=Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen | year=1918 | pages=21–29 | jfm=46.0265.02 }}
{{cite journal | last=Vinogradov |first=Ivan Matveyevich | authorlink=Ivan Matveyevich Vinogradov | title=Sur la distribution des residus and nonresidus des puissances | journal=J. Soc. Phys. Math. Univ. Permi | year=1918 | pages=18–28 | jfm=48.1352.04 }}
{{cite journal | doi=10.1112/S0025579300001157 | last1=Burgess | first1=D. A. | title=The distribution of quadratic residues and non-residues | journal=Mathematika | volume=4 | issue=2 | year=1957 | pages=106–112 | zbl=0081.27101 }}
{{cite journal | last1=Montgomery | first1=Hugh L. | authorlink=Hugh Montgomery (mathematician) |last2=Vaughan | first2=Robert C. |authorlink2=Robert Charles Vaughan (mathematician) | title=Exponential sums with multiplicative coefficients | journal=Inventiones Mathematicae | volume=43 | year=1977 | issue=1 | pages=69–82 | doi=10.1007/BF01390204 | bibcode=1977InMat..43...69M | doi-access=free | zbl=0362.10036 | url=https://deepblue.lib.umich.edu/bitstream/2027.42/46603/1/222_2005_Article_BF01390204.pdf | hdl=2027.42/46603 | hdl-access=free }}
{{cite book | last1=Montgomery | first1=Hugh L. | authorlink=Hugh Montgomery (mathematician) |last2=Vaughan | first2=Robert C. |authorlink2=Robert Charles Vaughan (mathematician) | title=Multiplicative number theory I. Classical theory | series=Cambridge tracts in advanced mathematics | volume=97 | publisher=Cambridge University Press | year=2007 | isbn=978-0-521-84903-6 | zbl=1142.11001 | pages=306–325}}

External links

{{MathWorld|urlname=Polya-VinogradovInequality| title=The Pólya–Vinogradov inequality}}
[https://web.archive.org/web/20050207212539/http://planetmath.org/encyclopedia/PolyaVinogradovInequality.html PlanetMath article on the Pólya–Vinogradov inequality]

Category:Analytic number theory