Distinct values among the pinned-distance counts R(x_i): is g(n) at least (1-o(1))n? (Erdős #653)
Statement
Let $x_1,\ldots,x_n\in \mathbb{R}^2$ be distinct points and, for each $i$, let $R(x_i)=\#\{ \lvert x_j-x_i\rvert : j\neq i\}$ be the number of distinct distances from $x_i$ to the other points, with the points ordered so that $$R(x_1)\leq \cdots \leq R(x_n).$$ Let $g(n)$ be the maximum, over all configurations of $n$ points, of the number of distinct values taken by $R(x_1),\ldots,R(x_n)$. Is it true that $g(n) \geq (1-o(1))n$?
Acceptance. FULLY RESOLVES: a proof that $g(n)\ge (1-o(1))n$ — an explicit family of configurations for all large $n$ together with a proof that the number of distinct values among the $R(x_i)$ is $(1-o(1))n$ — machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a refutation: a proof of an upper bound $g(n)\le (1-c)n$ for some fixed $c>0$. ADVANCES: an improvement of the lower-bound constant strictly beyond the $\frac{7}{10}$ stated in the background (construction plus proof); a sharpening of the upper bound $n-cn^{2/3}$ (a larger power of $n$ subtracted, or an explicit constant, with proof); or certified record values of $g(n)$ at concrete small $n$ via explicit rational-coordinate configurations whose pinned-distance counts are machine-verified. Deliver the construction with its proof or verification code, or the proof file.
Background
Posed by Erdős [Er97e]; listed as open on erdosproblems.com/653 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). The known frontier: Erdős and Fishburn proved $g(n)>\frac{3}{8}n$, Csizmadia improved this to $g(n)>\frac{7}{10}n$, and both groups proved the upper bound $g(n)<n-cn^{2/3}$ for some constant $c>0$. The conjecture $g(n)\ge (1-o(1))n$ is consistent with that upper bound (since $cn^{2/3}=o(n)$), so the gap to close is between $0.7\,n$ and $n-cn^{2/3}$. Because $g$ is a maximum over configurations, the conjectured lower bound calls for constructions: explicit $n$-point sets whose pinned-distance counts $R(x_i)$ take almost $n$ distinct values. The statement has been formalised in Lean in the google-deepmind/formal-conjectures repository. This is a sibling of the pinned distance problem, Erdős #604 (erdosproblems.com/604), asking about the spread of the pinned counts rather than their minimum size. The attacker's tool: constructive — design configurations (perturbed grids, points on curves, mixed-scale clusters) realising many distinct $R$-values and prove the counts; explicit rational-coordinate configurations at small $n$ give machine-checkable record lower bounds for $g(n)$ that can guide an asymptotic family.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #653 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of the statement (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.