Problem 1085

Let $f_d(n)$ be minimal such that, in any set of $n$ points in $\mathbb{R}^d$ , there exist at most $f_d(n)$ pairs of points which distance $1$ apart. Estimate $f_d(n)$ .

Source: erdosproblems.com/1085

Geometry
Distances

Wiki page

Status

Open

No claim settles this problem.

Open, in the site's label (OPEN; page last edited 23 May 2026). The site's remarks call $d=2$ and $d=3$ the most difficult cases and credit the results that determine $f_d(n)$ in dimension four and above. The problem's parts, listed in the frontmatter, are plane ( $d=2$ ), space ( $d=3$ ), even_dimensions (even $d\ge4$ ) and odd_dimensions (odd $d\ge5$ ); the claim pages in claims/ record the literature for $d\ge4$ as partial claims settling the last two parts, and OpenAI's planar power saving as an accepted partial claim that settles no part. The plane and space are open, so the standing in the frontmatter, derived from the claim pages, is open.

Br97: Brass, P., On the maximum number of unit distances among $n$ points in dimension four. Intuitive Geometry (Budapest, 1995), Bolyai Soc. Math. Stud. 6 (1997), 277-290.
CEGSW90: Clarkson, Kenneth L. and Edelsbrunner, Herbert and Guibas, Leonidas J. and Sharir, Micha and Welzl, Emo, Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom. 5 (1990), 99-160.
Er60b: Erdős, P., On sets of distances of $n$ points in Euclidean space. Magyar Tud. Akad. Mat. Kutató Int. Közl. (1960), 165-169.
Er67e: Erdős, P., On some applications of graph theory to geometry. Canadian J. Math. (1967), 968-971.
ErPa90: Erdős, P. and Pach, J., Variations on the theme of repeated distances. Combinatorica (1990), 261-269.
SST84: Spencer, J. and Szemerédi, E. and Trotter, Jr., W., Unit distances in the Euclidean plane. Graph theory and combinatorics (Cambridge, 1983) (1984), 293-303.
Sw09: Swanepoel, Konrad J., Unit distances and diameters in Euclidean spaces. Discrete Comput. Geom. (2009), 1-27.
vW99: van Wamelen, P., The maximum number of unit distances among $n$ points in dimension four. Beiträge Algebra Geom. 40 (1999), 475-477.

Problem 1085

Status

Proof claims

Discussion