Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
Abstract
We study codes correcting adversarial insertions and deletions with list size L fixed independently of the block length. We derive new achievable-rate bounds for binary codes and upper bounds over every fixed alphabet of size q≥2, retaining explicit dependence on L. We establish a combinatorial reduction that trades L units of insertion budget for one unit of deletion budget in the decoding guarantee, without changing the code or increasing the list size. Consequently, asymptotic bounds for mixed errors with insertion fraction γ and deletion fraction δ follow from insertion-only lower bounds at γ+Lδ and deletion-only upper bounds at δ+γ/L. For binary unique decoding, we strictly improve Levenshtein's classical asymptotic rate lower bound for every deletion fraction 0<δ<1/2 for which the classical rate expression is nonnegative. At δ=0.1, the lower bound increases from approximately $0.162009$ to $0.180431$, a relative increase of about 11.37%. Our framework also yields insertion and deletion lower bounds for every fixed list size. The existence proofs combine the Lovász local lemma with sampling from words having a specified number of runs, where a run is a maximal block of equal symbols. Generating functions provide refined bounds on the probability that L+1 sampled words share an allowed received word. We also derive a Levenshtein-type upper bound by run counting and, separately, a higher-order Elias bound using intersections and unions of the position sets used to embed L+1 codewords in a common supersequence. The latter recovers Yasunaga's asymptotic unique-decoding bound at L=1 and strictly improves the Haeupler--Shahrasbi--Sudan insertion bound for every fixed L and 0<γ<q−1. Numerical comparisons quantify the gains and remaining gaps.
Related
- A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
- Maximal input entropy for binary two-deletion and two-insertion channels
- Lower Bounds for all List-Decodable Deletion Codes
- Improved Lower Bounds on the Capacity of the Binary Deletion Channel via a Learning Approach to Run-Length Inputs
- Improved Bounds For The Lipschitz Retraction Constant In Classical Banach Spaces
BibTeX
@misc{kiah2026constantlist,
title = {{Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound}},
author = {Han Mao Kiah and Hengjia Wei and Ruixiao Zeng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21395},
eprint = {2609.21395},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21395},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
AU - Han Mao Kiah
AU - Hengjia Wei
AU - Ruixiao Zeng
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21395
UR - https://arxiv.org/abs/2609.21395
AB - We study codes correcting adversarial insertions and deletions with list size L fixed independently of the block length. We derive new achievable-rate bounds for binary codes and upper bounds over every fixed alphabet of size q≥2, retaining explicit dependence on L. We establish a combinatorial reduction that trades L units of insertion budget for one unit of deletion budget in the decoding guarantee, without changing the code or increasing the list size. Consequently, asymptotic bounds for mixed errors with insertion fraction γ and deletion fraction δ follow from insertion-only lower bounds at γ+Lδ and deletion-only upper bounds at δ+γ/L. For binary unique decoding, we strictly improve Levenshtein's classical asymptotic rate lower bound for every deletion fraction 0<δ<1/2 for which the classical rate expression is nonnegative. At δ=0.1, the lower bound increases from approximately $0.162009$ to $0.180431$, a relative increase of about 11.37%. Our framework also yields insertion and deletion lower bounds for every fixed list size. The existence proofs combine the Lovász local lemma with sampling from words having a specified number of runs, where a run is a maximal block of equal symbols. Generating functions provide refined bounds on the probability that L+1 sampled words share an allowed received word. We also derive a Levenshtein-type upper bound by run counting and, separately, a higher-order Elias bound using intersections and unions of the position sets used to embed L+1 codewords in a common supersequence. The latter recovers Yasunaga's asymptotic unique-decoding bound at L=1 and strictly improves the Haeupler--Shahrasbi--Sudan insertion bound for every fixed L and 0<γ<q−1. Numerical comparisons quantify the gains and remaining gaps.
ER -