LECTURE NOTES 5 FOR 254A

TERENCE TAO

1. More on arithmetic progressions of length 3

In last week’s notes we proved (among other things) Roth’s theorem, which is the following:

Theorem 1.1. Let 0 < δ ≤ 1. Then there exists an N(δ) such that for any N > N(δ, k) and any subset A of {1, …, N} of cardinality |A| ≥ δN, there exists an proper arithmetic progression in A of length 3.

Roth’s argument is ultimately based on proving the recursive inequality

N(δ) ≲ N(δ + cδ^{2})^{2}

which ultimately leads to an estimate for N(δ) of the form

N(δ) ≲ e^{e^{C/δ}}.

To put this another way, to ensure that a subset A of {1, …, N} contains a nontrivial arithmetic progression of length 3, Roth’s argument requires that A have density at least ≳ 1/ log log N.

One can ask whether this can be improved. Heath-Brown and Szemeredi [4] were able to improve this bound from 1/ log log N to 1/(log N)^{1/20}; the main new idea over Roth’s argument is to try to exploit data from several Fourier coefficients simultaneously, rather than Roth’s approach of locating one large Fourier coefficient and using that to refine the set. Bourgain [2] then improved this further, to (log log N)^{1/2}/(log N)^{1/2}, which is the best known result to date.

It is not known what the sharp relationship between N and δ should be. An old conjecture of Erdös and Turan [3] suggests that the correct density should be roughly 1/ log N (more precisely, one should have infinitely many progressions whenever A is a subset of the natural numbers with ∑_{n∈A} 1/n divergent; this corresponds to a density somewhere between 1/ log N and 1/(log N)^{1+ε}, roughly speaking; see Q1).

The best known counterexample of a set with no arithmetic progressions of length 3 is almost sixty years old, and is due to Behrend [1] (see also [8]). This example has density exp(−C\sqrt{log N}), which is substantially less dense than the positive results (which require a density of at least exp(−C log log N) or so). It is quite remarkable that this simple example has not been improved in so long a span of time. (The best that is known is that there are slightly larger sets, of density exp(−C(log N)^{1/(k−1)}), which contain no arithmetic progressions of length k; see [6], [5]).

We begin with Behrend’s example.

2. Behrend’s example

The objective of this section is to prove

Theorem 2.1. Let N ≫ 1 be a large number. Then there exists a subset A ⊂ \{1, …, N\} of cardinality |A| ≳ N exp(−C\sqrt{log N}) which does not contain any proper arithmetic progressions of length 3.

Behrend’s key observation is the following: in any Euclidean space R^{d}, no matter how large the dimension d, a sphere {x ∈ R^{d} : |x| = r} cannot contain any proper arithmetic progressions of length 3. This is basically because the sphere is the boundary of a strictly convex body.

Moving from continuous space back to discrete, we see that any set of the form

{(x_{1}, …, x_{d}) ∈ Z^{d} : x_{1}^{2} + … + x_{d}^{2} = R}

for any integers d ≥ 1 and R > 0, cannot contain any proper arithmetic progressions of length 3.

Now we have to map this example back to {1, …, N}. Let n, d, and R be large integers to be chosen later, and consider the set

S_{n,d,R} := {(x_{1}, …, x_{d}) ∈ {1, 2, …, n}^{d} : x_{1}^{2} + … + x_{d}^{2} = R};

thus S_{n,d,R} is free of proper arithmetic progressions of length 3 (or higher). Note that as R ranges from n to nd^{2}, the sets S_{n,d,R} cover the cube {1, 2, …, n}^{d}, which has cardinality n^{d}. Thus by the pigeonhole principle there exists an R with

|S_{n,d,R}| ≳ n^{d}/(nd^{2}).

Now we map S_{n,d,R} to {1, …, N}. Recall that the map ϕ : {1, …, n}^{d} → ϕ({1, …, n})^{d} defined by

ϕ(x_{1}, …, x_{d}) := ∑_{j=1}^{d} x_{j}(2n)^{j−1}

