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