Erdős #104 — o(n^2) unit circles through 3+ points

Statement

Given $n$ points in $\mathbb{R}^2$, the number of distinct unit circles (radius-1 circles, center anywhere in the plane) containing at least three of the points is $o(n^2)$.

Erdős additionally offered £100 for a proof or disproof of the sharper claim that the true maximum is $O(n^{3/2})$ [Er92e], and separately asked how many such circles are forced if the points are in general position [Er75h], [Er92e].

Facts

- Prize \$100 (site header); the original text cites £100 [Er92e,p.46]. Status: OPEN (erdosproblems.com/104, reflects site-owner belief; "cannot be resolved with a finite computation"). - Falsifiable: not by a single finite counterexample — the $o(n^2)$ (and $O(n^{3/2})$) claims are asymptotic statements; a disproof needs an infinite family of point sets with $\gg n^2$ (or $\gg n^{3/2+\epsilon}$) unit circles, or a genuine proof for the positive direction. - Origin: Erdős, "Some problems on elementary geometry," Austral. Math. Soc. Gaz. (1975), 2-3 [Er75h]; restated in [Er81d,p.144], [Er83b], [Er92e,p.46], [Er95,p.182]. - Upper bound (trivial, known since Erdős): every pair of points determines at most 2 unit circles through both (center = intersection of two unit circles centered at the two points), so double-counting pairs gives $O(n^2)$. Erdős repeatedly stated this as $n(n-1)$, but Harborth and Mengersen, "Point sets with many unit circles," Discrete Math. (1986), 193-197 [HaMe86], point out the correct double-count gives $\frac{n(n-1)}{3}$ (each circle with $k\ge3$ points contributes $\binom{k}{2}\ge3$ counted pairs). No improvement over this trivial $O(n^2)$ bound for the exact problem as stated has been found in the literature search below — the $o(n^2)$ claim itself, not just the sharper $O(n^{3/2})$ one, is open. - Lower bound (best known): Elekes, "$n$ points in the plane can determine $n^{3/2}$ unit circles," Combinatorica (1984), 131 [El84] — a simple explicit construction with $\gg n^{3/2}$ unit circles through $\geq 3$ points. Erdős proved $\gg n$ is achievable and conjectured $n^{3/2}$ is the truth [Er81d]. This construction is 41 years old and, as far as this search found, has never been beaten (see Literature state). - Related problems: erdos/506 — minimum number of circles determined by $n$ points not all concyclic. erdos/831 — lower bound $h(n)$ on circles of *distinct* radii through 3 points (no 3 collinear, no 4 concyclic). Erdős #90 — the unit distance conjecture (disproved 2026) — the sibling unit distance problem, recently DISPROVED (see Literature state). - OEIS A003829 tracks the maximal number of unit circles for small $n$ (https://oeis.org/A003829). - No Lean/formal-conjectures formalization exists (erdosproblems.com/104 shows "Formalised statement? No").

Literature state

Not resolved. No source found proves or disproves either the $o(n^2)$ statement or the sharper $O(n^{3/2})$ conjecture for Erdős's exact setup (a single arbitrary set of $n$ points, unit circles through $\geq 3$ of them). The erdosproblems.com forum thread for #104 (erdosproblems.com/forum/thread/104) has no comments or claimed progress.

A key derived reformulation (own reasoning, not sourced from a paper — flagged as such): since "unit circle $C$ (center anywhere) passes through points $p,q,r$" is equivalent to "the center of $C$ is at distance 1 from each of $p,q,r$," Erdős's question is *exactly* equivalent, by relabeling the $n$ given points as the centers of $n$ unit circles $S_1,\dots,S_n$, to: how many points in the plane can lie on $\geq 3$ circles of a single family of $n$ congruent (radius-1) circles? This is the "self-orchard problem" for one family of unit circles — as opposed to the structurally different setup below.

Closely related but NOT identical result, already solved: Székely conjectured, and Elekes, Simonovits and Szabó, "A combinatorial distinction between unit circles and straight lines: how many coincidences can they have?", Combin. Probab. Comput. 18(5) (2009), 691-705, proved, that for three separate families of $n$ unit circles each, with family $i$ passing through one of three *fixed, distinct* points $p_1,p_2,p_3$, the number of "triple points" (points lying on one circle from each family) is $O(n^{2-\eta})$ for some $\eta>0$ — genuinely $o(n^2)$, in contrast to three pencils of *lines* through 3 fixed points, which can achieve $\Theta(n^2)$ triple points. This was improved by Raz, Sharir, Solymosi, "On triple intersections of three families of unit circles," Discrete Comput. Geom. (2016), arXiv:1407.6625, to $O(n^{11/6})$, via the Elekes–Szabó algebraic/group method (Elekes–Szabó, Combinatorica 2012; Elekes–Rónyai, J. Combin. Theory Ser. A 2000). This is a structurally different question — three fixed points with three separate pencils of circles, vs. #104's single arbitrary $n$-point set with one self-family — but it is the closest existing "unit circles beat lines, $o(n^2)$" result in the literature, and the Elekes–Szabó group/polynomial method (exploiting that unit circles are cosets of the rotation-translation group $SE(2)$, giving an algebraic surface whose Cartesian-product intersection can be bounded) is the natural technique to try to adapt to the single-family self-orchard version. - Generic pseudocircle/curve incidence bounds (Clarkson–Edelsbrunner–Guibas–Sharir–Welzl-type "$k$-rich point" bounds for families of curves with $O(1)$ intersections per pair) give $O(n^2/k^3+n/k)$ rich points for $k=3$, i.e. only $O(n^2)$ again — they reproduce, but do not beat, the trivial double-counting bound, because they do not exploit the specific algebraic (congruence/coset) structure of unit circles. Breaking below $n^2$ requires that extra algebraic structure, exactly as ESS/RSS do for the three-pencil case. - Highly relevant sibling development (verified real, 2026, post my training cutoff): the closely related Erdős unit-distance problem, erdosproblems.com/90 ("does every $n$-point set have at most $n^{1+O(1/\log\log n)}$ unit distances?"), was DISPROVED and Lean-verified in May 2026. An internal OpenAI reasoning model produced a counterexample construction beating the conjectured near-linear bound; a human-digested, peer-reviewed companion paper — Alon, Bloom, Gowers, Litt, Sawin, Shankar, Tsimerman, Wang, Wood, "Remarks on the disproof of the unit distance conjecture," arXiv:2605.20695 (May 20 2026) — confirms the construction, crediting ideas from Ellenberg–Venkatesh, Golod–Shafarevich, and Hajir–Maire–Ramakrishna (infinite class field towers / algebraic number theory), beating the classical square-grid construction. Sawin, arXiv:2605.20579, made the bound explicit ($u(n) > n^{1.014}$ for arbitrarily large $n$); subsequent optimization (Emmerich, arXiv:2606.03419) pushed this to $n^{1.0152}$, and to $n^{1.031}$ with an enlarged prime set (Emmerich–Cordella), with community (MathOverflow) claims beyond $n^{1.035}$–$n^{1.036}$ noted in that paper as of its v4. Note: this disproves only the *conjectured exponent* of the lower bound; the best known *upper* bound on unit distances is still Spencer–Szemerédi–Trotter's classical $O(n^{4/3})$ (1984), confirmed current in Pach, Raz, Solymosi, "Erdős's unit distance problem and rigidity," arXiv:2507.15679, which reduces further improvement to a conjecture on rigid frameworks. This does not directly resolve #104 (unit circles vs. unit distances are different objects, though closely coupled), but it is the single most important nearby fact: it shows (a) that Elekes-style "obvious" extremal grid constructions for unit-distance/unit-circle-type problems are *not* always optimal — deep algebraic-number-theoretic constructions can beat them, suggesting Elekes's 1984 $n^{3/2}$ construction for #104 has never been seriously re-examined with modern tools and might be beatable; and (b) that AI-assisted search over algebraic-number-theoretic constructions is now a demonstrated, verified (Lean) technique for exactly this class of "how many coincidences among $n$ points" extremal geometry problem. - No evidence found that any AI system (GPT, AlphaEvolve, DeepMind formal-conjectures, Aristotle) has been applied to #104 specifically — the AI contributions wiki (github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems) was checked via search and no mention of problem 104 was found.

Attack surface

