Revision of Getting rid of nasty cutoffs from Thu, 02/04/2009 - 11:15

Quick description

When faced with an unpleasant looking cutoff condition in a quantity one wishes to estimate it, try expanding that condition using Fourier analysis.

Prerequisites

Basic harmonic analysis

Example 1

The classic example of this technique is the Pólya-Vinogradov theorem. Let $p$ be a prime, and write $(x | p)$ for the Legendre symbol: thus $(x | p) = 1$ if $x$ is a quadratic residue modulo $p$ and is $-1$ otherwise. The Pólya-Vinogradov theorem states that if $m < p$ then

$\sum_{x = 1}^m (x | p) = O(\sqrt{p}\log p).$

What this means is that, provided $m > C\sqrt{p}\log p$ , about 50 percent of the numbers less than $m$ are quadratic residues modulo $p$ .

There is a particular value of $m$ for which the result is very easy: when $m = p-1$ , one is just counting the number of quadratic residues and nonresidues modulo $p$ (excluding zero), and it is well-known that there are $(p-1)/2$ . Thus

$\sum_{x = 1}^{p-1} (x |p) = 0.$

The only obstacle lying between this easy result and the Pólya-Vinogradov theorem is a \emph{cutoff} hiding in the sum $\sum_{x=1}^m$ . To see this more clearly let us write the quantity we are to bound as

$\sum_{x = 1}^{p-1} 1_{\{1,\dots,m\}}(x)(x | p) .$

The notation $1_A(x)$ means a function which equals $1$ on the set $A$ and is zero elsewhere. Now we apply the trick under discussion: we claim that the cutoff $f = 1_{\{1,\dots,m\}}$ may be expanded as a Fourier series

$f(x) = \sum_{r = 0}^{p-1} c_{r,m} e^{2\pi i xr/p}$

where $\sum_r |c_{r,m}| = O(\log p)$ . To see this one uses (discrete) Fourier analysis on $\mathbb{Z}/p\mathbb{Z}$ . The Fourier coefficients

\[ \hat{f}(r) = \frac{1}{p}\sum_{x = 0}^{p-1} f(x) e^{-2\pi i xr/p}\]

of $f(x)$ are just geometric series, the common ratio of series one must sum for $\hat{f}(r)$ being $e^{2\pi i r/p}$ . An easy exercise shows that $|\hat{f}(r)| \leq C/|r|$ , where $|r|$ is the size of $r$ when reduced to lie between $-p/2$ and $p/2$ . The claim now follows from the Fourier inversion formula.

Applying this decomposition of $1_{\{1,\dots,m\}}(x)$ and the triangle inequality, our task now follows if we can establish that [{math]] \sum_{x = 1}^{p-1} e^{2\pi i xr/p} (x | p) = O(\sqrt{p}) [{\math]] for all $r = 0,\dots,p-1$ . We have now \emph{completed} the sum to the whole range $x = 1,\dots,p-1$ , though we have paid the price of introducing the exponential $e^{2\pi i xr/p}$ .

It turns out that this is not a huge price to pay: these new sums are \emph{gauss sums} and it is possible to show that they are $O(\sqrt{p})$ . We leave the details as an exercise (the solution to which may be found in any number of places).

Example 2

This trick is ubiquitous in analytic number theory. It is very important, for example, in the treatment of sums $\sum_{p \leq N} f(p)$ using the so-called \emph{method of bilinear forms}; see B.~Green's article Three topics in additive prime number theory, Chapter 2, for more information.

General discussion

Sometimes this principle is described as ``all cutoffs are the same, or as ``completing exponential sums. It can lead to extra logarithmic factors as in the Pólya-Vinogradov inequality mentioned above; in this example reducing the size of these factors is a major unsolved problem.