The Polya-Vinogradov inequality

Jordan Bell
April 3, 2014

Let χ: be a primitive Dirichlet character modulo m. χ being a Dirichlet character modulo m means that χ(kn)=χ(k)χ(n) for all k,n, that χ(n+m)=χ(n) for all n, and that if gcd(n,m)>1 then χ(n)=0. χ being primitive means that the conductor of χ is m. The conductor of χ is the smallest defining modulus of χ. If m is a divisor of m, m is said to be a defining modulus of χ if gcd(n,m)=1 and n1(modm) together imply that χ(n)=1. If n1(modm) then χ(n)=1 (sends multiplicative identity to multiplicative identity), so m is a defining modulus, so the conductor of a Dirichlet character modulo m is less than or equal to m.

We shall prove the Polya-Vinogradov inequality for primitive Dirchlet characters. The same inequality holds (using an O term rather than a particular constant) for non-primitive Dirichlet characters. The proof of that involves the fact [1, p. 152, Proposition 8] that a divisor m of m is a defining modulus for a Dirichlet character χ modulo m if and only if there exists a Dirichlet character χ modulo m such that

χ(n)=χ0(n)χ(n)  n,

where χ0 is the principal Dirichlet character modulo m. (The principal Dirichlet character modulo m is that character such that χ(n)=0 if gcd(n,m)>1 and χ(n)=1 otherwise.)

If χ is a Dirichlet character modulo m, define the Gauss sum G(,χ): corresponding to this character by


The Polya-Vinogradov inequality states that if χ is a primitive Dirichlet character modulo m, then


We can write χ(n) using a Fourier series (the Fourier coefficients are defined on the following line, and one proves that any function /m is equal to its Fourier series)


The coefficients are defined by

χ^(k) = 1mn=0m-1χ(n)e-2πikn/m
= 1mG(-k,χ).

We use the fact [1, p. 152, Proposition 9] that for any n we have G(n,χ)=χ¯(n)G(1,χ). This is straightforward to show if gcd(n,m)=1, but takes some more work if gcd(n,m)>1 (to show that G(n,χ)=0 in that case). Using G(n,χ)=χ¯(n)G(1,χ), we get



n=1Nχ(n) = n=1NG(1,χ)mk=0m-1χ(-k)¯e2πikn/m
= G(1,χ)mk=0m-1χ(-k)¯n=1Ne2πikn/m
= G(1,χ)mk=1m-1χ(-k)¯n=1Ne2πikn/m.

Let f(k)=n=1Ne2πikn/m. Thus


and so (because |χ(-k)¯| is either 1 or 0 and hence is 1)


We have f(m-k)=f(k)¯, so |f(m-k)|=|f(k)|. Hence


Moreover, for 1km/2 we have, setting r=e2πik/m,



|n=1Nχ(n)| |G(1,χ)|m21km/2|f(k)|
= |G(1,χ)|1km/21k
< |G(1,χ)|logm.

(If m is large enough. It’s not true that 1km/21klog(m/2), but it is true for large enough m that 1km/21k<logm.)

It is a fact [1, p. 154, Proposition 10] that if χ is a primitive Dirichlet character modulo m and gcd(n,m)=1 then |G(n,χ)|=m. Thus