Doubling constant ($|A+A|/|A|$)

The doubling constant of a nonempty finite set $S\subseteq G$ in an abelian group $G$ isIt measures the cardinality of the sumset relative to the original set. For the integer examples, $K(A)=7/4$ and $K(B)=10/4=5/2$. A nonconstant arithmetic progression with $n$ members has doubling constant $(2n-1)/n$, which stays below two as $n$ grows. This is the sense in which its sumset has small growth.

In any abelian group, $K(S)\ge 1$: fixing $s_0\in S$ puts a translated copy $s_0+S$ inside $S+S$. The stronger integer bound gives $K(S)\ge 2-1/|S|$ only in that setting. A finite subgroup $H$ has $K(H)=1$, as does every coset $x+H$, since its sumset is $2x+H$. In particular $H=\{0,2,4\}\subseteq \mathbb{Z}/6\mathbb{Z}$ has doubling constant one.

Small doubling constant is useful because it constrains repeated growth, as in the Plünnecke-Ruzsa inequality. It signals structure such as arithmetic progressions and subgroups; precise descriptions depend on the ambient abelian group and are the subject of the Freiman-Ruzsa theorem. The additive energy bound below gives a simpler immediate consequence: $E(S)\ge |S{|}^3/K(S)$.

For a finite nonempty subset of an abelian group with doubling constant at most $K$, the Plünnecke-Ruzsa inequality gives $|3A-2A|\le K^5|A|$. Applying the Ruzsa covering lemma to $2(A-A)$ using $A$ gives $2T\subseteq D+T$ for $T=A-A$ and $|D|=q\le K^5$. Thus $\ell T\subseteq (\ell -1)D+T$, and counting multiplicities in the finite set $D$ proves the displayed polynomial bound. For fixed $K>1$, it is eventually at most $K^{ϵ\ell }|A|$ for every $ϵ>0$.

If finite sets satisfy $|A+B|\le K|A|$, then the Plünnecke-Ruzsa inequality bounds iterated sumsets and difference sets by

If a nonempty finite set $X$ minimizes $|X+B|/|X|$ among the nonempty subsets of $A$, with minimum $K^{\prime }$, thenfor every finite set $C$. Iteration is a short proof of the Plünnecke-Ruzsa inequality.

For finite subsets $A,B,C$ of an abelian group with $A$ nonempty,An injective encoding chooses one representation of each element of $B-C$ and translates it by every element of $A$.

For nonempty finite subsets $A,B,C$ of an arbitrary group,Choose one representation $x=b_x{c}_x^{-1}$ for each $x\in B{C}^{-1}$. The map $(a,x)\mapsto (a{b}_x^{-1},a{c}_x^{-1})$ is injective.

If a finite subset $A$ of a group satisfies $|A^3|\le K|A|$, then repeated use of the Noncommutative Ruzsa triangle inequality gives

Let $H$ be a finite subgroup and choose $x$ with $H\cap xH{x}^{-1}=\{1\}$. For $A=H\cup \{x\}$, the set $A^2$ has size at most $3|H|+1$, while $A^3$ contains the double coset $HxH$ of size $|H{|}^2$. Thus bounded doubling alone gives no tripling bound in arbitrary groups.

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.