# Maximum number of points with distance 1 in finite subsets of $\mathbb{R}^d$

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?

-
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
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

## 1 Answer

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.

-
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