Isosceles-free planar sets: must n points determine at least f(n)·n distances with f(n) → ∞? (Erdős #657)
Statement
Is it true that if $A\subset \mathbb{R}^2$ is a set of $n$ points such that every subset of $3$ points determines $3$ distinct distances (i.e. $A$ has no isosceles triangles, degenerate ones included), then $A$ must determine at least $f(n)\,n$ distinct distances, for some $f(n)\to \infty$? Note that the hypothesis forces all $n-1$ distances from any fixed point to be distinct, so $A$ always determines at least $n-1$ distinct distances; the question is whether the total must be superlinear in $n$.
Acceptance. FULLY RESOLVES: a proof that every isosceles-free set of $n$ points in $\mathbb{R}^2$ determines at least $f(n)\,n$ distinct distances for some explicit $f(n)\to\infty$ (machine-checkable Lean/Coq preferred, else a complete written proof); OR a construction: an explicit infinite family of isosceles-free planar $n$-point sets determining $O(n)$ distinct distances, with proof. ADVANCES: an improvement of either one-dimensional bound stated in the background — raise the lower bound strictly above $2^{c(\log n)^{1/9}}$ or lower the upper bound strictly below $2^{O(\sqrt{\log n})}$ — with proof; a planar lower bound $f(n)\to\infty$ under an extra structural hypothesis (e.g. general position); or certified exact minimal distinct-distance counts for isosceles-free planar sets at concrete small $n$, with reproducible search code and an exhaustiveness argument over the combinatorial types searched. Deliver the proof file, or the construction/search code with its certificates.
Background
Erdős attributed the problem (posed more generally in $\mathbb{R}^k$) to himself and Davies [Er73]; in [Er97e] he says it was investigated by himself, Füredi, Ruzsa, and Pach, and it also appears in [Er75f, p.101] and [ErPa90]. Listed as open on erdosproblems.com/657 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'; page last edited 15 October 2025). Even the one-dimensional case is substantial: as Adenwalla observed (noted on the page), for $A\subset\mathbb{R}$ the isosceles-free condition says exactly that $A$ has no three-term arithmetic progression, and the problem becomes minimising the number of distinct differences of an $n$-element 3AP-free set of reals. In that setting Dumitrescu [Du08] proved $(\log n)^c \le f(n) \le 2^{O(\sqrt{\log n})}$ for some $c>0$, and — as Hunter observed, with details worked out by Alfaiz and Tang — the strong 3AP-free-set bounds of Kelley–Meka [KeMe23], as improved by Bloom–Sisask [BlSi23], yield $2^{c(\log n)^{1/9}} \le f(n)$ in $\mathbb{R}$. A 3AP-free set on a line, viewed as a planar set, is isosceles-free, so the planar minimum is at most the one-dimensional minimum and $f(n)\le 2^{O(\sqrt{\log n})}$ holds in the plane as well; whether $f(n)\to\infty$ for planar sets remains open. In high dimension the growth disappears: Straus observed that if $2^k\ge n$ there exist $n$ points in $\mathbb{R}^k$ containing no isosceles triangle that determine at most $n-1$ distances. See also Erdős #135 (erdosproblems.com/135). The attacker's tool: additive combinatorics (transfer of 3AP-free difference-set bounds) plus planar incidence geometry; computationally, certified minimal distinct-distance counts for isosceles-free planar configurations at small $n$ (exact search over combinatorial types, or optimisation with rational certificates) to map the low-end growth of $f$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #657 (T. F. Bloom) | website |
| REF-02 | Kelley–Meka, Strong bounds for 3-progressions (arXiv:2302.05537) | arxiv |
| REF-03 | Bloom–Sisask, An improvement to the Kelley–Meka bounds on three-term arithmetic progressions (arXiv:2309.02353) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.