A computer-assisted proof that the known nine-point Heilbronn configuration in the unit square is optimal
For Heilbronn's problem in the unit square, we give a computer-assisted proof that the largest possible minimum triangle area of nine points is H(9) = (9√65 − 55)/320 = 0.0548759991… . The value is attained only by the known configuration (Comellas and Yebra) and its images under the symmetries of the square. Optimality for n = 9 was previously established by global optimization software within numerical tolerances, not rigorously. The proof is a branch and bound over boxes of point positions, after exact symmetry and normalization reductions. Every discarded box is discarded by a test evaluated in exact integer or rational arithmetic; a floating-point LP solver only proposes dual multipliers, which are rounded and re-checked exactly. The boxes that survive are covered by an exact local certificate around the optimum. The run took 3.59·10^8 nodes and 16 hours on 14 worker processes, with no failures. A separately written checker accepted all 292,120 LP certificates of an n = 7 run and samples at n = 8 and 9. This is an AI-assisted, computer-assisted proof that has not been independently checked. Code, run logs and checksums are in the linked repository.
Authors
- Ethan Hendren
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-14
- DOI
- https://doi.org/10.5281/zenodo.24234316
- Primary Topic
- Computational Geometry and Mesh Generation
- Type
- preprint