NON-COMMUTATIVE SUM SET ESTIMATES

TERENCE TAO

Abstract. We give non-commutative analogues of some basic sum set estimates (inspired by some discussion at a recent AIM workshop)

1. Introduction

Let G be a non-abelian multiplicative group (with identity 1), and let A, B be finite non-empty subsets of G. We are interested in studying the cardinalities of the product set

A · B := {ab : a ∈ A, b ∈ B}

and the quotient set

A · B^{−1} := {ab^{−1} : a ∈ A, b ∈ B}

thus obtaining non-commutative generalizations of various sum set estimates. If x ∈ G, we write x · A as shorthand for {x} · A, and similarly for A · x. Note that in general A · B ≠ B · A and x · A ≠ A · x, but A, A · x, and x · A all have the same cardinality. We write A^{2} for A · A, A^{3} for A · A · A, etc.

It is convenient to introduce the Ruzsa distance

d(A, B) := log \frac{|A · B^{−1}|}{|A|^{1/2}|B|^{1/2}}

between two finite non-empty subsets A, B of G. One could also define the dual Ruzsa distance

d^{∗}(A, B) := log \frac{|A^{−1} · B|}{|A|^{1/2}|B|^{1/2}} = d(A^{−1}, B^{−1})

but clearly the theory of the two metrics are analogous after using the inverse map x ↦ x^{−1} to identify G with its reversal G^{op}.

Lemma 1.1 (Ruzsa triangle inequality). For any non-empty finite subsets A, B, C of G, we have the positivity property d(A, B) ≥ 0, the symmetry property d(A, B) = d(B, A), and the triangle inequality d(A, C) ≤ d(A, B) + d(B, C). Finally, we have the right-invariance property d(A·z, B·z) = d(A, B) and the left-invariance property d(x · A, y · B) = d(A, B) for all x, y, z ∈ G.

Proof If b ∈ B, then |A · B^{−1}| ≥ |A · b^{−1}| = |A|, and similarly |A · B^{−1}| ≥ |B|. In particular

|A · B^{−1}| ≥ max(|A|, |B|) ≥ |A|^{1/2}|B|^{1/2}

which gives the positivity property d(A, B) ≥ 0. From the identity (ab^{−1})^{−1} = (ba^{−1})^{−1} we see that (A · B^{−1}) = (B · A^{−1})^{−1} and hence we have the symmetry property d(A, B) = d(B, A). Finally, from the identity (ab^{−1})(bc^{−1}) = (ac^{−1}) we see that every element of A·C^{−1} has at least |B| representations in (A·B^{−1})·(B·C^{−1}) and hence

|A · C^{−1}||B| ≤ |A · B^{−1}||B · C^{−1}|

which gives the triangle inequality d(A, C) ≤ d(A, B) + d(B, C). The invariance properties are clear from inspection.

The Ruzsa distance is thus very close to being a metric in the usual sense of metric spaces, unfortunately d(A, A) is often non-zero. Indeed, we have

Lemma 1.2. Suppose A, B are non-empty finite subsets of G. Then the following are equivalent.

• We have d(A, B) = 0.

• A and B are left-cosets of a finite subgroup H of G, i.e. we have A = x · H and B = y · H.

Proof It is clear that the latter implies the former, so suppose that the former holds. By left invariance we may assume A, B contain the identity element 1. Then A·B contains both A and B, so if d(A, B) = 0 then we must have A·B = A = B, and thus A is closed under multiplication. Being finite, we thus see (by the pigeonhole principle) that every element of A has finite order and hence a^{−1} is a positive power of a for each a ∈ A. Thus A is also closed under inversion and is a subgroup, as claimed.

Some applications of the Ruzsa triangle inequality:

Corollary 1.3. Let A, be a finite non-empty subset of G, and let K ≥ 1.

• If |A · A| ≤ K|A| and B := A ∪ A^{−1}, then |B · B| ≤ (2K^{2} + 2K)|B|. (It is probable that one can improve this bound slightly). Thus a set with small doubling is contained inside a symmetric set B = B^{−1} of reasonably small doubling.

