Erdős Problem #1088
Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: geometry.
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.
UNACCEPTED DRAFT — mathematical editorial review pending
This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.
Review the underlying draft on GitHub.
The question in plain language
Suppose we have many points in \(d\)‑dimensional space. Can we find \(n\) of them so that every pair among the selected points has a different distance?
Erdős Problem #1088 defines \(f_d(n)\) as the number of points sufficient to guarantee such an \(n\)‑point rainbow-distance subset, regardless of the arrangement. The question emphasizes fixed \(n\ge3\) as dimension \(d\) grows:
This is not the same as requiring all distances in the whole original point set to be distinct.
A small example
Three equally spaced points at positions \(0,1,2\) on a line have three pair distances \(1,1,2\). They are not a rainbow-distance triple.
But selecting points at positions \(0,1,3\) gives distances \(1,2,3\), all different. Hence a set such as \(\{0,1,2,3\}\) can contain a rainbow triple even though the full four-point set has repeated distances.
The known sharp finite values cited by the catalogue, such as \(f_2(3)=7\) and \(f_3(3)=9\), require arguments covering every point set of that size. Individual examples cannot establish that guarantee.
What is known
The maintained catalogue reports a general exponential-in-dimension guarantee of the form \(f_d(n)\le c_n^d\) attributed to Erdős and Straus. For \(n=3\), stronger results establish
which is polynomial in \(d\) and thus subexponential.
The general fixed‑\(n\) question remains open. An affirmative result for triples cannot be extended to arbitrary target sizes without additional proof.
GCL's current state
Authenticated source audit #2359 fixes the order of the quantifiers and distinguishes the rainbow-selection problem from the neighboring distinct-distance problems.
The current catalogue says a formalized statement exists, but the frozen formal-conjectures snapshot does not contain a #1088 file. The version discrepancy requires a source refresh rather than an unsupported claim that no formalization exists.
What remains
Review Erdős's original 1975 statement, the modern proof of the \(d^2/2+O(d)\) triple result, and the claimed general exponential bound. Reconcile the current formal representation separately, then study whether the rainbow-extraction argument can extend to general fixed target \(n\).
Sources and claim boundaries
Erdős Problem #1088, maintained open status and references to #503 and #1208; Erdős (1975), p. 104; authenticated audit #2359. The small selection examples are independently checked; no general fixed‑\(n\) theorem has been proved by GCL. Unaccepted draft.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2359 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
- 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.