Erdős Problem #104

Erdős Problem 104: unit circles through three points

1. Statement and scope

For an $n$-point planar set $P$, let $C(P)$ count the distinct circles of radius one that contain at least three points of $P$. The problem asks whether $C(P)=o(n^2)$ uniformly. It remains unresolved. We prove the correct elementary quadratic bound, its richer-circle variant, and reconstruct in full the known Elekes construction giving $\Omega(n^{3/2})$ such circles. No new lower-bound order is claimed.

2. Pair counting, including the constant

Given two distinct points, a unit circle containing both has its center at an intersection of the two unit circles centered at those points. Thus there are at most two possible centers, at most one when their separation is two, and none when it exceeds two. Write $r_\Gamma=|P\cap\Gamma|$. Double-counting pairs of points on circles gives \[ \sum_{\Gamma:\,r_\Gamma\ge3}\binom{r_\Gamma}{2} \le2\binom n2=n(n-1). \] Since every summand is at least three, \[ C(P)\le\frac{n(n-1)}3.\tag{1} \] More generally the number $C_k(P)$ of unit circles containing at least $k\ge3$ points satisfies \[ C_k(P)\le\frac{2n(n-1)}{k(k-1)}.\tag{2} \] The factor two in $2$ is necessary for this double count: a point pair can belong to two different unit circles.

3. A complete $n^{3/2}$ construction

Choose a transcendental real number $t\in(0,1)$ and, for $1\le i\le m$, define the unit vectors \[ u_i=(t^i,\sqrt{1-t^{2i}}). \] Distinct finite subsets of $\{1,\ldots,m\}$ have distinct sums of these vectors. Indeed, equality of their first coordinates would give a nonzero polynomial in $t$ with integer coefficients equal to zero, contrary to transcendence. This observation simultaneously verifies all point and center distinctness conditions below.

Take \[ P_m=\{u_i+u_j:1\le i<j\le m\},\qquad |P_m|=\binom m2. \] For each three-element set $\{i,j,k\}$, form the unit circle centered at \[ c_{ijk}=u_i+u_j+u_k. \] It contains the three distinct points $u_i+u_j$, $u_i+u_k$, and $u_j+u_k$, since their differences from the center are respectively $-u_k,-u_j,-u_i$, all of norm one. Different three-element sets have different centers by the first-coordinate argument, so they give distinct unit circles. Therefore \[ C(P_m)\ge\binom m3 =\left(\frac{\sqrt2}{3}+o(1)\right)|P_m|^{3/2} \qquad(m\to\infty).\tag{3} \] Extra incidences, if any occur, cause no problem: the requirement is at least three points, and the circles are already distinguished by their centers.

This works for every sufficiently large point count up to the same asymptotic constant. Given $n$, take the largest $m$ with $\binom m2\le n$ and add distinct arbitrary points until there are $n$ in total. All the previously counted circles persist. Since $m=\sqrt{2n}+O(1)$, the lower bound is still $(\sqrt2/3+o(1))n^{3/2}$.

4. Assessment and attribution

The construction is the known Elekes subset-sum mechanism, with a transcendental parameter used here to make every distinctness check explicit. It shows that an upper bound smaller than order $n^{3/2}$ is impossible. Bound $1$ leaves a gap between the powers $3/2$ and $2$; it neither proves the conjectured little-$o(n^2)$ statement nor the stronger proposed $O(n^{3/2})$ bound.

Sources: https://www.erdosproblems.com/104; G. Elekes, $n$ points in the plane can determine $n^{3/2}$ unit circles, Combinatorica 4 $1984$, p. 131, https://doi.org/10.1007/BF02579212. The construction and upper bounds used in this attempt are fully proved above.

Completion rate estimate: 35%.

Erdős Problem #104

FORMAL RESTATEMENT

Verbatim problem statement (from file). "Given $n$ points in $\R^2$ the number of distinct unit circles containing at least three points is $o(n^2)$."

Definitions and conventions. Let $P\subset\R^2$ with $|P|=n$. A unit circle means a Euclidean circle of radius $1$. Let $C(P)$ be the number of distinct unit circles $\Gamma$ such that $|\Gamma\cap P|\ge 3$. The conjectured asymptotic statement is: \[\sup_{|P|=n} C(P) = o(n^2)\quad\text{as }n\to\infty. \]

QUICK LITERATURE/CONTEXT CHECK

No external browsing was used. The file states:

• Erdős proved $C(P)$ can be $\gg n$.
• A simple pair-counting argument gives $C(P)=O(n^2)$, with a corrected constant upper bound $\frac{n(n-1)}{3}$.
• A construction (Elekes) gives $\gg n^{3/2}$ such circles.

Below I re-prove the $\frac{n(n-1)}{3}$ upper bound and give an explicit elementary construction with $\Omega(n)$ circles.

ATTACK PLAN

• Upper bound: Double count point-pairs vs circles, using that each pair lies on at most two unit circles and each qualifying circle contains at least three pairs.
• Lower bound: Exhibit an explicit family of point sets with many distinct unit circles, and verify the circle count exactly.
• Hard part (not solved here): Improve the $O(n^2)$ upper bound to $o(n^2)$.

WORK

FAST REALITY CHECK (tiny $n$).

• $n<3$: $C(P)=0$.
• $n=3$: $C(P)$ can be $1$ if the three points lie on a unit circle.

VERIFICATION

• In the upper bound, the only geometric fact needed is: through two points there are at most two unit circles. This was checked by considering intersection of radius-1 circles around each point.
• In the construction, for each $i$ the circle $\Gamma_i$ is well-defined because the diameter endpoints are distance $2$ apart.
• Distinctness of circles follows from distinct centers.

FINAL

UNRESOLVED.

1. Strongest proved partial result here: For any $n$ points, $C(P)\le n(n-1)/3$ (Lemma), and there are explicit configurations with $C(P)\ge c n$ for an absolute $c>0$ (Proposition).
2. First gap (crisp): Improve the general upper bound from $O(n^2)$ to $o(n^2)$: prove that for every $\varepsilon>0$ and all sufficiently large $n$, any $n$-point set has at most $\varepsilon n^2$ unit circles containing $\ge 3$ points.
3. Top 3 next moves (concrete):
   1. Attempt to adapt point-circle incidence bounds (e.g. polynomial partitioning for circles) to bound the number of "3-rich" unit circles.
   2. Study structured constructions (lattices, Cartesian products) to see whether $n^{3/2}$ is a genuine barrier; implement a computational search for $n\le 50$ to estimate growth of the maximum.
   3. Prove intermediate statements: for example, show $C(P)=o(n^2)$ under mild "general position" assumptions, then try to remove assumptions.
4. What a minimal counterexample would likely look like: A family $P_n$ with $|P_n|=n$ and $C(P_n)\ge c n^2$ for some fixed $c>0$, meaning a positive fraction of all point pairs lie on unit circles that are 3-rich; such a family would likely require strong arithmetic structure producing many repeated unit distances.