Pinned distances: must some point of an n-point planar set see n^{1-o(1)} distinct distances? (Erdős #604)
Statement
Given $n$ distinct points $A\subset\mathbb{R}^2$, must there be a point $x\in A$ such that $$\#\{ d(x,y) : y \in A\} \gg n^{1-o(1)}\,?$$ Or even $\gg n/\sqrt{\log n}$? Here $d(x,y)$ is the Euclidean distance and $f(n)\gg g(n)$ means $f(n)\ge c\,g(n)$ for an absolute constant $c>0$. This is the pinned distance problem: rather than counting the distinct distances determined by all pairs of $A$, it asks whether a single point of $A$ must already see nearly the maximal possible number of distinct distances.
Acceptance. FULLY RESOLVES: a proof that for every set of $n$ distinct points in $\mathbb{R}^2$ some point sees $\gg n^{1-o(1)}$ distinct distances (or the stronger $\gg n/\sqrt{\log n}$) — machine-checkable (Lean/Coq) preferred, else a complete written proof with all steps; OR a disproof: an explicit infinite family of configurations with a proof that every point of the $n$-point configuration sees $O(n^{1-\delta})$ distinct distances for some fixed $\delta>0$. ADVANCES: a proof raising the pinned-distance exponent strictly above the Katz–Tardos value stated in the background; a proof of the average-version conjecture $\sum_{x\in A} d(x)\gg n^2/\sqrt{\log n}$; or a pinned bound beating the best general bound stated in the background for a natural restricted class (e.g. points in general position). Deliver the proof file (and, for a disproof, the construction together with verified pinned-distance counts).
Background
The pinned distance problem, a strengthening of Erdős's distinct distances problem (Erdős #89, erdosproblems.com/89). Erdős returned to it for four decades ([Er57], [Er61], [Er75f, p.99], [Er83c], [Er85], [Er87b, p.169], [Er90], [Er95], [Er97b], [Er97c], [Er97e], [Er97f]) and in [Er97e] offered \$500 for a solution — though it is unclear whether the prize was for the existence of a single such point or for the stronger claim that $\gg n$ points each see that many distances (Hunter notes on the site that the $\gg n$-points version follows trivially from the single-point version). The $\sqrt{n}\times\sqrt{n}$ integer grid shows $n/\sqrt{\log n}$ would be best possible. Erdős also conjectured an average form in [Er75f]: if $d(x)$ is the number of distinct distances from $x$, then $\sum_{x\in A} d(x) \gg n^2/\sqrt{\log n}$ for every $n$-point planar set $A$. He admitted in [Er97e] to having initially 'overconjectured' that the pinned count matches the all-pairs count; Harborth disproved that, though agreement up to a factor $n^{o(1)}$ remains possible. Best known: Katz and Tardos [KaTa04] proved some point always sees $\gg n^{c-o(1)}$ distinct distances with $c=\frac{48-14e}{55-16e}=0.864137\cdots$. For the all-pairs problem, Guth and Katz proved every $n$-point set determines $\gg n/\log n$ distinct distances, but their polynomial-partitioning method has not been adapted to the pinned problem, which remains stuck at the Katz–Tardos exponent. Listed as open on erdosproblems.com/604 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'; page last edited 23 March 2026). Closely related venue problems: the convex-position special case (Erdős #982, must some vertex of a convex $n$-gon see $\ge\lfloor n/2\rfloor$ distinct distances) and Szemerédi's general-position all-pairs conjecture (Erdős #1082); the present problem is the general pinned question. The attacker's tool: proof-shaped incidence geometry — sharpen the Katz–Tardos entropy/incidence argument or adapt Guth–Katz polynomial partitioning to pinned distances; computational purchase is limited to small-configuration exploration.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #604 (T. F. Bloom) | website |
| REF-02 | Guth–Katz, On the Erdős distinct distance problem in the plane (arXiv:1011.4105) — the all-pairs benchmark | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.