THE ROTH-BOURGAIN THEOREM

TERENCE TAO

Abstract. An exposition of Bourgain’s version of Roth’s theorem.

1. Introduction

A famous theorem of Roth [3] shows that any subset of the integers of positive density contains infinitely many progressions of length three. This theorem has since been generalized and refined by many authors. Here we present a strengthened, quantitative version of Roth’s theorem due to Bourgain [2], which gives the best bound known to date on the problem.

We will phrase things in a finite additive group Z = (Z, +). It is convenient to use probabilistic notation, viewing Z as a probability space (with every element x ∈ Z having equal probability 1/|Z|. Thus an event is a set A ⊆ Z, which is assigned the probability P(A) := |A|/|Z|. Similarly, a random variable is a function f : Z → C with expectation E(f) = E(f(x)|x ∈ Z) := \frac{1}{|Z|} ∑_{x∈Z} f(x). We also use the conditional expectations P(A|B) := P(A ∩ B)/P(B) and E(f|B) = E(f1_{B})/P(B).

We also define the trilinear form Λ_{3}(f, g, h) for any three random variables f, g, h : Z → C as

Λ_{3}(f, g, h) := E(f(x)g(x + r)h(x + 2r)|x, r ∈ Z);

note in particular that Λ_{3}(1_{A}, 1_{A}, 1_{A}) counts the number of progressions x, x+r, x+ 2r of length three in A (including the |A| trivial progressions when r = 0), divided by the normalizing factor of Z. This form can also be conveniently expressed using a Fourier transform. We introduce a bicharacter e : Z × Z → S^{1}, obeying the multiplicativity properties

e(x + x′, ξ) = e(x, ξ)e(x′, ξ); e(x, ξ + ξ′) = e(x, ξ)e(x, ξ′)

and is non-degenerate in the sense that e(x, ·) ≡ 1 if and only if x = 0, and e(·, ξ) ≡ 1 if and only if ξ = 0. Such a bi-character always exists, as can be seen from the characterization of finite abelian groups. We then have the Fourier transform

f̂(ξ) := E(f(x)\overline{e(x, ξ)}|x ∈ Z)

the Plancherel formula

∑_{ξ∈Z} |f̂(ξ)|^{2} = E(|f|^{2})  (1)

and the inversion formula

f(x) = ∑_{ξ∈Z} f̂(ξ)e(x, ξ).

1991 Mathematics Subject Classification. 42B15, 35L05.

From the latter formula one can easily verify the identity

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

With these preliminaries, we can now state the Roth-Bourgain theorem.

Theorem 1.1 (Roth-Bourgain theorem). [2] Let δ > 0 and let Z be a finite additive group of odd order. Then for any event A ⊆ Z with P(A) ≥ δ, we have Λ_{3}(1_{A}, 1_{A}, 1_{A}) ≥ (Cδ)^{−C/δ^{2}} for some absolute constant C > 0.

This theorem was proven by Bourgain in [2]; a related earlier result is in [1]. It easily implies that when N is large, any subset of {1, …, N} with density at least \frac{C\sqrt{log log N}}{\sqrt{log N}} for a sufficiently large absolute constant C > 0 will contain a proper arithmetic progression of length three. In comparison, the original argument of Roth requires a density of C/ log log N.

Roth’s original argument uses Fourier analysis to conclude that a set in {1, …, N} either has a large number of arithmetic progressions of length three, or has a density increment on some relatively short subprogression of \{1, …, N\} (of length \sqrt{N} or so); one then iterates this observation until the density stops incrementing. In contrast, Bourgain’s argument obtains a density increment on a Bohr set instead of a subprogression; after iteration one gets Bohr sets of fairly large “dimension”. These Bohr sets behave like progressions but have worse behavior with respect to doubling; if B is a Bohr set of dimension d, B + B can be roughly 2^{d} as large as B. This causes problems with the estimates, but is resolved by a neat trick of Bourgain, in which one works with pairs B, B′ of Bohr sets with B′ much narrower than B, so that B + B′ is only a little bit different from B and one does not lose as many factors of 2^{d} in the argument.

We now define Bohr sets rigorously.

Definition 1.2 (Bohr sets). Let S ⊂ Z be a set of frequencies, let z = (z_{ξ})_{ξ∈S} ∈ C^{S} be a collection of complex numbers, and let 0 < r ≤ 2. We define the Bohr set Bohr_{Z}(S, r, z) ⊆ Z to be the set

Bohr_{Z}(S, r, z) := {x ∈ Z : |e(x, ξ) − z_{ξ}| ≤ r for all ξ ∈ S}.

In particular we have

Bohr_{Z}(S, r, 1) := {x ∈ Z : |e(x, ξ) − 1| ≤ r for all ξ ∈ S}.

Observe that any translate h + Bohr_{Z}(S, r, z) is also a Bohr set,

h + Bohr_{Z}(S, r, z) = Bohr_{Z}(S, r, z′), where z′_{ξ} = e(h, ξ)z_{ξ}.

Also observe that Bohr_{Z}(S, r, 1) is symmetric around the origin.

It turns out that some Bohr sets will be too “irregular” to be usable, in the sense that the “boundary” of the Bohr set is too large compared to the “interior”. A very useful observation of Bourgain is that one can easily restrict one’s attention to regular Bohr sets.

Definition 1.3. Let 0 < δ_{0} < 1/2 be a small parameter. We say that a Bohr set Bohr_{Z}(S, r, z) is regular with respect to δ_{0} (or regular for short) if it is non-empty and we have the estimate

P(Bohr_{Z}(S, (1 + δ_{0}^{10})r, z)\Bohr_{Z}(S, (1 − δ_{0}^{10})r, z)) ≤ δ_{0}^{5}P(Bohr_{Z}(S, r, z)).

The powers of 10 and 5 in the above definition should not be taken too seriously; they ultimately affect the constant C in Theorem 1.1 but are otherwise irrelevant. The parameter δ_{0} will be fixed throughout the argument. Observe that the translate of a regular Bohr set is another regular Bohr set. Let us now give two simple lemmas that show that regular Bohr sets are both fairly large, and fairly common.

Lemma 1.4. Let Bohr_{Z}(S, r, z) be a regular Bohr set. Then

P(Bohr_{Z}(S, r, z)) ≥ (C^{−1}δ_{0}^{10}r)^{|S|}

for some absolute constant C > 0.

Proof By the regularity of Bohr_{Z}(S, r, z), we see that Bohr_{Z}(S, r, z)\Bohr_{Z}(S, (1− δ_{0}^{10})r, z)) is strictly smaller than Bohr_{Z}(S, r, z), thus there exists h ∈ Bohr_{Z}(S, (1− δ_{0}^{10})r, z)). By the triangle inequality, we then has the inclusion

Bohr_{Z}(S, r, z) ⊇ h + Bohr_{Z}(S, δ_{0}^{10}r).

On the other hand, a simple volume packing argument (partitioning the torus (R/Z)^{S} into cubes of side-length roughly δ_{0}^{10}r/2, and using the pigeonhole principle to find one cube which contains many points of the form (e(x, ξ))_{ξ∈S}, as in the proof of the Kronecker approximation theorem) we have we have

P(Bohr_{Z}(S, δ_{0}^{10}r)) ≥ (C^{−1}δ_{0}^{10}r)^{|S|}.

The claim follows.

Lemma 1.5. If δ_{0} > 0 is sufficiently small, then for all S ⊆ Z with |S| ≤ δ_{0}^{−2} and r_{0} > 0 there exists r_{0}/2 < r < r_{0} such that Bohr_{Z}(S, r, 1) is regular.

Proof We can find radii r_{0} > r_{1} > … > r_{N} > r_{N+1} = r_{0}/2 with N = Θ(δ_{0}^{−10}) and

r_{i+1} ≤ (1 − δ_{0}^{10})r_{i} ≤ (1 + δ_{0}^{10})r_{i} ≤ r_{i−1} for all 1 ≤ i ≤ N.

On the other hand, a simple Vitali covering lemma argument shows that

