Cross-posted from <https://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn>.


Given a finite set $S$ of $m$ points in $\mathbb R^n$ that do not all lie in the same $(n-1)$-dimensional hyperplane, consider the set of difference vectors:


$\{x-y \, | \, x,y \in S\}$


What is the minimum cardinality of this set, as a function of $m$ and $n$?


(The sets that minimize this should be "small" subsets of a lattice, but I don't know what specific shapes minimize it.)


What is the status of exact results for this problem for small $n$ (say $n = 2$ or $3$)?



Minimum cardinality of a difference set in $R^n$
A basic inequality proved in 1987 by Freiman, Heppes, and Uhrin ("A lower estimation for the cardinality of finite difference sets in $R^n$", Number theory, Vol. I (Budapest, 1987), 125–139, Colloq. Math. Soc. János Bolyai, 51, North-Holland, Amsterdam, 1990) is that $|S-S|\ge(n+1)|S|-n(n+1)/2$. A number of improvements have been obtained since then; in particular, Stanchescu ("On finite difference sets", Acta Math. Hungarica 79 (1998), no. 1-2, 123–138) showed that for $n=3$ one has $|S-S|\ge 4.5|A|-9$, with an explicit description of those sets $S$ for which equality is attained. 


You can recover much more starting with these two papers and their MathReviews.


