Applications of Additive Combinatorics in Theoretical Computer Science
Explore Set Addition, Abelian Groups, Ruzsa Calculus, and the Ruzsa Distance in Chapter 2 of 'Additive Combinatorics and its Applications' by Shachar Lovett, with a focus on basic inequalities, triangle inequality proofs, and their implications in theoretical computer science.
Uploaded on | 1 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Additive Combinatorics and its Applications in Theoretical CS By Shachar Lovett Chapter 2: Set addition, Sections 2.1-2.3, pp. 3-8. Presented by Tomer Bincovich
Set addition ? an abelian group (think about ? = ??). ? ?. The sumset of ? is 2? = ? + ? = ? + ? ?,? ? Always 2? ? . When does equality hold?
When does 2? = |?|? Equality holds if ? is empty, a subgroup of ? or a coset of a subgroup. For the other direction: If ? , we can assume w.l.o.g. 0 ? by shifting. Then ? 2?, and since 2? = ? we have that 2? = ?. ? is a nonempty finite subset that is closed under addition, hence is a subgroup.
Planned topics Ruzsa calculus The span of sets of small doubling The growth of sets of small doubling
Ruzsa calculus A set of basic inequalities between sizes of sets and their sumsets. For ?,? ?, define: Sumset: ? + ? = ? + ? ? ?,? ? Difference set: ? ? = ? ? ? ?,? ? Claim 2.1 (Ruzsa triangle inequality): ? ? ? ? ? ? ?
Proof of Claim 2.1 Claim 2.1 (Ruzsa triangle inequality): ? ? ? ? ? ? ? Define a map ?:? ? ? ? ? ? ? : for any ? ? ? fix ? ?,? ? s.t. ? = ? ?, and define ? ?,? = ? ?,? ? . ? is injective, hence ? ? ? ? ? ? ? .
The Ruzsa distance ? ? 1 2? ? ?,? = log 1 2 ? Not formally a distance function. Why? Claim 2.3: The Ruzsa distance is symmetric and obeys the triangle inequality.
Proof of Claim 2.3 ? ? 1 2? ? ?,? = log 1 2 ? Symmetry: since ? ? = ? ? . Moreover, ? ?,? ? ?,? + ? ?,? is equivalent to ? ? ? 1 2? ? ? 1 2? ? ? 1 2? log 1 2 log 1 2+ log 1 2 ? ? ? ? 1 2? ? ? 1 2? ? ? 1 2? 1 2 1 2 1 2 ? ? ? ? ? ? ? ? ? ? Which follows from Claim 2.1.
Corollary 2.4 1 2? 1 2then ? ? ?2? . If ? ? ? ? For ? = ? we get that if ? + ? ? ? then ? ? ?2? .
Proof of Corollary 2.4 1 2? 1 2then ? ? ?2? . If ? ? ? ? 2 ? ? ? ? ? 1 2? = ?? ?,? ?? ?,? +? ?,?= ?2 1 2 ? ? ? 1 2? ? ?,? = log 1 2 ?
The span of sets of small doubling
The doubling constant ?+? ?. The doubling constant of ? is ? = We saw that ? = 1 corresponds to subgroups. Can we use ? to say something about the size of the smallest subgroup containing ?? (or, in the case of ? = ??, the size of the span of ?)
Lemma 2.5 (Laba) If ? ? <3 2? then ? ? is a subgroup. The constant 3/2 is tight: take ? = 0,1 . ? ? = 1,0,1 is not a subgroup.
Proof of Lemma 2.5 We will show that for any ? ? ?, ? ? + ? This implies that for any ?,? ? ?, ? + ? ? + ? : Denoting ??= ? ? + ? , by the inclusion exclusion principle > ? /2. ? + ? ? + ? ?? ?? = ??+ ?? ?? A? > ? /2 + ? /2 ? = 0 There are ?1,?2 ? s.t. ?1+ ? = ?2+ ?, thus ? ? = ?2 ?1 ? ?. ? ? is closed under taking difference, hence must be a subgroup.
Proof of Lemma 2.5 cont. We will show that for any ? ? ?, ? ? + ? Let ? = ? ? ? ?. Then ? ? + ? Similarly to before: ? ? ? ? = ? ? + ? ? > ? /2. ? ? ? ? . = ? ? ? ? ? + ? ? ? > |?|/2 As needed.
Lemma 2.6 (Freiman) Let ? ?with ? + ? ? ? . Then ? lies in an affine subspace of dimension at most 2? 1.
Proof of Lemma 2.6 We will prove that if ? has affine dimension ? then ? + 1 2 ? + ? ? + 1 ? ?+1 2 Thus ? + 1 ? ? + ? ? ? , and since ? ?, ? + 1 =? + 1 ? + 1 ? ? ? + 1 ? ? ? 2 2 Hence ? ?+1 2, or ? 2? 1.
Proof of Lemma 2.6 cont. We prove by induction on ? that if ? has affine dimension ? then ? + 1 2 ? + ? ? + 1 ? If ? = 1 then ? + ? = 1, ? = 0 and the claim follows. ?+? 2 ?,? ? . Assume ? > 1. Let ? ? = Clearly ? ? Let ?(?) be the convex hull of ?, which is a ?-dimensional polytope by assumption. Its vertices are the points in ? that cannot be obtained as a convex combination of the other points. = ? + ? .
Inductive proof, case (1) Fix a vertex ? ? of ? ? , and let ? = ? ? . We have two cases: 1) The affine dimension of ? is ? 1. Then the mid-points ?+? ? ? are outside ?(? ). for all 2 ? 2 ? 2 ? + ? ? ? + ? ? ? ? = ? + 1 ? ? ? + 1 2 = ? + 1 ? ? ? + 1 2 ? + ? ? + 1 ?
Inductive proof, case (2) Fix a vertex ? ? of ? ? , and let ? = ? ? . We have two cases: 2) The affine dimension of ? is ?. Let ?1, ,??be the neighboring vertices to ? in ? ? (two vertices are neighbors if the segment connecting them is a one-dim. face of ? ? ). Note that ? ? since ? ? is ?-dim. The points ? and ? +?? 2 ? + 1 + ? ? ? + 1 + ? + 1 ? for 1 ? ? are mid-points outside ? ? . ? + 1 2 ? ? ? + 1 2 = ? + 1 ? ? ? + 1 2 ? + ? ? + 1 ?
Lemma 2.6 tightness Let ? ?with ? + ? ? ? . Then ? lies in an affine subspace of dimension at most 2? 1. The dimension is tight up to lower order terms. Take ? = ?1, ,?2? a set of linearly independent vectors, then ? + ? = = ?(2? + 1) and ?+? ? 2? 2 + 2? = ? +1 2.
Theorem 2.7 (Ruzsa) Let ? be an Abelian group of torsion ?, ? ? with ? + ? ? ? . Then there exists a subgroup ? < ?, ? ?2??4? s.t. ? ?. A group has torsion ? 1 if ? ? = 0 for all ? ?.
Example ?has torsion ? = ?. Let ?,? ?? ?two subspaces with ? = ?? ? ? = 0 , and set ? = ? + {?1, ,?2?} where ?1, ,?2? ? are linearly independent. ? = ? 2?. Since ? + ? = ? + ??+ ??1 ? ? 2? , ? + ? = ? ? 2? + 1 and ?+? ? However, the size of the minimal subspace containing ? is ?2?? =?2? = ? +1 2 ?. ? 2? Thus an exponential dependency on ? is unavoidable.
Conjecture 2.8 (Ruzsa) There exists an absolute constant ? 2 s.t. for any Abelian group ? of torsion ?, and any ? ? with ? + ? ?|?|, the subgroup generated by ? has order ???? . Was established with ? = 2 for ? = 2 and then extended for prime ?: Theorem 2.9: Let ? be a prime, ? ?? subspace ? ?? ?with ? + ? ? ? . Then there exists a ?2? 2? 1? . ?s.t. ? ? and ?
Theorem 2.10 If 2? ? ? then 2? 2? ?4? . Used to prove Theorem 2.7. We will prove a more general result later today.
Proof of Theorem 2.7 - Sketch Let ? ? with 2? ? ? . We can assume 0 ? by possibly replacing ? with ? ? for some ? ?. Let ? = ?1, ,?? 2? ? be a maximal collection of elements s.t. ?? ? are all disjoint ( Ruzsa covering ). ? has small doubling, thus Theorem 2.10 implies that ? is bounded. We will show that ? ? 1 ? + ? ? for all 1. Together the theorem follows.
Proof of Theorem 2.7 cont. Since ?? ? 2? 2?, 2? 2? ? ?4 ? Therefore ? ?4. 2? ? ? 2? 2? ?4?
? ? 1 ? + ? ? = 1 is trivial. For = 2, we need to show 2? ? ? + ? ?. Take ? 2? ?, by construction there exists ? ? s.t. ? ? ? ? , i.e. ? ? = ? ? for some ?,? ?. Hence ? = ? + ? ? ? + ? ?. By induction on , ? ? = ? + 1 ? ? ? + 2 ? + ? ? 2 ? + ? + ? ? = 1 ? + ? ?
Concluding the proof ? ? 1 ? + ? ? Let ? be the subgroup spanned by ?, and similarly for ?. ? = ? ? ? 1 ? + ? ? = ? + ? ? 1 1 1 Hence, using Corollary 2.4 (which implies ? ? ?2? ), ? ? ? ? We conclude by bounding ? . As ? has torsion ? and we saw that ? ?4we have ? ??4. Finally, ? ?2??4? . ?2? ?
The growth of sets of small doubling
Iterated sumsets ? = ?1+ + ? ?1, ,? ? ? ?? = ?1+ + ? ? +1 ? +??1, ,? +? ? Theorem 2.11 (Pl nneke-Ruzsa): If ? = ? and ? + ? ? ? then ? ?? ? +?? . For ? = ? or ? = ? we obtain the following: Corollary 2.12: If ? + ? ? ? or ? ? ? ? then ? ?? ? +?? .
Lemma 2.13 Let ?,? ? with ? = ? and ? + ? ? ? . Let ?0 ? a nonempty set minimizing the ratio ?0= ? + ?0+ ? ?0?0+ ? ?+?0 ?0 . Then for any ? ?, Notice that ?0 ?.
Proof of Theorem 2.11 Let ?0 ? as in Lemma 2.13. We will prove by induction on that ?0+ ? ?0 = 0 is easy: ?0+ 0? = 1 ?0. For > 0: ?0+ ? = ? + ?0+ ( 1)? ?0?0+ 1 ? ?0 ?0 By the Ruzsa triangle inequality (Claim 2.1), applied to ?0, ?,??: ?0 ? ?? ?0+ ? ?0+ ?? ? +??0 Hence ? ?? ? +??0 ? +?? ? ? + ?0+ ? ?0?0+ ? ?0 ? ?0 . 1?0 = ?0 ?0 2 ? ? ? ? ? ? ?
Lemma 2.13 (Reminder) Let ?,? ? with ? = ? and ? + ? ? ? . Let ?0 ? a nonempty set minimizing the ratio ?0= ? + ?0+ ? ?0?0+ ? ?+?0 ?0 . Then for any ? ?,
Proof of Lemma 2.13 Observe that by minimality of ?0, for any ? ? we have that ? + ? ?0? . The proof is by induction on ? . If ? = ? , ? + ?0+ ? = ? + ?0 = ?0?0 = ?0?0+ ? If ? > 1, write ? = ? ? . Define ? ?0as ? = ? ?0? + ? + ? ? + ?0+ ? . We can write ? + ?0+ ? = ? + ?0+ ? ? + ?0+ ? ? + ? + ?
Proof of Lemma 2.13 cont. ? + ?0+ ? = ? + ?0+ ? ? + ?0+ ? ? + ? + ? ? + ?0+ ? ? + ?0+ ? + = ? + ?0+ ? + ? + ?0+ ? ? + ? + ? ?0?0+ ? + ? + ?0 ? + ? ?0?0+ ? + ?0?0 ?0? = ?0 ?0+ ? + ?0 ? ? + ?0+ ? ? + ? + ? ? ? ? + ? ?0? It remains to show that: ?0+ ? + ?0 ? ?0+ ?
Concluding the proof ? = ? ?0? + ? + ? ? + ?0+ ? It remains to show that: ?0+ ? + ?0 ? ?0+ ? Define ? = ? ?0? + ? ?0+ ? . Note that ? ? . We decompose ?0+ ? as a disjoint union: ?0+ ? = ?0+ ? Thus ?0+ ? = ?0+ ? + ?0 ? ?0+ ? + ?0 ? Which is what we needed to show. ?0+ ? ? + ?
