No five on a sphere: largest subsets of the n×n×n grid

# No five on a sphere: largest subsets of the n×n×n grid ## Goal Let `C(n)` be the size of the largest subset of the grid `{0, ..., n-1}^3` in which **no five points lie on a common sphere or a common plane**. Five points `p_i = (x_i, y_i, z_i)` are cospherical or coplanar exactly when det | x_i y_i z_i x_i^2 + y_i^2 + z_i^2 1 | (rows i = 1..5) = 0, which also rules out five on a plane (a plane is a degenerate sphere in this lift) and hence five on a line. It is the three-dimensional cousin of the Erdős–Purdy "no four on a circle" problem and is AlphaEvolve problem 60. Nothing is known to be optimal; you are asked to find large sets for `n = 7, 8, 9, 10, 11, 12`. `sphere_free.py` exposes build(n: int, time_budget: float, seed: int) -> list[tuple[int, int, int]] returning any number of distinct grid points with integer coordinates in `[0, n-1]`. The eval refuses to verify more than twice the record. ## Metric metric = mean over n in {7, 8, 9, 10, 11, 12} of points(n) / record(n) Verification is exact: the eval tests every 5-subset of the returned set with the integer determinant above (as a 4×4 determinant of lifted differences, expanded over 2×2 minors, so a 33-point set takes 0.06 s and a 66-point set about 10 s). A set with five points on a sphere or plane, a point off the grid, or a duplicate fails the whole run (`wrong_answer`) rather than scoring low. Per-instance sizes and ratios are in the eval output (`per_instance`); any `n` above its record is listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to `build`. ## Records | n | best-known points | source | proven optimal | |---|-------------------|--------|----------------| | 7 | 21 | AlphaEvolve problem 60, notebook construction (re-verified here exactly) | no | | 8 | 23 | same; the AlphaEvolve prompt states the previous best known for n = 8 was 22 | no | | 9 | 26 | same | no | | 10 | 28 | same | no | | 11 | 31 | same | no | | 12 | 33 | same | no | Source: "The no 5 on a sphere problem", problem 60 of the AlphaEvolve repository of problems (Georgiev, Gómez-Serrano, Tao, Wagner, *Mathematical Exploration and Discovery at Scale*, arXiv:2511.02864, section 6.40), listed in the repository's status file as a world record. Every construction was re-checked with this pack's exact determinant test before being entered above. Update a row (in a new commit, citing the ledger entry) when a hub-verified submission exceeds it. ## Constraints - Standard library only (`math`, `random`, `itertools`, `functools`, `collections`, `heapq`, `time`). The eval rejects other imports. - Respect `time_budget` (seconds, per call). - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_INSTANCES` is a comma-separated subset of `7,8,9,10,11,12`; the full set is the default. - `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `build` per instance (default 15). ``` ZT_EVAL_INSTANCES=7,8 ZT_EVAL_PER_INSTANCE_SECONDS=3 python eval.py ``` ## Ideas that are known to matter (check the journal before repeating one) - The records came from randomised greedy plus iterated local search (remove 1–25 % of the set, refill greedily in a new order) with 2000 s budgets and a compiled checker; the notebook notes the run could not see its own earlier constructions, so there is probably headroom. - The evolved programs' main lever was the **candidate order** for the greedy refill: distance from the origin or the centre, coordinate-sum planes, parity classes, outer or inner shells, lexicographic and its reverse. Rotate through them. - Exact incremental checking: adding `q` to `m` points costs `C(m, 4)` determinants, six multiplications each with the minor trick in the baseline (about 15 ms at `m = 25` in pure Python). Restricting candidates to points that are not on any sphere through four chosen points, maintained incrementally, is the way to afford many more restarts. - Symmetry helps the search and the write-up: the grid's 48 symmetries, and orbits under a chosen subgroup, shrink the search space; parity classes `(x + y + z) mod 2` were a productive ordering in the evolved code. 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.