CS Paper Radar

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

Valery, Grishin, Aryeh Lev Zabokritskiy

cs.IT ·submitted 2026-09-29 11:45 UTC · v2

Abstract

We construct systematic $q$-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length $n\ge2$, our first construction has length $n+3$ over an alphabet of size $q=2^s<2^{32}n^7$ for some integer $s$, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size $O(n^4)$, leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size $q<(n+2)^4$. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for $n\ge2$.

Comment
52 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Order-Optimal Systematic Permutation Codes for Correcting t Deletions

cs.IT ·2026-09-29 ·Bolin Wu, Quan D. Bui, Kai Niu, Van Khu Vu, Shuche Wang
similarity 0.74
Abstract

This paper investigates the construction of full-systematic permutation codes capable of correcting multiple deletions under two complementary models, namely symbol-invariant deletions (SIDs), where surviving symbol values are preserved, and permutation-invariant deletions (PIDs), where the surviving sequence is standardized to a permutation. For any fixed integer $t \ge 1$ and all sufficiently large message lengths $n$, our proposed encoders map any message permutation of length $n$ to a codeword by inserting distinct redundancy symbols while strictly preserving the sequence order of the original message symbols. The proposed constructions correct up to $t$ deletions using $7t-1$ redundancy markers for PIDs and $4t$ redundancy markers for SIDs, achieving redundancies of $(7t-1)\log n + O_t(1)$ bits and $4t\log n + O_t(1)$ bits, respectively. Both code families are uniformly constructible, encodable, and decodable in $n^{O(t)}$ time. The underlying framework stores an inner deletion-correcting syndrome in the relative positions of redundancy markers via an algebraic outer code based on integer moments and residual graph coloring. We further extend this framework to fixed-composition and strictly $λ$-regular multipermutations, proving that the PID and SID channels coincide whenever the common multiplicity satisfies $λ> t$.

0.39

The Ternary and Quaternary Cases of the $\{2,4\}$-Distance Code Conjecture

cs.IT math.CO ·2026-10-22 ·Yen-Chi Roger Lin, Valjakas Djaljapayan, Wei-Hsuan Yu
theory similarity 0.70
Abstract

For an integer $q\ge2$, let $A_q(n,\{2,4\})$ be the largest cardinality of an unrestricted $q$-ary code of length $n$ in which any two distinct words have Hamming distance $2$ or $4$. We prove that \[ A_q(n,\{2,4\})=1+\binom n2 \qquad(q\in\{3,4\},\ n\ge6), \] thereby settling the two remaining alphabet sizes in the conjecture of Boyvalenkov, Delchev, Zinoviev, and Zinoviev; the binary case was settled previously. The quaternary result implies the ternary result by alphabet inclusion. For $n\ge16$, the quaternary upper bound is proved combinatorially. After normalizing one word to zero, the weight-four supports form a $2$-intersecting family; exact support intersections force symbol synchronization and restrict support multiplicities. We combine the nontrivial intersection theorem with matching arguments and a three-coordinate projection lemma. The finite lengths $6\le n\le13$ are handled by a complete Hamming-isometry reduction to exact clique decisions, and $n=14,15$ by a smaller exact weighted-clique relaxation. All finite decisions are reproduced by two standalone integer-only C++17 verifiers provided as supplementary source files.

0.20

Polynomially larger deletion codes by linear hashing of substring counts

cs.IT math.CO ·2026-09-16 ·Eyal En Gad
highly cited similarity 0.69
Abstract · Extended to arbitrary fixed alphabets, mixed edits, and bounded substring edits; simplified proof using binary linear hashing

We reduce the leading redundancy coefficient for binary codes correcting any fixed number $t\ge2$ 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\ge2$, 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_q\log_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.

0.51

Concatenation Locality under Successive Adjacent Transpositions

cs.IT ·2026-11-01 ·Adelin Ataba, Aryeh Lev Zabokritskiy
theory similarity 0.68
Abstract · 32 pages

We study codes correcting up to $t\geq1$ successive adjacent transpositions, using block concatenation to support blockwise encoding and decoding. A fixed set $P$ of words of length $b$ over a $q$-symbol alphabet generates, for every $m$, the length-$mb$ code of all concatenations of $m$ words from $P$. For our explicit constructions, the prepared encoder and decoder depend only on the block parameters and are reused at every concatenation length. We first prove that correction at every concatenation length is certified by a single finite test at $2t+1$ blocks, and this test is tight over a $q$-symbol alphabet exactly when $\binom q2\geq2t$. For binary words and $b\geq2t+1$, we give an explicit construction with total redundancy at most $mt\log_2 b+O_t(m)$, matching the optimal per-block redundancy $t\log_2 b+O_t(1)$ among block sets correcting at every concatenation length. Among all binary $t$-correcting codes of length $mb$, the optimal total redundancy is $t\log_2(mb)+O_t(1)$. Using all concatenations of one block set makes our total redundancy grow linearly in $m$ and buys independent block encoding, with one encoder and decoder at every length. The construction encodes and decodes in time linear in $mb$ for fixed $b,t$, and recovers the $j$-th source block from the first $jb$ received symbols. We also prove that, whenever the length-$mb$ code corrects $t$ transpositions, the $j$-th source block is determined within $2tb$ received symbols beyond position $jb$, and that explicit binary block sets with rates tending to one as $b$ grows with $t$ fixed attain this bound in the worst case. Finally, we prove that every ordinary correcting code contains a constant fraction of its words whose arbitrary concatenations retain correction, for fixed $q,t$.

0.28

Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes

cs.IT ·2026-10-05 ·Zuo Ye, Gennian Ge
similarity 0.67
Abstract · 35 pages

A $k$-substring edit in a sequence first deletes a substring of length at most $k$, and then inserts a sequence of length at most $k$ at the same position. A code that can correct a $k$-substring edit is called a $k$-substring edit code. In this paper, we develop a new localization method and use it to construct a $q$-ary $k$-substring edit correcting code with $\log n+8\log\log n+o(\log\log n)$ bits of redundancy for any fixed $q\ge2$ and $k\ge1$, where $n$ is the code length. For the binary alphabet, this improves upon the redundancy $\log n+16k\log\log n+o(\log\log n)$ obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy $\log n+O_{q,k}(1)$, which is optimal up to an additive constant. As corollaries, for all fixed $q\ge2$ and $1\le t\le T$, we obtain $q$-ary $(\le t)$-burst-deletion correcting codes and $(t,T)$-localized deletion correcting codes with redundancies $\log n+O_{q,t}(1)$ and $\log n+O_{q,T}(1)$, respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For $(\le t)$-burst-deletion correction with $t\ge2$, such redundancy had previously been achieved only for $q=t=2$ by Levenshtein in 1967.

0.17

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound

cs.IT ·2026-11-02 ·Ryan Gabrys, Shubhransh Singhvi, Eitan Yaakobi
similarity 0.67
Abstract

We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at most $t$ insertions, deletions, and substitutions in total, with redundancy at most $2t\log_2 n+O_t(1)$. All algorithms run in polynomial time in $n$ for fixed $t$, and decoding recovers the original information message. This realizes the classical counting guarantee algorithmically without enumerating the exponentially large space of binary words.

0.41

Nonlinear fixed-distance codes via real lifts of moment configurations

cs.IT cs.DMmath.CO ·2026-10-14 ·Sergey Yekhanin
theory similarity 0.67
Abstract

Let $A_q(n,d)$ denote the largest size of a code of length $n$ and minimum Hamming distance $d$ over an alphabet of $q$ symbols. For fixed $q\ge2$ and $d\ge4$ we construct codes with redundancy $n-\log_q A_q(n,d)\le(d-3)\log_q n+O(\sqrt{\log n})$ for all large $n$. No algebraic structure is imposed on the alphabet, and the codes are not linear. For $d=4$ and $d=5$ the coefficient of $\log_q n$ matches the Hamming bound, so the redundancy is determined up to lower-order terms. At distance four the codes are provably better than every linear code: by the polynomial-method bound for cap sets, $\mathbb{F}_q$-linear codes with $q>2$ require a strictly larger coefficient in front of $\log_q n$. The construction imposes moment checksums over an auxiliary finite field, as BCH codes do, but one fewer than the distance would normally require. The affine-line theorem from prior work describes the dependencies left by these checks. We exclude them by placing the code positions inside a specially structured subset of the field, built from Behrend's sphere construction with the help of algebraic number theory.

0.44

The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths

cs.IT ·2026-09-16 ·Weiguo Gao, Zhi Shan
theory similarity 0.66
Abstract · 33 pages, 4 figures, 1 table

We prove the \(3/4\) conjecture for \(q\)-ary fix-free codes with at most three distinct codeword lengths, for every integer \(q\geq2\). Every prescribed length distribution with Kraft sum at most \(3/4\) is realized by a deterministic construction. We introduce a matrix approach based on an exact identity for the overlap between forbidden prefix extensions and suffix residuals. Natural numerical order fixes the shortest layer, and the remaining selection problem is expressed through row and column counts. A fixed-cardinality interpolation theorem supplies feasible sets of every intermediate cardinality between nested endpoints, provided their differences satisfy one-sided uniqueness and either acyclicity or integral slack. Reverse-order selection handles the uniform cases directly; in the remaining cases, layer completion and aligned groups provide endpoints for interpolation. Together, these methods extend the binary three-length result to arbitrary finite alphabets and give a deterministic procedure for constructing the code.

0.28