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}$?



Freiman-isomorphic sets
It is an open conjecture from [a paper of Konyagin and myself](http://math.haifa.ac.il/seva/Papers/colifr.dvi) 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](https://en.wikipedia.org/wiki/Minkowski%27s_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. 


