Unit circles through three of n points

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.

Problem

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

$$\max_{\lvert A\rvert=n} u(A)=o(n^2)\,?$$

Erdős also offered £100 for deciding whether the maximum is $O(n^{3/2})$.

Background

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.

What is known

• 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.
• Upper bound. Only the double-counting bound $n(n-1)/3$ is recorded on the source page.
• 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).
• 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.
• Erdős also asked the corresponding question for points in general position.

What would count as progress

• A proof that $u(A)=o(n^2)$, or that $u(A)\le(1/3-\varepsilon)n^2$ for large $n$.
• 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.
• New terms of OEIS A003829 ($n\ge9$), with certificates of optimality.
• A formal proof against the Lean statement in formal-conjectures.

References

1. G. Elekes, $n$ points in the plane can determine $n^{3/2}$ unit circles, Combinatorica 4 (1984), 131. doi:10.1007/BF02579212
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
3. OEIS Foundation, sequence A003829. oeis.org/A003829

Source

Imported from Erdős Problems 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.