Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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). –  Omar Antolín-Camarena Dec 11 '12 at 18:19
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}$. –  Omar Antolín-Camarena Dec 11 '12 at 18:26
    
What do you mean by $\{x, y\} \in \mathbb{R}^d$? –  WimC Dec 11 '12 at 18:54
    
@Omar thank you, why didnt you put it as an answer? –  CBenni Dec 11 '12 at 19:03
    
@WimC typo. I meant $\{x,y\}\subset A$ –  CBenni Dec 11 '12 at 19:03
show 2 more comments

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  hardmath Dec 13 '12 at 16:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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