7
$\begingroup$

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.)

  • 0
    Cross-posted to http://mathoverflow.net/questions/75908/minimum-cardinality-of-a-difference-set-in-rn2011-09-20

1 Answers 1

2

The question has an accepted answer at MO.

I am posting the link here (as a CW answer) so that the question does not remain unanswered.