Ruzsa modelling lemma

For a nonempty finite set $A\subseteq \mathbb{Z}$ with bounded doubling constant and a fixed positive integer $s$, the Ruzsa modelling lemma finds a subset of size at least $c_s|A|$ that is Freiman s-isomorphic to a dense subset of a finite cyclic group. The model order is at most $C_{K,s}|A|$ when $|A+A|\le K|A|$. The cyclic Freiman model of a small-doubling integer set gives an explicit order-eight version.

The integer, or appropriate torsion-free, setting matters. If $A\subseteq {\mathbb{F}}_2^n$, then $x+x=y+y$ for every $x,y\in A$. A Freiman 2-isomorphism into a cyclic group would force $2\varphi (x)=2\varphi (y)$. All image differences would lie in its subgroup of elements killed by two, which has at most two elements. Thus no subset with more than two points can be Freiman 2-isomorphic to a cyclic model. General abelian groups need models retaining their torsion, rather than an unrestricted cyclic-model assertion.

A nonempty finite integer set has a subset of the displayed size Freiman s-isomorphic to a subset of ${\mathbb{Z}}_N$. Embed in a sufficiently large auxiliary prime modulus and randomly dilate. Avoid the residues of every nonzero multiple of $N$ of absolute value less than that prime for all nonzero members of $kA-kA$; a union bound gives a successful dilation. Retain a most-populated one of $k+1$ short intervals of representatives. Its $k$-term sum differences have absolute value less than the auxiliary prime, so reduction modulo $N$ both preserves and reflects relations. Under $|kA-kA|\le C|A|$, this gives $N\le 4C|A|+1$.

For $|A+A|\le K|A|$, one can take $q=8|8A-8A|\le 8K^{16}|A|$. Embed in a much larger prime cyclic group and choose a dilation avoiding the residues of all nonzero multiples of $q$ of absolute value below that prime for every nonzero eightfold difference. A union bound ensures such a dilation. Retain a most-populated ninth-interval of representatives. Eight-term sums then have range shorter than the prime, and reduction modulo $q$ both preserves and reflects eight-term additive relations.

For a nonempty integer set with doubling constant at most $K$, Plünnecke-Ruzsa inequality bounds $|2A-2A|$ by $K^4|A|$. Embed the set modulo a sufficiently large auxiliary prime $q$, randomly dilate it, and select the more populated of two half-intervals of representatives. Differences of two pair sums on that half have absolute value less than $q$, so the lift preserves original relations. Every nonzero original difference is uniformly dilated among nonzero residues; avoiding all residues represented by nonzero multiples of $p$ of absolute value less than $q$ has positive probability when $p>4|2A-2A|$. Reduction modulo $p$ then yields a Freiman 2-isomorphism on the selected half.

For a finite nonempty integer set $A$, put $D=2A-2A$. If an integer $N>|D|$, some $A^{\prime }\subseteq A$ of size at least $|A|/2$ has a Freiman 2-isomorphism into $\mathbb{Z}/N\mathbb{Z}$. Choose an auxiliary prime $P>N$ so large that reduction is injective on $A$ and every nonzero element of $D$ remains nonzero. Dilate modulo $P$ by a uniformly chosen nonzero multiplier. The forbidden residues are those represented by nonzero multiples of $N$ of absolute value less than $P$, at most $2\lfloor (P-1)/N\rfloor$ residues. The nonzero elements of $D$ occur in opposite pairs; the two elements in each pair have the same bad event. The union bound therefore gives failure probability at most $(|D|-1)/N<1$. Choose a multiplier avoiding all these events. Select the more populated of two half-intervals of residues modulo $P$. Differences of two pair sums of representatives then have absolute value less than $P$. An original additive relation must therefore lift to equality in the integers; conversely an equality modulo $N$ cannot have a nonzero lifted difference, by the forbidden-residue choice. Reduction modulo $N$ is the required isomorphism.