Experiment · Geometry

Friedman Packing Center: exact, certified circle packings

This experiment addresses two pages of Erich Friedman’s Packing Center, which list, for each number n of circles, the packing with the largest known sum of radii, in a rectangle of perimeter 4 and in a circle of radius 1. Outcome: 16 of the 20 entries of the “rectangle” page for n from 31 to 50, and the n = 50 entry of the “circle” page, are credited to the experiment. Each packing is exact, comes with a certificate in rational arithmetic that anyone can recheck.

1. The question

For a number n of circles, what is the largest sum of radii that can be reached by placing them, without overlap, in a fixed container? Radii are free. The two containers of the experiment are the disc of radius 1 and the rectangle of perimeter 4: the sides W and H satisfy W + H = 2, and the shape of the rectangle is free too. No formula gives the answer, apart from a few small cases.

2. Protocol and reference page

Erich Friedman keeps the pages of his Packing Center: for each n, a picture of the packing, the value of Σ r truncated to five decimals (the “+” sign marks a lower bound), the author’s name and the month. Each result is a packing whose coordinates are checked in exact rational arithmetic by a program of a few lines (section 5).

3. Results

When read on 1 October 2026, the “rectangle” page stopped at n = 30 and the “circle” page showed 6.53814+ for n = 50. When read on 11 October 2026, the “rectangle” page has 50 entries and the “circle” page shows 6.53881+ for n = 50. The table gives, for n from 31 to 50, the exact sum of radii of the submitted packing, the value shown on the page and the credit it carries.

For the 16 entries credited to the experiment, the value shown on the page is the exact sum truncated to five decimals. For n = 50 in the circle, the submitted packing has exact sum 6.538814832; the page’s previous value was 6.53814+.

The packings, drawn from the exact coordinates: the centre and radius of every circle. Colour follows the radius, from violet (small) to cyan (large). The circles of the animated figure appear from left to right: this is a display sweep. The data behind each figure can be downloaded as JSON.

The 20 rectangles for n = 31 to 50 are drawn at the same scale. The rectangle is free: its width W is a parameter of the packing, with W + H = 2.

4. Theorem and certificate

The certificate is the exact check of the n lines of a file. It uses neither square roots nor tolerance: the decimal values are read as rational numbers, and every comparison is made on those rationals.

Statement of validity

Proposition. Let (x_i, y_i, r_i), i = 1…n, be rational numbers with r_i > 0, and let the container C be either the rectangle [0, W] × [0, H] (W rational, 0 < W < 2, H = 2 − W) or the closed disc of radius 1 centred at the origin. If

1. for the rectangle: r_i ≤ x_i ≤ W − r_i and r_i ≤ y_i ≤ H − r_i; for the disc: r_i < 1 and x_i² + y_i² ≤ (1 − r_i)²;
2. for every i < j: (x_i − x_j)² + (y_i − y_j)² ≥ (r_i + r_j)²;

then (a) each closed disc D_i with centre (x_i, y_i) and radius r_i lies inside C; (b) the interiors of two distinct discs are disjoint; (c) the sum of the radii is exactly Σ r_i, a rational number computed without rounding.

Proof

(a) Rectangle: if (X, Y) belongs to D_i, then |X − x_i| ≤ r_i, so X ∈ [x_i − r_i, x_i + r_i] ⊂ [0, W]; likewise for Y. Disc: if P belongs to D_i, then |P| ≤ |c_i| + r_i ≤ (1 − r_i) + r_i = 1, where |c_i| ≤ 1 − r_i comes from condition 1 by taking square roots, 1 − r_i being positive.

(b) If a point P lay in the interior of both D_i and D_j, the triangle inequality would give |c_i − c_j| < r_i + r_j, hence |c_i − c_j|² < (r_i + r_j)², contradicting condition 2.

(c) It is a finite sum of rationals.

What the certificate guarantees

• that the n circles fit inside the container, with no excess, however small;
• that no pair of circles overlaps: at most, two circles touch;
• the exact value of the sum of radii of the submitted file;
• that exactly n circles are present.

