Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 21 min ago
PreprintarXiv licencearXiv

Polynomially larger deletion codes by linear hashing of substring counts

  • Eyal En Gad
Open at sourcePDFDOICite

Abstract

We reduce the leading redundancy coefficient for binary codes correcting any fixed number t≥2 of deletions from 2t to 2t−1. This is the first improvement to that coefficient since Levenshtein's 1965 bound. More generally, over every fixed alphabet of size q≥2, codes of length n correcting any combination of at most t insertions, deletions and substitutions exist with redundancy (2t−1)logq n+Ot(logqlogq n). For two deletions, the upper-bound coefficient drops from $4$ to $3$, halving the gap to the lower-bound coefficient $2$. The leading coefficient 2t−1 also holds for t bounded substring edits, where both the removed and inserted strings have bounded length. The proof combines random binary linear hashing of substring counts with a two-colouring argument. A linear dependence among differences of substring-count vectors forces their local changes to overlap, and this overlap lowers the redundancy coefficient from 2t to 2t−1. The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.

Related

  1. Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
    Zuo Ye, Gennian Ge
    arXivPreprintCC BY 4.0Full textGeneral mathematicsarXiv
  2. List Decoding, Linear Hashing, and Furstenberg over 𝔽q
    Vinayak M. Kumar, Geoffrey Mon
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Two-sided linear hashing and quadratic density bounds for smooth lattice coverings
    Ben Lund
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Linear Hashing Is Poissonesque
    Vinayak M. Kumar
    arXivPreprintCC BY-NC-ND 4.0Full textProbabilityarXiv
  5. The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients
    Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis
    arXivPreprintCC0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{gad2026polynomially,
  title = {{Polynomially larger deletion codes by linear hashing of substring counts}},
  author = {Eyal En Gad},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2609.19493},
  eprint = {2609.19493},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.19493},
}
RIS
TY  - UNPB
TI  - Polynomially larger deletion codes by linear hashing of substring counts
AU  - Eyal En Gad
PY  - 2026
DA  - 2026/10/18
PB  - arXiv
DO  - 10.48550/arxiv.2609.19493
UR  - https://arxiv.org/abs/2609.19493
AB  - We reduce the leading redundancy coefficient for binary codes correcting any fixed number t≥2 of deletions from 2t to 2t−1. This is the first improvement to that coefficient since Levenshtein's 1965 bound. More generally, over every fixed alphabet of size q≥2, codes of length n correcting any combination of at most t insertions, deletions and substitutions exist with redundancy (2t−1)log_q n+O_t(log_qlog_q n). For two deletions, the upper-bound coefficient drops from $4$ to $3$, halving the gap to the lower-bound coefficient $2$. The leading coefficient 2t−1 also holds for t bounded substring edits, where both the removed and inserted strings have bounded length. The proof combines random binary linear hashing of substring counts with a two-colouring argument. A linear dependence among differences of substring-count vectors forces their local changes to overlap, and this overlap lowers the redundancy coefficient from 2t to 2t−1. The result provides an edit-distance analogue of Varshamov's 1957 bound in the Hamming metric, both in the leading redundancy coefficient and in the role of linear independence in the proof.
ER  -