{"id":"kissing-numbers","name":"Kissing numbers, lower bounds in dimensions 5 to 16","family":"spherical-codes","description":"Return as many non-zero vectors in R^d as possible with every pairwise angle at least 60 degrees (centres of unit spheres all touching a central unit sphere), for d = 5..16. Integer coordinates are verified exactly. Scored against the best-known kissing numbers from Henry Cohn's table; only d = 8 is proven.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["kissing.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Kissing numbers, lower bounds in dimensions 5 to 16\n\n## Goal\n\n`kissing.py` exposes `kiss(d: int, time_budget: float, seed: int) -> list[list[int]]`: a list of\nnon-zero vectors in `R^d` such that every pair is at least 60 degrees apart. Return as many as you\ncan. The vectors are directions only: the eval never looks at their lengths, so any non-zero\nmultiple is the same vector, and two vectors with a positive dot product `<x,y>` pass exactly when\n\n    4 <x,y>^2  <=  |x|^2 |y|^2        (i.e. cos(angle) <= 1/2)\n\nThe kissing number `tau(d)` is the largest number of non-overlapping unit spheres that can all touch\none central unit sphere; their centres, seen from the centre, are exactly a set of directions with\npairwise angles at least 60 degrees. It is known exactly only in `d = 1, 2, 3, 4, 8, 24`. In every\nother dimension the best known configuration is a lower bound and there is a gap to the best upper\nbound; those gaps are what this benchmark is about. The records in `d = 10, 11, 12, 14` all fell\nbetween 2022 and 2026 (Ganzhinov's symmetric constructions, AlphaEvolve's 593 in `d = 11`, then 604\nand 841 in 2026), so the table is still moving.\n\n## Records\n\nBest-known lower bounds read from Henry Cohn's table (cohn.mit.edu/kissing-numbers, 2026-09-07) with\nthe sources it cites, cross-checked against the Wikipedia table the same day. Upper bounds are from\nthe same table (de Laat and Leijenhorst 2024 for `d >= 10`). Only `d = 8` is proven; the rest are\nopen. `size / record` above 1 in any open dimension is a new record.\n\n| d | best known | upper bound | proven | source of the lower bound |\n|---|---|---|---|---|\n| 5 | 40 | 44 | no | Korkine and Zolotareff, Math. Ann. 6 (1873); the D5 lattice |\n| 6 | 72 | 77 | no | Korkine and Zolotareff (1873); the E6 lattice |\n| 7 | 126 | 134 | no | Korkine and Zolotareff (1873); the E7 lattice |\n| 8 | 240 | 240 | yes | Korkine and Zolotareff (1873), E8; upper bound Levenshtein 1979, Odlyzko and Sloane 1979 |\n| 9 | 306 | 363 | no | Leech and Sloane, Canad. J. Math. 23 (1971); non-lattice, from codes |\n| 10 | 510 | 553 | no | Ganzhinov, \"Highly symmetric lines\", Linear Algebra Appl. 722 (2025), arXiv:2207.08266 |\n| 11 | 604 | 868 | no | Bianchi, Kwon, Pappu, Zou, arXiv:2606.10402 (June 2026); previously 593 (AlphaEvolve, Novikov et al. 2025) and 592 (Ganzhinov) |\n| 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 |\n| 13 | 1154 | 2064 | no | Zinoviev and Ericson, Problems Inform. Transmission 35 (1999) |\n| 14 | 1932 | 3174 | no | Ganzhinov (2025), arXiv:2207.08266 |\n| 15 | 2564 | 4853 | no | Leech and Sloane (1971) |\n| 16 | 4320 | 7320 | no | Barnes and Wall, J. Austral. Math. Soc. 1 (1959); the Barnes-Wall lattice |\n\nThe 11- and 12-dimensional entries are 2026 preprints that Cohn's table has accepted; the 841 was\nconstructed numerically, so an exact (integer) 841 in `d = 12` would be worth reporting even at\nratio 1.0. AlphaEvolve's 593-point configuration in `d = 11` is public\n(google-deepmind/alphaevolve_results, `mathematical_results.ipynb`, section B.11, integer\ncoordinates) and passes this eval exactly; it scores 593/604.\n\n## Metric\n\n    metric = mean over d in {5, ..., 16} of  size(d) / record(d)\n\nThe eval re-derives everything from the vectors you return. Two verification modes:\n\n- **Exact** (preferred): every coordinate is a Python `int` (any size, `bool` is rejected). The\n  check is pure integer arithmetic, `<x,y> <= 0 or 4<x,y>^2 <= |x|^2 |y|^2`, so there is no\n  tolerance at all. Rational coordinates: multiply each vector by its common denominator.\n- **Float**: if any coordinate is a `float`, all vectors are normalised in floating point and every\n  pairwise cosine must be `<= 0.5 + 1e-9`. A float configuration above a record is reported in\n  `records_beaten_float`, not `records_beaten`; only exact configurations count as record claims.\n\nAny zero vector, non-finite coordinate, wrong-length vector, or pair closer than 60 degrees fails the\nrun (`wrong_answer`), and so does returning more than `record + 50` vectors (the eval refuses to\nspend `O(m^2 d)` on an absurd list). A solver that raises or overruns `1.25 * time_budget + 3`\nseconds fails too. `ZT_EVAL_SEED` only changes the `seed` handed to `kiss`; the dimension set is\nfixed.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The default is 7 s per dimension, so a full eval takes\n  about a minute plus verification (about 3 s for a 4320-vector answer in `d = 16`).\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=8,11` runs a subset of dimensions; `ZT_EVAL_PER_INSTANCE_SECONDS=2` shortens\n  the per-dimension budget. Run `python eval.py` in your workspace.\n- The per-dimension detail in the eval output (`size`, `ratio`, `verify_seconds`) shows where you\n  are furthest from the record. The baseline scores 1.0 in `d = 5` and 0.16 in `d = 16`\n  (metric 0.546), so the big dimensions are where the metric is.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- The records are lattices and codes, not search output: `D_d` roots give `2d(d-1)`; `E8` is `D8`\n  plus the 128 vectors `(+-1)^8` with an even number of minus signs (scale the roots by 2 so all\n  norms match, or just return them unscaled, the eval only cares about angles). The Barnes-Wall\n  lattice in `d = 16`, the laminated lattices `Lambda_9 .. Lambda_15` and Leech-Sloane's\n  \"Construction A/B\" from binary codes (a code word `c` of length `d` becomes the vectors with\n  `+-1` on its support, `+-2 e_i`, etc.) reproduce most of the table. The non-lattice records in\n  `d = 9, 10, 11, 13, 14` come from codes too: Zinoviev-Ericson's 1154 in `d = 13` and Ganzhinov's\n  configurations are unions of orbits under a finite group.\n- Greedy over a small alphabet works for a while: sample vectors with entries in `{-2..2}` (or\n  `{-1,0,1}` on supports of size `>= 8`, which are automatically 60 degrees from all `D_d` roots),\n  keep those that fit. The baseline does this; it saturates far below the records because random\n  vectors do not organise into a code. Seed the search with a code instead.\n- Local search on the angle graph: a vector that blocks several candidates can be moved or dropped.\n  Since angles only matter, represent vectors as integers and mutate coordinates; check the new\n  vector against its neighbours only (keep a list of near-60-degree pairs).\n- AlphaEvolve's 593 came from a perturbation search over large-integer coordinates (13-digit\n  entries); the lemma it uses is `min |x - y| >= max |x|`, a sufficient condition slightly stronger\n  than the angle test used here.\n- Pairwise checks in pure Python cost about 0.35 microseconds per pair for `d = 16`; a candidate\n  screened against 4000 vectors costs about 1.5 ms, so budget candidates accordingly.\n\nWrite one honest line in `NOTES.md`: the idea, and which `d` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for kissing-numbers. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns vectors; the eval recomputes everything (non-zero, pairwise angle >= 60 degrees)\nfrom those vectors and counts them. Nothing the solver reports is trusted. Integer coordinates are\nchecked with exact integer arithmetic; float coordinates with a 1e-9 tolerance on the cosine.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to kiss()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per dimension (default 7)\n  ZT_EVAL_INSTANCES              comma-separated dimensions (default \"5,6,7,8,9,10,11,12,13,14,15,16\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom operator import mul\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"7\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"5,6,7,8,9,10,11,12,13,14,15,16\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nEPS = 1e-9\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\n# Best-known kissing numbers (lower bounds), read 2026-09-07 from Henry Cohn's table\n# (cohn.mit.edu/kissing-numbers) and cross-checked against the Wikipedia table. Sources as cited there:\n#   5, 6, 7:  Korkine and Zolotareff, Math. Ann. 6 (1873): lattices D5, E6, E7\n#   8:        240, proven (Korkine-Zolotareff 1873 lower bound, E8; Levenshtein 1979 and Odlyzko-Sloane 1979 upper)\n#   9, 15:    Leech and Sloane, Canad. J. Math. 23 (1971): non-lattice constructions from codes\n#   10, 14:   Ganzhinov, \"Highly symmetric lines\", Linear Algebra Appl. 722 (2025), arXiv:2207.08266\n#   11:       Bianchi, Kwon, Pappu, Zou, arXiv:2606.10402 (June 2026), 604; the previous bests were\n#             AlphaEvolve's 593 (Novikov et al. 2025) and Ganzhinov's 592\n#   12:       Takhanov, Assylbekov, Yun, arXiv:2606.18984 (June 2026), 841; previous best 840\n#   13:       Zinoviev and Ericson, Problems Inform. Transmission 35 (1999)\n#   16:       Barnes and Wall, J. Austral. Math. Soc. 1 (1959): the Barnes-Wall lattice\n# Every dimension here except 8 is open (upper bounds 44, 77, 134, 363, 553, 868, 1355, 2064, 3174,\n# 4853, 7320). Update when a hub-verified integer submission exceeds these.\nRECORDS = {5: 40, 6: 72, 7: 126, 8: 240, 9: 306, 10: 510, 11: 604, 12: 841, 13: 1154, 14: 1932, 15: 2564, 16: 4320}\nPROVEN = {8}\nMAX_EXTRA = 50  # refuse to verify more than record + MAX_EXTRA vectors (keeps the O(m^2 d) check bounded)\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in kissing.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\ndef parse(vectors, d: int) -> tuple[list[tuple], bool]:\n    \"\"\"Return (vectors, exact). exact is True when every coordinate is an int (bools are rejected).\"\"\"\n    if not isinstance(vectors, (list, tuple)):\n        fail(f\"kiss({d}) must return a list of {d}-dimensional vectors\", \"wrong_answer\")\n    if len(vectors) > RECORDS[d] + MAX_EXTRA:\n        fail(f\"kiss({d}) returned {len(vectors)} vectors, more than record + {MAX_EXTRA} = {RECORDS[d] + MAX_EXTRA}; \"\n             \"refusing to verify\", \"wrong_answer\")\n    exact = True\n    out = []\n    for v in vectors:\n        if not isinstance(v, (list, tuple)) or len(v) != d:\n            fail(f\"kiss({d}) returned a vector that is not a length-{d} list: {v!r}\"[:300], \"wrong_answer\")\n        row = []\n        for x in v:\n            if isinstance(x, bool) or not isinstance(x, (int, float)):\n                fail(f\"kiss({d}) returned a non-numeric coordinate {x!r}\"[:300], \"wrong_answer\")\n            if isinstance(x, float):\n                if not math.isfinite(x):\n                    fail(f\"kiss({d}) returned a non-finite coordinate\", \"wrong_answer\")\n                exact = False\n            row.append(x)\n        out.append(tuple(row))\n    return out, exact\n\n\ndef count_exact(vs: list[tuple], d: int) -> int:\n    \"\"\"Integer vectors: no zero vector, and for every pair <x,y> <= 0 or 4<x,y>^2 <= |x|^2 |y|^2.\"\"\"\n    n2 = [sum(x * x for x in v) for v in vs]\n    for i, s in enumerate(n2):\n        if s == 0:\n            fail(f\"kiss({d}): vector {i} is the zero vector, which has no direction\", \"wrong_answer\")\n    m = len(vs)\n    for i in range(m):\n        vi, ni = vs[i], n2[i]\n        for j in range(i + 1, m):\n            s = sum(map(mul, vi, vs[j]))\n            if s > 0 and 4 * s * s > ni * n2[j]:\n                fail(f\"kiss({d}): vectors {i} and {j} are less than 60 degrees apart \"\n                     f\"(<x,y> = {s}, |x|^2 = {ni}, |y|^2 = {n2[j]})\", \"wrong_answer\")\n    return m\n\n\ndef count_float(vs: list[tuple], d: int) -> int:\n    \"\"\"Float vectors: normalise, then every pairwise cosine must be <= 1/2 + EPS.\"\"\"\n    unit = []\n    for i, v in enumerate(vs):\n        r = math.sqrt(sum(float(x) * float(x) for x in v))\n        if not r > 0.0 or not math.isfinite(r):\n            fail(f\"kiss({d}): vector {i} is zero or overflowed, which has no direction\", \"wrong_answer\")\n        unit.append(tuple(float(x) / r for x in v))\n    m = len(unit)\n    lim = 0.5 + EPS\n    for i in range(m):\n        vi = unit[i]\n        for j in range(i + 1, m):\n            c = sum(map(mul, vi, unit[j]))\n            if c > lim:\n                fail(f\"kiss({d}): vectors {i} and {j} are less than 60 degrees apart (cosine {c:.12f})\", \"wrong_answer\")\n    return m\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"kissing.py\")\n    sys.dont_write_bytecode = True  # a stale kissing.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import kissing as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import kissing.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"kiss\"):\n        fail(\"kissing.py must define kiss(d, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"kissing|{SEED}\").getrandbits(32)\n    per_d, beaten, beaten_float = {}, [], []\n    for d in INSTANCES:\n        if d not in RECORDS:\n            fail(f\"no record for d={d}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            vectors = cand.kiss(d, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"kiss({d}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"kiss({d}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        vs, exact = parse(vectors, d)\n        t1 = time.perf_counter()\n        size = count_exact(vs, d) if exact else count_float(vs, d)\n        per_d[d] = {\"size\": size, \"record\": RECORDS[d], \"proven_optimal\": d in PROVEN, \"exact\": exact,\n                    \"ratio\": round(size / RECORDS[d], 6), \"seconds\": round(elapsed, 2),\n                    \"verify_seconds\": round(time.perf_counter() - t1, 2)}\n        if size > RECORDS[d]:\n            (beaten if exact else beaten_float).append(d)\n    metric = sum(v[\"ratio\"] for v in per_d.values()) / len(per_d)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_d\": per_d, \"records_beaten\": beaten,\n                      \"records_beaten_float\": beaten_float}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"kissing.py":"\"\"\"Baseline: the D_d root system (all +-e_i +- e_j, 2d(d-1) vectors, angle >= 60 degrees pairwise),\nthen a greedy that keeps adding random {-1, 0, 1} vectors of support >= 8 whenever they stay at\nleast 60 degrees from everything placed so far. Matches the record only in d = 5. Beat it.\"\"\"\n\nimport random\nimport time\nfrom operator import mul\n\n\ndef _roots(d: int) -> list[tuple[int, ...]]:\n    out = []\n    for i in range(d):\n        for j in range(i + 1, d):\n            for si in (1, -1):\n                for sj in (1, -1):\n                    v = [0] * d\n                    v[i], v[j] = si, sj\n                    out.append(tuple(v))\n    return out\n\n\ndef _fits(c: tuple[int, ...], nc: int, vs: list[tuple[int, ...]], n2: list[int]) -> bool:\n    \"\"\"True when c is >= 60 degrees from every v: <c,v> <= 0 or 4<c,v>^2 <= |c|^2 |v|^2.\"\"\"\n    for v, nv in zip(vs, n2):\n        s = sum(map(mul, c, v))\n        if s > 0 and 4 * s * s > nc * nv:\n            return False\n    return True\n\n\ndef kiss(d: int, time_budget: float, seed: int) -> list[tuple[int, ...]]:\n    rng = random.Random(seed)\n    vs = _roots(d)\n    n2 = [2] * len(vs)\n    if d < 8:\n        return vs  # no {-1,0,1} vector is 60 degrees from every D_d root when d < 8\n    deadline = time.perf_counter() + 0.9 * time_budget\n    for _ in range(200_000):\n        if time.perf_counter() > deadline:\n            break\n        k = rng.randint(8, d)\n        support = rng.sample(range(d), k)\n        c = [0] * d\n        for i in support:\n            c[i] = rng.choice((-1, 1))\n        c = tuple(c)\n        if _fits(c, k, vs, n2):\n            vs.append(c)\n            n2.append(k)\n    return vs\n"}}