{"id":"cap-sets","name":"Cap sets in F_3^n","family":"discrete-geometry","description":"Find the largest subset of F_3^n with no three distinct points on a line (no x + y + z = 0), for n = 6, 7, 8, 9. Exact verification; scored against 112 (proven), 236 (Calderbank-Fishburn), 512 (FunSearch, Nature 2024) and 1082 (product construction).","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["capset.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":"# Cap sets in F_3^n\n\n## Goal\n\nA *cap set* is a subset of `F_3^n` (vectors of length `n` over `{0, 1, 2}`, addition mod 3) that\ncontains no three distinct points on a line. Lines in `F_3^n` have exactly three points and\n`{x, y, z}` is a line iff `x + y + z = 0`, so the condition is: for every two distinct points\n`x, y` of the set, `-(x + y)` (coordinatewise `(-(x_i + y_i)) mod 3`) is not in the set.\nEquivalently, no three-term arithmetic progression. The card game SET is the case `n = 4`.\n\nBuild the largest cap set you can for `n = 6, 7, 8, 9`.\n\n`capset.py` exposes\n\n    cap(n: int, time_budget: float, seed: int) -> list\n\nreturning the points of the set, each either a tuple/list of `n` digits in `{0, 1, 2}` or an\ninteger `v` in `[0, 3^n)` read in base 3 (coordinate `i` is `(v // 3**i) % 3`). Mixing the two\nforms is fine. The eval refuses to verify more than `record + 50` points.\n\n## Metric\n\n    metric = mean over n in {6, 7, 8, 9} of  size(n) / record(n)\n\nVerification is exact and trusts nothing the solver reports: points are normalised, duplicates\nare rejected, and for every unordered pair the third point of the line is looked up in the set\n(bitmask encoding, `O(size^2)` with a hash lookup: under a second for 1082 points). A set with\nthree collinear points on any `n` fails the whole run (`wrong_answer`). Any `n` whose size exceeds\nthe record is listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to\n`cap`; the instance set is fixed.\n\n## Records\n\n| n | best known | proven optimal | source |\n|---|---|---|---|\n| 6 | 112 | yes | Potechin, \"Maximal caps in AG(6,3)\", Des. Codes Cryptogr. 46 (2008): the doubled Hill cap is the unique maximum. Calibration instance. |\n| 7 | 236 | no (no 289-cap exists: arXiv:2206.09804) | Calderbank & Fishburn, \"Maximal three-independent subsets of {0,1,2}^n\", Des. Codes Cryptogr. 4 (1994); still the best known per Bierbrauer & Edel, \"Large caps in projective Galois spaces\" (2012) and Romera-Paredes et al., Nature 625 (2024), Fig. 4a |\n| 8 | 512 | no | FunSearch: Romera-Paredes et al., \"Mathematical discoveries from program search with large language models\", Nature 625 (2024) 468-475, Fig. 4 and SI Appendix E.2 (explicit construction); previous best 496 (Edel 2004) |\n| 9 | 1082 | no | Edel's generalized product construction, \"Extensions of generalized product caps\", Des. Codes Cryptogr. 31 (2004); FunSearch's SI Fig. C.5 gives a priority function reproducing 1082 and its notebook calls it the largest known |\n\nWhy no `n = 10`: the number 2474 is widely quoted for it, but on 2026-09-07 no primary source\nstating it could be reached (Edel's site no longer hosts the affine table; the TU Delft thesis on\nupper bounds lists only the product bound 2240; FunSearch stops at `n = 9`). Rather than pin an\nunverifiable record, the instance is left out; add it to `RECORDS` in `eval.py` once a citation\nis in hand.\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). The default is 20 s per instance, about 90 s for a\n  full eval including verification.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating quickly\n\n- `ZT_EVAL_INSTANCES` is a comma-separated subset of `6,7,8,9`; the full set is the default.\n- `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `cap` per instance (default 20).\n\n```\nZT_EVAL_INSTANCES=6,7 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py\n```\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- **Products.** If `A` is a cap in `F_3^a` and `B` a cap in `F_3^b`, then `A x B` (concatenate\n  coordinates) is a cap in `F_3^(a+b)`. With the exact small caps (2, 4, 9, 20, 45, 112 for\n  `n = 1..6`) this gives 224 for `n = 7`, 448 for `n = 8`, 1008 for `n = 9`. The baseline only\n  finds its factors greedily; hard-coding the Pellegrino 20-cap and the 112-cap already helps.\n- **Doubling.** An `m`-cap in `PG(d, 3)` gives a `2m`-cap in `AG(d+1, 3)`: the 56-point Hill cap\n  in `PG(5, 3)` is how the 112-cap in dimension 6 arises. Ovoids (`q^2 + 1` points in `PG(3, q)`)\n  are the other classical ingredient.\n- **The 512-cap has structure.** FunSearch's explicit construction (Nature 2024, Fig. 4c and SI\n  E.2) is a union of four 128-point pieces: all vectors with no zero entries satisfying a\n  reflection condition (entry `i` versus entry `-i`), plus vectors of half support on chosen\n  support patterns. Priority functions that score a vector by counts of zeros, by\n  `(v[i], v[-i])` reflections and by support patterns, then greedily add in priority order, are\n  what found it; that search space is small and cheap to evaluate.\n- **Edel's generalized product / admissible sets** underlie 1082 and every asymptotic record\n  (Tyrrell 2023, FunSearch, X-evolve). Symmetric \"admissible sets\" combined with the 112-cap give\n  caps in dimensions that are multiples of 6 plus small offsets.\n- **Local search.** Keep the set of forbidden points (`-(x+y)` over pairs) incrementally; remove\n  a few points, re-add greedily by a priority, keep if not smaller (tabu on recently removed\n  points). Extending a cap by one point is possible iff the point is outside the forbidden set,\n  so \"complete\" caps are easy to detect and swaps are cheap.\n- Beating 236, 512 or 1082 would be a new record in a well-studied table; expect the last few\n  points to be hard and treat any `ratio > 1` as a bug until the hub's exact re-verification agrees.\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 cap-sets. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nA cap set is a subset of F_3^n with no three distinct points x, y, z satisfying x + y + z = 0\n(equivalently: no three collinear points). Verification is exact: every point is normalised to a\nvector over {0, 1, 2}, duplicates are rejected, and for every unordered pair {x, y} the third point\nof their line, -(x + y), is looked up in the set. Nothing the solver reports is trusted.\nEnvironment:\n  ZT_EVAL_SEED                    seed handed to cap() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated n values (default \"6,7,8,9\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to cap() per instance (default 20)\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# Largest known cap sets in F_3^n. Sources (read 2026-09-07):\n#   6: 112, proven maximal by Potechin, \"Maximal caps in AG(6,3)\", Des. Codes Cryptogr. 46 (2008);\n#      the cap is the doubled Hill cap.\n#   7: 236, Calderbank & Fishburn, \"Maximal three-independent subsets of {0,1,2}^n\", Des. Codes\n#      Cryptogr. 4 (1994); quoted as the best known in Bierbrauer & Edel, \"Large caps in projective\n#      Galois spaces\" (2012) and in Romera-Paredes et al., Nature 625 (2024), Fig. 4a. Not proven\n#      (no 289-cap exists in dimension 7: arXiv:2206.09804).\n#   8: 512, FunSearch (Romera-Paredes et al., \"Mathematical discoveries from program search with\n#      large language models\", Nature 625 (2024) 468-475, Fig. 4 and SI Appendix E.2), improving\n#      Edel's 496. Not proven.\n#   9: 1082, Edel's generalized product construction (Des. Codes Cryptogr. 31 (2004)); FunSearch's\n#      SI Fig. C.5 rediscovers a 1082-point set and its notebook calls 1082 the largest known.\n#      Not proven.\n# n = 10 is deliberately absent: the value 2474 circulates for it but no primary source could be\n# reached on 2026-09-07 (see program.md). Update when a hub-verified submission exceeds these.\nRECORDS = {6: 112, 7: 236, 8: 512, 9: 1082}\nPROVEN = {6}\nEXTRA = 50   # refuse to verify sets larger than record + EXTRA\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"6,7,8,9\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"20\"))\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 _int(v, n: int, what: str) -> int:\n    if isinstance(v, bool) or not isinstance(v, (int, float)) or v != int(v):\n        fail(f\"cap({n}): {what} is not an integer: {v!r}\", \"wrong_answer\")\n    return int(v)\n\n\ndef to_vectors(raw, n: int) -> list[tuple[int, ...]]:\n    \"\"\"Normalise the returned object to tuples over {0, 1, 2} of length n.\n\n    Each point may be a sequence of n digits in {0, 1, 2}, or an integer v in [0, 3^n) read in\n    base 3 with coordinate i equal to (v // 3**i) % 3.\n    \"\"\"\n    if not isinstance(raw, (list, tuple, set, frozenset)):\n        fail(f\"cap({n}) must return a list of points\", \"wrong_answer\")\n    if len(raw) > RECORDS[n] + EXTRA:\n        fail(f\"cap({n}) returned {len(raw)} points, more than record + {EXTRA}; refusing to verify\", \"wrong_answer\")\n    pts = []\n    for i, p in enumerate(raw):\n        if isinstance(p, (int, float)) and not isinstance(p, bool):\n            v = _int(p, n, f\"point {i}\")\n            if not (0 <= v < 3 ** n):\n                fail(f\"cap({n}): point {i} = {v} is outside [0, 3^{n})\", \"wrong_answer\")\n            digs = []\n            for _ in range(n):\n                digs.append(v % 3)\n                v //= 3\n            pts.append(tuple(digs))\n            continue\n        try:\n            coords = list(p)\n        except Exception:\n            fail(f\"cap({n}): point {i} is neither a coordinate sequence nor an integer: {p!r}\", \"wrong_answer\")\n        if len(coords) != n:\n            fail(f\"cap({n}): point {i} has {len(coords)} coordinates, expected {n}\", \"wrong_answer\")\n        digs = []\n        for c in coords:\n            d = _int(c, n, f\"a coordinate of point {i}\")\n            if d not in (0, 1, 2):\n                fail(f\"cap({n}): point {i} has a coordinate {d} outside 0..2\", \"wrong_answer\")\n            digs.append(d)\n        pts.append(tuple(digs))\n    if len(set(pts)) != len(pts):\n        fail(f\"cap({n}) returned a repeated point\", \"wrong_answer\")\n    return pts\n\n\ndef verify(raw, n: int) -> int:\n    \"\"\"Exact cap check. Returns the number of points.\"\"\"\n    pts = to_vectors(raw, n)\n    full = (1 << n) - 1\n    # Each point becomes a pair of bitmasks: positions holding digit 1 and positions holding digit 2.\n    enc = []\n    for p in pts:\n        m1 = m2 = 0\n        for i, d in enumerate(p):\n            if d == 1:\n                m1 |= 1 << i\n            elif d == 2:\n                m2 |= 1 << i\n        enc.append((m1, m2))\n    keys = {m1 | (m2 << n): idx for idx, (m1, m2) in enumerate(enc)}\n    # Third point on the line through a and b: z = -(a + b) digitwise, i.e.\n    #   digit 1 where (a, b) in {(0,2), (2,0), (1,1)},  digit 2 where (a, b) in {(0,1), (1,0), (2,2)}.\n    m = len(enc)\n    for i in range(m):\n        a1, a2 = enc[i]\n        a0 = full & ~(a1 | a2)\n        for j in range(i + 1, m):\n            b1, b2 = enc[j]\n            b0 = full & ~(b1 | b2)\n            z1 = (a0 & b2) | (a2 & b0) | (a1 & b1)\n            z2 = (a0 & b1) | (a1 & b0) | (a2 & b2)\n            k = keys.get(z1 | (z2 << n))\n            if k is not None:\n                fail(f\"cap({n}): three collinear points {pts[i]}, {pts[j]}, {pts[k]} (they sum to 0)\", \"wrong_answer\")\n    return m\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"capset.py\")\n    sys.dont_write_bytecode = True  # a stale capset.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import capset as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import capset.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"cap\"):\n        fail(\"capset.py must define cap(n, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"capset|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for n in INSTANCES:\n        if n not in RECORDS:\n            fail(f\"no record for n={n}\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            raw = cand.cap(n, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"cap({n}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"cap({n}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        size = verify(raw, n)\n        rec = RECORDS[n]\n        per_instance[str(n)] = {\"size\": size, \"record\": rec, \"proven_optimal\": n in PROVEN,\n                                \"ratio\": round(size / rec, 6), \"seconds\": round(elapsed, 2)}\n        if size > rec:\n            beaten.append(n)\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":{"capset.py":"\"\"\"Baseline: randomised greedy caps in small dimensions, combined by the product construction.\n\nIf A is a cap in F_3^a and B a cap in F_3^b then A x B (concatenate coordinates) is a cap in\nF_3^(a+b). Greedy search finds decent caps for a <= 5 quickly; the best split a + b = n wins.\nLands around 0.6-0.8 of the records. Beat it (the doubled Hill cap alone gives 112 for n = 6).\n\"\"\"\n\nimport itertools\nimport random\nimport time\n\nRESTARTS = {1: 1, 2: 4, 3: 30, 4: 60, 5: 40, 6: 12}   # fixed counts keep the result deterministic\n\n\ndef greedy_cap(d, rng):\n    \"\"\"Random-order greedy: keep a point unless it completes a line with two chosen points.\"\"\"\n    pts = list(itertools.product(range(3), repeat=d))\n    rng.shuffle(pts)\n    chosen, forbidden = [], set()\n    for p in pts:\n        if p in forbidden:\n            continue\n        for q in chosen:\n            forbidden.add(tuple((-x - y) % 3 for x, y in zip(p, q)))\n        chosen.append(p)\n    return chosen\n\n\ndef cap(n: int, time_budget: float, seed: int) -> list[tuple[int, ...]]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.8 * time_budget\n    best = {1: [(0,), (1,)]}\n    for d in range(2, n + 1):\n        cands = []\n        for _ in range(RESTARTS.get(d, 4)):\n            if time.perf_counter() > deadline:   # only bites when the budget is cut short\n                break\n            cands.append(greedy_cap(d, rng))\n        best[d] = max(cands, key=len) if cands else []\n        for a in range(1, d // 2 + 1):           # product of the best caps in a and d - a dimensions\n            prod = [p + q for p in best[a] for q in best[d - a]]\n            if len(prod) > len(best[d]):\n                best[d] = prod\n    return best[n]\n"}}