The TME-EMT project
Home > Projet TME-EMT > Character sums
Character sums
1. Explicit Polya-Vinogradov inequalities
The main Theorem of [
Qiu, 1991 †Qiu, Zhuo Ming. 1991
An inequality of Vinogradov for character sums
Shandong Daxue Xuebao Ziran Kexue Ban, 26(1), 125--128.]
implies the following result.
Theorem (1991)
For $\chi$ a primitive character to the modulus $q > 1$, we have
$
\left|\sum\limits_{a=M+1}^{M+N}\chi(a)\right|
\le
\frac{4}{\pi^2}\sqrt{q}\log q+0.38\sqrt{q}+\frac{0.637}{\sqrt{q}}
$.
When $\chi$ is not especially primitive, but is still non-principal, we
have
$
\left|\sum\limits_{a=M+1}^{M+N}\chi(a)\right|
\le
\frac{8\sqrt{6}}{3\pi^2}\sqrt{q}\log q+0.63\sqrt{q}+\frac{1.05}{\sqrt{q}}
$.
This was improved later by
[
Bachman & Rachakonda, 2001 †Bachman, Gennady, & Rachakonda, Leelanand. 2001
On a problem of Dobrowolski and Williams and the Pólya-Vinogradov inequality
Ramanujan J., 5(1), 65--71.] into
the following.
Theorem (2001)
For $\chi$ a non-principal character to the modulus $q > 1$, we have
$
\left|\sum\limits_{a=M+1}^{M+N}\chi(a)\right|
\le
\frac{1}{3\log 3}\sqrt{q}\log q+6.5\sqrt{q}
$.
These results are superseded by
[
Frolenkov, 2011 †Frolenkov, D. 2011
A numerically explicit version of the Pólya-Vinogradov inequality
Mosc. J. Comb. Number Theory, 1(3), 25--41.] and more
recently by
[
Frolenkov & Soundararajan, 2013 †Frolenkov, D. A., & Soundararajan, K. 2013
A generalization of the Pólya--Vinogradov inequality
Ramanujan J., 31(3), 271--279.] into
the following.
Theorem (2013)
For $\chi$ a non-principal character to the modulus $q\ge 1000$, we have
$
\left|\sum\limits_{a=M+1}^{M+N}\chi(a)\right|
\le
\frac{1}{\pi\sqrt{2}}\sqrt{q}(\log q+6)+\sqrt{q}
$.
In the same paper they improve upon estimates of
[
Pomerance, 2011 †Pomerance, C. 2011
Remarks on the Pólya-Vinogradov inequality
Integers (Proceedings of the Integers Conference, October 2009), 11A, Article 19, 11pp.] and get the following.
Theorem (2013)
For $\chi$ a primitive character to the modulus $q \ge 1200$, we have
$$
\max_{M,N}\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le
\begin{cases}
\frac{2}{\pi^2}\sqrt{q}\log q+\sqrt{q},&
\text{$\chi$ even,}\\
\frac{1}{2\pi}\sqrt{q}\log q+\sqrt{q},&
\text{$\chi$ odd}.
\end{cases}
$$
This latter estimates holds as soon as $q\ge40$.
In case $\chi$ odd, the constant $1/(2\pi)$ has already
been asymptotically obtained in
[
Landau, 1918 †Landau, E. 1918
Abschätzungen von Charaktersummen, Einheiten und Klassenzahlen
Gött. Nachr., 2, 79--97.].
When $\chi$ is odd and $M=1$, the best asymptotical constant before 2020 was
$1/(3\pi)$ from Theorem 7 of
[
Granville & Soundararajan, 2007 †Granville, A., & Soundararajan, K. 2007
Large character sums: pretentious characters and the Pólya-Vinogradov theorem
J. Amer. Math. Soc., 20(2), 357--384 (electronic).],
In case $\chi$ even, we have
$$
\max_{M,N}\left|\sum_{a=M}^N\chi(a)\right|
=2\max_{N}\left|\sum_{a=1}^N\chi(a)\right|.
$$
(The LHS is always less than the RHS. Equality is then easily proved).
The asymptotical best constant in 2007
was $23/(35\pi\sqrt{3})$ from Theorem 7 of
[
Granville & Soundararajan, 2007 †Granville, A., & Soundararajan, K. 2007
Large character sums: pretentious characters and the Pólya-Vinogradov theorem
J. Amer. Math. Soc., 20(2), 357--384 (electronic).].
These results are improved upon for large values squarefree values of $q$ in
[
Bordignon & Kerr, 2020 †Bordignon, Matteo, & Kerr, Bryce. 2020
An explicit Pólya-Vinogradov inequality via partial Gaussian sums
Trans. Amer. Math. Soc., 373(9), 6503--6527.]
by a different method into the following.
Theorem (2020)
For $\chi$ a primitive character to the squarefree modulus $q \ge \exp(1088\ell^2)$, we have
$$
\max_{N}\left|\sum_{a=1}^{N}\chi(a)\right|
\le
\begin{cases}
\frac{2}{\pi^2}\sqrt{q}\bigl(\frac14+\frac{1}{4\ell}\bigr)\log q
+\bigl(49+\frac{1}{1088\ell}\bigr)\sqrt{q},&
\text{$\chi$ even,}\\
\frac{1}{2\pi}\bigl(\frac12+\frac{1}{2\ell}\bigr)\sqrt{q}\log q
+\bigl(49+\frac{1}{1088\ell}\bigr)\sqrt{q},&
\text{$\chi$ odd}.
\end{cases}
$$
This latter estimates holds as soon as $q\ge40$.
Corresponding estimates when $q$ is not squarefree are proved in
[
Bordignon, 2021 †Bordignon, Matteo. 2021
A Pólya-Vinogradov inequality for short character sums
Canad. Math. Bull., 64(4), 906--910.], the
saving $1/4$ being slightly degraded to $3/8$.
2. Burgess type estimates
The following from
[
Treviño, 2015a †Treviño, Enrique. 2015a
The Burgess inequality and the least {$k$}th power non-residue
Int. J. Number Theory, 11(5), 1653--1678.]
is an explicit version of Burgess with the only restriction being
$p\ge 10^7$.
Theorem (2015)
Let $p$ be a prime such that $p \ge 10^7$. Let $\chi$ be a non-principal character $\bmod{\,p}$. Let $r$ be a positive integer, and let $M$ and $N$ be non-negative integers with $N\ge 1$. Then
$$
\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le 2.74 N^{1-\frac{1}{r}}
p^{\frac{r+1}{4r^2}}(\log{p})^{\frac{1}{r}}.
$$
From the same paper, we get the following more specific result.
Theorem (2015)
Let $p$ be a prime. Let $\chi$ be a non-principal character
$\bmod{\,p}$. Let $M$ and $N$ be non-negative integers with $N\ge 1$,
let $2\le r\le 10$ be a positive integer, and let $p_0$ be a positive
real number. Then for $p \ge p_0$, there exists $c_1(r)$, a constant
depending on $r$ and $p_0$ such that
$$
\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le
c_1(r) N^{1-\frac{1}{r}} p^{\frac{r+1}{4r^2}}(\log{p})^{\frac{1}{r}}
$$
where $c_1(r)$ is given by
|
---|
$r$ |
$p_0=10^7$ |
$p_0=10^{10}$ |
$p_0=10^{20}$ |
2 |
2.7381 |
2.5173 |
2.3549 |
3 |
2.0197 |
1.7385 |
1.3695 |
4 |
1.7308 |
1.5151 |
1.3104 |
5 |
1.6107 |
1.4572 |
1.2987 |
6 |
1.5482 |
1.4274 |
1.2901 |
7 |
1.5052 |
1.4042 |
1.2813 |
8 |
1.4703 |
1.3846 |
1.2729 |
9 |
1.4411 |
1.3662 |
1.2641 |
10 |
1.4160 |
1.3495 |
1.2562 |
We can get a smaller exponent on $\log$ if we restrict the range of
$N$ or if we have $r\ge 3$.
Theorem (2015)
Let $p$ be a prime. Let $\chi$ be a non-principal character
$\bmod{\,p}$. Let $M$ and $N$ be non-negative integers with $1\le N\le
2 p^{\frac{1}{2} + \frac{1}{4r}}$ or $r\ge 3$. Let $r\le 10$ be a
positive integer, and let $p_0$ be a positive real number. Then for $p
\ge p_0$, there exists $c_2(r)$, a constant depending on $r$ and $p_0$
such that
$$
\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le
c_2(r) N^{1-\frac{1}{r}} p^{\frac{r+1}{4r^2}}(\log{p})^{\frac{1}{2r}},
$$
where $c_2(r)$ is given by
|
---|
$r$ |
$p_0=10^7$ |
$p_0=10^{10}$ |
$p_0=10^{20}$ |
2 |
3.7451 |
3.5700 |
3.5341 |
3 |
2.7436 |
2.5814 |
2.4936 |
4 |
2.3200 |
2.1901 |
2.1071 |
5 |
2.0881 |
1.9831 |
1.9037 |
6 |
1.9373 |
1.8504 |
1.7748 |
7 |
1.8293 |
1.7559 |
1.6843 |
8 |
1.7461 |
1.6836 |
1.6167 |
9 |
1.6802 |
1.6262 |
1.5638 |
10 |
1.6260 |
1.5786 |
1.5210 |
Kevin McGown in
[
McGown, 2012 †McGown, Kevin J. 2012
Norm-Euclidean cyclic fields of prime degree
Int. J. Number Theory, 8(1), 227--254.]
has slightly worse constants in a slightly larger range of $N$ for
smaller values of $p$.
Theorem (2012)
Let $p\ge 2\cdot 10^{4}$ be a prime number. Let $M$ and $N$ be
non-negative integers with $1\le N\le 4 p^{\frac{1}{2} +
\frac{1}{4r}}$. Suppose $\chi$ is a non-principal character
$\bmod{\,p}$. Then there exists a computable constant $C(r)$ such that
$$
\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le
C(r) N^{1-\frac{1}{r}} p^{\frac{r+1}{4r^2}}(\log{p})^{\frac{1}{2r}},
$$
where $C(r)$ is given by
|
---|
$r$ |
$C(r)$ |
$r$ |
$C(r)$ |
2 |
10.0366 |
9 |
2.1467 |
3 |
4.9539 |
10 |
2.0492 |
4 |
3.6493 |
11 |
1.9712 |
5 |
3.0356 |
12 |
1.9073 |
6 |
2.6765 |
13 |
1.8540 |
7 |
2.4400 |
14 |
1.8088 |
8 |
2.2721 |
15 |
1.7700 |
If the character is quadratic (and with a more restrictive
range), we have slightly stronger results due to Booker in
[
Booker, 2006 †Booker, A.R. 2006
Quadratic class numbers and character sums
Math. Comp., 75(255), 1481--1492 (electronic).].
Theorem (2006)
Let $p > 10^{20}$ be a prime number with $p \equiv 1 \pmod{4}$. Let
$r\in \{2,3,4,\ldots,15\}$. Let $M$ and $N$ be real numbers such that
$0 < M , N \le 2\sqrt{p}$. Let $\chi$ be a non-principal quadratic
character $\bmod{\,p}$. Then
$$
\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le \alpha(r) N^{1-\frac{1}{r}} p^{\frac{r+1}{4r^2}}\left(\log{p} +
\beta(r)\right)^{\frac{1}{2r}},
$$
where $\alpha(r)$ and $\beta(r)$ are given by
|
---|
$r$ |
$\alpha(r)$ |
$\beta(r)$ |
$r$ |
$\alpha(r)$ |
$\beta(r)$ |
2 |
1.8221 |
8.9077 |
9 |
1.4548 |
0.0085 |
3 |
1.8000 |
5.3948 |
10 |
1.4231 |
-0.4106 |
4 |
1.7263 |
3.6658 |
11 |
1.3958 |
-0.7848 |
5 |
1.6526 |
2.5405 |
12 |
1.3721 |
-1.1232 |
6 |
1.5892 |
1.7059 |
13 |
1.3512 |
-1.4323 |
7 |
1.5363 |
1.0405 |
14 |
1.3328 |
-1.7169 |
8 |
1.4921 |
0.4856 |
15 |
1.3164 |
-1.9808 |
Concerning composite moduli, we have the next result in
[
Jain-Sharma et al., 2021 †Jain-Sharma, Niraek, Khale, Tanmay, & Liu, Mengzhen. 2021
Explicit Burgess bound for composite moduli
Int. J. Number Theory, 17(10), 2207--2219.]
.
Theorem (2021)
Let $\chi$ be a primitive character with modulus $q\ge e^{e^{9.594}}$.
Then for $N\le q^{5/8}$, we have
$$
\left|\sum_{a=M+1}^{M+N}\chi(a)\right|
\le 9.07 \sqrt{N}q^{3/16}(\log q)^{1/4}
\bigl(2^{\omega(q)}d(q)\bigr)^{3/4}
\sqrt{\frac{q}{\varphi(q)}}.
$$
Last updated on December 11th, 2021, by Olivier Ramaré