{"id":"no-five-on-a-sphere","name":"No five on a sphere: largest subsets of the n×n×n grid","family":"discrete-geometry","description":"Pick as many points of the n×n×n integer grid as possible so that no five lie on a common sphere or plane, for n = 7..12. Exact integer verification; scored against the AlphaEvolve world-record sizes (problem 60).","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":240,"agent_timeout_seconds":1800,"mutable":["sphere_free.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":"# No five on a sphere: largest subsets of the n×n×n grid\n\n## Goal\n\nLet `C(n)` be the size of the largest subset of the grid `{0, ..., n-1}^3` in which **no five\npoints lie on a common sphere or a common plane**. Five points `p_i = (x_i, y_i, z_i)` are\ncospherical or coplanar exactly when\n\n    det | x_i  y_i  z_i  x_i^2 + y_i^2 + z_i^2  1 |  (rows i = 1..5)  =  0,\n\nwhich also rules out five on a plane (a plane is a degenerate sphere in this lift) and hence five\non a line. It is the three-dimensional cousin of the Erdős–Purdy \"no four on a circle\" problem and\nis AlphaEvolve problem 60. Nothing is known to be optimal; you are asked to find large sets for\n`n = 7, 8, 9, 10, 11, 12`.\n\n`sphere_free.py` exposes\n\n    build(n: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]\n\nreturning any number of distinct grid points with integer coordinates in `[0, n-1]`. The eval\nrefuses to verify more than twice the record.\n\n## Metric\n\n    metric = mean over n in {7, 8, 9, 10, 11, 12} of  points(n) / record(n)\n\nVerification is exact: the eval tests every 5-subset of the returned set with the integer\ndeterminant above (as a 4×4 determinant of lifted differences, expanded over 2×2 minors, so a\n33-point set takes 0.06 s and a 66-point set about 10 s). A set with five points on a sphere or\nplane, a point off the grid, or a duplicate fails the whole run (`wrong_answer`) rather than\nscoring low. Per-instance sizes and ratios are in the eval output (`per_instance`); any `n` above\nits record is listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to\n`build`.\n\n## Records\n\n| n | best-known points | source | proven optimal |\n|---|-------------------|--------|----------------|\n| 7 | 21 | AlphaEvolve problem 60, notebook construction (re-verified here exactly) | no |\n| 8 | 23 | same; the AlphaEvolve prompt states the previous best known for n = 8 was 22 | no |\n| 9 | 26 | same | no |\n| 10 | 28 | same | no |\n| 11 | 31 | same | no |\n| 12 | 33 | same | no |\n\nSource: \"The no 5 on a sphere problem\", problem 60 of the AlphaEvolve repository of problems\n(Georgiev, Gómez-Serrano, Tao, Wagner, *Mathematical Exploration and Discovery at Scale*,\narXiv:2511.02864, section 6.40), listed in the repository's status file as a world record. Every\nconstruction was re-checked with this pack's exact determinant test before being entered above.\nUpdate a row (in a new commit, citing the ledger entry) when a hub-verified submission exceeds it.\n\n## Constraints\n\n- Standard library only (`math`, `random`, `itertools`, `functools`, `collections`, `heapq`,\n  `time`). The eval rejects other imports.\n- Respect `time_budget` (seconds, per call).\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES` is a comma-separated subset of `7,8,9,10,11,12`; the full set is the default.\n- `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `build` per instance (default 15).\n\n```\nZT_EVAL_INSTANCES=7,8 ZT_EVAL_PER_INSTANCE_SECONDS=3 python eval.py\n```\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- The records came from randomised greedy plus iterated local search (remove 1–25 % of the set,\n  refill greedily in a new order) with 2000 s budgets and a compiled checker; the notebook notes\n  the run could not see its own earlier constructions, so there is probably headroom.\n- The evolved programs' main lever was the **candidate order** for the greedy refill: distance\n  from the origin or the centre, coordinate-sum planes, parity classes, outer or inner shells,\n  lexicographic and its reverse. Rotate through them.\n- Exact incremental checking: adding `q` to `m` points costs `C(m, 4)` determinants, six\n  multiplications each with the minor trick in the baseline (about 15 ms at `m = 25` in pure\n  Python). Restricting candidates to points that are not on any sphere through four chosen\n  points, maintained incrementally, is the way to afford many more restarts.\n- Symmetry helps the search and the write-up: the grid's 48 symmetries, and orbits under a\n  chosen subgroup, shrink the search space; parity classes `(x + y + z) mod 2` were a productive\n  ordering in the evolved code.\n\nWrite one honest line in `NOTES.md`: the idea, and which `n` 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 no-five-on-a-sphere. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact integer arithmetic: every 5-subset of the returned grid points is tested\nwith the lifted determinant det[x, y, z, x^2+y^2+z^2, 1], which is zero exactly when the five\npoints lie on a common sphere or a common plane. Environment:\n  ZT_EVAL_SEED                    seed handed to build() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated grid sizes n (default \"7,8,9,10,11,12\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to build() per instance (default 15)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\n# Best-known sizes of subsets of {0..n-1}^3 with no five points on a sphere or plane. Source:\n# AlphaEvolve problem 60 (\"The no 5 on a sphere problem\", arXiv:2511.02864 section 6.40), listed\n# there as a world record; the constructions in the published notebook were re-verified here with\n# exact integer determinants. None is proven optimal.\nRECORDS = {\"7\": 21, \"8\": 23, \"9\": 26, \"10\": 28, \"11\": 31, \"12\": 33}\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"7,8,9,10,11,12\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"15\"))\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\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 {path.name}: {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_points(raw, n: int) -> list[tuple[int, int, int]]:\n    if not isinstance(raw, (list, tuple)) or not raw:\n        fail(f\"build({n}) must return a non-empty list of (x, y, z) grid points\", \"wrong_answer\")\n    if len(raw) > 2 * RECORDS[str(n)]:\n        fail(f\"build({n}) returned {len(raw)} points, over twice the record; refusing to verify\", \"wrong_answer\")\n    pts = []\n    for i, p in enumerate(raw):\n        try:\n            if len(p) != 3:\n                raise TypeError\n            c = []\n            for v in p:\n                if isinstance(v, bool) or v != int(v):\n                    raise TypeError\n                c.append(int(v))\n        except Exception:\n            fail(f\"build({n}): point {i} is not an integer triple: {p!r}\", \"wrong_answer\")\n        if not all(0 <= v < n for v in c):\n            fail(f\"build({n}): point {i} = {tuple(c)} is outside the grid [0, {n - 1}]^3\", \"wrong_answer\")\n        pts.append(tuple(c))\n    if len(set(pts)) != len(pts):\n        fail(f\"build({n}) returned duplicate points\", \"wrong_answer\")\n    return pts\n\n\ndef five_cospherical(pts: list[tuple[int, int, int]]):\n    \"\"\"Exact search for five points on a common sphere or plane. Returns them, or None.\n\n    Lifting p -> (x, y, z, x^2+y^2+z^2), the 5x5 determinant with a column of ones equals the 4x4\n    determinant of the lifted differences from the first point; that is expanded by Laplace over\n    pairs of rows using precomputed 2x2 minors, so each 5-subset costs six multiplications.\n    \"\"\"\n    P = [(x, y, z, x * x + y * y + z * z) for x, y, z in pts]\n    m = len(P)\n    for i in range(m):\n        pi = P[i]\n        V = [(q[0] - pi[0], q[1] - pi[1], q[2] - pi[2], q[3] - pi[3]) for q in P[i + 1:]]\n        r = len(V)\n        minors = [[None] * r for _ in range(r)]\n        for a in range(r):\n            va = V[a]\n            for b in range(a + 1, r):\n                vb = V[b]\n                minors[a][b] = (va[0] * vb[1] - va[1] * vb[0], va[0] * vb[2] - va[2] * vb[0],\n                                va[0] * vb[3] - va[3] * vb[0], va[1] * vb[2] - va[2] * vb[1],\n                                va[1] * vb[3] - va[3] * vb[1], va[2] * vb[3] - va[3] * vb[2])\n        for a in range(r):\n            ma = minors[a]\n            for b in range(a + 1, r):\n                m01, m02, m03, m12, m13, m23 = ma[b]\n                for c in range(b + 1, r):\n                    mc = minors[c]\n                    for d in range(c + 1, r):\n                        n01, n02, n03, n12, n13, n23 = mc[d]\n                        if m01 * n23 - m02 * n13 + m03 * n12 + m12 * n03 - m13 * n02 + m23 * n01 == 0:\n                            base = i + 1\n                            return pts[i], pts[base + a], pts[base + b], pts[base + c], pts[base + d]\n    return None\n\n\ndef verify(n: int, raw) -> int:\n    \"\"\"Exact check. Returns the number of points.\"\"\"\n    pts = parse_points(raw, n)\n    bad = five_cospherical(pts)\n    if bad is not None:\n        fail(f\"build({n}): five points on a common sphere or plane: {bad}\", \"wrong_answer\")\n    return len(pts)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"sphere_free.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import sphere_free as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import sphere_free.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"build\"):\n        fail(\"sphere_free.py must define build(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"no5sphere|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for n={label}\", \"error\")\n        n = int(label)\n        t0 = time.perf_counter()\n        try:\n            raw = cand.build(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"build({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"build({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        size = verify(n, raw)\n        rec = RECORDS[label]\n        per_instance[label] = {\"points\": size, \"record\": rec, \"ratio\": round(size / rec, 6), \"seconds\": round(elapsed, 2)}\n        if size > rec:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per_instance.values()) / len(per_instance)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per_instance, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"sphere_free.py":"\"\"\"Baseline: random greedy. Walks the grid in a seeded random order and keeps every point that\ndoes not complete five points on a sphere or plane (exact integer determinants). Lands well\nshort of the records.\"\"\"\n\nimport itertools\nimport random\nimport time\n\n\ndef can_add(P, q):\n    \"\"\"P: list of lifted points (x, y, z, x^2+y^2+z^2). Exact: no 4 of P are cospherical with q.\"\"\"\n    V = [(p[0] - q[0], p[1] - q[1], p[2] - q[2], p[3] - q[3]) for p in P]\n    r = len(V)\n    if r < 4:\n        return True\n    minors = [[None] * r for _ in range(r)]\n    for a in range(r):\n        va = V[a]\n        for b in range(a + 1, r):\n            vb = V[b]\n            minors[a][b] = (va[0] * vb[1] - va[1] * vb[0], va[0] * vb[2] - va[2] * vb[0],\n                            va[0] * vb[3] - va[3] * vb[0], va[1] * vb[2] - va[2] * vb[1],\n                            va[1] * vb[3] - va[3] * vb[1], va[2] * vb[3] - va[3] * vb[2])\n    for a in range(r):\n        ma = minors[a]\n        for b in range(a + 1, r):\n            m01, m02, m03, m12, m13, m23 = ma[b]\n            for c in range(b + 1, r):\n                mc = minors[c]\n                for d in range(c + 1, r):\n                    n01, n02, n03, n12, n13, n23 = mc[d]\n                    if m01 * n23 - m02 * n13 + m03 * n12 + m12 * n03 - m13 * n02 + m23 * n01 == 0:\n                        return False\n    return True\n\n\ndef build(n: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]:\n    rnd = random.Random(seed)\n    t0 = time.perf_counter()\n    grid = list(itertools.product(range(n), repeat=3))\n    rnd.shuffle(grid)\n    chosen = []\n    for x, y, z in grid:\n        if time.perf_counter() - t0 > 0.8 * time_budget:\n            break\n        q = (x, y, z, x * x + y * y + z * z)\n        if can_add(chosen, q):\n            chosen.append(q)\n    return [(x, y, z) for x, y, z, _ in chosen]\n"}}