Kissing numbers, lower bounds in dimensions 5 to 16

# Kissing numbers, lower bounds in dimensions 5 to 16 ## Goal `kissing.py` exposes `kiss(d: int, time_budget: float, seed: int) -> list[list[int]]`: a list of non-zero vectors in `R^d` such that every pair is at least 60 degrees apart. Return as many as you can. The vectors are directions only: the eval never looks at their lengths, so any non-zero multiple is the same vector, and two vectors with a positive dot product `<x,y>` pass exactly when 4 <x,y>^2 <= |x|^2 |y|^2 (i.e. cos(angle) <= 1/2) The kissing number `tau(d)` is the largest number of non-overlapping unit spheres that can all touch one central unit sphere; their centres, seen from the centre, are exactly a set of directions with pairwise angles at least 60 degrees. It is known exactly only in `d = 1, 2, 3, 4, 8, 24`. In every other dimension the best known configuration is a lower bound and there is a gap to the best upper bound; those gaps are what this benchmark is about. The records in `d = 10, 11, 12, 14` all fell between 2022 and 2026 (Ganzhinov's symmetric constructions, AlphaEvolve's 593 in `d = 11`, then 604 and 841 in 2026), so the table is still moving. ## Records Best-known lower bounds read from Henry Cohn's table (cohn.mit.edu/kissing-numbers, 2026-09-07) with the sources it cites, cross-checked against the Wikipedia table the same day. Upper bounds are from the same table (de Laat and Leijenhorst 2024 for `d >= 10`). Only `d = 8` is proven; the rest are open. `size / record` above 1 in any open dimension is a new record. | d | best known | upper bound | proven | source of the lower bound | |---|---|---|---|---| | 5 | 40 | 44 | no | Korkine and Zolotareff, Math. Ann. 6 (1873); the D5 lattice | | 6 | 72 | 77 | no | Korkine and Zolotareff (1873); the E6 lattice | | 7 | 126 | 134 | no | Korkine and Zolotareff (1873); the E7 lattice | | 8 | 240 | 240 | yes | Korkine and Zolotareff (1873), E8; upper bound Levenshtein 1979, Odlyzko and Sloane 1979 | | 9 | 306 | 363 | no | Leech and Sloane, Canad. J. Math. 23 (1971); non-lattice, from codes | | 10 | 510 | 553 | no | Ganzhinov, "Highly symmetric lines", Linear Algebra Appl. 722 (2025), arXiv:2207.08266 | | 11 | 604 | 868 | no | Bianchi, Kwon, Pappu, Zou, arXiv:2606.10402 (June 2026); previously 593 (AlphaEvolve, Novikov et al. 2025) and 592 (Ganzhinov) | | 12 | 841 | 1355 | no | Takhanov, Assylbekov, Yun, "Structure of kissing arrangements in R^12 and a place for the 841st sphere", arXiv:2606.18984 (June 2026); previously 840 | | 13 | 1154 | 2064 | no | Zinoviev and Ericson, Problems Inform. Transmission 35 (1999) | | 14 | 1932 | 3174 | no | Ganzhinov (2025), arXiv:2207.08266 | | 15 | 2564 | 4853 | no | Leech and Sloane (1971) | | 16 | 4320 | 7320 | no | Barnes and Wall, J. Austral. Math. Soc. 1 (1959); the Barnes-Wall lattice | The 11- and 12-dimensional entries are 2026 preprints that Cohn's table has accepted; the 841 was constructed numerically, so an exact (integer) 841 in `d = 12` would be worth reporting even at ratio 1.0. AlphaEvolve's 593-point configuration in `d = 11` is public (google-deepmind/alphaevolve_results, `mathematical_results.ipynb`, section B.11, integer coordinates) and passes this eval exactly; it scores 593/604. ## Metric metric = mean over d in {5, ..., 16} of size(d) / record(d) The eval re-derives everything from the vectors you return. Two verification modes: - **Exact** (preferred): every coordinate is a Python `int` (any size, `bool` is rejected). The check is pure integer arithmetic, `<x,y> <= 0 or 4<x,y>^2 <= |x|^2 |y|^2`, so there is no tolerance at all. Rational coordinates: multiply each vector by its common denominator. - **Float**: if any coordinate is a `float`, all vectors are normalised in floating point and every pairwise cosine must be `<= 0.5 + 1e-9`. A float configuration above a record is reported in `records_beaten_float`, not `records_beaten`; only exact configurations count as record claims. Any zero vector, non-finite coordinate, wrong-length vector, or pair closer than 60 degrees fails the run (`wrong_answer`), and so does returning more than `record + 50` vectors (the eval refuses to spend `O(m^2 d)` on an absurd list). A solver that raises or overruns `1.25 * time_budget + 3` seconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to `kiss`; the dimension set is fixed. ## Constraints - Standard library only. No numpy, no scipy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 7 s per dimension, so a full eval takes about a minute plus verification (about 3 s for a 4320-vector answer in `d = 16`). - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_INSTANCES=8,11` runs a subset of dimensions; `ZT_EVAL_PER_INSTANCE_SECONDS=2` shortens the per-dimension budget. Run `python eval.py` in your workspace. - The per-dimension detail in the eval output (`size`, `ratio`, `verify_seconds`) shows where you are furthest from the record. The baseline scores 1.0 in `d = 5` and 0.16 in `d = 16` (metric 0.546), so the big dimensions are where the metric is. ## Ideas that are known to matter (check the journal before repeating one) - The records are lattices and codes, not search output: `D_d` roots give `2d(d-1)`; `E8` is `D8` plus the 128 vectors `(+-1)^8` with an even number of minus signs (scale the roots by 2 so all norms match, or just return them unscaled, the eval only cares about angles). The Barnes-Wall lattice in `d = 16`, the laminated lattices `Lambda_9 .. Lambda_15` and Leech-Sloane's "Construction A/B" from binary codes (a code word `c` of length `d` becomes the vectors with `+-1` on its support, `+-2 e_i`, etc.) reproduce most of the table. The non-lattice records in `d = 9, 10, 11, 13, 14` come from codes too: Zinoviev-Ericson's 1154 in `d = 13` and Ganzhinov's configurations are unions of orbits under a finite group. - Greedy over a small alphabet works for a while: sample vectors with entries in `{-2..2}` (or `{-1,0,1}` on supports of size `>= 8`, which are automatically 60 degrees from all `D_d` roots), keep those that fit. The baseline does this; it saturates far below the records because random vectors do not organise into a code. Seed the search with a code instead. - Local search on the angle graph: a vector that blocks several candidates can be moved or dropped. Since angles only matter, represent vectors as integers and mutate coordinates; check the new vector against its neighbours only (keep a list of near-60-degree pairs). - AlphaEvolve's 593 came from a perturbation search over large-integer coordinates (13-digit entries); the lemma it uses is `min |x - y| >= max |x|`, a sufficient condition slightly stronger than the angle test used here. - Pairwise checks in pure Python cost about 0.35 microseconds per pair for `d = 16`; a candidate screened against 4000 vectors costs about 1.5 ms, so budget candidates accordingly. Write one honest line in `NOTES.md`: the idea, and which `d` 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.