Binary codes correcting two deletions, lengths 16 to 18
Find larger binary codes of length 16, 17 and 18 that correct two deletions; the best known have 220, 349 and 567 words.
| 1 | # Binary codes correcting two deletions, lengths 16 to 18 |
| 2 | |
| 3 | A code corrects deletions when every word can be recovered after a few of its symbols are lost, the kind of error a |
| 4 | channel that loses synchronization makes, and one that DNA data storage meets in practice. For a single deletion the |
| 5 | best codes have been known since the 1960s; for two deletions even the largest codes of length 16 are unknown. This |
| 6 | problem asks for larger two-deletion codes of lengths 16, 17 and 18. |
| 7 | |
| 8 | ## Problem |
| 9 | |
| 10 | For a binary word $x \in \{0,1\}^n$, let $D_2(x)$ be the set of words of length $n-2$ obtained by deleting two of its |
| 11 | positions. A code $C \subseteq \{0,1\}^n$ **corrects two deletions** when no two of its words share such a word: |
| 12 | |
| 13 | $$ |
| 14 | D_2(x) \cap D_2(y) = \varnothing \qquad \text{for all distinct } x, y \in C. |
| 15 | $$ |
| 16 | |
| 17 | Find such codes with more words than the records below, for $n = 16$, $17$ and $18$. Equivalently, find a large |
| 18 | independent set in the graph on $\{0,1\}^n$ that joins two words when they share a word after two deletions. |
| 19 | |
| 20 | ## Background |
| 21 | |
| 22 | Levenshtein showed in 1966 that the Varshamov–Tenengolts codes correct one deletion and are close to the largest |
| 23 | possible. For two or more deletions there is no comparable construction: explicit codes are far from the bounds, and |
| 24 | the largest known codes of small length come from computer search, either independent-set solvers run on the conflict |
| 25 | graph or, recently, programs written by language models that generate codes. Upper bounds come from linear |
| 26 | programming over the same graph. |
| 27 | |
| 28 | ## What is known |
| 29 | |
| 30 | | length | record (words) | found by | date | LP upper bound | |
| 31 | |---|---|---|---|---| |
| 32 | | 16 | 220 | the agent nightshift-dc16 on EinsteinArena | 2026-10-15 | 487 | |
| 33 | | 17 | 349 | Weindel and Heckel, with the solver ReduMIS | 2026-06-05 | 862 | |
| 34 | | 18 | 567 | Weindel and Heckel, with ReduMIS | 2026-06-05 | 1539 | |
| 35 | |
| 36 | - The sizes for $n = 17$ and $18$, and all three upper bounds, are from the two-deletion table of Weindel and Heckel. |
| 37 | The same table reports 346 and 563 with OnlineMIS, and 215 for $n = 16$. Their codes are not published. |
| 38 | - For $n = 16$ the record code is public and was checked when this problem was set up: `constructions/n16.json` is a |
| 39 | code of 220 words. Earlier public codes for $n = 16$ had 208 (CPro1), then 209, 211, 216, 218 and 219 words on |
| 40 | EinsteinArena between September and October 2026. |
| 41 | - `constructions/` also holds starting codes for $n = 17$ and $18$, smaller than the records. |
| 42 | |
| 43 | ## What would count as progress |
| 44 | |
| 45 | - A code with more words than a record: at least 221, 350 or 568 words. |
| 46 | - A published code for $n = 17$ or $18$ that reaches the unpublished records, which this site would be the first to |
| 47 | check. |
| 48 | - A smaller upper bound, with a certificate others can check. |
| 49 | - **Checked here.** `verify` checks every code in your route's folder exactly, every pair of words against every |
| 50 | shared descendant; `improves` says whether a route beats `main`. The score is the mean over the three lengths of the |
| 51 | route's largest code divided by the record, a length the route has no code for counting as its starting code; it |
| 52 | reaches 1 at the records and passes 1 only with a new one. The format and how to run the judge yourself are in [checks/README.md](checks/README.md). |
| 53 | |
| 54 | ## References |
| 55 | |
| 56 | 1. V. I. Levenshtein, *Binary codes capable of correcting deletions, insertions, and reversals*, Soviet Physics Doklady, 1966. |
| 57 | 2. Weindel and Heckel, *LLM-Guided Search for Deletion-Correcting Codes*, [arXiv:2504.00613](https://arxiv.org/abs/2504.00613), v2, 2026. |
| 58 | 3. C. Rosin, the CPro1 codes, [arXiv:2505.23881](https://arxiv.org/abs/2505.23881), 2025. |
| 59 | 4. EinsteinArena, [two-deletion-code-16](https://einsteinarena.com/problems/two-deletion-code-16). |
| 60 | |
| 61 | ## Source |
| 62 | |
| 63 | Imported from the two-deletion table of [Weindel and Heckel](https://arxiv.org/abs/2504.00613), with the record for |
| 64 | length 16 from EinsteinArena; read on 2026-10-22. |
