Automated Discovery of Improved Constant Weight Binary Codes

Christopher D. Rosin

cs.ITFeb 26, 2026

Automated Discovery of Improved Constant Weight Binary Codes

Authors: Christopher D. Rosin

Abstract

A constant weight binary code consists of $n$ -bit binary codewords, each with exactly $w$ bits equal to 1, such that any two codewords are at least Hamming distance $d$ apart. $A(n,d,w)$ is the maximum size of a constant weight binary code with parameters $n,d,w$ . We establish improved lower bounds on $A(n,d,w)$ by constructing new larger codes, for 24 values of $(n,d,w)$ with $6 \leq d \leq 18$ and $18 \leq n \leq 35$ . The improved lower bounds come from two strategies. The first is a tabu search that operates at the level of bit swaps. The second is a novel greedy heuristic that repeatedly chooses the candidate codeword that maximizes a randomly-scored histogram of distances to previously-added codewords. These strategies were proposed by CPro1, an automated protocol that generates, implements, and tests diverse strategies for combinatorial constructions.

Figures & tables

$n$	$d$	$w$	Prior	New	Method
18	6	6	132	133	Bit-Swap Tabu
22	8	9	280	292	RSDH
23	8	9	400	412	RSDH
23	8	10	616	648	RSDH
24	8	9	640	656	RSDH
24	8	11	1288	1378	S-RSDH $b=1$

Table 1: New lower bounds on

A(n,d,w)

. Prior lower bounds are from [ 2 ] . * indicates matching upper bound;

A(n,d,w)

is now exactly determined in these cases.

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
10	4	4	30	13	6	5	18	14	6	6	42	15	6	7	69
18	8	6	21	20	8	7	80	17	6	7	149	17	6	8	166
18	6	6	119	19	6	6	155	20	6	8	528	21	6	8	698
27	6	5	234	22	8	9	252	23	8	6	69	24	8	6	70
17	6	7	166	17	6	8	184	18	6	6	132	19	6	6	172
20	6	8	588	21	6	8	775	27	6	5	260	22	8	9	280

Table 2: The 32 Dev instances used with CPro1. For each of these, a code with

n,d,w

having

s

codewords is known to exist. Candidate CPro1 programs are scored based on their ability to produce a code with these parameters.

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
17	6	7	167	17	6	8	185	18	6	6	133	19	6	6	173
20	6	8	589	21	6	8	776	27	6	5	261	22	8	9	281
23	8	6	78	24	8	6	79	28	8	6	131	21	10	9	28
21	10	10	39	22	10	8	25	22	10	9	36	24	10	8	39

Table 3: The 16 Open instances used with CPro1. The programs scoring best on the Dev instances are then tested on these Open instances.

Panel of Figure 3 — Figure 3: Bit-Swap Tabu Search. In the efficient implementation, Conflict-Pairs and Penalty are maintained incrementally. Note HD ( $x,y$ ) is the Hamming Distance between binary words $x$ and $y$ . We set $t_{min}=5$ , $t_{max}=15$ , max_no_improve_restart=1M.

Panel of Figure 4 — Figure 4: Random-Score Distance Histograms (RSDH). $n,w,d$ are the parameters of the code, and $s$ is the target size (number of codewords). Note HD ( $x,y$ ) is the Hamming Distance between binary words $x$ and $y$ .

Panel of Figure 5 — Figure 5: Sliced Random-Score Distance Histograms (S-RSDH). $b$ is the number of bits that define the slice; we use $b\in\{1,2,3\}$ . $t$ is the number of trials for the remainder of the code; we fix $t=1000$ . Greedy-Build, Rand-Vec, and HD are defined in Fig. 4 .

Panel of Figure 6 — Figure 6: Multi-Sliced Random-Score Distance Histograms (MS-RSDH).

Figure 7: Example trajectories of total objective function for

n=23

d=8

w=9

. Each color uses a different scoring vector. The solid trajectory reaches 400, and the dashed trajectory reaches 412 with the same scoring vector.

Figure 8: Distance map for a $n=25$ $d=8$ $w=11$ code with 1666 codewords generated by RSDH. The 1666 codewords are ordered in the sequence chosen by the greedy algorithm, from left to right and top to bottom. Row $i$ column $j$ is colored according to the distance between codeword $i$ and codeword $j$ , as shown in the color key at the top of the figure. The red/maroon/black upper-left block is size 960x960.

Error-Correcting Codes

