Optimal packings of 15-20 equal circles in a circle

TL;DR

We prove that the classical packings of 15, 16, 17, 18 and 20 equal circles in a circle are optimal (previously, proofs were known only for up to 14 circles and for 19), and also characterize the optimal packings for 15, 16, 17 and 20. This resolves optimal radii for all $N \le 20$.

The proofs are computer-assisted (with exact rational arithmetic throughout), and were found by GPT-6 Astra with steering, checking and a lot of rewriting from my side.

Proof and other material can be found at this link.

Introduction

The problem is the following: given $N$, what is the smallest radius $R_N$ of a circle that can contain $N$ unit disks with disjoint interiors? Writing $b = R - 1$, this is equivalent to asking for the smallest $b$ such that there are points $x_1, \dots, x_N$ with $\|x_i\| \le b$ and $\|x_i - x_j\| \ge 2$ for all $i \ne j$ (we'll call such a set of points feasible for $b$).

The history of the problem is roughly as follows. Graham settled $N \le 7$ in 1968, and Pirl went up to $N \le 10$ in 1969 (Pirl also gave the fifteen-circle packing, which turns out to be optimal). Goldberg gave the sixteen- and twenty-circle packings in 1971, and Reis gave the seventeen-circle packing in 1975. After this, the proofs came much more slowly - Melissen proved the case $N = 11$ in 1994, Fodor proved $N = 19, 12, 13$ and $14$ between 1999 and 2003, and Ekanayake and LaFountain gave another proof for $N = 14$ in 2024. Note that numerical searches have produced very good candidate packings for much larger $N$, so the difficulty is entirely in proving that nothing better exists.

I first came across this problem more than a decade ago, back when geometry used to be my favorite math Olympiad subject, and it seemed both very elegant and very hard (at that point, there had been no progress for over a decade). Since LLMs have been resolving much bigger problems lately (see also my post on the unit distance problem, and more recently, the large number of results proved by LLMs), I gave this one to GPT-6 Astra. I gave it the case $N = 15$ first, and after it solved that, I asked it to try and generalize the approach to 16 and 17, which it did. I then did the same for 18 and 20. The proofs were, as usual, barely readable and very hard to understand (and surprisingly also had subtle issues).

My contributions were identifying the problem as feasible, motivating the model, battling the extremely buggy web UI, suffering through the horrible writing, fixing subtle issues, iterating over the exposition, verifying its work manually, and rechecking everything using both Astra and Opus 5.5. The approach seems generalizable, and there was no reason to stop at 20 other than it being a nice round number to stop at, so I expect more LLM-discovered proofs for higher $N$.

The rest of this post goes over the main ideas of the proof, and leaves out most of the details (which make the paper fairly long).

The results

The optimal radii are as follows:

For 15, 16 and 17, the optimal packing is unique (up to isometries and relabeling). The cases 18 and 20 are a bit different. For 18, the hexagon-and-dodecagon packing leaves enough room for one more disk at the center (so $R_{18} = R_{19}$), and if we remove one boundary disk from the nineteen-circle packing, a neighboring boundary disk can slide along an arc, which gives a continuous family of optimal packings that are not all congruent. We do not show that these are all the optimal packings for 18. For 20, the disk near the center doesn't touch anything, and the result determines the other nineteen disks exactly, along with the whole region where the twentieth one can be.

Outline of the proof

Fix $N$, and let $b = b_N$ be the radius of the known packing. Instead of showing directly that nothing fits in a smaller radius, we show that every feasible set for $b$ has a point with $\|x_i\| = b$. This is enough, since a feasible set for some $b' < b$ is also feasible for $b$, with all its points strictly inside. In most cases, the same argument also determines the feasible set completely, which gives uniqueness for free.

The proof for each $N$ consists of the same five steps, some of which are already present in the literature.

Projecting to the boundary

Moving a point outward can decrease its distance to some other point, but this doesn't happen for points that are already close to the boundary. More precisely, if $\|x\| \ge c(b) := b - 4/b$, moving $x$ radially to norm $b$ does not decrease any distance. This follows from $$D(b,s;\alpha) - D(r,s;\alpha) = (b-r)(b + r - 2s\cos\alpha),$$ where $D(r,s;\alpha) = r^2+s^2-2rs\cos\alpha$ is the squared distance between points at radii $r, s$ with angle $\alpha$ between them, since the original separation $D(r,s;\alpha) \ge 4$ and $r \ge c(b)$ make the second factor nonnegative. After projecting all such points, every point is either outer ($\|x\| = b$) or inner ($\|x\| < c(b)$).

The distance increases strictly if the point actually moves and the other point has norm less than $b$. So if an outer point touches an inner point after projection, the outer point must already have had norm $b$. An outer-outer contact similarly implies that at least one of its endpoints originally had norm $b$. These contacts let us recover an original boundary point and hence prove the lower bound.

Counting using angles

Two outer points must be at an angle of at least $2\eta$ from each other, where $\eta = \arcsin(1/b)$, and an inner point at radius $r$ must be at an angle of at least $h_b( r)$ from every outer point (where $h_b( r)$ comes from the cosine rule). If we assign each outer point an arc of half-width $\eta$ and each inner point an arc of half-width $\max(h_b( r) - \eta, 0)$, these arcs have disjoint interiors, so $$m\,\eta + \sum_{\text{inner } i} \max\big(h_b(r_i) - \eta,\ 0\big) \le \pi ,$$ where $m$ is the number of outer points. Together with an upper bound on the number $k$ of inner points, this gives finitely many possible pairs $(m,k)$. A preliminary certified search uses the angular inequality to exclude most of them, leaving between one and three pairs for each $N$. As an aside, for $N = 15$ this inequality is tight at the optimal packing.

A finite search over radii and cyclic orders

Searching over positions directly is not feasible (there are $2N$ real parameters), so the search only keeps track of an interval for the radius of each inner point, and the cyclic order of the points (i.e., the number of outer points between consecutive inner points). Every test is a necessary condition that has to hold for some choice of directions:

• two separated points satisfy $r_i + r_j \ge 2$;
• two separated points with given radii must be at some minimum angle from each other, and over a box of radii, it suffices to check this at the four corners;
• combining these pairwise lower bounds on differences of directions around the circle (via a longest-path computation, i.e., Floyd-Warshall), if some cycle requires more than $2\pi$, the box is excluded.

If a box is excluded, we discard it. If its whole radial box and cyclic order satisfy one of the prescribed target conditions (a specific cyclic order together with small intervals around the radii of a known configuration), we retain it without further subdivision. Otherwise, one of its intervals is split into two, and we recurse. A completed calculation therefore either excludes a case completely or puts every feasible configuration into one of the target neighborhoods. Depending on $N$, a target describes the whole packing or a specified subset of its points.

The largest computation (17 circles, 10 of them on the boundary) looks at roughly 15 million boxes. All arithmetic is exact rational arithmetic, and floating point is only used to propose angle tables and approximate matrix inverses, which are then checked exactly before being used. The full verification takes about eight minutes, which is not a lot.

From approximate to exact

The search only shows that the radii lie in small intervals and that the cyclic order is fixed. Together with the angle bounds from the longest-path computation, this puts every point within a small distance of a known packing after a rotation, but no finite search can do better than that. The next step is thus a quantitative rigidity argument. Let's get rid of the common rotational freedom first, and let $U$ be the size ($\ell_\infty$ norm) of the displacement from the known packing, and linearize each contact. Feasibility gives that each linearized contact term $y_a$ is at least $-8U^2$. Now suppose there are weights $w_a > \sigma_* > 0$ summing to $1$ such that $\sum_a w_a y_a = 0$ for every displacement (this is a positive equilibrium stress). Then each $y_a$ is also at most $8U^2/\sigma_*$, and if we also have $U \le \kappa \max_a |y_a|$, we get $$U \le \frac{8\kappa}{\sigma_*}\,U^2,$$ so $U = 0$ whenever $U < \sigma_*/(8\kappa)$. The constants $\sigma_*$ and $\kappa$ come from an approximate inverse of the rigidity matrix (with an extra column of ones and optionally some additional rational columns to make it square), with the approximation error bounded exactly, and in every case the bound from the search is below $\sigma_*/(8\kappa)$.

For $N = 15$, the last step is different and doesn't need any matrices. Write the five inner radii as $r_i = a(1+\xi_i)$, where $a$ is the radius of the pentagon. The angle between consecutive inner points has two lower bounds, whose first-order terms are $-\chi(\xi_i + \xi_{i+1})$ and $t(\xi_i + \xi_{i+1})$ for some positive constants $\chi < t$, so the larger of the two exceeds $2\pi/5$ by roughly $\chi|\xi_i + \xi_{i+1}|$. On a cycle of length $5$, we have $\sum_i |\xi_i + \xi_{i+1}| \ge \tfrac25 \sum_i |\xi_i|$ (on an even cycle this fails, since alternating signs make every $\xi_i + \xi_{i+1}$ zero). Since the angles add up to $2\pi$, and perturbations from the search are small, the first-order terms have to be bounded by the second-order terms, which can only happen when all the $\xi_i$ are zero.

Undoing the projection

Once the projected set is known exactly, the contact property from the first step shows that some original point had norm $b$, and in most cases recovers the whole original set.

Differences between the cases

• 15: the odd-cycle argument above replaces the rigidity step.
• 16: everything goes through as described above.
• 17: two inner points of Reis's packing lie on the same ray from the center, so the search has to allow both orders of these two points.
• 18: if there are twelve outer points, their angular gaps must all equal $\pi/6$. Their contacts already force an original boundary point. For ten or eleven outer points, the search leaves six reference configurations, whose coordinates lie in $\mathbb{Q}(\sqrt2,\sqrt3)$. Five references have a point at radius exactly $c(b)$ matched to an inner point, and rigidity forces equality at these reference points and contradicts the strict inner bound. The sixth pins down seventeen of the points (which already gives an original boundary point), and the vacant arc it leaves leads to the family above.
• 20: because of the free disk, a feasible set doesn't have to be close to the known packing as a whole. So the search matches 19 of the 20 points instead (trying each inner point as the one left out), and the rigidity step is applied to those 19.

On correctness and verification

This is a computer-assisted proof, and I've verified the arguments (and the computations) manually as well as using LLMs (GPT-6 Astra and Claude Opus 5.5). Long proofs like this can always have subtle errors, so if you find a mistake, please let me know.

Acknowledgements

Thanks to GPT-6 Astra for finding the proofs, and to Opus 5.5 for also helping write this post.

References

• Bateman, P. and Erdős, P. "Geometrical extrema suggested by a lemma of Besicovitch". American Mathematical Monthly 58, 1951.
• Connelly, R. and Whiteley, W. "Second-order rigidity and prestress stability for tensegrity frameworks". SIAM Journal on Discrete Mathematics 9, 1996.
• Ekanayake, D. B. and LaFountain, D. J. "Tight partitions for packing circles in a circle". Italian Journal of Pure and Applied Mathematics 51, 2024.
• Fodor, F. "The densest packing of 19 congruent circles in a circle". Geometriae Dedicata 74, 1999.
• Fodor, F. "The densest packing of 12 congruent circles in a circle". Beiträge zur Algebra und Geometrie 41, 2000.
• Fodor, F. "The densest packing of 13 congruent circles in a circle". Beiträge zur Algebra und Geometrie 44, 2003.
• Fodor, F. "Packing of 14 congruent circles in a circle". Studies of the University of Žilina, Mathematical Series 16, 2003.
• Goldberg, M. "Packing of 14, 16, 17 and 20 circles in a circle". Mathematics Magazine 44, 1971.
• Graham, R. L. "Sets of points with given minimum separation (solution to Problem E1921)". American Mathematical Monthly 75, 1968.
• Graham, R. L., Lubachevsky, B. D., Nurmela, K. J. and Östergård, P. R. J. "Dense packings of congruent circles in a circle". Discrete Mathematics 181, 1998.
• Melissen, H. "Densest packings of eleven congruent circles in a circle". Geometriae Dedicata 50, 1994.
• Pirl, U. "Der Mindestabstand von n in der Einheitskreisscheibe gelegenen Punkten". Mathematische Nachrichten 40, 1969.
• Reis, G. E. "Dense packing of equal circles within a circle". Mathematics Magazine 48, 1975.

@online{circle-in-circle-packing-15-20,
  author    = {nor},
  title     = {Optimal packings of 15-20 equal circles in a circle},
  year      = {2026},
  month     = {10},
  day       = {11},
  url       = {https://nor-blog.pages.dev/posts/2026-10-11-circle-in-circle-packing-15-20/},
}