Freiman homomorphism

A Freiman homomorphism preserves additive quadruples: whenever $x_1+x_2=x_3+x_4$ in its domain, its values satisfy $\varphi (x_1)+\varphi (x_2)=\varphi (x_3)+\varphi (x_4)$.

A map $\varphi :A\to B$ is a Freiman $s$-homomorphism whenimplies the corresponding equality between the $\varphi (a_i)$. It is a Freiman $s$-isomorphism when it is bijective and the converse implication also holds.

A Freiman $s$-isomorphism is a bijection whose forward and inverse maps are both Freiman s-homomorphisms.

An eight-term Freiman isomorphism extends injectively to the two-sum/two-difference set by sending its representations to the corresponding integer differences. Independence of representation uses four-term relations, and additivity whenever $y,z,y+z$ lie in that difference set uses six-term relations. Thus a proper symmetric progression in the modeled difference set lifts, one coordinate step at a time, to a proper integer progression of the same rank and cardinality.

A Freiman 2-isomorphism is a bijection between subsets of abelian groups preserving additive quadruple relations in both directions. It need not extend to an ambient group homomorphism. Multiplication by a nonzero scalar in a finite field and translation are examples; reduction of an integer set modulo a prime is an example only when it creates no new additive relations.

If a Freiman 2-isomorphism into ${\mathbb{F}}_2^m$ uses minimal $m$, every nonzero vector lies in the fourfold sumset. Otherwise quotienting by the line it spans would preserve all additive quadruple relations and would still be injective, contradicting minimality. Since zero also belongs to the fourfold sumset, that sumset is the full model group. Plünnecke-Ruzsa inequality then bounds its size by $K^4|A|$. A finite subset of the direct sum of countably many binary fields has a finite-dimensional model to start with.

The Ruzsa modelling lemma says that a finite set with bounded doubling has a large subset Freiman $s$-isomorphic to a dense subset of a finite cyclic group, whose order is bounded by a constant depending only on the doubling constant and $s$ times the original set size.

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.

Let $X$ be the image of all additive second differencesIf a subspace $V$ satisfies $V\cap X=\{0\}$, then the restriction of $\varphi$ to the inverse image of every coset of $V$ is a Freiman homomorphism.

Suppose every derivative $x\mapsto \varphi (x+d)-\varphi (x)$ on ${\mathbb{F}}_p^n$ takes at most $C$ values. Then $\varphi$ restricts to a Freiman homomorphism on a set of density at least $p^{-1}{C}^{-5}$. The proof bounds the second-difference image by $C^5$ and chooses a random subspace avoiding its nonzero elements.