a repository of mathematical know-how

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.


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.