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

  • 3
    Crap, I just spent an hour working on proving the maximum is $1+{m\choose2}$ and apparently this problem is about the **minimum**. $*$headdesk$*$2011-09-17
  • 0
    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$?2011-09-17
  • 0
    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.2011-09-17
  • 0
    On the contrary, I'm interested in exact results for small m. Why do you say exact results are so unlikely?2011-09-18
  • 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.