Pólya-Vinogradov inequality

Theorem 1.

For $m\mathrm{,}n\mathrm{\in }\mathrm{N}$ and $p$ a positive odd rationalprime,

Proof.

Start with the following manipulations:

$$\sum _{t=m}^{m+n}\left(\frac{t}{p}\right)=\frac{1}{p}\sum _{t=0}^{p-1}\sum _{x=m}^{m+n}\sum _{a=0}^{p-1}\left(\frac{t}{p}\right)e^{2\pi ia(x-t)/p}=\frac{1}{p}\sum _{a=1}^{p-1}\sum _{x=m}^{m+n}{e}^{2\pi iax/p}\sum _{t=0}^{p-1}\left(\frac{t}{p}\right)e^{-2\pi iat/p}$$

The expression ${\sum }_{t=0}^{p-1}(\frac{t}{p})e^{-2\pi iat/p}$ is just a Gauss sum, and has magnitude$\sqrt{p}$. Hence

$\left|{\displaystyle \sum _{t=m}^{m+n}}\left({\displaystyle \frac{t}{p}}\right)\right|$$\le$$\left|{\displaystyle \frac{\sqrt{p}}{p}}{\displaystyle \sum _{a=1}^{p-1}}{\displaystyle \sum _{x=m}^{m+n}}{e}^{2\pi aix/p}\right|=\left|{\displaystyle \frac{\sqrt{p}}{p}}{\displaystyle \sum _{a=1}^{p-1}}{e}^{2\pi iam/p}{\displaystyle \sum _{x=0}^n}{e}^{2\pi iax/p}\right|\le \left|{\displaystyle \frac{\sqrt{p}}{p}}{\displaystyle \sum _{a=1}^{p-1}}{\displaystyle \frac{e^{2\pi ian/p}-1}{e^{2\pi ia/p}-1}}\right|$

$=$$\left|{\displaystyle \frac{\sqrt{p}}{p}}{\displaystyle \sum _{a=1}^{p-1}}{\displaystyle \frac{e^{\pi ian/p}\sin (\pi an/p)}{e^{\pi ia/p}\sin (\pi a/p)}}\right|\le {\displaystyle \frac{\sqrt{p}}{p}}{\displaystyle \sum _{a=1}^{p-1}}\left|{\displaystyle \frac{1}{\sin (\pi ⟨a/p⟩)}}\right|\le {\displaystyle \frac{\sqrt{p}}{p}}{\displaystyle \sum _{a=1}^{p-1}}{\displaystyle \frac{1}{2⟨a/p⟩}}$

Here $⟨x⟩$ denotes the absolute value of the differencebetween $x$ and the closest integer to $x$, i.e. $⟨x⟩={inf}_{z\in 𝐙}\{|x-z|\}$.

Since $p$ is odd, we have

Now $\ln \frac{2x+1}{2x-1}>\frac{1}{x}$ for $x>1$; to prove this, itsuffices to show that the function $f:[1,\mathrm{\infty })\to 𝐑$given by $f(x)=x\ln \frac{2x+1}{2x-1}$is decreasing and approaches 1 as $x\to \mathrm{\infty }$. To prove thelatter statement, substitute $v=1/x$ and take the limit as $v\to 0$ using L’Hôpital’s rule. To prove the former statement,it will suffice to show that $f^{\prime }$ is less than zero on the interval$[1,\mathrm{\infty })$. But $f^{\prime }(x)\to 0$ as $x\to \mathrm{\infty }$ and$f^{\prime }$ is increasing on $[1,\mathrm{\infty })$, since $f^{\prime \prime }(x)=\frac{-4}{4x^2-1}(1-\frac{4x^2+1}{4x^2-1})>0$ for $x>1$, so $f^{\prime }$is less than zero for $x>1$.

With this in hand, we have

∎