7
$\begingroup$

Cross-posted from https://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$)?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Keenan Pepper
    Sep 20, 2011 at 5:02
  • $\begingroup$ Please also mention on math.SE that you cross posted. $\endgroup$
    – user9072
    Sep 20, 2011 at 13:14

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Keenan Pepper
    Sep 20, 2011 at 21:43
  • $\begingroup$ Are things very different over the complex numbers? $\endgroup$
    – Jose Brox
    Aug 23, 2016 at 18:52
  • $\begingroup$ @Jose Brox: with any finite set $S\subset {\mathbb C}^n$ you can associate a set $T\subset {\mathbb R}^{2n}$ such that $|T|=|S|$ and $|S-S|=|T-T|$, cannot you? $\endgroup$
    – Seva
    Aug 23, 2016 at 19:19
  • $\begingroup$ @Seva Sure, I should have thought before asking and see the obvious! Thank you $\endgroup$
    – Jose Brox
    Aug 23, 2016 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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