21.13.04 · number-theory / dirichlet-l-functions-characters

The Polya-Vinogradov Inequality

shipped3 tiersLean: none

Anchor (Master): Polya 1918 *Göttinger Nachrichten* 21-29 (originator: Über die Verteilung der quadratischen Reste und Nichtreste); Vinogradov 1918 *Perm. Univ. Fiz.-Mat. Obshch.* (independent originator); Davenport 2000 *Multiplicative Number Theory* 3rd ed. (Springer GTM 74) §23; Montgomery-Vaughan 2007 *Multiplicative Number Theory I* (Cambridge) §9.4; Burgess 1957 *Mathematika* 4, 106-112 and 1962 *Proc. London Math. Soc.* (3) 12, 193-206 (the Burgess bound, the only known improvement in the short-sum range); Montgomery-Vaughan 1977 *Invent. Math.* 43, 69-82 (GRH-conditional refinement); Granville-Soundararajan 2007 *J. Amer. Math. Soc.* 20, 357-384 (the structure of large character sums); Paley 1932 *J. London Math. Soc.* 7, 28-32 (the $\Omega$-result: the inequality is sharp up to the constant for infinitely many $q$); Iwaniec-Kowalski 2004 *Analytic Number Theory* (AMS Colloquium Publications 53) §12.4

Intuition Beginner

Take a non-principal character — for the cleanest case, the $\pm 1$ pattern that labels each odd number as a square or a non-square modulo a fixed odd prime. Walk along the integers and keep a running tally: add $1$ when the label is $+ 1$ , subtract $1$ when the label is $- 1$ . The question of this unit is simple to state. As you walk further and further, how big can the running tally get?

If the labels behaved like genuine coin flips, the tally would drift like a random walk, wandering away from zero only as fast as the square root of the number of steps. The labels are not random — they are a fixed arithmetic pattern — yet the Polya-Vinogradov inequality says the tally stays almost as well-behaved as a random walk: no matter where you start the walk and no matter how long you walk, the tally never strays farther from zero than roughly $q$ (with a small extra logarithm), where $q$ is the modulus. The pattern cannot conspire to build up a long one-sided run.

Why does this matter? Because a bounded tally means the $+ 1$ and $- 1$ labels stay nearly balanced over every stretch of integers. That balance is the quantitative engine behind statements like "the squares and non-squares modulo $q$ are evenly mixed," and it forces the first non-square to appear early — you cannot have a long opening run of squares, because that run would push the tally up past what the inequality allows.

Visual Beginner

The picture is the running tally of the $\pm 1$ pattern modulo $7$ . Using the Legendre symbol from 21.01.06, the squares modulo $7$ are $1, 2, 4$ and the non-squares are $3, 5, 6$ , so the labels on $1, 2, 3, 4, 5, 6$ are $+ 1, + 1, - 1, + 1, - 1, - 1$ and the pattern then repeats with period $7$ .

The table shows the running tally $S (N)$ , the sum of the first $N$ labels:

$n$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
label	$+ 1$	$+ 1$	$- 1$	$+ 1$	$- 1$	$- 1$	$0$	$+ 1$	$+ 1$
tally $S (N)$	$1$	$2$	$1$	$2$	$1$	$0$	$0$	$1$	$2$

The tally never climbs above $2$ and never falls below $0$ over a full period. The label at $n = 7$ is $0$ because $7$ shares a factor with the modulus, so multiples of $q$ contribute nothing. Over the whole period the labels sum to zero — three $+ 1$ 's and three $- 1$ 's — which is why the walk returns to where it began. Polya-Vinogradov is the statement that this narrow band persists for every modulus, with width controlled by $q$ .

Worked example Beginner

Track the running tally for the squares-versus-non-squares pattern modulo $11$ and find the largest tally over one period.

Step 1. List the squares modulo $11$ . Squaring $1, 2, 3, 4, 5$ gives $1, 4, 9, 5, 3$ , so the squares modulo $11$ are ${1, 3, 4, 5, 9}$ and the non-squares are ${2, 6, 7, 8, 10}$ .

Step 2. Write the labels on $1$ through $10$ : the label is $+ 1$ on a square and $- 1$ on a non-square, giving $$ +1, -1, +1, +1, +1, -1, -1, -1, +1, -1. $$

Step 3. Form the running tally by adding the labels one at a time: $$ 1,\ 0,\ 1,\ 2,\ 3,\ 2,\ 1,\ 0,\ 1,\ 0. $$

Step 4. Read off the largest value: the tally peaks at $3$ , reached at $n = 5$ after the opening run $+ 1, - 1, + 1, + 1, + 1$ . Over the full period the tally returns to $0$ , as it must, since the five $+ 1$ 's and five $- 1$ 's cancel.

What this tells us: the peak tally $3$ is comfortably below $11 \approx 3.3$ . The largest tally measures the worst imbalance between squares and non-squares over any opening stretch, and here that imbalance never exceeds $3$ . Polya-Vinogradov guarantees a bound of this size — about $q$ — for every modulus and for every non-principal character, not just this small example.

Check your understanding Beginner

Exercise (easy, multiple choice).

The running tally of a non-principal character over one full period (from $1$ to $q$ ) always ends at which value?

A. $q$
B. $q$
C. $0$
D. $lo g q$

Hint

A non-principal character sums to zero over a complete period — this is the orthogonality relation from 21.03.02. The running tally is exactly that complete sum once you reach $n = q$ .

Answer

C. Over a complete period the values of a non-principal character add up to $0$ (the orthogonality of characters), so the running tally returns to $0$ after every full block of $q$ consecutive integers. Feedback-correct: the tally always closes the loop at $0$ after a full period. Feedback-wrong: the tally never reaches $q$ — that would require every label to be $+ 1$ , which is the principal character, not a non-principal one; the value $q$ is the bound on the peak of the tally, not its end value.

Formal definition Intermediate+

Throughout, $q \geq 2$ is an integer, $χ$ is a Dirichlet character modulo $q$ in the sense of 21.03.02, and $e (x) := e^{2 π i x}$ denotes the standard additive character of $R / Z$ . For a real number $α$ , write $∥ α ∥$ for the distance from $α$ to the nearest integer.

Definition (character sum). For integers $M$ and $N \geq 1$ the character sum over the interval $(M, M + N]$ is $$ S_\chi(M, N) := \sum_{M < n \leq M + N} \chi(n). $$ The sum is complete when $N = q$ (it runs over a full period) and incomplete otherwise. The triangle inequality gives the elementary bound $∣ S_{χ} (M, N) ∣ \leq N$ , and a second elementary bound $∣ S_{χ} (M, N) ∣ \leq φ (q)$ holds for any length, since the complete sum vanishes for non-principal $χ$ and any incomplete sum differs from a sub-interval of a single period.

Definition (Gauss sum). For a character $χ$ modulo $q$ , the Gauss sum is $$ \tau(\chi) := \sum_{a \bmod q} \chi(a) e(a/q). $$ A character $χ$ modulo $q$ is primitive if it is not induced by any character of strictly smaller modulus dividing $q$ ; equivalently, $χ$ is not constant on the cosets of $1 + (d)$ for any proper divisor $d ∣ q$ . For primitive $χ$ the separability identity holds: $χ (n) τ (\overline{χ}) = \sum_{a mod q} \overline{χ} (a) e (an / q)$ for every integer $n$ , and the Gauss sum has absolute value $∣ τ (χ) ∣ = q$ .

Definition (finite Fourier expansion of $χ$ ). Rearranging the separability identity, a primitive character admits the finite Fourier expansion $$ \chi(n) = \frac{1}{\tau(\overline\chi)} \sum_{a \bmod q} \overline\chi(a), e!\left(\frac{an}{q}\right), $$ expressing $χ$ as a linear combination of the $q$ additive characters $n \mapsto e (an / q)$ with coefficients $\overline{χ} (a) / τ (\overline{χ})$ of constant modulus $1/ q$ .

The expansion is the analytic heart of the unit: it converts a sum of the multiplicative quantity $χ (n)$ over an interval into a weighted sum of linear exponential sums $\sum_{n} e (an / q)$ , each of which is a geometric series and therefore explicitly summable.

Counterexamples to common slips

"The Gauss-sum expansion holds for any character." The clean identity $χ (n) τ (\overline{χ}) = \sum_{a} \overline{χ} (a) e (an / q)$ holds for all $n$ only when $χ$ is primitive. For imprimitive $χ$ it fails when $g cd (n, q) > 1$ , and one must first reduce $χ$ to the primitive character $χ^{⋆}$ modulo its conductor $q^{⋆} ∣ q$ . The Polya-Vinogradov bound for imprimitive $χ$ then follows from the primitive case with $q^{⋆} \leq q$ , so primitivity is no loss of generality.
" $q lo g q$ is a bound on the complete sum." The complete sum of a non-principal character is exactly $0$ . Polya-Vinogradov is a bound on the incomplete sums $S_{χ} (M, N)$ over arbitrary sub-intervals, uniformly in $M$ and $N$ ; the content is that no partial run can build up an imbalance larger than $q lo g q$ .
"The logarithm comes from the Gauss sum." The factor $q$ comes from $∣ τ (\overline{χ}) ∣ = q$ , but the $lo g q$ comes from summing the geometric-series bounds $min (N, \frac{1}{2} ∥ a / q ∥^{- 1})$ over $a$ : the tail behaves like $\sum_{1 \leq a < q /2} (a / q)^{- 1} \approx q lo g q$ before division by $q$ . The two factors have distinct origins.

Key theorem with proof Intermediate+

The signature theorem is the Polya-Vinogradov inequality, proved by completing the incomplete character sum through the Gauss-sum Fourier expansion and bounding the resulting linear exponential sums.

Theorem (Polya-Vinogradov; Polya 1918, Vinogradov 1918). Let $χ$ be a non-principal Dirichlet character modulo $q$ . Then for all integers $M$ and all $N \geq 1$ , $$ \left| \sum_{M < n \leq M + N} \chi(n) \right| \leq \sqrt{q}, \log q. $$

Proof. By the reduction noted in the formal-definition section it suffices to treat $χ$ primitive modulo $q$ (an imprimitive non-principal $χ$ is induced by a primitive $χ^{⋆}$ of conductor $q^{⋆} ∣ q$ , and the interval sum changes only by terms where $g cd (n, q) > 1$ , controlled by the same bound with $q^{⋆} \leq q$ ). Assume henceforth $χ$ primitive, so $∣ τ (\overline{χ}) ∣ = q$ and the finite Fourier expansion holds for every $n$ .

Insert the expansion into the character sum and exchange the two finite sums: $$ S_\chi(M, N) = \sum_{M < n \leq M + N} \frac{1}{\tau(\overline\chi)} \sum_{a \bmod q} \overline\chi(a), e!\left(\frac{an}{q}\right) = \frac{1}{\tau(\overline\chi)} \sum_{a \bmod q} \overline\chi(a) \sum_{M < n \leq M + N} e!\left(\frac{an}{q}\right). $$

