Problem 756

Let $A\subset \mathbb{R}^2$ be a set of $n$ points. Can there be $\gg n$ many distinct distances each of which occurs for more than $n$ many pairs from $A$ ?

Source: erdosproblems.com/756

Geometry
Distances

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

PROVED (LEAN). The site marks the problem proved, crediting Bhowmick's construction, and flags a Lean formalization of his proof; see the claim page (Bhowmick, 2024).

Bh24: K. Bhowmick, A problem of Erdős about rich distances. arXiv:2407.01174 (2024). Published as: A note on a problem of Erdős about rich distances. Studia Sci. Math. Hungar. 62 (2025), no. 1, 89-94.
CDL25: F. Clemen, A. Dumitrescu, and D. Liu, On multiplicities of interpoint distances. arXiv:2505.04283 (2025). Acta Math. Hungar. 177 (2025), 231-245.
Er97b: Erdős, Paul, Some old and new problems in various branches of combinatorics. Discrete Math. 165/166 (1997), 227-231.
ErPa90: Erdős, Paul and Pach, János, Variations on the theme of repeated distances. Combinatorica 10 (1990), 261-269.
HoPa34: Hopf, H. and Pannwitz, E., Aufgabe 167. Jber. Deutsch. Math. Verein. (1934), 114.

Problem 756

Status

Proof claims

Discussion