LECTURE NOTES 1 FOR 254A TERENCE TAO 1. Introduction The aim of this course is to tour the highlights of arithmetic combinatorics - the combinatorialestimatesrelatingtothesums,differences,andproductsoffinitesets, ortorelatedobjectssuchasarithmeticprogressions. Thematerialhereisofcourse 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 aretheintegersZ,acyclicgroupZ =Z/NZ,oralatticeZn. Thesearealldiscrete examples;onecouldofcourseconsidercontinuousgroupssuchasthe reallineRor 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 | | ∼ | | alsoessentiallyclosedundersubtraction,inthe sensethat A A A? And isA | − |∼| | essentiallyclosedunderiteratedaddition,inthe sensethat A+A+A A, etc.? | |∼| | Ofcourse,the numberofquestionsonecouldaskhereisendless,andwedonotyet have a completely satisfactory theory, but there are a number of very useful tools developed which can attack these problems. Someofwhatwedohastheflavorof“approximategrouptheory”. AsubgroupGof Zhasthepropertyofbeingclosedunderaddition,ormorepreciselythatG+G=G. In particular, G+G = G. We do not directly deal with subgroups here, but | | | | 1 2 TERENCE TAO instead with approximate subgroups in which (for instance) A+A is only slightly largerthanA. Thequestionisthentowhatextentdoesthemachineryandintuition 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 appli- cation to the Kakeya problem, which we will discuss later in this course. (I’ll just give one small hint about the relationshiphere: the Kakeyaproblem 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 smallset, one should end up with a situationin whicha certainpartialsum setis smallbutthe correspondingpartialdifference set is large. Thus any estimate wehaveconnectingpartialsumsetswithpartialdifferencesetsshouldleadtosome bound on the size of Kakeya sets.) The above questions were all concerned with sums and differences, and the meth- ods we will use to deal with them are mostly combinatorial, and based on basic arithmeticfacts,suchasthecommutativityandassociativityofaddition,orofsuch equivalences as “a+b =c+d if and only if a d= c b”. However, we will also − − relysometimesontheFouriertransform. Thereasonthistransformcomesinisthe 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 − abouthowf g andf g˜arerelatedwillleadto informationabouthowA+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 an- alytic 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 closedunder 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 pro- gressions. Arithmetic progressions are the most obvious example of “approximate groups”: if A:= a+jr :1 j N is an arithmetic progressionof size N, then { ≤ ≤ } A+A is another arithmetic progression of almost the same size (2N 1, to be − LECTURE NOTES 1 3 precise). More generally, we can consider an arithmetic progression of dimension d, which is something of the form A:= a+j r +...+j r :1 j N for j =1,... ,d ; 1 1 d d s s { ≤ ≤ } forgenericchoicesofspacingr ,... ,r ,this hassize N ...N ,while A+Ais only 1 d 1 d slightlylargerwithsize(2N 1)...(2N 1) 2d A. Thusarithmeticprogressions 1 d − − ∼ | | are good examples of sets where A+A is comparable to A. One could also take | | a large subset A′ A of an arithmetic progressionto obtain another set for which ⊂ A′ + A′ is comparable to A′ . (For instance, A′ could be N/2 numbers from | | | | 1,... ,N ,selectedatrandom). ThereisaverydeeptheoremknownasFreiman’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 progressionsare closely related to the Fourier transform. The key con- nectionisthefollowing: (infinite)arithmeticprogressionsarenothingmorethanthe level sets of characters (such as exp(2πikx))! (Another, closely related connection is the Poisson summation formula). Lateroninthiscoursewewillstudyarithmeticprogressionsinmoredetail. Anold conjectureofErdo¨s-stillunsolved- iswhether the prime numbershavearithmetic progressionsofarbitrarylength. Eveninthe simplestnon-trivialcaseofarithmetic 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/logN. 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 nowbeginwith oneofthe mostbasic questions: giventhe 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 . | | 4 TERENCE TAO We firstmakea basicobservation: ifwe translateAorB by anyamount,this does not affect the cardinalities of A, B, or A+B (or of A B, etc.). − Lemma 2.1. IfAandB arenon-emptyfinitesubsetsofZ,thenwehave 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. | ∪ | | | | |− Theseboundsaresharp;seeExercises1and2. NotefromExercise2thatthelower 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 non- 6 zero 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 → suchthat φ(x+y)=φ(x)+φ(y) for allx,y Z. Unfortunately, isomorphismsare ∈ very rare (e.g. there is no isomorphism between Z and Z2). 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 thesubsetofanotherabeliangroup. AFreiman isomorphism of order k ⊂ φ:A B is a bijection from A to B such that for any x ,... ,x ,y ,... ,y A, 1 k 1 k → ∈ we have φ(x )+...+φ(x )=φ(y )+...+φ(y ) 1 k 1 k if and only if x +...+x =y +...+y . 1 k 1 k The idea is that a Freiman isomorphism looks exactly like an actual isomorphism aslongasyouareonlyallowedtoperformatmostk additions. Observethatifφis aFreimanisomorphismoforderk, thenit is automaticallya Freimanisomorphism 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 isomorphismoforderk. NotethateverygenuineisomorphismisaFreimanisomor- phismofeveryorder,asis anytranslationmapφ(x):=x+x . Finally,weseethat 0 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 anexplicit bijectionbetween the two sets. (Note alsothat the sameis true forA B,becauseofthe simple identity x +x =y +y x y =y x . 1 2 1 2 1 2 1 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.). − LECTURE NOTES 1 5 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 mayextendZ tobeavectorspaceovertherationalsQ(byreplacingZ withZ ZQ). WithoutlossofgeneralitywemaytranslateAsothatitcontains0. ⊗ Now look atspan(A), the spanofA overthe rationals. This is a finite-dimensional vector space over Q and is thus isomorphic to Qn for some n. Since A is finite, we thus see that A is contained in some lattice which is isomorphic to Zn. Thus without loss of generality we may assume that Z =Zn. Now let M be a large integer, and define the map φ:Zn Z by → φ(a ,... ,a ):=a +a M +a M2+...+a Mn−1. 1 n 1 2 3 n (i.e. we view elements of Zn as digit strings of integers base M. If M is large enoughdepending onA andk,we see that this is a Freimanisomorphism(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 (andindeed,anyinequalityinvolvingafinitenumberofsumsanddifferenceswhich 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. Nowwelookatwhathappenswhenthereistorsion,e.g. ifZ =Z/NZforsomeN. 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.) | |≥ | | | | Nowlet’s look atwhathappens whenthere aren’tany propersubgroups,i.e. when Z =Z/pZ for some prime p. Theorem 2.5 (Cauchy-Davenportinequality). IfA,Bareanytwonon-emptysub- sets 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 6 TERENCE TAO inequality. Note that we need the p on the right-handside, since clearlywe 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 alwaysintersect 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 nowbeginthe firstproofofthe Cauchy-Davenportinequality,basedoncontra- diction. Suppose we have a counterexample to the inequality, so that A+B < | | A + B 1 pforsomeAandB. Let’sassumethecounterexampleisminimalin | | | |− ≤ 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. Nowwe doa little trick,knownasthe Dyson e-transform1: we replaceAandB 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 ∪ ⊆ ∪ ⊆ ∪ ). ThusA′,B′ willbeanothercounterexampletotheCauchy-Davenportinequality (we’vekept A + B 1thesamesize,butmadeA+B equalorsmallercardinality; | | | |− 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 in- equality, 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,thismeansthatB A+A B (sinceA+xintersectsB preciselywhen − ⊆ x B A). Thus B A+A B . ByExercise3thismeansthatB isatranslate ∈ − | − |≤| | 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. NowwegiveacompletelydifferentproofofCauchy-Davenport,duetoElon,Nathanson, and Ruzsa. Write m := A, n := B ; we may assume that m+n 1 < p. Write | | | | − F := Z/pZ, and consider the set FA, the set of F-valued functions on A. This is an m-dimensional vector space over the field F. Now consider the polynomi- als 1,x,x2,... ,xm−1, thought of as functions from A to F (i.e. elements of FA). These m functions are linearly independent (over F) in FA, because polynomials of degree m 1 have at most m 1 zeroes. Thus these functions form a basis for − − FA. Similarly the functions 1,y,y2,... ,ym−1 form a basis for FB. Now considerFA FB =FA×B, the space ofF-valuedfunctions f(x,y)for x A ⊗ ∈ and y B. Then the functions xjyk, for 0 j m 1 and 0 k n 1, form ∈ ≤ ≤ − ≤ ≤ − a basis for FA×B. In particular, if we let S be the mn 1 monomials xjyk :0 − { ≤ j m 1,0 k n 1,(j,k) = (m 1,n 1) , then xm−1yn−1 does not lie in ≤ − ≤ ≤ − 6 − − } 1Actually,thisistheDyson0-transform. Thee-transformisthe0-transformcomposedwitha translationbye. LECTURE NOTES 1 7 the span of S (over F). On the other hand, observe that xjyk does lie in the span of S if 0 j < m 1 (because yk is a linear combination of 1,y,... ,yn−1) or if ≤ − 0 k <n 1 (because xj is a linear combination of 1,x,... ,xm−1). ≤ − Now suppose that the Cauchy-Davenportinequality 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 FA×B by ⊆ ∈ f(x,y):= (x+y z) − zY∈C thenf vanishesonA B,i.e. f 0. However,ifweexpandf(x,y)outcompletely, × ≡ we get a monomial term of the form m+n 2 − xm−1yn−1, (cid:18) m 1 (cid:19) − plusalotofothermonomialtermsinvolvexjyk whereeitherj <m 1ork <n 1 − − or both, and which thus lie in the span of S. But since m 1 < p, we see that n − m+n 2 − is nota multiple ofp, andso it is invertible inF. This contradicts (cid:18) m 1 (cid:19) − the fact that xm−1yn−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-Davenportinequality is equivalent to the more symmetrical: Proposition 2.6. LetA,B,C benon-emptysubsetsofF suchthat 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. − \ WewillusetheFouriertransform. Letl2(F)bethevectorspaceofcomplex-valued functionsonF. Givenanyf l2(F),wecandefinetheFouriertransformfˆ l2(F) ∈ ∈ by 1 fˆ(ξ):= e2πixξ/pf(x). √p xX∈F This is an isometry from l2(F) to l2(F). Now look at the subspace l2(A) of l2(F); this is the A-dimensional space of complex-valued functions on A. The Fourier [| | transforml2(A) ofthisspaceisthus also A dimensional. Heuristically,this means | | thatgivenany A distinctfrequenciesξ ,... ,ξ ,weshouldbeabletofindafunc- 1 |A| | | tion f l2(A) whose Fourier coefficients fˆ(ξ ),... ,fˆ(ξ ) are equal to anything 1 |A| ∈ we specify. (This is true if the characters e2π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 canfindfunctions f,g,hinl2(A), l2(B), l2(C) suchthat f hasa non- zero Fourier coefficient at 0 but zero coefficients on X, and similarly for g, h and 8 TERENCE TAO Y, Z. ButbyParseval,this implies thatthe Fouriercoefficientsoff g harezero ∗ ∗ everywhereexceptat0 where it is non-zero;this implies that f g his a non-zero ∗ ∗ constant. Since f g h is supported on A+B+C, the claim follows. ∗ ∗ UnfortunatelyIhaven’tbeenabletoprovethelinearindependenceofthecharacters necessary to make this proof work (even though one has a vast amount of freedom inselecting the setsX,Y,Z), howeveritdoesshowhowthe Fouriertransformcan (in principle) be used to control additive information of sets. 3. On A and A+B Nowlet’sgobacktoageneralabeliangroupZ,andsupposethatwehavetwofinite 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-invariantsets 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 | | ∼ | | foressentiallyB-invariantsets-thattheyareessentiallycosetsofagroupgenerated 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. Firstofall,supposethatAandA′ aretwogenuinelyB-invariantsets. ThenAand A′ are unions of cosets of the same sub-group G. This gives us some additional informationonthesumsetA+A′. Firstofall,itmustalsobeunionsofcosetsofG, 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 essentiallyB-invariantsetsinsteadofgenuinelyB-invariantsets. Onecanpartially answer this question by means of the following elementary lemma of Imre Ruzsa. Lemma 3.1. [4]If U, V, W are threenon-empty finitesubsets of an abelian group Z, then V W |U+V||U+W|. | − |≤ |U| LECTURE NOTES 1 9 Note that this is a generalization of the trivial bound V W V W . In the | − | ≤ | || | specialcasewhereU isasubgroup,thisboundinfactcomesfromthetrivialbound applied to the abelian group Z/U, and then pulled back to Z. (In that particular caseonecanimprovetheleft-handsideto U+V W ,andmoregenerallyonecan | − | do so when U is essentially closed under addition, see Q10. However for general U onecannothopeforsuchanestimate,seeQ9). Onecanthinkofthislemmaassort of a triangle inequality: if one can control the arithmetic interaction between U andV,andbetweenU andW,thenonecanalsocontrolthe arithmeticinteraction between V and W. Proof Considerthelinearmapπ :V W V W definedbyπ(x,y):=x y. This × → − − map is clearly surjective, and so we can find a partial inversef :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 diagonalU∆ := (u,u):u U . Observe that (V W)+ ∈ × { ∈ } × U∆ =(U+V) (U+W). Inparticular,foranyw V W,thesetsf(w)+U∆ lie × ∈ − in(U+V) (U+W). Furthermore,since U∆ isin the nullspace ofπ, we seethat × 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(orpartialinverse)f toaninjectivefunctionπ,whichisthenusedtoobtain a certain disjointness property. We will meet this trick again later in this course. Fromthis lemma we see that if A and A′ are two essentially B-invariantsets, then A+B A′+B A A′ A A′ | || | . | || | | − |≤ B B | | | | which is consistent with our previous discussion. Or if A is both essentially B- invariant and B′-invariant, then A+B A+B′ B 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 genuinelyB-invariantsets isthatifAis essentiallyB-invariant,thenitshouldalso be essentially B+B-invariant,essentially B B-invariant, essentially B+B+B- − invariant, etc. We will prove something like this in the next three sections. 10 TERENCE TAO 4. Plu¨nnecke’s theorem The purpose of this section is to prove Theorem 4.1 (Plu¨nnecke’s theorem). [3]LetA,B betwofinitenon-emptysubsets ofanabeliangroupZ,andsupposethat A+B K A forsomerealnumberK 1. | |≤ | | ≥ Then there is some non-empty subset A′ of A such that A′+B+B K2 A′ . | |≤ | | Inparticular,everyessentiallyB-invariantsetcontainsanessentiallyB+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” cardinalitybyK,thenthepassagefromAtoA+B+B shouldmagnifycardinality by at most K2. In order to quantify this notion of magnification, we shall need some machinery from graph theory. Set V := A, V := A+B, V := A+B +B. We can define a directed graph 0 1 2 G = G[A,B] connecting V to V and V to V as follows: for every a A and 0 1 1 2 ∈ b B, we connect a V to a+b V ; we let E be the set of all such edges. 0 1 0→1 ∈ ∈ ∈ For every a+b A+B and c B, we connect a+b V to a+b+c V . 1 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 Plu¨nnecke graph)ofdepth2isagraphGwiththree(possiblyoverlapping)finitesetsofvertices V ,V ,V Z, and two sets of directed edges E , E , such that each edge e 0 1 2 0→1 1→2 ⊂ inE connectsV toV ,andeachedgeinE connectsV toV . Furthermore, 0→1 0 1 1→2 1 2 we have the following commuting square property: if the edge a a+b lies in → E , and the edge a+b a+b+c lies in E , then the edge a a+c must 0→1 1→2 → → also lie in E , and the edge a+c a+b+c must also lie in E . 0→1 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. 7→ 7→ 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 induces a pushforward map from 1→2 → → 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 to V must 0 1 somehow be similar to that from V to V . 1 2 We do allow V , V , V to overlap,but this can be easily fixed by replacing Z with 0 1 2 the productspaceZ Z,andreplacingV ,V ,V bytheir respectivelifts V 0 , 0 1 2 0 × ×{ } V 1 , V 2 , and adjusting the edges accordingly. Thus we will take V , 1 2 0 ×{ } ×{ } V , V to be disjoint. (Note how the freedom to take Cartesian products of our 1 2