The term $a \equiv 0 (mod q)$ contributes $\overline{χ} (0) = 0$ since $χ$ is non-principal (indeed $\overline{χ} (0) = 0$ by the convention that characters vanish off the units), so the outer sum runs over $1 \leq a \leq q - 1$ . Take absolute values, using $∣ \overline{χ} (a) ∣ \leq 1$ and $∣ τ (\overline{χ}) ∣ = q$ : $$ |S_\chi(M, N)| \leq \frac{1}{\sqrt{q}} \sum_{a = 1}^{q - 1} \left| \sum_{M < n \leq M + N} e!\left(\frac{an}{q}\right) \right|. $$

The inner sum is a geometric series with ratio $e (a / q)$ . For $a \neq \equiv 0 (mod q)$ , $$ \left| \sum_{M < n \leq M + N} e!\left(\frac{an}{q}\right) \right| = \left| \frac{e(a(M+N)/q) - e(aM/q)}{e(a/q) - 1} \right| \leq \frac{2}{|e(a/q) - 1|} = \frac{1}{|\sin(\pi a/q)|}, $$ using $∣ e (θ) - 1∣ = 2∣ sin (π θ) ∣$ and the numerator bound $\leq 2$ . With the elementary inequality $∣ sin (π t) ∣ \geq 2∥ t ∥$ for the distance $∥ t ∥$ to the nearest integer, this gives $$ \left| \sum_{M < n \leq M + N} e!\left(\frac{an}{q}\right) \right| \leq \frac{1}{2 |a/q|}. $$

For $1 \leq a \leq q - 1$ the distance $∥ a / q ∥$ equals $a / q$ when $a \leq q /2$ and $(q - a) / q$ when $a > q /2$ ; the values $∥ a / q ∥$ for $a = 1, \dots, q - 1$ are therefore $1/ q, 2/ q, \dots$ taken symmetrically about the midpoint, so $$ \sum_{a = 1}^{q - 1} \frac{1}{2|a/q|} = \frac{q}{2} \sum_{a = 1}^{q - 1} \frac{1}{\min(a, q - a)} \leq \frac{q}{2} \cdot 2 \sum_{b = 1}^{\lfloor q/2 \rfloor} \frac{1}{b} = q \sum_{b = 1}^{\lfloor q/2 \rfloor} \frac{1}{b}. $$

The harmonic sum satisfies $\sum_{b = 1}^{⌊ q /2 ⌋} 1/ b \leq 1 + lo g (q /2) < lo g q$ for $q \geq 7$ (and the bound is checked directly for the finitely many smaller $q$ ). Hence $$ |S_\chi(M, N)| \leq \frac{1}{\sqrt{q}} \cdot q \log q = \sqrt{q}, \log q, $$ which is the claimed inequality. $□$

Bridge. The Polya-Vinogradov inequality builds toward the Burgess bound and the analytic theory of $L$ -functions, and appears again in 21.12.02 (the prime-number theorem in arithmetic progressions), where uniform control of character sums underlies the error term. The central insight is that completion — replacing an incomplete multiplicative sum by a weighted complete one through the finite Fourier expansion — trades the hard problem of cancellation in $\sum χ (n)$ for the easy problem of cancellation in geometric series $\sum e (an / q)$ ; this is exactly the mechanism that converts the Gauss-sum bound $∣ τ (χ) ∣ = q$ into a bound on every interval sum. The same expansion generalises: replacing the linear phase $e (an / q)$ by higher-degree phases gives Weil's bounds for complete sums, and the bridge is that all of analytic number theory's character-sum estimates begin by writing a multiplicative weight as a Fourier series in additive characters. Putting these together, the foundational reason the squares and non-squares stay mixed is the unit-modulus Gauss sum, and this is dual to the statement that $L (1, χ) \neq = 0$ proved in 21.03.02.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the linear exponential sum bound used in the proof: for $α \in / Z$ , $$ \left| \sum_{n = M+1}^{M+N} e(\alpha n) \right| \leq \frac{1}{2|\alpha|}, $$ where $∥ α ∥$ is the distance from $α$ to the nearest integer.

Hint

Sum the geometric series, bound the numerator by $2$ , and use $∣ e (α) - 1∣ = 2∣ sin (π α) ∣ \geq 4∥ α ∥$ .

Answer

The sum is geometric with ratio $e (α) \neq = 1$ : $$ \sum_{n = M+1}^{M+N} e(\alpha n) = e(\alpha(M+1)) \frac{e(\alpha N) - 1}{e(\alpha) - 1}. $$ The leading factor has modulus $1$ , and $∣ e (α N) - 1∣ \leq 2$ , so $$ \left| \sum_{n = M+1}^{M+N} e(\alpha n) \right| \leq \frac{2}{|e(\alpha) - 1|}. $$ Now $∣ e (α) - 1∣ = ∣ e^{iπ α} ∣ ∣ e^{iπ α} - e^{- iπ α} ∣ = 2∣ sin (π α) ∣$ . The function $∣ sin (π t) ∣$ has period $1$ and on $[- \frac{1}{2}, \frac{1}{2}]$ satisfies $∣ sin (π t) ∣ \geq 2∣ t ∣$ by concavity of $sin$ on $[0, \frac{π}{2}]$ (the chord from $0$ to $\frac{π}{2}$ lies below the curve). Since $∥ α ∥$ is the distance to the nearest integer, $∣ sin (π α) ∣ = ∣ sin (π ∥ α ∥) ∣ \geq 2∥ α ∥$ . Therefore $$ \left| \sum_{n = M+1}^{M+N} e(\alpha n) \right| \leq \frac{2}{2 \cdot 2|\alpha|} = \frac{1}{2|\alpha|}. $$ Rubric: full credit for the geometric-series evaluation, the numerator bound, and the inequality $∣ sin (π t) ∣ \geq 2∥ t ∥$ .

Exercise 4 (medium, symbolic).

Derive the least-quadratic-non-residue bound: if $p$ is an odd prime and $χ$ is the Legendre-symbol character modulo $p$ , the least positive integer $n$ with $χ (n) = - 1$ satisfies $n = O (p lo g p)$ .

Hint

If every integer up to $N$ were a quadratic residue, the partial sum $S_{χ} (0, N)$ would equal $N$ . Compare with the Polya-Vinogradov bound.

Answer

Let $n_{0}$ be the least positive integer with $χ (n_{0}) = - 1$ , so $χ (k) = + 1$ for every $k$ with $1 \leq k < n_{0}$ and $g cd (k, p) = 1$ (none of these $k$ can be divisible by $p$ since $n_{0} \leq p$ ). Then the partial sum over $(0, n_{0} - 1]$ counts $n_{0} - 1$ residues, all with value $+ 1$ : $$ S_\chi(0, n_0 - 1) = \sum_{k = 1}^{n_0 - 1} \chi(k) = n_0 - 1. $$ By Polya-Vinogradov, $∣ S_{χ} (0, n_{0} - 1) ∣ \leq p lo g p$ , hence $$ n_0 - 1 \leq \sqrt{p},\log p, \qquad n_0 \leq \sqrt{p},\log p + 1 = O(\sqrt{p},\log p). $$ So the first quadratic non-residue modulo $p$ appears no later than $p lo g p$ . This is the classical bound; Burgess later lowered the exponent below $\frac{1}{2}$ , and under GRH the bound becomes $O ((lo g p)^{2})$ .

Exercise 6 (medium, symbolic).

Show that for a non-principal character $χ$ modulo $q$ , the short-sum cancellation $S_{χ} (M, N) = o (N)$ holds whenever $N / (q lo g q) \to \infty$ . State precisely the range of lengths $N$ for which Polya-Vinogradov yields genuine cancellation.

Hint

Compare the bound $q lo g q$ with the elementary bound $N$ . Cancellation is genuine exactly when the Polya-Vinogradov bound is smaller than $N$ .

Answer

Polya-Vinogradov gives $∣ S_{χ} (M, N) ∣ \leq q lo g q$ , a bound independent of $N$ . The elementary bound is $∣ S_{χ} (M, N) ∣ \leq N$ . The Polya-Vinogradov bound improves on the elementary one precisely when $$ \sqrt{q},\log q < N, \qquad\text{i.e.}\qquad N > \sqrt{q},\log q. $$ For such $N$ , the ratio $∣ S_{χ} (M, N) ∣/ N \leq q lo g q / N \to 0$ as $N / (q lo g q) \to \infty$ , so the average of $χ$ over the interval tends to $0$ — genuine cancellation. For $N \leq q lo g q$ (short sums), Polya-Vinogradov gives nothing beyond the elementary bound, and the Burgess bound is needed to extract cancellation in the range $q^{1/4 + ϵ} \leq N \leq q lo g q$ . Thus the useful range of Polya-Vinogradov is $N ≫ q lo g q$ , and the inequality is most useful for $N$ of order $q$ or larger relative to $q$ .

Exercise 7 (hard, symbolic).

Prove the sharper constant for the complete-sum bound: for primitive non-principal $χ$ modulo $q$ , $$ \max_{M, N} |S_\chi(M, N)| \leq \frac{\sqrt{q}}{\pi} \log q + O(\sqrt{q}), $$ by retaining the constant in the harmonic-sum estimate and using $∣ sin (π t) ∣ \geq 2∥ t ∥$ more carefully. (Outline the constant-chasing; full rigour on the error term is optional.)

Hint

The bound $∣ \sum_{n} e (an / q) ∣ \leq \frac{1}{2∥ a / q ∥} = \frac{q}{2 m i n ( a , q - a )}$ summed over $a$ gives $\frac{q}{q} \sum_{b \leq q /2} \frac{1}{b}$ . The factor $1/ π$ appears when you instead keep $\frac{1}{2 s i n ( π a / q )}$ and approximate the resulting sum by an integral.

Answer

Starting from the exact geometric-series bound $\sum_{M < n \leq M + N} e (an / q) \leq 1/∣ sin (π a / q) ∣$ (not yet weakened to $1/ (2∥ a / q ∥)$ ), insert it into the completed sum: $$ |S_\chi(M, N)| \leq \frac{1}{\sqrt{q}} \sum_{a=1}^{q-1} \frac{1}{|\sin(\pi a/q)|}. $$ By symmetry $a \leftrightarrow q - a$ and the bound $sin (π a / q) \geq sin (π / q) > 0$ , $$ \sum_{a=1}^{q-1} \frac{1}{\sin(\pi a/q)} = 2 \sum_{a=1}^{(q-1)/2} \frac{1}{\sin(\pi a/q)}. $$ For small angles $sin (π a / q) \approx π a / q$ , so the dominant contribution is $$ 2 \sum_{a=1}^{(q-1)/2} \frac{q}{\pi a} (1 + O((a/q)^2)) = \frac{2q}{\pi} \sum_{a=1}^{(q-1)/2} \frac{1}{a} + O(q) = \frac{2q}{\pi}\left(\log \frac{q}{2} + \gamma\right) + O(q), $$ using $\sum_{a \leq x} 1/ a = lo g x + γ + O (1/ x)$ . The terms with $a$ near $q /2$ , where the small-angle approximation degrades, contribute only $O (q)$ in total since $1/ sin$ is bounded there. Dividing by $q$ : $$ |S_\chi(M, N)| \leq \frac{1}{\sqrt q} \cdot \frac{2q}{\pi}\left(\log \frac{q}{2} + \gamma\right) + O(\sqrt q) = \frac{2\sqrt q}{\pi}\log q + O(\sqrt q). $$ A more careful split between even and odd characters (using $χ (- 1) = \pm 1$ to fold the sum) improves the leading constant to $\frac{1}{π}$ for one parity class, giving the stated $\frac{q}{π} lo g q + O (q)$ . Rubric: full credit for replacing $∥ a / q ∥$ by $sin (π a / q)$ , the small-angle approximation with the harmonic-sum asymptotic $lo g (q /2) + γ$ , and the identification of the $1/ π$ constant.

Exercise 8 (hard, symbolic).

State the Burgess bound and explain precisely the range of $N$ in which it improves on Polya-Vinogradov, and what it gives for the least quadratic non-residue.

Hint

Burgess: $∣ S_{χ} (M, N) ∣ ≪ N^{1 - 1/ r} q^{(r + 1) / (4 r^{2}) + ϵ}$ for each integer $r \geq 1$ (with $r \leq 3$ unconditional for general $q$ , all $r$ for prime $q$ ). Find the range where this beats both $N$ and $q lo g q$ .

Answer

Burgess bound (Burgess 1957, 1962). For a non-principal character $χ$ modulo a prime $q$ , every integer $r \geq 1$ , and every $ϵ > 0$ , $$ \left| \sum_{M < n \leq M + N} \chi(n) \right| \ll_{r, \epsilon} N^{1 - 1/r}, q^{(r+1)/(4r^2) + \epsilon}. $$ For general (composite) $q$ the bound holds unconditionally for $r = 1, 2, 3$ , and for $r = 2$ already it improves the elementary bound.

Range of improvement. Polya-Vinogradov gives cancellation only for $N ≫ q lo g q$ . The Burgess bound is a genuine saving (smaller than the elementary $N$ ) as soon as $N \geq q^{1/4 + ϵ}$ : setting the two factors comparable, $N^{1 - 1/ r} q^{(r + 1) / (4 r^{2})} < N$ requires $q^{(r + 1) / (4 r^{2})} < N^{1/ r}$ , i.e. $N > q^{(r + 1) / (4 r)}$ , which tends to $q^{1/4}$ as $r \to \infty$ . Thus Burgess extracts cancellation in the previously inaccessible short range $q^{1/4 + ϵ} \leq N \leq q lo g q$ , where Polya-Vinogradov fails. For $N ≫ q lo g q$ the two are comparable; Burgess is the strict improvement in the short range.

Least non-residue. Feeding the Burgess bound into the argument of Exercise 4 (the first non-residue $n_{0}$ forces a partial sum of size $n_{0}$ ) gives $n_{0} ≪ q^{1/ (4 e) + ϵ}$ , where $1/ (4 e) \approx 0.1516$ . This is the best known unconditional bound on the least quadratic non-residue, improving on the Polya-Vinogradov exponent $1/2$ . Under the Generalised Riemann Hypothesis for $L (s, χ)$ the least non-residue is $O ((lo g q)^{2})$ (Ankeny 1952), far beyond what any character-sum bound delivers.

Advanced results Master

The unconditional inequality $∣ S_{χ} (M, N) ∣ \leq q lo g q$ is sharp in its dependence on $q$ up to the secondary logarithm. Paley's $Ω$ -result (Paley 1932 ^{[Paley 1932]}) produces, for infinitely many real primitive characters $χ$ modulo $q$ , partial sums as large as $c q lo g lo g q$ ; the gap between $lo g q$ and $lo g lo g q$ is the entire remaining uncertainty in the unconditional theory. Under the Generalised Riemann Hypothesis for $L (s, χ)$ , Montgomery and Vaughan (1977) ^{[Montgomery-Vaughan 1977]} closed most of that gap from above, proving $S_{χ} (M, N) ≪ q lo g lo g q$ , which matches Paley's lower bound up to the implied constant. The conditional truth is therefore $max_{N} ∣ S_{χ} (0, N) ∣ ≍ q lo g lo g q$ for the extremal characters.

The mechanism behind the extremal characters is pretentiousness, isolated by Granville and Soundararajan (2007) ^{[Granville-Soundararajan 2007]}. A character has an abnormally large partial sum exactly when it correlates with — "pretends to be" — a character of small conductor and a fixed parity; the pretentious distance $$ \mathbb{D}(\chi, \xi; x)^2 = \sum_{p \leq x} \frac{1 - \mathrm{Re},\chi(p)\overline{\xi(p)}}{p} $$ between $χ$ and a short test character $ξ$ measures the deficit. For characters of odd order $g$ , Granville and Soundararajan improve the unconditional bound to $q (lo g q)^{1 - δ_{g} + o (1)}$ with $δ_{g} = 1 - \frac{g}{π} sin (π / g) > 0$ , beating the classical $lo g q$ . This is the first unconditional improvement to the constant exponent of the logarithm and locates the obstruction precisely in low-order, low-conductor mimicry.

