Pinned distances with no four points on a circle: is f(n) > (1/3+c)n, or even (1-o(1))n? (Erdős #654)
Statement
Let $f(n)$ be the largest function such that, given any $x_1,\ldots,x_n\in \mathbb{R}^2$ with no four points on a circle, there exists some $x_i$ with at least $f(n)$ distinct distances to the other $x_j$. Estimate $f(n)$ — in particular, is it true that $$f(n)>(1-o(1))n\,?$$ Or at least $$f(n) > (1/3+c)n$$ for some constant $c>0$, for all large $n$? (The first, strongest form has been disproved — see the background — so the live questions are the $(1/3+c)n$ lower bound and the variant where the points are additionally in general position, i.e. also no three on a line.)
Acceptance. FULLY RESOLVES: a proof that $f(n)>(1/3+c)n$ for an explicit constant $c>0$ and all large $n$ (machine-checkable preferred, else a complete written proof); OR an explicit infinite family of $n$-point sets with no four on a circle together with a proof that every point sees at most $(1/3+o(1))n$ distinct distances, showing the trivial bound is asymptotically sharp; or any determination of the asymptotics of $f(n)$ up to $(1+o(1))$ factors. ADVANCES: an upper-bound construction strictly below the $\frac{3}{4}n$ stated in the background (with proof, or with machine-verifiable pinned-distance-count certificates for a growing family plus a proof sketch of the asymptotic); any lower bound strictly better than the trivial $(n-1)/3$; or nontrivial bounds in either direction for the general-position variant. Deliver the proof file, or the construction plus verification code for its pinned-distance counts.
Background
Raised by Erdős [Er87b, p.168], by Erdős and Pach [ErPa90, p.267], and again in [Er97e, p.530]; listed as open on erdosproblems.com/654 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'; page last edited 01 February 2026). The trivial bound is $f(n)\ge (n-1)/3$: with no four points on a circle, each circle centred at $x_i$ passes through at most $3$ of the other points, so the distances from $x_i$ take at least $(n-1)/3$ distinct values. In [Er97e] Erdős asked whether $f(n)>(1-o(1))n$, conceding this was 'perhaps too optimistic' while insisting the trivial bound can be significantly improved. In [Er87b] and [ErPa90] Erdős and Pach posed the question under the extra assumption of general position (no three on a line), asking only for a bound of the shape $(\tfrac{1}{3}+c)n$; they suggested $(1-o(1))n$ should hold when every circle centred at a point contains at most $2$ other points. The strongest form was disproved by Aletheia [Fe26] (the page credits Google DeepMind's Superhuman Reasoning team): a construction of $n$ points in $\mathbb{R}^2$, no four on a circle, with at most $\frac{3}{4}n$ distinct distances from any single point. That construction places all points on a union of two lines, so it says nothing about the general-position variant. Current frontier: trivial $(n-1)/3$ lower bound versus $\frac{3}{4}n$ upper bound, with the general-position variant wide open above $(n-1)/3$. Closely related to the general pinned distance problem, Erdős #604 (erdosproblems.com/604). The attacker's tool: explicit structured constructions (multi-line or lattice families with controlled concyclicities) to push the upper bound below $\frac{3}{4}n$ or to attack the general-position variant — candidate constructions can be machine-verified at finite sizes before proving asymptotics — plus incidence-geometry arguments toward a $(1/3+c)n$ lower bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #654 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.