2
$\begingroup$

What is the maximum number of unordered tupels of 2 points in finite subsets (with n elements for future reference) of $\mathbb{R}^d$ that have distance 1 to eachother; in other words, $m=\max_{A\subset\mathbb{R}^d,|A|=n} |\{\{x,y\}\subset A \mid \|x-y\|=1\}|$

Obviously, $m\le \frac{n^2-n}{2}$, for this is when every point in A has distance 1 to any other point in A. This is only achieved for $n\lt d$; To what value can the upper bound be set for $n\ge d$? There will always be such a set A for which the maximum is achieved, how is such a solution constructed?

  • 0
    @Omar I guess, if not even "real" mathematicians can solve this, there will be little chance I will ^.^ I have accepted your answer however, as it is the most accurate answer known to man. Thank you ;)2012-12-11

1 Answers 1

2

This problem is called the unit distance problem and is open even for $d=2$. Erdős proved a lower bound of the form $m \ge n^{1+c/\log\log n}$ and Spencer, Szemerédi and Trotter proved an upper bound of the form $m \le c n^{4/3}$. See the Open Problems Project's Problem 39 for references.

  • 0
    The comment you made about simplices acheiving the upper bound is also particularly relevant to the OP's question, esp. so as it concerns higher dimensions. Worth adding to your answer.2012-12-13