Take the 2-minute tour ×
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.

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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.