Thomson problem, minimum Coulomb energy on the sphere

# Thomson problem, minimum Coulomb energy 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. Minimise the Coulomb energy E = sum over i < j of 1 / |x_i - x_j| This is Problem 33 in DeepMind's AlphaEvolve repository of problems (Section 6.18 of "Mathematical Exploration and Discovery at Scale", arXiv:2511.02864). AlphaEvolve ran it for n up to 300 and matched the state of the art to about 1e-8 (its constructions for n = 282, 292, 306 reproduce the Cambridge Cluster Database energies) without improving any of them. The exact minimum is known only for n = 2, 3, 4, 5, 6 and 12; every n in this benchmark is open. ## Metric metric = mean over n in NS of record(n) / E(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, the wrong count, or two coincident points is a failed run) and recomputes the energy 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 energies from the Cambridge Cluster Database table "Global Minima for the Thomson Problem" (D. J. Wales and S. Ulker, Phys. Rev. B 74, 212101 (2006), with updates from Wayne Deeter; https://www-wales.ch.cam.ac.uk/~wales/CCD/Thomson/table.html, fetched 2026-09-07), exactly as printed there. An energy below a record by more than 1e-6 is listed in `records_beaten`. | n | record E | point group | proven optimal | |---|---|---|---| | 16 | 92.9116553 | T | no | | 37 | 560.6188877 | D5h | no | | 38 | 593.0385035 | D6d | no | | 42 | 732.0781075 | D5h | no | | 47 | 927.0592706 | Cs | no | | 54 | 1239.3614747 | C2 | no | | 59 | 1490.7733352 | C2 | no | | 64 | 1765.8025779 | D2 | no | | 77 | 2591.8501523 | D5 | no | | 88 | 3416.7201967 | D2 | no | | 100 | 4448.3506343 | T | no | | 122 | 6698.3744992 | Ih | no | The n were chosen so that a single gradient descent from a Fibonacci spiral (the baseline) ends in the wrong basin on most of them; a Thomson n that plain descent solves gives no signal. ## 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=16,47` 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 energy landscape has exponentially many local minima; a single gradient descent from a Fibonacci spiral gets stuck a few 1e-4 above the record. Basin hopping (perturb, re-minimise, accept if better) is what found most of the database entries. - Good minima are near-triangular lattices with exactly twelve 5-fold defects. The n = 122 record has icosahedral symmetry, n = 37 and 42 are D5h, n = 16 and 100 are T. Symmetry-constrained starts converge faster than random ones. - Second-order convergence: after gradient descent, a few Newton or conjugate-gradient steps on the tangent space reach the minimum to 1e-10. The ratio only rounds to 1.0 once you are within about 1e-7 relative, so finishing matters. - The pure-Python pair loop is the bottleneck: cache differences, avoid function-call overhead, and reuse the force computation as the energy computation. 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.