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.
can be contained in a small generalized arithmetic progression.
is contained in a generalized arithmetic progression of dimension at most
is a subset of a finite proper generalized arithmetic progression
, so that 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.
Then the Ruzsa modeling lemma states the following: The last statement means there exists some Freiman
The result follows after composing this map with the earlier Freiman
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: Generalizing this lemma to arbitrary cyclic groups requires an analogous notion to “subspace”: that of the Bohr set.
The following lemma generalizes Bogolyubov's lemma: 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.
The proof of this proposition uses Minkowski's theorem, a fundamental result in geometry of numbers.
By the Ruzsa modeling lemma, there exists a subset
contains a proper generalized arithmetic progression of dimension
Then the image under the 2-isomorphism of the proper generalized arithmetic progression in
is contained in a generalized arithmetic progression of dimension
A result due to Ben Green and Imre Ruzsa generalized Freiman's theorem to arbitrary abelian groups.
[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.
, 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.
In 2012 Tom Sanders gave an almost polynomial bound of the conjecture for abelian groups.
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.
This article incorporates material from Freiman's theorem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.