Tammes problem, maximum minimum distance on the sphere

# Tammes problem, maximum minimum distance on the sphere ## 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 smallest pairwise Euclidean distance D = min over i < j of |x_i - x_j| Equivalently: pack `n` equal spherical caps as large as possible, or find the best spherical code of size `n`. This is Problem 34 in DeepMind's AlphaEvolve repository of problems (Section 6.18 of "Mathematical Exploration and Discovery at Scale", arXiv:2511.02864). AlphaEvolve matched the records for n = 3, 7, 12 and 25 and fell slightly short at n = 32, 50, 100 and 200 (Table 5 of the paper), so the larger n here are where a good pure-Python search can still make a difference. Optimality is proven only for n <= 14 and n = 24; every n in this benchmark is open. ## Metric metric = mean over n in NS of D(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 points simply score 0 for that n) and recomputes the minimum distance itself. 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 configurations from N. J. A. Sloane, R. H. Hardin, W. D. Smith et al., "Tables of Spherical Codes" (NeilSloane.com/packings/, files `dim3/pack.3.<n>.txt`, fetched 2026-09-07). The record distance below was recomputed from those coordinates; each matches the table's angular separation to its full 1e-7 degree precision. A distance above a record by more than 1e-8 is listed in `records_beaten`. | n | record D | angle (deg) | source | proven optimal | |---|---|---|---|---| | 15 | 0.902656188015 | 53.6578501 | Hardin, Sloane, Smith 1994 | no | | 17 | 0.862444879257 | 51.0903285 | Hardin, Sloane, Smith 1994 | no | | 19 | 0.808558114565 | 47.6919141 | Hardin, Sloane, Smith 1994 | no | | 21 | 0.775243921143 | 45.6132231 | Kottwitz, Acta Cryst. A47 (1991) | no | | 25 | 0.710776154955 | 41.6344612 | Hardin, Sloane, Smith 1994 | no | | 27 | 0.695141408884 | 40.6776007 | Kottwitz, Acta Cryst. A47 (1991) | no | | 32 | 0.642469275564 | 37.4752140 | Hardin, Sloane, Smith 1994 | no | | 33 | 0.622257802439 | 36.2545530 | Kottwitz, Acta Cryst. A47 (1991) | no | | 50 | 0.513472084621 | 29.7529564 | Hardin, Sloane, Smith 1994 | no | | 54 | 0.495975188171 | 28.7169205 | Kottwitz, Acta Cryst. A47 (1991) | no | | 64 | 0.453898297814 | 26.2350433 | Hardin, Sloane, Smith 1994 | no | | 100 | 0.365006496096 | 21.0312020 | 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=15,25` 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 objective is a max-min, so plain gradient methods stall. Standard tricks: minimise a soft energy sum d^-p with p ramped up (the baseline), or iterate "find the active contact pairs, then solve the LP that pushes them apart" (an SLP), which converges to the true local optimum. - The record configurations have very specific contact graphs (Kottwitz's improvements at n = 21, 27, 33, 54 came from symmetric constructions). Search over starting symmetries, not just random starts, and finish each candidate with a contact-graph polish. - Basin hopping: perturb the current best a little, re-optimise, accept if the minimum distance did not drop. Many restarts beat one long run. - The pure-Python pair loop is the bottleneck: only the near-contact pairs matter once the configuration is decent, so keep a neighbour list and refresh it occasionally. 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.