is a Freiman isomorphism of order 2. In particular, ϕ(S_{n,d,R}) also has cardinality ≳ n^{d}/(nd^{2}) and has no arithmetic progressions of length 3. It is also contained in {1, …, N} if N ≫ C^{d}n^{d}. Thus if we set n := cN^{1/d}, then we have found a subset A of {1, …, N} without arithmetic progressions of length 3, which has cardinality

|A| ≳ c^{d}N/(N^{1/d}d^{2}) ≳ N exp(−Cd − \frac{log N}{d} − C log d).

Thus if we set d ∼ log N, we obtain the result.

3. Bourgain’s argument

We now present Bourgain’s argument, which states that any subset of {1, …, N} with density ≫ \sqrt{log log N}/\sqrt{log N} will contain an arithmetic progression. Equivalently, this asserts that N(δ) ≲ (\frac{1}{δ})^{C/δ^{2}}; see Q2.

By embedding {1, …, N} in a cyclic group of order p ∼ 3N, it suffices to prove the following:

Theorem 3.1. Let 0 < δ_{0} ≤ 1, and let p ≫ (\frac{1}{δ_{0}} )^{C/δ_{0}^{2}} be a prime. Then every subset A of Z/pZ of density at least δ_{0} contains a proper arithmetic progression (in Z/pZ) of length 3.

We now begin the proof of Theorem 3.1. Assume for contradiction that A contains no proper arithmetic progressions of length 3. We will also assume that |A| = δ_{0}p (since one can just adjust δ_{0} if necessary if |A| > δ_{0}p).

We recall the trilinear form T (f, g, h) defined by

T (f, g, h) := ∫_{Z/pZ} ∫_{Z/pZ} f(a)g(a+r)h(a+2r) dadr = p^{−2} ∑_{a,r∈Z/pZ} f(a)g(a+r)h(a+2r)

where integration is over normalized counting measure on Z/pZ. Then, since A has no proper arithmetic progressions, we see that

T (χ_{A}, χ_{A}, χ_{A}) = p^{−2} ∑_{a∈Z/pZ} χ_{A}(a)χ_{A}(a)χ_{A}(a) = |A|/p^{2} = δ_{0}/p.

More generally, we see that for any functions ψ_{1}, ψ_{2}, ψ_{3} on Z/pZ, we have

T (χ_{A}ψ_{1}, χ_{A}ψ_{2}, χ_{A}ψ_{3}) = p^{−2} ∑_{a∈A} ψ_{1}(x)ψ_{2}(x)ψ_{3}(x).  (1)

On the other hand, we have the identity

T (f, g, h) = ∑_{ξ∈Z/pZ} f̂(ξ)ĝ(−2ξ)ĥ(ξ).  (2)

As before, the idea is to use both (1) and (2) to force χ_{A} − δ to have a large Fourier coefficient, say { \atop χ_{A} − δ}(ξ) is large. This rather directly shows that A is fairly dense (density at least δ + cδ^{2}) on a Bohr neighborhood - some translate of the set {x ∈ Z/pZ : ∥xξ/p∥ ≪ δ^{2}}. Roughly speaking, the idea is to let ψ be a probability distribution on this Bohr neighborhood, and then note that ψ̂(ξ) is large, thus (χ_{A} −δ)∗ψ is large, thus χ_{A} −δ is large on some translate of the support of ψ.

