= Solution
A <Freiman 2-isomorphism> is an <injective> map onto its image preserving pair-sum equality in both directions, with repeated summands allowed. Put $D=2A-2A$, so $D=-D$, $0\in D$, and $|D|<N$. We prove the <half-size cyclic Freiman model with a sharp difference-set bound>. Assume $A\ne\varnothing$; for an empty <set> the conclusion is immediate.
Choose an odd auxiliary <prime> $P>N$ large enough that reduction modulo $P$ is <injective> on $A$ and no nonzero element of $D$ reduces to zero. Choose a multiplier $t$ uniformly in $\mathbb Z_P^\times$. The forbidden residues are
$$
\mathcal F=\{jN\pmod P: j\in\mathbb Z,\ 0<|jN|<P\}.
$$
They form a symmetric <set>, exclude zero since $P>N$, and have <cardinality> at most $2\lfloor(P-1)/N\rfloor$. For each nonzero $d\in D$, the product $td$ is uniform on the $P-1$ nonzero residues. Moreover, $td\in\mathcal F$ is the same event as $t(-d)\in\mathcal F$, so one need only sum over the $(|D|-1)/2$ opposite pairs. The <union bound> gives
$$
\Pr\bigl(td\in\mathcal F\text{ for some }d\in D\setminus\{0\}\bigr)\leq\frac{|D|-1}{2}\frac{2\lfloor(P-1)/N\rfloor}{P-1}\leq\frac{|D|-1}{N}<1.
$$
Fix a multiplier avoiding all forbidden events. The use of opposite pairs is what achieves the threshold $N>|D|$ without an extra factor of two.
Represent each $ta\pmod P$ by an <integer> $r(a)\in\{0,\ldots,P-1\}$. Partition these residues into the two half-intervals
$$
I_0=\{0,\ldots,(P-1)/2\},\qquad I_1=\{(P+1)/2,\ldots,P-1\}.
$$
At least half of $A$ has representatives in one of them; call this <subset> $A'$. Both intervals have diameter less than $P/2$, so for $a_1,a_2,a_3,a_4\in A'$ the <integer>
$$
R=r(a_1)+r(a_2)-r(a_3)-r(a_4)
$$
satisfies $|R|<P$.
Define $\phi(a)=r(a)\pmod N$. If $a_1+a_2=a_3+a_4$, then $R\equiv0\pmod P$, hence $R=0$ and the image relation holds. Conversely, if the image relation holds, then $R=jN$. If the original difference $d=a_1+a_2-a_3-a_4$ were nonzero, $R\equiv td\pmod P$ would be nonzero; since $|R|<P$, this would be a forbidden residue in $\mathcal F$. Thus $d=0$.
Finally $\phi$ is <injective>. If $\phi(a)=\phi(b)$, choose any $c\in A'$ and apply the converse to $\phi(a)+\phi(c)=\phi(b)+\phi(c)$, obtaining $a+c=b+c$. Therefore
$$
\boxed{|A'|\geq|A|/2,\qquad\phi:A'\longrightarrow\phi(A')\subseteq\mathbb Z_N\text{ is a Freiman 2-isomorphism}.}
$$
The construction actually works for any <integer> $N>|D|$; the <prime> hypothesis in the question is sufficient.
Back to article page
