Sum-Product Theorems Over Finite Fields: Expansion and Proof
Explore the extension of the Erdos-Szemeredi Theorem to finite fields, with an in-depth proof involving lemma application and subset analysis in an Abelian group. Theorems and lemmas are discussed alongside the dense bipartite graph concept for a comprehensive understanding.
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
Sum-product theorems over finite fields 1
Goal Last week we saw |?|1+? Theorem[Erdos-Szemeredi]: ? ?.? ??? ??? ? ?,max ? + ? , ? ? 1 96and it s conjectured to be close to 1. We saw a proof last week of ? = Today we wish to extend this theorem to finite Fields Problem 1: If ? has a subfield ? , then clearly for ? = ? ,|? + ?| = |? ?| = |?| . So this limits us to ?? where p is a prime. Problem 2: It always holds that ? + ? , ? ? ? then clearly if ? is too close to ?we can t expect too much growth 2
Goal General statement: ?>0 ?>0 ?.? ??? ??? ????? ? ??? ??? ? ?? ?? ???? ? ?1 ? ?? ???? ? ?? max | ? , ? ? ?1+? | ? + Today we show: ??? ??? ????? ? ??? ??? ? ?? ?? ???? ? ?0.9 ?? ???? ? ?? max ? + ? , ? ? ?1+ 1 100? ??? ???? ???????? ? 3
Plan Lemma 1: ??? ??? ? ??, ? ?0.9,?? ???? ? ? ?1.01 WhereR = ? ? ? ? + ? ? ? + ? ? + ? ? ? ? ? (We saw the proof of this lemma last week) Lemma 2: ??? ? ?? ?? ?.? ? + ? , ? ? ?1+?.??? ??? ?????????? ?????????? ? ?1+?? ? ??? ????? ? ?????? ? ??? ? ?? ? ? ? ????=?(?) is?????????? ???????????????? ??????????? 4
Proof of Theorem (Using lemmas) Let ? ?0.9 and let ? be such that ? + ? , ? ? |?|1+?. |?|1+? ? ? Using lemma 2 with R gives us that exists ? ? such that ? ? But by lemma 1 we know that ? ? |?|1.01 1 Meaning ? 100? ? as requested. 5
Lemma 2 plan From now until the end of the talk, we aim to prove lemma 2: ??? ? ?? ?? ?.? ? + ? , ? ? ?1+?.??? ??? ?????????? ?????????? ? ?1+?? ? ??? ????? ? ?????? ? ??? ? ?? ? ? ? ????=?(?) is?????????? ???????????????? ??????????? 6
Proving Lemma 2 Lemma 3: Let A be a subset of an Abelian group s.t ? + ? ?|?|. Then exists ? ? of size ? ? ? 1|?| s.t any ?1 ?2 ? ? can be written as: 12??, ?1 ?2= ?=1 ?? A ? In at least ? ? 1?11 distinct ways and any ?1+ ?2 ? + ? can be written as 12??, ?1+ ?2= ?=1 ?? A ? In at least ? ? 1?11 distinct ways 7
Proving Lemma 3 (1/4) We will use the BSG theorem (distinct paths of length 3 in dense bipartite graph) Let ? = |?| ; Let K s.t ? + ? ?|?| Let ? ? + ? be the set of elements that can be written as ? = ?1+ ?2 in ? 2? distinct ways. ? 2? (Shown on board) We note that ? Denote H as the following bipartite graph: each element in a ? has a vertex in both the left and the right side. ? ? = { ?1,?2 |?1+ ?2 ?} 8
Proving Lemma 3 (2/4) Recall Sudakov s Lemma - Let H = (A;B;E) be a bipartite graph with vertex sets A,B and edge set E. Assume that |?| = |? | = ? and |?| = ??2. Then there exist ? ?,? ? of size |?|,|? | ?2 length 3 between b and b . 16 ? such that for any ? ?,? ? there are at least ?5?2 paths of ?2 4?2, meaning we have |?|,|? | ? ? 1?, where each b,b has at least ? 2? Here E = ? ? ? 1?2 paths of length 3. 9
Proving Lemma 3 (3/4) |?|,|? | ? ? 1? ; Each ?,? has at least ? ? 1?2 paths of length 3. A path like that looks like (b,a,a ,b ). Meaning we can write ? + ? = ? + ? ? + ? + ? + ? = ?1 ?2+ ?3 In at least ? ? 1?2 ways. Any element in C can be written as ? = ?1+ ?2 at least ? 2? distinct ways means that 6 ? + ? = ?=1 ?? ;?? ? ? Can be written in ? ? 1?5 distinct ways 10
Proving Lemma 3 (4/4) So we can express any ?1 ?2 ? ? as ?1+ ? ?2+ ? for any ? ? so overall we can express 12??;?? ? ? ?1 ?2= ?=1 in ? ? 1?5 ? ? 1?5 ? ? 1? = ? ? 1?11 ways. ? + ? proven in similar way 11
Lemma 4 We proceed to prove by induction that any polynomial expression does not grow (which is the original goal of lemma 2) Lemma 4: For any integers t,s there exists a constant c = c(t,s) > 0 such that the following holds. If ? + ? , ? ? ?1+? then there exists ? ? of size ? ?1 ?? such that | ?? ???? ? ?| ?1+?? 12
Lemma 2 Proof From Lemma 4 Reminder: Pl nneke Ruzsa theorem ?? ? ? ?? ? + ? ? ? ? ?? ?? ?? ??+??for any ?,? ? Note that this is a stronger than lemma 2 for the case of linear functions 13
Lemma 2 Proof From Lemma 4 If ? + ? , ? ? ?1+? then there exists ? ? of size ? ?1 ?? such that | ?? ???? ? ?| ?1+?? Plug ? = 0. we get that | ?? ??| ?1+?? . By Pl nneke Ruzsa theorem, there exists c such that | ??? ???| ?1+? ?. So we get that any monomial any sum of monomials over degree t is not large. Take t to be the degree of R(B) and we get that R(B)isn t too large 14
Proving Lemma 4 (1/8) Proof by induction on t. Base case ? = 1 Apply lemma 3 to get a B of size ? ?1 ? ?such that ?1 ?2 ? ? can be written as: 12??, ?? A ? in at least ?11 ? ? distinct ways. ?1 ?2= ?=1 12??, ?? A?+1? ? in at least ?11 ? ? So any ? ? ? ??? ? can be written as ? = ?=1 distinct ways. 15
Proving Lemma 4 (2/8) Applying Pl nneke Ruzsa on the multiplicative group of ?? we get that ??+1? ? ?1+ 2?+1 ?= ?1+? ?? (here m=s+1,l=s), therefore the number of choices for the ?? s is a most ?1+? ?? 12= ?12+? ?? ?12+? ?? ?11 ? ?= ?1+? ?? ?1+? ?? +? ? So ? ? ?? ? ? Which concludes the case of t=1 (for any s). 16
Proving Lemma 4 (3/8) Assume correctness for t, and we ll show that it holds for t+1. Let l(t,s)=t+s+12. By induction we assume that there exists ? ? of size ? ?1 ?? s.t | ?? ???? ? ?| ?1+??. In particular ? ? ?1+??, so applying lemma 3 to the multiplicative group of ??, we get that there exists ? ? of size ? ?1 ? ?? s.t any ? ? C can be written as 12?? ?? ? ? 1in at least ?11 ? ?? distinct ways. ? = ?=1 17
Proving Lemma 4 (4/8) We can assume (and lose a constant factor) that for some 1 ? 12 , ?1, ,?? ? and ??+1, ,?12 ? 1 (i.e elements in B are consecutive, and elements in ? 1 are consecutive) Multiplying by an element in ?? 1 we get that we can write any element ? ??+1 as 12?? ;?1 ??,?2, ,?? ?,??+1, ?12 ? 1in at least ?11 ? ?? distinct ways. ? = ?=1 Now we look at ?,? ??+1, and look at ? = ?1 ?2 ?12,? = ?1 ?2 ?12 ?1,?1 ??, ??,?? ? ??? 2 ? ?, ??,?? ? 1 ??? ? + 1 ? 12 18
Proving Lemma 4 (5/8) ? ? = ?1 ?2 ?12 ?1 ?2 ?12= ?1 ?1?2?3 ?12+ ?1?2 ?2?3 ?12+ ?1?2?3 ?3?4 ?12+ + ?1?2 ?11 ?12 ?12 (This is a telescopic sum) 19
Proving Lemma 4 (6/8) ?1 ?1?2?3 ?12+ ?1?2 ?2?3 ?12+ ?1?2?3 ?3?4 ?12+ + ?1?2 ?11 ?12 ?12 The first sum element is contained in ?? ???? 1?12 ? The next m-1 elements are contained in B?? ? ?? 2? 12 ? The next 12-m elements are contained in B?? 1 ? 1?? 1? 11 ? 20
Proving Lemma 4 (7/8) It s easy to see that ? 1 ? 1 ? ? ? 2. So ?? ???? 1?12 ? , B?? ? ?? 2? 12 ? ,B?? 1 ? 1?? 1? 11 ? are all contained in ?? ?????12? 12If we multiply by an element of ??? ? we get that any element of ??+1 ??+1??? ? can be written as 12 terms of ?? ????+?+12? ?+?+12 = ?? ????? ? in ?11 ?? ways 21
Proving Lemma 4 (8/8) Any element of ??+1 ??+1??? ? can be written as 12 terms of ?? ????+?+12? ?+?+12 = ?? ????? ? in ?11 ?? ways By induction on t we have that the number of x s in ?? ????? ? is at most ?12 ? ?? ?12 ? ?? ?11 ? ??= ?1+? ?? | ??+1 ??+1??? ?| Which concludes the reduction and the theorem. 22
Considering the constants We can get from the base case that ? 1,? = ? ? And the induction step gives us ? ? + 1,? = ? ? ?,? + ? + 12 [Here the O(.) is very important)] What we ve shown grows exponentially in t (and linearly in s) For our chosen R from lemma 1 R = ? ? ? ? + ? ? ? + ? ? + ? ? ? ? ? 1 1 we get a very large constant, meaning we shown over all that ? 100? ? 100 ?????12 23
