Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 5 down vote favorite
1

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|improve this question
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$*$ – 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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.