• If A = A^{−1} and K_{m} := |A^{m}|/|A|, then K_{m+n−2} ≤ K_{m}K_{n} for all m, n ≥ 2.

• If |A^{3}| ≤ K|A|, then |A^{m}| ≤ C_{m}K^{C_{m}}|A| for all m.

Proof If |A·A| ≤ K|A|, then d(A, A^{−1}) ≤ log K. By the Ruzsa triangle inequality, this means that d(A, A), d(A^{−1}, A^{−1}) ≤ 2 log K, and thus

|A · A|, |A^{−1} · A^{−1}| ≤ K|A|; |A · A^{−1}|, |A^{−1} · A| ≤ K^{2}|A|,

and the first claim follows. For the second claim, we expand the Ruzsa triangle inequality

d(A^{m−1}, A^{n−1}) ≤ d(A^{m−1}, A) + d(A, A^{n−1})

using the symmetry assumption A = A^{−1} to conclude that K_{m+n−2} ≤ K_{m}K_{n} as claimed.

Now we prove the third claim. Write B := A ∪ A^{−1}, then by the second claim it will suffice to show that |B^{3}| ≤ CK^{C}|A|. But since |A| ≤ |A^{2}| ≤ |A^{3}| ≤ K|A| we have d(A, A^{−1}) ≤ log K and d(A^{2}, A^{−1}) ≤ log K, so in particular d(A^{2}, A) ≤ 2 log K, thus |A · A · A^{−1}| ≤ K^{2}|A|. But this forces d(A, A · A^{−1}) ≤ 2 log K which implies d(A^{−1}, A · A^{−1}) ≤ 3 log K, thus |A^{−1} · A · A^{−1}| ≤ K^{3}|A|. But this forces d(A^{−1} ·A, A) ≤ 3 log K which implies d(A^{−1} ·A, A^{−1}) ≤ 4 log K, thus |A^{−1} ·A·A| ≤ K^{4}|A|, and thus d(A^{−1}, A^{−2}) ≤ 4 log K. From all of these inequalities we see that A, A^{−1}, A^{2}, A · A^{−1}, A^{−1} · A, A^{−2} are all within O(log K) of each other in the Ruzsa metric, and hence we have |B^{3}| ≤ CK^{C}|A| as claimed.

These two facts are not quite as strong as the sum set theory, in which sets with small doubling are automatically known to have small tripling or indeed stay small under repeated addition or subtraction. Indeed, such a claim is false (as was pointed out to the author independently by Ben Green and Mei-Chu Chang). Indeed, consider a set of the form A = H∪{x} where H is a finite subgroup of G and x ∉ H, then A^{2} = H ∪x·H ∪H ·x∪{x^{2}}, so in particular |A^{2}| ≤ 3|H|+1 = 3|A|−2. On the other hand, A^{3} contains H · x · H, which can be significantly larger than |H| if x lies outside the normalizer of H (indeed, one can easily construct an example in the free non-abelian group generated by H and x in which this set is as large as |H|^{2} = (|A| − 1)^{2}). This shows also that one cannot expect the Plünnecke inequalities for sum sets to hold in the non-commutative setting.

However, it is still possible for a subset of a set with small doubling to have small tripling (and hence have all other multiples under control, thanks to the preceding corollary). We begin with a non-commutative vesion of the standard Balog-Szemerédi-Gowers lemma.

Lemma 1.4 (Non-commutative Balog-Szemerédi-Gowers lemma). Let A, B, P be finite non-empty subsets of G with |A|, |B|, |P | ≤ N, and suppose that P contains many products in A · B, or more precisely that

|{(a, b) ∈ A × B : ab ∈ P }| ≥ K^{−1}N^{2}.

