The Polya-Vinogradov inequality

Let $\chi :\mathbb{Z}\to ℂ$ be a primitive Dirichlet character modulo $m$. $\chi$ being a Dirichlet character modulo $m$ means that $\chi (kn)=\chi (k)\chi (n)$ for all $k,n$, that $\chi (n+m)=\chi (n)$ for all $n$, and that if $\gcd (n,m)>1$ then $\chi (n)=0$. $\chi$ being primitive means that the conductor of $\chi$ is $m$. The conductor of $\chi$ is the smallest defining modulus of $\chi$. If $m^{\prime }$ is a divisor of $m$, $m^{\prime }$ is said to be a defining modulus of $\chi$ if $\gcd (n,m)=1$ and $n\equiv 1(mod{m}^{\prime })$ together imply that $\chi (n)=1$. If $n\equiv 1(modm)$ then $\chi (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^{\prime }$ of $m$ is a defining modulus for a Dirichlet character $\chi$ modulo $m$ if and only if there exists a Dirichlet character ${\chi }^{\prime }$ modulo $m^{\prime }$ such that

$$\chi (n)={\chi }_0(n)\cdot {\chi }^{\prime }(n)\mathit{\hspace{1em}\hspace{1em}}n\in \mathbb{Z},$$

where ${\chi }_0$ is the principal Dirichlet character modulo $m$. (The principal Dirichlet character modulo $m$ is that character such that $\chi (n)=0$ if $\gcd (n,m)>1$ and $\chi (n)=1$ otherwise.)

If $\chi$ is a Dirichlet character modulo $m$, define the Gauss sum $G(\cdot ,\chi ):\mathbb{Z}\to ℂ$ corresponding to this character by

$$G(n,\chi )=\sum _{k=0}^{m-1}\chi (k)e^{2\pi ikn/m},n\in \mathbb{Z}.$$

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

We can write $\chi (n)$ using a Fourier series (the Fourier coefficients are defined on the following line, and one proves that any function $\mathbb{Z}/m\to ℂ$ is equal to its Fourier series)

$$\chi (n)=\sum _{k=0}^{m-1}\widehat{\chi }(k)e^{2\pi ikn/m}.$$

The coefficients are defined by

$\widehat{\chi }(k)$ $=$ ${\displaystyle \frac{1}{m}}{\displaystyle \sum _{n=0}^{m-1}}\chi (n)e^{-2\pi ikn/m}$

$=$ ${\displaystyle \frac{1}{m}}G(-k,\chi ).$

We use the fact [1, p. 152, Proposition 9] that for any $n$ we have $G(n,\chi )=\overline{\chi }(n)\cdot G(1,\chi )$. 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,\chi )=0$ in that case). Using $G(n,\chi )=\overline{\chi }(n)\cdot G(1,\chi )$, we get

$$\chi (n)=\sum _{k=0}^{m-1}\frac{1}{m}\overline{\chi (-k)}\cdot G(1,\chi )e^{2\pi ikn/m}=\frac{G(1,\chi )}{m}\sum _{k=0}^{m-1}\overline{\chi (-k)}{e}^{2\pi ikn/m}.$$

Therefore

${\displaystyle \sum _{n=1}^N}\chi (n)$ $=$ ${\displaystyle \sum _{n=1}^N}{\displaystyle \frac{G(1,\chi )}{m}}{\displaystyle \sum _{k=0}^{m-1}}\overline{\chi (-k)}{e}^{2\pi ikn/m}$

$=$ ${\displaystyle \frac{G(1,\chi )}{m}}{\displaystyle \sum _{k=0}^{m-1}}\overline{\chi (-k)}{\displaystyle \sum _{n=1}^N}{e}^{2\pi ikn/m}$

$=$ ${\displaystyle \frac{G(1,\chi )}{m}}{\displaystyle \sum _{k=1}^{m-1}}\overline{\chi (-k)}{\displaystyle \sum _{n=1}^N}{e}^{2\pi ikn/m}.$

Let $f(k)={\sum }_{n=1}^N{e}^{2\pi ikn/m}$. Thus

$$\sum _{n=1}^N\chi (n)=\frac{G(1,\chi )}{m}\sum _{k=1}^{m-1}\overline{\chi (-k)}f(k),$$

and so (because $|\overline{\chi (-k)}|$ is either $1$ or $0$ and hence is $\le 1$)

$$\left|\sum _{n=1}^N\chi (n)\right|=\frac{|G(1,\chi )|}{m}\sum _{k=1}^{m-1}|f(k)|.$$

We have $f(m-k)=\overline{f(k)}$, so $|f(m-k)|=|f(k)|$. Hence

$$\sum _{k=1}^{m-1}|f(k)|\le 2\sum _{1\le k\le m/2}|f(k)|.$$

Moreover, for $1\le k\le m/2$ we have, setting $r=e^{2\pi ik/m}$,

$$|f(k)|=\left|\frac{1-r^{N+1}}{1-r}\right|\le \frac{2}{|1-r|}=\frac{1}{\sin \frac{\pi k}{m}}\le \frac{1}{\frac{2}{\pi }\cdot \frac{\pi k}{m}}=\frac{m}{2k}.$$

Therefore,

$\left|{\displaystyle \sum _{n=1}^N}\chi (n)\right|$ $\le$ ${\displaystyle \frac{|G(1,\chi )|}{m}}\cdot 2{\displaystyle \sum _{1\le k\le m/2}}|f(k)|$

$\le$ ${\displaystyle \frac{|G(1,\chi )|}{m}}\cdot 2{\displaystyle \sum _{1\le k\le m/2}}{\displaystyle \frac{m}{2k}}$

$=$ $|G(1,\chi )|{\displaystyle \sum _{1\le k\le m/2}}{\displaystyle \frac{1}{k}}$

$|G(1,\chi )|\log m.$

(If $m$ is large enough. It’s not true that ${\sum }_{1\le k\le m/2}\frac{1}{k}\le \log (m/2)$, but it is true for large enough $m$ that .)

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