Additive Combinatorics

Additive Combinatorics
Last lecture we discussed the relation between the ratios |A + A| / |A| and |A – A| / |A|, which are both sometimes called the “doubling constant” of A. We arrived at the following result: Theorem 1 (Pl¨ unnecke-Ruzsa). Let A ? G with |A + A| = K |A|. Then for all nonnegative integers m, n we have |mA – nA| = K m+n |A| where mA = A + A + · · · + A.
m times

This is proved in the Lecture 6, except for a key lemma which we prove now. (In fact, this is precisely the proof we came up with collaboratively last lecture, just tidied up a bit.) Lemma (Petridis). Suppose A ? G is a set such that |A + A| = K |A|. Choose Ø = X ? A such that the ratio |A + X | / |X | is minimized, and denote this ratio by K0 . Then for all B ? G we have |A + B + X | = K0 |B + X | . Before proving this, we quickly work out the trivial upper bound (to see what we’re trying to beat). Fix an enumeration B = {b1 , b2 , . . . , b }. Then B+X =
i

{bi } + X ,

whence |A + B + X | =
i

A + {bi } + X =
i

A+X =
i

K0 |X | = K0 |B | |X |.

This is much weaker than what we’re trying to prove (and is too weak to work in the proof of Pl¨ unneckeRuzsa). Note that in the above estimates, only one involves an inequality! This tells us what the problem is: the sets A + {bi } + X potentially have a lot of overlap we’re ignoring. In the proof below, we’ll get around this in two steps. First, we construct sets Xi which approximate {bi } + X , but which are disjoint. Next, when considering the set A + B + X , we try to remove any new overlap in the sets A + Xi . Proof. Fix an enumeration B = {b1 , b2 , . . . , b }. De?ne the following sets recursively X1 = {b1 } + X, X2 = ({b2 } + X ) \ X1 . . .
j -1

Xj = ({bj } + X ) \
i=1

Xi .

(Here

denotes the disjoint union.) These sets clearly form a partition of B + X , i.e. B+X =
i=1

Xi .

1

This implies A+B+X = (A + Xi ),
i=1

but the sets A + Xi have too much overlap for the above to be useful. However, we can do better: A+B+X =
i=1

(A + Xi ) \ (A + Yi ) ,

(1)

where Yi = ({bi } + X ) \ Xi . To see this, we start by observing the following. Exercise 1. If y ? Yi for some i = 2, then y ? Xj for some j < i. Exercise 2. Prove that A+B+X ?
i=1

(A + Xi ) \ (A + Yi ) ,

[Hint: Given s ? A + B + X , consider the least m such that s ? A + Xm .] Since Xi n Yi = Ø, it is unlikely that A + Yi is entirely contained in A + Xi . This makes it di?cult to appreciate how much of the overlap we’re removing in (1). However, observe that A+B+X ?
i=1

(A + Xi ) \ (A + Yi ) ?
i=1

(A + {bi } + X ) \ (A + Yi ) ,

and now we have A + Yi ? A + {bi } + X . This tells us that |A + B + X | =
i

|A + {bi } + X | – |A + Yi | |A + X | – |A + Yi – {bi }|
i

=

Now on the one hand, Yi – {bi } ? X , so by de?nition of K0 we have |A + (Yi – {bi })| = K0 |Yi – {bi }|. On the other hand, |A + X | = K0 |X |. We deduce that |A + B + X | = K0
i

|X | – |Yi – {bi }| |X + {bi }| – |Yi |
i

= K0 = K0
i

|Xi |

= K0 |B + X |. Exercise 3. Modify the above proof to prove the following generalization: Suppose that A and A are ?nite subsets of an abelian group (G, +), with |A| = |A |. If |A + A | = K |A|, then |mA – nA| = K m+n |A|. (Note: in practice, A is usually taken to be A or -A.) * * * * *

As mentioned, Pl¨ unnecke-Ruzsa will play a key role in the proof of the Frieman-Ruzsa Theorem. As a warm-up to Freiman-Ruzsa, we ?rst prove a beautiful result due to Ruzsa: we show that in any abelian group of bounded torsion, the only sets of small doubling are essentially subgroups. More precisely:

2

Theorem 2 (Ruzsa). Suppose (G, +) is an abelian group with exponent* r, and A ? G has small doubling, say, |A + A| = K |A|. Then there exists a subgroup H = G such that H?A and |H |
r,K

|A| .

Remark. Recall that the subscripts on the indicate that the implicit constant is allowed to depend on r and K , but on nothing else. In particular, the constant does not depend on |A| at all. Thus, the result asserts that if A has small doubling, then it’s possible to tack a few elements onto A to make it into a subgroup. (Note that one can make any set into a subgroup by adding elements to it; the point of this theorem is that one doesn’t have to add many element to do so, so long as the set has small doubling.) Before proceeding to the formal proof, let me sketch the strategy. Recall that A denotes the subgroup of G generated by A (i.e. the smallest subgroup of G containing A). Given A, how does one actually generate A ? By adding and subtracting elements of A from each other until you stop getting new elements. In other words, A = mA – nA .
m,n=0

In particular, A – A ? A , but as you can see from above, |A – A| is typically much smaller than A . It is therefore somewhat surprising that we can approximate a reverse inclusion: we will construct a small set X such that A ? (A – A) + X . Because X is small and G has bounded torsion, | X | must itself be fairly small, whence | A | ˜ |A – A|. But if A has small doubling, then |A – A| ˜ |A|, so we deduce that | A | ˜ |A| as claimed. It is worth pointing out that all of this strongly uses the hypotheses of the theorem; for example, the fact that we can construct a small X depends on the assumption that A has small doubling. Proof. We shall prove the theorem for the special case where A is symmetric (i.e. A = -A); the proof of the general case is left as an exercise (see below). Choose X ? 3A to be maximal such that the sets A + {x} are pairwise disjoint over all x ? X . Exercise 4. Prove that 3A ? 2A + X . [Hint: Pick an arbitrary t ? 3A. Then A + {t} must intersect one of the sets A + {x} (why?). Conclude.] Adding A to both sides and simplifying, we ?nd 4A ? 3A + X ? 2A + 2X. Adding A to both sides of this inclusion and simplifying yields 5A ? 3A + 2X ? 2A + 3X. Continuing this process, we obtain nA ? 2A + (n – 2)X for any n = 3. Exercise 5. Prove that A =
n=3

(2)

nA.

Taking the union of the inclusions (2) over all n = 3, we deduce that A ? 2A + X . Exercise 6. Prove that | X | = r|X | . Deduce that | A | = Kr|X | |A|. To conclude the proof, it su?ces to show that |X | K,r 1, i.e. that the size of X does not depend on the size of A. (Note that this is a pretty fantastic claim, since X is de?ned in terms of A!) Since X ? 3A, it is tempting to applying Pl¨ unnecke-Ruzsa directly, but this only gives the bound |X | = K 3 |A|, which is much too weak for our purposes. The following exercise shows that we can do much better.
*

Recall that the exponent of a group is the smallest positive integer e such that g + g + · · · + g = 0 for any g ? G.
e

3

Exercise 7. Prove that |X | = K 4 . [Hint: Apply Pl¨ unnecke-Ruzsa to the set A + X .] Putting all the above together, we conclude that | A | = K rK |A|. This concludes the proof of Ruzsa’s theorem for symmetric A. For the general case, see the exercise below. Exercise 8. Prove the general case of the theorem (where A is not symmetric). [Hint: Let X ? 2A – A be maximal such that A + {x} are all disjoint.] Note that we did better than simply prove |H | optimal?
r,K
4

|A|; we’ve shown that |H | = KrK |A|. Is this bound

4

Conjecture 1 (Ruzsa). Ruzsa’s Theorem holds with |H | = rCK |A|, for some constant C . This conjecture is best-possible, as can be seen by the following simple example. Let p be some prime number and consider G = (Fn p , +). This is an abelian group with exponent r . Let U, V be two subgroups such that U n V = {0}. Let V = {v1 , . . . , v } be a set of linearly independent vectors from V . Take A := U × V , so 1 that |A| = |U |. Since A + A = U × {vi + vj : 1 = i = j = }, we have |A + A| = |U | · 2 ( + 1). Thus, | A + A| 1 = ( + 1). |A| 2 However, it is easy to see that A = U × span V = U × (Fp v1 + Fp v2 + · · · + Fp v ) so that | A | = |U | · p = Now, simply choose p |A| .

= 2K – 1. Since A is the smallest subgroup containing A, we must have H= p2K -1 |A| . 2K – 1

This shows that the bound in Ruzsa’s conjecture is in optimal form. In 2012, Lovett and Zohar showed that the conjecture holds for any prime exponent. We conclude by discussing an open question which has recently generated considerable interest. Conjecture 2 (Polynomial Freiman-Ruzsa). Let (G, +) be an abelian group with exponent r. Let A ? G. If |A + A| = K |A|, then there exists a constant Cr > 0 and a subset A ? A such that • |A | =
1 KC

|A|, and

• | A | = K C |A | . The way to think about this theorem is that A is simply A minus a small number of “throw-away” elements. As we’ve seen with our example above, if we restrict ourselves to A, the bound must be at least exponential in K . Polynomial Freiman-Ruzsa conjectures that if we allow ourselves to throw away some small number of elements from A, we can improve the bound to being polynomial in K . This conjecture, if true, would have signi?cant consequences (both within additive combinatorics and in applications to computer science).
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT 🙂

 

© 2020 customphdthesis.com. All Rights Reserved. | Disclaimer: for assistance purposes only. These custom papers should be used with proper reference.