GPT 6 Astra Ultra attempt on Math-678

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%.