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
    There is a typo where you say $\frac{n^2-n}{2}$ is only achieved for $n < d$, you probably meant for $n \le d+1$ (a regular $d$-simplex has $d+1$ vertices, for example, an equilateral triangle has $3$ vertices and lives in the plane).2012-12-11
  • 1
    This problem is called the unit distance problem and was posed by Erdös. Even in the plane it is still open. Erdos proved a lower bound of the form $m \ge n^{1 + c/\log \log n}$ and Spencer, Szemeredi and Trotter proved an upper bound of the form $m \le c n^{4/3}$.2012-12-11
  • 0
    What do you mean by $\{x, y\} \in \mathbb{R}^d$?2012-12-11
  • 0
    @Omar thank you, why didnt you put it as an answer?2012-12-11
  • 0
    @WimC typo. I meant $\{x,y\}\subset A$2012-12-11
  • 0
    I misread the question as posing the unit distance question. My comment obviously doesn't answer that, it just says that no-one else knows how to answer at the moment, @CBenni.2012-12-11
  • 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