Unit distances: a simple question, an unexpected construction

Points spaced one apart on a line already give $n - 1$ unit distances, so $u(n)$ is at least linear. For an upper bound, note that two unit circles meet in at most two points, so no two points can share three unit-distance neighbours. Turning that observation into a count is a problem about incidences between points and circles, and Spencer, Szemerédi and Trotter (1984) proved

which is still the best upper bound known.

Take the $\sqrt{n} \times \sqrt{n}$ integer grid and call a distance $\sqrt{m}$ the unit, for a well-chosen integer $m$. The pairs at that distance correspond to ways of writing $m = a^2 + b^2$, and when $m$ is a product of many primes of the form $4k + 1$ there are unusually many: the number of representations

can be as large as $m^{c / \log \log m}$ for a constant $c > 0$.

Scaling the grid so that $\sqrt{m}$ becomes $1$ gives

Since $c / \log \log n \to 0$, this is $n^{1 + o(1)}$: barely more than linear. Erdős conjectured in 1946 that nothing does substantially better.

The grid works because of the Gaussian integers $\mathbb{Z}[i]$: $m = a^2 + b^2$ is the factorization $m = (a + bi)(a - bi)$, and many prime factors mean many such pairs. The new construction, per the companion paper, draws on algebraic number theory beyond this. If an infinite family of configurations achieves

the bound $n^{1 + o(1)}$ is false. The true growth rate then lies somewhere between $n^{1 + \delta}$ and $n^{4/3}$, and finding it remains open.