Loading [MathJax]/extensions/jsMath2jax.js

     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é