In the short range the Burgess bound (Burgess 1957, 1962) ^{[Burgess 1957]} remains the only unconditional cancellation below $N = q$ , a genuine saving for $N \geq q^{1/4 + ϵ}$ , and its consequence $n_{0} ≪ q^{1/ (4 e) + ϵ}$ for the least quadratic non-residue is still, after seven decades, the best unconditional exponent. Breaking the $q^{1/4}$ barrier in the Burgess range is equivalent to subconvexity bounds for $L (\frac{1}{2}, χ)$ and remains open.

Synthesis. The Polya-Vinogradov inequality is the foundational reason character sums cancel, and the entire tower above is a refinement of its single mechanism: completion through the Gauss-sum Fourier expansion. The central insight is that the bound $q lo g q$ factors as a Gauss-sum amplitude $q$ times a harmonic tail $lo g q$ , and each later improvement attacks one factor — Burgess shortens the range by iterating the completion with multiplicative shifts, GRH sharpens the tail from $lo g q$ to $lo g lo g q$ , and the pretentious method explains the extremal characters as those that mimic short conductors. This is exactly the pattern that organises analytic number theory: a clean unconditional bound, an $Ω$ -result showing it is nearly sharp, a conditional bound matching the $Ω$ -result, and a structural theory explaining the extremisers. Putting these together, the least-non-residue problem, the subconvexity problem for $L (\frac{1}{2}, χ)$ , and the distribution of character sums are dual faces of one question, and the bridge between them is the Gauss sum $∣ τ (χ) ∣ = q$ that first appeared in 21.03.02. The non-vanishing $L (1, χ) \neq = 0$ and the boundedness of $\sum χ (n)$ generalise the same arithmetic harmony, and the whole structure builds toward the subconvexity programme and the Langlands-theoretic $L$ -function estimates that appears again in 21.10.01.

Full proof set Master

Proposition 1 (Gauss-sum separability for primitive characters). Let $χ$ be a primitive Dirichlet character modulo $q$ . Then for every integer $n$ , $$ \chi(n), \tau(\overline\chi) = \sum_{a \bmod q} \overline\chi(a), e!\left(\frac{an}{q}\right). $$

Proof. When $g cd (n, q) = 1$ , substitute $a = n^{- 1} b$ (a bijection of the units modulo $q$ ) in $τ (\overline{χ}) = \sum_{b} \overline{χ} (b) e (b / q)$ : with $b = an$ , $$ \tau(\overline\chi) = \sum_{a} \overline\chi(an) e(an/q) = \overline\chi(n) \sum_a \overline\chi(a) e(an/q), $$ and multiplying by $χ (n) = \overline{\overline{χ} (n)} = 1/ \overline{χ} (n)$ (a value of modulus $1$ ) gives the claim. When $g cd (n, q) = d > 1$ , the left side is $χ (n) τ (\overline{χ}) = 0$ since $χ (n) = 0$ ; the right side is $\sum_{a} \overline{χ} (a) e (an / q)$ , an exponential sum over a subgroup that vanishes precisely because $χ$ is primitive (an imprimitive character would leave a nonzero residual sum over the cosets of the inducing modulus). The primitivity hypothesis is exactly what forces both sides to vanish together. $□$

Proposition 2 (Gauss-sum modulus). For primitive $χ$ modulo $q$ , $∣ τ (χ) ∣ = q$ .

Proof. Compute $∣ τ (χ) ∣^{2} = τ (χ) \overline{τ (χ)} = \sum_{a, b} χ (a) \overline{χ} (b) e ((a - b) / q)$ . By Proposition 1 applied with the substitution $a = b c$ over units $b$ (and the vanishing off the units), the double sum collapses to $\sum_{c} χ (c) \sum_{b} e (b (c - 1) / q)$ . The inner sum over a complete residue system is $q$ when $c \equiv 1 (mod q)$ and $0$ otherwise, leaving $∣ τ (χ) ∣^{2} = q χ (1) = q$ . Hence $∣ τ (χ) ∣ = q$ . $□$

Proposition 3 (imprimitive reduction). Let $χ$ be a non-principal character modulo $q$ induced by the primitive character $χ^{⋆}$ of conductor $q^{⋆} ∣ q$ . If the Polya-Vinogradov bound holds for $χ^{⋆}$ , then $∣ S_{χ} (M, N) ∣ \leq q^{⋆} lo g q^{⋆} \cdot d (q) \leq q lo g q$ for an absolute treatment, where the divisor factor accounts for removing the primes dividing $q / q^{⋆}$ .

Proof. Write $χ (n) = χ^{⋆} (n) 1_{g c d (n, q) = 1}$ . Möbius-expanding the coprimality indicator over divisors $e ∣ (q / q^{⋆})$ that capture the extra primes, $1_{g c d (n, q) = 1} = \sum_{e ∣ g c d (n, q / q^{⋆})} μ (e)$ , gives $$ S_\chi(M, N) = \sum_{e \mid q/q^\star} \mu(e), \chi^\star(e) \sum_{M/e < m \leq (M+N)/e} \chi^\star(m). $$ Each inner sum is a character sum for the primitive $χ^{⋆}$ over an interval, bounded by $q^{⋆} lo g q^{⋆}$ . Summing over the squarefree divisors $e$ of $q / q^{⋆}$ and using $q^{⋆} \leq q$ with the standard divisor estimate yields the stated bound; the leading $q lo g q$ absorbs the divisor factor for the inequality as stated. $□$

Connections Master

This unit specialises the Gauss-sum and orthogonality theory of 21.03.02 (Dirichlet $L$ -functions and characters): the Fourier expansion $χ (n) = τ (\overline{χ})^{- 1} \sum_{a} \overline{χ} (a) e (an / q)$ and the evaluation $∣ τ (χ) ∣ = q$ are the only inputs beyond the geometric series, so Polya-Vinogradov is the simplest quantitative payoff of the character theory developed there.

The least-non-residue corollary refines the qualitative residue theory of 21.01.06 (quadratic residues and the Legendre symbol): where that unit establishes which residues are squares, this one bounds how soon the first non-square must appear, turning a structural fact into an effective $O (q lo g q)$ estimate.

The inequality is a workhorse in 21.12.02 (the prime-number theorem in arithmetic progressions), where uniform control of $\sum_{n \leq x} χ (n)$ across moduli feeds the explicit-formula error term, and in 21.14.01 (the large sieve), whose mean-value bounds for character sums generalise the single-character Polya-Vinogradov estimate to averages over all characters of a given modulus.

Historical & philosophical context Master

George Polya and Ivan Vinogradov proved the inequality independently in 1918 ^{[Polya 1918]}, Polya in the Göttinger Nachrichten and Vinogradov in the journal of the Perm physico-mathematical society, each as a tool for studying the distribution of quadratic residues. Polya's motivation was the spacing of residues and non-residues; Vinogradov's was the least non-residue, a problem he would return to repeatedly. The two derivations are essentially the same completion argument through the Gauss sum, and the joint name reflects the genuine independence of the discoveries in the disrupted scientific communication of 1918.

Raymond Paley showed in 1932 ^{[Paley 1932]} that the bound cannot be unconditionally improved beyond $q lo g lo g q$ , using a clever averaging over real characters; this fixed the target for all later work. David Burgess's 1957 thesis result ^{[Burgess 1957]} broke the $N = q$ range barrier for the first time, and his $q^{1/ (4 e)}$ bound for the least non-residue has stood unimproved since. The pretentious reformulation of Granville and Soundararajan (2007) recast the extremal-character question in the language of multiplicative-function distance, connecting Polya-Vinogradov to the Halász-Montgomery theory and to subconvexity for $L (\frac{1}{2}, χ)$ .

Bibliography Master

@article{polya1918verteilung,
  author  = {P{\'o}lya, George},
  title   = {{\"U}ber die Verteilung der quadratischen Reste und Nichtreste},
  journal = {Nachrichten von der K{\"o}niglichen Gesellschaft der Wissenschaften zu G{\"o}ttingen, Mathematisch-Physikalische Klasse},
  year    = {1918},
  pages   = {21--29}
}

@article{vinogradov1918distribution,
  author  = {Vinogradov, Ivan M.},
  title   = {On the distribution of residues and non-residues of powers},
  journal = {Journal of the Physico-Mathematical Society of Perm University},
  volume  = {1},
  year    = {1918},
  pages   = {94--98},
  note    = {In Russian}
}

@article{paley1932theorem,
  author  = {Paley, Raymond E. A. C.},
  title   = {A theorem on characters},
  journal = {Journal of the London Mathematical Society},
  volume  = {7},
  year    = {1932},
  pages   = {28--32}
}

@article{burgess1957character,
  author  = {Burgess, David A.},
  title   = {On character sums and {$L$}-series},
  journal = {Mathematika},
  volume  = {4},
  year    = {1957},
  pages   = {106--112}
}

@article{burgess1962character2,
  author  = {Burgess, David A.},
  title   = {On character sums and {$L$}-series. {II}},
  journal = {Proceedings of the London Mathematical Society (3)},
  volume  = {12},
  year    = {1962},
  pages   = {193--206}
}

@article{montgomeryvaughan1977exponential,
  author  = {Montgomery, Hugh L. and Vaughan, Robert C.},
  title   = {Exponential sums with multiplicative coefficients},
  journal = {Inventiones Mathematicae},
  volume  = {43},
  year    = {1977},
  pages   = {69--82}
}

@article{granvillesound2007large,
  author  = {Granville, Andrew and Soundararajan, Kannan},
  title   = {Large character sums: pretentious characters and the {P}{\'o}lya-{V}inogradov theorem},
  journal = {Journal of the American Mathematical Society},
  volume  = {20},
  year    = {2007},
  pages   = {357--384}
}

@book{montgomeryvaughan2007mult,
  author    = {Montgomery, Hugh L. and Vaughan, Robert C.},
  title     = {Multiplicative Number Theory I: Classical Theory},
  series    = {Cambridge Studies in Advanced Mathematics},
  volume    = {97},
  publisher = {Cambridge University Press},
  year      = {2007}
}

@book{davenport2000mult,
  author    = {Davenport, Harold},
  title     = {Multiplicative Number Theory},
  edition   = {3},
  series    = {Graduate Texts in Mathematics},
  volume    = {74},
  publisher = {Springer},
  year      = {2000},
  note      = {Revised by H. L. Montgomery}
}

Prerequisites

21.03.02
21.01.06

Tier anchors

beginner: A running tally of $\pm 1$ steps with no long drift — a bounded random-walk picture for the partial sums of a $\pm 1$ character, calibrated to the level of a 3Blue1Brown 'cancellation in oscillating sums' explainer
intermediate: Davenport 2000 *Multiplicative Number Theory* 3rd ed. (Springer GTM 74, revised by H. L. Montgomery) §23 (the Polya-Vinogradov inequality via the finite Fourier expansion of $\chi$ in Gauss sums and the geometric-series bound); Montgomery-Vaughan 2007 *Multiplicative Number Theory I: Classical Theory* (Cambridge Studies in Advanced Mathematics 97) §9.4
master: Polya 1918 *Göttinger Nachrichten* 21-29 (originator: Über die Verteilung der quadratischen Reste und Nichtreste); Vinogradov 1918 *Perm. Univ. Fiz.-Mat. Obshch.* (independent originator); Davenport 2000 *Multiplicative Number Theory* 3rd ed. (Springer GTM 74) §23; Montgomery-Vaughan 2007 *Multiplicative Number Theory I* (Cambridge) §9.4; Burgess 1957 *Mathematika* 4, 106-112 and 1962 *Proc. London Math. Soc.* (3) 12, 193-206 (the Burgess bound, the only known improvement in the short-sum range); Montgomery-Vaughan 1977 *Invent. Math.* 43, 69-82 (GRH-conditional refinement); Granville-Soundararajan 2007 *J. Amer. Math. Soc.* 20, 357-384 (the structure of large character sums); Paley 1932 *J. London Math. Soc.* 7, 28-32 (the $\Omega$-result: the inequality is sharp up to the constant for infinitely many $q$); Iwaniec-Kowalski 2004 *Analytic Number Theory* (AMS Colloquium Publications 53) §12.4

References

Polya, G. — Über die Verteilung der quadratischen Reste und Nichtreste · *Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Mathematisch-Physikalische Klasse*, 1918, 21-29. The originating paper, proving that for a non-principal character $\chi$ modulo $q$ the partial sums $\sum_{M < n \leq M + N} \chi(n)$ are bounded by $O(\sqrt{q} \log q)$ uniformly in $M, N$, via the finite Fourier (Gauss-sum) expansion of $\chi$ and the geometric-series estimate for linear exponential sums.
Vinogradov, I. M. — On the distribution of residues and non-residues of powers · *Journal of the Physico-Mathematical Society of Perm University* 1 (1918), 94-98 (in Russian). Vinogradov's independent and contemporaneous proof of the same $\sqrt{q} \log q$ bound, obtained as part of his programme on the least quadratic non-residue and the distribution of power residues. The inequality is named jointly for Polya and Vinogradov.
Davenport, H. — Multiplicative Number Theory · 3rd ed., revised by H. L. Montgomery, Springer Graduate Texts in Mathematics 74, 2000. §23 (the large sieve chapter's neighbourhood) develops the Polya-Vinogradov inequality through the Gauss-sum Fourier expansion $\chi(n) = \tau(\chi)^{-1} \sum_{a \bmod q} \overline{\chi}(a) e(an/q)$ for primitive $\chi$, reducing the character-sum bound to the geometric-series estimate $|\sum_{M < n \leq M+N} e(an/q)| \leq \min(N, \tfrac{1}{2}\|a/q\|^{-1})$ and summing the harmonic-type tail. The standard graduate reference.
Montgomery, H. L. and Vaughan, R. C. — Multiplicative Number Theory I: Classical Theory · *Cambridge Studies in Advanced Mathematics* 97, Cambridge University Press, 2007. §9.4 gives the modern textbook treatment of the Polya-Vinogradov inequality with the sharp constant analysis (the even/odd character split, the $\tfrac{1}{\pi}$-type constants), and §9.5 discusses the consequences for the least non-residue and short character sums.
Burgess, D. A. — On character sums and L-series · *Mathematika* 4 (1957), 106-112; and *Proceedings of the London Mathematical Society* (3) 12 (1962), 193-206. The Burgess bound $|\sum_{M < n \leq M + N} \chi(n)| \ll N^{1 - 1/r} q^{(r+1)/(4r^2) + \epsilon}$, a genuine saving for $N \geq q^{1/4 + \epsilon}$ — the only known unconditional improvement of Polya-Vinogradov in the short-sum range, lowering the least-non-residue bound from $O(\sqrt{q} \log q)$ to $O(q^{1/(4\sqrt{e}) + \epsilon})$.
Montgomery, H. L. and Vaughan, R. C. — Exponential sums with multiplicative coefficients · *Inventiones Mathematicae* 43 (1977), 69-82. Establishes the GRH-conditional refinement $|\sum_{M < n \leq M + N} \chi(n)| \ll \sqrt{q} \log \log q$, an improvement of the unconditional $\sqrt{q} \log q$ by a factor $\log q / \log \log q$, conditional on the Generalised Riemann Hypothesis for $L(s, \chi)$.
Paley, R. E. A. C. — A theorem on characters · *Journal of the London Mathematical Society* 7 (1932), 28-32. Proves the $\Omega$-result: there is a constant $c > 0$ such that for infinitely many real primitive characters $\chi$ (modulo $q$) one has $\max_N |\sum_{n \leq N} \chi(n)| > c \sqrt{q} \log \log q$. This shows the Polya-Vinogradov $\sqrt{q} \log q$ bound is sharp up to the size of the secondary logarithm and cannot be improved past $\sqrt{q} \log \log q$ unconditionally.
Granville, A. and Soundararajan, K. — Large character sums: pretentious characters and the Polya-Vinogradov theorem · *Journal of the American Mathematical Society* 20 (2007), 357-384. Determines the structure of characters with large partial sums via the pretentious-distance framework, sharpening both the upper bound for characters of odd order and the conditional results, and clarifying that extremal behaviour comes from $\chi$ 'pretending' to be a character of small conductor.
Iwaniec, H. and Kowalski, E. — Analytic Number Theory · *AMS Colloquium Publications* 53, 2004. §12.4 places the Polya-Vinogradov inequality within the general theory of complete and incomplete exponential sums, deriving it from completion (the Fourier expansion converting an incomplete sum into a weighted complete sum) and the Gauss-sum evaluation $|\tau(\chi)| = \sqrt{q}$ for primitive $\chi$.

Estimated time

beginner: 18m
intermediate: 45m
master: 80m