In our previous proof of Roth’s theorem, we then passed from the Bohr neighborhood to an arithmetic progression, since that was Freiman equivalent to an interval {1, …, M} and we could continue the induction. However, this step of passing from neighborhoods to progressions is quite inefficient (in particular, it causes the square in the recursion N(δ) ≲ N(δ + cδ^{2})^{2}). Bourgain’s trick is to avoid this step by staying with the Bohr neighborhood. At the first iteration we only restrict to a Bohr neighborhood of dimension 1, but each stage introduces another dimension to the Bohr neighborhood, because we add another frequency restriction to the previous neighborhood at each stage. Also while Bohr neighborhoods are very similar in spirit to arithmetic progressions and intervals, they are not quite as wellbehaved under sums; for instance the sumset of {x : ∥xω/p∥ ≤ 1/K} with itself can have significantly larger cardinality (about 2^{d} as large, if d is the dimension of the Bohr neighborhood). However, things are much better if one takes the sumset of {x : ∥xω/p∥ ≤ 1/K} with {x : ∥xω/p∥ ≤ 1/K′} if K′ ≫ K (e.g. K′ ≥ d^{2}K), so we will be using tricks like this to keep the Bohr neighbourhoods behaving as much like intervals or arithmetic progressions as possible. Actually to make this work neatly we will not quite use Bohr neighborhoods, but rather exponential cutoff functions which are localized near Bohr neighborhoods. Each new Bohr neighborhood has a density which is δ^{2} better than the previous one, but has one higher dimension, and the width K has to narrow by a factor of δ^{C} (mostly because of this K versus K′ issue). Thus the procedure has to halt after O(1/δ) iterations, in which case we have a Bohr neighborhood of dimension O(1/δ) and width O(δ^{C/δ}), so a net density of about O(δ^{C/δ^{2}}). This is only meaningful if p ≫ δ^{−C/δ^{2}}, whence the restriction on p.

We now turn to the details.

4. Bohr cutoff functions

We shall need the following cutoff functions.

Given any x ∈ Z/pZ, write ∥x/p∥ for the distance from x/p to the nearest integer, thus ∥x/p∥ ranges between 0 and 1/2. Given any d ≥ 0 and any vector ω = (ω_{1}, …, ω_{d}) ∈ (Z/pZ)^{d}, write

∥xω/p∥ := ∑_{j=1}^{d} ∥xω_{j}/p∥,

and let ϕ_{ω} be the function

ϕ_{ω}(x) := exp(−∥xω_{j}/p∥).

We shall be using cutoff functions of the form ϕ_{ω}^{K} for various large numbers K ≫ 1. Roughly speaking, this is a smooth projection to the Bohr neighborhood

\{x ∈ Z/pZ : ∑_{j=1}^{d} ∥\frac{xω_{j}}{p} ∥ ≲ 1/K\},  (3)

