Points with no 3 on a line and no 4 on a circle: is the number of distinct distances superlinear? (Erdős #98)
Statement
Let $h(n)$ be the largest number such that any $n$ points in $\mathbb{R}^2$ with no three on a line and no four on a circle determine at least $h(n)$ distinct distances. Does $h(n)/n\to\infty$?
Acceptance. FULLY RESOLVES: a proof that $h(n)/n\to\infty$, or a disproof — an explicit infinite family of configurations (no three collinear, no four concyclic) with $O(n)$ distinct distances, with a complete correctness proof of both the position constraints and the distance count. Machine-checkable (Lean/Coq) preferred, else a full written proof. ADVANCES: (a) a proof of $h(n)\ge n$, or any lower bound superlinear in $n$, or any lower bound strictly better than the best general-position-free bound stated in the background; (b) a construction giving an upper bound with strictly smaller growth than the $n\exp(c\sqrt{\log n})$ bound stated in the background, with proof; (c) exact values of $h(n)$ for small $n$ established by exhaustive, reproducible search with a certificate of exhaustiveness (code + configuration witnesses). Deliver the proof file, or the construction with its verification, or the search code plus certified table of small-$n$ values.
Background
A recurring Erdős question, appearing in [Er75f, p.101], [Er83c], [Er87b, p.167], [Er90], [Er92b], [EFPR93], [Er94b] and [Er97e]; listed as open on erdosproblems.com/98 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Without the position constraints, lattice sections show that $n$ points can determine as few as $O(n/\sqrt{\log n})$ distinct distances (Guth–Katz proved $\gg n/\log n$ is forced); the no-three-collinear/no-four-concyclic hypotheses kill those lattice examples, and the question is whether they force superlinearly many distances. The frontier: Erdős could not even prove $h(n)\ge n$, which remains open. On the upper-bound side, Pach constructed configurations showing $h(n)<n^{\log_2 3}\approx n^{1.585}$, improved in [EFPR93] to $$h(n)<n\exp(c\sqrt{\log n})$$ for some constant $c>0$ — barely superlinear, so the answer is delicately balanced. Closely related venue neighbour: Szemerédi's conjecture that $n$ points with no three collinear determine at least $\lceil n/2\rceil$ distinct distances (Erdős #1082) — that problem drops the concyclicity condition and asks for a linear bound, whereas #98 asks whether the stronger hypotheses force superlinear growth. The statement is formalised in Lean in DeepMind's formal-conjectures repository. The attacker's tools: explicit low-distance constructions respecting both constraints (perturbed lattices, algebraic curves, computer search over small configurations) to push the upper bound down, incidence-geometry arguments for lower bounds, and exact computation of $h(n)$ for small $n$ via exhaustive certified search.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #98 (T. F. Bloom) | website |
| REF-02 | Formalised Lean statement of Erdős #98 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.