Erdős Problem #100
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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
Place \(n\) distinct points in the Euclidean plane. Assume every distance between two different points is at least one. Additionally, whenever two pairwise distances are different, their numerical values must differ by at least one.
Erdős #100 asks whether the diameter \(D\), the largest pairwise distance, must satisfy
for some universal constant \(c>0\) and all sufficiently large \(n\). A stronger conjecture proposes \(D\ge n-1\). Equal distances are permitted without restriction; requiring all distances to be different would be a different problem.
A small example
For points \((0,0),(1,0),\ldots,(n-1,0)\), the distinct distances are \(1,2,\ldots,n-1\). Their pairwise gaps are at least one, and the diameter equals \(n-1\). Thus the stronger conjectured value would be sharp if it held universally.
In contrast, a square of side length one has distance values \(1\) and \(\sqrt2\), which differ by less than one. Despite its unit minimum separation, it fails the second hypothesis. This example shows why that hypothesis cannot be discarded.
What is known
The conjecture is OPEN. The maintained Erdős #100 records Kanold's historical lower bound \(D\ge n^{3/4}\) and a nine-point construction of Piepmeyer with diameter less than five. The latter does not refute a claim asserted only for sufficiently large \(n\), and the original construction has not been independently audited here.
Guth and Katz's primary 2015 Annals theorem proves that any \(n\) distinct planar points determine at least \(c n/\log n\) distinct distances. In this problem those distinct lengths \(u_1<\cdots<u_t\) obey \(u_1\ge1\) and \(u_{j+1}\ge u_j+1\). Therefore the largest one, \(D=u_t\), satisfies \(D\ge t\), giving the unconditional consequence
This is a rigorous reduction from a primary theorem, but still weaker than the desired linear lower bound.
GCL's current state
The pinned catalogue and maintained #100 classify it OPEN. The original assignment is #1369. The Guth–Katz abstract was verified, and the transfer from distinct-length count to diameter is elementary and self-contained. Kanold's original proof and Piepmeyer's coordinates remain bibliographic leads rather than primary-page-checked evidence.
The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.
What remains
A bounded proof task is to formalize the separation lemma: \(t\) distinct real numbers, all at least one and separated by gaps at least one, have maximum at least \(t\). Apply it to a finite metric distance set and replay the Guth–Katz consequence with correct universal quantifiers. Acceptance: the one-dimensional arithmetic progression gives equality \(D=n-1\); the unit square is rejected as an invalid separated-distance input. Stop without asserting \(D\gg n\).
Sources and claim boundaries
- Guth and Katz, Annals of Mathematics 181 (2015), primary distinct-distance result.
- Erdős #100, Kanold and Piepmeyer leads; GCL issue #1369.
No new diameter lower bound, verification of the historical counterexample coordinates, or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1369 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.