Problem 1083

Let $d\geq 3$ , and let $f_d(n)$ be the minimal $m$ such that every set of $n$ points in $\mathbb{R}^d$ determines at least $m$ distinct distances. Estimate $f_d(n)$ - in particular, is it true that

f_d(n)=n^{\frac{2}{d}-o(1)}?

Source: erdosproblems.com/1083

Geometry
Distances

Wiki page

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

Open, in the site's label (OPEN; page last edited 16 October 2025, proof-claims tab empty on 2026-10-06). Tidor, Yu and Zakharov's preprint of 14 August 2026 proves $f_3(n)=n^{2/3-o(1)}$ , a yes to the particular question for $d=3$ , recorded as a pending partial claim on its claim page (Tidor Yu Zakharov, 2026). OpenAI's release preprint of 23 September 2026 claims $f_d(n)\gg_d n^{2/d}$ for every fixed $d\ge3$ , which would answer the question in the affirmative for every $d$ ; the OpenAI claim page (2026) records it as a pending full claim without acceptance evidence, so the standing in the frontmatter, derived from the claim pages, is claimed.

APST04: Aronov, Boris and Pach, János and Sharir, Micha and Tardos, Gábor, Distinct distances in three and higher dimensions. Combin. Probab. Comput. (2004), 283-293.
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.
Er46b: Erdős, P., On sets of distances of $n$ points. Amer. Math. Monthly (1946), 248-250.
SoVu08: Solymosi, József and Vu, Van H., Near optimal bounds for the Erdős distinct distances problem in high dimensions. Combinatorica (2008), 113-125.

Problem 1083

Status

Proof claims

Discussion