Additive Combinatorics
Today we are going to complete the proof of Solymosi’s theorem. While the theorem is valid over C, we shall only prove it over R>0 . For ease of reference: Theorem (Solymosi, 2009). For all A, B ? R>0 , |A · B | · |A + B | · |B + B | |A|2 |B |2 . log(|A| |B |)
Last time we de?ned the notation rA?B (x) and noted the ?rst key insight in the proof: rA·B (x)2 =
x?A·B m?B ÷A
rB ÷A (m)2 .
(1)
We then established the following lower bound using Cauchy-Schwarz: rA·B (x)2 =
x?A·B
|A|2 |B |2 . |A · B |
(2)
It therefore su?ces to prove that rB ÷A (m)2
m?B ÷A
|A + A| · |B + B | · log(|A|).
(3)
The signi?cance of the identity (1) is that it admits a geometric interpretation: rB ÷A (m) enumerates the number of (A × B )-lattice points on the line Lm through the origin with slope m. In the example below A, B are sets of positive real numbers having 5 elements each. The lattice A × B is illustrated as well as the line L2 going through the point (a1 , b2 ). Since L2 only contains a single lattice point, we see that rB ÷A (2) = 1. B b5 b4 b3 b2 b1
a1 a2
a3 a4 a5
A
1
Proof of Solymosi’s Theorem Continued. Recall that we wish to prove the upper bound (3). For aesthetic reasons, set r(m) := rB÷A (m) for the remainder of the proof. One di?culty in analyzing the sum (3) is that r(m) varies drastically from one line to the next. To remedy this, we employ a simple but e?ective trick: divide and conquer. We partition the sum into pieces in such a way that within each piece, r(m) doesn’t vary too much: r(m)2 =
m?B ÷A j m?B ÷A 2j -1 <r(m)=2j
r(m)2
(4)
Suppose the inner sum on the RHS of (4) is maximized at j = J . Exercise 1. Carefully prove that r(m)2
m?B ÷A
log(|A|)
m?B ÷A 2J -1 <r(m)=2J
r(m)2
(5)
Let M := m ? B ÷ A : 2J -1 < r(m) = 2J . To conclude the proof of Solymosi’s theorem, it su?ces to show that r(m)2 |A + A| · |B + B | .
m?M
Observe that for any m, m ? M we have r(m) = 2r(m ); by symmetry of m and m , we deduce that r(m) r(m ). Now, M is a ?nite set of positive numbers; enumerate its elements M = {m1 , m2 , . . . , mn }, where mi < mi+1 for all i. We have r(m)2
i= n i=n
r(mi ) · r(mi+1 ).
(6)
Recall that r(m) has a geometric interpretation: it is the number of lattice points on the line Lm . Abusing notation, we take Lm to be the set of lattice points lying on the line, i.e. Lm := {(x, y ) ? A × B : y = mx}. Solymosi’s second key insight concerns the geometry of the sumset Lmi + Lmi+1 . Exercise 2. Show that: (a) Any point in Lmi + Lmi+1 lies in between the lines Lmi and Lmi+1 . Conclude that if i = j then (Lmi + Lmi+1 ) n (Lmj + Lmj +1 ) = Ø. (b) For all p ? Lm + Lm , we have rLm +L (p) = 1.
m
(c) Conclude that |Lm + Lm | = |Lm | · |Lm |. Applying the above exercise to (6), we have (“ ” denotes disjoint union) |Lmi |2
i=n i= n
|Lmi | Lmi+1 =
i=n
Lmi + Lmi+1
=
(Lmi + Lmi+1 ) = |A × B + A × B | = |A + A| · |B + B | .
i= n
2
Exercise 3. Justify the inequality step (“=”) in the calculation above. Can you come up with an example of A and B where it’s a tight bound? What about where it’s a poor bound? Exercise 4. Above, we were a bit sloppy with the ‘extra’ term Lmn+1 . Fix the proof to account for this. [One way to do this is to de?ne Lmn+1 to be {0} × B . But there are other ways as well.] * * * * *
If you re?ect back to our ?rst lecture you’d realize that we were focusing on sets of integers; consider Erd? os-Szemer´ edi Conjecture for example. It turns out, however, that a more natural setting for the type of questions we’ve been asking are arbitrary ?elds and abelian groups. For instance, let (G, +) be an abelian group. Let A ? G be ?nite. How big is |A + A|? We have the trivial bounds |A| = |A + A| = 1 2 |A| (|A| + 1). When is the lower bound tight? In class we interactively came up with the following: Proposition. Given an abelian group (G, +) and a ?nite subset A ? G, we have |A + A| = |A| i? A is a coset of a subgroup of G. Exercise 5. Prove the above proposition. Exercise 6. Let (G, +) be an abelian group, and let A ? G be ?nite. Prove that |A – A| = |A| i? A is a coset of a subgroup of G. Note that cosets of subgroups of Z are precisely arithmetic progressions. Thus the proposition above gives some intuition for the Freiman-Rusza theorem. More generally, suppose that |A + A| = K |A| for some constant K (called the “doubling constant” of A). What can we say about A now? If K isn’t too big, then A should hopefully “look like” a coset. Until very recently, no one new how to think cohesively about additive combinatorics. Ben Green (one of the pioneers in the ?eld) commented on this in a 2009 paper. However, a current viewpoint on the ?eld is the following: Additive Combinatorics is the study of approximate algebraic structures. For example, one can characterize cosets of subgroups by the condition that they satisfy |A + A| = |A|. What happens when one weakens this to |A + A| = K |A|? Then A becomes a coset of an approximate subgroup. * * * * *
In the ?nal part of the lecture, we considered a lovely result due to Izabella Laba (who, like Solymosi, is a professor at UBC). Theorem (Laba, 2001). Let G be an abelian group. If A ? G is a ?nite subset such that |A – A| < then A – A is a subgroup of G. Exercise 7. Show (by example) that the doubling constant Next, we outlined a proof of this result. Exercise 8. Show that: 1. ?x ? A – A , |A n (A + x)| >
1 2 3 2 3 2
|A|,
in Laba’s Theorem is tight.
|A|. Conclude that (A + x) n (A + y ) = Ø for any x, y ? A – A.
2. Show that A – A is closed under di?erences. Conclude that it is a subgroup of G.
PLACE THIS ORDER OR A SIMILAR ORDER WITH US TODAY AND GET AN AMAZING DISCOUNT 🙂