Freiman's theorem
In additive combinatorics, a discipline within mathematics, Freiman's theorem is a central result which indicates the approximate structure of sets whose sumset is small. It roughly states that if is small, then can be contained in a small generalized arithmetic progression.
Statement
If is a finite subset of with , then is contained in a generalized arithmetic progression of dimension at most and size at most , where and are constants depending only on .
Examples
For a finite set of integers, it is always true that
with equality precisely when is an arithmetic progression.
More generally, suppose is a subset of a finite proper generalized arithmetic progression of dimension such that for some real . Then , so that
History of Freiman's theorem
This result is due to Gregory Freiman (1964, 1966).[1][2][3] Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1992,1994).[4][5] Mei-Chu Chang proved new polynomial estimates for the size of arithmetic progressions arising in the theorem in 2002.[6] The current best bounds were provided by Tom Sanders.[7]
Tools used in the proof
The proof presented here follows the proof in Yufei Zhao's lecture notes.[8]
Plünnecke–Ruzsa inequality
Ruzsa covering lemma
The Ruzsa covering lemma states the following:
- Let and be finite subsets of an abelian group with nonempty, and let be a positive real number. Then if , there is a subset of with at most elements such that .
This lemma provides a bound on how many copies of one needs to cover , hence the name. The proof is essentially a greedy algorithm:
Proof: Let be a maximal subset of such that the sets for are all disjoint. Then , and also , so . Furthermore, for any , there is some such that intersects , as otherwise adding to contradicts the maximality of . Thus , so .
Freiman homomorphisms and the Ruzsa modeling lemma
Let be a positive integer, and and be abelian groups. Let and . A map is a Freiman -homomorphism if
whenever for any .
If in addition is a bijection and is a Freiman -homomorphism, then is a Freiman -isomorphism.
If is a Freiman -homomorphism, then is a Freiman -homomorphism for any positive integer such that .
Then the Ruzsa modeling lemma states the following:
- Let be a finite set of integers, and let be a positive integer. Let be a positive integer such that . Then there exists a subset of with cardinality at least such that is Freiman -isomorphic to a subset of .
The last statement means there exists some Freiman -homomorphism between the two subsets.
Proof sketch: Choose a prime sufficiently large such that the modulo- reduction map is a Freiman -isomorphism from to its image in . Let be the lifting map that takes each member of to its unique representative in . For nonzero , let be the multiplication by map, which is a Freiman -isomorphism. Let be the image . Choose a suitable subset of with cardinality at least such that the restriction of to is a Freiman -isomorphism onto its image, and let be the preimage of under . Then the restriction of to is a Freiman -isomorphism onto its image . Lastly, there exists some choice of nonzero such that the restriction of the modulo- reduction to is a Freiman -isomorphism onto its image. The result follows after composing this map with the earlier Freiman -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:
- Let and let . Then contains a subspace of of dimension at least .
Generalizing this lemma to arbitrary cyclic groups requires an analogous notion to “subspace”: that of the Bohr set. Let be a subset of where is a prime. The Bohr set of dimension and width is
where is the distance from to the nearest integer. The following lemma generalizes Bogolyubov's lemma:
- Let and . Then contains a Bohr set of dimension at most and width .
Here the dimension of a Bohr set is analogous to the codimension of a set in . 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.
- Let be a Bohr set in of dimension and width . Then contains a proper generalized arithmetic progression of dimension at most and size at least .
The proof of this proposition uses Minkowski's theorem, a fundamental result in geometry of numbers.
Proof
By the Plünnecke–Ruzsa inequality, . By Bertrand's postulate, there exists a prime such that . By the Ruzsa modeling lemma, there exists a subset of of cardinality at least such that is Freiman 8-isomorphic to a subset .
By the generalization of Bogolyubov's lemma, contains a proper generalized arithmetic progression of dimension at most and size at least . Because and are Freiman 8-isomorphic, and are Freiman 2-isomorphic. Then the image under the 2-isomorphism of the proper generalized arithmetic progression in is a proper generalized arithmetic progression in called .
But , since . Thus
so by the Ruzsa covering lemma for some of cardinality at most . Then is contained in a generalized arithmetic progression of dimension and size at most , completing the proof.
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 is a set for a proper generalized arithmetic progression and a subgroup of . The dimension of this coset progression is defined to be the dimension of , and its size is defined to be the cardinality of the whole set. Green and Ruzsa showed the following:
- Let be a finite set in an abelian group such that . Then is contained in a coset progression of dimension at most and size at most , where and are functions of that are independent of .
Green and Ruzsa provided upper bounds of and for some absolute constant .[9]
Terence Tao (2010) also generalized Freiman's theorem to solvable groups of bounded derived length.[10]
Extending Freiman’s theorem to an arbitrary nonabelian group is still open. Results for , when a set has very small doubling, are referred to as Kneser theorems.[11]
The polynomial Freiman–Ruzsa conjecture,[12] is a generalization published in a paper[13] by Imre Ruzsa but credited by him to Katalin Marton. It states that if a subset of a group (a power of a cyclic group) has doubling constant such that then it is covered by a bounded number of cosets of some subgroup with. In 2012 Toms Sanders gave an almost polynomial bound of the conjecture for abelian groups.[14][15] In 2023 a solution over a field of characteristic 2 has been posted as a preprint by Tim Gowers, Ben Green, Freddie Manners and Terry Tao.[16][17][18] This proof was completely formalized in the Lean 4 formal proof language, a collaborative project that marked an important milestone in terms of mathematicians successfully formalizing contemporary mathematics.[19]
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, I. Z. (August 1992). "Arithmetical progressions and the number of sums". Periodica Mathematica Hungarica. 25 (1): 105–111. doi:10.1007/BF02454387. ISSN 0031-5303.
- ^ 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. S2CID 42609470.
- ^ Zhao, Yufei. "Graph Theory and Additive Combinatorics" (PDF). Archived from the original (PDF) on 2019-11-23. Retrieved 2019-12-02.
- ^ 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. S2CID 15115236.
- ^ 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 (10 November 2009). "An elementary non-commutative Freiman theorem". Terence Tao's blog.
- ^ "(Ben Green) The Polynomial Freiman–Ruzsa conjecture". What's new. 2007-03-11. Retrieved 2023-11-14.
- ^ Ruzsa, I. (1999). "An analog of Freiman's theorem in groups" (PDF). Astérisque. 258: 323–326.
- ^ Sanders, Tom (2012-10-15). "On the Bogolyubov–Ruzsa lemma". Analysis & PDE. 5 (3): 627–655. arXiv:1011.0107. doi:10.2140/apde.2012.5.627. ISSN 1948-206X.
- ^ Brubaker, Ben (2023-12-04). "An Easy-Sounding Problem Yields Numbers Too Big for Our Universe". Quanta Magazine. Retrieved 2023-12-11.
- ^ Gowers, W. T.; Green, Ben; Manners, Freddie; Tao, Terence (2023). "On a conjecture of Marton". arXiv:2311.05762 [math.NT].
- ^ "On a conjecture of Marton". What's new. 2023-11-13. Retrieved 2023-11-14.
- ^ Sloman, Leila (December 6, 2023). "'A-Team' of Math Proves a Critical Link Between Addition and Sets". Quanta Magazine. Retrieved December 16, 2023.
- ^ "The Polynomial Freiman-Ruzsa Conjecture". PFR Project homepage.
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.