and is somewhat similar to the characteristic function of a subgroup or of an arithmetic progression (since the above set is somewhat closed under addition, especially if d is not too large.

Note that ϕ_{ω} is always even and positive, and in particular equals 1 at the origin 0. We observe the following crude lower bound on ϕ_{ω}^{K}.

Lemma 4.1. We have

∫ ϕ_{ω}^{K} ≳ (CdK)^{−d}.

Proof This is Minkowski’s theorem again. We cover the torus R^{d}/Z^{d} into about (CdK)^{d} cubes of side length 1/CdK. By the pigeonhole principle, one of these cubes must contain at least (CdK)^{−d}p points of the form xω, where x ∈ Z/pZ. Subtracting, we thus see that the cube centered at the origin of sidelength 2/CdK also contains at least (CdK)^{−d}p points of the form xω. Since ϕ_{ω}^{K} ∼ 1 on this cube, the claim follows.

We now introduce the normalized functions ψ_{ω,K} by

ψ_{ω,K} := \frac{ϕ_{ω}^{K}}{∫ ϕ_{ω}^{K}};

thus ψ_{ω,K} is the L^{1}-normalized version of ψ_{ω}^{K}, and can be thought of as a probability measure concentrated on the Bohr neighborhood (3).

One measure of this is the following localization estimate.

Lemma 4.2. For any λ ≫ d^{2}, we have

∫_{∥xω/p∥≥λ/K} ψ_{ω,K}(x) dx ≲ e^{−λ/2}.

Proof It suffices to show that

∫_{(λ+1)/K≥∥xω/p∥≥λ/K} ψ_{ω,K}(x) dx ≲ e^{−λ/2},

since the claim then follows by summing in λ. Since ϕ_{ω}^{K}(x) ∼ e^{−λ} on this set, it thus suffices to show that

|{x ∈ Z/pZ : (λ + 1)/K ≥ ∥xω/p∥ ≥ λ/K}| ≲ e^{λ/2} ∫ ϕ_{ω}^{K}.

But we have

∫ ϕ_{ω}^{K} ≲ |{x ∈ Z/pZ : ∥xω/p∥ ≤ 1/K}|.

Now we can cover the region

{y ∈ R^{d}/Z^{d} : (λ + 1)/K ≥ ∥y∥ ≥ λ/K}

by O((Cλ)^{d}) = O(e^{λ/2}) l^{1}-balls of radius 1/2K. Each one of these balls can contain at most |{x ∈ Z/pZ : ∥xω/p∥ ≤ 1/K}| points of the form xω/p by the Minkowski’s theorem argument, and the claim follows.

We now prove a basic estimate, that narrower projections are essentially convolution idempotents for wider projections.

Lemma 4.3. Let ω ∈ (Z/pZ)^{d} and K′ ≫ d^{2}K. Then we have the pointwise estimate

∫ ψ_{ω,K}(x − jy)ψ_{ω/k,K′}(y) dy = (1 + O(\frac{K}{K′}))ψ_{ω,K}(x)

for j = 1, 2 and k = 1, 2. More generally, for any subset A′ of Z/pZ and any ω_{d+1} ∈ Z/pZ, we have

∫ ψ_{ω,K}(x − jy)χ_{A′}(x − jy)ψ_{(ω/k,ω_{d+1}),K′}(y) dy = (∫ χ_{A′}(x − jy)ψ_{ω,K′}(y) dy + O(d^{2} \frac{K}{K′}))ψ_{ω,K}(x). (4)

In particular we have

∥ψ_{ω,K} ∗ ψ_{ω/k,K′} − ψ_{ω,K}∥_{1} ≲ d^{2} \frac{K}{K′} .

Proof It suffices to prove (4). Fix x. We have to show that

∫ (ψ_{ω,K}(x − jy) − ψ_{ω,K}(x))χ_{A′}(x − jy)ψ_{(ω/k,ω_{d+1}),K′}(y) dy = O(d^{2} \frac{K}{K′})ψ_{ω,K}(x).

Dividing out by ψ_{ω,K}(x) and using the triangle inequality, it will suffice to show

∫ (e^{K∥kyω′/p∥} − 1)ψ_{ω′,K′}(y) dy = O(d^{2} \frac{K}{K′})

where ω′ := (ω/k, ω_{d+1}) ∈ (Z/pZ)^{d+1}. We split this into the region where ∥yω′/p∥ ≫ d^{2}/K′ and ∥yω′/p∥ ≲ d^{2}/K′. In the first part we use Lemma 4.2 and decomposition into shells λ ≤ ∥yω′/p∥ ≤ λ + 1; for the second part we use the Taylor approximation

e^{K∥kyω′/p∥} − 1 = O(d^{2} \frac{K}{K′})

and the L^{1}-normalization of ψ_{ω′,K′}.

This estimate has two important consequences for our application. First, the functional T is large when applied to these measures ψ_{ω,K}:

Corollary 4.4. Let ω ∈ (Z/pZ)^{d} and K′ ≫ d^{2}K. Then we have

T (ψ_{ω,K}^{1/2}, ψ_{ω,K′}, ψ_{ω,K}^{1/2}) = 1 + O(d^{2}K/K′).

More generally, for any subset A′ ⊆ Z/pZ we have

T (ψ_{ω,K}^{1/2}, ψ_{ω,K′}, χ_{A′}ψ_{ω,K}^{1/2}) = (1 + O(d^{2}K/K′)) ∫ χ_{A′}ψ_{ω,K}.  (5)

Proof It suffices to prove (5). The left-hand side is

∫ χ_{A′}(x)ψ_{ω,K}(x)^{1/2}(∫ ψ_{ω,K}(x − 2y)^{1/2}ψ_{ω,K′}(y) dy) dx,

where we have used the even-ness of ψ_{ω,K}. Since ψ_{ω,K}^{1/2} is a scalar multiple of ψ_{ω,K/2}, we may use Lemma 4.3 to write this as

∫ χ_{A′}(x)ψ_{ω,K}(x)^{1/2}ψ_{ω,K}(x)^{1/2}(1 + O(d^{2}K/K′)) dx

and the claim follows from the L^{1} normalization of ψ_{ω,K}.

Secondly, if the Fourier coefficient of a wide projection is large, then so is the coefficient of the narrow projection:

Lemma 4.5. Let ω ∈ (Z/pZ)^{d} and K′ ≫ d^{2}K. Suppose that ξ ∈ Z/pZ is such that

|ψ̂_{ω,K}(−2ξ)| ≫ d^{2} \frac{K}{K′} .

Then we have

|ψ̂_{ω/2,K′}(ξ)| ∼ 1.

Proof Write ω′ := ω/2. Let y ∈ Z/pZ be such that ∥yω′/p∥ ≤ d^{2}/K′. Then if we write y′ := y/2 in Z/pZ, then ∥y′ω/p∥ ≤ d^{2}/K′. In particular, we have

ψ_{ω,K}(x + y′) − ψ_{ω,K}(x) = O(d^{2} \frac{K}{K′} ψ_{ω,K}).

Integrating this against e^{−2πi(−2ξ)x/p}, we obtain

(e^{2πii(2ξ)y′/p} − 1)ψ̂_{ω,K}(−2ξ) = O(d^{2} \frac{K}{K′}).

By hypothesis we thus have

|e^{2πii(2ξ)y′/p} − 1| ≪ 1,

so in particular

|e^{−2πiiξy/p} − 1| ≪ 1.

Integrating this against ψ_{ω′,K′} we obtain

∫_{∥yω′/p∥≤d^{2}/K′}(e^{−2πiiξy/p} − 1)ψ_{ω′,K′}(y) dy| ≪ 1.

On the other hand, from Lema 4.2 we have

∫_{∥yω′/p∥≥d^{2}/K′}(e^{−2πiiξy/p} − 1)ψ_{ω′,K′}(y) dy| ≪ 1.

Adding the two, we obtain the claim.

Finally, we present one of the inductive steps, reminiscent of Roth’s argument: if χ_{A′} has density δ on ψ_{ω,K}, and (χ_{A′} − δ)ψ_{ω,K} has a large Fourier coefficient, then some translate of χ_{A′} has density strictly greater than δ for some refined cutoff ψ_{ω′,K′}.

Lemma 4.6. Let ω ∈ (Z/pZ)^{d} and K′ ≫ d^{2}K. Suppose that A′ is a subset of Z/pZ, and set δ := ∫ χ_{A′}ψ_{ω,K}. Write f := (χ_{A′} − δ)ψ_{ω,K}. Suppose we have a frequency ξ ∈ Z/pZ such that |f̂(ξ)| ≫ \frac{d^{2}K}{K′}. Then there exists an ω′ ∈ (Z/pZ)^{d+1} and a translate A′′ of A′ such that

∫ χ_{A′′}ψ_{ω′,K′} ≥ δ + c|f̂(ξ)|.

Proof Write ω′ := (ω, ξ). By construction (and Lemma 4.2), we see that

ψ̂_{ω′,K′}(ξ) ∼ 1

since the phase e^{−2πixξ/p} is close to 1 on the effective support of ψ_{ω′,K′}. Thus we have

|f̂(ξ)ψ̂_{ω′,K′}(ξ)| ∼ |f̂(ξ)|

and in particular that

∥f ∗ ψ_{ω′,K′}∥_{1} ≳ |f̂(ξ)|.

Since f has mean zero, so does f ∗ ψ_{ω′,K′}. Thus we have

∫ (f ∗ ψ_{ω′,K′})_{+} ≳ |f̂(ξ)|,

and by the pigeonhole principle so there exists an x such that

f ∗ ψ_{ω′,K′}(x) ≳ |f̂(ξ)|ψ_{ω,K}(x).

But by Lemma 4.3, we have

ψ_{ω,K} ∗ ψ_{ω′,K′}(x) = (1 + O(\frac{d^{2}K}{K′}))ψ_{ω,K}(x)

and

χ_{A′}ψ_{ω,K} ∗ ψ_{ω′,K′}(x) = (1 + O(\frac{d^{2}K}{K′}))(χ_{A′} ∗ ψ_{ω′,K′})(x)ψ_{ω,K}(x),

so we conclude that

χ_{A′} ∗ ψ_{ω′,K′}(x) − δ ≳ |f̂(ξ)|

and the claim follows.

5. Putting it all together

Using all the above tools, we can now conclude Bourgain’s argument. Recall that we are assuming A to have density δ_{0} and no proper arithmetic progressions of length 3. Let C_{0} be a large absolute constant (e.g. C_{0} = 1000); assume that p ≫ (1/δ)^{C_{0}^{5}/δ^{2}}. The key inductive step is the following:

Proposition 5.1. Let d ≤ C_{0}/δ_{0}, let ω ∈ (Z/pZ)^{d}, and let 1 ≤ K ≤ δ^{C_{0}/δ_{0}}. Suppose we have a translate A′ of A such that

∫ χ_{A′}ψ_{ω,K} = δ

for some δ_{0} ≤ δ ≤ 1. Then there exists ω′ ∈ (Z/pZ)^{d+1} , K′ ≤ δ^{−C}K and a translate A′′ of A′ such that

∫ χ_{A′′}ψ_{ω,K′} = δ′

where δ′ ≥ δ + cδ^{2}.

Proof The first step is to refine ψ_{ω,K} a little bit in such a way that the density of A′ remains close to δ.

Set K_{j} := (cd^{2}δ^{2})^{j}K for j = 1, 2, 3. From Lemma 4.3 we have

∫ χ_{A′}(ψ_{ω,K} ∗ ψ_{ω,K_{j}} − ψ_{ω,K}) = O(cδ^{2})

for j = 1, 2, and hence

∫ χ_{A′}(ψ_{ω,K} ∗ ψ_{ω,K_{j}}) = δ + O(cδ^{2})

LECTURE NOTES 5 9

which can be rewritten (using the L^{1} normalization of ψ_{ω,K}) as ∫ χ_{A′}(ψ_{ω,K} ∗ ψ_{ω,K_{j}}) = δ + O(cδ^{2})

∫ (χ_{A′} ∗ ψ_{ω,K_{j}} − δ)ψ_{ω,K} = O(cδ^{2}).

Also we can assume that

(χ_{A′} ∗ ψ_{ω,K_{j}} − δ)(x) < cδ^{2}

for all x ∈ Z/pZ, since we are done otherwise (by setting K′ := K, ω′ = (ω, 0), and A′′ := A′ − x). In particular we have

∫ (χ_{A′} ∗ ψ_{ω,K_{j}} − δ)_{+}ψ_{ω,K} = O(cδ^{2}).

Combining this with the previous we see that

∫ ∑_{j=1}^{2} |χ_{A′} ∗ ψ_{ω,K_{j}} − δ|ψ_{ω,K} = O(cδ^{2}).

By the pigeonhole principle we can thus find an x_{0} such that

∑_{j=1}^{2} |χ_{A′} ∗ ψ_{ω,K_{j}} − δ|(x_{0}) = O(cδ^{2}).

Without loss of generality we can take x_{0} = 0. Thus we have

∫ χ_{A′}(x)ψ_{ω,K_{j}}(x) = δ + O(cδ^{2})  (6)

for j = 1, 2. Now we compute the quantity

T (χ_{A′}ψ_{ω,K_{1}}^{1/2}, χ_{A′}ψ_{ω,K_{2}}, χ_{A′}ψ_{ω,K_{1}}^{1/2}) − T (δψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, δψ_{ω,K_{1}}^{1/2}).  (7)

Since A has no proper arithmetic progressions of length 3, we have (1). In particular from Lemma 4.1 we have the very crude bound

T (χ_{A′}ψ_{ω,K_{1}}^{1/2}, χ_{A′}ψ_{ω,K_{2}}, χ_{A′}ψ_{ω,K_{1}}^{1/2}) ≤ (CdK_{2})^{Cd}/p.

On the other hand, from Corollary 4.4 we have

T (δψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, δψ_{ω,K_{1}}^{1/2}) ∼ δ^{3}.

From our lower bounds on p and upper bounds on d, K_{2} we thus have

|(7)| ∼ δ^{3}.

Now we split (7) into pieces. We first investigate the quantity

T (χ_{A′}ψ_{ω,K_{1}}^{1/2}, χ_{A′}ψ_{ω,K_{2}}, χ_{A′}ψ_{ω,K_{1}}^{1/2}) − T (χ_{A′}ψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, χ_{A′}ψ_{ω,K_{1}}^{1/2}). (8)

Suppose first that |(8)| ≳ δ^{3}. By (2) we thus have

∑_{ξ} |{ \atop χ_{A′}ψ_{ω,K_{1}}^{1/2}}(ξ)|^{2}|{ \atop (χ_{A′} − δ)ψ_{ω,K_{2}}}(−2ξ)| ≳ δ^{3}.

10 TERENCE TAO

But by Plancherel we have

∑_{ξ} |{ \atop χ_{A′}ψ_{ω,K_{1}}^{1/2}}(ξ)|^{2} = ∫ χ_{A′}ψ_{ω,K_{1}} ∼ δ

and hence we have a frequency ξ such that

|{ \atop (χ_{A′} − δ)ψ_{ω,K_{2}}}(−2ξ)| ≳ δ^{2}.

By Lemma 4.6 we can thus find a translate A′′ of A, an ω′ ∈ (Z/pZ)^{d+1} such that

∫ χ_{A′′}ψ_{ω′,K_{3}} ≥ δ + cδ^{2}

as desired. We may now suppose that |(8)| ≪ δ^{3}, which implies that

T (χ_{A′}ψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, χ_{A′}ψ_{ω,K_{1}}^{1/2}) − T (δψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, δψ_{ω,K_{1}}^{1/2})

has magnitude ∼ δ^{3}. We split this as a linear combination of

T (δψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, (χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2})  (9)

and

T ((χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, (χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2})  (10)

where we use the symmetry T (f, g, h) = T (h, f, g). To estimate (9), we observe from Corollary 4.4 that

T (δψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, δψ_{ω,K_{1}}^{1/2}) = δ^{3} + O(cδ^{4})

and

T (δψ_{ω,K_{1}}^{1/2}, δψ_{ω,K_{2}}, χ_{A′}ψ_{ω,K_{1}}^{1/2}) = δ^{2}(1 + O(cδ))(∫ χ_{A′}ψ_{ω,K_{1}}) = δ^{3} + O(cδ^{4})

and so (9) is O(cδ^{4}). Thus we must have |(10)| ∼ δ^{3}, thus by (2)

∑_{ξ} |{ \atop (χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}}(ξ)|^{2}|{ \atop ψ_{ω,K_{2}}}(−2ξ)| ≳ δ^{3}.

On the other hand, from Plancherel we have

∑_{ξ} |{ \atop (χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}}(ξ)|^{2} = ∫ (χ_{A′} − δ)^{2}ψ_{ω,K_{1}} = O(δ),

and thus we have

∑_{ξ:|{ \atop ψ_{ω,K_{2}}} (−2ξ)|≳cδ^{2}} |{ \atop (χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}}(ξ)|^{2}|{ \atop ψ_{ω,K_{2}}}(−2ξ)| ≳ δ^{3}.

By Lemma 4.5 we thus have

∑_{ξ} |{ \atop (χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}}(ξ)|^{2}|{ \atop ψ_{ω/2,K_{3}}}(ξ)|^{2} ≳ δ^{3},

which by Plancherel implies that

∫ |((χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}) ∗ ψ_{ω/2,K_{3}}|^{2} ≳ δ^{3}.  (11)

So now let us investigate the quantity

|((χ_{A′} − δ)ψ_{ω,K_{1}}^{1/2}) ∗ ψ_{ω/2,K_{3}}|(x).

We can rewrite this as

∫ (χ_{A′}(x − y) − δ)ψ_{ω,K_{1}}^{1/2}(x − y)ψ_{ω/2,K_{3}}(y) dy.

By Lemma 4.3, this is equal to

∫ (χ_{A′}(x − y) − δ)ψ_{ω/2,K_{3}}(y) dyψ_{ω,K_{1}}^{1/2}(x) + O(cδ^{2}ψ_{ω,K_{1}}^{1/2}(x)).

The error term contributes O(cδ^{4}) to (11), and hence we have

∫ | ∫ (χ_{A′}(x − y) − δ)ψ_{ω/2,K_{3}}(y) dy|^{2}ψ_{ω,K_{1}}(x) dx ≳ δ^{3}.  (12)

Note that we may assume as before that

∫ (χ_{A′}(x − y) − δ)ψ_{ω/2,K_{3}}(y) dy ≤ cδ^{2}  (13)

for all x, since we are done otherwise. In particular, the expression in absolute values in (12) is bounded by δ, and we thus have

∫ | ∫ (χ_{A′}(x − y) − δ)ψ_{ω/2,K_{3}}(y) dy|ψ_{ω,K_{1}}(x) dx ≳ δ^{2}.

From this and (13) we have

| ∫ ∫ (χ_{A′}(x − y) − δ)ψ_{ω/2,K_{3}}(y) dyψ_{ω,K_{1}}(x) dx| ≳ δ^{2}.

or equivalently,

| ∫ (χ_{A′} − δ)(ψ_{ω/2,K_{3}} ∗ ψ_{ω,K_{1}})| ≳ δ^{2}.

From Lemma 4.3 we may replace ψ_{ω/2,K_{3}} ∗ψ_{ω,K_{1}} by ψ_{ω,K_{1}} with an acceptable error, thus

| ∫ (χ_{A′} − δ)ψ_{ω,K_{1}}| ≳ δ^{2}.

But this contradicts (6). This proves the Proposition.

Observe that the map δ → δ + cδ^{2} will reach size > 1 after most C/δ_{0} steps, starting from δ_{0}. Thus iterating Proposition 5.1 this many times (starting with d = 0, K = 1, and A′ = A), we can eventually get the density greater than 1, a contradiction. Thus A must contain a progression of length 3.

6. Exercises

• Q1. Let ε > 0 be a small number. Suppose we knew that for every large N ≫ 1 and every subset A ⊆ {1, …, N} of density at least 1/(log N)^{1+ε} contained a non-trivial arithmetic progression of length 3. Deduce that for any subset B ⊂ Z^{+} with ∑_{n∈A} 1/n = ∞ contains an infinite number of arithmetic progressions of length 3.

• Q2. Show that the following two statements are equivalent: (a) For every N ≫ 1 and every subset A of \{1, …, N\} of density ≫ \sqrt{log log N}/\sqrt{log N}, A contains a proper arithmetic progression of order 3. (b) For every δ and every N ≫ (\frac{1}{δ})^{C/δ^{2}}, any subset A of \{1, …, N\} of density at least δ will contain an arithmetic progression of order 3. (Note: this equivalence has nothing to do with arithmetic progressions, and is basically a matter of algebra.)

References

[1] F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc. Nat. Acad. Sci. 32 (1946), 331–332

[2] J. Bourgain, On triples in arithmetic progression, GAFA 9 (1999), 968–984.

[3] P. Erdös, P. Turan, On some sequences of integers, J. London Math. Soc. 11 (1936), , 261– 264.

[4] D.R. Heath-Brown, Integer sets containing no arithmetic progressions, J. London Math. Soc. 35 (1987), 385–394.

[5] I. Laba, M. Lacey, On sets of integers not containing long arithmetic progressions, preprint.

[6] R.A. Rankin, Sets of integers containing not more than a given number of terms in arithmetic progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960/1961), 332–344.

[7] K.F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953), 245–252.

[8] R. Salem, D.C. Spencer, On sets of integers which contain no three terms in arithmetic progression, Proc. Nat. Acad. Sci. 32 (1942), 561-563.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu