# Minimum cardinality of a difference set in $\mathbb 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. I think this falls into the realm of "additive combinatorics" or "arithmetic combinatorics", but there aren't tags for those.)

-
Crap, I just spent an hour working on proving the maximum is $1+{m\choose2}$ and apparently this problem is about the minimum. $*$headdesk$*$ –  anon Sep 17 '11 at 4:26
It's very unlikely that the answer is known exactly. What ranges of $m,n$ interest you? Say, the asymptotic behavior for fixed $n$ and $m \to \infty$? –  Alon Amit Sep 17 '11 at 4:50
Yeah, the minimum is a much more interesting problem. It definitely depends on n because f(m=3,n=1) = 5 but f(m=3,n=2) =7. Convex lattice subsets are clearly the way to go. –  Keenan Pepper Sep 17 '11 at 4:55
On the contrary, I'm interested in exact results for small m. Why do you say exact results are so unlikely? –  Keenan Pepper Sep 18 '11 at 3:37
Cross-posted to mathoverflow.net/questions/75908/… –  Keenan Pepper Sep 20 '11 at 16:12