A TRILINEAR MAXIMAL FUNCTION ESTIMATE VIA ARITHMETIC COMBINATORICS

CIPRIAN DEMETER, TERENCE TAO, AND CHRISTOPH THIELE

Abstract. By means of a primarily combinatorial argument, we show that the discrete operator

T (f, g, h)(x) := sup_{N≥1} \frac{1}{(2N + 1)^{2}} ∑_{s=−N}^{N} ∑_{t=−N}^{N} f(x + s)g(x + t)h(x + s + t)

obeys some non-trivial estimates.

1. Introduction

Define an interval to be any set of the form I = {x − N, …, x + N}, where x ∈ Z, N ∈ Z^{+}. We refer to x = x_{I} as the length of I and N = N_{I} as the radius. One can think of the space of intervals as a discrete half-space Z_{+}^{2}; it will be convenient to work on this space instead of on the integers, and our notation for maximal functions etc. shall reflect this perspective.

For any sets E, F, G of integers, consider the quantities

T (E, F, G)(I) := \frac{1}{|I|^{2}} |\{(y, z) : y ∈ E ∩ I, z ∈ F ∩ I, y + z − x_{I} ∈ G ∩ I\}|
M(E)(I) := \frac{1}{|I|}|E ∩ I|

and their associated maximal functions

T (E, F, G)(x) := sup_{I:x_{I}=x} T (E, F, G)(I); M(E)(x) := sup_{I:x_{I}=x} M(E)(x).

Clearly we have the trivial estimate

T (E, F, G)(I) ≤ min(M(E)(I)M(F)(I), M(E)(I)M(G)(I), M(F)(I), M(G)(I)). (1)

Thus from the Hardy-Littlewood maximal inequality

|{x : M(E)(x) > λ}| ≤ Cλ^{−1}|E|  (2)

(which is, incidentally, a special case of Theorem 2.7) we immediately obtain the distributional inequality

|{x : T (E, E, E)(x) > λ^{2}}| ≤ Cλ^{−1}|E|.

The purpose of this note is to obtain the following improvement:

Theorem 1.1. There exists an absolute constant ε > 0 such that

|{x : T (E, E, E)(x) > λ^{2}}| ≤ Cλ^{−1+ε}|E|.  (3)

for some absolute constant ε > 0 and all 0 < λ ≤ 1 (the claim is vacuously true for λ > 1).

This claim will be superceded by a later paper in which we show that ε can be taken arbitrarily close to 1/3 by using time-frequency analysis, similar to that used to prove Carleson’s theorem. However, here we present a more elementary approach based on arithmetic combinatorics.

2. An abstract maximal function inequality

Let G be a discrete abelian group. Given any two sets A, B ⊂ G, we can define the sum set A + B := {a + b : a ∈ A, b ∈ B} and the difference set A − B := {a − b : a ∈ A, b ∈ B}, and then define iterated sums 2A = A + A, 3A = A + A + A, 2A − A = A + A − A, etc. We recall the following definition from [3]:

Definition 2.1. [3, Definition 2] Let k ≥ 1 and let A be a finite non-empty subset of G. We say that A is k-covering if there exists a finite set T ⊂ G of cardinality k such that A − A ⊆ A + T − T.

Examples 2.2. A finite subgroup of G is 1-covering, as is any coset of that subgroup. An arithmetic progression is 2-covering. Using the obvious generalization of the above concept to continuous groups, any interval in IR is 2-covering, while a rectangle in IR^{2} is 3-covering. One should view sets that are k-covering for small k should be

A set which is k-covering has good properties with respect to iterated sumsets. For instance, it is clear that |A − A| ≤ |A||T ||T | ≤ k^{2}|A|; another example is that

2A − 2A = (A − A) − (A − A)
⊆ (A + T − T) − (A + T − T)
= (A − A) + (2T − 2T)
⊆ A + (2T − 2T) + (T − T)
= A + 3T − 3T

and hence |2A − 2A| ≤ k^{6}|A|.

Conversely, if a set A has small sumset, then A − A is k-covering for a small k:

Lemma 2.3. [3, Lemma 3] Let A be a finite non-empty subset of G such that |A + A| ≤ K|A| for some K ≥ 1. Then A − A is 2K^{2} − 1-covering.

