Bounds on edit-metric codes

Notes

Reading the tables

A single number is the exact value. a–b means the value is between a and b. ≥a means only a lower bound is known. Hover a coloured cell to see where its value comes from and what Houghten's table gives; click it to jump to its entry in the list of improvements. In the variable-length tables a code may contain words of any length up to n, the empty word included.

Bounds that follow from others

Appending the same symbol to every word of a code leaves all distances unchanged, so E_q(n+1,d) ≥ E_q(n,d). A code with minimum distance d+1 also has minimum distance d, so E_q(n,d) ≥ E_q(n,d+1). Cells marked as following from an improved cell take their value this way. Every upper bound is Houghten's.

Checking a code

Each code file has a short header declaring q, n, d, the size and the SHA-256 of the sorted codewords, followed by one word per line. check.py needs only Python 3 and checks one file at a time:

python3 check.py codes/edit4_n13_d3_size500882.txt

Before it was listed, each code here was also accepted by three verifiers that share no code: a ball-marking check, a sort-based ball-collision check and a pairwise bit-parallel Levenshtein check.

How the new codes were found

The entries from Yeung 2026 came from searching for codes invariant under a chosen group of symbol permutations and reversal, which shrinks the search to orbits of words. Of the entries first published here, the large quaternary ones are lexicodes: take the words in lexicographic order and keep each one that is far enough from every word kept so far. Most binary and ternary ones come from iterated local search for a maximum independent set in the conflict graph, whose vertices are all qⁿ words, with an edge between two words closer than d. Where that graph is too large, the search runs on the graph of orbits under a small group of symbol permutations and reversal, which the paper uses for the quaternary cells. The same search reproduces every exact value it was run on before any open cell was believed. The small codes at large d come from tabu search on the codewords themselves: random words are changed one symbol at a time, always making the change that most reduces how far the close pairs fall short of d, and a word is added whenever no pair is too close. All of these searches were run by an LLM coding agent under the protocol in the paper, which also describes what went wrong along the way.

Sources

• S. Houghten, tables of bounds on edit-metric codes, Brock University: index, with the five tables linked above. They first appeared in S. K. Houghten, D. Ashlock and J. Lenarz, Construction of optimal edit metric codes, Proc. 2006 IEEE Information Theory Workshop, 259–263, and S. Baker, R. Flack and S. Houghten, Optimal variable-length insertion-deletion correcting codes and edit metric codes, Congressus Numerantium 186 (2008), 65–80. Houghten's pages list the later improvements and their sources.
• A. Yeung, Coding Agents for Coding Theory, NeurIPS 2026 MATH-AI Workshop, arXiv:2609.39081 arxiv.org/abs/2609.39081
• F. Weindel and R. Heckel, LLM-Guided Search for Deletion-Correcting Codes, arXiv:2504.00613, Table 3. The codewords are not published. arxiv.org/abs/2504.00613