A proven bound, and the ratio of each entry

An upper bound gives a fixed ruler, independent of the other entries on the page.

Proposition. For every packing of n pairwise disjoint circles: (i) in a rectangle of perimeter 4, Σ r_i ≤ √(n/π); (ii) in the disc of radius 1, Σ r_i ≤ √n.

Proof. (i) The discs are disjoint and contained in the rectangle, whose area WH is at most 1 since W + H = 2 (WH ≤ ((W + H)/2)² = 1). So Σ π r_i² ≤ 1. By Cauchy–Schwarz on (r₁, …, r_n) and (1, …, 1), (Σ r_i)² ≤ n · Σ r_i² ≤ n/π. (ii) Same argument with the disc’s area π: Σ π r_i² ≤ π, so (Σ r_i)² ≤ n · Σ r_i² ≤ n. ∎

This bound is elementary: it takes a few lines (area and Cauchy–Schwarz) and serves here as a yardstick.

The bound check (distinct from the validity certificate) verifies π·(Σ r)² ≤ n for the rectangle and (Σ r)² ≤ n for the disc, in exact rational arithmetic (π is bracketed by two rationals with 30 decimals, and its upper bound is the one used in the test). On 11 Oct 2026, it declares all 20 rectangle packings and the circle packing compliant. The 16 rectangle entries credited to the experiment reach 92.2 % (n = 32) to 92.7 % (n = 49) of the bound; for the circle n = 50, 92.5 %. This ratio does not change when a value on the page is beaten.

5. Recheck it yourself

Download the JSON file of one packing, then run this short Python program (standard library only). It reads the coordinates as exact rationals, tests conditions 1 and 2 for every pair (n(n − 1)/2 pairs, that is 1,225 for n = 50) and prints the outcome. For the circle, only the containment condition changes:

import json
from fractions import Fraction as F

d = json.load(open("friedman_rect_50.json"))
W = F(d["W"]); H = 2 - W                              # rectangle [0, W] x [0, H], périmètre 2(W + H) = 4
P = [tuple(F(v) for v in c) for c in d["circles"]]     # (x, y, r) en rationnels exacts
dedans = all(r > 0 and r <= x and x + r <= W and r <= y and y + r <= H for x, y, r in P)
disjoints = all((a[0]-b[0])**2 + (a[1]-b[1])**2 >= (a[2]+b[2])**2
                for i, a in enumerate(P) for b in P[i+1:])
print(len(P), dedans and disjoints, float(sum(r for _, _, r in P)))

d = json.load(open("friedman_cercle_50.json"))
P = [tuple(F(v) for v in c) for c in d["circles"]]
dedans = all(0 < r < 1 and x*x + y*y <= (1 - r)**2 for x, y, r in P)     # le disque est dans le disque unité
# (la condition de disjonction est la même que ci-dessus)

Expected output for the rectangle n = 50: 50 True 3.6953181299845124. The JSON files also hold the sha256 fingerprint of the submitted file.

6. The map of the challenge

The 50 entries of each of the two pages, in rows of 25 (n = 1 to 25, then 26 to 50). Cyan: credited to the experiment; gold: credited to another contributor for n from 31 to 50 on the “rectangle” page; pale violet: the other entries. Pages read on 11 October 2026.

7. What this question models

This type of question models placement problems that arise in cutting and packaging (laying round parts of different sizes in a sheet or a box), placing sensors or antennas with circular coverage, and studying granular materials. Friedman's pages are a common reference for comparing packings; those shown here are exact, certified and rechecked by anyone.

My AI project in the service of my research

This challenge is not an end in itself: it is a test bench for my research on a certifiable embedded AI. My AI project, whose inner workings remain confidential, lets me reach 16 of the 20 rectangle entries and the circle entry, each rechecked in exact arithmetic. The certificate and the referee vouch for it: it is not my explanation you need to believe, it is the result, which can be checked again. This is the best known result at the date given, not a proven optimum.