CS Paper Radar

On Sequence Reconstruction Problem for q-ary Deletion Channels

Xiang Wang, Han Li, Fang-Wei Fu

cs.IT ·submitted 2026-09-15 08:33 UTC · v1
theory

Abstract

The sequence reconstruction problem for $q$-ary deletion channels, introduced by Levenshtein in 2001, concerns the minimum number of channels required to uniquely recover a transmitted sequence when each channel introduces exactly $t$ deletions. Combinatorially, it is equivalent to determining $N_q(n,d,t)$, the maximum intersection size of two $t$-deletion balls with centers at Levenshtein distance at least $d$, for $q$-ary sequences of length $n$ over the alphabet \(Σ_q=\{0,1,\dots,q-1\}\). Levenshtein solved the uncoded case $N_q(n,1,t)$ for all $n\ge t$; subsequently, Gabrys and Yaakobi determined $N_2(n,2,t)$, and Wang et al. extended the result to $N_3(n,2,t)$. In this paper, we study the problem for \(q\)-ary sequences under minimum Levenshtein distance \(d=2\) with channels that introduce exactly \(t\) deletions. We determine the exact value of \(N_q(n,2,t)\) for all \(t\ge 2, q\geq 4\), and for sufficiently large \(n\), and construct explicit pairs of sequences attaining the maximum intersection. Furthermore, for each $q\ge3$, we characterize all extremal sequence pairs. In particular, if the intersection size matches the first two terms of \(N_q(n,2,t)\), then the two center sequences must contain, at the same positions, length-5 blocks of the forms \((a,b,c,a,b)\) and \((b,a,c,b,a)\) for some distinct \(a,b,c\inΣ_q\); for \(t\ge q+2\), the exact maximum \(N_q(n,2,t)\) is attained precisely by \(2q!\) unordered pairs of sequences with a specific block structure. Asymptotically, we prove that for \(q\ge 4\) and \(t\ge 2\), \[ N_q(n,2,t)=\frac{6}{(t-2)!}n^{t-2}-\frac{3t+13}{(t-3)!}n^{t-3}+\frac{3t^2+25t+64}{4(t-4)!}n^{t-4}+O(n^{t-5}). \] Moreover, \(N_q(n,2,t)\) and \(N_{q-1}(n,2,t)\) share their first \(q-1\) terms, and for \(t\ge q\) the coefficient of \(n^{t-q}\) in their difference is \(\frac{6t-6q+5}{(t-q)!}\).

Closest papers

Nearest neighbours by meaning across the whole index.

Coding for Multiple Reverse-Complement and Palindromic Duplications

cs.IT ·2026-09-01 ·Aryeh Lev Zabokritskiy
theory similarity 0.64
Abstract · 33 pages

Reverse-complement (RC) and palindromic (PAL) duplications insert a reversed copy of a length-$k$ block immediately after the block; an RC duplication also applies a fixed involutive complement to the inserted symbols. We study $q$-ary codes correcting $t$ such operations applied in sequence, where later operations may copy inserted symbols. For fixed $q\geq2$ and $k,t\geq1$, we prove that every length-$n$ code $C$ for either channel has redundancy $n-\log_q|C|\geq t\log_q n-O_{q,k,t}(1)$; for fixed $q,k$ and $1\leq t=t(n)=o(n)$ the lower bound is $t\log_q(n/t)-O_{q,k}(t)$. For fixed $k$, known codes for one length-$k$ insertion burst attain redundancy $\log_q n+O_{q,k}(1)$ for a single duplication of either type. For every even $k$ and any involutive complement, we show that the two channels are equivalent for every number of errors: the bijection complementing every other coordinate turns each RC duplication into a PAL duplication. This bijection therefore converts any $t$-error-correcting RC code into a PAL code of the same size, and conversely, with linear-time transfer of encoders and decoders. For every even $k$, we also determine the maximum number of descendants of one word under exactly two errors; by the bijection, it is the same for both channels. For fixed even $k$, a direct count using this maximum proves the existence of two-error-correcting PAL and RC codes with redundancy at most $4\log_q n+O_{q,k}(1)$. A known existence bound for two deletion bursts transfers to insertions with the same leading term as ours and a larger additive constant. For two errors, the converse gives $2\log_q n-O_{q,k}(1)$, a factor of two below these existence bounds.

0.31

Lower Bounds for all List-Decodable Deletion Codes