(Note that such a P necessarily exists if |A·B| ≤ KN from the pigeonhole principle, but the hypothesis is in fact stronger than this). Then there exists non-empty subsets A_{1} ⊆ A, B_{1} ⊆ B with |A_{1}|, |B_{1}| ≥ C^{−1}K^{−C}N such that each x ∈ A_{1} · B_{1} has at least C^{−1}K^{−C}N^{5} representations of the form

x = (a_{1}b_{1})(a_{2}b_{2})^{−1}(a_{3}b_{3})

where a_{1}, a_{2}, a_{3} ∈ A and b_{1}, b_{2}, b_{3} ∈ B. In particular, this implies that |A_{1} · B_{1}| ≤ CK^{C}N.

Proof Let P′ ⊂ P be the products p in P which are popular in the sense that

|\{(a, b) ∈ A × B : ab = p\}| ≥ \frac{N}{2K} .

Using the hypotheses on A, B, P we conclude that |P′| ≥ N/2K.

For every a ∈ A we set B_{a} := {b ∈ B : ab ∈ P′}, then

∑_{a∈A} |B_{a}| = ∑_{p∈P′} |\{(a, b) ∈ A × B : ab = p\}| ≥ \frac{N}{2K} |P′| ≥ \frac{N^{2}}{4K^{2}} .

Thus if we set

A′ := \{a ∈ A : |B_{a}| ≥ \frac{N}{8K^{2}} \}

then

∑_{a∈A′} |B_{a}| ≥ \frac{N^{2}}{8K^{2}} .

Now for each b ∈ B, let A′_{b} := {a ∈ A′ : ab ∈ P′} ⊆ A′, then

∑_{b∈B} |A′_{b}| = ∑_{a∈A′} |B_{a}| ≥ \frac{N^{2}}{8K^{2}} .

4 TERENCE TAO

By Cauchy-Schwarz we thus have

∑_{b∈B} |A′_{b}|^{2} ≥ \frac{N^{3}}{64K^{4}} .  (1)

Call a pair (a, a′) ∈ A′ × A′ unacquainted if

|\{b ∈ B : \{a, a′\} ⊂ A′_{b}\}| ≤ \frac{N}{2^{20}K^{10}} .

Then clearly

∑_{(a,a′) unacquainted} |\{b ∈ B : \{a, a′\} ⊂ A′_{b}\}| ≤ \frac{N^{3}}{2^{20}K^{10}} ,

and hence

∑_{b∈B} |\{(a, a′) ∈ A′_{b} × A′_{b} : (a, a′) unacquainted\}| ≤ \frac{N^{3}}{2^{20}K^{10}} .

Comparing this with (1) we see that

∑_{b∈B} |A′_{b}|^{2} − \frac{N^{2}}{128K^{4}} − 2^{14}K^{6}|\{(a, a′) ∈ A′_{b} × A′_{b} : (a, a′) unacquainted\}| ≥ 0

and thus there exists b ∈ B such that

|A′_{b}|^{2} − \frac{N^{2}}{128K^{4}} − 2^{14}K^{6}|\{(a, a′) ∈ A′_{b} × A′_{b} : (a, a′) unacquainted\}| ≥ 0.

Fix this b; thus

\frac{N}{2^{7/2}K^{2}} ≤ |A′_{b}| ≤ N

and

|{(a, a′) ∈ A′_{b} × A′_{b} : (a, a′) unacquainted}| ≤ 2^{−14}K^{−6}|A′_{b}|^{2}.

Thus if we define

A_{1} := {a ∈ A′_{b} : |{a′ ∈ A′_{b} : (a, a′) unacquainted}| ≥ 2^{−15}K^{−6}|A′_{b}|} then by Chebyshev’s inequality

|A_{1}| ≥ \frac{1}{2}|A′_{b}| ≥ \frac{N}{2^{9/2}K^{2}} .

By definition of A′, we have

|B_{a}| ≥ \frac{N}{8K^{2}} for all a ∈ A′_{b}

and hence

