Skip to content

Erdős Problem #1089

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: solved (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.

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

How many points in \(d\) dimensions are needed to guarantee at least \(n\) different positive distances among their pairs?

Write this threshold as \(g_d(n)\). Erdős Problem #1089 asks particularly what happens as the dimension becomes very large while the required number \(n\) of different distances stays fixed.

It is closely related to Problem #1083, which instead starts with a fixed number of points and asks how few distances they can determine.

A small example

On a line, the four distinct points \(0,1,2,3\) determine three positive distances: \(1,2,3\). In contrast, the three points \(0,1,2\) determine only \(1\) and \(2\). In fact, any four distinct collinear points determine at least three distances by examining the gaps between consecutive ordered points. Hence \(g_1(3)=4\).

The interesting asymptotic regime is not dimension one, but dimension \(d\to\infty\) at fixed distance target \(n\).

What is known

The limiting question is solved. The maintained catalogue gives the two bounds

\[ \binom{d+1}{n-1}+1 \ \le\ g_d(n)\ \le\ \binom{d+n-1}{n-1}+1. \]

The upper bound is attributed to Bannai, Bannai and Stanton (1983), while the lower bound is attributed to the Aletheia research reported by Feng and colleagues (2026). The original proofs of these bounds have not been independently replayed by GCL.

The limit follows from the bounds by elementary algebra. For every fixed positive integer \(m\),

\[ \binom{d+c}{m}=\frac{d^m}{m!}+O_m(d^{m-1}) \]

when \(c\) is fixed. Taking \(m=n-1\) and squeezing between the two binomial expressions yields

\[ \boxed{\lim_{d\to\infty}\frac{g_d(n)}{d^{n-1}} =\frac1{(n-1)!}.} \]

For example, the limiting constant for \(n=3\) is \(1/2\).

GCL's current state

Authenticated source audit #2360 separates the externally established geometric bounds from the elementary asymptotic deduction.

The maintained catalogue reports a newer formalized statement, but there is no #1089 file in the protected older formal-conjectures snapshot. The original 1983 and 2026 proof sources and current formal version require independent review.

What remains

Verify the mathematical hypotheses and precise integer boundaries in both published bounding theorems. The fixed‑\(n\) squeeze is straightforward once those inequalities are granted. Do not present it as an original GCL theorem, and do not extend the limit to growing \(n\) without new uniform estimates.

Sources and claim boundaries

Erdős Problem #1089, solved limit and bounds; Bannai–Bannai–Stanton (1983), Combinatorica, pp. 147–152; Feng et al. (2026), arXiv:2601.22401; authenticated audit #2360. The binomial squeeze is independently derived from reported external inequalities. Unaccepted draft.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2360 — 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.

Back to catalogue · Compendium introduction