Logarithmically larger deletion codes of all distances

Noga Alon, Gabriela Bourla, Ben Graham, Xiaoyu He, Noah Kravitz

Introduction

In classical coding theory, the primary focus is often on Hamming distance, which accounts for "bit flip" errors. However, synchronization errors—specifically deletions and insertions—present a significantly more complex challenge. When a bit is deleted, the receiver loses track of the relative positions of all subsequent bits, leading to a total loss of synchronization.

A $k$-deletion code is defined as a set of binary strings of length $n$ where no two distinct strings share a common subsequence of length $n-k$. In 1965, Vladimir Levenshtein established the fundamental bounds for the maximum size of such a code, $D(n, k)$:

$$\Omega_k\left(\frac{2^n}{n^{2k}}\right) \leq D(n, k) \leq O_k\left(\frac{2^n}{n^k}\right)$$

While the bounds for $k=1$ are tight, a substantial polynomial gap has persisted for any fixed $k \geq 2$ for nearly six decades. This research provides the first asymptotic improvement to the lower bound in sixty years, demonstrating that $k$-deletion codes can be larger than previously believed by a logarithmic factor.

The Deletion Graph Framework

The authors approach the problem through the lens of extremal graph theory. They define a deletion graph $\Gamma_{n,k,\alpha}$ where:

  • Vertices represent all possible words of length $n$ over an alphabet of size $\alpha$.
  • Edges connect any two words that share a common subsequence of length at least $n-k$.

In this framework, finding a $k$-deletion code is equivalent to finding a maximum independent set in the graph—a collection of vertices where no two are connected by an edge.

Methodology: Local Sparsity and Pseudorandomness

The core technical innovation lies in proving that the deletion graph is locally sparse. In graph theory, if a graph has a relatively low number of triangles (cycles of length three) compared to its degree, it is guaranteed to contain a larger independent set than a dense graph. To quantify this, the authors utilized the Ajtai-Komlós-Szemerédi lemma, which provides a mechanism to translate triangle counts into lower bounds for independent sets.

Applying this to deletion codes required overcoming significant hurdles. Unlike the graphs associated with standard error-correcting codes, deletion graphs are not "regular" (vertices have varying degrees) and lack the symmetry typical of Hamming-space problems. To resolve this, the authors focused on "pseudorandom" words—strings that lack frequent internal repeating patterns (specifically, $\lambda$-nonrepeating strings). By proving that the vast majority of strings in the graph behave like these pseudorandom words, they were able to bound the behavior of the entire graph structure.

Combinatorial Insights: LCS and SCS Multiplicity

A significant secondary contribution of the paper involves the "multiplicity" of Longest Common Subsequences (LCS) and Shortest Common Supersequences (SCS). The authors investigated how many distinct LCSs or SCSs can exist between two words. They established a new, tight upper bound:

$$m_{LCS}(u, v) \leq m_{SCS}(u, v) \leq \binom{a+b}{a}$$

where $a$ and $b$ are the number of deletions and insertions required to transform one word into the other. This result is not only crucial for the main proof but is also of independent interest to fields such as bioinformatics and string algorithms.

Key Results

The research establishes that for $n \geq k \geq 2$, the maximum size of a $k$-deletion code satisfies:

$$D_\alpha(n, k) \geq \Omega_{\alpha,k}\left(\frac{\alpha^n \log n}{n^{2k}}\right)$$

This result is significant for several reasons:

  1. Asymptotic Improvement: It adds a $\log n$ factor to the lower bound that has stood since Levenshtein’s original 1965 work.
  2. Universality: The improvement is robust, holding for all alphabet sizes $\alpha \geq 2$ and all deletion distances $k \geq 2$.
  3. Tightness: The authors demonstrated that their new bounds on LCS/SCS multiplicity are tight by constructing specific word families that reach the $\binom{2d}{d}$ limit.

Limitations and Future Directions

Despite the theoretical breakthrough, the proof remains nonconstructive. It guarantees the existence of larger codes but does not provide an explicit algorithm for generating codewords or an efficient decoding procedure. Furthermore, while the $\log n$ factor narrows the gap, a large polynomial difference remains between the new lower bound (roughly $1/n^{2k}$) and the known upper bound (roughly $1/n^k$). Closing this remaining gap remains one of the most significant open problems in coding theory. The authors suggest that their findings on LCS/SCS multiplicity may provide the structural foundation needed for future algorithmic developments.

Summary updated

BibTeX
@article{alon2024logarithmically,
  author = {Noga Alon and Gabriela Bourla and Ben Graham and Xiaoyu He and Noah Kravitz},
  title = {{Logarithmically larger deletion codes of all distances}},
  journal = {IEEE Trans. Information Theory},
  year = {2024},
  doi = {10.1109/tit.2023.3304565},
}
Figure