The Erdős distinct distances problem

How few distinct distances can $n$ points in the plane determine? A square grid of $\sqrt n\times\sqrt n$ points determines only about $n/\sqrt{\log n}$ of them, and Erdős conjectured in 1946 that no configuration does better. Guth and Katz came within a factor of $\sqrt{\log n}$ in 2015; closing that gap is the remaining question.

Problem

For a finite set $A\subset\mathbb{R}^2$ let $D(A)=\{\lvert x-y\rvert : x,y\in A,\ x\neq y\}$ be its set of distinct distances. Is it true that every set of $n$ points satisfies

\lvert D(A)\rvert \gg \frac{n}{\sqrt{\log n}}\,?

The integer grid shows that this would be best possible up to the constant. Erdős offered $500 for a solution.

Background

Erdős posed the problem in his 1946 paper on sets of distances, which also introduced the unit distance problem, and returned to it in many problem papers. The grid example rests on number theory: the distances in a $\sqrt n\times\sqrt n$ grid are square roots of integers that are sums of two squares, and there are only about $n/\sqrt{\log n}$ of those up to $n$ . Guth and Katz followed a set-up of Elekes and Sharir that turns the question into one about incidences between points and lines in three-dimensional space, and handled it with a cell decomposition from the polynomial ham sandwich theorem, now known as polynomial partitioning.

What is known

Near-solution. Guth and Katz (2015) proved that every set of $n$ points in the plane determines $\gg n/\log n$ distinct distances.
Pinned distances. A stronger form asks for a single point $x\in A$ from which $\gg n/\sqrt{\log n}$ distances are seen; it is a separate problem on the source site (problem 604). Katz and Tardos (2004) showed that some point always sees at least $n^{0.8641\ldots}$ distinct distances. A September 2026 preprint posted by OpenAI, with a Lean formalisation, proves that all but $o(n)$ of the points each see at least $n^{1-\varepsilon}$ distinct distances, for every fixed $\varepsilon>0$ ; this is still far from $n/\sqrt{\log n}$ .
Averages. Erdős also conjectured that $\sum_{x\in A}d(x)\gg n^2/\sqrt{\log n}$ , where $d(x)$ is the number of distinct distances from $x$ .

What would count as progress

A proof of $\lvert D(A)\rvert\gg n/(\log n)^{1-\delta}$ for some $\delta>0$ , improving Guth and Katz.
A proof of the full conjecture, or a construction beating the grid, which would disprove it; for any explicit point set the distances can be counted exactly.
Progress on structured cases, for example point sets on a small number of lines or curves, with complete proofs.
A formal proof against the Lean statement in formal-conjectures.

References

P. Erdős, On sets of distances of $n$ points, Amer. Math. Monthly 53 (1946), 248–250. doi:10.2307/2305092
P. Erdős, On some problems of elementary and combinatorial geometry, Ann. Mat. Pura Appl. 103 (1975), 99–108. doi:10.1007/BF02414146
N. H. Katz and G. Tardos, A new entropy inequality for the Erdős distance problem, in Towards a Theory of Geometric Graphs, Contemp. Math. 342 (2004), 119–126. doi:10.1090/conm/342/06136
L. Guth and N. H. Katz, On the Erdős distinct distances problem in the plane, Ann. of Math. 181 (2015), 155–190. doi:10.4007/annals.2015.181.1.2
OpenAI, The weak pinned planar distance theorem, preprint (2026). PDF

Source

Imported from Erdős Problems 89, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.