Determine $n_k$: fewest general-position points forcing $k$ whose triples give all-distinct circle radii (Erdős #827)
Statement
Let $n_k$ be minimal such that any $n_k$ points in general position in $\mathbb{R}^2$ (no three on a line, so that every triple determines a unique circle) contain a subset of $k$ points for which all $\binom{k}{3}$ triples determine circles of pairwise distinct radii. Determine $n_k$, and in particular its growth rate as $k\to\infty$.
Acceptance. FULLY RESOLVES: determine $n_k$ exactly for all $k$ (a closed form or exact recurrence, with proof), OR determine its asymptotic growth rate with matching upper and lower bounds up to constant factors, with proof. Machine-checkable proof preferred, else a complete written proof. ADVANCES: improve the best known upper bound $n_k\ll k^5$ stated in the background (a smaller exponent, or a proof of a near-linear bound), with proof; OR prove a super-linear lower bound on $n_k$; OR determine an exact value of $n_k$ for a specific small $k\ge4$ via a reproducible search, delivering both an extremal configuration of $n_k-1$ points containing no valid $k$-subset and a certificate that $n_k$ points always force one. Deliver the proof, or the search code plus the extremal configuration and certificate.
Background
Posed by Erdős [Er75h] and revisited in [Er78c] and [Er92e]; listed as open on erdosproblems.com/827 (fetched 2026-07-13, status 'open', tagged 'geometry'). No prize. In [Er75h] Erdős first asked whether $n_k$ is even finite. In [Er78c] he gave an argument that it is, claiming the bound $n_k\le k+2\binom{k-1}{2}\binom{k-1}{3}$, but this argument is flawed, as explained by Martínez and Roldán-Pensado [MaRo15]. Martínez and Roldán-Pensado supplied a correct proof giving $n_k\ll k^9$, and a simple probabilistic argument (contributed as user FlaredRain in the site discussion) improves this to $n_k\ll k^5$. No nontrivial lower bound beyond the obvious $n_k\ge k$ appears in the cited record, and no exact value of $n_k$ is known for any $k\ge4$. This is a Ramsey-type existence problem in circle geometry, the counterpart of the venue's extremal-counting sibling Erdős #831 (how many distinct-radius circles are forced among $n$ points), which cites the same source [Er75h]. Attacker's tool: for small $k$, computer search (SAT or semi-algebraic/real-solver methods, or randomized construction plus certification) over point configurations to pin exact values of $n_k$ or to produce improved lower-bound configurations; refined probabilistic and hypergraph-Ramsey arguments for the upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #827 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.