Pólya-Vinogradov Inequality

From ProofWiki
Jump to: navigation, search

Theorem

Let $p$ be a positive odd prime.


Then:

$\forall m, n \in \N: \displaystyle \left|{\sum_{k \mathop = 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 \sum_{k \mathop = m}^{m+n} \left({\frac k p}\right)\) \(=\) \(\displaystyle \frac 1 p \sum_{k \mathop = 0}^{p-1} \sum_{x \mathop = m}^{m+n} \sum_{a \mathop = 0}^{p-1} \left({\frac k p}\right) e^{2 \pi i a \left({x - k}\right) / p}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac 1 p \sum_{a \mathop = 1}^{p-1} \sum_{x \mathop = m}^{m+n} e^{2 \pi i a x / p} \sum_{k \mathop = 0}^{p-1} \left({\frac k p }\right) e^{-2 \pi i a t / p}\) $\quad$ $\quad$


The expression:

$\displaystyle\sum_{k \mathop = 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 \left \vert{\sum_{t \mathop = m}^{m+n} \left({\frac t p}\right)}\right \vert\) \(\le\) \(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a \mathop = 1}^{p-1} \sum_{x \mathop = m}^{m + n} e^{2 \pi a i x / p} }\right \vert\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a \mathop = 1}^{p-1} e^{2 \pi i a m / p} \sum_{x \mathop = 0}^n e^{2 \pi i a x / p} }\right \vert\) $\quad$ $\quad$
\(\displaystyle \) \(\le\) \(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a \mathop = 1}^{p-1} \frac{e^{2 \pi i a n / p} - 1} {e^{2 \pi i a / p} - 1} }\right \vert\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left \vert{\frac{\sqrt p} p \sum_{a \mathop = 1}^{p-1} \frac{e^{\pi i a n / p} \sin \left({\pi a n / p}\right)} {e^{\pi i a / p} \sin \left({\pi a / p}\right)} }\right \vert\) $\quad$ $\quad$
\(\displaystyle \) \(\le\) \(\displaystyle \frac{\sqrt p} p \sum_{a \mathop = 1}^{p-1} \left \vert{\frac 1 {\sin \left({\pi \left \langle {a / p}\right \rangle}\right)} }\right \vert\) $\quad$ $\quad$
\(\displaystyle \) \(\le\) \(\displaystyle \frac{\sqrt p} p \sum_{a \mathop = 1}^{p-1} \frac 1 {2 \left \langle {a / p}\right \rangle}\) $\quad$ $\quad$


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

$\displaystyle \left\langle{x}\right\rangle = \inf_{z \mathop \in \Z} \left\{ {\left|{x - z}\right|}\right\}$

Since $p$ is odd, we have:

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


Now:

$\ln \dfrac {2 x + 1} {2 x - 1} > \dfrac 1 x$

for $x > 1$.

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

$f \left({x}\right) = x \ln \dfrac {2 x + 1} {2 x - 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 $\left[{1 \,.\,.\, \infty}\right)$.

Now we have that:

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

for $x > 1$.

So $f'$ is increasing on $\left[{1 \,.\,.\, \infty}\right)$.

But $f' \left({x}\right) \to 0$ as $x \to \infty$.

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


With this in hand, we have:

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

$\blacksquare$


Source of Name

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


Sources