- Mode: derivation+formalization primarily (both directions — improving the lower-bound construction, or proving a genuine $o(n^2)$ upper bound — require real mathematical technique, not finite search), with a secondary finite-search angle for small-$n$ extremal configurations (OEIS A003829) that could suggest structure. - Concrete first experiment (upper-bound / proof direction): attempt to adapt the Elekes–Szabó group-method proof of Raz–Sharir–Solymosi (arXiv:1407.6625) — which handles three fixed pencils of unit circles — to the single self-family case (all $n$ circles' centers are *free*, i.e. the "coincidence" configuration is one Cartesian product of the point set with itself rather than three fixed points). This means re-deriving the algebraic-surface reduction (Elekes–Szabó, Combinatorica 2012) for the "diagonal"/self-intersecting case, which is the genuine mathematical gap between the solved 3-pencil case and open #104. - Concrete first experiment (lower-bound / construction direction): computationally search whether algebraic-number-theoretic constructions in the style of the 2026 unit-distance disproof (arXiv:2605.20695, arXiv:2605.20579) — points derived from prime ideals in number fields with controlled class field towers — can be adapted (points at controlled *pairwise distances forming many concyclic unit-circle triples* rather than just many unit-distance pairs) to beat Elekes's 1984 $n^{3/2}$ bound. This is speculative but directly motivated by the demonstrated fact that AI-assisted algebraic constructions beat the "obvious" grid-type answer in the sibling problem. - Concrete first experiment (empirical/finite): CP-SAT or direct enumeration over small $n$ (extend OEIS A003829, https://oeis.org/A003829) to check whether Elekes's construction is empirically extremal for small $n$, or whether other configurations (e.g. algebraic/number-theoretic point sets analogous to the unit-distance disproof) already beat it at accessible $n$ — a finite computational check that could motivate (not prove) a stronger construction. - Oracle: for constructions — direct, mechanical (compute all pairwise "unit-circle-through-pair" candidates, count triples/circles with $\geq3$ points, exact rational/algebraic arithmetic to avoid floating point error, as done for OEIS A003829). For a proof of $o(n^2)$ or $O(n^{3/2})$ — no mechanical oracle; would need peer review / Lean formalization (none exists yet for #104). - Feasibility: honest read — famous-and-hard for the general proof direction (open since 1975, resisted the same Elekes–Rónyai–Szabó school that solved the adjacent 3-pencil case), but the construction/lower-bound direction is comparatively underexplored (a 1984 bound never revisited with modern algebraic or AI-search tools) and the adaptation of the Raz–Sharir–Solymosi self-family argument is a well-scoped, concrete research gap rather than requiring wholly new machinery — this is the most promising near-term lever.

Related

- erdos/506 — minimum number of circles (any radius) determined by $n$ points not all on one circle; same "circles through $\geq3$ points" family, dual extremal direction (minimize vs. maximize), unit-radius restriction dropped. - erdos/831 — lower bound on the number of circles of *distinct radii* through 3 points among $n$ points (no 3 collinear, no 4 concyclic); same underlying "concyclic triples" combinatorics, complementary radius constraint. - Erdős #90 — the unit distance conjecture (disproved 2026) — Erdős's unit-distance problem; DISPROVED and Lean-verified May 2026 via AI-generated algebraic-number-theoretic construction (arXiv:2605.20695); the closest sibling problem and the source of the most promising unexplored technique for #104's lower bound. - concept/elekes-szabo-method — the polynomial/algebraic-surface + group-coset technique (Elekes–Rónyai 2000, Elekes–Szabó 2012) used by ESS (2009) and Raz–Sharir–Solymosi (2016) to prove $o(n^2)$, even $O(n^{11/6})$, for the *three-pencil* unit-circle coincidence problem; the natural target for adaptation to #104's single-family case. - concept/incidence-double-counting — the elementary "each pair of points lies on $\leq2$ unit circles" argument giving the (only known) $O(n^2)$ upper bound (Erdős 1981, corrected constant by Harborth–Mengersen 1986). - concept/pseudocircle-arrangement-k-rich-points — Clarkson–Edelsbrunner–Guibas–Sharir–Welzl-type generic curve-arrangement bounds; shown here to only reproduce, not beat, the trivial $O(n^2)$ bound for unit circles, motivating why the extra algebraic (coset) structure is essential. - concept/algebraic-number-theory-extremal-constructions — class field towers / Golod–Shafarevich-style constructions (Ellenberg–Venkatesh, Hajir–Maire–Ramakrishna ideas) that produced the 2026 AI-discovered, Lean-verified disproof of the unit-distance conjecture (arXiv:2605.20695); the main speculative lever for beating Elekes's 1984 $n^{3/2}$ construction on #104. - concept/ai-assisted-extremal-construction-search — the demonstrated OpenAI-reasoning-model-plus-human-verification pipeline (arXiv:2605.20695, arXiv:2605.20579, arXiv:2606.03419) that found and then progressively optimized (via nonlinear integer optimization) an explicit extremal construction beating a decades-old conjectured bound — a directly transferable methodology for #104's open construction side.

PRIOR-ART SCAN (2026-07-03)

Verdict: HARD-OPEN. The exact problem (single arbitrary $n$-point set, $o(n^2)$ or $O(n^{3/2})$ unit circles through $\geq3$ points) is confirmed still fully unresolved in the literature, with no active claimed work targeting it directly. This is not a case of missed prior art like #64 — nobody, in the sources checked below, has attacked this specific formulation since Elekes's 1984 construction and Erdős's own $O(n^2)$ double-count.

Sources actually read/fetched (2026-07-03): - https://www.erdosproblems.com/104 (direct curl w/ browser UA, HTTP 200) — official remarks re-confirmed verbatim: OPEN, $100/£100 split explained, no new literature flagged by site owner. - https://www.erdosproblems.com/forum/discuss/104 (direct curl, full comment thread fetched) — 4 comments total, read in full: (1)/(2) a currency/prize-amount clarification thread (qawsed vs. Thomas Bloom, Dec 2025–Jan 2026) about why $100 ≠ £100-converted, resolved by a site edit; (3) DesmondWeisenberg (Aug 2025) pointing out Erdős also posed the question in [Er83b] p.18, already incorporated into the page's citation list. None of the 4 comments contain any mathematical progress, partial result, or solution claim. The "reactions" panel shows alexalex123456789 flagged as "working on formalising the results on this problem" — this refers to formalizing the *known* elementary bounds (double-counting, Elekes construction), not a new result; no Lean PR or formalization exists yet (site still shows "Formalised statement? No"). - github.com/teorth/erdosproblems — searched via GitHub search API for issues/PRs mentioning "104" + "unit circles": the only hit is PR #104 ("Add A062249 to problem 647"), an unrelated PR that happens to be GitHub PR number 104 — not about Erdős problem #104. No dedicated branch, data file, or discussion tied to this problem exists in the repo (checked, contra the #64 lesson). - github.com/teorth/erdosproblems/wiki/AI-contributions-to-Erdős-problems (fetched) — no mention of problem 104 anywhere in the page. - OpenAlex citation graph for the two nearest technical papers, queried directly via API: - Elekes–Simonovits–Szabó 2009 (OpenAlex W2166746278): only 2 citing works since 2022, both the same Solymosi–Zahl paper (preprint + journal version). - Raz–Sharir–Solymosi 2016 journal version (OpenAlex W2570731303): 11 citing works total, ever; only 3 since 2022 (one an unrelated agriculture paper — a metadata false-positive). - Solymosi–Zahl, "Improved Elekes–Szabó type estimates using proximity," arXiv:2211.13294 / JCTA 2023 (abstract read via WebFetch) — a general Elekes–Szabó Cartesian-product estimate improving the exponent from $11/6$ to $12/7$ for the underlying algebraic machinery; does not mention unit circles, three families of unit circles, or #104, and was not applied to the ESS/RSS unit-circle setting by the authors. Flagged here only as an unexploited lever: plugging this sharper general bound into the Raz–Sharir–Solymosi framework would presumably improve their $O(n^{11/6})$ triple-point bound for the (structurally different, already-solved) 3-pencil problem — it does not touch #104's single-family case. - Red herring caught and discarded: a WebSearch summary claimed "the constant of Elekes's construction was improved from 1 to about 1.27," which sounded directly relevant to #104's $n^{3/2}$ lower bound. Verified via WebFetch of the actual paper, Klein–?, "The constant of point-line incidence constructions," arXiv:2210.04821 (abstract read in full) — this is about a different, unrelated "Elekes construction": Elekes's classical point-*line* lower-bound construction for the Szemerédi–Trotter theorem constant, nothing to do with Elekes's 1984 unit-*circle* construction [El84]. Elekes's 1984 $n^{3/2}$ unit-circle bound remains unimproved and unrevisited, as stated in the existing Literature-state section above — this scan actively ruled out the one candidate "improvement" that surfaced. - Pach–Raz–Solymosi, arXiv:2507.15679 (abstract re-verified via WebFetch) — confirmed again to be about the unit-*distance* problem (point–circle incidences), not the unit-*circle*-through-3-points problem; does not mention #104 or Elekes's construction. - General WebSearches ("unit circles three points o(n^2)", "unit circles incidence 2025 2026", "self-family unit circles construction beat n^{3/2}") turned up no new papers, preprints, or blog posts beyond what is already cited on the erdosproblems.com page and in this wiki page's existing Literature-state section.

Net effect of this scan: confirms, rather than overturns, the existing page's conclusion. No resolution, no active claimed work, no beatable lower-bound improvement found, and one plausible-looking "improvement" (the 1.27 constant) is explicitly ruled out as a same-name-different-object false lead. The existing "Attack surface" section's two concrete directions (adapt Elekes–Szabó self-family/diagonal case; try algebraic-number-theoretic constructions à la the 2026 unit-distance disproof) remain the most promising unexplored levers — no one else has published on either as of this scan.