See all 30 papers

Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes
Sep 29, 2026Amal Seddas, Vladyslav Shashkov, Maryna Viazovska +1Automated Algorithm Discovery Error-Correcting Codes
EPFL
Coding Agents for Coding Theory
Sep 30, 2026Abraham YeungCoding Agents LLM Agent Reliability
Stanford University
Large Language Model-Guided Discovery of Weight-Five Bivariate Bicycle Codes
Oct 5, 2026Juan Cruz-BenitoQuantum LDPC Codes Quantum Error Correction
IBM Research

Sep 29, 2026J/K move · Enter open · S save

Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes

Amal Seddas, Vladyslav Shashkov, Maryna Viazovska, Emmanuel Abbe

EPFL

Automated Algorithm Discovery Error-Correcting Codes

Open paper AskPDF arXiv

Evolutionary program search driven by large language models (LLMs) has produced record-breaking constructions for open problems in combinatorics and beyond. We apply this approach to the longstanding problem of improving the best-known bounds for binary linear codes. Building on the EvoTune evolutionary framework and the ShinkaEvolve codebase, we introduce LinCodeEvolve, which evolves code-construction programs against an exact minimum-distance evaluator. A strategy loop combines diversity-driven search and expert supervision: when progress plateaus, new strategies are used to redirect the search. LinCodeEvolve discovers seven record-breaking codes,

[172,21,66]

[173,20,68]

[176,21,68]

[181,21,70]

[184,21,72]

[189,22,72]

and

[200,21,77]

, six of which have concise quasi-cyclic descriptions. With standard code modification techniques, they improve

22

entries of the tables. Every code is verified by exhaustive enumeration. These results suggest that LLM-guided search can help find improved codes and complement existing methods in coding theory.

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
10	4	4	30	13	6	5	18	14	6	6	42	15	6	7	69
18	8	6	21	20	8	7	80	17	6	7	149	17	6	8	166
18	6	6	119	19	6	6	155	20	6	8	528	21	6	8	698
27	6	5	234	22	8	9	252	23	8	6	69	24	8	6	70
17	6	7	166	17	6	8	184	18	6	6	132	19	6	6	172
20	6	8	588	21	6	8	775	27	6	5	260	22	8	9	280

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
17	6	7	167	17	6	8	185	18	6	6	133	19	6	6	173
20	6	8	589	21	6	8	776	27	6	5	261	22	8	9	281
23	8	6	78	24	8	6	79	28	8	6	131	21	10	9	28
21	10	10	39	22	10	8	25	22	10	9	36	24	10	8	39

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
10	4	4	30	13	6	5	18	14	6	6	42	15	6	7	69
18	8	6	21	20	8	7	80	17	6	7	149	17	6	8	166
18	6	6	119	19	6	6	155	20	6	8	528	21	6	8	698
27	6	5	234	22	8	9	252	23	8	6	69	24	8	6	70
17	6	7	166	17	6	8	184	18	6	6	132	19	6	6	172
20	6	8	588	21	6	8	775	27	6	5	260	22	8	9	280

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
17	6	7	167	17	6	8	185	18	6	6	133	19	6	6	173
20	6	8	589	21	6	8	776	27	6	5	261	22	8	9	281
23	8	6	78	24	8	6	79	28	8	6	131	21	10	9	28
21	10	10	39	22	10	8	25	22	10	9	36	24	10	8	39

Abstract

Error-Correcting Codes

Explore similar work

Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes

Coding Agents for Coding Theory

Large Language Model-Guided Discovery of Weight-Five Bivariate Bicycle Codes

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
10	4	4	30	13	6	5	18	14	6	6	42	15	6	7	69
18	8	6	21	20	8	7	80	17	6	7	149	17	6	8	166
18	6	6	119	19	6	6	155	20	6	8	528	21	6	8	698
27	6	5	234	22	8	9	252	23	8	6	69	24	8	6	70
17	6	7	166	17	6	8	184	18	6	6	132	19	6	6	172
20	6	8	588	21	6	8	775	27	6	5	260	22	8	9	280

n	d	w	s	n	d	w	s	n	d	w	s	n	d	w	s
17	6	7	167	17	6	8	185	18	6	6	133	19	6	6	173
20	6	8	589	21	6	8	776	27	6	5	261	22	8	9	281
23	8	6	78	24	8	6	79	28	8	6	131	21	10	9	28
21	10	10	39	22	10	8	25	22	10	9	36	24	10	8	39