1.3. Linear patterns 45

that such Bohr sets were regular (this condition is closely related to the

Fourier measurability condition used in the energy increment argument).

With this modification to the original Roth argument, the bound was low-

ered to N0

δ−O(1/δ2),

or equivalently obtaining length three progressions

in sets of density much larger than log log N/ log N. Even more recently,

this argument was combined with the Szemer´ edi-Heath-Brown argument by

Bourgain [Bo2008], and refined further by Sanders [Sa2010], to obtain the

further improvement of N0

exp(O(δ−4/3−o(1))),

and then (by a somewhat

different argument of Sanders [Sa2010]) of N0

exp(O(δ−1−o(1))).

This is

tantalisingly close to the k = 3 case of an old conjecture of Erd¨ os that asserts

that any subset of the natural numbers whose sums of reciprocals diverge

should have infinitely many arithmetic progressions of length k for any k.

To establish the k = 3 case from quantitative versions of Roth’s theorem,

one would basically need a bound of the form N0

exp(δ−1+c)

for some

c 0 (or the ability to obtain progressions in sets of density 1/

log1+c

N).

Very recently, a bound of this shape has been obtained in the bounded

characteristic case; see [BaKa2011].

On the other hand, there is an old counterexample of Behrend [Be1946]

(based ultimately on the observation that a sphere in a high-dimensional lat-

tice

Zd

does not contain any arithmetic progressions of length three) which

shows that N0 must be at least

exp(log2(1/δ))

(in particular, it must

be super-polynomial in δ); equivalently, it is known that there are subsets

of [N] of density about exp(−c

√

log N) with no arithmetic progressions of

length three. For the sharpest results in this direction, see [El2008] and

[GrWo2008].

The question of refining the bounds is an important one, as it tends to

improve the technological understanding of current methods, as well as shed

light on their relative strengths and weaknesses. However, this comes at the

cost of making the arguments somewhat more technical, and so we shall not

focus on the sharpest quantitative results in this section.

1.3. Linear patterns

In Section 1.2, we used (linear) Fourier analysis to control the number of

three-term arithmetic progressions a, a + r, a + 2r in a given set A. The

power of the Fourier transform for this problem ultimately stemmed from

the identity

En,r∈Z/N

Z

1A(n)1A(n + r)1A(n + 2r)

=

α∈

1

N

Z/Z

ˆA(α)ˆA(−2α)ˆA(α)

1 1 1

(1.17)