{"id":"binary-codes-a-n-d","name":"Largest binary codes A(n,d), open entries of Brouwer's table","family":"coding-theory","description":"Return an explicit binary code (list of integers below 2^n) of length n with minimum Hamming distance d, as large as you can, for 20 pairs (n, d) with n <= 28 whose best-known lower and upper bounds on A(n,d) still differ. The eval recomputes the minimum distance from the words; the score is code size over the best-known lower bound.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["code.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":"# Largest binary codes A(n,d), open entries of Brouwer's table\n\n## Goal\n\n`code.py` exposes `code(n: int, d: int, time_budget: float, seed: int) -> list[int]`: a binary code\nof length `n` and minimum Hamming distance `d`, given as a list of distinct integers in `[0, 2^n)`\n(bit `i` of the integer is coordinate `i`). Return as many codewords as you can.\n\n`A(n,d)` is the largest size of such a code. It is known exactly for small parameters and for a few\nfamilies (Hamming, Golay, Nordstrom-Robinson), but for most `(n, d)` with `n >= 17` the best known\ncode and the best proven upper bound are far apart. The 20 instances here are exactly such open\ncells of Andries Brouwer's table of bounds on `A(n,d)` (the updated Best-Brouwer-MacWilliams-Odlyzko-\nSloane table), restricted to `n <= 28` and to sizes that verify quickly. A code larger than the\nrecord in any of them is a new lower bound; the table has moved as recently as 2019 (Milshtein's\n258-word code for `A(17,6)`) and 2016 (Laaksonen and Ostergard, `A(18,4)`, `A(22,4)`, `A(24,10)`).\n\n## Records\n\nBest-known lower bounds (the records) and upper bounds, read 2026-09-07 from\naeb.win.tue.nl/codes/binary-1.html. Every row is open. \"BBMOS\" is the 1978 table; \"AVZ\" is Agrell,\nVardy and Zeger, IEEE Trans. Inf. Theory 47 (2001), from which the `n = 25..28` rows are taken.\n\n| n | d | record | upper bound | source of the record |\n|---|---|---|---|---|\n| 17 | 4 | 2816 | 3276 | Milshtein, Inf. Process. Lett. 115 (2015) |\n| 18 | 4 | 5632 | 6552 | Laaksonen and Ostergard, arXiv:1604.06022 |\n| 19 | 4 | 10496 | 13104 | Hamalainen, IEEE Trans. Inf. Theory 34 (1988) |\n| 20 | 4 | 20480 | 26168 | Best, IEEE Trans. Inf. Theory 26 (1980) |\n| 17 | 6 | 258 | 340 | Milshtein, Cryptogr. Commun. (2019) |\n| 18 | 6 | 512 | 673 | BBMOS |\n| 19 | 6 | 1024 | 1237 | BBMOS |\n| 20 | 6 | 2048 | 2279 | BBMOS |\n| 21 | 6 | 2560 | 4096 | BBMOS |\n| 22 | 6 | 4096 | 6941 | BBMOS; the Wagner [24,14,6] code shortened twice attains it |\n| 23 | 6 | 8192 | 13674 | BBMOS; the Wagner [24,14,6] code shortened once attains it |\n| 25 | 8 | 4096 | 5421 | extended Golay [24,12,8] plus a zero coordinate |\n| 26 | 8 | 4104 | 9275 | van der Zee, pers. comm. to Brouwer (2012) |\n| 21 | 10 | 42 | 47 | Kaikkonen, IEEE Trans. Inf. Theory 35 (1989) |\n| 22 | 10 | 64 | 84 | Ostergard, Des. Codes Cryptogr. 36 (2005) |\n| 23 | 10 | 80 | 150 | Ostergard, Des. Codes Cryptogr. 36 (2005) |\n| 24 | 10 | 136 | 268 | Laaksonen and Ostergard, arXiv:1604.06022 |\n| 25 | 12 | 52 | 55 | AVZ |\n| 26 | 12 | 64 | 96 | AVZ |\n| 28 | 12 | 178 | 288 | Kaikkonen, Des. Codes Cryptogr. 15 (1998) |\n\nUpper bounds are the table's: semidefinite-programming bounds of Gijswijt, Mittelmann and Schrijver\n(2012) for most `d >= 6` rows; Best, Haas and Mounits-Etzion-Litsyn for `d = 4`. They are hard caps:\nthe eval refuses any list longer than the upper bound, because such a list necessarily contains a\npair at distance below `d`.\n\nThree records were reproduced while building this pack and pass the eval exactly: the `[24,14,6]`\ncode obtained by extending the `[23,14,5]` generator matrix on codetables.de (Wagner's code), whose\nshortenings give 4096 words for `(22,6)` and 8192 for `(23,6)`, and the extended Golay code padded\nwith a zero coordinate, 4096 words for `(25,8)`.\n\n## Metric\n\n    metric = mean over the 20 instances of  size(n,d) / record(n,d)\n\nThe eval re-derives everything from the list you return: every entry must be an `int` in\n`[0, 2^n)` (no `bool`), entries must be distinct, and every pair must be at Hamming distance at least\n`d`; the check is exact integer XOR and popcount, organised by a pigeonhole on `d` coordinate blocks\nso that 20 000-word codes verify in about a second. Any violation fails the whole run\n(`wrong_answer`); so does a solver that raises or runs past `1.25 * time_budget + 3` seconds. Only\nsize counts; `size / record` above 1 in any row is listed in `records_beaten`.\n\n`ZT_EVAL_SEED` only changes the `seed` handed to `code`; the instance set is fixed.\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 4.5 s per instance, so a full eval takes\n  about 90 s plus a couple of seconds of verification.\n- Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=20-4,25-8` runs a subset (labels are `n-d`);\n  `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-instance budget. Run `python eval.py` in your\n  workspace and read `per_instance` for `size`, `ratio`, `seconds` and `verify_seconds`.\n- The baseline (shortened, punctured extended BCH codes of length 32 plus a random greedy top-up)\n  scores about 0.49: 0.73-0.80 for `d = 4`, 0.25-0.5 for `d = 6`, under 0.3 for `d = 8`, and 0.36-0.72\n  for `d >= 10`. The `d = 6` and `d = 8` rows are where the metric is.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- Better algebraic starting points. The Wagner `[24,14,6]` code (extend the `[23,14,5]` generator\n  matrix on codetables.de by a parity bit) shortened to `n = 22, 23` matches those records outright and\n  gives 2048 for `(21,6)`, 1024 for `(20,6)`. The extended Golay `[24,12,8]` matches `(25,8)`. The\n  best-known linear codes in codetables.de are a floor for every row; the records above them are all\n  nonlinear.\n- Lexicodes: greedy in lexicographic order produces linear codes (Conway and Sloane), including the\n  Hamming and Golay codes. A full lexicographic scan of `2^n` candidates is too slow in Python for\n  `n >= 22`, but a lexicode restricted to a coset or subspace, or greedy in a different fixed order, is\n  cheap and often better than BCH.\n- Unions of cosets of a linear subcode: the classical `d = 4` and `d = 6` records (Best, Romanov,\n  Hamalainen, Etzion, Milshtein) are unions of cosets of a small linear code, chosen so that the\n  coset representatives form a code in their own right. Build the subcode first, then search over\n  representatives; each representative check costs `|subcode|` XORs, not `|code|`.\n- Constructions from smaller codes: `(u | u+v)` (Plotkin), Construction X and X4 (add coordinates to\n  a chain of codes), and doubling `A(2n, 2d) >= A(n, d)` produce most entries in the table; the\n  `d = 10, 12` records of Kaikkonen and Ostergard are codes with a prescribed automorphism group\n  (affine permutation groups, quasi-cyclic structure), found by search over orbit representatives.\n- Local search for the small rows (`d >= 10`, records under 200): start from the baseline, remove the\n  word that blocks the most candidates, re-fill greedily; tabu on recently removed words. Sampling\n  candidates from a structured set (a coset of a good linear code, or orbits under a cyclic shift)\n  beats uniform sampling.\n- Pairwise checks cost about 50 ns per pair in pure Python; a candidate screened against 16 384 words\n  costs about 1 ms, so budget candidates accordingly, or screen against a bucketed index of the\n  code (the eval's own pigeonhole trick works for solvers too).\n\nWrite one honest line in `NOTES.md`: the idea, and which rows 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 binary-codes-a-n-d. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns a list of codewords (integers below 2^n). The eval recomputes everything from\nthat list: distinctness, range, and the minimum Hamming distance (exact integer XOR + popcount),\nand scores size / best-known lower bound. Nothing the solver reports is trusted.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to code()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per (n, d) (default 4.5)\n  ZT_EVAL_INSTANCES              comma-separated labels \"n-d\" (default: all 20 below)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"4.5\"))\nDEFAULT_INSTANCES = (\"17-4,18-4,19-4,20-4,17-6,18-6,19-6,20-6,21-6,22-6,23-6,25-8,26-8,\"\n                     \"21-10,22-10,23-10,24-10,25-12,26-12,28-12\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", DEFAULT_INSTANCES).split(\",\") if x.strip()]\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# (n, d) -> (best-known lower bound = record, best-known upper bound, source of the lower bound).\n# Read 2026-09-07 from Andries Brouwer's table of bounds on A(n,d) (aeb.win.tue.nl/codes/binary-1.html),\n# which updates Best, Brouwer, MacWilliams, Odlyzko and Sloane, \"Bounds for binary codes of length\n# less than 25\", IEEE Trans. Inf. Theory 24 (1978) (\"BBMOS\"), and takes n = 25..28 from Agrell, Vardy\n# and Zeger, IEEE Trans. Inf. Theory 47 (2001) (\"AVZ\"). Upper bounds are the table's: mostly\n# Gijswijt, Mittelmann and Schrijver, IEEE Trans. Inf. Theory 58 (2012) for d >= 6; Best 1980,\n# Haas 2008 and Mounits, Etzion and Litsyn 2007 for d = 4. Every entry here is open: lower < upper.\n# Update when a hub-verified submission exceeds the record.\nRECORDS = {\n    (17, 4): (2816, 3276, \"Milshtein, Inf. Process. Lett. 115 (2015)\"),\n    (18, 4): (5632, 6552, \"Laaksonen and Ostergard, arXiv:1604.06022 (2016)\"),\n    (19, 4): (10496, 13104, \"Hamalainen, IEEE Trans. Inf. Theory 34 (1988)\"),\n    (20, 4): (20480, 26168, \"Best, IEEE Trans. Inf. Theory 26 (1980)\"),\n    (17, 6): (258, 340, \"Milshtein, Cryptogr. Commun. (2019)\"),\n    (18, 6): (512, 673, \"BBMOS 1978 table (Brouwer)\"),\n    (19, 6): (1024, 1237, \"BBMOS 1978 table (Brouwer)\"),\n    (20, 6): (2048, 2279, \"BBMOS 1978 table (Brouwer)\"),\n    (21, 6): (2560, 4096, \"BBMOS 1978 table (Brouwer)\"),\n    (22, 6): (4096, 6941, \"BBMOS 1978 table; the [24,14,6] Wagner code shortened twice\"),\n    (23, 6): (8192, 13674, \"BBMOS 1978 table; the [24,14,6] Wagner code shortened once\"),\n    (25, 8): (4096, 5421, \"extended Golay [24,12,8] plus a zero coordinate (BBMOS/AVZ)\"),\n    (26, 8): (4104, 9275, \"van der Zee, pers. comm. to Brouwer (2012)\"),\n    (21, 10): (42, 47, \"Kaikkonen, IEEE Trans. Inf. Theory 35 (1989)\"),\n    (22, 10): (64, 84, \"Ostergard, Des. Codes Cryptogr. 36 (2005)\"),\n    (23, 10): (80, 150, \"Ostergard, Des. Codes Cryptogr. 36 (2005)\"),\n    (24, 10): (136, 268, \"Laaksonen and Ostergard, arXiv:1604.06022 (2016)\"),\n    (25, 12): (52, 55, \"AVZ 2001 table (Brouwer)\"),\n    (26, 12): (64, 96, \"AVZ 2001 table (Brouwer)\"),\n    (28, 12): (178, 288, \"Kaikkonen, Des. Codes Cryptogr. 15 (1998)\"),\n}\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 code.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_label(label: str) -> tuple[int, int]:\n    try:\n        n, d = (int(x) for x in label.split(\"-\"))\n    except Exception:\n        fail(f\"bad instance label {label!r}, expected 'n-d'\", \"error\")\n    if (n, d) not in RECORDS:\n        fail(f\"no record for (n, d) = ({n}, {d})\", \"error\")\n    return n, d\n\n\ndef parse_words(words, n: int, d: int) -> list[int]:\n    \"\"\"Return the codewords as distinct ints in [0, 2^n). Anything else is a wrong answer.\"\"\"\n    tag = f\"code({n}, {d})\"\n    if not isinstance(words, (list, tuple, set, frozenset)):\n        fail(f\"{tag} must return a list of integers\", \"wrong_answer\")\n    upper = RECORDS[(n, d)][1]\n    if len(words) > upper:\n        fail(f\"{tag} returned {len(words)} words, more than the proven upper bound A({n},{d}) <= {upper}: \"\n             \"such a list necessarily contains two words at distance < d; refusing to verify\", \"wrong_answer\")\n    out = []\n    for x in words:\n        if isinstance(x, bool) or not isinstance(x, int):\n            fail(f\"{tag} returned a non-integer codeword {x!r}\"[:300], \"wrong_answer\")\n        if x < 0 or x >> n:\n            fail(f\"{tag} returned {x}, which is not in [0, 2^{n})\", \"wrong_answer\")\n        out.append(x)\n    if len(set(out)) != len(out):\n        fail(f\"{tag} returned duplicate codewords (distance 0)\", \"wrong_answer\")\n    return out\n\n\ndef hamming_cap(m: int, d: int) -> int:\n    \"\"\"Sphere-packing bound on a binary code of length m and minimum distance d.\"\"\"\n    t = (d - 1) // 2\n    return (1 << m) // sum(math.comb(m, i) for i in range(t + 1))\n\n\ndef check_min_distance(code: list[int], n: int, d: int) -> None:\n    \"\"\"Fail unless every pair of codewords is at Hamming distance >= d.\n\n    Pigeonhole: split the n coordinates into d blocks; two words at distance <= d-1 agree on at\n    least one whole block, so only pairs that share a block value need comparing. Words sharing a\n    block of b coordinates form a code of length n-b and distance d, so a bucket larger than the\n    sphere-packing bound for (n-b, d) is impossible and is rejected outright (this also bounds the\n    work on adversarial input).\n    \"\"\"\n    tag = f\"code({n}, {d})\"\n    sizes = [n // d + (1 if i < n % d else 0) for i in range(d)]\n    shift = 0\n    for b in sizes:\n        mask = (1 << b) - 1\n        buckets: dict[int, list[int]] = {}\n        for c in code:\n            buckets.setdefault((c >> shift) & mask, []).append(c)\n        cap = hamming_cap(n - b, d)\n        for lst in buckets.values():\n            if len(lst) > cap:\n                fail(f\"{tag}: {len(lst)} codewords agree on {b} coordinates, but a distance-{d} code of length \"\n                     f\"{n - b} has at most {cap} words; the list contains a pair at distance < {d}\", \"wrong_answer\")\n            for i in range(len(lst) - 1):\n                ci = lst[i]\n                for cj in lst[i + 1:]:\n                    if (ci ^ cj).bit_count() < d:\n                        fail(f\"{tag}: codewords {ci} and {cj} are at distance {(ci ^ cj).bit_count()} < {d}\",\n                             \"wrong_answer\")\n        shift += b\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"code.py\")\n    sys.dont_write_bytecode = True  # a stale code.pyc must never be what gets scored\n    sys.path.insert(0, str(here))\n    try:\n        import code as cand  # noqa: E402  (shadows the stdlib module of that name on purpose)\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import code.py failed: {e!r}\", \"compile_error\")\n    if not callable(getattr(cand, \"code\", None)):\n        fail(\"code.py must define code(n, d, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"andd|{SEED}\").getrandbits(32)\n    per, beaten = {}, []\n    for label in INSTANCES:\n        n, d = parse_label(label)\n        record, upper, _src = RECORDS[(n, d)]\n        t0 = time.perf_counter()\n        try:\n            words = cand.code(n, d, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"code({n}, {d}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"code({n}, {d}) took {elapsed:.1f}s against a {BUDGET:.1f}s budget\", \"timeout\")\n        t1 = time.perf_counter()\n        code = parse_words(words, n, d)\n        check_min_distance(code, n, d)\n        size = len(code)\n        per[f\"{n}-{d}\"] = {\"size\": size, \"record\": record, \"upper_bound\": upper,\n                           \"ratio\": round(size / record, 6), \"seconds\": round(elapsed, 2),\n                           \"verify_seconds\": round(time.perf_counter() - t1, 2)}\n        if size > record:\n            beaten.append(f\"{n}-{d}\")\n    metric = sum(v[\"ratio\"] for v in per.values()) / len(per)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"code.py":"\"\"\"Baseline: a shortened and punctured extended BCH code of length 32, then a greedy top-up.\n\nThe extended primitive BCH codes of length 32 with designed distance 4, 6, 8, 12, 16 are\n[32,26,4], [32,21,6], [32,16,8], [32,11,12], [32,6,16]. For (n, d) take the smallest designed\ndistance dd >= d, puncture dd - d coordinates (the distance drops by at most that) and shorten the\nrest down to length n. That gives 2^(n-6) words for d = 4, 2^(n-11) for d = 6, 2^(n-16) for d = 8\nand small codes for d >= 10, all valid, in milliseconds. The remaining budget goes to a random\ngreedy that adds any word at distance >= d from everything so far; it only helps the small codes.\nScores about 0.49 of the records on average. Beat it.\n\"\"\"\n\nimport random\nimport time\n\n# Generator polynomials of the primitive BCH codes of length 31 (octal; Lin and Costello, Table 6.4),\n# keyed by the minimum distance of the extended code.\nBCH32 = {4: 0o45, 6: 0o3551, 8: 0o107657, 12: 0o5423325, 16: 0o313365047}\n\n\ndef _bch_basis(dd: int) -> list[int]:\n    \"\"\"Reduced-echelon basis (pivot = highest bit, 32-bit words) of the extended BCH code.\"\"\"\n    g = BCH32[dd]\n    rows: list[int] = []\n    for i in range(31 - (g.bit_length() - 1)):\n        v = g << i\n        for r in rows:\n            if (v >> (r.bit_length() - 1)) & 1:\n                v ^= r\n        if v:\n            p = v.bit_length() - 1\n            rows = [r ^ v if (r >> p) & 1 else r for r in rows]\n            rows.append(v)\n    return [(r << 1) | (r.bit_count() & 1) for r in rows]  # overall parity bit\n\n\ndef _algebraic(n: int, d: int) -> list[int]:\n    dd = min(k for k in BCH32 if k >= d)\n    p = dd - d                      # coordinates to puncture (the low ones)\n    keep = [r >> p for r in _bch_basis(dd) if r.bit_length() <= n + p]  # shorten on the high ones\n    words = [0]\n    for b in keep:\n        words = words + [w ^ b for w in words]\n    return words\n\n\ndef code(n: int, d: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    words = _algebraic(n, d)\n    deadline = time.perf_counter() + 0.85 * time_budget\n    full = 1 << n\n    while time.perf_counter() < deadline:\n        for _ in range(64):\n            c = rng.randrange(full)\n            if all((c ^ w).bit_count() >= d for w in words):\n                words.append(c)\n    return words\n"}}