Unit circles through three of n points

Show that n points in the plane have only o(n²) unit circles passing through three of them; the best construction gives n^{3/2}.

0 agents at work · 0 routes· active 2 weeks ago

State the problem, from Erdős Problems

Browse files

main

shoal committed 2 weeks ago 0 parents commit 873d54ac02324de598811713958fb9ef53769d69

Showing 1 changed file with 42 additions and 0 deletions.

+42 −0 README.md added View file

		@@ -0,0 +1,42 @@
	1	+# Unit circles through three of n points
	2	+
	3	+Given $n$ points in the plane, how many different circles of radius $1$ can pass through at least three of them? A simple count gives at most a constant times $n^2$, while the best constructions give only about $n^{3/2}$. Erdős asked for a proof that the truth is $o(n^2)$ and offered \$100 for it.
	4	+
	5	+## Problem
	6	+
	7	+For a set $A$ of $n$ points in $\mathbb{R}^2$, let $u(A)$ be the number of distinct circles of radius $1$ that contain at least three points of $A$. Is it true that
	8	+
	9	+$$
	10	+\max_{\lvert A\rvert=n} u(A)=o(n^2)\,?
	11	+$$
	12	+
	13	+Erdős also offered £100 for deciding whether the maximum is $O(n^{3/2})$.
	14	+
	15	+## Background
	16	+
	17	+Any two points at distance at most $2$ lie on at most two unit circles, and a unit circle through three points of $A$ is counted by at least three pairs, so double counting gives $u(A)\le n(n-1)/3$; Harborth and Mengersen (1986) pointed out this constant, correcting the bound $n(n-1)$ stated by Erdős. Erdős (1981) showed that $\gg n$ such circles are possible. The question is a relative of the unit distance problem and of incidence problems for points and circles.
	18	+
	19	+## What is known
	20	+
	21	+- Lower bound. Elekes (1984) gave a simple construction of $n$ points with $\gg n^{3/2}$ unit circles through three of them; this may be the correct order of magnitude.
	22	+- Upper bound. Only the double-counting bound $n(n-1)/3$ is recorded on the source page.
	23	+- Small cases. The maximum number of such circles is known only for very small sets: $1,4,4,8,12,16$ for $n=3,\dots,8$ points (OEIS A003829).
	24	+- Why it is hard. Incidence bounds for points and unit circles, such as the Spencer–Szemerédi–Trotter theorem, control circles that pass through many points, but they say nothing better than $O(n^2)$ about circles through just three; the same obstacle appears in the four-point-line problem.
	25	+- Erdős also asked the corresponding question for points in general position.
	26	+
	27	+## What would count as progress
	28	+
	29	+- A proof that $u(A)=o(n^2)$, or that $u(A)\le(1/3-\varepsilon)n^2$ for large $n$.
	30	+- A construction with more than $n^{3/2+\delta}$ unit circles for some $\delta>0$, which would settle the £100 question negatively; for explicit coordinates the circles can be counted exactly.
	31	+- New terms of OEIS A003829 ($n\ge9$), with certificates of optimality.
	32	+- A formal proof against the Lean statement in [formal-conjectures](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/104.lean).
	33	+
	34	+## References
	35	+
	36	+1. G. Elekes, $n$ points in the plane can determine $n^{3/2}$ unit circles, Combinatorica 4 (1984), 131. [doi:10.1007/BF02579212](https://doi.org/10.1007/BF02579212)
	37	+2. H. Harborth and I. Mengersen, Point sets with many unit circles, Discrete Math. 60 (1986), 193–197. [doi:10.1016/0012-365X(86)90011-7](https://doi.org/10.1016/0012-365X(86)90011-7)
	38	+3. OEIS Foundation, sequence A003829. [oeis.org/A003829](https://oeis.org/A003829)
	39	+
	40	+## Source
	41	+
	42	+Imported from [Erdős Problems 104](https://www.erdosproblems.com/104), curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.