Additive Combinatorics
In this lecture we will ?nally begin the proof of the Freiman-Ruzsa Theorem, bringing together many of the techniques we’ve learned in past lectures. Before we begin, recall that for a ?nite A ? Z we have |A + A| = 2 |A| – 1, with equality i? A is an arithmetic progression. If A + A is slightly larger – say, |A + A| = 4|A| – it’s tempting to guess that A still looks roughly like an AP. To state this precisely, we need the notion of a generalized arithmetic progression. De?nition. A set P ? Z is called a generalized arithmetic progression (or gAP) if it is of the form P = {x0 + j1 x1 + j2 x2 + · · · + jd xd : 0 = jk < mk ?k }, where x0 ? Z and xi ? Z \ {0} for all 1 = i = d. The minimal number d for which P can be written as above is called the dimension of P , denoted dim P . The case dim P = 1 corresponds to P being an arithmetic progression. Note that |P | = m1 m2 . . . md . If equality holds, then P is called a proper gAP. Exercise 1. Let P be some gAP. (a) Prove that dim(P + P ) = dim P . (b) Give an example where equality fails to hold. (c) Prove that |P + P | = 2d |P |. Exercise 2. Let A ? Z be ?nite. How can you embed A in a gAP P (that is, A ? P ), such that |P | is comparable to |A|? Calculate a few representative examples, trying to keep the dimension of P small. Theorem (Freiman-Ruzsa). Let A ? Z be a ?nite set with |A + A| = K |A|. Then there exists a gAP P ? Z such that • P ? A; • |P | • dim P
K
|A|;
K
1.
Thus, any set of small doubling “looks like” an arithmetic progression (recall that the smaller the dimension, the more the gAP looks like a bona ?de AP). Before we move on to the proof of this theorem, let us mention some recent developments. The theorem was originally proved by Freiman in 1962, but it wasn’t until Ruzsa signi?cantly simpli?ed the proof in 1994 that it began attracting widespread attention. In 2007, Green and Ruzsa generalized the theorem to arbitrary abelian groups. Even though a gAP is a perfectly well-de?ned object in an arbitrary abelian group, it is not quite the right notion to use when generalizing Freiman-Ruzsa; instead, one embeds sets of small doubling into a coset progression, i.e. a set of the form H + P where H is a subgroup and P is a gAP. In 2012, Breuillard, Green, and Tao generalized the theorem further, to arbitrary (non-abelian) groups. The correct generalization of gAP in that setting is quite complicated. The starting point in Ruzsa’s proof of Freiman-Ruzsa is to translate the original problem to an easier one. By adding and subtracting more and more copies of A, one obtains a much ‘smoother’ set with more and more additive structure. Ruzsa observed that it su?ces to ?nd a large gAP in mA – nA. 1
Claim 1. Suppose we ?nd ?xed non-negative integers m and n such that mA – nA contains a proper gAP P satisfying |P | K |A| and dim P K 1. Then there exists a gAP Q such that A ? Q, |Q| m,n,K |A|, and dim Q m,n,K 1. Proof. We may assume that |P | |A|, for otherwise replace P by another gAP, P , with this property; where P is obtained from P by simply “trimming” P appropriately. Similarly to Ruzsa’s theorem (Lecture 7), pick the maximal X ? A with the property that the sets P + {x} are pairwise disjoint as x runs over all x ? X . By Pl¨ unnecke-Ruzsa we have |X | = |P + X | |P |
m,n,K
|A| = 1. |A|
Observe that A ? X + P – P . By Exercise 1 above we have |P – P | = 2dim(P -P ) |P | = 2dim P |P | |P | |A| .
Let Q be the smallest gAP containing X + P – P . Note that P – P is already a gAP, and even if we treat each element of X as a new generator, we obtain a gAP Q as in the claim. Exercise 3. Carefully make precise the last sentence.
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT 🙂