∑_{a∈A′_{b}} |B_{a}| ≥ \frac{N}{8K^{2}} |A′_{b}| ≥ \frac{N^{2}}{2^{13/2}K^{4}} .

Rearranging this, we obtain

∑_{b∈B} |\{a ∈ A′_{b} : ab ∈ P′\}| ≥ \frac{N^{2}}{2^{13/2}K^{4}} .

Thus if we define

B_{1} := \{b ∈ B : |\{a ∈ A′_{b} : ab ∈ P′\}| ≥ \frac{N}{2^{15/2}K^{4}} \}

then

|B_{1}| ≥ \frac{N}{2^{15/2}K^{4}} .

Now let a ∈ A_{1} and b ∈ B_{1}. By definition of B_{1}, there exists at least \frac{N}{2^{15/2}K^{4}} values of a′ ∈ A′_{b} such that a′b ∈ P′. Of these, at most 2^{−15}K^{−6}N of these are unacquainted with a, thus there are at least 2^{−8}K^{−4}N a′ ∈ A′_{b} such that a′b ∈ P′ and a′ is acquainted with a. But note that if a′ is acquainted with a then there exist at least 2^{−10}K^{−10}N values of b′ ∈ B such that ab′, a′b′ ∈ P′. Thus we have

|{(a′, b′) ∈ A × B : a′b, ab′, a′b′ ∈ P′}| ≥ 2^{−18}K^{−14}N^{2}.

Since ab = (ab′)(a′b′)^{−1}(a′b), and since a′ and b′ can be reconstructed uniquely from a, b, a′b, ab′, we thus have

|{(p_{1}, p_{2}, p_{3}) ∈ P′ × P′ × P′ : ab = p_{1}p_{2}^{−1}p_{3}}| ≥ 2^{−18}K^{−14}N^{2}.

Applying the definition of P′, the claim follows.

We now give a number of applications to this lemma. We first need a symmetry lemma to get around the non-commutativity A · A^{−1} ≠ A^{−1} · A (for instance, if A = x · H for some subgroup H, then A^{−1} · A can be much larger than A · A^{−1}).

Corollary 1.5. If A is a finite non-empty subset of G with |A| = N and |A · A^{−1}| ≤ KN, then there exists a subset A′ ⊆ A with |A′| ≥ C^{−1}K^{−C}N and |A′ · (A′)^{−1}|, |(A′)^{−1} · A′| ≤ CK^{C}N.

Proof The map (a, b^{−1}) ↦ ab^{−1} maps the set A × A^{−1}, which has N^{2} elements, to A · A^{−1}, which has at most KN elements. By Cauchy-Schwarz we thus have

|{(a, b^{−1}, c, d^{−1}) ∈ A × A^{−1} × A × A^{−1} : ab^{−1} = cd^{−1}}| ≥ N^{3}/K.

Now observe that ab^{−1} = cd^{−1} if and only if c^{−1}a = d^{−1}b, thus

|{(a, b^{−1}, c, d^{−1}) ∈ A × A^{−1} × A × A^{−1} : c^{−1}a = d^{−1}b}| ≥ N^{3}/K

which we rewrite as

∑_{q∈G} |{(a, c) ∈ A × A : c^{−1}a = q}|^{2} ≥ N^{3}/K.

If we let Q be the set of all q ∈ G which have at least N/2K representations of the form q = c^{−1}a for a, c ∈ A, we have

∑_{q∉Q} |{(a, c) ∈ A : c^{−1}a = q}|^{2} ≤ |{(a, c) ∈ A × A}|N/2K = N^{3}/2K

and hence

∑_{q∈Q} |{(a, c) ∈ A × A : c^{−1}a = q}|^{2} ≥ N^{3}/2K.

Since each summand is at most N^{2}, we thus have |Q| ≥ N/2K; we also have |Q| ≤ 2KN since the total number of products of the form c^{−1}a is N^{2}. By definition of Q, we have

∑_{q∈Q} |{(c^{−1}, a) ∈ A^{−1} × A : c^{−1}a = q}| ≥ N^{2}/4K^{2}.

