How many pairs can be one apart

Place $n$ points anywhere in the plane and count the pairs that are exactly one unit apart. How large can that count be? Paul Erdős asked in 1946, and the question — the unit distance problem — looks as if it should be easy. It is not. The best constructions and the best upper bound differ by a power of $n$, and neither has improved since 1984.

The obvious arrangements are poor. Points in a row, one apart, give $n - 1$ pairs. A patch of the triangular lattice, every point with six neighbours one apart, gives close to $3n$. The square grid gives close to $2n$ with its spacing as the unit. All three are linear in $n$, and the first surprise is that a linear count is not the best possible: by choosing the unit cleverly, a grid can give more than any constant times $n$.

One grid, a better unit #

Take a square grid of 12 by 12 points and ask not which pairs are one spacing apart but which pairs are five apart. A step of $(5, 0)$ or $(0, 5)$ does it, and so do $(3, 4)$ and $(4, 3)$, with any signs.

At distance 5 the grid has 456 pairs, against 264 at distance 1. The reason is directions. Distance 1 is realised in only two directions, horizontal and vertical. Distance 5 is realised in six: along the axes and along the four diagonals of the 3–4–5 triangle. Each direction contributes about $n$ pairs, less the ones that fall off the edge, and the extra directions more than pay for the longer steps losing more pairs at the edges.

Rescaling the grid so that 5 becomes the unit changes nothing about the count. So among 144 points the plane allows at least 456 pairs one unit apart, which already beats the triangular lattice’s roughly 3 per point. The whole construction consists of choosing the distance.

Every pair is a point on a circle #

A pair of points at distance $r$ can be read another way: each point lies on the circle of radius $r$ drawn about the other. Counting pairs at one distance is counting incidences between the points and the circles of that radius centred on them.

That reformulation is what connects the problem to the geometry of circles through a point, and it is where both the constructions and the upper bound come from. A construction wants circles that each pass through many of the points. The upper bound needs a reason that $n$ circles cannot all pass through too many of $n$ points — and the basic reason is elementary: two different circles meet in at most two points. So two points cannot both lie on three of the circles, which would mean three circles sharing two points.

In graph terms, the unit-distance graph contains no complete bipartite graph $K_{2,3}$: no two points have three common neighbours at unit distance. A graph with that restriction has at most about $n^{3/2}$ edges, by the same counting of pairs of neighbours that bounds the densest graph without a square. That was Erdős’s first upper bound, and it is already much less than the $n^2/2$ pairs there are in all.

Directions come from primes #

The grid’s best distance at each size is decided by how many lattice vectors have that length, and that is a question about sums of two squares.

Most numbers are not sums of two squares at all, and those that are usually have only a few representations. The numbers with many are products of many primes of the form $4k + 1$ — 5, 13, 17, 29 and so on — because each such prime is a sum of two squares in essentially one way, and multiplying sums of two squares combines representations. The number $5 = 1 + 4$ has eight signed, ordered representations; $25$ has twelve; $65 = 5 \cdot 13$ has sixteen; $325 = 5^2 \cdot 13$ has twenty-four. Each representation is a direction in which the grid realises that length. Finding the directions for a given $m$ is itself a small computation: each prime factor of the form $4k + 1$ has to be split into its two squares, which a half-run of Euclid’s algorithm does quickly, and the splittings are then multiplied together in every combination of signs and conjugates. For 325 the representations are $1^2 + 18^2$, $6^2 + 17^2$ and $10^2 + 15^2$, each in both orders and with every choice of signs: twenty-four vectors, twelve directions.

The table was made by counting, for every grid size, the pairs at every possible distance and keeping the best. The smaller grids were also checked pair by pair. The winning squared distance is 1 for a 4-by-4 grid, 5 up to 8 by 8, 25 at 12 and 16, 65 from 20 to 40, and 325 at 48 and beyond — each one a product of primes of the form $4k + 1$, and each switch happening when the grid is large enough that the extra directions outweigh the extra length. Pairs per point climb steadily, from 1.5 to 8.8 over grids of 16 to 6,400 points.

Erdős turned this into a general construction. Take a grid of $n$ points and choose a squared distance $m$ that is a product of many small primes of the form $4k + 1$, small enough that the steps still fit inside the grid. The number of representations grows faster than any constant, and the count of pairs comes out as $n^{1 + c/\log\log n}$ for a constant $c$: more than any constant times $n$, but less than $n^{1 + \varepsilon}$ for every fixed $\varepsilon$, once $n$ is large enough.

Why the unit changes as the grid grows #

The switches in the table have a simple mechanism. A step $(x, y)$ inside an $s$-by-$s$ grid can start from $(s - |x|)(s - |y|)$ points and still land inside, so a long step wastes a band of starting points along two edges. For a small grid that waste is severe: in an 8-by-8 grid a step of length 5 along an axis can start from only $3 \times 8$ points, a quarter of the grid. For a large grid the waste is a thin border and hardly matters, and what matters is only how many directions the length has.

So each candidate distance trades directions against waste, and the balance tips as the grid grows. Distance $\sqrt5$, with four directions, beats distance 1, with two, once the grid is 6 points on a side. Distance 5, with six, beats $\sqrt5$ at 12. Distance $\sqrt{65}$, with eight, takes over at 20, and $\sqrt{325}$, with twelve, at 48. Every step up in directions needs a larger grid to pay for its longer steps, which is exactly why the count per point grows so slowly: to use a distance with $d$ directions the grid must be large compared with that distance, and numbers with many representations are large.

The same trade explains the shape of Erdős’s bound. The number of representations of $m$ as a sum of two squares can be as large as about $m^{c/\log\log m}$, and no larger; to use such an $m$ the grid needs side a few times $\sqrt m$; and putting those together gives the count $n^{1 + c/\log\log n}$. The exponent is small because numbers are rarely sums of two squares in many ways, and that is a fact about primes.

The triangular lattice’s own primes #

The triangular lattice does even better than the square grid at the sizes drawn, and for the same reason with different primes. Its points can be written as $a + b\omega$ with $\omega$ a cube root of unity, and the squared distance between two of them is $a^2 + ab + b^2$. The numbers of that form with many representations are products of primes of the form $3k + 1$ — 7, 13, 19, 31 — for the same reason as before: each such prime splits in the arithmetic of $\omega$, and multiplying combines the splittings.

The computation finds exactly those distances. For hexagonal patches of 37 to 331 points the best squared distance is 7, realised in six directions against the three of the unit; from 469 points on it is $91 = 7 \times 13$, realised in twelve. A patch of 1,261 points has 10,200 pairs at distance $\sqrt{91}$, about 8.1 per point, against the square grid’s 5.6 at a similar size. The triangular lattice starts with three directions for free where the square grid has two, and keeps the advantage.

Neither lattice changes the asymptotic answer. Both give $n^{1 + c/\log\log n}$ with different constants, and no other construction is known that does better by more than a constant factor in the exponent’s constant.

The four-thirds bound #

The best upper bound came in 1984 from Joel Spencer, Endre Szemerédi and William Trotter: the number of unit distances among $n$ points is at most a constant times $n^{4/3}$. Their proof bounded the incidences between points and circles by cutting the plane into cells, each containing few points and crossed by few circles, and adding up the cells.

László Székely found a much shorter proof in 1997, and it is one of the best-known applications of the crossing lemma. Draw the unit circles about the points, discarding the ones through fewer than three points, and read the arrangement as a drawing of a graph: the points are vertices and the arcs of the circles between consecutive points are edges. Two circles cross at most twice, so the drawing has at most about $2n^2$ crossings. The crossing lemma says a graph with many more edges than vertices must have many crossings — at least a constant times $e^3/v^2$ — and comparing the two gives at most a constant times $n^{4/3}$ edges, which is the bound.

So pairs per point can grow at most like $n^{1/3}$, and the grid constructions grow like $n^{c/\log\log n}$. Everything known lies between those two rates.

Small cases lie #

At the sizes anyone can compute, the two rates are hard to tell apart.

The triangular lattice at unit spacing flattens out below three pairs per point, as it must: each point has only six neighbours at distance one. Choosing a distance lifts both lattices far above that, and the triangular lattice at its own best distance — lengths like $\sqrt7$ and $\sqrt{91}$, realised in many directions of that lattice — does even better than the square grid. And over the range drawn, sixteen points to several thousand, both chosen-distance constructions rise at about the same rate as the $n^{1/3}$ curve.

That is not evidence that the upper bound is right. The function $n^{c/\log\log n}$ grows slower than every power of $n$ only eventually, and “eventually” here means sizes far beyond any drawing: at a few thousand points, $\log\log n$ is barely above two, and $n^{c/\log\log n}$ behaves like a power of about a third. The small cases say nothing about which rate is the true one. Erdős conjectured that the constructions are essentially best — that the answer is $n^{1 + o(1)}$ — and offered a prize for a proof.

A related question that was answered #

A sister problem, also Erdős’s from 1946, asks the opposite: among $n$ points, how few distinct distances can there be? The square grid again gives the best constructions, with about $n / \sqrt{\log n}$ distinct distances, and for sixty years the lower bounds crept upward by small exponents.

In 2010 Larry Guth and Nets Katz proved that $n$ points always determine at least a constant times $n / \log n$ distinct distances, matching the grid up to a factor of $\sqrt{\log n}$. Their proof used incidence bounds for lines in three-dimensional space and the polynomial method, a set of tools that did not exist when the problem was posed. The distinct distances problem is now essentially closed. The unit distance problem, which asks about the most common distance rather than the number of distances, has not yielded to the same methods: its difficulty is the circles, which in the distinct distances problem could be traded for lines.

The colouring question next door #

A unit-distance graph — the points as vertices, the pairs one apart as edges — is also the object of the question of how many colours the plane needs, so that no two points one apart share a colour. The two questions pull in different directions. Colouring cares about small, tightly knotted configurations, like the Moser spindle and de Grey’s graph, that force many colours; the unit distance problem cares about large, evenly spread configurations with as many edges as possible.

They meet less than one might expect, because many edges do not force many colours. Every record grid in the table uses an odd squared distance — 1, 5, 25, 65, 325 — and a step $(x, y)$ with $x^2 + y^2$ odd has $x + y$ odd, so it always joins a point with $x + y$ even to one with $x + y$ odd. Colour the grid like a chessboard and no two points one unit apart share a colour. The densest constructions known for the unit distance problem need only two colours, while the configurations that force five colours are sparse, irregular and small. The two problems study the same graphs and reward opposite features of them.

What the counting cannot show #

The counts are exact: every pair of every grid is counted by direction and the smaller grids pair by pair, and the triangular patches are counted by brute force over all pairs. What the figures show is what these particular constructions achieve at these particular sizes, and nothing more. The best arrangement of $n$ points need not be a piece of a lattice at all; for small $n$ the known record configurations are irregular, found by computer search, and the lattices are not optimal there.

The reference curve is drawn through the first grid point to show a shape of growth, not the upper bound itself, which has a constant that is not tight. And the log-log picture over three orders of magnitude cannot separate $n^{1/3}$ from $n^{c/\log\log n}$; that separation is a theorem about the limit, and no computation reaches it.

Still open: the exponent #

The number of unit distances among $n$ points is at least $n^{1 + c/\log\log n}$ and at most a constant times $n^{4/3}$. Whether the true exponent is 1, as Erdős believed, or $4/3$, or something between, is unknown. The upper bound has resisted every attempt at improvement for four decades, and the reason is understood in outline: the Spencer–Szemerédi–Trotter bound is sharp for points and lines, and any improvement for circles must use something specific to circles of one fixed radius that lines do not have.

The problem is also sensitive to the space it lives in. In three dimensions the best bounds are different, and in four dimensions the question collapses: points on two orthogonal circles of radius $1/\sqrt2$ give about $n^2/4$ unit distances, a positive fraction of all pairs. The plane sits between a trivial case and an impossible one, and the only tool that reached its version of the question, the crossing of circles, stops at four-thirds.

What a unit is for #

The construction that beats the obvious arrangements does nothing to the points; it chooses the unit. A grid has one spacing and many distances, and the distance it realises most often is the one whose square has the most representations as a sum of two squares. So a geometric question about pairs of points at one distance turns, at every size, into an arithmetic question about which numbers are sums of two squares in many ways — and the answer to that is controlled by primes of the form $4k + 1$. The upper bound, meanwhile, is pure geometry: two circles meet at most twice. The truth lies somewhere between an argument about primes and an argument about crossings, and no one knows which of the two is closer to it.