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
increment argument) and the energy increment
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
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.