Pairs of points exactly 1 unit apart in the plane

Question

I don't have an idea how to prove, that between any n points on the plane, there are not more than $O(n^\frac{3}{2})$ pairs with distance of 1 unit between each other... Thanks a lot for any help!

Answer 1

Weaker result :

Take a graph whose vertices are your $n$ points. We say that there is an edge joining two vertices iff the corresponding points are at distance $1$.

Then it is easy to prove that in the plane there cannot be $4$ points such that the distance between every pair of them is $1$.

Hence your graph is $K_4$ free, and you can use Turan's theorem (see Turan Theorem) : the number of edges is at most $\frac{1}{3}n^2$

---

After some researchs, the references $[48]$ and $[49]$ in this article (Distinct distances in graph drawings) should be useful : the bound they proved is proportional to $n^{\frac{4}{3}}$.

Answer 2

Number the points from $1$ to $n$, and let $m_i$ be the number of points which are at distance $1$ from the $i^\text{th}$ point. The number of pairs of points at distance $1$ is $\frac12\sum_{i=1}^n m_i$.

Consider the quantity $$ \sum_{i=1}^n \binom{m_i}2 $$ This quantity counts the number of triangles $ABC$, where each of $A,B$ and $C$ is one of the $n$ chosen points, and such that $AB=BC=1$.

I claim that $$ \sum_{i=1}^n\binom{m_i}2\le 2\binom n2\tag1 $$ Why? For each point, there are $\binom{m_i}2$ triangles $ABC$. For each of these triangles, delete the point $B$, so we get a pair of points $\{A,C\}$. So, we have a big list of $\sum_{i=1}^n \binom{m_i}2$ pairs of points, possibly with some repeats. However, each pair $\{X,Y\}$ of points can occur at most $2$ times in this big list; for any points $X,Y$, there are at most two ways to choose $Z$ in the plane such that $XZ=YZ=1$. This means that the length of the list is at most $2$ times the total number of pairs of points, proving $(1)$.

Next, since the function $x\mapsto x(x-1)/2$ is convex, using Jensen's inequality, you can show that $$ \tag2 \frac1n\sum_{i=1}^n\binom{m_i}2 \ge \binom{\frac1n\sum_{i=1}^n m_i}{2}=\binom{\frac2n (\text{# pairs at distance 1})}2 $$ Combining $(1)$ and $(2)$ proves what you want.