Plünnecke–Ruzsa inequality

Ruzsa covering lemma

The Ruzsa covering lemma states the following:

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

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

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

Freiman homomorphisms and the Ruzsa modeling lemma

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

${\displaystyle \varphi (a_{1})+\cdots +\varphi (a_{s})=\varphi (a_{1}')+\cdots +\varphi (a_{s}')}$

whenever ${\displaystyle a_{1}+\cdots +a_{s}=a_{1}'+\cdots +a_{s}'}$ for any ${\displaystyle a_{1},\ldots ,a_{s},a_{1}',\ldots ,a_{s}'\in A}$.

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

If ${\displaystyle \varphi }$ is a Freiman ${\displaystyle s}$-homomorphism, then ${\displaystyle \varphi }$ is a Freiman ${\displaystyle t}$-homomorphism for any positive integer ${\displaystyle t}$ such that ${\displaystyle 2\leq t\leq s}$.

Then the Ruzsa modeling lemma states the following:

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

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

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

Let ${\displaystyle A\in \mathbb {F} _{2}^{n}}$ and let ${\displaystyle \alpha =|A|/2^{n}}$. Then ${\displaystyle 4A}$ contains a subspace of ${\displaystyle \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. Let ${\displaystyle R}$ be a subset of ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$ where ${\displaystyle N}$ is a prime. The Bohr set of dimension ${\displaystyle |R|}$ and width ${\displaystyle \varepsilon }$ is

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

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

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

Here the dimension of a Bohr set is analogous to the codimension of a set in ${\displaystyle \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 ${\displaystyle X}$ be a Bohr set in ${\displaystyle \mathbb {Z} /N\mathbb {Z} }$ of dimension ${\displaystyle d}$ and width ${\displaystyle \varepsilon }$. Then ${\displaystyle X}$ contains a proper generalized arithmetic progression of dimension at most ${\displaystyle d}$ and size at least ${\displaystyle (\varepsilon /d)^{d}N}$.

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