1.2. Roth’s theorem 27

negligible. In this case, arithmetic progressions can be produced in abun-

dance via a Fourier-analytic calculation.

To handle the general case, one must somehow synthesise together the

argument that deals with the structured case with the argument that deals

with the random case. There are several known ways to do this, but they

can be basically classified into two general methods, namely the density

increment argument (or

L∞

increment argument) and the energy increment

argument (or

L2

increment argument).

The idea behind the density increment argument is to introduce a di-

chotomy: either the object A being studied is pseudorandom (in which case

one is done), or else one can use the theory of the structured objects to lo-

cate a sub-object of significantly higher “density” than the original object.

As the density cannot exceed one, one should thus be done after a finite

number of iterations of this dichotomy. This argument was introduced by

Roth in his original proof [Ro1953] of the above theorem.

The idea behind the energy increment argument is instead to decompose

the original object A into two pieces (and, sometimes, a small additional er-

ror term): a structured component that captures all the structured objects

that have significant correlation with A, and a pseudorandom component

which has no significant correlation with any structured object. This de-

composition usually proceeds by trying to maximise the “energy” (or

L2

norm) of the structured component, or dually by trying to minimise the en-

ergy of the residual between the original object and the structured object.

This argument appears for instance in the proof of the Szemer´ edi regular-

ity lemma [Sz1978] (which, not coincidentally, can also be used to prove

Roth’s theorem), and is also implicit in the ergodic theory approach to such

problems (through the machinery of conditional expectation relative to a

factor, which is a type of orthogonal projection, the existence of which is

usually established via an energy increment argument). However, one can

also deploy the energy increment argument in the Fourier analytic setting,

to give an alternate Fourier-analytic proof of Roth’s theorem that differs in

some ways from the density increment proof.

In this section we give both Fourier-analytic proofs of Roth’s theorem,

one proceeding via the density increment argument, and the other by the

energy increment argument. As it turns out, both of these arguments extend

to establish Szemer´ edi’s theorem, and more generally in counting other types

of patterns, but this is non-trivial (requiring some sort of inverse conjecture

for the Gowers uniformity norms in both cases); we will discuss this further

in later sections.