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 {estilo de exibição |A+A|/|UMA|} is small, então {estilo de exibição A} can be contained in a small generalized arithmetic progression.

Conteúdo 1 Declaração 2 Exemplos 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 Generalizações 7 Veja também 8 Referências 9 Further reading Statement If {estilo de exibição A} is a finite subset of {estilo de exibição mathbb {Z} } com {estilo de exibição |A+A|leq K|UMA|} , então {estilo de exibição A} is contained in a generalized arithmetic progression of dimension at most {estilo de exibição d(K)} and size at most {estilo de exibição f(K)|UMA|} , Onde {estilo de exibição d(K)} e {estilo de exibição f(K)} are constants depending only on {estilo de exibição K} .

Examples For a finite set {estilo de exibição A} of integers, it is always true that {estilo de exibição |A+A|geq 2|UMA|-1,} with equality precisely when {estilo de exibição A} is an arithmetic progression.

De forma geral, suponha {estilo de exibição A} is a subset of a finite proper generalized arithmetic progression {estilo de exibição P} of dimension {estilo de exibição d} de tal modo que {estilo de exibição |P|leq C|UMA|} for some real {displaystyle Cgeq 1} . Então {estilo de exibição |P+P|leq 2^{d}|P|} , de modo a {estilo de exibição |A+A|leq |P+P|leq 2^{d}|P|leq C2^{d}|UMA|.} History of Freiman's theorem This result is due to Gregory Freiman (1964, 1966).[1][2][3] Much interest in it, e aplicativos, 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: Deixar {estilo de exibição A} e {estilo de exibição S} be finite subsets of an abelian group with {estilo de exibição S} nonempty, e deixar {estilo de exibição K} be a positive real number. Então se {estilo de exibição |A+S|leq K|S|} , there is a subset {estilo de exibição T} do {estilo de exibição A} with at most {estilo de exibição 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 {estilo de exibição A} , hence the name. The proof is essentially a greedy algorithm: Prova: Deixar {estilo de exibição T} be a maximal subset of {estilo de exibição A} such that the sets {displaystyle t+S} por {estilo de exibição A} are all disjoint. Então {estilo de exibição |T+S|=|T|cdot |S|} , and also {estilo de exibição |T+S|leq |A+S|leq K|S|} , assim {estilo de exibição |T|leq K} . Além disso, para qualquer {estilo de exibição ain A} , there is some {displaystyle tin T} de tal modo que {displaystyle t+S} intersects {displaystyle a+S} , as otherwise adding {estilo de exibição a} para {estilo de exibição T} contradicts the maximality of {estilo de exibição T} . Desta forma {displaystyle ain T+S-S} , assim {displaystyle Asubseteq T+S-S} .

Freiman homomorphisms and the Ruzsa modeling lemma Let {displaystyle sgeq 2} be a positive integer, e {displaystyle Gama } e {displaystyle Gamma '} be abelian groups. Deixar {displaystyle Asubseteq Gamma } e {displaystyle Bsubseteq Gamma '} . A map {displaystyle varphi colon Ato B} is a Freiman {estilo de exibição s} -homomorphism if {estilo de exibição varphi (uma_{1})+cdots +varphi (uma_{s})=varphi (uma_{1}')+cdots +varphi (uma_{s}')} em qualquer momento {estilo de exibição a_{1}+cdots +a_{s}=a_{1}'+cdots +a_{s}'} para qualquer {estilo de exibição a_{1},ldots ,uma_{s},uma_{1}',ldots ,uma_{s}'in A} .

If in addition {estilo de exibição varphi } is a bijection and {displaystyle varphi ^{-1}colon Bto A} is a Freiman {estilo de exibição s} -homomorphism, então {estilo de exibição varphi } is a Freiman {estilo de exibição s} -isomorphism.

Se {estilo de exibição varphi } is a Freiman {estilo de exibição s} -homomorphism, então {estilo de exibição varphi } is a Freiman {estilo de exibição t} -homomorphism for any positive integer {estilo de exibição t} de tal modo que {displaystyle 2leq tleq s} .

Then the Ruzsa modeling lemma states the following: Deixar {estilo de exibição A} be a finite set of integers, e deixar {displaystyle sgeq 2} be a positive integer. Deixar {estilo de exibição N} be a positive integer such that {displaystyle Ngeq |sA-sA|} . Then there exists a subset {estilo de exibição A'} do {estilo de exibição A} with cardinality at least {estilo de exibição |UMA|/s} de tal modo que {estilo de exibição A'} is Freiman {estilo de exibição s} -isomorphic to a subset of {estilo de exibição mathbb {Z} /Nmathbb {Z} } .

The last statement means there exists some Freiman {estilo de exibição s} -homomorphism between the two subsets.