P(Bohr_{Z}(S, r_{0}, 1)) ≤ C^{|S|}P(Bohr_{Z}(S, r_{0}/2, 1)).  (3)

Hence by the pigeonhole principle we can find 1 ≤ i ≤ N such that

P(Bohr_{Z}(S, r_{i−1}, 1)) ≤ C^{2|S|/N}P(Bohr_{Z}(S, r_{i+1}, 1)).

Since |S| ≤ δ_{0}^{−2}, C^{2|S|/N} = 1 + O(δ_{0}^{8}). The claim then follows by setting r := r_{i}.

Theorem 1.1 will now follow from the following key proposition.

Proposition 1.6 (Lack of progressions implies density increment). [2] If 0 < δ_{0} < 1/2 is a sufficienty small quantity, then the following statement is true: for any finite additive group Z of odd order, any regular Bohr set B := Bohr_{Z}(S, r, z) with |S| < δ_{0}^{−2}, and any event A ⊆ Z with P(A|B) ≥ δ_{0}, at least one of the following statements is true:

• (Arithmetic progressions) We have Λ_{3}(1_{A}, 1_{A}, 1_{A}) ≥ C^{−1}(δ_{0}^{C}r)^{|S|} for some absolute constant C > 0.

• (Density increment) There exists a regular Bohr set B′ := Bohr_{Z}(S′, r′, z′) with |S′| ≤ |S| + 1 and r′ ≥ δ_{0}^{100}r such that

P(A|B′) ≥ P(A|B) + cP(A|B)^{2}

for some absolute constant 0 < c < 1.

Let us assume this proposition for the moment and see how it implies Theorem 1.1. Proof [Proof of Theorem 1.1] We set δ_{0} := min(δ, C^{−1}), where C is an absolute constant so large that Proposition 1.6 will apply to this value of δ_{0}.

We now apply the following algorithm to locate a Bohr set B.

• Step 0. Initialize B = Bohr(S, z, r) to be the trivial Bohr set B = Z, with S = ∅, z = (), and r = 1. Observe that this Bohr set is trivially regular.

• Step 1. If there exists a regular Bohr set B′ = Bohr_{Z}(S′, r′, z′) with |S′| ≤ |S| + 1 and r′ ≤ δ^{100}r such that P(A|B′) ≥ P(A|B) + cP(A|B)^{2}, where c > 0 is the constant in Proposition 1.6, then we replace B with B′ and return to Step 1. Otherwise, we halt the algorithm.

Observe that if 1 ≥ P(A|B′) ≥ P(A|B) + cP(A|B)^{2}, then 1 ≤ \frac{1}{P(A|B′)} ≤

\frac{1}{P(A|B)} − c′ for some absolute constant c′ > 0 depending on c. Since P(A|B) cannot exceed 1, and is initially at least δ, we see that the above algorithm must terminate in O(1/δ) steps. In particular, the parameters S, z, r of the final Bohr set B will obey the estimates |S| = O(1/δ) and r ≥ δ^{O(1/δ)}. In particular, if δ is sufficiently small, we will have |S| < δ^{−2}. Applying Proposition 1.6 we conclude that

Λ_{3}(1_{A}, 1_{A}, 1_{A}) ≥ C^{−1}(δ^{C}r)^{|S|} ≥ (Cδ)^{C/δ^{2}}

as desired.

It remains to prove Proposition 1.6. Proof [Proof of Proposition 1.6] Fix f, B = Bohr_{Z}(S, r, z), and set δ := P(A|B) ≥ δ_{0}. Let 0 < c < 1 be a small constant to be chosen later, and assume that

P(A|B′) ≤ δ + cδ^{2}  (4)

for any regular Bohr set B′ := Bohr_{Z}(S′, r′, z′) with |S′| ≤ |S| + 1 and r′ ≥ δ_{0}^{100}r. Our task is then to establish te bound Λ_{3}(1_{A}, 1_{A}, 1_{A}) ≥ C^{−1}(δ_{0}^{C}r)^{|S|} for some absolute constant C > 0.

We first need to narrow B slightly into two slightly different regular Bohr sets B_{1}, B_{2}. By Lemma 1.5 we can find regular Bohr sets B_{1} := Bohr_{Z}(S, r_{1}, 1) and B_{2} := Bohr(S, r_{2}, 1) with r_{1} = Θ(δ_{0}^{20}r) and r_{2} = Θ(δ_{0}^{40}r). Observe that for i = 1, 2, the convolution 1_{B} ∗ 1_{B_{i}} is equal to P(B_{i}) on Bohr_{Z}(S, (1 − δ_{0}^{10})r, z), vanishes outside of Bohr_{Z}(S, (1 + δ_{0}^{10})r, z), and lies between 0 and P(B_{i}) in between. Using the regularity of B, we conclude that

E(1_{A}(1_{B} ∗ 1_{B_{i}})) ≥ (δ + O(δ_{0}^{5}))P(B_{i})P(B) for i = 1, 2.

On the other hand, we can rearrange

E(1_{A}(1_{B} ∗ 1_{B_{i}})) = E(P(A|x + B_{i})|x ∈ B)P(B_{i})P(B)

and hence

E(P(A|x + B_{i}) − δ|x ∈ B) = O(δ_{0}^{5}).

On the other hand, from (4) (with B′ := x + B_{i}) we have P(A|x + B_{i}) − δ ≤ cδ^{2} for all x. Thus by the triangle inequality

E( ∑_{i=1,2} |P(A|x + B_{i}) − δ||x ∈ B) = O(cδ^{2}).

THE ROTH-BOURGAIN THEOREM 5

By the pigeonhole principle, we can then find an x_{0} ∈ B such that

P(A|x_{0} + B_{i}) = δ + O(cδ^{2}) for i = 1, 2.

By translating A and B if necessary we may assume x_{0} = 0, thus we now have

P(A|B_{1}), P(A|B_{2}) = δ + O(cδ^{2}).  (5)

We now use the positivity of 1_{A} to estimate Λ_{3}(A, A, A) from below as

\begin{aligned}Λ_{3}(1_{A}, 1_{A}, 1_{A}) & ≥ Λ_{3}(1_{A}1_{B_{1}}, 1_{A}1_{B_{2}}, 1_{A}1_{B_{1}}) \\ & = δΛ_{3}(1_{A}1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}}) + Λ_{3}(1_{A}1_{B_{1}}, (1_{A} − δ)1_{B_{2}}, 1_{A}1_{B_{1}}) \\ & = δ^{2}Λ_{3}(1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}}) + δΛ_{3}((1_{A} − δ)1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}}) \\ & + Λ_{3}(1_{A}1_{B_{1}}, (1_{A} − δ)1_{B_{2}}, 1_{A}1_{B_{1}}). \end{aligned} (6)

It will be important that the second factor of Λ_{3} is supported on a narrower Bohr set than the first and third factors.

We now estimate the three terms on the right-hand side of (6) separately. We begin with the first term, which is the main term. Since B_{1}, B_{2} are symmetric around the origin, and Z has odd order, we may rewrite

Λ_{3}(1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}}) = E(1_{A}1_{B_{1}}(1_{B_{1}} ∗ 1_{2·B_{2}})).

Observe that 1_{B_{1}} ∗ 1_{2·B_{2}} equals P(2 · B_{2}) = P(B_{2}) on Bohr_{Z}(S, (1 − δ_{0}^{10})r, 1) and is non-negative elsewhere. Using the regularity of B_{1}, we then conclude

E(1_{A}1_{B_{1}}(1_{B_{1}} ∗ 1_{2·B_{2}})) ≥ P(B_{2})E(1_{A}1_{B_{1}}) − δ_{0}^{5}P(B_{1})P(B_{2}),

and hence by (5) we conclude that

δ^{2}Λ_{3}(1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}}) ≥ (δ^{3} − O(δ^{2}δ_{0}^{5}))P(B_{1})P(B_{2}).  (7)

Now we turn to the second term in (6), which is a minor term. We rewrite Λ_{3}((1_{A} −δ)1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}}) = E(E(1_{A} −δ1_{B_{1}}|h−2·B_{2})1_{A}(h)|h ∈ B_{1})P(B_{1})P(B_{2}) and hence by the triangle inequality |δΛ_{3}((1_{A} − δ)1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}})| ≤ δE(|E(1_{A} − δ1_{B_{1}}|h − 2 · B_{2})||h ∈ B_{1})P(B_{1})P(B_{2}) On the other hand, since B_{2} is regular, so is h − 2 · B_{2} (here we use that Z has odd order). By (4), we conclude that E((1_{A} − δ)1_{B_{1}}|h − 2 · B_{2}) ≤ cδ^{2}, and hence |δΛ_{3}((1_{A}−δ)1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}})| ≤ (δ|E(E((1_{A}−δ)1_{B_{1}}|h−2·B_{2})||h ∈ B_{1})|+O(cδ^{3}))P(B_{1})P(B_{2}). On the other hand, we can rearrange E(E((1_{A} − δ)1_{B_{1}}|h − 2 · B_{2})||h ∈ B_{1})P(B_{1})P(B_{2}) = E((1_{A} − δ)1_{B_{1}}(1_{B_{1}} ∗ 1_{2·B_{2}})) and by arguing as with the first term in (6) we have E((1_{A}−δ)1_{B_{1}}(1_{B_{1}}∗1_{2·B_{2}})) = P(B_{2})E((1_{A}−δ)1_{B_{1}})−O(δ_{0}^{5})P(B_{1})P(B_{2}) = [O(cδ^{2})+O(δ_{0}^{5})]P(B_{1})P(B_{2}). We conclude (since δ_{0} ≤ δ is small) that

|δΛ_{3}((1_{A} − δ)1_{B_{1}}, 1_{B_{2}}, 1_{A}1_{B_{1}})| = O(cδ^{3})P(B_{1})P(B_{2}).  (8)

Finally we consider the third term in (6), which is the most interesting term. Using (2) we have

|Λ_{3}(1_{A}1_{B_{1}}, (1_{A} − δ)1_{B_{2}}, 1_{A}1_{B_{1}})| ≤ ∑_{ξ∈Z} |{ \atop 1_{A}1_{B_{1}}}|(ξ)^{2}|{ \atop (1_{A} − δ)1_{B_{2}}}(−2ξ)|.

6 TERENCE TAO

On the other hand, from (1) we have

∑_{ξ∈Z} |{ \atop 1_{A}1_{B_{1}}}|(ξ)^{2} = E(|1_{A}1_{B_{1}}|^{2}) = P(A|B_{1})P(B_{1}) = O(δ)P(B_{1})

while

{ \atop (1_{A} − δ)1_{B_{2}}}(−2ξ) = E((1_{A}(x) − δ)e(x, 2ξ)|B_{2})P(B_{2}).

Thus we have

|Λ_{3}(1_{A}1_{B_{1}}, (1_{A} − δ)1_{B_{2}}, 1_{A}1_{B_{1}})| = O(δP(B_{1})P(B_{2}) sup_{ξ∈Z} E((1_{A}(x) − δ)e(x, 2ξ)|B_{2})).

To estimate this, we use Lemma 1.7. For any ξ ∈ Z, we have E((1_{A}(x) − δ)e(x, 2ξ)|B_{2})) = O(cδ^{2}). Proof Let us write σ := |E((1_{A}(x) − δ)e(x, 2ξ)|B_{2})|, thus

