Additive Combinatorics – Cheap Research Essays

Additive Combinatorics
Recall that |[n] + [n]| = |[n] – [n]|, where [n] := {1, 2, . . . , n}. Is it always the case that A + A = A – A? We came up with the counterexample A = {1, 2, 4}, where |A + A| = 6 but |A – A| = 7. In this case the di?erence set is larger than the sumset. What about in reverse? Does there exist A ? Z for which |A – A| < |A + A|? Some playing around led to no such examples, and one might be tempted to conjecture that |A + A| = |A – A| for all ?nite sets A ? Z. We even came up with a heuristic argument for why this might be the case: addition is commutative, while subtraction is not, so where A + A automatically has many coincidences which A – A does not. Unfortunately, this argument is not rigorous. In fact, one can make an equally convincing argument in reverse: in A – A there are many ways to make 0, so there are automatically many coincidences in A – A. This is exactly what happens for the set A = {0, 2, 3, 4, 7, 11, 12, 14} (due to John Conway): we have |A + A| = 26 but |A – A| = 25. Nonetheless, empirically, sets for which the sumset is larger than the di?erence set are rare. This led us to the following questions (some of which may be open): 1. Find the smallest set A such that |A + A| > |A – A|. 2. Is it true that for “most” A ? Z we have |A + A| = |A – A|? 3. Are there in?nitely many fundamentally di?erent A ? Z such that |A + A| > |A – A|? 4. Classify all A ? Z such that |A + A| > |A – A|. 5. Is it true that for any A ? Z we have |A – A| – |A + A| * * * * * 1? [Update: The answer is NO!]

READ ALSO : Unit 2 paper .

We went back to discussing the general case of Abelian groups. For the remainder of the lecture we take (G, +) to be an abelian group and A, B, C, X, Y, Z to be ?nite subsets of G. Recall that the doubling constant of A is de?ned to be |A + A| / |A|. Some people use the same name for |A – A| / |A|. This is unfortunate, since (as we saw above) the relationship between these two quantities is mysterious. Nonetheless, it turns out that there is a relationship between them: Proposition 1.
|A-A| |A |

|A+A| | A|

for all ?nite A ? G.

We will deduce this from a more general relation: |B – C | |A + B | |A + C | = . |A| |A|2 Written in this form, the inequality looks a lot less natural than the one in the Proposition. After a bit of playing around, we realized there was a more symmetric way of writing the general inequality. 1

Theorem 1 (Ruzsa’s triangle inequality). For all ?nite sets X, Y, Z ? G we have |X – Z | |X | |Z | = |X – Y | |X | |Y | · |Y – Z | |Y | |Z | .

Although this does look a bit reminiscent of a triangle inequality, the name of the theorem may strike you as strange. We quickly realized that taking logarithms makes this a legitimate triangle inequality. More precisely: De?nition (Ruzsa Distance). For any A, B ? G we de?ne d(A, B ) := log |A – B | |A| |B | .

Exercise 1. Prove that d(·, ·) satis?es the following properties of a metric: 1. Non-negativity. d(A, B ) = 0. 2. Symmetry. d(A, B ) = d(B, A). 3. Triangle Inequality. d(A, B ) = d(A, C ) + d(C, B ). [We did this collaboratively in class. In case you missed it, here’s a hint: a good way to prove |X | = |Y | is ?nd an injection mapping X ? Y .] 4. Why isn’t the Ruzsa distance a metric? Just to illustrate the utility of the triangle inequality, we give a short proof of Proposition 1. We have | A – A| = ed(A,A) = ed(A,-A)+d(-A,A) = ed(A,-A) |A|
2

|A + A| |A|

Note that an immediate corollary of Proposition 1 is that if |A + A| = K |A|, then |A – A| = K 2 |A|. It turns out that this can be generalized: Theorem 2 (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 kA = A + A + · · · + A.
k times

The original proof of this theorem was long and complicated, using deep results from graph theory. Several years ago, Giorgis Petridis (then a PhD student of Gowers) discovered a simple and elegant combinatorial proof which we give below. Proof of Pl¨ unnecke-Ruzsa. Pick the nonempty set X ? A which minimizes the quotient |A + X | = K0 . |X | In particular, note that K0 = K . Petridis observed that this X enjoys the following remarkable property. Lemma. For all B ? G, we have |A + B + X | = K0 |B + X |. We will prove this lemma next class. For the moment, we deduce Pl¨ unnecke-Ruzsa from it. We have |mA| = |mA + X | = |A + (m – 1)A + X |
m-1 = K0 |(m – 1)A + X | = · · · = K0 |A + X | m = K0 |X | . |A + X | |X | ;

say,

Thus, if n = 0, we are done. Otherwise we use the same technique to deduce
n |nA| = K0 |X | .

Now, we wish to ?nd an upper bound on |mA – nA|. This suggests using the Ruzsa triangle inequality to bound d(mA, nA) = d(mA, ·) + d(·, nA). What can we put in place of ·? Examining our above bounds, we see that we not only bounded |mA|, we also bounded |mA + X |. In other words, we know something about the distance from mA to -X ! Taking this hint, we consider Ruzsa’s triangle inequality: d(mA, nA) = d(mA, -X ) + d(-X, nA). Expanding and simplifying yields |mA – nA| =
n |X | K m |X | · K 0 |mA + X | · |nA + X | m+n = 0 = K0 |X | = K m+n |A|. |X | |X |