Erdős Problem #1089
SOLVEDdatabase updated 2026-02-01
Resolved in some way other than a straight proof or disproof — usual for open-ended questions, or for multi-part problems whose parts went different ways.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
`g d n` is the least `m` such that every `m` points in `ℝ^d` determine at least `n` distinct distances, i.e. the least `m` with `n ≤ minimalDistinctDistances (EuclideanSpace ℝ (Fin d)) m`.
Let \(g_d(n)\) be minimal such that every collection of \(g_d(n)\) points in \(\mathbb{R}^d\) determines at least \(n\) many distinct distances. Estimate \(g_d(n)\). In particular, does \[\lim_{d \to \infty} \frac{g_d(n)}{d^{n-1}}\] exist? A problem of Erdős [Er75f, p.105]. The answer is yes: for \(n \ge 2\), \[\binom{d+1}{n-1} + 1 \le g_d(n) \le \binom{d+n-1}{n-1} + 1,\] where the upper bound is due to Bannai, Bannai and Stanton [BBS83] and the lower bound to a construction of Aletheia (generalising constructions for Problem 502), so that \(g_d(n) / d^{n-1} \to 1/(n-1)!\) as \(d \to \infty\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/1089.Prizenone
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1089
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.