Erdős Problem #1088
OPENdatabase updated 2025-10-17
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
A finite set of points has all pairwise distances distinct.
The finite set `S` contains an `n`-point subset with all pairwise distances distinct.
The set of cardinalities `m` such that every `m`-point subset of `ℝ^d` contains an `n`-point subset with all pairwise distances distinct.
Let \(f_d(n)\) be the minimal \(m\) such that any set of \(m\) points in \(\mathbb{R}^d\) contains a set of \(n\) points for which any two determined distances are distinct. Erdős Problem 1088 asks to estimate \(f_d(n)\). In particular, is it true that, for every fixed \(n \geq 3\), \[ f_d(n) = 2^{o(d)} \] as \(d \to \infty\)? The little-\(o\) condition is stated after taking the base-\(2\) logarithm.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open. The authoritative wording is on erdosproblems.com/1088.Prizenone
Topicsgeometry
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/1088
Attempts
submit one →Read our working report →
[a+d] Explicitly proved \(f_d(n)\ge\binom{d+1}{\binom n2-1}+1\), certified \(f_1(4)=7\), and reduced the fixed-\(n\) subexponential question equivalently to distinct-distance subsets on \((d-1)\)-sphe
PARTIAL