OPEN
This is open, and cannot be resolved with a finite computation.
- $500
Does every set of $n$ distinct points in $\mathbb{R}^2$ contain at most $n^{1+O(1/\log\log n)}$ many pairs which are distance 1 apart?
The unit distance problem. In
[Er94b] Erdős dates this conjecture to 1946. In
[Er82e] he offers \$300 for the upper bound $n^{1+o(1)}$.
This would be the best possible, as is shown by a set of lattice points. It is easy to show that there are $O(n^{3/2})$ many such pairs. The best known upper bound is $O(n^{4/3})$, due to Spencer, Szemerédi, and Trotter
[SST84]. In
[Er83c] and
[Er85] Erdős offers \$250 for an upper bound of the form $n^{1+o(1)}$.
Part of the difficulty of this problem is explained by a result of Valtr (see
[Sz16]), who constructed a metric on $\mathbb{R}^2$ and a set of $n$ points with $\gg n^{4/3}$ unit distance pairs (with respect to this metric). The methods of the upper bound proof of Spencer, Szemerédi, and Trotter
[SST84] generalise to include this metric. Therefore to prove an upper bound better than $n^{4/3}$ some special feature of the Euclidean metric must be exploited.
See a survey by Szemerédi
[Sz16] for further background and related results.
See also
[92],
[96],
[605], and
[956]. The higher dimensional generalisation is
[1085].
View the LaTeX source
This page was last edited 15 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #90, https://www.erdosproblems.com/90, accessed 2025-11-16
