44 1. Higher order Fourier analysis
we see that the energy increment argument, in the form presented here,
provides much worse bounds than the density increment argument; but see
For the ultralimit arguments, it is significantly harder to extract a quan-
titative bound from the argument (basically one has to painstakingly “fini-
tise” the argument first, essentially reaching the finitary counterparts of
these arguments presented above). Thus we see that there is a tradeoff
when using ultralimit analysis; the arguments become slightly cleaner (and
one can deploy infinitary methods), but one tends to lose
of what
quantitative bounds the method establishes.
It is possible to run the density increment argument more efficiently
by combining it with some aspects of the energy increment argument. As
described above, the density increment argument proceeds by locating a
single large Fourier coefficient
1 of A, and uses this to obtain a density
increment on a relatively short subprogression of [N] (of length comparable

N, ignoring factors of δ). One then has to iterate this about 1/δ times
before one obtains a truly significant density increment (e.g. from δ to 2δ).
It is this repeated passage from N to

N which is ultimately responsible
for the double exponential bound for N0 at the end of the day.
In an unpublished work, Endre Szemer´ edi observed that one can run
this argument more efficiently by collecting several large Fourier coefficients
of 1A simultaneously (somewhat in the spirit of the energy increment ar-
gument), and only then passing to a subprogression on which all of the
relevant Fourier characters are simultaneously close to constant. The sub-
progression obtained is smaller as a consequence, but the density increment
is much more substantial. Using this strategy, Endre was able to improve
the original Roth bound of N0 exp(exp(O(1/δ))) to the somewhat bet-
ter N0
(or equivalently, he was able to establish
length three progressions in any subset of [N] of density much larger than

log log N) for some c 0). By carefully optimising the choice of
threshold for selecting the “large Fourier coefficients”, Szemer´ edi (unpub-
lished) and Heath-Brown [HB1987] independently improved this method
further to obtain N0
or equivalently obtaining length three
progressions in
in [N] of density much larger than
The next advance was by Bourgain [Bo1999], who realised that rather
than pass to short subprogressions, it was more efficient to work on the sig-
nificantly larger (but messier) Bohr sets {n : αn mod 1 I}, after ensuring
7This is particularly the case if one begins to rely heavily on the axiom of choice (or on large
cardinal axioms) once one takes ultralimits, although these axioms are not used in the examples
result was later extended to arbitrary finite abelian groups by Meshulam [Me1995].
Previous Page Next Page