THE (GOWERS-)BALOG-SZEMERÉDI THEOREM: AN EXPOSITION

VSEVOLOD F. LEV This is an expository note not intended for publication

Abstract. We briefly discuss here the Balog-Szemerédi theorem, compare its different versions and prove, following Gowers, the strongest one — also due to Gowers.

1. Discussion

For a finite set A of elements of an abelian group and a group element s, by ν_{A}(s) we denote the number of representations of s as a sum of two elements of A:

ν_{A}(s) = #{(a′, a′′) ∈ A × A: s = a′ + a′′}.

We write 2A = {a′ + a′′: a′, a′′ ∈ A}, the set of all elements s with ν_{A}(s) > 0. Our motivation will be clear from the following simple lemma.

Lemma 1. Suppose that |2A| ≤ C|A| with some real C > 0. Then (i) there are at least |A|/2 elements s ∈ 2A with ν_{A}(s) ≥ |A|/(2C); (ii) if W is the set of all pairs (a′, a′′) ∈ A×A with ν_{A}(a′ +a′′) ≥ |A|/(2C), then

|W | ≥ |A|^{2}/(4C) and furthermore there are at most 2C|A| distinct sums of the form a′ + a′′ with (a′, a′′) ∈ W;

(iii) the number of solutions of the equation a_{1} + a_{2} = a_{3} + a_{4} in the variables a_{1}, a_{2}, a_{3}, a_{4} ∈ A is at least |A|^{3}/C.

Proof. Write S := {s ∈ 2A: ν_{A}(s) ≥ |A|/(2C)}. Then

|A|^{2} = ∑_{s∈2A} ν_{A}(s) = ∑_{s∈S} ν_{A}(s) + ∑_{s∈2A\S} ν_{A}(s) ≤ |S||A| + |2A||A|/(2C)

(the sum over s ∈ S contains |S| summands not exceeding |A|, the sum over s ∈ 2A \ S contains at most |2A| summands not exceeding |A|/(2C)). By the assumption we have |2A||A|/(2C) ≤ |A|^{2}/2 implying |S| ≥ |A|/2, as claimed in (i).

To prove (ii) we notice that

|W | = ∑_{s∈S} ν_{A}(s) ≥ |S||A|/(2C) ≥ |A|^{2}/(4C)

and that the number of distinct sums of the form a′ + a′′ with (a′, a′′) ∈ W is

|S| ≤ \frac{1}{|A|/(2C)} ∑_{s∈S} ν_{A}(s) ≤ \frac{1}{|A|/(2C)} ∑_{s∈2A} ν_{A}(s) = 2C|A|.

Finally, (iii) is established once we observe that the number of solutions of the equation in question is

∑_{s∈2A}(ν_{A}(s))^{2} ≥ \frac{1}{|2A|}( ∑_{s∈2A} ν_{A}(s))^{2} = \frac{|A|^{4}}{|2A|} ≥ |A|^{3}/C.

□

The Balog-Szemerédi theorem is an assertion “inverse” to the lemma above. In fact, it is not true that if A satisfies conditions of the sort (i)–(iii) then A has the small doubling property: consider, for instance, sets consisting of an arithmetic progression and a number of “sporadic” elements. Balog and Szemrédi have shown, however, that if (i)–(iii) hold then there is a large subset A_{0} ⊆ A with small doubling.

In the light of the discussion above it is not surprising that the assumptions of the Balog-Szemerédi theorem can be stated in several equivalent forms. More precisely, consider the following three conditions (depending on positive real parameters ε, δ, τ, K, and γ).

C1(ε, δ): there is a set S ⊆ 2A such that |S| ≥ ε|A| and ν_{A}(s) ≥ δ|A| for any

s ∈ S;

C2(τ, K): there is a set W ⊆ A × A such that |W | ≥ τ|A|^{2} and the number

of distinct sums a′ + a′′ with (a′, a′′) ∈ W is at most K|A|;

