Theorem 1.

For $m,n\in{\bf N}$ and $p$ a positive odd rational prime,

 $\left|\sum_{t=m}^{m+n}\left(\frac{t}{p}\right)\right|<\sqrt{p}\,\ln p.$
Proof.

 $\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

 $\displaystyle\left|\sum_{t=m}^{m+n}\left(\frac{t}{p}\right)\right|$ $\displaystyle\leq$ $\displaystyle\left|\frac{\sqrt{p}}{p}\sum_{a=1}^{p-1}\sum_{x=m}^{m+n}e^{2\pi aix% /p}\right|=\left|\frac{\sqrt{p}}{p}\sum_{a=1}^{p-1}e^{2\pi iam/p}\sum_{x=0}^{n% }e^{2\pi iax/p}\right|\leq\left|\frac{\sqrt{p}}{p}\sum_{a=1}^{p-1}\frac{e^{2% \pi ian/p}-1}{e^{2\pi ia/p}-1}\right|$ $\displaystyle=$ $\displaystyle\left|\frac{\sqrt{p}}{p}\sum_{a=1}^{p-1}\frac{e^{\pi ian/p}\sin(% \pi an/p)}{e^{\pi ia/p}\sin(\pi a/p)}\right|\leq\frac{\sqrt{p}}{p}\sum_{a=1}^{% p-1}\left|\frac{1}{\sin(\pi\langle a/p\rangle)}\right|\leq\frac{\sqrt{p}}{p}% \sum_{a=1}^{p-1}\frac{1}{2\langle a/p\rangle}$

Here $\langle x\rangle$ denotes the absolute value of the difference between $x$ and the closest integer to $x$, i.e. $\langle x\rangle=\inf_{z\in{\bf Z}}\{|x-z|\}$.

Since $p$ is odd, we have

 $\frac{1}{2}\sum_{a=1}^{p-1}\frac{1}{\langle a/p\rangle}=\sum_{0

Now $\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)\rightarrow{\bf R}$ given by $f(x)=x\ln\frac{2x+1}{2x-1}$ is decreasing and approaches 1 as $x\rightarrow\infty$. To prove the latter statement, substitute $v=1/x$ and take the limit as $v\rightarrow 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,\infty)$. But $f^{\prime}(x)\rightarrow 0$ as $x\rightarrow\infty$ and $f^{\prime}$ is increasing on $[1,\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

 $\left|\sum_{t=m}^{m+n}\left(\frac{t}{p}\right)\right|\leq\frac{\sqrt{p}}{p}% \cdot p\sum_{a=1}^{\frac{p-1}{2}}\frac{1}{a}<\sqrt{p}\sum_{a=1}^{\frac{p-1}{2}% }\ln\frac{2a+1}{2a-1}=\sqrt{p}\,\ln p.$

References

• 1 Vinogradov, I. M., , 5th rev. ed., Dover, 1954.
Title Pólya-Vinogradov inequality PolyaVinogradovInequality 2013-03-22 12:46:23 2013-03-22 12:46:23 djao (24) djao (24) 7 djao (24) Theorem msc 11L40