Pólya-Vinogradov Inequality

Theorem

Let $p$ be a positive odd prime.

Then:

$\forall m, n \in \N: \displaystyle \left|{\sum_{k=m}^{m+n} \left({\frac k p}\right)}\right| < \sqrt p \ \ln p$

where $\left({\dfrac k p}\right)$ is the Legendre symbol.

Proof

Start with the following manipulations:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{k=m}^{m+n} \left({\frac k p}\right)\)	\(=\)	\(\displaystyle \frac 1 p \sum_{k=0}^{p-1} \sum_{x=m}^{m+n} \sum_{a=0}^{p-1} \left(\frac k {p} \right) e^{2 \pi i a (x-k)/p}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \frac 1 p \sum_{a=1}^{p-1} \sum_{x=m}^{m+n} e^{2 \pi i a x/p} \sum_{k=0}^{p-1} \left(\frac k p \right) e^{-2 \pi i a t/p}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

The expression:

$\displaystyle\sum_{k=0}^{p-1} \left({\frac k p}\right) e^{-2 \pi i a t/p}$

is a Gauss sum, and has magnitude $\sqrt{p}$.

Hence:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left \vert{\sum_{t=m}^{m+n} \left({\frac t p}\right)}\right \vert\)	\(\le\)	\(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a=1}^{p-1} \sum_{x=m}^{m+n} e^{2 \pi a i x/p} }\right \vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a=1}^{p-1} e^{2 \pi i a m/p} \sum_{x=0}^{n} e^{2 \pi i a x/p} }\right \vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a=1}^{p-1} \frac{e^{2 \pi i a n/p}-1}{e^{2 \pi ia/p}-1} }\right \vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a=1}^{p-1} \frac{e^{\pi ian/p} \sin \left({\pi a n/p}\right)} {e^{\pi ia/p} \sin \left({\pi a/p}\right)} }\right \vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle \frac{\sqrt p} p \sum_{a=1}^{p-1} \left \vert{\frac 1 {\sin \left({\pi \left \langle {a/p}\right \rangle}\right)} }\right \vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\le\)	\(\displaystyle \frac{\sqrt p} p \sum_{a=1}^{p-1} \frac 1 {2 \left \langle {a/p}\right \rangle}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Here $\langle x \rangle$ denotes the non-Archimedean absolute value of the difference between $x$ and the closest integer to $x$, i.e.:

$\displaystyle \langle x \rangle = \inf_{z \in {\bf Z}} \{|x-z|\}$

Since $p$ is odd, we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \frac 1 2 \sum_{a=1}^{p-1} \frac 1 {\langle a/p \rangle}\)	\(=\)	\(\displaystyle \sum_{0 < a < \frac p 2} \frac p a\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle p \sum_{a=1}^{\frac{p-1} 2} \frac 1 a\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Now $\displaystyle \ln \frac{2x+1}{2x-1} > \frac 1 x$ for $x > 1$.

To prove this, it suffices to show that the function $f: [1 .. \infty) \to \R$ given by:

$\displaystyle f(x) = x \ln \frac{2x+1}{2x-1}$

is decreasing and approaches $1$ as $x \to \infty$.

To prove the latter statement, substitute $v = 1/x$ and take the limit as $v \to 0$ using L'Hospital's Rule.

To prove the former statement, it will suffice to show that $f'$ is less than zero on the interval $[1 .. \infty)$.

Now we have that:

$\displaystyle f''(x) = \frac{-4}{4 x^2-1} \left({1-\frac{4x^2+1}{4x^2-1}}\right) > 0$ for $x > 1$

So $f'$ is increasing on $[1 ..\infty)$.

But $f'(x) \to 0$ as $x \to \infty$.

So $f'$ is less than zero for $x > 1$.

With this in hand, we have:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left \vert {\sum_{t=m}^{m+n} \left({\frac t p}\right)}\right \vert\)	\(\le\)	\(\displaystyle \frac{\sqrt p} p \cdot p \sum_{a=1}^{\frac{p-1} 2} \frac 1 a\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(<\)	\(\displaystyle \sqrt p \sum_{a=1}^{\frac{p-1} 2} \ln \frac{2a+1}{2a-1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sqrt p \ \ln p\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$

Source of Name

This entry was named for George Pólya and Ivan Matveevich Vinogradov.

Sources

• This article incorporates material from Pólya-Vinogradov inequality on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.