Freiman-Ruzsa theorem

For every $K$, a finite set $A$ in an abelian group with $|A+A|\le K|A|$ is contained in a coset progression of rank and relative size bounded in terms of $K$ alone.

A finite nonempty set of integers with bounded doubling lies in a generalized arithmetic progression with rank and relative size bounded only by the doubling constant. A proof models a large subset in a dense cyclic set, finds a Bohr set in its fourfold difference set by Fourier analysis, and uses the progression in a Bohr set from successive minima. The progression lifts through a sufficiently high-order Freiman isomorphism. A greedy covering of the original set by translates of its doubled progression then gives the claimed containing progression. Geometry-of-numbers properification may make the final progression proper.

If $A\subseteq {\mathbb{F}}_p^n$ and $|A+A|\le K|A|$, then $A$ is contained in a vector subspace $H$ satisfying

Let $A$ be a nonempty subset of ${\mathbb{F}}_2^N$ with doubling constant at most $C\ge 1$. Translate to $B=A+a$ containing zero. The Petridis minimal-growth lemma and Ruzsa triangle inequality bound $|kB|\le C^k|B|$. In injective linear modelling of a small sumset, the image has density at least $1/(4C^{12})$. The Finite-field Bogolyubov lemma finds a subspace of codimension at most $\lceil 32C^{24}\rceil$ in its fourfold sumset.

After lifting a subspace through a Freiman model, obtain $\tilde{W}\subseteq 4B$ with $|\tilde{W}|\ge 2^{-\lceil 32C^{24}\rceil }|B|$. The set $B+\tilde{W}\subseteq 5B$ uses at most $C^5{2}^{\lceil 32C^{24}\rceil }$ cosets. Their representatives generate a quotient group of size at most two to this number. Since $|\tilde{W}|\le C^4|B|$, adjoining those representatives and $a$ proves the displayed bound. Its constants are deliberately coarse, but depend only on $C$. The nonempty assumption is necessary: no vector subspace has cardinality at most a constant times the size of the empty set.

For a finite subset $B\subseteq {\mathbb{F}}_2^N$ containing zero, choose $m=\lceil {\log }_2(2|12B|)\rceil$ and a uniformly random linear map $L:{\mathbb{F}}_2^N\to {\mathbb{F}}_2^m$. Each fixed nonzero vector has zero image with probability $2^{-m}$. The union bound gives a map whose kernel meets $12B$ only at zero. It is injective on $6B$, and $2^m<4|12B|$. The Plünnecke-Ruzsa inequality makes the image of $B$ have density at least $1/(4C^{12})$ if $|B+B|\le C|B|$.

Under injective linear modelling of a small sumset, every $w\in W$ has a unique lift $\sigma (w)\in 4B$, because differences of two lifts lie in $8B\subseteq 12B$. For $w_1,w_2\in W$, the discrepancy $\sigma (w_1)+\sigma (w_2)+\sigma (w_1+w_2)$ lies in $12B\cap \ker L$, so it is zero. Thus $\sigma$ is a linear map and its image is a vector subspace of the same size as $W$. This verifies the additive lifting step rather than assuming that a preimage chosen from a sumset is automatically a subspace.

For fixed density $\delta >0$, rank $r$, and progression length, every sufficiently large proper coset progression of rank at most $r$ has the property that each subset of relative density at least $\delta$ contains a nontrivial arithmetic progression of that length. This follows from the multidimensional Szemerédi theorem.

For every $C$ there is $N(C)$ such that a set $A\subseteq \mathbb{Z}$ with $|A|\ge N(C)$ and $|A-A|\le C|A|$ contains a nontrivial three-term arithmetic progression. The Freiman-Ruzsa theorem places $A$ densely in a bounded-rank coset progression, where the Szemerédi theorem in a bounded-rank coset progression applies.