Largest constant-weight codes A(n,d,w), open entries of Brouwer's table

# Largest constant-weight codes A(n,d,w), open entries of Brouwer's table ## Goal `cwc.py` exposes `code(n: int, d: int, w: int, time_budget: float, seed: int) -> list[int]`: a binary code of length `n`, minimum Hamming distance `d`, in which every codeword has Hamming weight exactly `w`, given as a list of distinct integers in `[0, 2^n)` (bit `i` is coordinate `i`). Return as many codewords as you can. `A(n,d,w)` is the largest size of such a code (equivalently, the largest family of `w`-subsets of an `n`-set with pairwise intersections at most `w - d/2`; packings and Steiner systems are the extreme cases). Brouwer's tables of bounds on `A(n,d,w)`, updating Brouwer, Shearer, Sloane and Smith (1990), give an explicit code for nearly every lower bound. The 22 instances here are open cells of those tables with `n <= 28`, `d = 6..14`, and records that verify in well under a second. Beat the record in any row and you have a new lower bound; the table moved in 2026 alone through Rosin (automated search, arXiv:2603.00174), Lysenstoen (arXiv:2607.19550), Echols (arXiv:2608.13906) and two batches of new codes from Boisclair, so these entries are live. ## Records Best-known lower bounds (the records) and upper bounds, read 2026-09-07 from aeb.win.tue.nl/codes/Andw.html. Every row is open. Unmarked upper bounds in the table are Agrell, Vardy and Zeger (2000); "S" Schrijver (2005), "KKT" Kang-Kim-Toan (2011), "Po" Polak (2017), "MEL" Mounits-Etzion-Litsyn (2005), "O" Ostergard (2010). "BSSS" is the 1990 table. | n | d | w | record | upper bound | source of the record | |---|---|---|---|---|---| | 18 | 6 | 5 | 69 | 72 | Aw, Chee and Ling, Ars Comb. 67 (2003) | | 20 | 6 | 5 | 90 | 100 | cyclic code, first given on Brouwer's page | | 22 | 6 | 5 | 132 | 136 | code with a prescribed automorphism group, Brouwer's page | | 18 | 6 | 6 | 133 | 186 | Rosin, arXiv:2603.00174 | | 20 | 6 | 6 | 232 | 276 | from the Nordstrom-Robinson / Golay code with tails (Brouwer, label t) | | 21 | 6 | 6 | 273 | 350 | code with a prescribed automorphism group, first given on Brouwer's page | | 20 | 6 | 7 | 462 | 651 | from the Nordstrom-Robinson / Golay code with tails (Brouwer, label t) | | 20 | 6 | 8 | 590 | 1084 (Po) | Echols, arXiv:2608.13906 | | 23 | 6 | 10 | 2992 | 7521 | Lysenstoen, arXiv:2607.19550, polished on Brouwer's page | | 24 | 6 | 10 | 4237 | 12186 | Lysenstoen, arXiv:2607.19550, polished on Brouwer's page | | 18 | 8 | 9 | 48 | 58 (O) | BSSS, shortened code | | 20 | 8 | 9 | 160 | 173 | code with a prescribed automorphism group, Brouwer's page | | 22 | 8 | 9 | 292 | 440 (Po) | Rosin, arXiv:2603.00174 | | 23 | 8 | 9 | 412 | 662 (Po) | Rosin, arXiv:2603.00174 | | 24 | 8 | 6 | 78 | 92 | BSSS | | 22 | 10 | 8 | 25 | 33 | Rosin, arXiv:2603.00174 | | 23 | 10 | 9 | 45 | 78 (MEL) | cyclic code, Brouwer's page | | 24 | 10 | 10 | 72 | 170 (KKT) | cyclic code, Brouwer's page | | 26 | 12 | 10 | 33 | 37 | Nurmela, Kaikkonen and Ostergard, IEEE Trans. Inf. Theory 43 (1997) | | 27 | 12 | 11 | 54 | 90 | cyclic code, Brouwer's page | | 28 | 12 | 12 | 119 | 198 (KKT) | code with a prescribed automorphism group, first given on Brouwer's page | | 27 | 14 | 12 | 19 | 20 | cyclic code, Brouwer's page | All 22 record codes were downloaded from the table's explicit-code links (`cwc/d6/i20.5` and so on; orbit files were expanded under the listed permutation group) and pass this eval at exactly the record size. The upper bounds 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`. ## Metric metric = mean over the 22 instances of size(n,d,w) / record(n,d,w) The eval re-derives everything from the list you return: every entry must be an `int` in `[0, 2^n)` (no `bool`) of weight exactly `w`, entries must be distinct, and every pair must be at Hamming distance at least `d` (for constant weight this is even, so `d = 6` means any two words share at most `w - 3` ones). The check is exact integer XOR and popcount, bucketed by a pigeonhole on `d` coordinate blocks. 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 s per instance, so a full eval takes about 90 s plus about a second of verification. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating - `ZT_EVAL_INSTANCES=20-6-5,24-6-10` runs a subset (labels are `n-d-w`); `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 (greedy union of random cyclic orbits, then random single words) scores about 0.56. It is weakest on the big `d = 6` rows and the `d >= 12` rows, where the records are structured. ## Ideas that are known to matter (check the journal before repeating one) - Codes with a prescribed automorphism group. Almost every record in the table is a union of orbits of a group acting on the coordinates: the full cyclic shift (`Z_n`), a product of shorter cycles (Brouwer's `cycle 1 1 9 9`, `cycle 3 3 3 ... 1 1 1`), affine groups `x -> ax + b` on `Z_p` or on `GF(q)`, `ASL(1,q)`, or two generating permutations. Enumerate orbits under the group (their internal minimum distance is fixed once), then solve a maximum clique / independent-set problem on the compatibility graph of orbits. This is the Nurmela-Kaikkonen-Ostergard method and the `g`/`c` entries of the table; it beats orbit-greedy by a wide margin. - Local search on the word level: pick a word, drop it, greedily refill from the candidates it was blocking; simulated annealing on the number of violated pairs with a tabu list. Rosin's 2026 records came from an automated search of this kind, and Lysenstoen's from fixing half the coordinates to a known code and solving the other half as a maximum-weight independent set. - Constructions from smaller codes: shortening (`A(n,d,w) >= A(n+1,d,w) * ... `, take the words with a 0 or a 1 in one coordinate), lengthening, juxtaposition, partitioning the weight-`w` words by a linear code of distance `d` (the Graham-Sloane construction), and taking the weight-`w` words of the Golay or Nordstrom-Robinson code (labels `G` and `t`) and appending "tails". - Steiner systems and packings are the `w - d/2 = t - 1` boundary: the `d = 2w - 2` rows are packings of `(w-1)`-subsets, so design-theoretic constructions (difference families, cyclic packings) apply directly. - Pairwise checks cost about 50 ns per pair in pure Python; a candidate screened against 4000 words costs about 0.2 ms, so budget candidates accordingly, or index the code by a coordinate block the way the eval does. 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.