Problem 653

Let $x_1,\ldots,x_n\in \mathbb{R}^2$ and let $R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}$ , where the points are ordered such that

R(x_1)\leq \cdots \leq R(x_n).

Let $g(n)$ be the maximum number of distinct values the $R(x_i)$ can take. Is it true that $g(n) \geq (1-o(1))n$ ?

Source: erdosproblems.com/653

Geometry
Distances

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved, against the site's label OPEN: the answer yes rests on a Lean proof certified by the bounty site Conjectures.io after its kernel check and review, which is the accepted claim on gus's claim page (2026); the site has not credited it. The erdosproblems.com page labels the problem open (2026-10-07) and records the literature bounds $g(n)>\tfrac{7}{10}n$ and $g(n)<n-cn^{2/3}$ , while its proof-claims tab carries a full claim through a Lean proof certified by the bounty site Conjectures.io and a partial-result entry through a Zenodo preprint.

Problem 653

Status

Proof claims

Discussion