Squares in circles

Two certified packings improve the records listed on Erich Friedman’s Squares in Circles page, checked on September 11, 2026. Every square has side length exactly 1.

These are rigorously feasible record improvements. Global optimality has not been proved.

The comparison uses the printed decimal prefixes, so omitted digits in the published radii can only increase these improvements.

The 31-square search started from a reconstruction of Haowei Lin’s July 2026 diagram, then improved through population search and removal/reinsertion. The 34-square search deleted a square from David Eppstein’s 35-square layout and then optimized the remaining squares; its comparison record is Jonathan Viquerat’s August 2026 result.

Coordinates and drawings

Each coordinate file stores the circle radius and each square’s center (x, y) and rational half-angle tangent t as exact decimal strings. The rotation is

c = (1 - t²) / (1 + t²)
s = 2t / (1 + t²)
vertices = (x + a*c - b*s, y + a*s + b*c), a,b ∈ {−1/2,+1/2}

Because c²+s²=1 exactly, the squares have exact unit sides. The certificate deliberately leaves small positive clearance after rounding the numerical search result.

Independent verification

Run with the Python standard library alone:

python3 verify_records.py

The verifier recomputes geometry from the coordinate strings. It checks exact unit edge lengths and right angles, all 260 corners for circle containment, all 1,026 pairs for separation, and strict improvement over both listed radii. All acceptance comparisons use rational arithmetic; floating-point numbers are used only to display the resulting positive margins. Convexity of the circle makes corner containment sufficient for every point of a square. Separating axes from the two squares’ edges establish disjoint interiors.

Search and reproduction

uv sync
uv run pytest -q
OPENBLAS_NUM_THREADS=1 uv run python reconstruct.py
OPENBLAS_NUM_THREADS=1 uv run python packing.py 31 --seed 1 --iterations 80
OPENBLAS_NUM_THREADS=1 uv run python vacancies.py 34 --workers 4

packing.py implements square separating-axis constraints and analytic derivatives, SLSQP local minimization, and repeated perturbation with penalty relaxation. grouped.py improves numerical conditioning by tying nearly aligned orientations. vacancies.py explores layouts obtained by deleting a square from a larger packing. Seeds, intermediate candidates, and search logs are saved in references/ and results/.

insertions.py adds squares to smaller layouts or removes and replaces 1–3 squares after allowing the remaining squares to rearrange. Replay the latest successful 31-square trial from its saved parent and seed:

OPENBLAS_NUM_THREADS=1 uv run python insertions.py --replay results/n31_repair70.json

See EXPERIMENTS.md for additional searches and their limitations.

For optional GPU batch searches, install the gpu extra. The search waits while other compute processes are present, yields between short chunks, and retries out-of-memory failures with smaller batches.

uv sync --extra gpu
OPENBLAS_NUM_THREADS=1 uv run --extra gpu python gpu_search.py 31 --seed 96

GPU proposals are refined on the CPU. Only the exact-rational verifier establishes feasibility. GPU memory preallocation is disabled by default.

To certify another numerical candidate:

uv run python certify.py results/n31_grouped.json --output results/example_certificate.json --plot
python3 certify.py results/example_certificate.json

The exact certificates are the authoritative deliverables. Raw optimizer files may have tiny numerical overlaps and are not feasibility proofs. The saved benchmark page is references/records.html.