1.2. Roth’s theorem 31

Remark 1.2.5. The above argument relied heavily on the fact that there

was only a one-parameter family of linear relations between n, n + r, n + 2r.

The same argument does not work directly for finding arithmetic progres-

sions of length longer than three; we return to this point in later sections.

The second step converts correlation with a linear character into a den-

sity increment on a subprogression:

Proposition 1.2.6 (Fragmenting a linear character into progressions). Let

N ≥ 1, let ε 0, and let φ(n) := e(αn) be a linear phase. Then there exists

N = N (N, ε) which goes to infinity as N → ∞ for fixed ε, and a partition

[N] =

J

j=1

Pj ∪ E

of [N] into arithmetic progressions Pj of length at least N , together with an

error term E of cardinality at most O(εN), such that φ fluctuates by at most

O(ε) on each progression Pj (i.e., |φ(x) − φ(y)| ε whenever x, y ∈ Pj).

Proof. We may assume that N is suﬃciently large depending on ε, as the

claim is trivial otherwise (just set N = 1).

Fix ε, and let N be a slowly growing function of N to be chosen later.

By using recurrence for the linear phase n → αn, we can find a shift h ≥ 1

of size h = ON ,ε(1) such that αh

R/Z

≤ ε/N . We then partition [N]

into h arithmetic progressions of spacing h, and then partition each of those

progressions in turn into subprogressions Pj of spacing h and length N , plus

an error of cardinality at most N , leading to an error set E of cardinality

at most hN = ON ,ε(1). On each of the Pj, αn fluctuates by at most ε.

The claim then follows by choosing N to be a suﬃciently slowly growing

function of N.

Now we can prove Proposition 1.2.3 (and thus Roth’s theorem). Let

N, δ, δ , A be as in Proposition 1.2.3. By Proposition 1.2.4 (if N is large

enough), we can find α for which

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

δ2.

We now let ε 0 be a small quantity depending on δ to be chosen later

(actually it turns out that we can take ε to be a small multiple of

δ2)

and

apply Proposition 1.2.6 to decompose [N] into progressions P1,...,PJ and

an error term E with the stated properties. Then we have

En∈[N](1A(n) − δ )e(−αn) =

1

N

(

J

j=1 n∈Pj

(1A(n) − δ )e(−αn)) + O(ε).