Applying Lemma 1.4, we conclude that there exists A_{1}^{−1} ⊂ A^{−1} and A_{2} ⊂ A such that

|A_{1}|, |A_{2}| ≥ C^{−1}K^{−C}N and |A_{1}^{−1} · A_{2}| ≤ CK^{C}N.

Using the Ruzsa triangle inequality, we conclude in particular that |A_{1}^{−1} · A_{1}| ≤ CK^{C}N. Since |A_{1} · A_{1}^{−1}| ≤ |A · A^{−1}| ≤ KN, the claim now follows by taking A′ := A_{1} (one could also take A′ := A_{2}, of course).

We now give a more general corollary in the same spirit:

Corollary 1.6. If A, B are finite non-empty subsets of G with |A|, |B| ≥ N and |A · B| ≤ KN, then there exists subsets A′ ⊂ A and B′ ⊂ B with |A′|, |B′| ≥ C^{−1}K^{−C}N and |A′ · B′ · (B′)^{−1} · (A′)^{−1}| ≤ CK^{C}N.

Proof By removing some elements of A, B if necessary we may take |A| = |B| = N. From the Ruzsa triangle inequality we have |B^{−1} · B| ≤ K^{2}N, so by the preceding Corollary we can find a subset B_{1} ⊂ B with |B_{1}| ≥ C^{−1}K^{−C}N and |B_{1}^{−1} · B_{1}|, |B_{1} · B_{1}^{−1}| ≤ CK^{C}N. Applying Lemma 1.4, we can then find subsets B_{2}, B_{3} of B_{1} such that |B_{2}|, |B_{3}| ≥ C^{−1}K^{−C}N and every element y in B_{2} · B_{3}^{−1} has at least C^{−1}K^{−C}N^{5} representations of the form y = b_{1}b_{2}^{−1}b_{3}b_{4}^{−1}b_{5}b_{6}^{−1}, where b_{1}, …, b_{6} ∈ B. Since |A · B_{2}| ≤ |A · B| ≤ KN, we can apply Lemma 1.4 yet again to find subsets A′ ⊂ A and B′ ⊂ B_{2} such that |A′|, |B′| ≥ C^{−1}K^{−C}N and every element x in A′ · B′ has at least C^{−1}K^{−C}N^{5} representations of the form x = a_{1}b_{1}b_{2}^{−1}a_{2}^{−1}a_{3}b_{3} where a_{1}, a_{2}, a_{3} ∈ A and b_{1}, b_{2}, b_{3} ∈ B_{2}. Similarly since |B_{3}^{−1} · A^{−1}| = |A · B_{3}| ≤ |A · B| ≤ KN we can find subsets B′′ ⊂ B_{3} and A′′ ⊂ A such that |B′′|, |A′′| ≥ C^{−1}K^{−C}N and every x′ ∈ (B′′)^{−1} · (A′′)^{−1} has at least C^{−1}K^{−C}N^{5} representations of the form x′ = b_{4}^{−1}a_{4}^{−1}a_{5}b_{5}b_{6}^{−1}a_{6}^{−1} with a_{4}, a_{5}, a_{6} ∈ A and b_{4}, b_{5}, b_{6} ∈ B_{3}.

Combining all these facts together, we see that if x ∈ A′ · B′ and x′ ∈ (B′′)^{−1} · (A′′)^{−1}, then x · x′ has at least C^{−1}K^{−C}N^{10} representations of the form

x · x′ = (a_{1}b_{1}b_{2}^{−1}a_{2}^{−1}a_{3}b_{3})(b_{4}^{−1}a_{4}^{−1}a_{5}b_{5}b_{6}^{−1}a_{6}^{−1})

