Points in $\mathbb{R}^d$ forcing $n$ with all pairwise distances distinct: is $f_d(n)=2^{o(d)}$? (Erdős #1088)
Statement
Let $f_d(n)$ be the least $m$ such that any set of $m$ points in $\mathbb{R}^d$ contains $n$ points all of whose pairwise distances are distinct. Estimate $f_d(n)$; in particular, is it true that for every fixed $n\ge3$ $$f_d(n)=2^{o(d)}$$ as $d\to\infty$?
Acceptance. FULLY RESOLVES: determine the growth rate of $f_d(n)$ for fixed $n\ge3$ as $d\to\infty$ — in particular deciding whether $f_d(n)=2^{o(d)}$ — with proof; OR an exact determination of $f_d(n)$ as a function of $d$ and $n$ with proof. Machine-checkable proof preferred, else a complete written proof. ADVANCES (target content beyond the venue's $f_9(3)$ isosceles-set slice): for some fixed $n\ge4$, prove an exponential lower bound $f_d(n)\ge c^{\,d}$ with $c>1$, or a subexponential upper bound, improving on the bounds stated in the background, with proof; OR extend the table of exact values $f_d(n)$ to new pairs $(d,n)$ via a reproducible search with an optimality/exhaustiveness certificate; OR give an improved explicit construction of distinct-distance-free sets for a fixed $n\ge4$. Deliver the proof, or the construction/search code plus the configurations and certificate.
Background
Posed by Erdős [Er75f, p.104]; listed as open on erdosproblems.com/1088 (fetched 2026-07-13, status 'open', tagged 'geometry'). No prize. An easy argument gives $f_d(n)\le n^{O_d(1)}$, and Erdős [Er75f] claimed that he and Straus proved $f_d(n)\le c_n^{\,d}$ for some constant $c_n>0$ (exponential in the dimension); the headline question is whether the base can be lowered to $2^{o(d)}$, i.e. subexponential growth in $d$. Two slices are understood. For $d=1$ (Erdős #530) one has $f_1(n)\asymp n^2$. For $n=3$ the quantity is governed by isosceles-free sets (Erdős #503): $f_d(3)=d^2/2+O(d)$, with Erdős proving $f_2(3)=7$ and Croft [Cr62] proving $f_3(3)=9$. The behaviour for fixed $d$ as $n\to\infty$ is Erdős #1208. This overlaps the venue's problem on the largest isosceles set in $\mathbb{R}^9$ (Erdős #503), which is exactly the $n=3$, $d=9$ slice (that largest isosceles set has size $f_9(3)-1$); the present problem is the general-$d$, general-$n$ growth question, whose distinctive content is the subexponential-in-$d$ conjecture for fixed $n\ge3$. Attacker's tool: explicit constructions and SAT/search over integer or rational point configurations to build large distinct-distance-free (isosceles-free) sets, improving lower bounds on $f_d(n)$ and computing exact small values, together with linear-algebra and polynomial-method bounds on the upper side.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1088 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.