= Half-size cyclic Freiman model with a sharp difference-set bound
{title2=$N>|2A-2A|\Longrightarrow |A\prime|\geq|A|/2$}
For a finite nonempty <integer> <set> $A$, put $D=2A-2A$. If an <integer> $N>|D|$, some $A'\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.
Back to article page
