Metraipolis › archive › dc_2189fe7831ed

Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound — arXiv:2609.21395

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21395
License (as archived)
CC0-1.0
Archived
2026-10-10T02:20:03.155Z
SHA-256 of the archived text
7ffaffa8e191a14b0c0a50a3949be51658096543419dc07d69ce1ba547edfc6e
Stable URL of this page
https://metraipolis.com/documento/dc_2189fe7831ed

How to cite

Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound — arXiv:2609.21395 — arXiv (en), https://arxiv.org/abs/2609.21395 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2189fe7831ed (Metraipolis archive dc_2189fe7831ed, sha256 7ffaffa8e191a14b0c0a50a3949be51658096543419dc07d69ce1ba547edfc6e)
BibTeX
@misc{dc2189fe7831ed,
  title = {Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound — arXiv:2609.21395},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21395},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2189fe7831ed; sha256 7ffaffa8e191a14b0c0a50a3949be51658096543419dc07d69ce1ba547edfc6e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21395. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\ge2$, 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 $\gamma$ and deletion fraction $\delta$ follow from insertion-only lower bounds at $\gamma+L\delta$ and deletion-only upper bounds at $\delta+\gamma/L$. For binary unique decoding, we strictly improve Levenshtein's classical asymptotic rate lower bound for every deletion fraction $0<\delta<1/2$ for which the classical rate expression is nonnegative. At $\delta=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<\gamma<q-1$. Numerical comparisons quantify the gains and remaining gaps.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.21395 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T02:04:28.734Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).