Freiman's theorem

Freiman's theorem In additive combinatorics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if {stile di visualizzazione |A+A|/|UN|} è piccolo, poi {stile di visualizzazione A} can be contained in a small generalized arithmetic progression.

Contenuti 1 Dichiarazione 2 Esempi 3 History of Freiman's theorem 4 Tools used in the proof 4.1 Plünnecke-Ruzsa inequality 4.2 Ruzsa covering lemma 4.3 Freiman homomorphisms and the Ruzsa modeling lemma 4.4 Bohr sets and Bogolyubov's lemma 5 Prova 6 generalizzazioni 7 Guarda anche 8 Riferimenti 9 Further reading Statement If {stile di visualizzazione A} is a finite subset of {displaystyle mathbb {Z} } insieme a {stile di visualizzazione |A+A|leq K|UN|} , poi {stile di visualizzazione A} is contained in a generalized arithmetic progression of dimension at most {stile di visualizzazione d(K)} and size at most {stile di visualizzazione f(K)|UN|} , dove {stile di visualizzazione d(K)} e {stile di visualizzazione f(K)} are constants depending only on {stile di visualizzazione K} .

Examples For a finite set {stile di visualizzazione A} of integers, it is always true that {stile di visualizzazione |A+A|geq 2|UN|-1,} with equality precisely when {stile di visualizzazione A} is an arithmetic progression.

Più generalmente, supponiamo {stile di visualizzazione A} is a subset of a finite proper generalized arithmetic progression {stile di visualizzazione P} of dimension {stile di visualizzazione d} tale che {stile di visualizzazione |P|leq C|UN|} for some real {displaystyle Cgeq 1} . Quindi {stile di visualizzazione |P+P|leq 2^{d}|P|} , affinché {stile di visualizzazione |A+A|leq |P+P|leq 2^{d}|P|leq C2^{d}|UN|.} History of Freiman's theorem This result is due to Gregory Freiman (1964, 1966).[1][2][3] Much interest in it, e applicazioni, stemmed from a new proof by Imre Z. Ruzsa (1994).[4] Mei-Chu Chang proved new polynomial estimates for the size of arithmetic progressions arising in the theorem in 2002.[5] The current best bounds were provided by Tom Sanders.[6] Tools used in the proof The proof presented here follows the proof in Yufei Zhao's lecture notes.[7] Plünnecke-Ruzsa inequality Main article: Plünnecke-Ruzsa inequality Ruzsa covering lemma The Ruzsa covering lemma states the following: Permettere {stile di visualizzazione A} e {stile di visualizzazione S} be finite subsets of an abelian group with {stile di visualizzazione S} nonempty, e lascia {stile di visualizzazione K} be a positive real number. Allora se {stile di visualizzazione |A+S|leq K|S|} , there is a subset {stile di visualizzazione T} di {stile di visualizzazione A} with at most {stile di visualizzazione K} elements such that {displaystyle Asubseteq T+S-S} .

This lemma provides a bound on how many copies of {displaystyle S-S} one needs to cover {stile di visualizzazione A} , hence the name. The proof is essentially a greedy algorithm: Prova: Permettere {stile di visualizzazione T} be a maximal subset of {stile di visualizzazione A} such that the sets {displaystyle t+S} per {stile di visualizzazione A} are all disjoint. Quindi {stile di visualizzazione |T+S|=|T|cdot |S|} , and also {stile di visualizzazione |T+S|leq |A+S|leq K|S|} , Così {stile di visualizzazione |T|leq K} . Inoltre, per ogni {stile di visualizzazione ain A} , there is some {displaystyle tin T} tale che {displaystyle t+S} intersects {displaystyle a+S} , as otherwise adding {stile di visualizzazione a} a {stile di visualizzazione T} contradicts the maximality of {stile di visualizzazione T} . così {displaystyle ain T+S-S} , Così {displaystyle Asubseteq T+S-S} .

