Combinatorics – Planar Subsets with Many Pairs of Points at Distance 1

co.combinatoricsdiscrete geometryopen-problemsplane-geometry

Let $X$ be a subset of $\mathbb R^2$ consisting of $n$ distinct points. Let $d_1(X)$ be the number of pairs of points of $X$ on distance $1$ from each other. Define

$$d_1(n)=\sup_{X\subset \mathbb R^2|, |X|=n}d_1(X).$$

In particular $d_1(1)=0$, $d_1(2)=1$, $d_1(3)=3$, $d_1(4)=5$, etc.

Question. I wonder what is known about the asymptotic behaviour of $d_1(n)$ and about its upper bound?

It should be at least $n\log(n)$ as the following example shows:

Example. It is easy to see that $d_1(2^d)\ge d2^d$, indeed, one can take the set $Y$ consisting of $d$ unit vectors and then take $2^Y$ consisting of sums of vectors over all $2^d$ subsets of $Y$. Then for generic $Y$ we have $|2^Y|=2^d$ and $d_1(2^Y)=d2^d$. By fiddling a bit with $Y$ one can increase $d_1(2^Y)$.

Best Answer

This is the so-called "Erdős unit distances problem"; see for instance the related Wikipedia entry or this recent survey by Szemerédi.

As you might expect, a good deal is known, but the problem is by no means resolved.