We also observe that the intersection of two k-covering sets is also k-covering for a small k (generalizing the observation that the intersection of two cosets of different subgroups is again a coset of a third subgroup):

Lemma 2.4. Let A, B be two non-empty finite subsets of G such that A is k-covering and B is k′-covering. Let E := (A − A) ∩ (B − B), so that E is a finite subset of G which contains 0. Then E is (kk′)^{6}-covering.

Proof By hypothesis, we have A − A ⊆ A + T − T and B − B ⊆ B + T′ − T′ for some sets T, T′ of cardinality k, k′ respectively. In particular we have

(2A − 2A) ⊆ A + 3T − 3T; (2B − 2B) ⊆ B + 3T′ − 3T′

and hence

E−E ⊆ (2A−2A)∩(2B−2B) ⊆ (A+3T −3T)∩(B+3T′−3T′) = ⋃_{t∈3T −3T,t′∈3T′−3T′}(A+t)∩(B+t′).

Now observe that if x, y are any two elements of (A + t) ∩ (B + t′), then x − y ∈ (A − A) ∩ (B − B) ∈ E. Thus every set of the form (A + t) ∩ (B + t′) can be covered by a translate of E. Since the number of pairs (t, t′) is at most (kk′)^{6}, the claim follows.

Remark 2.5. It is quite likely that one can improve the bound (kk′)^{6} here substantially, for instance by using the ideas from [3]. This would lead to an improvement of the final ε in our bounds.

A related lemma is

Lemma 2.6. Let H be a finite non-empty subset of G, and let A, B be non-empty subsets of H. Then

|(A − A) ∩ (B − B)| ≥ \frac{|A||B||H|}{|H − A||H − B|}.

Proof Observe that

∑_{y∈H−A} χ_{A+y} ≥ |A|χ_{H}

and

∑_{z∈H−B} χ_{B+z} ≥ |B|χ_{H}

and hence on multplying

∑_{y∈H−A} ∑_{z∈H−B} χ_{(A+y)∩(B+z)} ≥ |A||B|χ_{H}.

Taking L^{1} norms of both sides and then using the pigeonhole principle, we can thus find y, z such that

|(A + y) ∩ (B + z)| ≥ \frac{|A||B||H|}{|H − A||H − B|}.

Now the claim follows since

((A + y) ∩ (B + z)) − ((A + y) ∩ (B + z)) ⊆ (A − A) ∩ (B − B).

Now we prove a “Hardy-Littlewood maximal inequality” for k-covering sets.

Theorem 2.7 (Hardy-Littlewood maximal inequality). Let k ≥ 1, and let E_{1} ⊂ E_{2} ⊂ … ⊂ E_{N} be any nested sequence of finite non-empty subsets of G, such that each E_{j} is k-covering. For any summable function f ∈ l^{1}(G), define the maximal function

M_{E_{1},... ,E_{N}} f(x) := sup_{1≤n≤N} \frac{1}{|E_{n}|} ∑_{s∈E_{n}} |f(x + s)|.

Then we have the weak-type inequality

|{x ∈ G : M_{E_{1},... ,E_{N}} f(x) ≥ λ}| ≤ k^{2}∥f∥_{l^{1}(G)}/λ

for all λ > 0.

Proof Call a set of the form x + E_{n} heavy if we have

∑_{s∈E_{n}} |f(x + s)| ≥ λ|E_{n}|.

Observe that

{x ∈ G : M_{E_{1},... ,E_{N}} f(x) ≥ λ} = {x ∈ G : x + E_{n} is heavy for some 1 ≤ n ≤ N}.

Now we use a Vitali covering argument to select a disjoint collection F of heavy sets, by performing the following algorithm.

• Step 0. Initialize F to be the empty set, and n to be the integer N.

• Step 1. If there is a heavy set x + E_{n} for some x ∈ G which is disjoint from all the sets in F, add it to F and then repeat Step 1. Otherwise, go to Step 2.

• Step 2. If n = 1, then we stop the algorithm. Otherwise, we replace n by n − 1

and return to Step 1. It is clear that all the sets x + E_{n} that are placed in F by this algorithm are heavy and

disjoint. In particular we have

∑_{x+E_{n}∈F} λ|E_{n}| ≤ ∥f∥_{l^{1}(G)},  (4)

which ensures (since |E_{n}| ≥ 1 for all n) that F is finite, and the algorithm thus terminates in finite time. Now suppose that x ∈ G is such that Mf(x) ≥ λ. Then there exists 1 ≤ n ≤ N such that x + E_{n} is heavy. By construction, there must exist a heavy set y + E_{m} ∈ F with m ≥ n such that y + E_{m} intersects x + E_{n} (otherwise x + E_{n} itself would have been added to F at some stage, at which point one could take y + E_{m} = x + E_{n}). In particular x ∈ y + E_{m} − E_{n} ⊂ y + E_{m} − E_{m}. Thus we have

{x ∈ G : M_{E_{1},... ,E_{N}} f(x) ≥ λ} ⊂ ⋃_{y+E_{m}∈F} y + E_{m} − E_{m}.

Since E_{m} is k-covering, we have |E_{m} − E_{m}| ≤ k^{2}|E_{m}|, and so

| ⋃_{y+E_{m}∈F} y + E_{m} − E_{m}| ≤ k^{2} ∑_{y+E_{m}∈F} |E_{m}|.

Applying (4), the claim follows.

3. A trilinear maximal function

We now prove (3). The problem is that of multiple scales; for a single scale we have a good bound:

Lemma 3.1. For any fixed length scale L > 0, we have

|{x : T (E, E, E)[x − L, x + L] > λ^{2}}| ≤ Cλ^{−2/3}|E|.

Proof By dividing the integers up into intervals of length 2L, then decomposing E accordingly, one sees that it suffices to verify the claim when E is localized to a single such interval, e.g. [−L, L] (possibly after lowering λ by a factor of 2 or so), thanks to the local nature of the T operator. But then one has the crude bound

|{x : T (E, E, E)[x − L, x + L] > λ^{2}}| ≤ CL

(since the interval [x − L, x + L] has to intersect E), while from Chebyshev’s inequality we have

|\{x : T (E, E, E)[x − L, x + L] > λ^{2}\}| ≤ \frac{1}{λ^{2}} ∑_{x} T (E, E, E)[x − L, x + L]

≤ \frac{1}{λ^{2}L^{2}} |\{(x, y, z) : y, z, y + z − x ∈ E\}|

≤ \frac{|E|^{3}}{λ^{2}L^{2}} .

Combining these two estimates, the result follows.

Now we prove (3). In light of (1), (2), it would suffice to show the “good-lambda” inequality

|{x : T (E, E, E)(x) > λ^{2} and λ ≤ M(E)(x) ≤ λ^{1−ε}}| ≤ Cλ^{−1+ε}|E|.  (5)

Observe that since E is finite, that there are only finitely many I which can be involved in the above set.

To prove (5) we begin with the following observation.

Lemma 3.2. If I is an interval such that T (E, E, E)(I) > λ^{2}/2 and λ ≤ M(E)(x) ≤ λ^{1−ε} then there exists a non-empty set P ⊂ I which is Cλ^{−Cε}-covering and such that

C^{−1}λ^{1+Cε}|I| ≤ |P ∩ E| ≤ max(|E ∩ I|, |P |) ≤ Cλ^{1−Cε}|I|.

Proof By hypothesis, we have

|{(y, z) : y, z, y + z − x_{I} ∈ E ∩ I}| > λ^{2}|I|^{2}/2

and

|E ∩ I| ≤ λ^{1−ε}|I|

and hence by (1)

λ|I| ≤ |E ∩ I| ≤ λ^{1−ε}|I|.  (6)

Thus if we let A := E ∩ I and G ⊂ A × A be the set of those pairs (y, z) for which y + z − x_{I} ∈ A, then

|G| ≥ λ^{2ε}|A|^{2}/2

and

|{y + z : (y, z) ∈ G}| ≤ |A|.

By the Balog-Szemerédi-Gowers theorem (see [2, Proposition 12]) we can thus find a non-empty subset A′ of A such that

|A′| ≥ C^{−1}λ^{Cε}|A|

and

C^{−1}λ^{Cε}|A| ≤ |A′ − A′| ≤ Cλ^{−Cε}|A|

By Lemma 2.3, A′ −A′ is Cλ^{−Cε}-covering. We now set P := A′ −A′ +a for some arbitrary element a in A′, then P is also Cλ^{−Cε}-covering and has cardinality

C^{−1}λ^{Cε}|A| ≤ |P | ≤ Cλ^{−Cε}|A|

and since P contains A′,

|A ∩ P | ≥ |A′| ≥ C^{−1}λ^{Cε}|A|.

The claims then follow from (6).

Now we introduce our key decomposition.

Proposition 3.3 (Atomic decomposition). There exists an integer n ≥ 1 and a sequence of triples

(I_{1}, P_{1}, E_{1}), …, (I_{n−1}, P_{n−1}, E_{n−1}),

wiith the following properties.

• (a) For each 1 ≤ i ≤ n − 1, each I_{i} is an interval which obeys the monotonicity

|I_{1}| ≥ |I_{2}| ≥ … ≥ |I_{n−1}|  (7)

and the total size bound

∑_{i=1}^{n−1} |I_{i}| ≤ Cλ^{−Cε}λ^{−1}|E|.  (8)

• (b) For each 1 ≤ i ≤ n−1, P_{i} is a non-empty subset of I_{i} which is Cλ^{−Cε}-covering and such that

C^{−1}λ^{1+Cε}|I_{i}| ≤ |P_{i} ∩ E_{i−1}| ≤ max(|E_{i−1} ∩ I_{i}|, |P_{i}|) ≤ Cλ^{1−Cε}|I_{i}|.  (9)

• (c) For each 1 ≤ i ≤ n − 1, we have

E_{i} := E\ ⋃_{1≤j≤i} P_{j}.  (10)

In other words, with the convention that E_{0} := E, we have E_{i} = E_{i−1}\P_{i} for all 1 ≤ i ≤ n − 1.

• (d) For all intervals I, we have T (E_{n−1}, E_{n−1}, E_{n−1})(I) < λ^{2}/2. More generally, we have

T (E_{i}, E_{i}, E_{i})(I) < λ^{2}/2 whenever |I| > |I_{i+1}|  (11)

(with the convention that |I_{n}| = 0).

Proof

We construct the triples (I_{i}, P_{i}, E_{i}) by performing the following algorithm. • (Step 0) Initialize n to equal 1.

• (Step 1) Locate an interval I_{n} such that T (E_{n−1}, E_{n−1}, E_{n−1})(I_{n}) ≥ λ^{2}/2, and such that the length |I_{n}| of the interval is maximal with respect to this property. (Note that since E is finite, that there are only finitely many intervals I_{n} for which T (E_{n−1}, E_{n−1}, E_{n−1})(I_{n}) ≥ λ^{2}/2). If no such interval can be found, then we terminate the algorithm. Otherwise, we move on to Step 2.

• (Step 2) Using Lemma 3.2, find a non-empty set P_{n} ⊂ I_{n} which is Cλ^{−Cε}-covering and such that

C^{−1}λ^{1+Cε}|I_{n}| ≤ |P_{n} ∩ E_{n−1}| ≤ max(|E_{n−1} ∩ I_{n}|, |P_{n}|) ≤ Cλ^{1−Cε}|I_{n}|.  (12)

• (Step 3) We set E_{n} := E_{n−1}\P_{n}, and then return to Step 1.

It is clear that this algorithm will ensure the properties (10), (9), (11). Since P_{n} ∩ E_{n−1} is non-empty by construction, we see that E_{n} is strictly smaller than E_{n−1}; since E is finite, we thus see that this algorithm terminates in finite time.

Since the quantities T (E_{i}, E_{i}, E_{i})(I) are monotone decreasing in i, it is easy to verify the nesting property (7) also. To prove (8), we observe from construction that the sets P_{i} ∩ E_{i−1} are disjoint subsets of E, thus

∑_{i=1}^{n−1} |P_{i} ∩ E_{i−1}| ≤ E,

and the claim then follows from (12).

We return to the proof of (5). Since P_{i} is Cλ^{−Cε}-covering, we see from (9) that

|2P_{i} − P_{i}| ≤ Cλ^{−Cε}|P_{i}| ≤ Cλ^{−Cε}λ|I_{i}|,

and thus from (8) we have

∥ ∑_{i=1}^{n−1} χ_{2P_{i}−P_{i}}∥_{L^{1}} ≤ Cλ^{−Cε}|E|,

and so by the Hardy-Littlewood maximal inequality we have

|{x : M(∑_{i=1}^{n−1} χ_{2P_{i}−P_{i}})(x) > λ^{1−Cε}} ≤ Cλ^{1+ε}|E|

for C chosen suitably large. Thus we may exclude this set from (5). In other words, if we define a bad interval to be any I such that

T (E, E, E)(I) > λ^{2}; λ ≤ M(E)(x_{I}) ≤ λ^{1−ε}; M(∑_{i=1}^{n−1} χ_{2P_{i}−P_{i}})(x_{I}) ≤ λ^{1−Cε}

then it suffices to show that

|{x_{I} : I is a bad interval }| ≤ Cλ^{1+ε}|E|.

Now let I be a bad interval. Let 1 ≤ i_{0} ≤ n − 1 be the least integer such that

T (E_{i_{0}}, E_{i_{0}}, E_{i_{0}})(I) ≥ λ^{2}/2;

from (11) we see that such an integer exists, and |I| ≤ |I_{i_{0}+1}|. By telescoping series we thus have

∑_{i=1}^{i_{0}} T (E_{i−1}, E_{i−1}, E_{i−1})(I) − T (E_{i}, E_{i}, E_{i})(I) ≥ λ^{2}/2.

We may clearly restrict the sum to those i for which P_{i} ∩ I is non-empty, since the summands vanish otherwise. On the other hand, P_{i} is contained in an interval I_{i} which is larger than I, hence if P_{i} intersects I then P_{i} and I are both contained in the interval 2I_{i} − I_{i}. Applying Lemma 2.6 we see that

|(P_{i} − P_{i}) ∩ (I − I)| ≥ C^{−1} \frac{|P_{i}||I|}{|I_{i}|},

hence by (9)

|(P_{i} − P_{i}) ∩ (I − I)| ≥ C^{−1}λ^{1+Cε}|I|.  (13)

Since P_{i} intersects I, we have

|(P_{i} − P_{i}) ∩ (I − I)| ≤ |(2P_{i} − P_{i}) ∩ (2I − I)|

and hence

M(χ_{2P_{i}−P_{i}})(2I − I) ≥ C^{−1}λ^{1+Cε}.

On the other hand, since I is a bad interval, we have

∑_{i=1}^{n−1} M(χ_{2P_{i}−P_{i}})(2I − I) ≤ Cλ^{1−Cε}

and hence there are at most Cλ^{−Cε} values of i for which P_{i} ∩ I is non-empty. By the pigeonhole principle, we may therefore find 1 ≤ i ≤ i_{0} such that

T (E_{i−1}, E_{i−1}, E_{i−1})(I) − T (E_{i}, E_{i}, E_{i})(I) ≥ C^{−1}λ^{2+Cε}.

By (8), it thus suffices to show that

|{x_{I} : I is a bad interval and T (E_{i−1}, E_{i−1}, E_{i−1})(I)−T (E_{i}, E_{i}, E_{i})(I) ≥ C^{−1}λ^{2+Cε}}| ≤ Cλ^{C_{0}ε}|I_{i}|

for some large absolute constant C_{0}. Note that the trivial bound here is C|I_{i}| since x_{I} must lie in 2I_{i} − I_{i}. We can discard those intervals I for which |I| ≥ C^{−1}λ^{1/100}|I_{i}| since those intervals can be dealt with by Lemma 3.1 (actually we can discard many more intervals than this using dyadic decomposition).

We crudely estimate

T (E_{i−1}, E_{i−1}, E_{i−1})(I) − T (E_{i}, E_{i}, E_{i})(I) ≤ T (E_{i} ∩ P_{i}, E_{i}, E_{i})(I)
+ T (E_{i}, E_{i} ∩ P_{i}, E_{i})(I)
+ T (E_{i}, E_{i}, E_{i} ∩ P_{i})(I)

so at least one of these three terms has to be at least C^{−1}λ^{2+Cε}. Let us say it is the first term; the others are similar. Thus we need to show

