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

below.

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

sight7

of what

quantitative bounds the method establishes.

It is possible to run the density increment argument more eﬃciently

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 coeﬃcient

ˆA(α)

1 of A, and uses this to obtain a density

increment on a relatively short subprogression of [N] (of length comparable

to

√

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 eﬃciently by collecting several large Fourier coeﬃcients

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

exp(exp(O(log2(1/δ))))

(or equivalently, he was able to establish

length three progressions in any subset of [N] of density much larger than

exp(−c

√

log log N) for some c 0). By carefully optimising the choice of

threshold for selecting the “large Fourier coeﬃcients”, Szemer´ edi (unpub-

lished) and Heath-Brown [HB1987] independently improved this method

further to obtain N0

exp(δ−O(1)),

or equivalently obtaining length three

progressions in

sets8

in [N] of density much larger than

log−c

N.

The next advance was by Bourgain [Bo1999], who realised that rather

than pass to short subprogressions, it was more eﬃcient 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

above.

8This

result was later extended to arbitrary finite abelian groups by Meshulam [Me1995].