3
$\begingroup$

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)$.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Sam Hopkins
    Commented Aug 9, 2021 at 14:41
  • $\begingroup$ @SamHopkins Dear Sam, huge thanks for providing this reference! I was guessing that this must be some well known problem, but could not find a reference. If you make your comment an answer, I'll happily accept it. $\endgroup$
    – aglearner
    Commented Aug 9, 2021 at 15:07

1 Answer 1

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .