The Erdős Unit-Distance Problem

Take $n$ points, scattered anywhere you like on a flat page. Draw a line between every pair that happens to be exactly one unit apart — say, exactly one inch. How many lines can you possibly draw?

In 1946, Paul Erdős asked exactly this question, and it turned out to be far subtler than it looks. With only 2 points you get at most 1 unit-distance pair; with 3 you can get a unit equilateral triangle, giving 3. But as $n$ grows, what is the largest number of unit-distance pairs achievable, as a function of $n$?

Erdős found a clever arrangement that does surprisingly well — better than most people's first guess — and conjectured it was close to the truth. Eighty years later, nobody has proven he was right, and nobody has found anything better either.

Erdős's own construction is almost embarrassingly simple: take an $\sqrt{n} \times \sqrt{n}$ grid of points, spaced one unit apart. Below, grow the grid and watch the unit-distance edges (drawn in red) appear between every pair of adjacent points.

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label class="lbl">{{lbl_size}} <span id="sizeVal">4</span></label>
  <input type="range" id="size" min="2" max="9" value="4" step="1">
  <div class="modebtns">
    <button id="modeSquare" type="button" class="mode active">{{btn_square}}</button>
    <button id="modeTri" type="button" class="mode">{{btn_tri}}</button>
  </div>
</div>
<svg id="canvas" viewBox="0 0 320 320"></svg>
<div class="stats" id="stats"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .8rem; margin-bottom: .6rem; }
.lbl { font: 600 14px system-ui, sans-serif; color: #1d3557; display: flex; gap: .4rem; align-items: center; }
input[type="range"] { accent-color: #1d3557; }
.modebtns { display: flex; gap: .4rem; }
button.mode { font: 600 13px system-ui, sans-serif; padding: .35rem .7rem; border: 1px solid #1d3557;
         background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; }
button.mode.active { background: #1d3557; color: #fff; }
svg#canvas { width: 100%; max-width: 320px; height: auto; display: block; background: #f7f9fb;
         border: 1px solid #dde4ea; border-radius: 8px; margin: .3rem 0; }
.pt { fill: #1d3557; }
.edge { stroke: #e63946; stroke-width: 1.6; }
.stats { font-size: .95rem; font-weight: 600; color: #1d3557; margin-top: .3rem; line-height: 1.5; }
.stats .n { color: #e63946; }

// Code not found

Notice how the edge count grows a little faster than $n$ itself — each interior point contributes several unit-distance neighbors. Erdős showed that with a cleverer, number-theoretic tweak to the grid spacing, you can squeeze out even more unit-distance pairs than the naive square grid gives you, roughly $n^{1 + c/\log\log n}$ of them for some constant $c > 0$. Toggle between the square and triangular grid to see how packing choice changes the count.

So what do we actually know, and what is still guesswork?

• The construction (lower bound). Erdős's grid — refined using the fact that integers have many ways to be written as a sum of two squares — produces $n^{1+c/\log\log n}$ unit-distance pairs for some constant $c > 0$. This grows just barely faster than linearly in $n$: the exponent creeps above 1 but the rate of creep shrinks as $n$ grows.
• The conjecture. Erdős believed this grid was essentially optimal — that no configuration of $n$ points can beat $n^{1+o(1)}$ unit-distance pairs, where the $o(1)$ hides that vanishingly slow growth.
• The best proven upper bound. Nobody can rule out something much bigger. Using their celebrated theorem on incidences between points and lines, Joel Spencer, Endre Szemerédi and William Trotter proved in 1984 that the number of unit-distance pairs among $n$ points is always $O(n^{4/3})$.
• The gap. $n^{4/3}$ is polynomially larger than $n^{1+o(1)}$ — a gap of an entire power of $n$, not just a constant factor. Closing it — proving a bound closer to $n^{1+o(1)}$, or finding a construction that beats the grid — has resisted every attempt for decades.

This is what makes the problem a genuine open question rather than a "just hasn't been written up yet" exercise: the upper and lower bounds disagree by a growing polynomial factor, and nobody knows which side is closer to the truth.

The unit-distance problem is not just a curiosity — it is one of the founding questions of an entire field:

• Incidence geometry. The Szemerédi–Trotter machinery built to attack this problem — bounding how many times points can lie on lines or curves — is now a standard tool used across combinatorics and theoretical computer science.
• The distinct-distances problem. Erdős's sister question — how few distinct distances can $n$ points determine — was resolved much more precisely (Guth–Katz, 2015) using similar algebraic techniques, showing this style of geometric argument really can be pushed to a tight answer. It sits in the same neighborhood as other classic point-configuration puzzles, like the Happy Ending problem about convex polygons hiding inside any large enough set of points.
• Algorithm design. Counting or bounding repeated distances shows up in range searching, nearest-neighbor data structures, and collision-detection routines — anywhere geometry needs to reason about how "clustered" a point set can be.
• A benchmark for new techniques. Because the bounds are so far apart and the statement is so simple, any new tool in combinatorial geometry gets tried on this problem first, as a sanity check on its power.

A question you could pose to a child — "how many pairs of dots are exactly one apart?" — turned into a laboratory for the mathematics of points, lines and curves.

The unit-distance problem is open: we know a construction achieving roughly $n^{1+c/\log\log n}$ unit-distance pairs, we know no configuration can exceed $O(n^{4/3})$, and the true answer somewhere between them has resisted every attack since 1946.

Erdős himself offered $500 for resolving it — a modest bounty by the standards of his other prizes, but a sign of how much he wanted someone to close the gap. Whether the grid is already the best you can do, or a smarter arrangement is waiting to be found, is still anyone's guess — much like the broader mystery of P vs NP, where a believable answer and a proof of that answer remain stubbornly far apart.