Freiman-isomorphic sets

Question

Haw can we prove that an arbitrary set $A$ of $n$ positive integers is 2-Freiman isomorphic to a subset of {$ 1,2,...,4^{n}$} and $4^{n}$ cannot be improved to $2^{n}$?

Answer 1

It is an open conjecture from a paper of Konyagin and myself that every $n$-element set of integers is Freiman-isomorphic to a subset of $[0,2^{n-2}]$. There are some counterexamples for small values of $n$, but it is believed that the conjecture is "essentially true"; if so, your $4^n$ actually can be improved to $2^n$ (and in fact, to $2^{n-2}+1$). No further improvements are possible: the set $\{0,1,2,4,\dotsc,2^{n-2}\}$ is not isomorphic to any shorter integer set. (If it is isomorphic to a set $\{a_0,a_1,\dotsc, a_{n-1}\}$, then $a_0+a_2=2a_1$, $a_0+a_3=2a_2$, ... , $a_0+a_{n-1}=2a_{n-2}$; assuming without loss of generality $a_0=0$, this results in $a_i=2^{i-1}a_1$, so that the diameter of $\{a_0,a_1,\dotsc, a_{n-1}\}$ is $|a_{n-1}-a_0|\ge 2^{n-2}$.)

The bound $8^n$ (somewhat weaker than you indicated) can be obtained as follows.

It suffices to show that if $A\subseteq[0,l]$ is an $n$-element integer set not isomorphic to a set of diameter smaller than $l$, then $l<8^n$. Write $A=\{a_1,\dotsc,a_n\}$ and fix a prime $2l<p\le 4l$, so that $A$ is isomorphic to its image $A_p$ under the canonical homomorphism $\Bbb Z\to\Bbb Z/p\Bbb Z$.

Consider the $n$-dimensional integer lattice $\Lambda:=(a_1,\dotsc, a_n)\Bbb Z+p\Bbb Z^n$. It is easily seen that the determinant of this lattice is $p^{n-1}$; hence, by Minkowski's First Theorem, $\Lambda$ has a non-zero point in the $n$-dimensional cube $[-p^{1-1/n},p^{1-1/n}]^n$. Consequently, there exist integers $y_1,\dotsc,y_n\in[-p^{1-1/n},p^{1-1/n}]$, not all equal to $0$, such that for yet another integer $z$ we have $y_i\equiv za_i\ (i\in[1,n])$. It is immediately seen that $z\not\equiv 0\pmod p$; hence, the set $\{y_1,\dotsc,y_n\}$ is isomorphic to $A_p$, and therefore to $A$. The assumption that $A$ is not isomorphic to a set of diameter smaller than $l$ implies now $2p^{1-1/n}\ge l$. Combining this with $p\le 4l$ yields the desired bound $l<8^n$.

For $l$ large, the prime $p$ can be chosen to satisfy $p=(2+o(1))l$, leading to $l<4^{(1+o(1))n}$. Much better estimates (something like $2^{(1+o(1))n}$, I believe) can be obtained using the method of the aforementioned paper; see also Chapter 20 of the monograph Structural Additive Theory by David Grynkiewicz.