Use Fourier expansion to eliminate nasty cutoffs

Quick description

When faced with an unpleasant looking cutoff condition in a quantity one wishes to estimate, 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 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 $\Z/p\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

$\sum_{x = 1}^{p-1} e^{2\pi i xr/p} (x | p) = O(\sqrt{p})$

for all $r = 0,\dots,p-1$ . We have now 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 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 method of bilinear forms; see B. Green's article Three topics in additive prime number theory, Chapter 2, for more information.

Example 3

Suppose one has an integral operator

$= \int_\R K(x,y) f(y)\ dy$

which one knows to be bounded from $L^p(\R)$ to $L^q(\R)$ for some $1 \leq p,q \leq \infty$ . Then, given any bump function $\phi(x,y)$ , the smoothly truncated bump function

$= \int_\R K(x,y) \phi(x,y) f(y)\ dy$

is also bounded from $L^p(\R)$ to $L^q(\R)$ (and in fact the operator norm of $T_\phi$ is bounded by that of $T$ , times a constant depending only on $\phi$ ). To see this, observe that the support of $\phi$ can be placed in a box $[-L/2,L/2]^2$ for some sufficiently large $L$ . Performing a Fourier series expansion, one can write

$\phi(x,y) = 1_{[-L/2,L/2]}(x) 1_{[-L/2,L/2]}(y) \sum_{n,m \in \Z} c_{n,m} e^{2\pi i nx/L} e^{2\pi i my/L}$

for some rapidly decreasing Fourier coefficients $c_{n,m}$ . Interchanging sums and integrals (neglecting for now the issue of how to justify this; in practice, one can create an epsilon of room and regularize $f$ and $K$ as needed), we obtain

$T_\phi f(x) = \sum_{n,m} c_{n,m} 1_{[-L/2,L/2]}(x) e^{2\pi i nx/L} \int_\R K(x,y) (1_{[-L/2,L/2]}(y) e^{2\pi i my/L} f(y))\ dy.$

Applying the triangle inequality, we conclude that

$\| T_\phi f \|_{L^q(\R)} \leq \sum_{n,m} |c_{n,m}| \| \int_\R K(x,y) (1_{[-L/2,L/2]}(y) e^{2\pi i my/L} f(y))\ dy \|_{L^q(\R)}.$

Thus if $T$ is bounded from $L^p(\R)$ to $L^q(\R)$ with operator norm $A$ , one has

$\| T_\phi f \|_{L^q(\R)} \leq \sum_{n,m} |c_{n,m}| A \|f\|_{L^p(\R)},$

and the claim then follows from the rapid decrease of the coefficients $c_{n,m}$ .

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. Often it is very helpful to smooth the cutoffs before decomposing them into Fourier modes.