Polya-Vinogradov best constant (squarefree asymptotic)

Description of constant

Let $\chi$ be a primitive Dirichlet character modulo $q$, and define

$$S(\chi ):=\underset{N\le q}{\max }\left|\sum _{1\le n\le N}\chi (n)\right|.$$

The Polya-Vinogradov inequality states that

$$S(\chi )\le c\sqrt{q}\log q$$

for some absolute constant $c$.

<a href="#BK2020-def-PV">[BK2020-def-PV]</a>

For squarefree moduli, define $C_{72}^{\mathrm{even}}$ (resp. $C_{72}^{\mathrm{odd}}$) as the infimum of all $c$ such that

$$S(\chi )\le (c+o(1))\sqrt{q}\log q\text{as }q\to \infty$$

for every primitive even (resp. odd) character $\chi$ modulo squarefree $q$. Define

$$C_{72}:=\max \{C_{72}^{\mathrm{even}},C_{72}^{\mathrm{odd}}\}.$$

Bordignon and Kerr proved, for squarefree $q$, that one can take

$$c=\frac{1}{2{\pi }^2}+o(1)\text{(even)},c=\frac{1}{4\pi }+o(1)\text{(odd)}.$$

<a href="#BK2020-main-constants">[BK2020-main-constants]</a>

Hence

$$C_{72}\le \frac{1}{4\pi }.$$

Known upper bounds

Known lower bounds

Additional comments and links

• The best known asymptotic leading constants differ between even and odd characters in the squarefree setting. <a href="#BK2020-main-constants">[BK2020-main-constants]</a>

• BK2020 identifies Frolenkov-Soundararajan as the previous sharpest explicit benchmark and improves it (for large $q$) in the squarefree setting. <a href="#BK2020-prev-best">[BK2020-prev-best]</a> <a href="#FS2013">[FS2013]</a>

• A follow-up by Bordignon gives fully explicit constants for all primitive moduli, namely $3/(4{\pi }^2)+o_q(1)$ (even) and $3/(8\pi )+o_q(1)$ (odd), improving Frolenkov-Soundararajan for large $q$. <a href="#B2022-main">[B2022-main]</a>

• Kerr obtains a cubefree-modulus bound with leading constant $1/{\pi }^2$ for arbitrary intervals; this is weaker than BK2020 in the squarefree setting but still relevant context. <a href="#Kerr2020-main">[Kerr2020-main]</a>

• Wikipedia page on the Polya-Vinogradov inequality

References

• <a id="BK2020"></a>[BK2020] Bordignon, Matteo; Kerr, Bryce. An explicit Polya-Vinogradov inequality via Partial Gaussian sums. Transactions of the American Mathematical Society 373 (2020), no. 9, 6503-6527. DOI: https://doi.org/10.1090/tran/8138. arXiv PDF: https://arxiv.org/pdf/1909.01052.pdf. Google Scholar
• <a id="BK2020-def-PV"></a>[BK2020-def-PV] loc: arXiv PDF p.1, Introduction, definition of $S(\chi )$ and displayed inequality (1) quote: "Given two integers $N$, $q$ and a primitive character $\chi$ modulo $q$ consider the sums $S(\chi ):={\max }_{N\le q}\left|{\sum }_{1\le n\le N}\chi (n)\right|$. A bound, proven independently by Polya and Vinogradov in the early 1900s, is the following $S(\chi )\le c\sqrt{q}\log q$ for some absolute constant $c$."
• <a id="BK2020-main-constants"></a>[BK2020-main-constants] loc: arXiv PDF p.1, Abstract quote: "Given a primitive character $\chi$ to squarefree modulus $q$, we prove the following upper bound $\left|{\sum }_{1\le n\le N}\chi (n)\right|\le c\sqrt{q}\log q$, where $c=1/(2{\pi }^2)+o(1)$ for even characters and $c=1/(4\pi )+o(1)$ for odd characters, with an explicit $o(1)$ term."
• <a id="BK2020-prev-best"></a>[BK2020-prev-best] loc: arXiv PDF p.4, Introduction, paragraph beginning "Fully explicit Pólya-Vinogradov inequalities have previously been considered ..." quote: "Fully explicit Pólya-Vinogradov inequalities have previously been considered by Frolenkov [15], Frolenkov and Soundararajan [16] and Pomerance [27]. The current sharpest result is Frolenkov and Soundararajan [16]."

• <a id="B2022"></a>[B2022] Bordignon, Matteo. Partial Gaussian sums and the Pólya-Vinogradov inequality for primitive characters. Revista Matemática Iberoamericana 38 (2022), no. 4, 1101-1127. DOI: https://doi.org/10.4171/RMI/1328. Google Scholar
• <a id="B2022-main"></a>[B2022-main] loc: journal PDF p.1101 (first page), Abstract quote: "In this paper we obtain a new fully explicit constant for the Pólya-Vinogradov inequality for primitive characters. Given a primitive character $\chi$ modulo $q$, we prove the following upper bound $\left|{\sum }_{1\le n\le N}\chi (n)\right|\le c\sqrt{q}\log q$, where $c=3/(4{\pi }^2)+o_q(1)$ for even characters and $c=3/(8\pi )+o_q(1)$ for odd characters, with explicit $o_q(1)$ terms. This improves a result of Frolenkov and Soundararajan for large $q$."

• <a id="Kerr2020"></a>[Kerr2020] Kerr, Bryce. On the constant in the Pólya-Vinogradov inequality. Journal of Number Theory 212 (2020), 265-284. DOI: https://doi.org/10.1016/j.jnt.2019.11.003. arXiv PDF: https://arxiv.org/pdf/1807.09573.pdf. Google Scholar
• <a id="Kerr2020-main"></a>[Kerr2020-main] loc: arXiv source Polya-Vinogradov_-_constant.tex, Section 2 (Main result), Theorem 1 quote: "For integer $q$ we define c=\begin{cases} \frac{1}{4} \quad \text{if q is cubefree}, \\ \frac{1}{3} \quad \text{otherwise}. \end{cases} For any primitive character $\chi \mathrm{mod}q$ and integers $M$ and $N$ we have $\left|{\sum }_{M<n<M+N}\chi (n)\right|\le (1+o(1))\frac{4c}{{\pi }^2}{q}^{1/2}\log q.$"

• <a id="Pom2011"></a>[Pom2011] Pomerance, Carl. Remarks on the Pólya-Vinogradov Inequality. Integers 11A (2011), Article A19. DOI: https://doi.org/10.1515/integ.2011.039. PDF: https://math.colgate.edu/~integers/a16int2009/a16int2009.pdf. Google Scholar
• <a id="Pom2011-thm1"></a>[Pom2011-thm1] loc: Integers PDF p.3, Theorem 1 quote: "For $\chi$ a primitive character to the modulus $q>1$, we have $S(\chi )\le \frac{2}{{\pi }^2}{q}^{1/2}\log q+\frac{4}{{\pi }^2}{q}^{1/2}\log \log q+\frac{3}{2}{q}^{1/2}$ if $\chi$ is even, and $S(\chi )\le \frac{1}{2\pi }{q}^{1/2}\log q+\frac{1}{\pi }{q}^{1/2}\log \log q+q^{1/2}$ if $\chi$ is odd."

• <a id="FS2013"></a>[FS2013] Frolenkov, D. A.; Soundararajan, K. A generalization of the Pólya-Vinogradov inequality. The Ramanujan Journal 31 (2013), no. 3, 271-279. DOI: https://doi.org/10.1007/s11139-012-9462-y. Google Scholar

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.