Freiman homomorphisms and the Ruzsa modeling lemma Let {displaystyle sgeq 2} be a positive integer, e {stile di visualizzazione Gamma } e {displaystyle Gamma '} be abelian groups. Permettere {displaystyle Asubseteq Gamma } e {displaystyle Bsubseteq Gamma '} . A map {displaystyle varphi colon Ato B} is a Freiman {stile di visualizzazione s} -homomorphism if {stile di visualizzazione varphi (un_{1})+cdots +varphi (un_{S})=varphi (un_{1}')+cdots +varphi (un_{S}')} Ogni volta che {stile di visualizzazione a_{1}+cdot +a_{S}=a_{1}'+cdots +a_{S}'} per ogni {stile di visualizzazione a_{1},ldot ,un_{S},un_{1}',ldot ,un_{S}'in A} .

If in addition {stile di visualizzazione varphi } is a bijection and {displaystyle varphi ^{-1}colon Bto A} is a Freiman {stile di visualizzazione s} -homomorphism, poi {stile di visualizzazione varphi } is a Freiman {stile di visualizzazione s} -isomorphism.

Se {stile di visualizzazione varphi } is a Freiman {stile di visualizzazione s} -homomorphism, poi {stile di visualizzazione varphi } is a Freiman {stile di visualizzazione t} -homomorphism for any positive integer {stile di visualizzazione t} tale che {displaystyle 2leq tleq s} .

Then the Ruzsa modeling lemma states the following: Permettere {stile di visualizzazione A} be a finite set of integers, e lascia {displaystyle sgeq 2} be a positive integer. Permettere {stile di visualizzazione N} be a positive integer such that {displaystyle Ngeq |sA-sA|} . Then there exists a subset {stile di visualizzazione A'} di {stile di visualizzazione A} with cardinality at least {stile di visualizzazione |UN|/S} tale che {stile di visualizzazione A'} is Freiman {stile di visualizzazione s} -isomorphic to a subset of {displaystyle mathbb {Z} /Nmathbb {Z} } .

The last statement means there exists some Freiman {stile di visualizzazione s} -homomorphism between the two subsets.

