Erdős Problem #652
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: geometry, distances.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Take \(n\) distinct points in the plane. At any one point \(x\), count the different distances from \(x\) to the other \(n-1\) points. Call that number \(R(x)\). Several neighbours may be equally far away, so \(R(x)\) can be smaller than \(n-1\).
Order the points so that
Erdős Problem #652 asks how small \(R(x_k)\) can be when we insist on \(k\) points with relatively few distinct distances. The maintained formulation calls \(\alpha_k\) the least threshold (or infimum if the threshold is not attained) such that, for all sufficiently large \(n\), there exists a configuration of \(n\) points with
Must \(\alpha_k\) grow without bound as \(k\to\infty\)? According to the maintained catalogue and published work, the answer is yes. Crucially, \(k\) is fixed first and \(n\) then grows.
A small example
Place five points equally spaced around a circle of radius \(1\). From any vertex of the resulting regular pentagon, the other four vertices occur at only two distances: the side length and the diagonal length. Their exact squared values are
Thus, after ordering,
This calculation was independently checked with numerical coordinates \((\cos(2\pi j/5),\sin(2\pi j/5))\) for \(j=0,\ldots,4\): every vertex has precisely two squared distances, approximately \(1.381966\) and \(3.618034\).
The example distinguishes different radii around one point from all pairs of points. It does not contradict the question's asymptotic lower bound, which concerns arbitrarily large \(n\) for each fixed \(k\).
What is known
A particularly useful published theorem appears in Surya Mathialagan's On Bipartite Distinct Distances in the Plane, Electronic Journal of Combinatorics 28 (2021), P4.33. Its Theorem 14, printed page 7, says that if \(P\) and \(Q\) are planar point sets with \(|P|=m\), \(|Q|=N\), and
then some point in \(P\) determines at least \(c\sqrt{mN}\) different distances to the points of \(Q\), for a universal \(c>0\). This pointwise assertion is stronger than saying the union of all distances between \(P\) and \(Q\) is large. The published proof uses a graph crossing-number argument.
Apply this theorem to the first \(k\) ordered points and their complement:
For fixed \(k\geq2\) and sufficiently large \(n\), the condition \(k\leq(n-k)^{1/3}\) holds. The theorem gives some \(p\in P\) at least \(c\sqrt{k(n-k)}\) different distances to \(Q\). But every \(p\in P\) has at most \(R(x_k)\) distances even when all other points are counted. Hence
For \(n\geq2k\), divide by \(\sqrt n\):
The bound applies to every configuration. It therefore also constrains the least possible threshold in the maintained definition:
In particular \(\alpha_k\to\infty\). This consequence uses a published theorem and elementary quantifier manipulation. It is not a GCL mathematical discovery or an independently certified proof of Mathialagan's deeper theorem.
Mathialagan also details Elekes' circle-grid construction in Section 2, Proposition 6 (printed p. 5). It builds \(k\) distinguished centres \(P\) and a larger set \(Q\) with only \(O(\sqrt{k|Q|})\) distinct cross-distances. Every centre in \(P\) gains at most \(k-1\) additional distances to other centres. For fixed \(k\), choose the grid sufficiently large and remove surplus points of \(Q\) when necessary to obtain any sufficiently large total size \(n\). The \(k\) distinguished centres then see at most \(O(\sqrt{kn})+k-1\) distances each, so \(\alpha_k=O(\sqrt{k})\). Combined with Theorem 14, the established sharp order is \(\boxed{\alpha_k=\Theta(\sqrt{k})}\). This is a deduction from published mathematics, not a new GCL discovery. A distinct 2026 preprint by Feng and collaborators gives an \(\Omega(k^{1/4})\) conclusion using Pach–Sharir incidence estimates and discusses corrections to earlier incorrectly cited exponents. That weaker exponent does not supersede the published Mathialagan theorem's pointwise consequence.
GCL's current state
The original authenticated RESULT/1 source return has historical disposition PARTIAL. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.
Source interpretation and unresolved mathematical qualification: Mathialagan's bipartite-distances theorem has explicit |P|<=|Q|^(1/3); its application to fixed early indices does not assert an unrestricted theorem in k.
The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.
What remains
The affirmative answer, including the matching \(\Theta(\sqrt{k})\) growth order, follows from the external published theorem and circle-grid construction. The next task is exact source fidelity: obtain the full Erdős (1997) Math. Japon. survey, locate the relevant paragraph, and compare its words and quantifiers with the maintained formulation. That comparison can confirm or limit the theorem's application to the original question.
A separate editorial critique must confirm the pointwise Theorem 14 citation, the uniformity of its constant in \(k\), the inequality \(k\leq(n-k)^{1/3}\), and the independent pentagon calculation. The cohort then requires protected production, deployed MathJax verification in a real browser, and one distinct V2 editorial admission transaction. None has occurred for this draft.
Sources and claim boundaries
- Erdős Problems #652: maintained problem statement, PROVED status, and references; indexed last-edit date 18 January 2026. Direct live HTTP fetch returned 403 during this audit.
- P. Erdős, Some of my favourite unsolved problems, Math. Japon. (1997), 527–537, MR1487304 (maintained original-source key Er97e). Full source and exact problem page uninspected. The separate Erdős–Fishburn article, Distinct distances in finite planar sets (1997), is background and must not be mislabeled Er97e.
- S. Mathialagan, On Bipartite Distinct Distances in the Plane, Electronic Journal of Combinatorics 28 (2021), P4.33, published Theorem 14, page 7. The theorem was inspected in the published PDF.
- T. Feng and collaborators, Semi-Autonomous Mathematics Discovery with Gemini: A Case Study on the Erdős Problems, arXiv:2601.22401v3 (5 February 2026), discussion of #652. Externally reported preprint result; not GCL proof certification.
- GCL #652 authenticated RESULT/1: mathematical reduction, primary-source limitation, and bounded successor.
Authority boundary: researched editorial explanation of published mathematics, with a recorded historical-source fidelity gap. No novelty, certified theorem, rendered-site readback, protected manuscript merge, or batch acceptance is asserted.
Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1923 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.