where a_{1}, …, a_{6} ∈ A, b_{1}, …, b_{3} ∈ B_{2}, b_{4}, …, b_{6} ∈ B_{3}, and the expressions in parentheses equal x and x′ respectively. For each such representation, the expression b_{3}b_{4}^{−1} ∈ B_{2}·B_{3}^{−1} in that representation has at least C^{−1}K^{−C}N^{5} representations of its own of the form

b_{3}b_{4}^{−1} = b_{7}b_{8}^{−1}b_{9}b_{10}^{−1}b_{11}b_{12}^{−1}

where b_{7}, …, b_{12} ∈ B. Thus there are at least C^{−1}K^{−C}N^{15} distinct representations of the form

x · x′ = a_{1}b_{1}b_{2}^{−1}a_{2}^{−1}a_{3}b_{7}b_{8}^{−1}b_{9}b_{10}^{−1}b_{11}b_{12}^{−1}a_{4}^{−1}a_{5}b_{5}b_{6}^{−1}a_{6}^{−1}

where a_{1}, …, a_{6} ∈ A and b_{1}, b_{2}, b_{5}, …, b_{12} ∈ B (note that one can use x and x′ to reconstruct b_{3} and b_{4} uniquely from these 16 variables). Since the 16 variables on the right-hand side can have at most N^{16} different values, we thus see that x · x′ can take at most CK^{C}N different values, thus

|A′ · B′ · (B′′)^{−1} · (A′′)^{−1}| ≤ CK^{C}N.

The claim then follows from Ruzsa’s triangle inequality.

To proceed further we need a covering lemma of Ruzsa.

Lemma 1.7 (Ruzsa covering lemma). Let A, B be finite non-empty subsets of G. Then there exists a set X ⊆ B with cardinality |X| ≤ |A · B|/|A| such that B ⊆ A^{−1} · A · X; thus if |A · B| = O(|A|) then B can be covered by O(1) righttranslates of A^{−1} · A.

By symmetry we also see that there exists a set Y ⊆ A of cardinality |Y | ≤ |A · B|/|B| such that A ⊆ Y · B · B^{−1}. Proof Consider the sets A · b, where b ∈ B; these sets all have cardinality |A| and range inside the set |A · B|, thus at most |A · B|/|A| of these sets can be disjoint. Let {A · b : b ∈ X} be a maximal disjoint family of such sets for some X ⊆ B, thus |X| ≤ |A · B|/|A|. If b ∈ B, then there must exist x ∈ X such that A · b intersects A · x, otherwise one could add b to X and contradict maximality. But then b ∈ A^{−1} · A · x ⊆ A^{−1} · A · X. Since b ∈ B was arbitrary, the claim follows.

We remark that variants of this covering lemma exist, such as the Green-Ruzsa covering lemma and the Chang covering lemma. We can now finally give a satisfactory non-commutative sum set estimate.

Proposition 1.8 (Non-commutative sum set estimate). If A, B are finite nonempty subsets of G with |A|, |B| ≥ N and |A · B| ≤ KN. Then there exists a set H with C^{−1}K^{−C}N ≤ |H| ≤ CK^{C}N and H = H^{−1}, a set X ⊂ H^{2} with |X| ≤ CK^{C} and a set Y ⊂ G with |Y | ≤ CK^{C} such that we have the inclusions

A ⊆ Y · H; B ⊆ H · Y; H · H ⊆ X · H ⊂ H · X^{2}; H · H ⊆ H · X ⊆ X^{2} · H.

Note that this proposition is fairly efficient in the sense that if the conclusion holds, then necessarily |A · B| ≤ CK^{C}N. Also the proposition allows us to control arbitrary powers of H quite efficiently, as well as certain combinations of A, H and B (as long as the Y factors are never placed between two copies of H). The inclusions involving H and X can be viewed as a weak form of the Freiman dimension lemma, which in the setting of a torsion-free abelian group shows that if |A + A| ≤ K|A| then A has Freiman dimension at most K −1. One should compare this Proposition with Lemma 1.2, which roughly speaking corresponds to the K = 1 case. Proof By Corollary 1.6, we can find A′ ⊆ A and B′ ⊆ B with |A′|, |B′| ≥ C^{−1}K^{−C}N such that |A′ · B′ · (B′)^{−1} · (A′)^{−1}| ≤ CK^{C}N, so in particular d(A′ · B′ · (B′)^{−1}, A′) ≤ C + C log K. By Ruzsa’s triangle inequality this implies that d(A′ · B′ · (B′)^{−1}, A′ · B′ · (B′)^{−1}) ≤ C + C log K, thus

|A′ · B′ · (B′)^{−1} · B′ · (B′)^{−1} · (A′)^{−1}| ≤ CK^{C}N

so in particular

|B′ · [(B′)^{−1} · B′ · (B′)^{−1}]| ≤ CK^{C}N.

Applying Ruzsa’s triangle inequality again we obtain

|[B′ · (B′)^{−1} · B′] · [(B′)^{−1} · B′ · (B′)^{−1}]| ≤ CK^{C}N,

so if we set H_{0} := B′ · (B′)^{−1} then C^{−1}K^{−C}N ≤ |H_{0}| ≤ CK^{C}N, we have the symmetry property H_{0} = H_{0}^{−1} and H_{0} has small tripling:

|H_{0}^{3}| ≤ CK^{C}|H_{0}|.

From Corollary 1.3 we thus see that |H_{0}^{5}| ≤ CK^{C}|H_{0}|. Thus if we set H := H_{0}^{2}, then we have C^{−1}K^{−C}N ≤ |H| ≤ CK^{C}N, and we have the symmetry property H = H^{−1}. Also, since |H^{2} · H_{0}| ≤ CK^{C}|H_{0}|, we may apply Lemma 1.7 and cover H^{2} by O(CK^{C}) right-translates of H_{0}^{−1}H_{0} = H, thus there exists X_{1} ⊂ H^{2} with |X_{1}| ≤ CK^{C} such that H^{2} ⊂ H · X_{1}; inverting this we also obtain H^{2} ⊂ X_{1}^{−1} · H. If we set X := X_{1} ∪ X_{1}^{−1} then we thus have X ⊂ H^{2}, |X| ≤ CK^{C} and

H · H ⊆ X · H, H · X

which then implies also that

X · H ⊆ H^{2} · H = H · (H · H) ⊆ H · H · X ⊆ H · X^{2}

and similarly H · X ⊆ X^{2} · H.

Next, we observe that

|A′ · B| ≤ |A · B| ≤ KN

and hence d(A′, B) ≤ C + C log K. On the other hand, we have

|H · B′| ≤ |H · B′ · (B′)^{−1}| = |H · H_{0}| ≤ |H^{2}| ≤ CK^{C} log N

and hence d(H, B′) ≤ C + C log K. By the Ruzsa triangle inequality we thus have d(A, H) ≤ C + C log K. Applying the reflected version of Lemma 1.7, we can thus find a set Y_{0} with cardinality |Y_{0}| ≤ CK^{C} such that

A ⊂ Y_{0} · H · H^{−1} = Y_{0} · H · H ⊆ Y_{0} · X · H.

Since d(A, B^{−1}) ≤ log K, we also have d(B^{−1}, H) ≤ C + C log K, so we may also find a set Y_{1} with cardinality |Y_{1}| ≤ CK^{−C} such that B^{−1} ⊆ Y_{1} · X · H, or in other words B ⊆ H · X · Y_{1}^{−1}. The claim now follows by setting Y := Y_{0} · X ∪ X · Y_{1}^{−1}.

Note that one can also combine this Proposition with the Balog-Szemerédi-Gowers lemma to conclude that if A, B have size N and there are at least K^{−1}N^{3} solutions to the equation ab = a′b′ with a, a′ ∈ A and b, b′ ∈ B, then there exists H, X, Y, Z as above such that A has large intersection with Y · H and B has large intersection with H · Y. We omit the details.

Department of Mathematics, UCLA, Los Angeles, CA 90024

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