|E((1_{A}(x) − δ)e(x, 2ξ)1_{B_{2}}(x))| = σP(B_{2}).

Also, from (5) we have

|E((1_{A}(x) − δ)1_{B_{2}}(x))| = O(cδ^{2})P(B_{2}).

Let S′ := S∪{2ξ}. By Lemma 1.5 we can find a regular Bohr set B_{3} = Bohr_{Z}(S′, r_{3}, 1) with r_{3} = Θ(δ_{0}^{60}r). Arguing as before, we see that 1_{B_{2}} ∗ 1_{B_{3}} equals P(B_{3}) on Bohr(S, (1−δ_{0}^{10})r_{2}, 1), vanishes outside of Bohr(S, (1+δ_{0}^{10})r_{2}, 1), lies between P(B_{3}) and 0 otherwise, thus by the regularity of B_{2} we have

|E((1_{A}(x) − δ)e(x, 2ξ)(1_{B_{2}} ∗ 1_{B_{3}})(x))| = (σ + O(δ_{0}^{5}))P(B_{2})P(B_{3}) and similarly

|E((1_{A}(x) − δ)(1_{B_{2}} ∗ 1_{B_{3}})(x))| = O(cδ^{2})P(B_{2})P(B_{3}).

We can rearrange E((1_{A}(x)−δ)e(x, 2ξ)(1_{B_{2}}∗1_{B_{3}})(x)) = E(E((1_{A}(x)−δ)e(x, 2ξ)|x ∈ h+B_{3})|h ∈ B_{2})P(B_{2})P(B_{3}) to conclude

|E(E((1_{A}(x) − δ)e(x, 2ξ)|x ∈ h + B_{3})|h ∈ B_{2})| ≥ σ + O(δ_{0}^{5})

and similarly

|E(E((1_{A}(x) − δ)|x ∈ h + B_{3})|h ∈ B_{2})| = O(cδ^{2}).

On the other hand, from (4) we have E((1_{A}(x) − δ)|x ∈ h + B_{3}) ≤ cδ^{2} for all h, and hence

|E(|E((1_{A}(x) − δ)|x ∈ h + B_{3})||h ∈ B_{2})| = O(cδ^{2}).

On the other hand, if x ∈ h + B_{3}, then e(x, 2ξ) = e(h, 2ξ) + O(r_{3}) by definition of the Bohr set B_{3}, and thus E((1_{A}(x) − δ)e(x, 2ξ)|x ∈ h + B_{3}) = e(h, 2ξ)E((1_{A}(x) − δ)|x ∈ h + B_{3}) + O(r_{3}). Thus by the triangle inequality |E(E((1_{A}(x)−δ)e(x, 2ξ)|x ∈ h+B_{3})|h ∈ B_{2})| ≤ E(|E((1_{A}(x)−δ)|x ∈ h+B_{3})|)+O(r_{3}) ≤ O(cδ^{2})+O(r_{3}) and hence

σ ≤ O(cδ^{2}) + O(r_{3}) + O(δ_{0}^{5}) = O(cδ^{2})

as desired.

Inserting this lemma into the previous estimate we conclude that

|Λ_{3}(1_{A}1_{B_{1}}, (1_{A} − δ)1_{B_{2}}, 1_{A}1_{B_{1}})| = O(cδ^{3})P(B_{1})P(B_{2});

from this, (6), (7), (8) we conclude

Λ_{3}(1_{A}, 1_{A}, 1_{A}) ≥ (δ^{3} − O(cδ^{3}))P(B_{1})P(B_{2})

and the desired lower bound on Λ_{3}(1_{A}, 1_{A}, 1_{A}) now follows from Lemma 1.4 if c is chosen suitably small.

References

[1] J. Bourgain, A Szemerédi type theorem for sets of positive density in R^{k}, Israel J. Math. 54 (1986), no. 3, 307–316.

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

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

Department of Mathematics, UCLA, Los Angeles, CA 90024

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