Freiman's theorem

If $A$ is a finite subset of $\backslash mathbb\{Z\}$ with $|A+A|\backslash le\; K|A|$, then $A$ is contained in a generalized arithmetic progression of dimension at most $d(K)$ and size at most $f(K)|A|$, where $d(K)$ and $f(K)$ are constants depending only on $K$.

For a finite set $A$ of integers, it is always true that

:$|A\; +\; A|\; \backslash ge\; 2|A|-1,$

with equality precisely when $A$ is an arithmetic progression.

More generally, suppose $A$ is a subset of a finite proper generalized arithmetic progression $P$ of dimension $d$ such that $|P|\; \backslash le\; C|A|$ for some real $C\; \backslash ge\; 1$. Then $|P+P|\; \backslash le\; 2^d\; |P|$, so that

:$|A+A|\; \backslash le\; |P+P|\; \backslash le\; 2^d\; |P|\; \backslash le\; C2^d|A|.$

This result is due to Gregory Freiman (1964, 1966).{{cite journal | zbl=0163.29501 | last=Freiman | first=G.A. | author-link=Gregory Freiman | title=Addition of finite sets | language=en | journal=Soviet Mathematics. Doklady | volume=5 | pages=1366–1370 | year=1964 }}{{cite book | first=G. A. | last=Freiman | author-link=Gregory Freiman | title=Foundations of a Structural Theory of Set Addition | language=ru | publisher=Kazan Gos. Ped. Inst. | location=Kazan | year=1966 | pages=140 | zbl=0203.35305 }}{{cite book| last=Nathanson | first=Melvyn B. | year=1996 | title=Additive Number Theory: Inverse Problems and Geometry of Sumsets | volume=165 | series=Graduate Texts in Mathematics | publisher=Springer | isbn=978-0-387-94655-9 | zbl=0859.11003}} p. 252. Much interest in it, and applications, stemmed from a new proof by Imre Z. Ruzsa (1992,1994).{{Cite journal |last=Ruzsa |first=I. Z. |date=August 1992 |title=Arithmetical progressions and the number of sums |url=http://link.springer.com/10.1007/BF02454387 |journal=Periodica Mathematica Hungarica |language=en |volume=25 |issue=1 |pages=105–111 |doi=10.1007/BF02454387 |issn=0031-5303|url-access=subscription }}{{cite journal | first=Imre Z. | last=Ruzsa | author-link=Imre Z. Ruzsa | title=Generalized arithmetical progressions and sumsets | journal=Acta Mathematica Hungarica | volume=65 | number=4 | year=1994 | pages=379–388 | zbl=0816.11008 | doi=10.1007/bf01876039 | doi-access=free}} Mei-Chu Chang proved new polynomial estimates for the size of arithmetic progressions arising in the theorem in 2002.{{cite journal|date=2002|title=A polynomial bound in Freiman's theorem|journal=Duke Mathematical Journal|volume=113|pages=399–419|mr=1909605|last1=Chang|first1=Mei-Chu|number=3|doi=10.1215/s0012-7094-02-11331-3|citeseerx=10.1.1.207.3090}} The current best bounds were provided by Tom Sanders.{{cite journal|first=Tom|last=Sanders|author-link=Tom Sanders (mathematician)|date=2013|title=The structure theory of set addition revisited|journal=Bulletin of the American Mathematical Society|volume=50|pages=93–127|doi=10.1090/S0273-0979-2012-01392-7 |arxiv=1212.0458|s2cid=42609470 }}

The proof presented here follows the proof in Yufei Zhao's lecture notes.{{cite web |last1=Zhao |first1=Yufei |title=Graph Theory and Additive Combinatorics |url=http://yufeizhao.com/gtac/fa17/gtac.pdf |access-date=2019-12-02 |archive-date=2019-11-23 |archive-url=https://web.archive.org/web/20191123230241/http://yufeizhao.com/gtac/fa17/gtac.pdf |url-status=dead }}

{{Main|Plünnecke–Ruzsa inequality}}

The Ruzsa covering lemma states the following:

:Let $A$ and $S$ be finite subsets of an abelian group with $S$ nonempty, and let $K$ be a positive real number. Then if $|A+S|\; \backslash le\; K|S|$, there is a subset $T$ of $A$ with at most $K$ elements such that $A\; \backslash subseteq\; T+S-S$.

This lemma provides a bound on how many copies of $S-S$ one needs to cover $A$, hence the name. The proof is essentially a greedy algorithm:

Proof: Let $T$ be a maximal subset of $A$ such that the sets $t+S$ for $A$ are all disjoint. Then $|T+S|=|T|\; \backslash cdot\; |S|$, and also $|T+S|\; \backslash le\; |A+S|\; \backslash le\; K|S|$, so $|T|\; \backslash le\; K$. Furthermore, for any $a\; \backslash in\; A$, there is some $t\; \backslash in\; T$ such that $t+S$ intersects $a+S$, as otherwise adding $a$ to $T$ contradicts the maximality of $T$. Thus $a\; \backslash in\; T+S-S$, so $A\; \backslash subseteq\; T+S-S$.

Let $s\; \backslash ge\; 2$ be a positive integer, and $\backslash Gamma$ and $\backslash Gamma\text{'}$ be abelian groups. Let $A\; \backslash subseteq\; \backslash Gamma$ and $B\; \backslash subseteq\; \backslash Gamma\text{'}$. A map $\backslash varphi\; \backslash colon\; A\; \backslash to\; B$ is a Freiman $s$-homomorphism if

:$\backslash varphi(a\_1)\; +\; \backslash cdots\; +\; \backslash varphi(a\_s)\; =\; \backslash varphi(a\_1\text{'})\; +\; \backslash cdots\; +\; \backslash varphi(a\_s\text{'})$

whenever $a\_1\; +\; \backslash cdots\; +\; a\_s\; =\; a\_1\text{'}\; +\; \backslash cdots\; +\; a\_s\text{'}$ for any $a\_1,\; \backslash ldots,\; a\_s,\; a\_1\text{'},\; \backslash ldots,\; a\_s\text{'}\; \backslash in\; A$.

If in addition $\backslash varphi$ is a bijection and $\backslash varphi^\{-1\}\; \backslash colon\; B\; \backslash to\; A$ is a Freiman $s$-homomorphism, then $\backslash varphi$ is a Freiman $s$-isomorphism.

If $\backslash varphi$ is a Freiman $s$-homomorphism, then $\backslash varphi$ is a Freiman $t$-homomorphism for any positive integer $t$ such that $2\backslash le\; t\; \backslash le\; s$.

Then the Ruzsa modeling lemma states the following:

:Let $A$ be a finite set of integers, and let $s\; \backslash ge\; 2$ be a positive integer. Let $N$ be a positive integer such that $N\; \backslash ge\; |sA-sA|$. Then there exists a subset $A\text{'}$ of $A$ with cardinality at least $|A|/s$ such that $A\text{'}$ is Freiman $s$-isomorphic to a subset of $\backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$.

The last statement means there exists some Freiman $s$-homomorphism between the two subsets.

Proof sketch: Choose a prime $q$ sufficiently large such that the modulo-$q$ reduction map $\backslash pi\_q\; \backslash colon\; \backslash mathbb\{Z\}\; \backslash to\; \backslash mathbb\{Z\}/q\backslash mathbb\{Z\}$ is a Freiman $s$-isomorphism from $A$ to its image in $\backslash mathbb\{Z\}/q\backslash mathbb\{Z\}$. Let $\backslash psi\_q\; \backslash colon\; \backslash mathbb\{Z\}/q\backslash mathbb\{Z\}\; \backslash to\; \backslash mathbb\{Z\}$ be the lifting map that takes each member of $\backslash mathbb\{Z\}/q\backslash mathbb\{Z\}$ to its unique representative in $\backslash \{1,\backslash ldots,q\backslash \}\; \backslash subseteq\; \backslash mathbb\{Z\}$. For nonzero $\backslash lambda\; \backslash in\; \backslash mathbb\{Z\}/q\backslash mathbb\{Z\}$, let $\backslash cdot\backslash lambda\; \backslash colon\; \backslash mathbb\{Z\}/q\backslash mathbb\{Z\}\; \backslash to\; \backslash mathbb\{Z\}/q\backslash mathbb\{Z\}$ be the multiplication by $\backslash lambda$ map, which is a Freiman $s$-isomorphism. Let $B$ be the image $(\backslash cdot\backslash lambda\backslash circ\backslash pi\_q)(A)$. Choose a suitable subset $B\text{'}$ of $B$ with cardinality at least $|B|/s$ such that the restriction of $\backslash psi\_q$ to $B\text{'}$ is a Freiman $s$-isomorphism onto its image, and let $A\text{'}\; \backslash subseteq\; A$ be the preimage of $B\text{'}$ under $\backslash cdot\backslash lambda\backslash circ\backslash pi\_q$. Then the restriction of $\backslash psi\_q\; \backslash circ\; \backslash cdot\backslash lambda\; \backslash circ\; \backslash pi\_q$ to $A\text{'}$ is a Freiman $s$-isomorphism onto its image $\backslash psi\_q(B\text{'})$. Lastly, there exists some choice of nonzero $\backslash lambda$ such that the restriction of the modulo-$N$ reduction $\backslash mathbb\{Z\}\; \backslash to\; \backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$ to $\backslash psi\_q(B\text{'})$ is a Freiman $s$-isomorphism onto its image. The result follows after composing this map with the earlier Freiman $s$-isomorphism.

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 $A\; \backslash subseteq\; \backslash mathbb\{F\}\_2^n$ and let $\backslash alpha=\; |A|/2^n$. Then $4A$ contains a subspace of $\backslash mathbb\{F\}\_2^n$ of dimension at least $n-\backslash alpha^\{-2\}$.

Generalizing this lemma to arbitrary cyclic groups requires an analogous notion to “subspace”: that of the Bohr set. Let $R$ be a subset of $\backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$ where $N$ is a prime. The Bohr set of dimension $|R|$ and width $\backslash varepsilon$ is

:$\backslash operatorname\{Bohr\}(R,\; \backslash varepsilon)\; =\; \backslash \{\; x\; \backslash in\; \backslash mathbb\{Z\}/N\backslash mathbb\{Z\}\; :\; \backslash forall\; r\; \backslash in\; R,\; |rx/N|\; \backslash le\; \backslash varepsilon\; \backslash \},$

where $|rx/N|$ is the distance from $rx/N$ to the nearest integer. The following lemma generalizes Bogolyubov's lemma:

:Let $A\; \backslash subseteq\; \backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$ and $\backslash alpha\; =\; |A|/N$. Then $2A-2A$ contains a Bohr set of dimension at most $\backslash alpha^\{-2\}$ and width $1/4$.

Here the dimension of a Bohr set is analogous to the codimension of a set in $\backslash 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.

:Let $X$ be a Bohr set in $\backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$ of dimension $d$ and width $\backslash varepsilon$. Then $X$ contains a proper generalized arithmetic progression of dimension at most $d$ and size at least $(\backslash varepsilon/d)^dN$.

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

By the Plünnecke–Ruzsa inequality, $|8A-8A|\backslash le\; K^\{16\}|A|$. By Bertrand's postulate, there exists a prime $N$ such that $|8A-8A|\backslash le\; N\backslash le\; 2K^\{16\}|A|$. By the Ruzsa modeling lemma, there exists a subset $A\text{'}$ of $A$ of cardinality at least $|A|/8$ such that $A\text{'}$ is Freiman 8-isomorphic to a subset $B\backslash subseteq\; \backslash mathbb\{Z\}/N\backslash mathbb\{Z\}$.

By the generalization of Bogolyubov's lemma, $2B-2B$ contains a proper generalized arithmetic progression of dimension $d$ at most $(1/(8\backslash cdot\; 2K^\{16\}))^\{-2\}=256K^\{32\}$ and size at least $(1/(4d))^dN$. Because $A\text{'}$ and $B$ are Freiman 8-isomorphic, $2A\text{'}-2A\text{'}$ and $2B-2B$ are Freiman 2-isomorphic. Then the image under the 2-isomorphism of the proper generalized arithmetic progression in $2B-2B$ is a proper generalized arithmetic progression in $2A\text{'}-2A\text{'}\backslash subseteq\; 2A-2A$ called $P$.

But $P+A\backslash subseteq\; 3A-2A$, since $P\backslash subseteq\; 2A-2A$. Thus

:$|P+A|\backslash le\; |3A-2A|\backslash le\; |8A-8A|\backslash le\; N\backslash le\; (4d)^d|P|$

so by the Ruzsa covering lemma $A\backslash subseteq\; X+P-P$ for some $X\backslash subseteq\; A$ of cardinality at most $(4d)^d$. Then $X+P-P$ is contained in a generalized arithmetic progression of dimension $|X|+d$ and size at most $2^$

{{See also|Arithmetic combinatorics#Breuillard–Green–Tao_theorem}}

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 $G$ is a set $P+H$ for a proper generalized arithmetic progression $P$ and a subgroup $H$ of $G$. The dimension of this coset progression is defined to be the dimension of $P$, and its size is defined to be the cardinality of the whole set. Green and Ruzsa showed the following:

:Let $A$ be a finite set in an abelian group $G$ such that $|A+A|\; \backslash le\; K|A|$. Then $A$ is contained in a coset progression of dimension at most $d(K)$ and size at most $f(K)|A|$, where $f(K)$ and $d(K)$ are functions of $K$ that are independent of $G$.

Green and Ruzsa provided upper bounds of $d(K)=CK^4\backslash log\; (K+2)$ and $f(K)=e^\{CK^4\backslash log^2(K+2)\}$ for some absolute constant $C$. {{cite journal | first1=Imre Z. | last1=Ruzsa | author-link=Imre Z. Ruzsa |last2 =Green | first2 = Ben | author-link2 = Ben Green (mathematician) | title=Freiman's theorem in an arbitrary abelian group | journal= Journal of the London Mathematical Society| volume=75 | number=1 | year=2007 | pages=163–175 | doi=10.1112/jlms/jdl021| arxiv=math/0505198 | s2cid=15115236 }}

Terence Tao (2010) also generalized Freiman's theorem to solvable groups of bounded derived length. {{cite journal | first=Terence | last=Tao| author-link=Terence Tao | title=Freiman's theorem for solvable groups | journal = Contributions to Discrete Mathematics | volume=5 | number=2 | year=2010 | pages=137–184 | doi=10.11575/cdm.v5i2.62020 | doi-access=free}}

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. {{cite web |last1=Tao |first1=Terence |author-link = Terence Tao|title=An elementary non-commutative Freiman theorem | url=https://terrytao.wordpress.com/2009/11/10/an-elementary-non-commutative-freiman-theorem/ |website=Terence Tao's blog|date=10 November 2009 }}

The polynomial Freiman–Ruzsa conjecture{{Cite web |date=2007-03-11 |title=(Ben Green) The Polynomial Freiman–Ruzsa conjecture |url=https://terrytao.wordpress.com/2007/03/11/ben-green-the-polynomial-freiman-ruzsa-conjecture/ |access-date=2023-11-14 |website=What's new |language=en}} is a generalization published in a paper{{cite journal |last=Ruzsa |first=I. |year=1999 |title=An analog of Freiman's theorem in groups |url=http://www.numdam.org/article/AST_1999__258__323_0.pdf |journal=Astérisque |volume=258 |pages=323–326}} 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) $A\backslash subset\; G$ has doubling constant such that $|A+A|\backslash le\; K|A|$, then it is covered by a bounded number $K^\{C\}$of cosets of some subgroup $H\backslash subset\; G$ with$|H|\backslash le\; |A|$. In 2012, Tom Sanders gave an almost-polynomial bound of the conjecture for abelian groups.{{Cite journal |last=Sanders |first=Tom |date=2012-10-15 |title=On the Bogolyubov–Ruzsa lemma |url=http://msp.org/apde/2012/5-3/p05.xhtml |journal=Analysis & PDE |language=en |volume=5 |issue=3 |pages=627–655 |doi=10.2140/apde.2012.5.627 |issn=1948-206X|doi-access=free |arxiv=1011.0107 }}{{Cite web |last=Brubaker |first=Ben |date=2023-12-04 |title=An Easy-Sounding Problem Yields Numbers Too Big for Our Universe |url=https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ |access-date=2023-12-11 |website=Quanta Magazine |language=en}} In 2023, a solution over $G=\backslash mathbb\; F\_2^n$ a field of characteristic 2 has been posted as a preprint by Tim Gowers, Ben Green, Freddie Manners, and Terry Tao.{{Cite arXiv |last1=Gowers |first1=W. T. |last2=Green |first2=Ben |last3=Manners |first3=Freddie |last4=Tao |first4=Terence |date=2023 |title=On a conjecture of Marton |class=math.NT |eprint=2311.05762}}{{Cite web |date=2023-11-13 |title=On a conjecture of Marton |url=https://terrytao.wordpress.com/2023/11/13/on-a-conjecture-of-marton/ |access-date=2023-11-14 |website=What's new |language=en}}{{cite web |last=Sloman |first=Leila |date=December 6, 2023 |title='A-Team' of Math Proves a Critical Link Between Addition and Sets |url=https://www.quantamagazine.org/a-team-of-math-proves-a-critical-link-between-addition-and-sets-20231206/?mc_cid=cda01dcc5c |access-date=December 16, 2023 |website=Quanta Magazine}} 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.{{Cite web|url=https://teorth.github.io/pfr/ |website=PFR Project homepage| language=en |title=The Polynomial Freiman-Ruzsa Conjecture }}

• Markov spectrum
• Plünnecke–Ruzsa inequality
• Kneser's theorem (combinatorics)

{{reflist}}

• {{cite journal | first=G. A. | last=Freiman | author-link=Gregory Freiman | title=Structure theory of set addition | journal=Astérisque | volume=258 | year=1999 | pages=1–33 | zbl=0958.11008 }}

{{PlanetMath attribution|id=4304|title=Freiman's theorem}}

Category:Sumsets

Category:Theorems in number theory