most recent 30 from http://mathoverflow.net 2013-05-24T02:00:42Z http://mathoverflow.net/feeds/question/75908 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75908/minimum-cardinality-of-a-difference-set-in-rn Keenan Pepper 2011-09-20T04:59:50Z 2011-09-20T07:23:27Z

<p>Cross-posted from <a href="http://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn" rel="nofollow">http://math.stackexchange.com/questions/65195/minimum-cardinality-of-a-difference-set-in-mathbb-rn</a>.</p> <p>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:</p> <p><code>$\{x-y \, | \, x,y \in S\}$</code></p> <p>What is the minimum cardinality of this set, as a function of $m$ and $n$?</p> <p>(The sets that minimize this should be "small" subsets of a lattice, but I don't know what specific shapes minimize it.)</p> <p>What is the status of exact results for this problem for small $n$ (say $n = 2$ or $3$)?</p>

http://mathoverflow.net/questions/75908/minimum-cardinality-of-a-difference-set-in-rn/75918#75918 Seva 2011-09-20T07:23:27Z 2011-09-20T07:23:27Z

<p>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. </p> <p>You can recover much more starting with these two papers and their MathReviews.</p>