Coding Agents for Coding Theory
Abstract
We spent five weeks using an LLM coding agent on open problems in coding theory: finding large sets of four-letter words, such as DNA barcodes, that stay far apart in edit distance. The agent wrote the verifiers and search code; a human chose the problem and set the verification protocol. Restricting the search to codes with a prescribed symmetry, a classical technique, shrank the problem about fourfold and raised the best known code of length 6 and minimum edit distance 3 from 114 to 120 words (E4(6,3) ≥ 120). The same pipeline improved twelve further lower bounds at lengths 6 to 9 and distances 3 to 6. We give the failures equal space. Our own search stopped at 116 and recorded the last symmetry class as topping out at 112; a second agent session, running the same search with a better operator, found the 120. A later verdict that the method did not carry over to length 7 was wrong for the same reason, and an earlier instance cost three weeks. Each time, an intermediate result was written down, never rechecked, and treated as a fact that ruled out further search. Checking final outputs, as our protocol required, does not catch such errors.
Related
- GTDD: Generative Test-Driven Development for AI Coding Agents with Adversarial Testing
- Perfect Combinatorial Structures in Coding Theory and Cryptography
- Covert Multi-bit LLM Watermarking: An Information Theory and Coding Approach
- Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs
- Complete Topological Invariant and Coding of Homoclinic Flows on the Two-Dimensional Sphere
BibTeX
@misc{yeung2026coding,
title = {{Coding Agents for Coding Theory}},
author = {Abraham Yeung},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39081},
eprint = {2609.39081},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39081},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Coding Agents for Coding Theory
AU - Abraham Yeung
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39081
UR - https://arxiv.org/abs/2609.39081
AB - We spent five weeks using an LLM coding agent on open problems in coding theory: finding large sets of four-letter words, such as DNA barcodes, that stay far apart in edit distance. The agent wrote the verifiers and search code; a human chose the problem and set the verification protocol. Restricting the search to codes with a prescribed symmetry, a classical technique, shrank the problem about fourfold and raised the best known code of length 6 and minimum edit distance 3 from 114 to 120 words (E_4(6,3) ≥ 120). The same pipeline improved twelve further lower bounds at lengths 6 to 9 and distances 3 to 6. We give the failures equal space. Our own search stopped at 116 and recorded the last symmetry class as topping out at 112; a second agent session, running the same search with a better operator, found the 120. A later verdict that the method did not carry over to length 7 was wrong for the same reason, and an earlier instance cost three weeks. Each time, an intermediate result was written down, never rechecked, and treated as a fact that ruled out further search. Checking final outputs, as our protocol required, does not catch such errors.
ER -