Pólya-Vinogradov inequality

Theorem 1.

For m,nN and p a positive odd rational prime,


Start with the following manipulations:


The expression t=0p-1(tp)e-2πiat/p is just a Gauss sumDlmfPlanetmath, and has magnitude p. Hence

|t=mm+n(tp)| |ppa=1p-1x=mm+ne2πaix/p|=|ppa=1p-1e2πiam/px=0ne2πiax/p||ppa=1p-1e2πian/p-1e2πia/p-1|
= |ppa=1p-1eπian/psin(πan/p)eπia/psin(πa/p)|ppa=1p-1|1sin(πa/p)|ppa=1p-112a/p

Here x denotes the absolute valueMathworldPlanetmathPlanetmathPlanetmath of the difference between x and the closest integer to x, i.e. x=infz𝐙{|x-z|}.

Since p is odd, we have


Now ln2x+12x-1>1x for x>1; to prove this, it suffices to show that the functionMathworldPlanetmath f:[1,)𝐑 given by f(x)=xln2x+12x-1 is decreasing and approaches 1 as x. To prove the latter statement, substitute v=1/x and take the limit as v0 using L’Hôpital’s rule. To prove the former statement, it will suffice to show that f is less than zero on the interval [1,). But f(x)0 as x and f is increasing on [1,), since f′′(x)=-44x2-1(1-4x2+14x2-1)>0 for x>1, so f is less than zero for x>1.

With this in hand, we have



Title Pólya-Vinogradov inequality
Canonical name PolyaVinogradovInequality
Date of creation 2013-03-22 12:46:23
Last modified on 2013-03-22 12:46:23
Owner djao (24)
Last modified by djao (24)
Numerical id 7
Author djao (24)
Entry type Theorem
Classification msc 11L40