Given $n$ points in the plane, prove that less than $2n^{\frac{3}{2}}$ pairs of points are a distance 1 apart.

Question

Given $n$ points in the plane, prove that less than $2n^{\frac{3}{2}}$ pairs of points are a distance 1 apart.

It seems like Piegeon Hole Principle but I don't know how to proceed.

Answer 1

$\newcommand\ip[2]{\left\langle #1,#2\right\rangle}$

Ordered pairs or unordered pairs?

Say $S$ is the set of $n$ points. For each $p\in S$ let $$S_p=\{q\in S:|p-q|=1\},$$so the number of ordered pairs at distance $1$ from each other is $$\sum_p|S_p|$$(where $|S_p|$ is the cardinality of $S_p$).

If the $S_p$ were disjoint then that sum would be no larger than $n$. They're not disjoint, but they're sort of almost disjoint: It's clear that $$|S_p\cap S_q|\le 2\quad(p\ne q).$$

Hmm. Oh. Define $f_p:S\to\{0,1\}$ by saying $f_p(q)=1$ if and only if $q\in S_p$. (That is, $f_p$ is the indicator function, or characteristic function, of $S_p$.) And for functions $f$ and $g$ defined on $S$ let $$\ip fg=\sum_p f(p)g(p).$$If the $S_p$ were disjoint that would say the $f_p$ were orthogonal; since the $S_p$ are in a sense almost disjoint that should say the $f_p$ are in a sense almost orthogonal, so we should be able to use some inner-product stuff to get an estimate.

Note that $$\ip{f_p}{f_p}\le n$$and$$\ip{f_p}{f_q}\le 2\quad(p\ne q).$$

So Cauchy-Schwarz shows that $$\sum|S_p|=\sum_q\sum_p f_p(q)\le n^{1/2}\left(\ip{\sum f_p}{\sum f_p}\right)^{1/2}$$And $$\ip{\sum f_p}{\sum f_p}=\sum_p\ip{f_p}{f_p}+\sum_{p\ne q}\ip{f_p}{f_q}\le n(n)+n(n-1)(2)\le 3n^2.$$Substituting this above gives $$\sum|S_p|\le 3^{1/2}n^{3/2}.$$

Of course the actual number is much smaller; there are huge overestimates above. I bet it's really $O(n)$, maybe even no larger than $6n$. (And I wonder if some more subtle Fourier-analysis-ish argument gives $O(n)$; hence the added tag.)