|{x_{I} : I is a bad interval and |I| ≤ C^{−1}λ^{1/100}|I_{i}| and T (E_{i} ∩ P_{i}, E_{i}, E_{i})(I) ≥ C^{−1}λ^{2+Cε}}| ≤ Cλ^{C_{0}ε}|I_{i}|. (14)

Let I_{min} be the interval of minimal length which contributes to the above set (which we can of course assume is non-empty). Since I_{min} is a bad interval, we know that

\begin{aligned}|(P_{i} − P_{i}) ∩ (I_{min} − I_{min})| & ≤ |(2P_{i} − P_{i}) ∩ |2I_{min} − I_{min}| \\ & = |2I_{min} − I_{min}|M(χ_{2P_{i}−P_{i}})(2I_{min} − I_{min}) \\ & ≤ Cλ^{1−Cε}|I_{min}|. \end{aligned}  (15)

This implies a certain “even spacing” property for P_{i} − P_{i}.

Lemma 3.4. There exists a set X_{i} of integers with cardinality

|X_{i}| ≤ Cλ^{−Cε}  (16)

such that for any integer x with |x| ≤ C^{−1}λ^{1/100}|I_{i}|, there exists a y ∈ X_{i} such that

|[x − y − 2|I_{min}|, x − y + 2|I_{min}|] ∩ (P_{i} − P_{i})| ≥ C^{−1}λ^{1+Cε}|I_{min}|.

Proof From (9) we have

|P_{i} ∩ I_{i}| ≥ C^{−1}λ^{1+Cε}|I_{i}|

and hence

|{(x, t) : x ∈ 2I_{i} − I_{i}; |t| ≤ |I_{min}|/2; x + t ∈ P_{i} ∩ I_{i}}| ≥ C^{−1}λ^{1+Cε}|I_{i}||I_{min}|.

On the other hand, from (15) we have for any integer x ∈ 2I_{i} − I_{i} that

|{t : |t| ≤ |I_{min}|/2; x + t ∈ P_{i} ∩ I_{i}}| ≤ |(P_{i} − P_{i}) ∩ (I_{min} − I_{min})| ≤ Cλ^{1−Cε}|I_{min}|,

hence there must exist a subset A ⊂ 2I_{i} − I_{i} with |A| ≥ Cλ^{Cε}|I_{i}| such that

|{t : |t| ≤ |I_{min}|/2; x + t ∈ P_{i} ∩ I_{i}}| ≥ C^{−1}λ^{1+Cε}|I_{min}| for all x ∈ A.

Now, consider a maximal disjoint collection of translates y + A of A, where |y| ≤ C^{−1}λ^{1/100}|I_{i}|; let X_{i} denote the set of such x’s. Since all these sets lie inside 3I_{i} − 2I_{i} (say), we have |X_{i}||A| ≤ |3I_{i} − 2I_{i}|, which implies (16). On the other hand, for any |x| ≤ C^{−1}λ^{1/100}|I_{i}|, there must exist y ∈ X_{i} such that x + A intersects y + A (otherwise this would contradict the maximality of A). Thus there exists a, a′ ∈ A such that x = y+a−a′. But then there exists |t| ≤ |I_{min}|/2 such that a+t ∈ P_{i}∩I_{i}, and there exists at least C^{−1}λ^{1+Cε}|I_{min}| values of t′ such that a′ +t′ ∈ P_{i} ∩I_{i}. Observe that (a+t)−(a+t′) lies in [x − y − 2|I_{min}|, x + y + 2|I_{min}|] and also in P_{i} − P_{i}, and the claim follows.

For each N ≥ 1, let B_{N} := (4P_{i} − 4P_{i}) ∩ [−N, N], and introduce the maximal function

m_{i}(z) := sup_{N} \frac{|E_{i} ∩ (2I_{i} − I_{i}) ∩ B_{N}|}{|B_{N}|}.

From Lemma 2.6 we know that each B_{N} is Cλ^{−Cε}-covering, hence by Theorem 2.7 we have

|\{z : m_{i}(z) > α\}| ≤ Cλ^{−Cε} \frac{|E_{i} ∩ (2I_{i} − I_{i})|}{α} for all α > 0.

Since 2I_{i} − I_{i} contains the one bad interval I, and M(E)(x_{I}) ≤ Cλ^{1−Cε}, we thus have

|E_{i} ∩ (2I_{i} − I_{i})| ≤ Cλ^{1−Cε}|I_{i}|.

Thus if let A ≫ 1 be a large absolute constant to be chosen later, and set

Ω := {z : m_{i}(z) > λ^{Aε}}

then

|Ω| ≤ Cλ^{1−(A+C)ε}|I_{i}|.  (17)

One can think of Ω as a slight thickening of E_{i} ∩ I_{i}. We enlarge it further by defining

Ω̃ := Ω ∪ (Ω − X_{i}) ∪ (Ω − 2X_{i})

and observe from (17), (16) that

|Ω̃| ≤ Cλ^{1−(A+C)ε}|I_{i}|.  (18)

Now we claim

Lemma 3.5. If I contributes to the set (14), and A is a large enough absolute constant, then

T (Ω̃, Ω̃, Ω̃)([x_{I} − 5|I_{min}|, x_{I} + 5|I_{min}|]) ≥ Cλ^{2+Cε}.  (19)

10 CIPRIAN DEMETER, TERENCE TAO, AND CHRISTOPH THIELE

The point is that the interval I has been replaced by an interval of a fixed size, so that Lemma 3.1 is now applicable. Proof Since T (E_{i} ∩ P_{i}, E_{i}, E_{i})(I) ≥ C^{−1}λ^{2+Cε}, we have

|{(y, z) : y ∈ E_{i} ∩ P_{i} ∩ I; z, y + z − x_{I} ∈ E_{i} ∩ I}| ≥ C^{−1}λ^{2+Cε}|I|^{2}.

Also, since I is bad, we know that

|E_{i} ∩ I| = |I|M(E_{i})(I) ≤ Cλ^{1−Cε}|I|

and thus

|E_{i} ∩ P_{i} ∩ I| ≥ C^{−1}λ^{1+Cε}|I|,

while since I is bad we also know that

|P_{i} ∩ I| ≤ |(P_{i} − P_{i}) ∩ (I − I)| ≤ C|I|M(2P_{i} − P_{i})(2I − I) ≤ Cλ^{1−Cε}|I|. To summarize, we have

C^{−1}λ^{1+Cε}|I| ≤ |E_{i} ∩ P_{i} ∩ I|, |E_{i} ∩ I|, |P_{i} ∩ I|, |(P_{i} − P_{i}) ∩ (I − I)| ≤ Cλ^{1−Cε}|I| (20)

Observe that every y ∈ P_{i} ∩ I has at least |P_{i} ∩ I| representations of the form y = y′ − t, where y′ ∈ P_{i} ∩ I and t ∈ (P_{i} − P_{i}) ∩ (I − I). Thus |{(y′, t, z) : y′ ∈ P_{i} ∩ I; t ∈ (P_{i} − P_{i}) ∩ (I − I); z, y′ − t + z − x_{I} ∈ E_{i} ∩ I} ≥ C^{−1}λ^{3+Cε}|I|^{3}. Now substitute z′ := z − t to obtain |{(y′, t, z′) : y′ ∈ P_{i} ∩ I; t ∈ (P_{i} − P_{i}) ∩ (I − I); z′ + t, z′ + y′ − x_{I} ∈ E_{i} ∩ I} ≥ C^{−1}λ^{3+Cε}|I|^{3}. We can rewrite this as

∑_{z′} f(z′)g(z′) ≥ C^{−1}λ^{3+Cε}|I|^{3}

where f(z′) := |{y′ ∈ P_{i}∩I : z′+y′−x_{I} ∈ E_{i}∩I}|; g(z′) := |{t ∈ (P_{i}−P_{i})∩(I−I) : z′+t ∈ E_{i}∩I}|. Now observe from (20) that

∑_{z′} f(z′) = |P_{i} ∩ I||E_{i} ∩ I| ≤ Cλ^{2−Cε}|I|^{2}

and

∑_{z′} g(z′) = |(P_{i} − P_{i}) ∩ (I − I)||E_{i} ∩ I| ≤ Cλ^{2−Cε}|I|^{2}

and also

f(z′), g(z′) ≤ |E_{i} ∩ I| ≤ Cλ^{1−Cε}|I| for all z′.

