1.2. Roth’s theorem 33

Exercise 1.2.3. Show that if N is an unbounded limit natural number, and

A ⊂ [N] is a limit subset of positive density (st |A|/N) = δ 0 with no

arithmetic progressions of length three, then there exists a limit real α such

that |En∈[N](1A(n) − δ )e(−αn)| 1.

Exercise 1.2.4. If N is an unbounded limit natural number, and α is a

limit real, show that one can partition [N] =

J

j=1

Pj ∪ E, where J is a

limit natural number, the Pj are limit arithmetic subprogressions of [N] of

unbounded length (with the map j → Pj being a limit function), such that

n → e(αn) fluctuates by o(1) on each Pj (uniformly in j), and |E| = o(N).

Exercise 1.2.5. Use the previous three exercises to reprove Roth’s theorem.

Exercise 1.2.6 (Roth’s theorem in bounded characteristic). Let F be a

finite field, let δ 0, and let V be a finite vector space. Show that if

the dimension of V is suﬃciently large depending on F, δ, and if A ⊂ V

is such that |A| ≥ δ|V |, then there exists a, r ∈ V with r = 0 such that

a, a + r, a + 2r ∈ A. (Hint: Mimic the above arguments (either finitarily, or

with ultralimits), using hyperplanes as a substitute for subprogressions.)

Exercise 1.2.7 (Roth’s theorem in finite abelian groups). Let G be a finite

abelian group, and let δ 0. Show that if |G| is suﬃciently large depending

on δ, and A ⊂ G is such that |A| ≥ δ|G|, then there exists a, r ∈ V with

r = 0 such that a, a + r, a + 2r ∈ A. (Hint: If there is an element of

G of large order, one can use Theorem 1.2.2 and the pigeonhole principle.

If all elements have bounded order, one can instead use Exercise 1.2.6.)

This result (as well as the special case in the preceding exercise) was first

established by Meshulam [Me1995].

1.2.2. The energy increment argument. Now we turn to the energy

increment approach. This approach requires a bit more machinery to set

up, but ends up being quite flexible and powerful (for instance, it is the

starting point for my theorem with Ben Green establishing arbitrarily long

progressions in the primes, which we do not know how to establish via

density increment arguments).

Instead of passing from [N] to a subprogression, we now instead coarsen

[N] to some partition (or factor) of [N], as follows. Define a factor of [N]

to be a σ-algebra of subsets B of [N], or equivalently a partition of [N]

into disjoint atoms or cells (with the elements of B then being the arbitary

unions of atoms). Given a function f : [N] → C and a factor B, we define

the conditional expectation E(f|B): [N] → C to be the function whose value

at a given point x ∈ [N] is given by the formula

E(f|B)(x) :=

1

|B(x)|

y∈B(x)

f(y),