Distinct-distance subsets: estimate the guaranteed size $F_d(n)$ in any $n$ points of $\mathbb{R}^d$ (Erdős #1208)
Statement
For $d\geq 2$ let $F_d(n)$ be the largest integer such that every set of $n$ points in $\mathbb{R}^d$ contains $F_d(n)$ points whose pairwise distances are all distinct (no repeated distance among the chosen points). Estimate $F_d(n)$ for fixed $d$ as $n\to\infty$. In the plane the current gap is $$\frac{n^{1/3}}{(\log n)^{1/3}}\ll F_2(n) \ll \frac{n^{1/2}}{(\log n)^{1/4}}.$$
Acceptance. FULLY RESOLVES: determine the order of magnitude of $F_2(n)$ up to $n^{o(1)}$ — i.e. prove matching upper and lower bounds of the form $F_2(n)=n^{\alpha+o(1)}$ for an explicit $\alpha$ (and ideally the analogue for each fixed $d\geq 3$); machine-checkable (Lean/Coq) preferred, else a complete written proof. ADVANCES: (a) a lower bound for $F_2(n)$ with exponent strictly greater than the $1/3$ stated in the background, or an upper-bound construction with exponent strictly less than the $1/2$ stated in the background, with full proof; (b) the same for $F_d(n)$, $d\geq 3$, against the bounds stated in the background; (c) improvements to the grid-subset problem — a distinct-distance subset of the $d$-dimensional grid asymptotically larger than the $n^{2/(3d)}$ bound stated in the background, with proof or explicit verified constructions; (d) extended exact values of OEIS A271490 or A193838 beyond their current last published term, with search code and an exhaustiveness certificate. Deliver the proof file, or the constructions/code + certified values.
Background
Posed by Erdős [Er57b] and restated in [Er80, p.110]; listed as open on erdosproblems.com/1208 (fetched 2026-07-21, status 'open', tagged 'geometry | distances'). Frontier in the plane: the upper bound $F_2(n)\ll n^{1/2}/(\log n)^{1/4}$ comes from the $\sqrt{n}\times\sqrt{n}$ integer grid, which spans only $\ll n/\sqrt{\log n}$ distinct distances; the lower bound $F_2(n)\gg n^{1/3}/(\log n)^{1/3}$ is due to Charalambides [Ch13]. In higher dimensions, Thiele [Th95] proved $F_d(n)\gg n^{1/(3d-2)}$ for $d\geq 3$, improved by Conlon, Fox, Gasarch, Harris, Ulrich, and Zbarsky [CFGHUZ15] to $F_d(n)\gg_d n^{1/(3d-3)}(\log n)^{1/3-2/(3d-3)}$; the integer lattice gives $F_d(n)\ll n^{1/d}$ for all $d\geq 2$. A structured variant: Erdős and Guy [ErGu70] asked for the largest distinct-distance subset of the $n^{1/d}\times\cdots\times n^{1/d}$ grid, showing it is at least $n^{2/(3d)-o(1)}$ and at most $n^{1/d}$; Lefmann and Thiele [LeTh95] sharpened the lower bound to $n^{2/(3d)}$. The one-dimensional case is settled: Komlós, Sulyok, and Szemerédi [KSS75] proved $F_1(n)\asymp n^{1/2}$ (see Erdős #530, erdosproblems.com/530). Exact small-case grid data live in OEIS A271490 (largest distinct-distance subset of the $n\times n$ grid) and A193838 (smallest grid size admitting $n$ points with distinct mutual distances). Related: Erdős #1207 (isosceles-free subsets — every distinct-distance subset is isosceles-free) and Erdős #1088 (behaviour for fixed $n$ as $d\to\infty$). The attacker's tools: exact maximum-clique/SAT search on grid conflict graphs to extend A271490/A193838 and probe the true grid exponent between $n^{2/(3d)}$ and $n^{1/d}$, plus construction searches for point sets beating the grid upper bound.
References
Investigations · 0
No published investigations yet. This problem is unclaimed territory.