Nine points in the unit-circle problem

The problem

Given a finite set P of n points in the Euclidean plane, count the distinct unit circles that contain at least three points of P. Let a(n) be the maximum possible count.

The classical table begins a(3),…,a(8)=1,4,4,8,12,16. The construction below attains 20 for n=9. The upper-bound certificate proves that 21, 22, and 23 cannot occur; the elementary bound already rules out every larger number. The two halves meet at 20.

Smaller cases, before nine

The first six known values help explain what is being counted. For n=3,4,5,6 the panels are drawn from explicit coordinate constructions. For n=7, the panel replots the exact coordinates displayed in the OEIS/Martin Fuller illustration. For n=8, the value is 16; we could not find a publicly available coordinate source or illustration for that construction, so the panel below shows the exact reconstruction we obtained.

n=3, a(3)=1

An equilateral triple on a unit circle gives the only possible counted circle.

n=4, a(4)=4

The centre of an equilateral triangle plus the three vertices gives four unit circles.

n=5, a(5)=4

The fifth point can be placed generically, without creating any new counted unit circle.

n=6, a(6)=8

A pair-sum construction from four unit vectors realizes the classical value eight.

n=7, a(7)=12

Exact coordinate construction from the OEIS/Martin Fuller illustration; exactness is Harborth–Mengersen.

n=8, a(8)=16

Our reconstruction keeps the Harborth base points (-2/3,0), (0,0), and (2/3,0), then splits the old tangent four-point circle into two counted triples.

The twenty-circle construction

The certified nine-point pattern is all-triple: every counted circle contains exactly three of the nine points. The twenty intended triples are

Partition the labels as A={0,1,2}, B={3,4,5}, and C={6,7,8}. The pattern consists of the two internal triples 012 and 345, together with all cross triples from A×B×C except the nine triples whose three within-block indices sum to 0 mod 3. This places the construction in the all-triple 20T,s=6 deficiency layer.

Circle 01: triple 012

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20

The buttons switch between the twenty certified unit circles. The inactive circles are left faintly visible to keep the full arrangement in view.

Approximate coordinates

These decimals are for orientation only. The exact construction is not defined by these decimals; it is defined by a rational polynomial system and a rational interval certificate.

Why the answer cannot be larger

The proof that a(9)≤20 has a simple outer shell and an exact finite core. The outer shell says that a nine-point configuration cannot have more than 23 counted unit circles. The finite core then eliminates 23, 22, and 21.

The pair-slot bound

Let C be a counted circle, and let s(C) be the number of selected points on it. A circle with s(C) selected points uses binom(s(C),2) unordered point-pairs. A fixed pair of points can lie on at most two unit circles: geometrically, the two possible centers are the two intersections of the unit circles centered at the two points. Therefore

For n=9, the right-hand side is 2·binom(9,2)=72. Since every counted circle has at least three points, every counted circle uses at least three pair-slots. The raw estimate gives m≤24.

The one-slot improvement

Pinchasi’s Gallai–Sylvester theorem for pairwise-intersecting unit circles improves this by one pair-slot for every n≥5:

For n=9 this gives a(9)≤floor((72−1)/3)=23. Hence no number above 23 needs a separate certificate. To prove a(9)≤20, it remains only to rule out m=23, m=22, and m=21.

The finite-certificate machinery

The upper-bound certificate does not search over coordinates. It searches over finite incidence templates, and only then applies exact algebraic tests to decide whether a surviving template could possibly be realized by points and unit circles in the plane.

1. Hypergraphs and pair deficiencies

For an all-triple profile, write codeg(i,j) for the number of intended triples containing pair ij, and define

The number δij is the unused capacity of pair ij. Since there are 72 possible pair-slots on nine points and each triple uses three slots,

At every vertex i, the weighted deficiency degree is even:

Mixed profiles use the same accounting, but a four-point circle Q uses all six internal pairs of its four support points, and a five-point circle R5 uses all ten internal pairs of its five support points.

2. Local caps

Every subset S of the nine labels must induce no more circles than are possible on |S| points. Thus every induced subtemplate of size 3,4,5,6,7,8 is capped by 1,4,4,8,12,16. This matters because many formal pair-capacity patterns already contain, for example, too many circles on seven of the labels.

3. Four-point closure

If four points A,B,C,D have unit circles through three of the four triples, then the fourth triple also lies on a unit circle. A quick proof: translate A to the origin. Let the centers of ABC, ABD, and ACD be x,y,z. Reflection across the midpoints gives B=x+y, C=x+z, and D=y+z. Then B,C,D lie on the unit circle centered at x+y+z.

4. Reflection equations

Suppose two counted unit circles B and B′ share the point-pair i,j. Their centers are the two unit-circle centers through that same pair, so they are mirror images across the midpoint of pipj. Therefore

These are linear equations, one scalar coordinate at a time. Constants always form a one-dimensional solution space; a non-collinear planar realization needs scalar solution-space dimension at least three and must not force any original point labels to coincide.

5. Affine Gram forms and rank two

After quotienting by constants, the remaining scalar solution space is an affine coordinate skeleton. A Euclidean planar realization is equivalent to a positive semidefinite Gram form G of rank at most two. For each intended incidence pi∈B, the unit-radius condition becomes a linear equation in the entries of G:

If the linear Gram system is inconsistent, the incidence template cannot be geometric. If it leaves a family, the certificate imposes rank at most two by exact 3×3 minor equations. Terminal branches are then eliminated by exact ideal infeasibility, point collisions, or forced extra incidences.

6. Forced extra incidences

For an all-triple profile, a template is supposed to contain only triple-circles. If the algebra proves that some outside point v∉B must satisfy

on every Gram solution, then the alleged triple-circle actually has a fourth point. That template is discarded from the all-triple case. This is how the last residual m=21 orbits disappear.

Consequently, any nine-point configuration with at least 21 counted unit circles would have to appear in this finite search, but every possible incidence template is certified impossible. Therefore a(9)≤20.

The lower certificate: exactly twenty

The construction must also be certified as a real Euclidean configuration with no hidden extra counted circles. The lower certificate does this with exact rational interval arithmetic.

Polynomial system

The reflection equations reduce the twenty centers and nine points to a rational linear parametrization. With variables

the certificate stores a rational matrix whose first nine rows define the points and whose next twenty rows define the intended centers. The sixty intended point-center incidences reduce, up to sign, to fifteen rational displacement rows r1,…,r15. The fifteen unit equations are

Five gauge equations remove translation, rotation, and scale choices: Z0x=0, Z0y=0, Z1y=0, Z7x=1/8, and Z8y=−1/2. Altogether this is a square system of twenty rational polynomial equations in twenty real variables.

Krawczyk root isolation

Let F:R20→R20 be this polynomial map. The certificate stores a rational center c, a rational approximate inverse C, and the interval box

Using exact rational interval arithmetic, the verifier evaluates

and proves K(c,X) lies strictly inside the interior of X. It also proves the contraction bound

Therefore the polynomial system has a unique real zero in the box. This supplies the real points and centers used by the construction.

What is certified after the root exists

The polynomial used for the last row is

For a non-collinear triple, Φijk=0 is equivalent to circumradius one. There are binom(9,3)=84 triples in total. Twenty are listed. The remaining 64 are all interval-excluded. Hence the construction has exactly twenty counted unit circles, not merely at least twenty.

How the construction was found

The twenty-circle configuration was found through the same incidence-template search that powers the upper-bound certificate, not by tuning the visible drawing.

The project first had a certified nine-point construction with nineteen counted circles. The upper-bound search then narrowed the remaining possible twenty-circle cases. The successful candidate appeared in the all-triple 20T,s=6 deficiency layer.

The candidate note’s high-precision recount found exactly twenty distinct unit circles across all binom(9,3)=84 triples, with no near-collisions and no near-extra circle. At that stage it was still only a numerical discovery. The final proof is the interval certificate above: it isolates a real root and proves the non-listed triples stay away from unit circumradius.

Two immediate extensions

The nine-point construction also gives lower bounds for the next two values. If A,B,C lie on a unit circle centered at Q, put

Then ABD, ACD, and BCD lie on unit circles with centers A+B−Q, A+C−Q, and B+C−Q. Completing the certified 012 circle gives a(10)≥23. Completing both 012 and 345 gives a(11)≥26.

Selected further bounds

The manuscript also records certified lower bounds from exact square- and triangular-lattice checks, together with the general Pinchasi upper bound used here.

References and sources

1. N. J. A. Sloane, OEIS A003829, “Maximal number of unit circles through n points in plane, each circle containing 3 of the points.” Includes the sequence 1,4,4,8,12,16, the small-value table, and the Martin Fuller illustration link.
2. OEIS, Martin Fuller illustration of a(3) through a(7). Used for the exact coordinate panel shown here for n=7.
3. Heiko Harborth and Ingrid Mengersen, “Point sets with many unit circles,” Discrete Mathematics 60 (1986), 193–197. This is the cited source for the exact small values through n=7.
4. H. T. Croft, K. J. Falconer, and R. K. Guy, Unsolved Problems in Geometry, Springer, 1991, Problem F9. This records the classical small table including f(8)=16 and asks for the next values.
5. R. Pinchasi, “The Gallai–Sylvester theorem for pairwise-intersecting unit circles,” Discrete & Computational Geometry 28 (2002), 607–624. Used for the one-slot improvement a(n)≤floor((n(n−1)−1)/3).
6. P. Erdős and G. Purdy, “Extremal problems in combinatorial geometry,” in Handbook of Combinatorics, North-Holland, 1995.
7. G. Elekes, “N-point configurations with many unit circles,” manuscript / example cited in the Erdős problem literature.
8. Thomas Bloom, Erdős Problems, Problem 104, current online formulation of the asymptotic unit-circle problem.