Convex and discrete geometry Discrete and combinatorial geometry Problem

Erdős distinct distances problem

Problem

Let $n \ge 2$ be an integer. For a set $S$ of $n$ points in the plane $\R^2$ , consider the Euclidean distances $\norm{p - q}$ with $p, q \in S$ and $p \ne q$ . Let $g(n)$ be the least number of distinct values of these distances, over all such sets $S$ . Find the order of growth of $g(n)$ as $n \to \infty$ . Erdős conjectured that the square grid is essentially optimal. A weaker form of his conjecture says that $g(n) \ge n^{1 - \varepsilon}$ for every $\varepsilon > 0$ and all large enough $n$ .

Remarks

Erdős posed the problem in 1946 and proved the lower bound $g(n) = \Omega(\sqrt{n})$ . A $\sqrt{n} \times \sqrt{n}$ piece of the integer lattice determines only $O(n / \sqrt{\log n})$ distinct distances, so $g(n) = O(n / \sqrt{\log n})$ . Guth and Katz proved the lower bound $g(n) = \Omega(n / \log n)$ . This settles the weaker conjecture $g(n) \ge n^{1 - \varepsilon}$ . The exact order of $g(n)$ is still open: the known bounds differ by a factor of order $\sqrt{\log n}$ . The analogous questions in higher dimensions are also studied.

Reading path

To understand this page from the ground up, read these 2 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Euclidean distance concept
Erdős distinct distances problem problem

Tag	`4H31EM5T0C`
URI	`m2://4H31EM5T0C`
Kind	problem
Writing	W0 stub
MSC	52C10, 52C45
Status	This copy of the site has no build data. Run `m2 status 4H31EM5T0C`.
About	Euclidean distance
Uses	Euclidean distance
Same as	Wikidata Q3406261 Wikipedia Erdős distinct distances problem
Changed	2 November 2026

Erdős distinct distances problem

Problem

Remarks

Reading path

Further reading

What this page needs for W1

What links here