28 1. Higher order Fourier analysis

1.2.1. The density increment argument. We begin with the density

increment argument. We first rephrase Roth’s theorem in a finitary form:

Theorem 1.2.2 (Roth’s theorem, again). For every δ 0, there exists an

N0 = N0(δ) 0, such that for every N ≥ N0, and every A ⊂ [N] with

|A| ≥ δN, A contains an arithmetic progression of length three.

Exercise 1.2.1. Show that Theorem 1.2.1 and Theorem 1.2.2 are equiva-

lent.

We prove Theorem 1.2.2 by a downward induction on the density pa-

rameter δ. Let P (δ) denote the proposition that Theorem 1.2.2 holds for

that value of δ (i.e., for suﬃciently large N and all A ⊂ [N] with |A| ≥ δN,

A contains an arithmetic progression of length three). Our objective is to

show that P (δ) holds for all δ 0.

Clearly, P (δ) is (vacuously) true for δ 1 (and trivially true for δ ≥ 1).

It is also monotone in the sense that if P (δ) holds for some δ, then P (δ )

holds for all δ δ. To downwardly induct on δ, we will prove the following

dichotomy:

Proposition 1.2.3 (Lack of progressions implies density increment). Let

δ 0, let N be suﬃciently large depending on δ, and let A ⊂ [N] be such

that |A| ≥ δN. Then one of the following holds:

(i) A contains an arithmetic progression of length three; or

(ii) there exists a subprogression P of [N] of length at least N such

that |A ∩ P | ≥ (δ + c(δ))|P |, where N = N (N) goes to infinity as

N → ∞, and c(δ) 0 is bounded away from zero whenever δ is

bounded away from zero.

Let us see why Proposition 1.2.3 implies Theorem 1.2.2. It is slightly

more convenient to use a “well-ordering principle” argument rather than an

induction argument, though unsurprisingly the two approaches turn out to

be equivalent. Let δ∗ be the infimum of all δ for which P (δ) holds, thus

0 ≤ δ∗ ≤ 1. If δ∗ = 0, then we are done, so suppose that δ∗ is non-zero.

Then for any ε 0, P (δ∗ − ε) is false, thus there exist arbitrarily large N

and A ⊂ [N] with |A| ≥ (δ∗ − ε)N with no progressions of length three. By

Proposition 1.2.3, we can thus find a subprogression P of N of length at

least N with |A ∩ P | ≥ (δ∗ − ε + c(δ∗ − ε))|P |; if ε is small enough, this

implies that |A ∩ P | ≥ (δ∗ + ε)|P |. We then use an aﬃne transformation to

map P to [N ] (noting crucially that the property of having no arithmetic

progressions of a given length is preserved by aﬃne transformations). As N

can be arbitrarily large, N can be arbitrarily large also. Since P (δ∗ + ε) is

true, we see that A ∩ P contains an arithmetic progression of length three,

hence A does also; which gives the desired contradiction.