C3(γ): the number T (A) of solutions of the equation a_{1} + a_{2} = a_{3} + a_{4} in the

variables a_{1}, a_{2}, a_{3}, a_{4} ∈ A satisfies T (A) ≥ γ|A|^{3}.

These conditions are essentially equivalent: we leave it to the reader to verify that C1(ε, δ) implies C2(εδ, 1/δ); furthermore, C2(τ, K) implies C3(τ^{2}/K); and finally, C3(γ) implies C1(γ/2, γ/2). Once equivalence is established we can switch freely between the conditions. In practice we prefer to use C3(γ) which depends on just one parameter, and from now on we adopt T (A) as a standard notation.

It is possible to re-state conditions C1 and C2 so that they will depend on just one parameter, too. It is also possible to consider sumsets of the form A + B := {a + b: a ∈ A, b ∈ B} instead of 2A, and indeed the most general form of the Balog-Szemerédi theorem addresses this situation. We will not discuss this below, however.

The “original” (pre-Gowers) version of the Balog-Szemerédi theorem is as follows.

THE (GOWERS-)BALOG-SZEMERÉDI THEOREM 3

Theorem 1. Let A be a finite non-empty set of elements of an abelian group and suppose that T (A) ≥ γ|A|^{3}, where γ > 0 is a real number. Then there exists a subset A_{0} ⊆ A satisfying |A_{0}| ≥ c|A| and |2A_{0}| ≤ C|A_{0}| with positive constants c and C depending only on γ.

For a nicely presented classical proof of Theorem 1 (with the assumptions in the form C1) we refer the reader to [C04]. The problem with the classical proof is that it is based on the Szemerédi regularity lemma, hence the dependence of c and C on γ arising from this proof is very poor; more precisely tower-like, which in practice means ineffective. In contrast, Gowers was able to find a proof which does not use the regularity lemma and leads to “good” relation between c and C, on the one hand, and γ on the other hand. His result is also somewhat stronger than the original Balog-Szemerédi theorem.

Theorem 2 (Gowers, [G98]). Let A be a finite non-empty set of elements of an abelian group and suppose that T (A) ≥ γ|A|^{3}, where γ > 0 is a real number. Then there exists a subset A_{0} ⊆ A satisfying |A_{0}| ≥ (γ^{2}/40)|A| such that for any a_{1}, a_{2} ∈ A_{0} the number of solutions of the equation

a_{1} − a_{2} = x_{1} + x_{2} + x_{3} + x_{4} − y_{1} − y_{2} − y_{3} − y_{4}

in the variables x_{i}, y_{i} ∈ A (i = 1, …, 4) is at least 2^{−28}γ^{10}|A|^{7}. Consequently, we have |A_{0} − A_{0}| < 2^{28}γ^{−10}|A|.

We note that the “consequently part” of the theorem (to which we will never return again) is almost immediate. There are totally |A|^{8} expressions of the form x_{1}+⋯−y_{4}, and by the first assertion any element of the difference set A_{0}−A_{0} “eats up” at least 2^{−28}γ^{10}|A|^{7} expressions; thus the number of elements of the difference set is at most |A|^{8}/(2^{−28}γ^{10}|A|^{7}).

It is worth pointing out that the conclusion of Theorem 2 deals with the difference set A_{0} − A_{0} rather than the sumset 2A_{0}. However, the cardinalities of the two sets are known to be tightly related; in particular, by a well-known lemma of Ruzsa from |A_{0} − A_{0}| < C|A_{0}| it follows that |2A_{0}| < C^{2}|A_{0}|.

2. Proof of the (Gowers-)Balog-Szemerédi theorem

Suppose that we are given subsets A_{1}, …, A_{n} ⊆ A of cardinality at least δ|A| each, with some δ > 0. It is easily seen then that the average intersection A_{i} ∩ A_{j} has at least δ^{2}|A| elements. The following lemma shows that, indeed, one can select a “large” group of subsets so that “almost all” pairs of selected subsets have intersection of about expected size.

4 VSEVOLOD F. LEV

Lemma 2. Let A be a finite non-empty set of cardinality m = |A| and suppose that A_{1}, …, A_{n} ⊆ A satisfy |A_{i}| ≥ δm (i = 1, …, n), where δ > 0 is a real number. Then there is a set of indices I ⊆ [1, n] such that |I| ≥ δn/2 and

#\{(i, j) ∈ I × I: |A_{i} ∩ A_{j}| ≤ 0.03δ^{2}m\} < \frac{1}{25} |I|^{2}.

Remark. There is the usual trade-off between the constants 0.03, 1/25, and δ/2 (in |I| ≥ δn/2); for instance, 0.03 can be replaced by any value, smaller than one. One can obtain slightly better constants modifying the argument as follows: instead of a random element a ∈ A consider a random k-tuple a = (a_{1}, …, a_{k}) ∈ A^{k} and define I_{a} = {i ∈ [1, n]: a_{1}, …, a_{k} ∈ A_{i}}. Indeed, this is the how the argument runs in Gowers’ original proof.

Proof of Lemma 2. For a ∈ A let I_{a} = {i ∈ [1, n]: a ∈ A_{i}}; thus i ∈ I_{a} if and only if a ∈ A_{i}, and

∑_{i,j=1}^{n} |A_{i} ∩ A_{j}| = ∑_{a∈A} |I_{a}|^{2} ≥ \frac{1}{m}( ∑_{a∈A} |I_{a}|)^{2} = \frac{1}{m}( ∑_{i=1}^{n} |A_{i}|)^{2} ≥ δ^{2}mn^{2}

(showing that the average intersection A_{i} ∩ A_{j} has at least δ^{2}m elements).

We prove that one can take I = I_{a} for some a. For this, choose a ∈ A at random. Then

E|I_{a}|^{2} = E #{(i, j): i, j ∈ I_{a}} = E#{(i, j): a ∈ A_{i} ∩ A_{j}}

= ∑_{i,j=1}^{n} P{a ∈ A_{i} ∩ A_{j}} = ∑_{i,j=1}^{n} m^{−1}|A_{i} ∩ A_{j}| ≥ δ^{2}n^{2};

on the other hand,

E#\{(i, j) ∈ I_{a} × I_{a}: |A_{i} ∩ A_{j}| ≤ 0.03δ^{2}m\} = ∑_{\begin{matrix}i,j=1 \\ |A_{i}∩A_{j}|≤0.03δ^{2}m \end{matrix}}^{n} P\{i, j ∈ I_{a}\}

= ∑_{\begin{matrix}i,j=1 \\ m^{−1}|A_{i}∩A_{j}|≤0.03δ^{2} \end{matrix}}^{n} P\{a ∈ A_{i} ∩ A_{j}\} = ∑_{\begin{matrix}i,j=1 \\ m^{−1}|A_{i}∩A_{j}|≤0.03δ^{2} \end{matrix}}^{n} m^{−1}|A_{i} ∩ A_{j}| ≤ 0.03δ^{2}n^{2}.

Therefore,

E\{|I_{a}|^{2} − 25 #\{(i, j) ∈ I_{a} × I_{a}: |A_{i} ∩ A_{j}| ≤ 0.03δ^{2}m\}\} ≥ \frac{1}{4} δ^{2}n^{2},

THE (GOWERS-)BALOG-SZEMERÉDI THEOREM 5

and there exists a ∈ A such that

|I_{a}| ≥ \frac{1}{2} δn,

#\{(i, j) ∈ I_{a} × I_{a}: |A_{i} ∩ A_{j}| ≤ 0.03δ^{2}m\} < \frac{1}{25} |I_{a}|^{2}.

□

To make Lemma 2 easier to apply we restate it in a slightly different form.

Lemma 2′. Let A and B be two finite non-empty sets. Write m := |A| and suppose that to any b ∈ B there corresponds a subset N(b) ⊆ A of cardinality |N(b)| ≥ δm, where δ is a positive real number. Then there exists B′ ⊆ B with |B′| ≥ δ|B|/2 such that

#\{(b′, b′′) ∈ B′ × B′: |N(b′) ∩ N(b′′)| ≤ 0.03δ^{2}m\} < \frac{1}{25} |B′|^{2}.

We need a simple graph-theoretic lemma.

Lemma 3. Let G be a graph (possibly, with loops) on the vertex set V of average degree d̄ ≥ (1 − λ)|V |. Then V contains at least (1 − \sqrt{λ})|V | vertices of degree greater than (1 − \sqrt{λ})|V |:

#\{v ∈ V : deg(v) > (1 − \sqrt{λ})|V |\} ≥ (1 − \sqrt{λ})|V |.

Proof. If k is the number of vertices v ∈ V of degree deg(v) > (1 − \sqrt{λ})|V |, then

d̄|V | = ∑_{v: deg(v)≤(1−\sqrt{λ})|V |} deg(v) + ∑_{v: deg(v)>(1−\sqrt{λ})|V |} deg(v)
≤ (1 − \sqrt{λ})|V |(|V | − k) + |V |k,

whence

(1 − λ)|V | ≤ (1 − \sqrt{λ})(|V | − k) + k = (1 − \sqrt{λ})|V | + \sqrt{λ}k

and therefore

k ≥ (1 − \sqrt{λ})|V |.
□

Combining Lemmas 2′ and 3 we get

Lemma 4. Let A and B be as in Lemma 2′. Then there exist subsets B_{0} ⊆ B′ ⊆ B with |B_{0}| ≥ 4|B′|/5 > 2δ|B|/5 and such that for any b_{0} ∈ B_{0} we have

#\{b′ ∈ B′: |N(b_{0}) ∩ N(b′)| ≥ 0.03δ^{2}m\} > \frac{4}{5} |B′|.

6 VSEVOLOD F. LEV

Proof. Find B′ as in Lemma 2′ and construct a graph on the vertex set {N(b′)}_{b′∈B′}, joining N(b′) and N(b′′) if |N(b′) ∩ N(b′′)| ≥ 0.03δ^{2}m. (The case b′ = b′′ is not excluded so that each N(b′) is joined to itself.) The number of non-loop edges of this graph is more than \binom{|B′|}{2} − \frac{|B′|^{2}}{50} , the average degree is more than 24|B′|/25, and applying Lemma 3 with λ = 1/25 we conclude that there is a set B_{0} of at least 4|B′|/5 elements such that if b_{0} ∈ B_{0}, then N(b_{0}) is adjacent to more than 4|B′|/5 sets N(b′) with b′ ∈ B′. □

Proof of the Gowers-Balog-Szemerédi theorem. Write m := |A|. Let ν_{A}^{−}(d) denote the number of representations of the group element d as d = a_{1}−a_{2} with a_{1}, a_{2} ∈ A. We say that d is a popular difference if ν_{A}^{−}(d) ≥ γm/2, and we let D := {d ∈ A − A: ν_{A}^{−}(d) ≥ γm/2}, the set of all popular differences.

Consider the graph G on the vertex set A, in which a_{1} and a_{2} are adjacent if and only if a_{1} − a_{2} ∈ D (the case a_{1} = a_{2} not excluded). The average degree of G is

d̄= \frac{1}{m} ∑_{a∈A} deg(a)

= \frac{1}{m} ∑_{a∈A} #\{a′ ∈ A: a′ − a ∈ D\}

= \frac{1}{m} #\{(a, a′) ∈ A × A: a′ − a ∈ D\}

= \frac{1}{m} ∑_{d∈D} ν_{A}^{−}(d),

and to estimate the sum at the right we observe that

γm^{3} ≤ T (A) = ∑_{d∈A−A}(ν_{A}^{−}(d))^{2} = ∑_{d∈(A−A)\D}(ν_{A}^{−}(d))^{2} + ∑_{d∈D}(ν_{A}^{−}(d))^{2}

≤ \frac{1}{2} γm ∑_{d∈A−A} ν_{A}^{−}(d) + m ∑_{d∈D} ν_{A}^{−}(d) = \frac{1}{2} γm^{3} + m ∑_{d∈D} ν_{A}^{−}(d).

Therefore ∑_{d∈D} ν_{A}^{−}(d) ≥ γm^{2}/2 whence d̄≥ γm/2 and by Lemma 3 as applied with λ = 1 − γ/2, there is a subset B ⊆ A such that |B| ≥ (1 − \sqrt{1 − γ/2})m > γm/4 and deg(b) > γm/4 for any b ∈ B. Thus if N(b) denotes the neighborhood of b in G (including b itself), then |N(b)| > γm/4 (b ∈ B).

We now apply Lemma 4 to the system of sets N(b) ⊆ A (b ∈ B) with δ = γ/4 to find two subsets A_{0} ⊆ A′ ⊆ B such that

(i) |A′| ≥ (γ/4)|B|/2 ≥ γ^{2}m/32, and |A_{0}| ≥ 4|A′|/5 ≥ γ^{2}m/40;

THE (GOWERS-)BALOG-SZEMERÉDI THEOREM 7

(ii) for any a_{0} ∈ A_{0} we have #{a′ ∈ A′: |N(a_{0}) ∩ N(a′)| ≥ 0.03(γ/4)^{2}m} >

\frac{4}{5} |A′|. We claim that A_{0} possesses the property in question. Indeed, fix a_{1}, a_{2} ∈ A_{0} and

notice that

#\{a′ ∈ A′: |N(a_{i}) ∩ N(a′)| ≥ 0.03(γ/4)^{2}m for i = 1, 2\} > \frac{3}{5} |A′|.

Choose one of these values of a′. For any a ∈ N(a_{1}) ∩ N(a′) both a_{1} − a and a′ − a are popular differences, yielding at least (γm/2)^{2} representations a_{1} − a′ = (x_{1} − y_{1}) − (x′_{1} − y′_{1}) with

x_{1}, y_{1}, x′_{1}, y′_{1} ∈ A, x_{1} − y_{1} = a_{1} − a, x′_{1} − y′_{1} = a′ − a.

The total number of possible values of a is |N(a_{1}) ∩ N(a′)| ≥ 0.03(γ/4)^{2}m, leading to at least

0.03(γ/4)^{2}m (γm/2)^{2} = 0.03 · 2^{−6}γ^{4}m^{3}

representations a_{1} − a′ = (x_{1} − y_{1}) − (x′_{1} − y′_{1}). (Notice that a′ and a can be recovered from any such representation, hence all these representations are pairwise distinct.) Similarly, there are at least 0.03 · 2^{−6}γ^{4}m^{3} representations a_{2} − a′ = (x_{2}−y_{2})−(x′_{2}−y′_{2}) with x_{2}, y_{2}, x′_{2}, y′_{2} ∈ A. Combining, we get at least 0.03^{2}·2^{−12}γ^{8}m^{6} distinct representations

a_{1} − a_{2} = (x_{1} − y_{1}) − (x′_{1} − y′_{1}) − (x_{2} − y_{2}) − (x′_{2} − y′_{2})

and each of them determines a′ uniquely. Using all possible a′ we get at least

0.03^{2} · 2^{−12}γ^{8}m^{6} · \frac{3}{5} |A′| > 2^{−28}γ^{10}m^{7}

representations, as wanted. □

References

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

[C04] E. Croot, An exposition of the Balog-Szemerédi theorem, an expository note available at http://www.math.gatech.edu/ ecroot/balog.pdf.

[G98] W.T. Gowers, A new proof of Szemerédi’s theorem for arithmetic progressions of length four, Geometric And Functional Analysis 8 (1998).

Department of Mathematics, University of Haifa at Oranim, Tivon 36006, Israel.

  E-mail address: seva@math.haifa.ac.il