If your problem can be expressed in terms of convolutions and inner products then take the Fourier transform

Quick description

There are many problems in mathematics that do not at first seem to concern the Fourier transform, but for which the Fourier transform can be a major help in the solution. This article is about how to recognise such problems.

Prerequisites

A basic knowledge of the Fourier transform. (See for example the definitions and basic facts laid out in the Fourier transforms front page, and some of the further reading suggested there.)

This article is incomplete. Many more examples needed. Perhaps the rest of the proof of Roth's theorem should be sketched?

Example 1

Roth's theorem about arithmetic progressions is the following beautiful statement.

Theorem 1 For every $\delta>0$ there exists $N$ such that every subset $A\subset\{1,2,\dots,N\}$ of size at least $\delta N$ contains an arithmetic progression of length 3.

One of the first ideas towards a proof is to come up with an analytic expression for the number of arithmetic progressions of length 3. (This is an instance of the idea of turning sets into functions.) We define the characteristic function $1_A$ of $A$ by setting $1_A(x)=1$ if $x\in A$ and $0$ otherwise. Then the number of progressions $(x,x+d,x+2d)$ with all three terms in $A$ is $\sum_{n=1}^N\sum_{d=1}^N1_A(x)1_A(x+d)1_A(x+2d)$ .

We can make this expression a lot tidier and easier to analyse if we think of the numbers $1,2,\dots,N$ as elements of the group $\Z/N\Z$ . Then we can think about the expression $\sum_x\sum_d1_A(x)1_A(x+d)1_A(x+2d)$ , where both $x$ and $d$ range over all of $\Z/N\Z$ . This is not equal to the previous expression, but the extra convenience of this definition more than compensates for the small technicalities needed to deal with the differences between it and the previous one.

Now let us rearrange this second expression as follows.

$\sum_x\sum_d1_A(x)1_A(x+d)1_A(x+2d)=\sum_y\sum_{x+z=2y}1_A(x)1_A(y)1_A(z)$

$=\sum_y1_A(y)\sum_{x+z=2y}1_A(x)1_A(z).$

This is, up to a normalizing factor, the inner product of a function very closely related to $1_A$ with the convolution of $1_A$ with itself. As such, we know it will have some simple expression in terms of the Fourier transform of $1_A$ .

Before we go ahead and give this expression, let us switch to a more standard normalization. We shall write $\mathbb{E}$ for $N^{-1}\sum$ , and instead of looking at the sum $\sum_y1_A(y)\sum_{x+z=2y}1_A(x)1_A(z)$ we shall look at the expectation $\mathbb{E}_y1_A(y)\mathbb{E}_{x+z=2y}1_A(x)1_A(z)$ . Also, we shall define the convolution of two functions $f$ and $g$ from $\Z/N\Z$ to $\C$ by the formula

$f*g(x)=\mathbb{E}_{u+v=x}f(u)g(v).$

Then we can rewrite $\mathbb{E}_y1_A(y)\mathbb{E}_{x+z=2y}1_A(x)1_A(z)$ as $\mathbb{E}_y1_A(y)1_A*1_A(2y)$ . If $N$ is odd, then we can substitute $u=2y$ and replace this by $\mathbb{E}_u1_A(u/2)1_A*1_A(u)=\langle 1_{A_2},1_A*1_A\rangle$ , where $a\in A\}$ .

We have now expressed our problem, or at least a quantity closely associated with our problem, in terms of convolutions and inner products. At this point we use Parseval's identity and the convolution identity to rewrite the expression as $\langle \hat{A}_2,\hat{A}^2\rangle=\sum_r\hat{A}(r)^2\hat{A}(-2r)$ . (See the Fourier transforms front page for a definition of the discrete Fourier transform and a discussion of these two identities.)

Why are we any better off? The reason is that now we have an unrestricted sum over one variable rather than a sum over three variables that satisfy an additive condition. Therefore, the sum we need to analyse can be estimated using more standard inequalities. This does not solve the problem, but it does turn out to be a very useful step in Roth's proof of his theorem, and in many other arguments of a similar nature.