Erdős #604 — pinned distinct-distances at a single point

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 the stronger $\gg n/\sqrt{\log n}$? I.e.: is there always a single point in $A$ that alone "sees" almost as many distinct distances as the whole configuration determines in total (the ordinary, unpinned distinct-distances problem, Erdős #89 — distinct distances in the plane)?

Facts

- Prize \$500; status OPEN, "cannot be resolved with a finite computation" (erdosproblems.com/604, site-owner belief, verified by direct fetch 2026-07-02). - Falsifiable: no in the finite-computation sense — this is an asymptotic $\gg$ statement over all $n$ and all configurations; disproving it would require an infinite family of counterexample configurations with a proof of the near-degenerate distance count, not a single finite witness. Proving it needs a genuine incidence-geometry proof. - Origin: Erdős [Er57], [Er61], [Er75f, p.99], [Er83c], [Er85], [Er87b, p.169], [Er90], [Er95], [Er97b], [Er97c], [Er97e], [Er97f] — Erdős posed and restated this across a dozen of his problem-list papers; the \$500 prize is explicitly attached in [Er97e], though erdosproblems.com notes it is "unclear whether he intended this for proving the existence of a single such point or for $\gg n$ many such points." - Known results / best bounds: - Upper bound / tightness: the $\sqrt n\times\sqrt n$ integer grid shows $n/\sqrt{\log n}$ is best possible (same extremal example as Erdős #89 — distinct distances in the plane), so the strong form of the conjecture is the natural target. - Best known lower bound: $\gg n^{c-o(1)}$ with $c=\frac{48-14e}{55-16e}=0.864137\cdots$, due to Katz and Tardos, "A new entropy inequality for the Erdős distance problem", Contemp. Math. 342 (2004) 119-126 [KaTa04] — confirmed verbatim in Sheffer's survey (arxiv.org/pdf/1406.1949, "Problem 36", $\hat D(n)=\Omega(n^{(48-14e)/(55-16e)})\approx\Omega(n^{0.864})$). This is the *same* exponent that was, before Guth-Katz 2015, also the best bound for the *unpinned* problem Erdős #89 — distinct distances in the plane — it predates and is not improved by the Guth-Katz polynomial-partitioning breakthrough. - Guth-Katz 2015 (arXiv, Ann. of Math. 181 (2015) 155-190) resolved the *unpinned* form Erdős #89 — distinct distances in the plane up to log factors ($\gg n/\log n$ total distinct distances), but — as both erdosproblems.com/89 and Sheffer's survey state explicitly — "Guth and Katz's bound does not immediately imply a matching lower bound for $\hat D(n)$": their polynomial-partitioning / Elekes-Sharir reduction counts incidences on a ruled surface in $\mathbb R^3$ *aggregated over all pairs*, and does not localize to show one point alone realizes almost all the distinct distances. This non-transfer is exactly why #604 remains open 11+ years after #89 was essentially settled. - Erdős's stronger "on average" form [Er75f]: $\sum_{x\in A} d(x) \gg n^2/\sqrt{\log n}$ (Sheffer's "Problem 37", $\hat D_\Sigma(n)$). The Katz-Tardos bound trivially implies $\hat D_\Sigma(n)=\Omega(n^{1.864})$ by repeatedly removing the point maximizing $\hat D_p$ — still short of the conjectured $n^2/\sqrt{\log n}=\Omega(n^{2-o(1)})$. - Erdős himself notes in [Er97e] he initially over-conjectured that the pinned answer matches the unpinned one exactly, but this was disproved by Harborth — the pinned and unpinned problems are genuinely different in general, only conjectured equal up to an $n^{o(1)}$ factor. - Formalized: no. Confirmed via GitHub API (2026-07-02) that google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/604.lean does not exist, unlike the sibling 89.lean which formalizes both the open Erdős-1946 statement and the solved Guth-Katz bound as separate theorems (one sorry, one proved-solved marker). - Related problems: Erdős #89 — distinct distances in the plane — the unpinned parent problem, nearly resolved by Guth-Katz; #604 is explicitly framed on erdosproblems.com as "a stronger form of [89]". Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019) — bipartite/two-point-set variant of the same distance-count question, also open.

Literature state

Not resolved. The problem sits at exactly the gap left open by the 2015 Guth-Katz resolution of the classical (unpinned) Erdős distinct-distances problem: Guth-Katz's polynomial-partitioning method proves a near-optimal *total* distinct-distance count but its proof technique (reduction via the Elekes-Sharir framework to point-line incidences on a ruled quadric surface in $\mathbb R^3$, followed by algebraic cell decomposition) does not localize to a single pin. The best bound for the pinned version is still the pre-Guth-Katz Katz-Tardos (2004) entropy-inequality exponent $n^{0.864\ldots}$ — an over-20-year-old bound that has not been improved for the discrete finite-point-set problem, per this search (cross-checked via arXiv full-text search for "pinned distances" + "distinct distances", Sheffer's 2014 survey, and general web search for 2020-2026 improvements — nothing found for the *discrete* version). All post-2014 "pinned distance" progress located (arXiv:2101.12589 Guth-Iosevich-Ou-Wang-style spherical-average methods; arXiv:2207.12501 effective-dimension/point-to-set-principle methods of Stull et al.; arXiv:2408.00889; arXiv:2509.01152) is on the continuous Falconer pinned-distance conjecture for Hausdorff-dimension fractal sets in $\mathbb R^d$ — a genuinely different (measure-theoretic, Fourier-analytic) problem that shares the name and conjectural shape but not the discrete combinatorial machinery; it is not a resolution of #604. Erdős's own "average" strengthening [Er75f] ($\sum_x d(x)\gg n^2/\sqrt{\log n}$, Sheffer's Problem 37) is likewise open, with the same Katz-Tardos-derived bound as the best known. No AI/LLM/automated-theorem-prover contribution to #604 was found (no Lean/Isabelle formalization exists yet, unlike neighboring problem #89 which does have a Lean statement scaffold with both the open and solved cases stated). Note: a separate, much-publicized 2026 result (OpenAI-model-assisted improvement to the *unit-distance* problem via algebraic-number-theory / class-field-tower methods, reported by Gil Kalai's blog and covered by officechai.com) concerns a different Erdős problem (max pairs at exactly distance 1) and is unrelated to #604's pinned-count question, despite surface-level topical proximity.

Attack surface

- Mode: literature-resolution (first — confirm no 2004-2026 paper closes or narrows the discrete Katz-Tardos gap; this search found none, but a full MathSciNet citation-trace of Katz-Tardos [KaTa04] was not performed) + derivation+formalization (the real mathematical content: find why the Guth-Katz polynomial-partitioning proof for the unpinned case cannot be localized to a pin, and whether a refinement of the Elekes-Sharir reduction — e.g. tracking which points on the ruled surface correspond to a *fixed* pin's rigid-motion fibers — can push the exponent from $0.864$ toward $1-o(1)$). - Concrete first experiment: not a finite computation (falsifiability: not-finite). The realistic first move is a close reading of (1) the Elekes-Sharir framework as used in Guth-Katz's proof of Erdős #89 — distinct distances in the plane (arXiv version of Ann. of Math. 181 (2015) 155-190) to identify exactly which step aggregates over all pins and cannot be trivially localized, and (2) the Katz-Tardos entropy-inequality technique (Contemp. Math. 342 (2004), secondary description via Sheffer's survey since the primary source is not on arXiv) to see whether it composes with polynomial partitioning rather than being superseded by it. - Oracle: none mechanical for the general lower bound (an asymptotic inequality over all $n$ and all configurations); a candidate proof would be checked the traditional way (peer review / formalization), though the existing Lean scaffold for #89 (89.lean in google-deepmind/formal-conjectures) would be a natural template to extend for a machine-checked #604 statement once even a weak improvement is claimed. - Feasibility: honest read: famous-and-hard. This is the direct, still-open sequel to one of the highlight results of 2010s discrete geometry (Guth-Katz); the fact that a Fields-Medal-adjacent breakthrough left the pinned exponent completely untouched at its pre-2010 value is itself evidence of genuine technical difficulty, not neglect. The one concretely promising thread is *not* a finite search but a technique-transplant question: does the polynomial-partitioning machinery (or the more recent decoupling-theoretic machinery used for the continuous Falconer analog, arXiv:1808.09346 Guth-Iosevich-Ou-Wang) have a discrete-pinned-distance-shaped counterpart? Worth a literature-only follow-up focused specifically on post-2015 citations of Katz-Tardos [KaTa04] and post-2015 citations of Guth-Katz [GuKa15] that discuss "pinned" or "single point" variants, rather than a computational attack.

Related

- Erdős #89 — distinct distances in the plane — the unpinned parent: total distinct distances over $n$ points, nearly resolved by Guth-Katz 2015 ($\gg n/\log n$); #604 is the still-open "localize to one point" strengthening that Guth-Katz's technique does not reach. - Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019) — bipartite two-point-set variant of the same distinct-distances question, also open. - Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2) — reduction of planar distinct-distances counting to point-line incidences on a ruled surface in $\mathbb R^3$ parametrizing rigid motions; the core technique behind Guth-Katz Erdős #89 — distinct distances in the plane and the reason its bound doesn't transfer to #604. - concept/polynomial-partitioning — the algebraic cell-decomposition method (Guth-Katz 2010 joints problem, then 2015 distinct distances) that resolved the unpinned problem but has not been adapted to the pinned/single-point version. - concept/entropy-inequality-additive-combinatorics — Katz-Tardos's 2004 technique giving the still-standing best bound $n^{0.864\ldots}$ for #604. - concept/szemeredi-trotter-theorem — the point-line incidence bound underlying the pre-Katz-Tardos chain (Chung-Szemerédi-Trotter, Solymosi-Tóth) that #604's bound descends from. - concept/falconer-distance-conjecture — the continuous/fractal analog (Hausdorff-dimension pinned distance sets), partially resolved by Guth-Iosevich-Ou-Wang (arXiv:1808.09346, dim $>5/4$ in $\mathbb R^2$) via Fourier decoupling — same conjectural shape as #604 but a different (measure-theoretic) proof technology; not a resolution of the discrete problem. - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — no Lean/Isabelle formalization exists for #604 (confirmed absent from google-deepmind/formal-conjectures 2026-07-02), unlike sibling #89.