Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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… – Keenan Pepper Sep 20 '11 at 16:12
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.