Esboço de prova: Choose a prime {estilo de exibição q} sufficiently large such that the modulo- {estilo de exibição q} reduction map {estilo de exibição pi _{q}colon mathbb {Z} para mathbb {Z} /qmathbb {Z} } is a Freiman {estilo de exibição s} -isomorphism from {estilo de exibição A} to its image in {estilo de exibição mathbb {Z} /qmathbb {Z} } . Deixar {estilo de exibição psi _{q}colon mathbb {Z} /qmathbb {Z} para mathbb {Z} } be the lifting map that takes each member of {estilo de exibição mathbb {Z} /qmathbb {Z} } to its unique representative in {estilo de exibição {1,ldots ,q}subseteq mathbb {Z} } . For nonzero {lambda de estilo de exibição em mathbb {Z} /qmathbb {Z} } , deixar {displaystyle cdot lambda colon mathbb {Z} /qmathbb {Z} para mathbb {Z} /qmathbb {Z} } be the multiplication by {lambda de estilo de exibição } map, which is a Freiman {estilo de exibição s} -isomorphism. Deixar {estilo de exibição B} be the image {estilo de exibição (cdot lambda circ pi _{q})(UMA)} . Choose a suitable subset {estilo de exibição B'} do {estilo de exibição B} with cardinality at least {estilo de exibição |B|/s} such that the restriction of {estilo de exibição psi _{q}} para {estilo de exibição B'} is a Freiman {estilo de exibição s} -isomorphism onto its image, e deixar {displaystyle A'subseteq A} be the preimage of {estilo de exibição B'} under {displaystyle cdot lambda circ pi _{q}} . Then the restriction of {estilo de exibição psi _{q}circ cdot lambda circ pi _{q}} para {estilo de exibição A'} is a Freiman {estilo de exibição s} -isomorphism onto its image {estilo de exibição psi _{q}(B')} . Lastly, there exists some choice of nonzero {lambda de estilo de exibição } such that the restriction of the modulo- {estilo de exibição N} reduction {estilo de exibição mathbb {Z} para mathbb {Z} /Nmathbb {Z} } para {estilo de exibição psi _{q}(B')} is a Freiman {estilo de exibição s} -isomorphism onto its image. The result follows after composing this map with the earlier Freiman {estilo de exibição 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: Deixar {displaystyle Ain mathbb {F} _{2}^{n}} e deixar {displaystyle alpha =|UMA|/2^{n}} . Então {displaystyle 4A} contains a subspace of {estilo de exibição 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. Deixar {estilo de exibição R} be a subset of {estilo de exibição mathbb {Z} /Nmathbb {Z} } Onde {estilo de exibição N} is a prime. The Bohr set of dimension {estilo de exibição |R|} and width {displaystyle épsilon } é {nome do operador de estilo de exibição {Bohr} (R,épsilon )={xin mathbb {Z} /Nmathbb {Z} :forall rin R,|rx/N|leq épsilon },} Onde {estilo de exibição |rx/N|} is the distance from {displaystyle rx/N} to the nearest integer. The following lemma generalizes Bogolyubov's lemma: Deixar {displaystyle Ain mathbb {Z} /Nmathbb {Z} } e {displaystyle alpha =|UMA|/N} . Então {displaystyle 2A-2A} contains a Bohr set of dimension at most {displaystyle alpha ^{-2}} and width {estilo de exibição 1/4} .

Here the dimension of a Bohr set is analogous to the codimension of a set in {estilo de exibição 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.

Deixar {estilo de exibição X} be a Bohr set in {estilo de exibição mathbb {Z} /Nmathbb {Z} } of dimension {estilo de exibição d} and width {displaystyle épsilon } . Então {estilo de exibição X} contains a proper generalized arithmetic progression of dimension at most {estilo de exibição d} and size at least {estilo de exibição (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, {estilo de exibição |8A-8A|leq K^{16}|UMA|} . By Bertrand's postulate, there exists a prime {estilo de exibição N} de tal modo que {estilo de exibição |8A-8A|leq Nleq 2K^{16}|UMA|} . By the Ruzsa modeling lemma, there exists a subset {estilo de exibição A'} do {estilo de exibição A} of cardinality at least {estilo de exibição |UMA|/8} de tal modo que {estilo de exibição 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 {estilo de exibição d} at most {estilo de exibição (1/(8cdot 2K^{16}))^{-2}=256K^{32}} and size at least {estilo de exibição (1/(4d))^{d}N} . Porque {estilo de exibição A'} e {estilo de exibição 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} chamado {estilo de exibição P} .

Mas {displaystyle P+Asubseteq 3A-2A} , desde {displaystyle Psubseteq 2A-2A} . Desta forma {estilo de exibição |P+A|leq |3A-2A|leq |8A-8A|leq Nleq (4d)^{d}|P|} so by the Ruzsa covering lemma {displaystyle Asubseteq X+P-P} para alguns {displaystyle Xsubseteq A} of cardinality at most {estilo de exibição (4d)^{d}} . Então {displaystyle X+P-P} is contained in a generalized arithmetic progression of dimension {estilo de exibição |X|+d} and size at most {estilo de exibição 2 ^{|X|}2^{d}|P|leq 2^{|X|+d}|2A-2A|leq 2^{|X|+d}K^{4}|UMA|} , completando a prova.

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 {estilo de exibição G} is a set {displaystyle P+H} for a proper generalized arithmetic progression {estilo de exibição P} and a subgroup {estilo de exibição H} do {estilo de exibição G} . The dimension of this coset progression is defined to be the dimension of {estilo de exibição P} , and its size is defined to be the cardinality of the whole set. Green and Ruzsa showed the following: Deixar {estilo de exibição A} be a finite set in an abelian group {estilo de exibição G} de tal modo que {estilo de exibição |A+A|leq K|UMA|} . Então {estilo de exibição A} is contained in a coset progression of dimension at most {estilo de exibição d(K)} and size at most {estilo de exibição f(K)|UMA|} , Onde {estilo de exibição f(K)} e {estilo de exibição d(K)} are functions of {estilo de exibição K} that are independent of {estilo de exibição G} .

Green and Ruzsa provided upper bounds of {estilo de exibição d(K)=CK^{4}registro(K+2)} e {estilo de exibição f(K)=e^{CK^{4}log ^{2}(K+2)}} for some absolute constant {estilo de exibição 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 {estilo de exibição 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