Statistical Set Addition and Polynomial Freiman-Rusza Conjecture
Explore the concepts of Statistical Set Addition and the Polynomial Freiman-Rusza Conjecture in additive combinatorics and their applications in theoretical computer science. The content discusses sets with small doubling, growth factors, subspace size bounds, the BSG theorem, polynomial Freiman-Rusza conjecture, and more.
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
Statistical Set Addition & The Polynomial Freiman-Rusza Conjecture Additive Combinatorics and its Applications in Theoretical CS Sections 2.4, 2.6 Shachar Lovett Presented by Guy Shalev
A Short Reminder We discussed sets ? ? with small doubling. We bounded the size of subspaces containing such ? Growth-factor was exponential in the doubling constant, ? For example, we saw that ? < ?, ? ?2???? s.t. ? ? We bounded the size of sets of the form ? ?? ? ?? ??+??
Todays sections (2.4) Statistical Set Addition The BSG theorem + lemma from graph theory. (2.6) Polynomial Freiman-Rusza conjecture An important conjecture explaining the structure of a set with small doubling. 5 equivalent conjectures over ?2 Versions for higher torsion groups ? 3
Statistical set addition Motivation (1) ? + ? is much larger than ? But many pairs ?1+ ?2lie in a small set (of size ?|?|) ?, take ? = ? ?1,?2 ,?2? , where ? is a For example: In ?2 subspace of dimension ?, and ??are random vectors. ? = 2?+1 ? + ? = ? ? + ?1,?2 ,?2? ? + ? 2?2 ?2 But for at least 1 + ??+ ?? 4of the pairs ?1,?2, we have ?1+ ?2 ? 4
Statistical set addition Motivation (2) ? = ? ?1,?2 ,?2? In this example, ? has large-doubling, but there is a large subset (? ?) with small-doubling. This is always the case.If a significant part of ? ? lands in a set of size ?|?|, then there is some large ? ? with small- doubling. Another point of view there is a simple explanation for such an ? The BSG theorem is a generalization of this idea 5
BSG Theorem BSG Theorem: by Balog, Szemeredi & Gowers 1. Let ?,? ?, s.t. ? = ? = ? 2. There exists ? ? s.t. ? = ??, and ? ?,? ?[? + ? ?] ? Pr ?2 16? Then there are subsets ? ?,? ? s.t. ? , ? And ? + ? 212?3 ?5? A a A+B By theorem 2.11, ? + ? , ? ? ???? ?,1 ? ? C a+b b B 6
The plan We will state a lemma in graph theory Easily prove BSG using the lemma Work hard to prove the lemma Take a break before the second part 7
Lemma (by Sudakov) The Lemma: 1. Let ? = (?,?,?) be a bipartite graph 2. ? = ? = ? , ? = ??2 As many as we could expect ?2 16? Then there are subsets ? ?,? ? s.t. ? , ? Such that for any ? ? ,? ? there are at least 2 12?5?2paths of length 3 from ? to ?. ? a b ? 8
Proof of BSG using the lemma (1/3) We have sets ?,?,? ? as given in the theorem. Build the natural bipartite graph ?: The vertex sets are ?,? ? = ?,? ? + ? ? ? = ??2 Obviously, the conditions of the lemma hold, so we get vertex sets ? ,? as stated, and we have many paths from any ? ? to ? ? 9
Proof of BSG using the lemma (2/3) For any ? ? ,? ? , and a specific path (?, ?, ?,?) we get ? = ? + ? = ? + ? ? + ? + ? + ? Denote ?1= ? + ? , ?2= ? + ? , ?3= ? + ? From the definition of ?, we know ?1,?2,?3 ? Any element ? ? + ? can be represented as ? = ?1 ?2+ ?3in at least 2 12?5?2ways. ? = ?? , so there are ??3triples ?1,?2,?3 ? 10
Proof of BSG using the lemma (3/3) Any element ? ? + ? can be represented as ? = ?1 ?2+ ?3in at least 2 12?5?2ways. There are ??3triples ?1,?2,?3 ? Splitting the triples between elements in ? + ? we get: 2 12?5?2=212?3 ?3?3 ? + ? ? ?5 11
Half way there! We will state a lemma in graph theory Easily prove BSG using the lemma Work hard to prove the lemma Take a break before the second part 12
High-level proof of lemma (1) a1 b1 b2 b3 b4 a1 b1 b2 b3 b4 a1 b1 b2 b3 b4 a a2 a3 a4 a5 a6 a a a2 a3 a4 a5 a6 a a a2 a3 a4 a5 a6 a a a a a a a b5 b6 Define good pairs such as (?1,?2) and bad pairs such as (?3,?4) Define a good neighbor for vertex ? ?: For a random ?, we prove it has many good neighbors Take specific ? with many good neighbors, and fix its good neighbors as ? Define ? as all ? s with many neighbors in ? Show there are many paths of length 3 from ? ? to ? ? ? ? forms few bad pairs inside ? 13
High-level proof of lemma a1 b1 b2 b3 b4 a1 b1 b2 b3 b4 a a2 a3 a4 a5 a6 a a a2 a3 a4 a5 a6 a a a a a Define good pairs such as (?1,?2) and bad pairs such as (?3,?4) Define a good neighbor for vertex ? ?: For a random ?, we prove it has many good neighbors Take specific ? with many good neighbors, and fix its good neighbors as ? Define ? as all ? s with many neighbors in ? Show there are many paths of length 3 from ? ? to ? ? ? ? forms few bad pairs inside ? 14
Proof of the lemma (1/6) ? a The Lemma: 1. Let ? = (?,?,?) be a bipartite graph 2. ? = ? = ? , ? = ??2 We want large subsets ? ,? s.t.for any ? ? ,? ? there are many paths of length 3 from ? to ?. b ? The average degree of a vertex is ??.We start by removing vertices from ? with degree smaller than ? We deleted less than ? 2? 2?2edges, left with at least ? 2?2edges 15
Proof of the lemma (2/6) Define a bad pair ?1,?2 ? if they have less than ?3 neighbors in ? For ? ?, let ??(?) denote the number of bad pairs which belong to ? For any bad pair ?1,?2 ?, by definition: 128? common ?3 128? ? ? ?1,?2 ? So after bucketing , averaging over the vertices yields: ?3 128? ? ? 2 ?3 256?2 ????(?) 16
Proof of the lemma (3/6) For ? ?, let ? ? be the neighbors ? ? which form a bad pair with at least ?2 neighbors ) Let ??(?) = | ?|. For any ? ? : ?2 32? 2 ??(?) (Counting the bad pairs using the bad neighbors. Each pair is counted at most twice) Taking expectation on both sides, ( ? = bad 32? other neighbors ? ? ??(?) ?3 64 ?2? 64 ? ????(?) ????(?) To conclude: we bounded the number of bad neighbors for an average ? ? ?2 = ? ?2? 256 ? 17
Proof of the lemma (4/6) So, for an average ? ?, ? ??) There are many neighbors (?????(?) ? ??) There are few bad neighbors (????(?) So there are many good neighbors! Denote ? = (?)\ ? ? ?? ? ? = ? ??? ? ?? Take ? ? where ? ? 4?. Fix this to be ? . 18
Proof of the lemma (5/6) So we have our ? , and ? ? 4? ?2 16? Define ? = a ? | | ? ? | Lets lower-bound |? |: Intuition: If |? | was small, ? ?,? ? ? + ? \ ? ?2 would have few edges (and it doesn t) 16? ? ? +?? ? 2? ? ?? Minimal degree in ? ? ?,? ???? ? ?,? ??? ?2 16? Combining these we get ? 19
?2 16? ?2 32? ?3 128? = 2 12?5?2 Proof of the lemma (6/6) ?2 16? We have ? ,? , with ? , ? Last step: show that for any ? ? ,? ? there are many paths of length 3 from ? to ?. 1. Fix ?,?. From ? ? construction, ? has many neighbors ? ? . 2. Out of these neighbors, only few form a bad pair with ? 3. For ? ? that don t form a bad pair with ?, there are many common neighbors ? ? 4. So we have (many few) * many paths ?,? ,? ,? of length 3 20
To conclude the section We will state a lemma in graph theory Easily prove BSG using the lemma Work hard to prove the lemma Take a break before the second part Questions? 21
