Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Cross-posted from http://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn.

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

What is the status of exact results for this problem for small $n$ (say $n = 2$ or $3$)?

share|improve this question
2  
I added the "arithmetic-progression" tag because the solution for n=1 is any arithmetic progression, giving a difference set with cardinality $2m-1$. So in some sense the higher-dimensional solutions generalize arithmetic progressions. –  Keenan Pepper Sep 20 '11 at 5:02
    
Please also mention on math.SE that you cross posted. –  quid Sep 20 '11 at 13:14
add comment

1 Answer 1

up vote 7 down vote accepted

A basic inequality proved in 1987 by Freiman, Heppes, and Uhrin ("A lower estimation for the cardinality of finite difference sets in $R^n$", Number theory, Vol. I (Budapest, 1987), 125–139, Colloq. Math. Soc. János Bolyai, 51, North-Holland, Amsterdam, 1990) is that $|S-S|\ge(n+1)|S|-n(n+1)/2$. A number of improvements have been obtained since then; in particular, Stanchescu ("On finite difference sets", Acta Math. Hungarica 79 (1998), no. 1-2, 123–138) showed that for $n=3$ one has $|S-S|\ge 4.5|A|-9$, with an explicit description of those sets $S$ for which equality is attained.

You can recover much more starting with these two papers and their MathReviews.

share|improve this answer
    
I have no idea why I didn't come across this paper on my own, because I was using all those search terms. Now it should be easier for others to find. –  Keenan Pepper Sep 20 '11 at 21:43
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.