Combining all these bounds for f, g together, we see that there must exist z_{0} such that

f(z_{0}), g(z_{0}) ≥ C^{−1}λ^{1+Cε}|I|.

Let y_{0} be an arbitrary element of P_{i}∩I. Writing y′ = y_{0}+t for some t ∈ (P_{i}−P_{i})∩(I−I), we thus see that

\begin{matrix}|\{t ∈ (P_{i} − P_{i}) ∩ (I − I) : z_{0} + y_{0} − x_{I} + t ∈ E_{i} ∩ I\}|, \\ |\{t ∈ (P_{i} − P_{i}) ∩ (I − I) : z_{0} + t ∈ E_{i} ∩ I\}| & ≥ C^{−1}λ^{1+Cε}|I|. \end{matrix}  (21)

By Lemma (3.4), there exists integers a, b ∈ X_{i} such that

|[y_{0} − x_{I} − a − 2|I_{min}|, y_{0} − x_{I} − a + 2|I_{min}|] ∩ (P_{i} − P_{i})| ≥ C^{−1}λ^{1+Cε}|I_{min}| (22)

and

|[z_{0} − x_{I} − b − 2|I_{min}|, z_{0} − x_{I} − b + 2|I_{min}|] ∩ (P_{i} − P_{i})| ≥ C^{−1}λ^{1+Cε}|I_{min}| (23)

Now fix a, b and suppose that

c ∈ [y_{0} − x_{I} − a − 2|I_{min}|, y_{0} − x_{I} − a + 2|I_{min}|] ∩ (P_{i} − P_{i})

and

d ∈ [z_{0} − x_{I} − b − 2|I_{min}|, z_{0} − x_{I} − b + 2|I_{min}|] ∩ (P_{i} − P_{i}).

Then

y_{0} − a − c, z_{0} − b − d ∈ [x_{I} − 2|I_{min}|, x_{I} + 2|I_{min}|]

and thus

(y_{0} − a − c) + (z_{0} − b − d) − x_{I} ∈ [x_{I} − 4|I_{min}|, x_{I} + 4|I_{min}|].

Also, since

((y_{0} − c) + B_{5|I|}) ⊇ y_{0} + ((P_{i} − P_{i}) ∩ (I − I)) ⊇ P_{i} ∩ I

we have

m(y_{0} − c) ≥ Cλ^{−Cε}

and hence y_{0} ∈ Ω + X_{i} ⊆ Ω̃ (if A is large enough). Similarly, since

(z_{0} − d) + B_{5|I|} ⊇ z_{0} + ((P_{i} − P_{i}) ∩ (I − I))

we see from (21) that

m(z_{0} − d) ≥ Cλ^{−Cε}

and hence z_{0} ∈ Ω + X_{i} ⊆ Ω̃. Finally, since

(y_{0} − c) + (z_{0} − d) − x_{i} + B_{5|I|} ⊇ (z_{0} + y_{0} − x_{I}) + ((P_{i} − P_{i}) ∩ (I − I)) we see from (21) that

m(z_{0} + y_{0} − x_{I} − c − d) ≥ Cλ^{−Cε}

and hence z_{0} + y_{0} − x_{I} ∈ Ω + 2X_{i} ⊆ Ω̃. The claim (19) now follows from (22), (23).

From (17), (16), and Lemma 3.1 we have

|{x_{I} : T (Ω̃, Ω̃, Ω̃)([x_{I} − 5|I_{min}|, x_{I} + 5|I_{min}|]) ≥ Cλ^{2+Cε}}| ≤ Cλ^{1/3−(A+C)ε}|I_{i}| and (16) then follows from Lemma 3.5 if ε is sufficiently small depending on A.

References

[1] A. Balog, E. Szemerédi, A statistical theorem of set addition, Combinatorica, 14 (1994), 263–268.

[2] T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, GAFA 8 (1998), 529–551.

[3] B. Green, I. Ruzsa, Sets with small sumsets and rectification, preprint. math.NT/0403338

[4] I. Ruzsa, An analog of Freiman’s theorem in groups, Structure theory of set addition, Astérisque No. 258 (1999), 323–326.

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

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

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

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

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

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