Schizzo di prova: Choose a prime {stile di visualizzazione q} sufficiently large such that the modulo- {stile di visualizzazione q} reduction map {stile di visualizzazione pi _{q}colon mathbb {Z} a matematicabb {Z} /qmathbb {Z} } is a Freiman {stile di visualizzazione s} -isomorphism from {stile di visualizzazione A} to its image in {displaystyle mathbb {Z} /qmathbb {Z} } . Permettere {stile di visualizzazione psi _{q}colon mathbb {Z} /qmathbb {Z} a matematicabb {Z} } be the lifting map that takes each member of {displaystyle mathbb {Z} /qmathbb {Z} } to its unique representative in {stile di visualizzazione {1,ldot ,q}subseteq mathbb {Z} } . For nonzero {displaystyle lambda in mathbb {Z} /qmathbb {Z} } , permettere {displaystyle cdot lambda colon mathbb {Z} /qmathbb {Z} a matematicabb {Z} /qmathbb {Z} } be the multiplication by {displaystyle lambda } map, which is a Freiman {stile di visualizzazione s} -isomorphism. Permettere {stile di visualizzazione B} be the image {stile di visualizzazione (cdot lambda circ pi _{q})(UN)} . Choose a suitable subset {stile di visualizzazione B'} di {stile di visualizzazione B} with cardinality at least {stile di visualizzazione |B|/S} such that the restriction of {stile di visualizzazione psi _{q}} a {stile di visualizzazione B'} is a Freiman {stile di visualizzazione s} -isomorphism onto its image, e lascia {displaystyle A'subseteq A} be the preimage of {stile di visualizzazione B'} under {displaystyle cdot lambda circ pi _{q}} . Then the restriction of {stile di visualizzazione psi _{q}circ cdot lambda circ pi _{q}} a {stile di visualizzazione A'} is a Freiman {stile di visualizzazione s} -isomorphism onto its image {stile di visualizzazione psi _{q}(B')} . infine, there exists some choice of nonzero {displaystyle lambda } such that the restriction of the modulo- {stile di visualizzazione N} reduction {displaystyle mathbb {Z} a matematicabb {Z} /Nmathbb {Z} } a {stile di visualizzazione psi _{q}(B')} is a Freiman {stile di visualizzazione s} -isomorphism onto its image. The result follows after composing this map with the earlier Freiman {stile di visualizzazione s} -isomorphism.

Bohr sets and Bogolyubov's lemma Though Freiman's theorem applies to sets of integers, the Ruzsa modeling lemma allows one to model sets of integers as subsets of finite cyclic groups. So it is useful to first work in the setting of a finite field, and then generalize results to the integers. The following lemma was proved by Bogolyubov: Permettere {displaystyle Ain mathbb {F} _{2}^{n}} e lascia {displaystyle alpha =|UN|/2^{n}} . Quindi {displaystyle 4A} contains a subspace of {displaystyle mathbb {F} _{2}^{n}} of dimension at least {displaystyle n-alpha ^{-2}} .

Generalizing this lemma to arbitrary cyclic groups requires an analogous notion to “subspace”: that of the Bohr set. Permettere {stile di visualizzazione R} be a subset of {displaystyle mathbb {Z} /Nmathbb {Z} } dove {stile di visualizzazione N} is a prime. The Bohr set of dimension {stile di visualizzazione |R|} and width {displaystyle epsilon } è {nome dell'operatore dello stile di visualizzazione {Bohr} (R,epsilon )={xin mathbb {Z} /Nmathbb {Z} :forall rin R,|rx/N|leq epsilon },} dove {stile di visualizzazione |rx/N|} is the distance from {displaystyle rx/N} to the nearest integer. The following lemma generalizes Bogolyubov's lemma: Permettere {displaystyle Ain mathbb {Z} /Nmathbb {Z} } e {displaystyle alpha =|UN|/N} . Quindi {displaystyle 2A-2A} contains a Bohr set of dimension at most {displaystyle alpha ^{-2}} and width {stile di visualizzazione 1/4} .

Here the dimension of a Bohr set is analogous to the codimension of a set in {displaystyle mathbb {F} _{2}^{n}} . The proof of the lemma involves Fourier-analytic methods. The following proposition relates Bohr sets back to generalized arithmetic progressions, eventually leading to the proof of Freiman's theorem.

Permettere {stile di visualizzazione X} be a Bohr set in {displaystyle mathbb {Z} /Nmathbb {Z} } of dimension {stile di visualizzazione d} and width {displaystyle epsilon } . Quindi {stile di visualizzazione X} contains a proper generalized arithmetic progression of dimension at most {stile di visualizzazione d} and size at least {stile di visualizzazione (epsilon /d)^{d}N} .

The proof of this proposition uses Minkowski's theorem, a fundamental result in geometry of numbers.

Proof By the Plünnecke-Ruzsa inequality, {stile di visualizzazione |8A-8A|leq K^{16}|UN|} . By Bertrand's postulate, there exists a prime {stile di visualizzazione N} tale che {stile di visualizzazione |8A-8A|leq Nleq 2K^{16}|UN|} . By the Ruzsa modeling lemma, there exists a subset {stile di visualizzazione A'} di {stile di visualizzazione A} of cardinality at least {stile di visualizzazione |UN|/8} tale che {stile di visualizzazione A'} is Freiman 8-isomorphic to a subset {displaystyle Bsubseteq mathbb {Z} /Nmathbb {Z} } .

By the generalization of Bogolyubov's lemma, {displaystyle 2B-2B} contains a proper generalized arithmetic progression of dimension {stile di visualizzazione d} at most {stile di visualizzazione (1/(8cdot 2K^{16}))^{-2}=256K^{32}} and size at least {stile di visualizzazione (1/(4d))^{d}N} . Perché {stile di visualizzazione A'} e {stile di visualizzazione B} are Freiman 8-isomorphic, {displaystyle 2A'-2A'} e {displaystyle 2B-2B} are Freiman 2-isomorphic. Then the image under the 2-isomorphism of the proper generalized arithmetic progression in {displaystyle 2B-2B} is a proper generalized arithmetic progression in {displaystyle 2A'-2A'subseteq 2A-2A} chiamato {stile di visualizzazione P} .

Ma {displaystyle P+Asubseteq 3A-2A} , da {displaystyle Psubseteq 2A-2A} . così {stile di visualizzazione |P+A|leq |3A-2A|leq |8A-8A|leq Nleq (4d)^{d}|P|} so by the Ruzsa covering lemma {displaystyle Asubseteq X+P-P} per alcuni {displaystyle Xsubseteq A} of cardinality at most {stile di visualizzazione (4d)^{d}} . Quindi {displaystyle X+P-P} is contained in a generalized arithmetic progression of dimension {stile di visualizzazione |X|+d} and size at most {stile di visualizzazione 2 ^{|X|}2^{d}|P|leq 2^{|X|+d}|2A-2A|leq 2^{|X|+d}K^{4}|UN|} , completando la dimostrazione.

Generalizations A result due to Ben Green and Imre Ruzsa generalized Freiman's theorem to arbitrary abelian groups. They used an analogous notion to generalized arithmetic progressions, which they called coset progressions. A coset progression of an abelian group {stile di visualizzazione G} is a set {displaystyle P+H} for a proper generalized arithmetic progression {stile di visualizzazione P} and a subgroup {stile di visualizzazione H} di {stile di visualizzazione G} . The dimension of this coset progression is defined to be the dimension of {stile di visualizzazione P} , and its size is defined to be the cardinality of the whole set. Green and Ruzsa showed the following: Permettere {stile di visualizzazione A} be a finite set in an abelian group {stile di visualizzazione G} tale che {stile di visualizzazione |A+A|leq K|UN|} . Quindi {stile di visualizzazione A} is contained in a coset progression of dimension at most {stile di visualizzazione d(K)} and size at most {stile di visualizzazione f(K)|UN|} , dove {stile di visualizzazione f(K)} e {stile di visualizzazione d(K)} are functions of {stile di visualizzazione K} that are independent of {stile di visualizzazione G} .

Green and Ruzsa provided upper bounds of {stile di visualizzazione d(K)=CK^{4}tronco d'albero(K+2)} e {stile di visualizzazione f(K)=e^{CK^{4}log ^{2}(K+2)}} for some absolute constant {stile di visualizzazione C} .[8] Terence Tao (2010) also generalized Freiman's theorem to solvable groups of bounded derived length.[9] Extending Freiman’s theorem to an arbitrary nonabelian group is still open. Results for {stile di visualizzazione K<2} , when a set has very small doubling, are referred to as Kneser theorems.[10] See also Markov spectrum Plünnecke-Ruzsa inequality Kneser's theorem (combinatorics) References ^ Freiman, G.A. (1964). "Addition of finite sets". Soviet Mathematics. Doklady. 5: 1366–1370. Zbl 0163.29501. ^ Freiman, G. A. (1966). Foundations of a Structural Theory of Set Addition (in Russian). Kazan: Kazan Gos. Ped. Inst. p. 140. Zbl 0203.35305. ^ Nathanson, Melvyn B. (1996). Additive Number Theory: Inverse Problems and Geometry of Sumsets. Graduate Texts in Mathematics. Vol. 165. Springer. ISBN 978-0-387-94655-9. Zbl 0859.11003. p. 252. ^ Ruzsa, Imre Z. (1994). "Generalized arithmetical progressions and sumsets". Acta Mathematica Hungarica. 65 (4): 379–388. doi:10.1007/bf01876039. Zbl 0816.11008. ^ Chang, Mei-Chu (2002). "A polynomial bound in Freiman's theorem". Duke Mathematical Journal. 113 (3): 399–419. CiteSeerX 10.1.1.207.3090. doi:10.1215/s0012-7094-02-11331-3. MR 1909605. ^ Sanders, Tom (2013). "The structure theory of set addition revisited". Bulletin of the American Mathematical Society. 50: 93–127. arXiv:1212.0458. doi:10.1090/S0273-0979-2012-01392-7. ^ Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). ^ Ruzsa, Imre Z.; Green, Ben (2007). "Freiman's theorem in an arbitrary abelian group". Journal of the London Mathematical Society. 75 (1): 163–175. arXiv:math/0505198. doi:10.1112/jlms/jdl021. ^ Tao, Terence (2010). "Freiman's theorem for solvable groups". Contributions to Discrete Mathematics. 5 (2): 137–184. doi:10.11575/cdm.v5i2.62020. ^ Tao, Terence. "An elementary non-commutative Freiman theorem". Terence Tao's blog. Further reading Freiman, G. A. (1999). "Structure theory of set addition". Astérisque. 258: 1–33. Zbl 0958.11008. This article incorporates material from Freiman's theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. Categories: SumsetsTheorems in number theory