cs.IT cs.DMmath.CO ·2026-09-22 ·Andrew D. Lin
theory similarity 0.63
Abstract

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover the codeword. In this paper, we consider $t$-list decodable deletion codes, where after $k$ bits of a codeword are deleted, we can identify a list of size at most $t$ such that the original codeword lies in the list. We prove a lower bound of $Ω_k(2^n t\log^{1/t}n/n^{k+k/t})$ on the optimal size of a $t$-list decodable $k$-deletion code, giving a $\sqrt{\log n}$ improvement over the previously best known bounds for $2$-list decodable $2$-deletion codes [GH21] and providing the first nontrivial lower bound when $t>2$ or $k>2$. Our bound holds for all $t\leq n^k$, showing that $t=Ω(\log n)-$list decodable deletion codes have optimal size $Θ_k(2^n t/n^k)$, asymptotically matching the known upper bound. We also prove upper bounds on the number of common subsequences and common supersequences of a given length for any two binary strings.

0.06

Polynomially larger deletion codes by linear hashing of substring counts

cs.IT math.CO ·2026-09-16 ·Eyal En Gad
highly cited similarity 0.63
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.52

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.62
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

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.61
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Improving the Trifference Lower Bound via Non-Perfect Hashing

cs.IT ·2026-11-08 ·Chen Yuan, Ruiqi Zhu
theory similarity 0.61
Abstract · 18 pages

We strictly improve the Körner-Marton lower bound $\frac14\log \frac{9}{5}$ on the asymptotic rate of trifferent codes. We obtain this improvement by constructing non-perfect $(9,3)$-hash codes with rate above $\log(9/5)$ and then applying the Tetra-code construction, which gives $R_3\ge\frac14R_{9,3}$. More generally, for every $q\ge4$, we prove $R_{q,3}>B_{q,3}+\frac1{250000}$. We also extend the method to $(p,2,3)$-list recovery. For every $q\ge4$ and $0\le p<\frac{q-2}{12(q-1)}$, we prove $R_q^{\mathrm{LR}}(p)>B_q^{\mathrm{LR}}(p)$. Here $B_{q,3}$ and $B_q^{\mathrm{LR}}(p)$ denote the respective probabilistic lower bounds. For every fixed $0\le p<1/18$, the rate improvement is bounded below by a positive constant independent of $q\ge4$. For every fixed $0\le p<1/12$, we also obtain a positive rate improvement independent of $q$ for all sufficiently large $q$.

0.21

Asymptotic Bounds for Codes in Toroidal Distance

cs.IT ·2026-11-19 ·Pengjie Zhong, Jinquan Luo
theory similarity 0.60
Abstract

The toroidal distance naturally describes the geometry of codes over \(\mathbb Z_q\), where distances are measured modulo \(q\). In this paper, we study asymptotic bounds for codes in \(\mathbb Z_q^n\) under the toroidal metric. We first derive an explicit asymptotic lower bound from the classical Gilbert--Varshamov bounds for the Hamming and Lee metrics, which serves as a baseline for comparison. We then develop a saddle-point approach for the toroidal metric, which yields an asymptotic Gilbert--Varshamov lower bound and an asymptotic Hamming-type upper bound. For \(3\mid q\), we embed ternary Hamming codes into \(\mathbb Z_q^n\) and obtain another asymptotic lower bound for the toroidal metric. In addition, we derive an asymptotic lower bound for Maximum Toroidal Distance (MTD) codes. We compare these lower bounds with the baseline and prove that they are nontrivial in the corresponding parameter ranges. Finally, we compare the asymptotic bounds numerically.

0.15

Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-Ratios

cs.IT ·2026-11-16 ·Runqing Qiu, Shixin Zhu, Yang Li, San Ling
similarity 0.60
Abstract · 16 pages

Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an ${[n,2]}_q$ code has minimum insdel distance at most $2n-4$. The smallest field size of two-dimensional Reed--Solomon (RS) codes attaining this bound is $Θ(n^3)$. Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for $n\ge6$ every ${[n,2]}_q$ code attaining the half-Singleton bound is an RS code, and hence $q\ge\binom{n}{3}+2$. Secondly, we show that an ordering-free evaluation set with $n\ge6$ points in $\mathbb{F}_q$ satisfies $n<q^{1/3}+2$, and that it has at most $r+1$ points if $q=r^3$ for a prime power $r\ge3$. Finally, by using cross-ratios, we construct an ordering-free evaluation set with $r+1$ points in $\mathbb{F}_{r^3}$ for every prime power $r$. Hence, the bound $r+1$ is attained for $r\ge3$. Moreover, the constructed set is even robust against permutations combined with insdel errors.

0.14