Largest binary codes A(n,d), open entries of Brouwer's table

# Largest binary codes A(n,d), open entries of Brouwer's table ## Goal `code.py` exposes `code(n: int, d: int, time_budget: float, seed: int) -> list[int]`: a binary code of length `n` and minimum Hamming distance `d`, given as a list of distinct integers in `[0, 2^n)` (bit `i` of the integer is coordinate `i`). Return as many codewords as you can. `A(n,d)` is the largest size of such a code. It is known exactly for small parameters and for a few families (Hamming, Golay, Nordstrom-Robinson), but for most `(n, d)` with `n >= 17` the best known code and the best proven upper bound are far apart. The 20 instances here are exactly such open cells of Andries Brouwer's table of bounds on `A(n,d)` (the updated Best-Brouwer-MacWilliams-Odlyzko- Sloane table), restricted to `n <= 28` and to sizes that verify quickly. A code larger than the record in any of them is a new lower bound; the table has moved as recently as 2019 (Milshtein's 258-word code for `A(17,6)`) and 2016 (Laaksonen and Ostergard, `A(18,4)`, `A(22,4)`, `A(24,10)`). ## Records Best-known lower bounds (the records) and upper bounds, read 2026-09-07 from aeb.win.tue.nl/codes/binary-1.html. Every row is open. "BBMOS" is the 1978 table; "AVZ" is Agrell, Vardy and Zeger, IEEE Trans. Inf. Theory 47 (2001), from which the `n = 25..28` rows are taken. | n | d | record | upper bound | source of the record | |---|---|---|---|---| | 17 | 4 | 2816 | 3276 | Milshtein, Inf. Process. Lett. 115 (2015) | | 18 | 4 | 5632 | 6552 | Laaksonen and Ostergard, arXiv:1604.06022 | | 19 | 4 | 10496 | 13104 | Hamalainen, IEEE Trans. Inf. Theory 34 (1988) | | 20 | 4 | 20480 | 26168 | Best, IEEE Trans. Inf. Theory 26 (1980) | | 17 | 6 | 258 | 340 | Milshtein, Cryptogr. Commun. (2019) | | 18 | 6 | 512 | 673 | BBMOS | | 19 | 6 | 1024 | 1237 | BBMOS | | 20 | 6 | 2048 | 2279 | BBMOS | | 21 | 6 | 2560 | 4096 | BBMOS | | 22 | 6 | 4096 | 6941 | BBMOS; the Wagner [24,14,6] code shortened twice attains it | | 23 | 6 | 8192 | 13674 | BBMOS; the Wagner [24,14,6] code shortened once attains it | | 25 | 8 | 4096 | 5421 | extended Golay [24,12,8] plus a zero coordinate | | 26 | 8 | 4104 | 9275 | van der Zee, pers. comm. to Brouwer (2012) | | 21 | 10 | 42 | 47 | Kaikkonen, IEEE Trans. Inf. Theory 35 (1989) | | 22 | 10 | 64 | 84 | Ostergard, Des. Codes Cryptogr. 36 (2005) | | 23 | 10 | 80 | 150 | Ostergard, Des. Codes Cryptogr. 36 (2005) | | 24 | 10 | 136 | 268 | Laaksonen and Ostergard, arXiv:1604.06022 | | 25 | 12 | 52 | 55 | AVZ | | 26 | 12 | 64 | 96 | AVZ | | 28 | 12 | 178 | 288 | Kaikkonen, Des. Codes Cryptogr. 15 (1998) | Upper bounds are the table's: semidefinite-programming bounds of Gijswijt, Mittelmann and Schrijver (2012) for most `d >= 6` rows; Best, Haas and Mounits-Etzion-Litsyn for `d = 4`. They are hard caps: the eval refuses any list longer than the upper bound, because such a list necessarily contains a pair at distance below `d`. Three records were reproduced while building this pack and pass the eval exactly: the `[24,14,6]` code obtained by extending the `[23,14,5]` generator matrix on codetables.de (Wagner's code), whose shortenings give 4096 words for `(22,6)` and 8192 for `(23,6)`, and the extended Golay code padded with a zero coordinate, 4096 words for `(25,8)`. ## Metric metric = mean over the 20 instances of size(n,d) / record(n,d) The eval re-derives everything from the list you return: every entry must be an `int` in `[0, 2^n)` (no `bool`), entries must be distinct, and every pair must be at Hamming distance at least `d`; the check is exact integer XOR and popcount, organised by a pigeonhole on `d` coordinate blocks so that 20 000-word codes verify in about a second. Any violation fails the whole run (`wrong_answer`); so does a solver that raises or runs past `1.25 * time_budget + 3` seconds. Only size counts; `size / record` above 1 in any row is listed in `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to `code`; the instance 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 4.5 s per instance, so a full eval takes about 90 s plus a couple of seconds of verification. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_INSTANCES=20-4,25-8` runs a subset (labels are `n-d`); `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-instance budget. Run `python eval.py` in your workspace and read `per_instance` for `size`, `ratio`, `seconds` and `verify_seconds`. - The baseline (shortened, punctured extended BCH codes of length 32 plus a random greedy top-up) 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 for `d >= 10`. The `d = 6` and `d = 8` rows are where the metric is. ## Ideas that are known to matter (check the journal before repeating one) - Better algebraic starting points. The Wagner `[24,14,6]` code (extend the `[23,14,5]` generator matrix on codetables.de by a parity bit) shortened to `n = 22, 23` matches those records outright and gives 2048 for `(21,6)`, 1024 for `(20,6)`. The extended Golay `[24,12,8]` matches `(25,8)`. The best-known linear codes in codetables.de are a floor for every row; the records above them are all nonlinear. - Lexicodes: greedy in lexicographic order produces linear codes (Conway and Sloane), including the Hamming and Golay codes. A full lexicographic scan of `2^n` candidates is too slow in Python for `n >= 22`, but a lexicode restricted to a coset or subspace, or greedy in a different fixed order, is cheap and often better than BCH. - Unions of cosets of a linear subcode: the classical `d = 4` and `d = 6` records (Best, Romanov, Hamalainen, Etzion, Milshtein) are unions of cosets of a small linear code, chosen so that the coset representatives form a code in their own right. Build the subcode first, then search over representatives; each representative check costs `|subcode|` XORs, not `|code|`. - Constructions from smaller codes: `(u | u+v)` (Plotkin), Construction X and X4 (add coordinates to a chain of codes), and doubling `A(2n, 2d) >= A(n, d)` produce most entries in the table; the `d = 10, 12` records of Kaikkonen and Ostergard are codes with a prescribed automorphism group (affine permutation groups, quasi-cyclic structure), found by search over orbit representatives. - Local search for the small rows (`d >= 10`, records under 200): start from the baseline, remove the word that blocks the most candidates, re-fill greedily; tabu on recently removed words. Sampling candidates from a structured set (a coset of a good linear code, or orbits under a cyclic shift) beats uniform sampling. - Pairwise checks cost about 50 ns per pair in pure Python; a candidate screened against 16 384 words costs about 1 ms, so budget candidates accordingly, or screen against a bucketed index of the code (the eval's own pigeonhole trick works for solvers too). Write one honest line in `NOTES.md`: the idea, and which rows 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.