LECTURE NOTES 1 FOR 254A

TERENCE TAO

1. Introduction

The aim of this course is to tour the highlights of arithmetic combinatorics - the combinatorial estimates relating to the sums, differences, and products of finite sets, or to related objects such as arithmetic progressions. The material here is of course mostly combinatorial, but we will also exploit the Fourier transform at times. We will also discuss the recent applications of this theory to geometric combinatorics problems, and in particular the Kakeya problem.

The setup is as follows. Let Z be an abelian additive group: typical examples of Z are the integers Z, a cyclic group Z = Z/NZ, or a lattice Z^{n}. These are all discrete examples; one could of course consider continuous groups such as the real line R or the circle T but this will not add any new features to the theory, because we will always be dealing with finite subsets of Z.

Let A, B be two finite subsets of Z. We can then form their sum set

A + B := {a + b : a ∈ A, b ∈ B}

or their difference set

A − B := {a − b : a ∈ A, b ∈ B}.

If Z is also a ring, then we could form their product set also:

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

although we will not deal with this set for several weeks.

The type of questions we will be concerned with are the following: what are the relationships between the relative sizes of the sets A, B, A + B, A − B, A + A, A − A, A + B + B, etc.? A typical question is the following: if A is “essentially closed under addition”, in the sense that |A + A| ∼ |A|, does this mean that A is also essentially closed under subtraction, in the sense that |A − A| ∼ |A|? And is A essentially closed under iterated addition, in the sense that |A + A + A| ∼ |A|, etc.? Of course, the number of questions one could ask here is endless, and we do not yet have a completely satisfactory theory, but there are a number of very useful tools developed which can attack these problems.

Some of what we do has the flavor of “approximate group theory”. A subgroup G of Z has the property of being closed under addition, or more precisely that G+G = G. In particular, |G + G| = |G|. We do not directly deal with subgroups here, but instead with approximate subgroups in which (for instance) A + A is only slightly larger than A. The question is then to what extent does the machinery and intuition from group theory (e.g. the concepts of cosets, quotient spaces, homomorphisms, etc.) carry over to this approximate setting.

Another variant we will consider is when we no longer consider complete sum sets A + B, but rather partial sum sets of the form

{a + b : (a, b) ∈ G}

for some “large” subset G of A × B, as well as the associated partial difference set

{a − b : (a, b) ∈ G}.

Knowing the relationship between the size of these two sets has immediate application to the Kakeya problem, which we will discuss later in this course. (I’ll just give one small hint about the relationship here: the Kakeya problem concerns how well various line segments, pointing in different directions, can overlap each other. If a line segment connects two points a and b, then the point (a + b)/2 must also lie in the line segment, whereas the difference (a − b) is essentially the direction of the line segment. Thus if one can compress line segments in lots of directions into a very small set, one should end up with a situation in which a certain partial sum set is small but the corresponding partial difference set is large. Thus any estimate we have connecting partial sum sets with partial difference sets should lead to some bound on the size of Kakeya sets.)

The above questions were all concerned with sums and differences, and the methods we will use to deal with them are mostly combinatorial, and based on basic arithmetic facts, such as the commutativity and associativity of addition, or of such equivalences as “a + b = c + d if and only if a − d = c − b”. However, we will also rely sometimes on the Fourier transform. The reason this transform comes in is the following: if f is a function supported on a set A, and g is supported on B, then the convolution f ∗ g is supported on A + B, while f ∗ g̃ is supported on A − B, where g̃(x) := g(−x) is the reflection of g. Thus, it is plausible that knowledge about how f ∗ g and f ∗ g̃ are related will lead to information about how A + B and A − B are related. To analyze these convolutions, the most obvious tool to use is the Fourier transform.

(A side note: there are basically three aspects to the Fourier transform: the analytic side, which has to do with estimates such as Plancherel, Hausdorff-Young, Littlewood-Paley, Sobolev, and the uncertainty principle; the algebraic side, which has to do with group actions (symmetries), characters, representation theory, and so forth; and the arithmetic side, which has to do with how the Fourier transform measures how well a set is closed under addition or subtraction. The three aspects are of course related, but of course the emphasis in this course will mostly be on the arithmetic side of the Fourier transform).

Closely related to the theory of sums and differences is that of arithmetic progressions. Arithmetic progressions are the most obvious example of “approximate groups”: if A := {a + jr : 1 ≤ j ≤ N} is an arithmetic progression of size N, then A + A is another arithmetic progression of almost the same size (2N − 1, to be precise). More generally, we can consider an arithmetic progression of dimension d, which is something of the form

A := {a + j_{1}r_{1} + … + j_{d}r_{d} : 1 ≤ j_{s} ≤ N_{s} for j = 1, …, d};

for generic choices of spacing r_{1}, …, r_{d}, this has size N_{1} … N_{d}, while A + A is only slightly larger with size (2N_{1}−1) … (2N_{d}−1) ∼ 2^{d}|A|. Thus arithmetic progressions are good examples of sets where |A + A| is comparable to A. One could also take a large subset A′ ⊂ A of an arithmetic progression to obtain another set for which |A′ + A′| is comparable to |A′|. (For instance, A′ could be N/2 numbers from {1, …, N}, selected at random). There is a very deep theorem known as Freiman’s theorem which gives a converse to this statement: if A + A has size comparable to A, then A is a large subset of an arithmetic progression of small dimension. We’ll prove this theorem later in this course.

Arithmetic progressions are closely related to the Fourier transform. The key connection is the following: (infinite) arithmetic progressions are nothing more than the level sets of characters (such as exp(2πikx))! (Another, closely related connection is the Poisson summation formula).

Later on in this course we will study arithmetic progressions in more detail. An old conjecture of Erdös - still unsolved - is whether the prime numbers have arithmetic progressions of arbitrary length. Even in the simplest non-trivial case of arithmetic progressions of length 3, we do not know the answer (though in one sense we are very close, only off by a square root of a logarithm - more on this later). It may be that this question will be resolved using some deep facts from number theory, but it is also quite possible that one can use a far cruder argument, using only the fact that the set of primes in {1, …, N} has density ∼ 1/ log N. This leads to the following problem: given any k ≥ 3, what density do we need of subsets of {1, …, N} to guarantee a non-trivial arithmetic progression of length k? (By non-trivial we mean that the spacing of the progression is non-zero). There is a famous result of Szemeredi in this direction: given any δ > 0 and k ≥ 3, it is true that every subset of {1, …, N} of density at least δ (i.e. cardinality at least δN) has a non-trivial arithmetic progression of length k, provided N is large enough depending on δ and k. We will give several proofs of this result for small values of k, and give a beautiful (but rather unusual) proof by Furstenburg using ergodic theory in the general case.

2. Bounds on A + B

We now begin with one of the most basic questions: given the cardinalities |A|, |B| of two non-empty finite sets A, B in a group Z, what can one say about |A + B|? (This is of course a vacuous question if A or B is empty).

We have a trivial upper bound

|A + B| ≤ |A||B|

and this is sharp, as can be seen when A and B are generic (and Z is large). The more interesting question is what lower bound one can get on |A + B|.

We first make a basic observation: if we translate A or B by any amount, this does not affect the cardinalities of A, B, or A + B (or of A − B, etc.).

Lemma 2.1. If A and B are non-empty finite subsets of Z, then we have |A+B| ≥ |A| + |B| − 1.

Proof We exploit the fact that the integers are ordered. We may translate A so that sup(A) = 0, and translate B so that inf(B) = 0. Since 0 ∈ A, B, we thus see that A + B contains A ∪ B. But A consists of non-positive integers and B consists of non-negative integers, so |A ∪ B| = |A| + |B| − 1, and the claim follows.

These bounds are sharp; see Exercises 1 and 2. Note from Exercise 2 that the lower bound is only attained of A and B are arithmetic progressions.

This settles the problem when the group Z is the integers. What about other groups? We first observe that all torsion-free groups are “equivalent” to Z, in the following sense.

Definition 2.2. An abelian group Z is torsion-free if one has nx ≠ 0 for all nonzero x and all n ≥ 1, where nx = x + … + x is the summation of n copies of x.

Recall that an isomorphism ϕ : Z → Z′ between two abelian groups is a bijection such that ϕ(x + y) = ϕ(x) + ϕ(y) for all x, y ∈ Z. Unfortunately, isomorphisms are very rare (e.g. there is no isomorphism between Z and Z^{2}). Thus we will use a more relaxed notion of isomorphism.

Definition 2.3. Let k ≥ 2, let A ⊂ Z be the subset of one abelian group, and let B ⊂ Z′ be the subset of another abelian group. A Freiman isomorphism of order k ϕ : A → B is a bijection from A to B such that for any x_{1}, …, x_{k}, y_{1}, …, y_{k} ∈ A, we have

ϕ(x_{1}) + … + ϕ(x_{k}) = ϕ(y_{1}) + … + ϕ(y_{k})

if and only if

x_{1} + … + x_{k} = y_{1} + … + y_{k}.

The idea is that a Freiman isomorphism looks exactly like an actual isomorphism as long as you are only allowed to perform at most k additions. Observe that if ϕ is a Freiman isomorphism of order k, then it is automatically a Freiman isomorphism of order k′ for all k′ ≤ k. Also, the composition of two Freiman isomorphisms of order k is another Freiman isomorphism of order k, as is the inverse of a Freiman isomorphism of order k. Note that every genuine isomorphism is a Freiman isomorphism of every order, as is any translation map ϕ(x) := x + x_{0}. Finally, we see that if there is a Freiman isomorphism on A ∪ B ⊂ Z of order at least 2 which maps A to A′ and B to B′, then A + B will have the same cardinality as A′ + B′, in fact ϕ induces an explicit bijection between the two sets. (Note also that the same is true for A − B, because of the simple identity x_{1} + x_{2} = y_{1} + y_{2} ⟺ x_{1} − y_{2} = y_{1} − x_{2}. If one also wants to preserve the cardinality of more complicated expressions such as A + B − B then one needs higher order isomorphisms, of course.).

We can now make precise the statement that torsion-free abelian groups are no richer than the integers, for the purposes of understanding sums and differences of finite sets.

Lemma 2.4. Let A be a finite subset of a torsion-free abelian group. Then for any integer k, there is a Freiman isomorphism ϕ : A → ϕ(A) to some finite subset ϕ(A) of the integers.

Note that the converse is trivial: one can always embed the integers in any other torsion-free abelian group.

Proof We may extend Z to be a vector space over the rationals Q (by replacing Z with Z ⊗Z Q). Without loss of generality we may translate A so that it contains 0. Now look at span(A), the span of A over the rationals. This is a finite-dimensional vector space over Q and is thus isomorphic to Q^{n} for some n. Since A is finite, we thus see that A is contained in some lattice which is isomorphic to Z^{n}. Thus without loss of generality we may assume that Z = Z^{n}.

Now let M be a large integer, and define the map ϕ : Z^{n} → Z by

ϕ(a_{1}, …, a_{n}) := a_{1} + a_{2}M + a_{3}M^{2} + … + a_{n}M^{n−1}.

(i.e. we view elements of Z^{n} as digit strings of integers base M. If M is large enough depending on A and k, we see that this is a Freiman isomorphism (because if M is large enough we never have to “carry” a digit).

As a corollary, we see that Lemma 2.1 extends to all torsion-free abelian groups (and indeed, any inequality involving a finite number of sums and differences which works for Z, will work for all torsion-free abelian groups). Note that something slightly non-trivial is going on here, because Lemma 2.1 relied crucially on the ordering of Z, which is not an arithmetic property and is not preserved under Freiman isomorphisms.

Now we look at what happens when there is torsion, e.g. if Z = Z/NZ for some N. The first thing we see is that we have the trivial bound |A + B| ≥ max(|A|, |B|), since A + B must contain at least one translate of A and at least one translate of B. This is sharp: if A, B are equal to the same finite subgroup G of Z, then |A + B| = |A| + |B|. (See Exercise 3 for a more precise formulation of when |A + B| ≥ max(|A|, |B|) is sharp.)

Now let’s look at what happens when there aren’t any proper subgroups, i.e. when Z = Z/pZ for some prime p.

Theorem 2.5 (Cauchy-Davenport inequality). If A, B are any two non-empty subsets of Z/pZ for some prime p, then

|A + B| ≥ min(|A| + |B| − 1, p).

This theorem is superficially similar to the torsion-free inequality in Lemma 2.1, but is more non-trivial to prove - we will in fact give two and a half proofs of this inequality. Note that we need the p on the right-hand side, since clearly we cannot make |A + B| exceed p.

We first deal with a trivial case, when |A| + |B| − 1 ≥ p. Then |A| + |B| is larger than |Z/pZ|, and by the pigeonhole principle A and x − B will always intersect for any x ∈ Z/pZ. Thus A + B = Z/pZ, and so |A + B| = p as desired. So we only need to prove the inequality |A + B| ≥ |A| + |B| − 1 when |A| + |B| − 1 < p.

We now begin the first proof of the Cauchy-Davenport inequality, based on contradiction. Suppose we have a counterexample to the inequality, so that |A + B| < |A|+|B|−1 ≤ p for some A and B. Let’s assume the counterexample is minimal in the sense that |A| is as small as possible. (Note that the inequality is trivial when |A| = 1, so |A| > 1). By translating A and B we may assume that A, B have a point in common.

Now we do a little trick, known as the Dyson e-transform^{1}: we replace A and B by A′ := A ∩ B and B′ := A ∪ B. From inclusion-exclusion we see that |A′| + |B′| = |A| + |B|. Also we observe that A′ + B′ is a subset of A + B (because

A′ + B′ = A′ + (A ∪ B) ⊆ (A′ + B) ∪ (A′ + A) ⊆ (A + B) ∪ (B + A) = A + B

). Thus A′, B′ will be another counterexample to the Cauchy-Davenport inequality (we’ve kept |A|+|B|−1 the same size, but made A+B equal or smaller cardinality; note that A′ is non-empty by assumption). This will contradict minimality of A unless A′ = A ,i.e. if A is contained in B.

Thus when we have a minimal counterexample A, B to the Cauchy-Davenport inequality, we know that A ⊆ B whenever A and B intersect. More generally, by translation invariance we see that A + x ⊆ B whenever A + x and B intersect. In particular, this means that B − A + A ⊆ B (since A + x intersects B precisely when x ∈ B −A). Thus |B −A+A| ≤ |B|. By Exercise 3 this means that B is a translate of some subgroup of Z/pZ, which means that either |B| = 1 or B = Z/pZ. But in either case we can easily check that we do not have a counterexample to Cauchy-Davenport. Thus there is no minimal counterexample to Cauchy-Davenport.

Now we give a completely different proof of Cauchy-Davenport, due to Elon, Nathanson, and Ruzsa. Write m := |A|, n := |B|; we may assume that m + n − 1 < p. Write F := Z/pZ, and consider the set F^{A}, the set of F -valued functions on A. This is an m-dimensional vector space over the field F. Now consider the polynomials 1, x, x^{2}, …, x^{m−1}, thought of as functions from A to F (i.e. elements of F^{A}). These m functions are linearly independent (over F) in F^{A}, because polynomials of degree m − 1 have at most m − 1 zeroes. Thus these functions form a basis for F^{A}. Similarly the functions 1, y, y^{2}, …, y^{m−1} form a basis for F^{B}.

Now consider F^{A} ⊗ F^{B} = F^{A×B}, the space of F -valued functions f(x, y) for x ∈ A and y ∈ B. Then the functions x^{j}y^{k}, for 0 ≤ j ≤ m − 1 and 0 ≤ k ≤ n − 1, form a basis for F^{A×B}. In particular, if we let S be the mn − 1 monomials {x^{j}y^{k} : 0 ≤ j ≤ m − 1, 0 ≤ k ≤ n − 1, (j, k) ≠ (m − 1, n − 1)}, then x^{m−1}y^{n−1} does not lie in the span of S (over F). On the other hand, observe that x^{j}y^{k} does lie in the span of S if 0 ≤ j < m − 1 (because y^{k} is a linear combination of 1, y, …, y^{n−1}) or if 0 ≤ k < n − 1 (because x^{j} is a linear combination of 1, x, …, x^{m−1}).

1Actually, this is the Dyson 0-transform. The e-transform is the 0-transform composed with a translation by e.

Now suppose that the Cauchy-Davenport inequality failed, so that |A + B| < m + n − 1. Then there exists a set C ⊆ F of cardinality |C| = m + n − 2 such that A + B ⊆ C. Thus if we define the function f ∈ F^{A×B} by

f(x, y) := ∏_{z∈C}(x + y − z)

then f vanishes on A×B, i.e. f ≡ 0. However, if we expand f(x, y) out completely, we get a monomial term of the form

( \begin{matrix}m + n − 2 \\ m − 1 \end{matrix} ) x^{m−1}y^{n−1},

plus a lot of other monomial terms involve x^{j}y^{k} where either j < m−1 or k < n−1 or both, and which thus lie in the span of S. But since m_{n} − 1 < p, we see that

( \begin{matrix}m + n − 2 \\ m − 1 \end{matrix} ) is not a multiple of p, and so it is invertible in F. This contradicts

the fact that x^{m−1}y^{n−1} does not lie in the span of S.

Now we give half of a proof of the Cauchy-Davenport inequality. Note that the Cauchy-Davenport inequality is equivalent to the more symmetrical:

Proposition 2.6. Let A, B, C be non-empty subsets of F such that |A|+|B|+|C| ≥ p + 2. Then A + B + C = Z_{p}.

Indeed, to see how this proposition implies Cauchy-Davenport, just set C := −(Z/pZ\(A + B)) and take contrapositives.

We will use the Fourier transform. Let l^{2}(F) be the vector space of complex-valued functions on F. Given any f ∈ l^{2}(F), we can define the Fourier transform f̂ ∈ l^{2}(F) by

f̂(ξ) := \frac{1}{\sqrt{p}} ∑_{x∈F} e^{2πixξ/p}f(x).

This is an isometry from l^{2}(F) to l^{2}(F). Now look at the subspace l^{2}(A) of l^{2}(F); this is the |A|-dimensional space of complex-valued functions on A. The Fourier transform { \atop l^{2}(A)} of this space is thus also |A| dimensional. Heuristically, this means that given any |A| distinct frequencies ξ_{1}, …, ξ_{|A|}, we should be able to find a function f ∈ l^{2}(A) whose Fourier coefficients f̂(ξ_{1}), …, f̂(ξ_{|A|}) are equal to anything we specify. (This is true if the characters e^{2πixξ_{j}/p} for j = 1, …, |A| are linearly independent on A). If we believe this, then in particular we can make one Fourier coefficient equal to 1 and |A| − 1 other coefficients equal to 0.

Since |A| + |B| + |C| ≥ p + 2, we can find subsets X, Y, Z covering F − {0} with cardinality |A| − 1, |B| − 1, and |C| − 1 respectively. Then if we believe the above heuristic, we can find functions f, g, h in l^{2}(A), l^{2}(B), l^{2}(C) such that f has a nonzero Fourier coefficient at 0 but zero coefficients on X, and similarly for g, h and Y, Z. But by Parseval, this implies that the Fourier coefficients of f ∗ g ∗ h are zero everywhere except at 0 where it is non-zero; this implies that f ∗ g ∗ h is a non-zero constant. Since f ∗ g ∗ h is supported on A + B + C, the claim follows.

Unfortunately I haven’t been able to prove the linear independence of the characters necessary to make this proof work (even though one has a vast amount of freedom in selecting the sets X, Y, Z), however it does show how the Fourier transform can (in principle) be used to control additive information of sets.

3. On A and A + B

Now let’s go back to a general abelian group Z, and suppose that we have two finite non-empty sets A, B. We have the bound |A + B| ≥ |A|. Call a set A B-invariant if we have |A + B| = |A|; of course this can only happen when A has at least as many elements as B. From Exercise 3 we know that B-invariant sets are unions of cosets of some subgroup G, generated by some translate of B. Note that |G| must be larger than or equal to |B|, but less than or equal to |A|.

Thus we have a satisfactory description of B-invariant sets. Now let us call A essentially B-invariant if |A + B| ∼ |A|. Is there an analogous structure theorem for essentially B-invariant sets - that they are essentially cosets of a group generated by B (or one of its translates)?

It turns out the answer is yes - this is a variant of Freiman’s theorem - but it is not easy to prove. However, we can begin to approach this fact with a number of partial results of this nature.

First of all, suppose that A and A′ are two genuinely B-invariant sets. Then A and A′ are unions of cosets of the same sub-group G. This gives us some additional information on the sum set A+A′. First of all, it must also be unions of cosets of G, but secondly, it cannot be as large as |A||A′|, because G + G = G. Indeed, we now have the upper bound |A + A′| ≤ |A||A′|/|G|, and similarly |A − A′| ≤ |A||A′|/|G| (this is basically because we can pass to the quotient group Z/G and use the bound |(A + A′)/G| ≤ |A/G||A′/G|, etc.). In particular, if we use the crude bound |G| ≥ |B|, we obtain |A ± A′| ≤ |A||A′|/|B|.

Let’s look at the dual situation. Suppose A is both genuinely B-invariant and genuinely B′-invariant. Then it is not hard to see that A must consist of cosets of some group G which contains both a translate of B and a translate of B′. In particular, this means that B ± B′ is contained in a coset of G. Using the trivial bound |G| ≤ |A|, we thus obtain the bound |B ± B′| ≤ |A|.

The first question we can ask is whether these crude bounds continue to hold for essentially B-invariant sets instead of genuinely B-invariant sets. One can partially answer this question by means of the following elementary lemma of Imre Ruzsa.

Lemma 3.1. [4] If U, V, W are three non-empty finite subsets of an abelian group Z, then |V − W | ≤ \frac{|U+V ||U+W |}{|U|}.

Note that this is a generalization of the trivial bound |V − W | ≤ |V ||W |. In the special case where U is a subgroup, this bound in fact comes from the trivial bound applied to the abelian group Z/U, and then pulled back to Z. (In that particular case one can improve the left-hand side to |U +V −W |, and more generally one can do so when U is essentially closed under addition, see Q10. However for general U one cannot hope for such an estimate, see Q9). One can think of this lemma as sort of a triangle inequality: if one can control the arithmetic interaction between U and V, and between U and W, then one can also control the arithmetic interaction between V and W.

Proof Consider the linear map π : V ×W → V −W defined by π(x, y) := x−y. This map is clearly surjective, and so we can find a partial inverse f : V − W → V × W such that π(f(w)) = w for all w ∈ V − W. In particular, the points f(w) all have different values of π as w varies in V − W.

Let U^{Δ} ∈ Z × Z be the diagonal U^{Δ} := {(u, u) : u ∈ U}. Observe that (V × W) + U^{Δ} = (U +V)×(U +W). In particular, for any w ∈ V −W, the sets f(w)+U^{Δ} lie in (U + V) × (U + W). Furthermore, since U^{Δ} is in the null space of π, we see that the sets f(w) + U^{Δ} are all disjoint. Since each set f(w) + U^{Δ} has cardinality |U| and we have |V − W | such sets, we have |U||V − W | ≤ |U + V ||U + W | as desired.

In this proof we see a number of interesting tricks, notably the trick of selecting a section (or partial inverse) f to an injective function π, which is then used to obtain a certain disjointness property. We will meet this trick again later in this course.

From this lemma we see that if A and A′ are two essentially B-invariant sets, then

|A − A′| ≤ \frac{|A + B||A′ + B|}{|B|} ≲ \frac{|A||A′|}{|B|}

which is consistent with our previous discussion. Or if A is both essentially Binvariant and B′-invariant, then

|B − B′| ≤ \frac{|A + B||A + B′|}{|A|} ≲ |A|

which is also consistent with our previous discussion. Of course, we would also like to control |A + A′| and |B + B′|, but we do not yet have the technology to do so; the problem is that if |A + B| ∼ |A| we do not yet know if |A − B| ∼ |A| (this seems true, based on analogy with genuinely B-invariant sets, and we will eventually prove something like this, but we certainly don’t know it yet).

Another thing we see from the analogy between essentially B-invariant sets and genuinely B-invariant sets is that if A is essentially B-invariant, then it should also be essentially B + B-invariant, essentially B − B-invariant, essentially B + B + Binvariant, etc. We will prove something like this in the next three sections.

4. Plünnecke’s theorem

The purpose of this section is to prove

Theorem 4.1 (Plünnecke’s theorem). [3] Let A, B be two finite non-empty subsets of an abelian group Z, and suppose that |A+B| ≤ K|A| for some real number K ≥ 1. Then there is some non-empty subset A′ of A such that |A′ + B + B| ≤ K^{2}|A′|.

In particular, every essentially B-invariant set contains an essentially B+B-invariant set. Of course this theorem can be iterated to construct B + B + B + B-invariant sets, etc.

The idea behind this theorem is that if the passage from A to A + B “magnifies” cardinality by K, then the passage from A to A+B +B should magnify cardinality by at most K^{2}. In order to quantify this notion of magnification, we shall need some machinery from graph theory.

Set V_{0} := A, V_{1} := A + B, V_{2} := A + B + B. We can define a directed graph G = G[A, B] connecting V_{0} to V_{1} and V_{1} to V_{2} as follows: for every a ∈ A and b ∈ B, we connect a ∈ V_{0} to a + b ∈ V_{1}; we let E_{0→1} be the set of all such edges. For every a + b ∈ A + B and c ∈ B, we connect a + b ∈ V_{1} to a + b + c ∈ V_{2}.

This graph G[A, B] is an example of a commutative graph, which we now define.

Definition 4.2. Let Z be an abelian group. A commutative graph (or Plünnecke graph) of depth 2 is a graph G with three (possibly overlapping) finite sets of vertices V_{0}, V_{1}, V_{2} ⊂ Z, and two sets of directed edges E_{0→1}, E_{1→2}, such that each edge e in E_{0→1} connects V_{0} to V_{1}, and each edge in E_{1→2} connects V_{1} to V_{2}. Furthermore, we have the following commuting square property: if the edge a → a + b lies in E_{0→1}, and the edge a + b → a + b + c lies in E_{1→2}, then the edge a → a + c must also lie in E_{0→1}, and the edge a + c → a + b + c must also lie in E_{1→2}.

The commuting graph property is so named because it reflects a basic feature of addition, namely that the translation maps a ↦ a + b and a ↦ a + c commute. There are commuting graphs of higher order depths, but we will not need them here (but see Exercise 6).

Observe from the commuting square property that every edge a → a + b in E_{0→1} induces an injection from edges a + b → a + b + c emanating from a + b, and edges a → a + c emanating from a; we call this the pullback map induced by the edge a → a + b. Similarly, any edge d → d + c in E_{1→2} induces a pushforward map from edges d − b → d terminating at d, to edges d + c − b → d + c terminating at d + c. Intuitively, these maps show us that the behavior of the graph from V_{0} to V_{1} must somehow be similar to that from V_{1} to V_{2}.

We do allow V_{0}, V_{1}, V_{2} to overlap, but this can be easily fixed by replacing Z with the product space Z × Z, and replacing V_{0}, V_{1}, V_{2} by their respective lifts V_{0} × {0}, V_{1} × {1}, V_{2} × {2}, and adjusting the edges accordingly. Thus we will take V_{0}, V_{1}, V_{2} to be disjoint. (Note how the freedom to take Cartesian products of our abelian group gives us additional room to maneuver; we will see more examples of this product trick later on).

Let G = (V_{0}, V_{1}, V_{2}, E_{0→1}, E_{1→2}) be a commuting graph. If A′ is a subset of V_{0}, we define G(A′) ⊆ V_{1} to be the set of all vertices in V_{1} which are connected via an edge in E_{0→1} to some vertex in A′. Similarly we define G^{2}(A′) ⊆ V_{2} to be the set of all vertices in V_{2} which are connected via an edge in E_{1→2} to some vertex in G(A′), or equivalently the set of all vertices in V_{2} which are connected via a path of length 2 to a vertex in A′. In the special case G = G[A, B], observe that G(A′) is just A′ + B and G^{2}(A′) is just A′ + B + B.

Plünnecke’s theorem will then follow from the following proposition.

Proposition 4.3. Let G be a commutative graph, and suppose that |V_{1}| < K|V_{0}|. Then |G^{2}(A′)| < K^{2}|A′| for some A′ ⊆ V_{0}.

To prove this proposition, let us first prove it in the special case when C = 1:

Proposition 4.4. Let G be a commutative graph such that |V_{1}| < |V_{0}|. Then |G^{2}(A′)| < |A′| for some A′ ⊆ V_{0}.

This Proposition asserts, informally, that if G is not an expanding map, then neither is G^{2}. We prove this theorem in the next section.

5. Some graph theory

To prove Proposition 4.4, we recall Menger’s theorem from graph theory. Let G be a directed graph, and let A and B be two subsets of G. We define MAXF LOW (A → B; G) to be the maximum number of disjoint paths in G which connect a vertex in A with a vertex in B. We define MINCUT (A → B; G) to be the minimum number of vertices one needs to remove from G in order to disconnect A from B.

Theorem 5.1 (Menger’s theorem). MAXF LOW (A → B; G) = MINCUT (A → B; G).

This theorem has a nice intuitive interpretation; the only obstructions to flowing from A to B are cuts which disconnect A from B. In particular, if one cannot disconnect A from B using s−1 cuts, then one must be able to find s disjoint paths from A to B.

Proof It is obvious that MAXF LOW is less than or equal to MINCUT, since if S is a set disconnecting A from B then every path from A to B must pass through S, and so one can have at most |S| disjoint paths. The other direction, however, is not as obvious.

We induct on the number of edges in G. If there are no edges in G then MAXF LOW and MINCUT are both equal to |A ∩ B|. Now we assume that there is at least one edge (a → b) in G, and the claim has already been proven for all fewer edges.

Let s := MINCUT (A → B; G). We have to construct s disjoint paths from A to B. Let us first look at the quotient graph G/(a = b), with a and b identified into a single vertex {a, b}, and the edge (a → b) deleted. Let S/(a = b) be a minimal subset of G/(a = b) disconnecting A/(a = b) from B/(a = b). If S/(a = b) has at least s elements, then we can apply the induction hypothesis to G/(a = b) (which has fewer edges than G) to construct s disjoint paths in G/(a = b) from A/(a = b) to B/(a = b), which clearly lifts to s disjoint paths in G from A to B as desired. Thus we can assume S/(a = b) has fewer than s elements. But S disconnects A from B, and thus has at least s elements. The only way this can happen is if S contains both a and b, and |S| = s.

Now consider MINCUT (A → S; G). This must be at least s, because if we could disconnect A from S using fewer than s elements, then we could disconnect A from B using the same elements (because every path from A to B must pass through something in S). In fact we see that MINCUT (A → S; G − (a → b)) is at least s, because the edge from a to b plays no role in the connectivity between A and S. By the induction hypothesis we can thus find s disjoint paths from A to S; note each path must have a distinct endpoint since |S| = s. Similarly we can find s disjoint paths from S to B, with each path having a distinct initial point. The paths in the first family must be disjoint from the paths in the second family, except at S, since otherwise we could construct a path from A to B which avoids S entirely. Now all we do is concatenate the s paths from A to S with the s paths from S to B to create the s disjoint paths from A to B.

Now we prove Proposition 4.4. Write s := MAXF LOW (V_{0} → V_{2}; G). Since V_{1} disconnects V_{0} from V_{2}, we have s ≤ |V_{1}| < |V_{0}|. On the other hand, by Menger’s theorem there is a set S ⊆ V_{0}∪V_{1}∪V_{2} of cardinality |S| = s < |V_{0}| which disconnects V_{0} from V_{2}.

Write S = S_{0} ∪S_{1} ∪S_{2}, where S_{j} := S ∩V_{j}. The plan now is to push all the vertices in the S_{1} component of the disconnecting set over to V_{0}.

Let G′ be the subgraph of G whose edges E′_{0→1} ∪ E′_{1→2} are the union of all the paths from V_{0}\S_{0} to V_{2}\S_{2}. Since G has the commutative property, we see easily that G′ does also. Also, S_{1} disconnects V_{0} from V_{2} in G′. In particular, we have MINCUT (V_{0} → V_{2}; G′) = |S_{1}| (if the mincut was any smaller, we could contradict the minimality of |S| = s). Thus there are |S_{1}| disjoint paths in G′, which of course pass through distinct points in S_{1}. Let W_{0} ⊆ V_{0}\S_{0} denote the initial points of these paths and W_{1} ⊆ V_{2}\S_{2} denote the final points, thus |W_{0}| = |S_{1}| = |W_{2}|.

Now we use the commutative property of G′. By pulling back on these |S_{1}| disjoint paths, we see that we have an injection from the edges in E′_{1→2} to the edges in E′_{0→1} emanating from W_{0}, since every edge in E′_{1→2} emanates from some vertex in S_{1}. Similarly, by pushing forward on these paths, we see that we have an injection from the edges in E′_{0→1} to the edges in E′_{1→2} entering W_{2}. The only way both of these statements can be true is if every edge in E′_{0→1} emanates from W_{0}, and every edge in E′_{1→2} terminates at W_{2}. But then we can replace S_{0} ∪ S_{1} ∪ S_{2} by S_{0} ∪ W_{0} ∪ S_{2} to obtain a set of cardinality s disconnecting V_{0} from V_{2} in G. Since S_{0} ∪ W_{0} ∪ W_{2} disconnects S, the set G^{2}(V_{0}\(S_{0} ∪ W_{0})) must be contained in W_{2}. But since s < |V_{0}|, the set V_{0}\(S_{0} ∪ W_{0}) has larger cardinality than |W_{2}|, and we are done.

6. The Cartesian product trick

We have proven Proposition 4.3 in the special case C = 1. Now we leverage this special case to the general case by a surprisingly powerful trick, that of taking Cartesian products. We have already seen a very tiny hint of this when we used a lifting trick to make V_{0}, V_{1}, and V_{2} disjoint.

Let G and G̃ be two commutative graphs in two abelian groups Z and Z̃, with vertex sets V_{0}, V_{1}, V_{2} and Ṽ_{0}, Ṽ_{1}, Ṽ_{2} respectively, and edge sets E_{0→1}, E_{1→2} and Ẽ_{0→1}, Ẽ_{2→2}. Then we can form a Cartesian product G × G̃ in Z × Z̃ with vertex sets V_{0} × Ṽ_{0}, V_{1} × Ṽ_{1}, V_{2} × Ṽ_{2} and edge sets E_{0×1} × Ẽ_{0×1} and E_{1×2} × Ẽ_{1×2}, where the direct sum of two edges (a → b) and (ã → b̃) is understood to be the edge ((a, ã) → (b, b̃)).

One can easily verify that the Cartesian product of two commutative graphs is still commutative. For instance, the Cartesian product of G[A, B] and G[Ã, B̃] is G[A × Ã, B × B̃].

Let us also define the concept of magnification ratio. If G is a commutative graph, we define the magnification ratio D(G) to be the infimum

D(G) := inf_{A′⊆V_{0}, non-empty} \frac{|G^{2}(A′)|}{|A′|};

thus D(G) is the minimum amount by which G^{2} expands sets. Proposition 4.4 thus asserts that if \frac{|V_{1}|}{|V_{0}|} is less than 1, then so is the ratio D(G). We wish to prove

Proposition 4.3, which asserts that if \frac{|V_{1}|}{|V_{0}|} is less than K, then the ratio D(G) is less than K^{2}.

Two examples should be kept in mind. Let Z = Z^{k}, let A := {0}, and let B be the standard basis for Z^{k}. Then in the commutative graph G_{k} := G[A, B], we have |V_{0}| = 1, |V_{1}| = k, and D(G) = \frac{k(k−1)}{2} (why?). Dually, we have the reflected commutative graph G_{k}^{†}, in which the sets V_{0} and V_{2} are swapped, in which |V_{0}| = \frac{k(k−1)}{2}, |V_{1}| = k, and D(G) = \frac{2}{k(k−1)}. Note that in both cases we are pretty close to the bound in Proposition 4.3, up to a factor of 2 or so.

Now we make a key observation connecting magnification ratios with Cartesian products:

Lemma 6.1. Let G and G̃ be commutative graphs. Then D(G × G̃) = D(G) × D(G̃).

Proof Let d := D(G) and d̃ := D(G̃). Then there exists A′ ⊆ V_{0} such that |G^{2}(A′)| = d|A′|, while there exists Ã′ ⊆ Ṽ_{0} such that |G̃^{2}(Ã′)| = d̃|Ã′|. Multiplying together, we obtain

|(G × G̃)^{2}(A′ × Ã′)| = dd̃|A′ × Ã′|

which implies that D(G × G̃) ≥ dd̃.

Now we show the reverse inequality, i.e. for every Ω ⊆ V_{0} × V′_{0}, that

|(G × G̃)^{2}(Ω)| ≥ dd̃|Ω|.

The trick is to factorize the left-hand side. Let I_{V_{0}} = G[V_{0}, {0}] be the trivial commutative graph whose vertex sets V_{0}, V_{1}, V_{2} are all equal to V_{0}, and the edges are just the loops on V_{0}. Similarly define IṼ_{2}. Then observe that

(G × G̃)^{2}(Ω) = (G × IṼ_{2})^{2}(I_{V_{0}} × G̃)^{2}(Ω);

this basically arises because we can think of paths in G × G̃ as a path in I_{V_{0}} × G̃, followed by a path in G × IṼ_{2}. Also, it is easy to see that D(I_{V_{0}} × G̃) = D(G̃) and D(G × IṼ_{2}) = D(G). The claim follows.

Now we have enough tools to finish the proof of Proposition 4.3. Let G be a commutative graph such that |V_{1}|/|V_{0}| < K for some K > 1. Let k be an integer between 2K +1 and 2K +2, so that |V_{1}|/|V_{0}|\frac{2}{k−1} < 1. Then if we take the Cartesian product of G with G_{k}^{†}, the new graph G×G_{k}^{†} has a ratio |V_{1}|/|V_{0}| less than 1. Thus Proposition 4.4 applies, and D(G × G_{k}^{†}) < 1. By Lemma 6.1, we thus have

D(G) < 1/D(G_{k}^{†}) = \frac{k(k − 1)}{2} ≤ 10K^{2}.

This is almost what we want, except that we have lost a constant of 10. To remove this loss we resort to Cartesian products again. Let M be a large integer, and consider G × … × G, the Cartesian product of M copies of G. Applying the bound we have with G replaced by G × … × G (and K replaced by K^{M}) we obtain

D(G × … × G) ≤ 10K^{2M}.

But then applying Lemma 6.1 repeatedly and then taking M^{th} roots, we obtain

D(G) ≤ K^{2}

as desired. (This weird phenomenon occurs everywhere in this subject - all constants can be magically converted to 1 just by raising everything to sufficiently high powers. See, constants really don’t matter after all!) This completes the proof of Proposition 4.3, and hence of Plünnecke’s theorem.

7. Boosting the size of A′

We have just proven Plünnecke’s theorem, which roughly speaking says that if A is essentially B-invariant, then some subset A′ of A is essentially B + B-invariant. While this is a nice theorem to have, it seems a little unsatisfactory in one respect: the set A′ could be much smaller than A. Fortunately, we can remedy this quite easily.

Corollary 7.1. Let A and B be non-empty subsets of an abelian group Z such that |A + B| ≤ K|A|, and let 0 < δ < 1 be a parameter. Then there exists a subset A′ of A of cardinality |A′| ≥ (1 − δ)|A| such that |A′ + B + B| ≤ \frac{2K^{2}}{δ} |A|.

Thus one can make A′ nearly as large as A, although we begin to lose in the constants as one tries to push A′ closer and closer to being 100% of A. One cannot improve this factor K^{2}/δ by much; see Q11.

Proof We shall iterate Plünnecke’s theorem by performing the algorithm. Let A_{0} := A. By Plünnecke’s theorem we may find a non-empty subset A′_{0} of A_{0} such that

|A′_{0} + B + B| ≤ \frac{|A_{0} + B|^{2}}{|A_{0}|^{2}} |A′_{0}| ≤ \frac{K^{2}|A|^{2}}{|A_{0}|^{2}} |A′_{0}|.

Now set A_{1} := A_{0}\A′_{0}. If |A_{1}| < δ|A|, we terminate the algorithm. Otherwise we apply Plünnecke’s theorem again to find a non-empty subset A′_{1} of A_{1} such that

|A′_{1} + B + B| ≤ \frac{|A_{1} + B|^{2}}{|A_{1}|^{2}} |A′_{1}| ≤ \frac{K^{2}|A|^{2}}{|A_{1}|^{2}} |A′_{1}|.

Now we set A_{2} := A_{1}\A′_{1}. If |A_{2}| < δ|A| we terminate the algorithm. We repeat this procedure until it terminates (which it must, as each new A_{j} is strictly smaller than the previous one) at some A_{k} with |A_{k}| < δ|A|. We then set A′ := A\A_{k}; clearly we have |A′| ≥ (1 − δ)|A|. Also, by construction

|A′ + B + B| ≤ ∑_{j=0}^{k−1} |A′_{j} + B + B|

≤ ∑_{j=0}^{k−1} \frac{K^{2}|A|^{2}}{|A_{j}|^{2}} |A′_{j}|

= K^{2}|A|^{2} ∑_{j=0}^{k−1} \frac{|A_{j}| − |A_{j+1}|}{|A_{j}|^{2}}

≤ K^{2}|A|^{2}(\frac{1}{|A_{k−1}|} + ∑_{j=0}^{k−2} \frac{|A_{j}| − |A_{j+1}|}{|A_{j}||A_{j+1}|})

= K^{2}|A|^{2}(\frac{1}{|A_{k−1}|} + ∑_{j=0}^{k−2} \frac{1}{|A_{j+1}|} − \frac{1}{|A_{j}|}

≤ 2K^{2}|A|^{2}/|A_{k−1}|

≤ 2K^{2}|A|/θ

as desired.

Now one could ask why we couldn’t boost A′ up all the way to A and obtain a result of the form “If A is essentially B-invariant, then it is also essentially B + Binvariant”. The following example (due to Ruzsa) shows that this is too naive.

Proposition 7.2. [4] Let n be a large integer. Then there exists sets A of size |A| ∼ n^{2} and B of size |B| ∼ n, such that |A + B| ∼ n^{2} but |A + B + B| ∼ n^{3}.

Proof We shall use the abelian group Z^{2}. We shall need a set B for which B + B is much larger than B; a typical choice is the set

B := {(i, 0) : i = 1, …, n} ∪ {(0, j) : j = 1, …, n};

observe that |B| ∼ n but that |B + B| ∼ n^{2}.

Now let A_{0} be the n × n square {(i, j) : i, j = 1, …, n}; observe that |A_{0}| ∼ n^{2}, |A_{0} + B| ∼ n^{2}, and |A_{0} + B + B| ∼ n^{2}. Thus A_{0} is not a counterexample to our claim; it is both essentially B-invariant and essentially B + B-invariant. However, we can worsen things by adding a small number of maverick elements to A_{0}.

Specifically, let A_{1} be any collection of n points, sufficiently separated in space. Then |A_{1}| ∼ n, |A_{1} + B| ∼ n^{2}, and |A_{1} + B + B| ∼ n^{3}. If we then set A := A_{0} ∪ A_{1} then we obtain our desired counterexample.

Note how a key fact used here was that B + B was much larger than B. If B + B was the same size as B one could do much better; see Q10.

Thus we really do need to remove some exceptional elements before passing from essentially B-invariant sets to B + B-invariant sets. We will see more examples like this later on.

8. Some consequences of Plünnecke’s theorem

From Plünnecke’s theorem we have some immediate corollaries. To state them, we need some notation. Let us write 2A for A + A, 3A for A + A + A, etc, with the convention that 0A = {0}. (This should be kept separate from 2·A := {2a : a ∈ A}, 3 · A := {3a : a ∈ A}, etc.). Plünnecke’s theorem thus says that if you can control A + B, then you can also control A′ + 2B for some refinement A′ of A. Iterating this, we can get

Corollary 8.1 (Iterated Plünnecke’s theorem). Let A, B be two finite non-empty subsets of an abelian group Z, and suppose that |A + B| ≤ K|A| for some real number K ≥ 1. Then for every n = 1, 2, 3, … there is some non-empty subset A_{n} of A such that |A_{n} + nB| ≤ K^{C(n)}|A_{n}| for some absolute constant C(n).

Indeed, this claim when m is a power of two just follows by iterating Plünnecke’s theorem log_{2} m times, and then one makes the simple observation that once the theorem is proven for any large n, it automatically holds for smaller n (because if n < n′ then nA is contained in a translate of n′A).

One can in fact take C(n) = n; see Exercise 6.

From the above Corollary and Lemma 3.1 we see that

|nB − nB| ≤ \frac{|A_{n} + nB|^{2}}{|A_{n}|} ≤ K^{2C(n)}|A_{n}| ≤ K^{2C(n)}|A|.

Since nB is contained in a translate of mB when n ≥ m, we thus easily obtain

Corollary 8.2 (Sumset estimates.). Let A, B be two finite non-empty subsets of an abelian group Z, and suppose that |A + B| ≤ K|A| for some real number K ≥ 1. Then for every n, m ≥ 0 we have the bound

|nB − mB| ≤ K^{C(n,m)}|A|.

Thus if A is essentially B-invariant, then the sum or difference of an arbitrary number of copies of B cannot get much larger than A. This is consistent with our intuition that if A is essentially B-invariant, then B is essentially contained inside a coset of a subgroup G, and A is essentially the union of such cosets.

Let us call a set A essentially closed under addition if |A + A| ≲ |A|. The sumset estimates, specialized to the case A = B, then say that if A is essentially closed under addition, then it is also essentially closed under subtraction, and more generally any expression of the form A ± A ± A … ± A also has size comparable to |A|. This means that A behaves essentially like an additive subgroup of Z (especially if we translate A so that A contains the origin) - with one basic caveat: the more arithmetic operations we perform on A, the larger the exponent C(n, m) can get, and so eventually we might lose our closure properties if we insist on doing too much arithmetic. (A basic example to keep in mind here is when Z is the integers and A := {1, …, N}. This set is more or less closed under arithmetic operations as long as you don’t take too many of them.)

The exponents C(n) and C(n, m) can be computed, and the values that were worked out here are not the best exponents known, but we will not bother to make these exponents explicit and sharp in these lectures.

One can swap addition and subtraction here; if A is essentially closed under subtraction, then it is also essentially closed under addition (one just uses B := −A instead of B := +A in the sumset estimates. See also Exercise 7).

One should compare this situation with that of subgroups and submonoids. A submonoid G is closed under sums of two elements: G + G ⊆ G, and hence by iteration it is closed under sums of arbitrary elements: nG ⊆ G. If G is a finite monoid, then it must have torsion, and thus n · G = −G for some large n, and thus G is also closed under negation. Hence G is a subgroup and thus closed under all arithmetic operations. The above sumset estimates can thus be viewed as a perturbation of this basic principle: closure under one arithmetic operation (+ or -) implies closure under the other operation, and under iterates of these operations.

9. Covering one set by another

Compare the following two notions:

• A set G is closed under addition if G + G = G.

• A set A is essentially closed under addition if |A + A| ∼ |A|.

Up until now I have been trying to convince you that the second notion is basically a mild generalization of the first, although it is much more robust (it is stable under translations, finite unions of translations, and also refinements - passing from A to a subset A′ of comparable cardinality) But the observant reader should have noted that there seems to be a large gap between the two, because the first notion is about equating two sets, whereas the second notion is only about comparing two cardinalities. Saying that |A + A| and |A| have comparable cardinalities does not necessarily mean that they have similar structure... does it?

On the other hand, we do know that if |A+A| = |A|, then A is indeed a translate of a subgroup G, and so A = G + x for some x (see Exercise 3). So, up to translations (which, it should be clear by now, are quite harmless), the extreme limiting case of the second notion does indeed correspond to the first. So this helps close the gap between the two notions, at least in the extreme limiting case when |A + A| = |A|. However, this doesn’t help us when, say, |A + A| = |A| + 1; now the two notions seem quite different again.

To close this gap we use yet another clever elementary lemma of Imre Ruzsa.

Lemma 9.1 (Ruzsa’s quotient lemma). [5] Let A and B be finite sets. Then there exists a set X of cardinality |X| ≤ \frac{|A+B|}{|A|} such that B ⊆ X + A − A. In other words

we can cover B by at most \frac{|A+B|}{|A|} translates of A − A.

Proof Consider the sets x + A, where x ranges over B. These are a collection of sets contained in A + B, each with cardinality |A|. Let us consider a maximal disjoint family of such sets, i.e. a collection of the form {x + A : x ∈ X} such that the x + A are all disjoint. Such a collection can easily be obtained by the greedy algorithm. By the disjointness, we see that there can be at most \frac{|A+B|}{|A|} such sets. Now let b be any element of B. By maximality, b + A must intersect one of the x + A, i.e. b ∈ x + A − A for some x ∈ X, i.e. b ∈ X + A − A, thus B ⊆ X + A − A as desired.

Note how powerful this “maximal disjoint family” trick is. Note what is going on in the case when A is a subgroup, and B is a union of cosets of A (so that |A + B| = |B|). Then what X is doing is simply selecting a single element from each coset inside B, and of course X will end up having cardinality |B|/|A|. Thus this lemma is a generalization of the familiar algebraic notion of taking a quotient by a subgroup, which of course turns each coset into a single element of the quotient space.

To apply this quotient lemma, suppose that A is essentially closed under addition: |A + A| ∼ |A|. Then by sumset estimates we also have |nA − mA + A| ∼ |A|. By the above lemma, we can thus cover nA − mA by O(1) translates of A − A. In particular, if we set G := A − A, then G + G and G − G, and more generally nG − mG, is contained in O(1) translates of G.

Thus: if A is essentially closed under addition, then there is a slightly larger set G := A − A, which is “even more closed under addition” in the sense that G + G or G − G is contained in O(1) translates of G. Note that A is itself contained in a translate of G, and has comparable size, |A| ∼ |G|. This provides a satisfying connection between the approximate notion of “essentially closed under addition” and the more precise notion of “genuinely closed under addition”.

One may ask why we need this intermediate set G - why couldn’t we just use A directly? In other words, could we say that if A is essentially closed under addition, that A + A is contained in O(1) translates of A, etc? Looking at our first model example - that of A = {1, …, N} in the integers Z = Z, this seems plausible. However, this statement is false. Let us set A to be a random subset of {1, …, N} by flipping an independent coin for each integer from 1 to N and placing that integer in A if the coin turns up heads. This is almost surely a set of cardinality ≈ N/2. (By “almost surely” I mean that the probability of this statement being false is exponentially small in N). The set A + A almost surely contains a large interval, e.g. {N/2, …, 3N/2} (why?). However, it is difficult to cover such an interval with only a small number of translates of A. For instance, if you were to use two translates of A to cover {N/2, …, 3N/2}, you would almost surely only be able to cover 3/4 of this interval (why?). With three translates you could cover 7/8 at most, almost surely, and so forth. Indeed, if you are good with probability you will see that you will almost surely need ∼ log N translates to cover all of A + A.

This illustrates an important principle: even if a set A contains a lot of “holes” - in this case, it is missing half the elements of the interval {1, …, N}, the set A − A is much better behaved and will have almost no holes.

It turns out that this logarithmic loss is more or less sharp: if you do insist on trying to cover things using A instead of A − A, you only lose that logarithmic factor.

Theorem 9.2. Let A be a finite subset of an abelian group Z of cardinality |A| = N > 1 which is essentially closed under addition. Then for any fixed n, m ≥ 0 there is a set X = X(n, m) with cardinality |X| ≲ log N such that mA − nA ⊆ X + A.

In other words, a set like A − A (or more generally mA − nA) can be covered by O(log N) translates of A.

To illustrate the basic idea, let us first show a baby version of this theorem, which is already somewhat interesting:

Lemma 9.3. Let G be a finite group of cardinality |G| = N, and let A be a nonempty subset of G. Then one can cover G using at most O(\frac{N}{|A|} log N) translates of A; in other words, there exists a subset X of G with cardinality |X| ≲ \frac{N}{|A|} log N such that X + A = G.

Proof We shall use a random argument. We may assume that N ≫ 1 is large. Let 1 ≤ r ≪ N be a number to be chosen later. We construct X by taking each element of G and placing it in X with probability r/N, with each element being chosen independently of all the others. Clearly |X| = ∑_{x∈G} χ_{X}(x) has expected value of r, since χ_{X}(x) has expectation r/N for each x ∈ G. Furthermore, it is not hard to see that

|X|^{2} = ∑_{x∈G} ∑_{y∈G} χ_{X}(x)χ_{X}(y) = |X| + ∑_{x,y∈G:x≠y} χ_{X}(x)χ_{X}(y)

has expectation r +N(N −1)\frac{r}{N} \frac{r}{N} ∼ r^{2}, for similar reasons. By Markov’s inequality we thus see that |X| = O(r) with probability at least 99%.

Now we compute the expected value of |X + A|. First we take any element g ∈ G and ask what is the probability that g lies in X + A. This is the same as saying that X has some intersection with g − A. But g − A has |A| elements and each element has independently an r/N chance of lying in X. Thus the probability that X intersects g − A is

1 − (1 − \frac{r}{N})^{|A|}.

Summing over all g, we see that the expected value of |X + A| = ∑_{g∈G} χ_{X+A}(g) is

N − N(1 − \frac{r}{N})^{|A|} ≥ N − Ne^{−r|A|/N},

since e^{−x} ≥ 1 − x for all 0 ≤ x ≤ 1 by convexity of e^{−x}. Thus we can choose r = O(\frac{N}{|A|} log N) such that |X + A| has expected value at least N − 0.01, which means that it has to be equal to N at least 99% of the time. But then we see that X + A = G and |X| = O(r) at least 98% of the time, and we are done (since we only need to find at least one such X.

Another way to prove this lemma is sketched in Exercise 8. Note that this argument also shows that if you only want X + A to fill up, say, 90% of G, rather than all of G, then you only need O(N/|A|) translates rather than O(\frac{N}{|A|} log N). (Thus, fighting for that last 10% of G takes a lot of effort! Compare with the discussion on exceptional sets after Corollary 7.1).

Now we prove Theorem 9.2. Fix m, n, and write B := mA − nA. The idea is now to run the same argument, but using A − A as a proxy for the group G; we already saw earlier that in many ways A − A functions like a group. However, for technical reasons we first need to improve Lemma 9.1 a little bit:

Lemma 9.4 (Improved quotient lemma). Let A and B be finite sets. Then there exists a set X in Z of cardinality at most \frac{2|A+B|}{|A|} such that X + A − A covers B, and moreover for every y ∈ B there are at least |A|/2 triplets (x, a, a′) ∈ X × A × A such that x + a − a′ = y.

Thus not only does X + A − A cover B; it covers B multiple times. The only loss here compared to Ruzsa’s quotient lemma is that X could be twice as big.

Proof We perform the following algorithm. Initialize X to be the empty set, so that X + A − A is also the empty set. We now run the following loop. If we cannot find any element y in B which is “sufficiently disjoint from X + A − A” in the sense that |(y + A) ∩ (X + A)| < |A|/2, we terminate the algorithm. Otherwise, if there is such an element y, we add it to X, and then repeat the algorithm.

Every time we add an element to X, the size of |X + A| increases by at least |A|/2, by construction. However, X + A must always lie within the set B + A. Thus this algorithm terminates after at most \frac{2|A+B|}{|A|} steps.

Now let y be any element of B. By construction, we have |(y+A)∩(X+A)| ≥ |A|/2, and hence y has at least |A|/2 representations of the form x + a − a′ for some (x, a, a′) ∈ X × A × A′, as desired.

We are now ready to cover B by translates of A. We apply Lemma 9.4 to create our set X; note that |A| = N and |B + A| = O(N) by sumset estimates, so |X| = O(1). Let 1 ≤ r ≪ N be a number to be chosen later (we may of course assume that N is large since the claim is trivial for N small). Let Y be a subset of X × A chosen randomly, so that each pair (x, a′) of X ×A has an independent probability of \frac{r}{N|X|} of being selected. By the argument in Lemma 9.3 we see that |Y | = O(r) with probability at least 99%. Now pick any element y ∈ B and let us ask what is the probability that y lies in Y + A. From Lemma 9.4 we know that there are at least N/2 pairs (x, a′) ∈ X × A′ such that y lies in x − a′ + A. Each of these pairs has independently a r/N|X| chance of lying in Y. Thus the probability that y lies in Y + A is at least

1 − (1 − \frac{r}{N|X|})^{N/2} ≥ 1 − e^{−r/2|X|}.

Thus the expected value of |(Y + A) ∩ B is at least

|B|(1 − e^{−r/2|X|}).

If we choose r to be a sufficiently large multiple of log N, this is greater than |B| − 0.01, and so we have B ⊆ Y + A with probability 99%. Thus we have B ⊆ Y + A and |Y | ≲ log N for 98% of the choices of Y, and we are done.

We now have quite a satisfactory theory of the structure of sets A which are essentially closed under addition or subtraction; we now know that they are also closed under more complicated sums and differences, and we can cover these more complicated sums and differences by a small number of translates of either A or A − A, thus keeping close to our heuristic that A should basically be a translate of a subgroup, or a large subset thereof. Even this is not the best thing we can say; we can make this heuristic even more precise, thanks to a deep theorem known as Freiman’s theorem, but we won’t tackle it until the next set of notes.

10. A + B and A − B

In the previous section we saw that if A was essentially closed under addition - so that |A + A| ∼ |A|, then it was also essentially closed under subtraction |A − A|, and indeed we were able to say a lot more than this. Now one could ask whether the same thing is true when one has two sets instead of one. For instance, if we know that |A + B| ∼ |A|, does this mean that |A − B| ∼ |A|?

On the positive side, we have Q3, which implies that if |A + B| = |A|, then B is contained in some subgroup G, and A is the union of cosets of G, and so |A − B| = |A| as well. On the other hand, this argument also gives that |A + B + B| = |A|, and we already know from Proposition 7.2 that A+B +B is a problem. As it turns out, A − B is also not well behaved, and for similar reasons:

Proposition 10.1. [4] For any integer K ≥ 1, there exist finite subsets A, B of an abelian group Z such that |A + B| ∼ |A| but |A − B| ≳ |A|^{2−log 6/ log 7}.

Proof One of the key ingredients of Proposition 7.2 was to use a B such that B+B was a very different size from B. Here, the analogous trick is to use a B such that B − B is a very different size from B + B. To do this, first observe that we clearly cannot use a B which is symmetric, e.g. B = −B, or more generally B = x_{0} − B. The simplest non-symmetric set is B := {0, 1, 3} in the group Z/7Z; for this set, B −B = {−3, −2, −1, 0, 1, 2, 3} has cardinality 7, while B +B = {0, 1, 2, 3, 4, 6} has cardinality 6. This difference may not look like much, but we can use the Cartesian product trick to boost this. Let N be a large integer, and let B := {0, 1, 3}^{N} in the group Z := (Z/7Z)^{N}. Then |B| = 3^{N}, |B − B| = 7^{N}, and |B + B| = 6^{N}.

Thus if we were to set A = B, then A − B is significantly larger than A + B. This however is not enough, because A + B is much larger than A.

Another option is to set A = (Z/7Z)^{N}. Then A + B is the same size as A, but unfortunately so is A − B.

To get a genuine counterexample we shall take a combination of the two previous examples. Specifically, we set Z := (Z/7Z)^{N} × Z, so that Z contains an infinite number of copies of (Z/7Z). We let B be as before (identifying (Z/7Z)^{N} with (Z/7Z)^{N} × {0}), and let A consist of one copy of (Z/7Z)^{N} and roughly (7/6)^{N} copies of B. Then A has cardinality comparable to 7^{N} + (7/6)^{N}3^{N} ∼ 7^{N}, A + B has cardinality 7^{N} + (7/6)^{N}6^{N} ∼ 7^{N}, but A − B has cardinality 7^{N} + (7/6)^{N}7^{N} ∼ (49/6)^{N}. The proof follows.

Thus essentially B-invariant sets aren’t necessary (−B)-invariant. It is possible to make an example in the torsion-free group Z instead of the group (Z/7Z)^{N} × Z; the idea is to use the base 7 representation of the integers. We leave the details to the reader (or see [4]).

In the case of A + B and A + B + B, Plünnecke’s theorem (and Corollary 7.1) allow us to salvage a satisfactory result if we pass from A to a subset A′; we know that we can make A′ nearly the same size as A, though we begin to pay if we try to make A′ too close to A. We could hope to pull off a similar trick with A + B and A − B, but now we will lose a logarithm.

Proposition 10.2. [4] For any integer n ≥ 1, there exist finite non-empty subsets A, B of an abelian group Z such that |A| ∼ |A + B| ∼ C^{n}, and |B| ∼ n, but |A′ − B| ≳ n|A′| for all non-empty subsets A′ of A.

Proof The trick here is to make A + B “small” (so many sums of the form a + b collide) but A − B “large” (so many differences of the form a − b are distinct; in fact, since |A′ − B| ∼ |A′||B|, we need a very large fraction of the differences to be distinct). Furthermore, this largeness of A − B has to be fairly “uniform”; unlike Proposition 10.2, we cannot get away with using a small exceptional set to generate this largeness of A − B.

We shall work in the group Z^{2n}. Let A be the set

A := {(x_{1}, x_{2}, …, x_{2n}) ∈ Z^{2n} : x_{1} + … + x_{n} = n; x_{1}, …, x_{n} ≥ 0}.

In other words, A is the set of partitions of n consecutive objects into 2n groups.

The number of such partitions is ( \begin{matrix}3n − 1 \\ 2n − 1 \end{matrix} ), because every time you choose 2n−1

objects out of an ordered sequence of 3n − 1 objects, the remaining n objects are partitioned into 2n groups, and this map from choices to partitions is bijective. From Stirling’s formula n! ∼ n^{n}e^{−n}n^{−1/2} we thus see that |A| ∼ C^{n} for some C (actually C = 27/4, if you must know).

Now let B := {e_{1}, …, e_{2n}} be the basis elements of Z^{2n}, thus |B| = 2n. Clearly A + B is equal to

A + B = {(x_{1}, x_{2}, …, x_{2n}) ∈ Z^{2n} : x_{1} + … + x_{n} = n + 1; x_{1}, …, x_{n} ≥ 0}

and thus has cardinality

|A + B| = ( \begin{matrix}3n \\ 2n − 1 \end{matrix} ) = \frac{3n}{n + 1} ( \begin{matrix}3n − 1 \\ 2n − 1 \end{matrix} ) ∼ |A|.

Now look at A − B. The problem here is that every element (x_{1}, x_{2}, …, x_{2n}) in A has at least n co-efficients which are zero, and thus generates n elements in A − B for which exactly one of the coefficients is equal to −1. Conversely, given such an element of A − B one can reconstruct the elements of A and B which generated it; i.e. these elements of A − B are all distinct. Thus |A − B| ≥ n|A|, and more generally |A′ − B| ≥ n|A′| for every subset A′ of A.

The factor n is pretty small compared to A, it is comparable to log |A|. We now show that this logarithmic loss is about as bad as it can get:

Proposition 10.3. Let A, B be finite non-empty subsets of an abelian group Z such that |A| ∼ |A + B|. Then for any ε > 0 we can find some subset A′ of A such that |A′| ∼ |A| and |A′ − B| ≤ C_{ε}|A|^{1+ε}.

Proof We let N be a large number to be chosen later. By the Iterated Plünnecke theorem we can find a subset A′ of A such that |A′ + 2^{N}B| ≤ C(N)|A′|; by using either the statement or proof of Corollary 7.1 one can also make |A′| ∼ |A|. Now consider the sequence of numbers

1, |B|, |2B|, |4B|, …, |2^{N}B|.

These are an increasing sequence of numbers bounded above by C(N)|A|, so by the pigeonhole principle there exists 0 ≤ j < N such that

|2^{j+1}B| ≤ C(N)|A|^{1/N}|2^{j}B|.

Now let B_{∗} := 2^{j}B, thus

|B_{∗} + B_{∗}| ≤ C(N)|A|^{1/N}|B_{∗}|.

By Lemma 3.1 we have

|A′ − B_{∗}| ≤ \frac{|A′ + B_{∗}||B_{∗} + B_{∗}|}{|B_{∗}|} ≤ C(N)|A|^{1/N}|A′ + B ∗ | ≤ C(N)|A|^{1/N}|A|

as desired, if N is chosen large enough.

This exploiting of the pigeonhole principle in a long monotone sequence is a useful trick: the point is that a long monotone sequence must be close to constant at some point along the sequence.

This above discussion concludes the limit of what we will say about the cardinality of sets such as A, A + B, A + A, A − B, etc. In the next set of notes we will analyze the structure of these sets also.

11. Exercises

• Q1. Let m ≥ 1, n ≥ 1, and m + n − 1 ≤ s ≤ mn. Show that there exists sets A, B of integers such that |A| = m, |B| = n, and |A + B| = s. (Thus there are no further relationships on |A|, |B|, |A+B| beyond the bounds |A| + |B| − 1 ≤ |A + B| ≤ |A||B| already proven.)

• Q2. Let A, B be non-empty finite sets of integers with |A|, |B| ≥ 2. Show that |A+B| = |A|+|B|−1 if and only if A and B are arithmetic progressions with exactly the same spacing.

• Q3. Let A, B be non-empty finite subsets of an abelian group Z. Show that |A + B| = |A| if and only if A is the union of cosets of some finite subgroup G of Z, and B is contained in a translate of the same subgroup G. (As a corollary, note that |A + A| = |A| if and only if A is a translate of a subgroup G).

• Q4*. Let A, B be non-empty finite subsets of the field Z/pZ, and suppose that |A + B| = |A| + |B| − 1 < p. Show that A and B are arithmetic progressions with exactly the same spacing. (Hint: Use the Dyson e-transform proof, and induct on the size of A. The key is to show that if A′ and B′ are progressions with the same spacing, and A′ + B′ = A + B, then A and B are also progressions with the same spacing. You may find it convenient to use translations and isomorphisms to transform arithmetic progressions to an interval {1, 2, …, m}. Note that if the interval is small enough, then one can perform a Freiman isomorphism to transform Z/pZ back to Z.)

• Q5. Suppose that A is a finite collection of women, and B is a finite collection of men, such that some of the women are compatible with some of the men (i.e. there is a graph G from A to B describing the compatibility). For every set A′ ⊆ A of women, let G(A′) denote the set of men who are compatible with at least one woman in A′. Show that it is possible for each woman in A to marry a separate man with whom she is compatible, if and only if one has |G(A′)| ≥ |A′| for all |A′| ⊆ A. (This is known as Hall’s marriage theorem, and can be deduced from Menger’s theorem. One could say that this theorem lists all the possible (graph-theoretical) obstructions to marriage.)

• Q6**. Extend Plünnecke’s theorem to higher sums. More precisely, show that if A, B are finite non-empty subsets of an abelian group Z such that |A + B| ≤ C|A|, and n ≥ 1, then there is a non-empty subset A′ of A such that |A′ + nB| ≤ C^{n}|A′|. (Note that iterating Plünnecke’s theorem only gives this for n which are powers of two. For general n, the main trick is to start with a separating set of the obvious graph on V_{0} ∪ … ∪ V_{n}, and move all the intermediate separating points down to V_{0}.)

• Q7. Suppose that A, B are finite sets such that |A + B| ∼ |A| ∼ |B|. Show that A, B, and A ∪ B are all essentially closed under addition (Hint: Use the iterated Plünnecke theorem). Conclude that any expression of sums and differences of A and B, e.g. A+A−A+B−B−B, has cardinality comparable to |A|.

• Q8. Let A and B be any two non-empty subsets of a finite abelian group G. Use the pigeonhole principle to show that there exists a translate B + x of B in G such that |A ∩ (B + x)| ≥ \frac{|A||B|}{|G|}, and hence that

\frac{|G| − |A ∪ (B + x)|}{|G|} ≤ \frac{|G| − |A|}{|G|} \frac{|G| − |B|}{|G|}.

Iterate this fact to give a different proof of Lemma 9.3.

• Q9. Show that for any n ≥ 1, there exists an abelian group Z and a finite set U such that |U| = 4^{n}, |U + U| = 10^{n}, and |U + U − U| = 28^{n}. (Hint: first do the case n = 1). Conclude that one cannot hope to replace the left-hand side of Lemma 3.1 by |U + V − W |, even if we are prepared to lose a constant or a logarithm in the estimate.

• Q10. Let A, A′, B be finite non-empty subsets of an abelian group Z such that B is essentially closed under addition. The purpose of this question is to show that B behaves much like a subgroup of Z for purposes of quotienting out by B.

• (a) Show that |A + B| ∼ |A| if and only if A is contained in O(|A|/|B|) translates of B.

• (b) Show that if |A + B| ∼ |A|, then |A + mB − nB| ∼ |A| for all m, n (with the constants depending on m and n, of course.

• (c) Show that |A + A′ + B| ≲ \frac{|A+B||A′+B|}{|B|} (compare this with Lemma 3.1).

• Q11. Let 0 < δ < 1. Show that there exists finite non-empty subsets A,B of an abelian group Z such that |A + B| ∼ |A| such that for every subset A′ of A for which |A′| ≥ (1 − δ)|A|, we have |A′ + B + B| ≳ |A|/δ. (Hint: adapt the proof of Proposition 7.2). Thus one cannot get rid of the 1/δ factor in Corollary 7.1.

References

[1] B. Green, Edinburgh lecture notes on Freiman’s theorem, preprint.

[2] M. Nathanson, Additive number theory. Inverse problems and the geometry of sumsets, Graduate Texts in Mathematics 165, Springer-Verlag, New York, 1996.

[3] H. Plünnecke, Eigenschaften un Abschätzungen von Wirkingsfunktionen, BMwF-GMD-22 Gesellschaft für Mathematik und Datenverarbeitung, Bonn 1969.

[4] I. Ruzsa, Sums of finite sets, Number Theory: New York Seminar; Springer-Verlag (1996), D.V. Chudnovsky, G.V. Chudnovsky and M.B. Nathanson editors.

[5] 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: tao@math.ucla.edu