Polya-Vinogradov best constant (squarefree asymptotic)

Description of constant

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

$S (χ) := N \leq q max 1 \leq n \leq N \sum χ (n) .$

The Polya-Vinogradov inequality states that

$S (χ) \leq c q lo g q$

for some absolute constant $c$ .

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

$S (χ) \leq (c + o (1)) q lo g q as q \to \infty$

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

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

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

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

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

Hence

$C_{72} \leq \frac{1}{4 π} .$

Known upper bounds

Bound	Reference	Comments
$\frac{2}{π ^{2}}$	[[Pom2011](#Pom2011)]	Primitive characters, explicit inequality; asymptotically this gives $c = 2/ π^{2}$ (even) and $c = 1/ (2 π)$ (odd), so $C_{72} \leq 2/ π^{2}$ . <a href="#Pom2011-thm1">[Pom2011-thm1]</a>
$\frac{3}{8 π}$	[[B2022](#B2022)]	All primitive moduli (hence also squarefree), odd characters; gives $C_{72}^{odd} \leq 3/ (8 π)$ and thus $C_{72} \leq 3/ (8 π)$ . <a href="#B2022-main">[B2022-main]</a>
$\frac{1}{π ^{2}}$	[[Kerr2020](#Kerr2020)]	Cubefree moduli (hence squarefree), arbitrary intervals; implies the same leading constant for the initial-interval quantity $S (χ)$ . <a href="#Kerr2020-main">[Kerr2020-main]</a>
$\frac{1}{4 π}$	[[BK2020](#BK2020)]	Squarefree moduli, odd characters; this controls $C_{72} = max C_{72}^{even}, C_{72}^{odd}$ . <a href="#BK2020-main-constants">[BK2020-main-constants]</a>
$\frac{1}{2 π ^{2}}$	[[BK2020](#BK2020)]	Squarefree moduli, even characters. <a href="#BK2020-main-constants">[BK2020-main-constants]</a>

Known lower bounds

Bound	Reference	Comments
$0$		Trivial from nonnegativity of the defining infimum.

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 π^{2}) + o_{q} (1)$ (even) and $3/ (8 π) + 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/ π^{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 (χ)$ and displayed inequality (1) quote: "Given two integers $N$ , $q$ and a primitive character $χ$ modulo $q$ consider the sums $S (χ) := max_{N \leq q} \sum_{1 \leq n \leq N} χ (n)$ . A bound, proven independently by Polya and Vinogradov in the early 1900s, is the following $S (χ) \leq c q lo g 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 $χ$ to squarefree modulus $q$ , we prove the following upper bound $\sum_{1 \leq n \leq N} χ (n) \leq c q lo g q$ , where $c = 1/ (2 π^{2}) + o (1)$ for even characters and $c = 1/ (4 π) + 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 $χ$ modulo $q$ , we prove the following upper bound $\sum_{1 \leq n \leq N} χ (n) \leq c q lo g q$ , where $c = 3/ (4 π^{2}) + o_{q} (1)$ for even characters and $c = 3/ (8 π) + 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 $χ mod q$ and integers $M$ and $N$ we have $\sum_{M < n < M + N} χ (n) \leq (1 + o (1)) \frac{4 c}{π ^{2}} q^{1/2} lo g 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 $χ$ a primitive character to the modulus $q > 1$ , we have $S (χ) \leq \frac{2}{π ^{2}} q^{1/2} lo g q + \frac{4}{π ^{2}} q^{1/2} lo g lo g q + \frac{3}{2} q^{1/2}$ if $χ$ is even, and $S (χ) \leq \frac{1}{2 π} q^{1/2} lo g q + \frac{1}{π} q^{1/2} lo g lo g q + q^{1/2}$ if $χ$ 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 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.