Points on a sphere, maximum convex-hull volume

# Points on a sphere, maximum convex-hull volume ## Goal `sphere.py` exposes `place(n: int, time_budget: float, seed: int) -> list[tuple[float, float, float]]`: `n` points `(x, y, z)` on the unit sphere. Maximise the volume of their convex hull, i.e. find the largest polyhedron with `n` vertices inscribed in the unit sphere (Fejes Toth's 1964 problem). This is Problem 41 in DeepMind's AlphaEvolve repository of problems (Section 6.24 of "Mathematical Exploration and Discovery at Scale", arXiv:2511.02864). AlphaEvolve matched the first ~60 entries of Sloane's table to all 13 printed digits and improved none of them. Optimality is proven only for n <= 8 (Berman and Hanes 1970); Mutoh (2003) found numerical candidates for n <= 30 and Sloane's table extends to n = 130. Every n in this benchmark is open. ## Metric metric = mean over n in NS of V(n) / record(n) 1.0 means matching every record; above 1.0 means beating at least one. The eval projects every returned point onto the unit sphere (any finite non-zero vector is accepted; a zero vector, a non-finite coordinate or the wrong count is a failed run; coincident or coplanar points just lose volume) and computes the hull volume itself with an incremental convex hull, summing the origin tetrahedra over the hull's faces. Nothing your solver reports is used. `ZT_EVAL_SEED` only changes the `seed` handed to `place`, so your method must be robust to its starting point. ## Records Best-known volumes from R. H. Hardin, N. J. A. Sloane and W. D. Smith, "Maximal Volume Spherical Codes" (NeilSloane.com/maxvolumes/, 1994; fetched 2026-09-07), exactly as printed there. The eval's hull code reproduces each from the site's coordinate files (`dim3/maxvol.3.<n>.txt`) to 5e-13. A volume above a record by more than 1e-9 is listed in `records_beaten`. | n | record volume | source | proven optimal | |---|---|---|---| | 9 | 2.043750115900 | Hardin, Sloane, Smith 1994 | no | | 10 | 2.218711131545 | Hardin, Sloane, Smith 1994 | no | | 11 | 2.354634495069 | Hardin, Sloane, Smith 1994 | no | | 13 | 2.612834152060 | Hardin, Sloane, Smith 1994 | no | | 14 | 2.720977899349 | Hardin, Sloane, Smith 1994 | no | | 16 | 2.886455392275 | Hardin, Sloane, Smith 1994 | no | | 18 | 3.009613252523 | Hardin, Sloane, Smith 1994 | no | | 20 | 3.118538793195 | Hardin, Sloane, Smith 1994 | no | | 24 | 3.283995205283 | Hardin, Sloane, Smith 1994 | no | | 30 | 3.455125752062 | Hardin, Sloane, Smith 1994 | no | | 40 | 3.634130342837 | Hardin, Sloane, Smith 1994 | no | | 50 | 3.740940879707 | Hardin, Sloane, Smith 1994 | no | ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The eval fails a call that runs past 1.25x + 3 s. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_NS=9,13` runs a subset of n; `ZT_EVAL_PER_N_SECONDS=2` shortens the per-n budget. The default is all twelve n at 8 s each (about 100 s). Run `python eval.py` in your workspace. - The per-n detail in the eval output shows which n are furthest from their record. ## Ideas that are known to matter (check the journal before repeating one) - The volume has a clean gradient: for a triangulated hull, the derivative of the volume with respect to vertex `v` is one sixth of the sum of the cross products of the two other vertices over the faces containing `v` (the "area vector" of its link). Build the hull once per step (the eval's incremental hull is a template you may copy), project the gradient onto the tangent plane, and ascend. The baseline only does Coulomb repulsion, which is not the same objective. - Berman and Hanes' necessary condition: at an optimum every vertex is the normalised sum of the area vectors of its incident faces, and all faces are triangles. Use it as a stopping test and a polish step. - The optimal polyhedra are "medial" (vertex degrees 5 and 6 only, like Thomson minima but not the same configurations). Start from a good Thomson or Tammes configuration and ascend the volume. - Basin hopping over the combinatorial type: small perturbations that flip an edge, then re-ascend. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.