How many unit circles can $n$ points determine through $\ge 3$ points? Prove $o(n^2)$ (Erdős #104)
Statement
Let $n$ points be given in $\mathbb{R}^2$. Call a circle of radius $1$ 'determined' if it passes through at least three of the points. Prove that the number of distinct determined unit circles is $o(n^2)$ as $n\to\infty$. Erdős further conjectured the sharper bound $O(n^{3/2})$; decide whether the maximum number of determined unit circles is $O(n^{3/2})$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred) that the number of distinct unit circles through at least three of $n$ points is $o(n^2)$, and/or a proof or disproof of the sharper $O(n^{3/2})$ bound — a disproof being an explicit infinite family with $\gg n^{3/2+\delta}$ (or $\gg n^2$) determined unit circles for some $\delta>0$, given with coordinates and a verifiable incidence count. ADVANCES (each independently checkable): (a) a lower-bound construction beating the best bound stated in the background ($\gg n^{3/2}$ determined unit circles, Elekes), delivered as explicit coordinates plus a machine-checkable count; (b) an upper bound of the form $o(n^2)$, or any $O(n^2/\phi(n))$ with $\phi(n)\to\infty$, improving on the double-count bound $n(n-1)/3$, with proof; (c) new exact values or improved lower bounds for OEIS A003829 at specific $n$, with the search code and a certificate. Deliver the proof file, the explicit configuration plus incidence certificate, or the search code plus extended table.
Background
Posed by Erdős in several places [Er75h, p.2; Er81d, p.144; Er83b; Er92e, p.46; Er95, p.182]; tagged 'geometry' (distances/incidences). Erdős offered £100 for a proof or disproof of the $O(n^{3/2})$ bound. Frontier: Erdős [Er81d] showed that $\gg n$ determined unit circles are possible and that there are at most $O(n^2)$, by the simple double count that each pair of points lies on at most two unit circles; Harborth and Mengerson [HaMe86] corrected the explicit constant of this argument to $n(n-1)/3$ (Erdős had repeatedly stated $n(n-1)$). Elekes [El84] gave a simple construction with $\gg n^{3/2}$ determined unit circles, which may be the correct order of magnitude. The maximal number of unit circles passing through at least three of $n$ points is OEIS A003829. Erdős [Er75h; Er92e] also asked the analogous question for points in general position. Related: Erdős #506 and #831 (erdosproblems.com/506, erdosproblems.com/831). Listed as open on erdosproblems.com/104 (fetched 2026-07-13, status 'open'); no formalisation exists. Attacker's tool: extremal lattice/algebraic constructions to push the lower bound toward the conjectured $n^{3/2}$ and to extend A003829 by exact small-$n$ search, together with unit-circle incidence bounds (a Szemerédi–Trotter analogue for unit circles) toward the $o(n^2)$ and $O(n^{3/2})$ upper bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #104 (T. F. Bloom) | website |
| REF-02 | OEIS A003829 — maximal number of unit circles through at least three of n points | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.