# Minimum cardinality of a difference set in $R^n$

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

-
I added the "arithmetic-progression" tag because the solution for n=1 is any arithmetic progression, giving a difference set with cardinality $2m-1$. So in some sense the higher-dimensional solutions generalize arithmetic progressions. – Keenan Pepper Sep 20 '11 at 5:02
Please also mention on math.SE that you cross posted. – quid Sep 20 '11 at 13:14

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.