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-
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
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.