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
    Commented Sep 20, 2011 at 5:02
  • $\begingroup$ Please also mention on math.SE that you cross posted. $\endgroup$
    – user9072
    Commented 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
    Commented Sep 20, 2011 at 21:43
  • $\begingroup$ Are things very different over the complex numbers? $\endgroup$
    – Jose Brox
    Commented 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
    Commented Aug 23, 2016 at 19:19
  • $\begingroup$ @Seva Sure, I should have thought before asking and see the obvious! Thank you $\endgroup$
    – Jose Brox
    Commented Aug 23, 2016 at 19:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .