View PDF HTML (experimental)

Abstract:We study the problem of correcting pairwise disjoint adjacent transpositions (or swaps) in $q$-ary strings. Equivalently, the model we assume is the radius-one instance of the so-called $\ell_\infty$-limited permutation channel. We first study the relevant combinatorial properties of the appropriately defined transposition distance, including center-specific and average ball sizes. We then derive two lower bounds and one upper bound on the asymptotic rates of optimal codes correcting $t=\tau n$ transpositions. The first achievability result is a generalized Gilbert--Varshamov bound, while the second follows from a construction of codes correcting all possible patterns of adjacent transpositions and therefore represents a lower bound on the zero-error capacity of this model. This construction improves the classical general-alphabet construction for $3\leqslant q\leqslant 8$ as well as the recent bounds for $q=4,5$. The upper bound is obtained by a packing argument adjusted to the run-structure of a given code. To the best of our knowledge, these are the first nonconstant, $\tau$-dependent lower and upper bounds developed for the pairwise disjoint $q$-ary model throughout the linear regime. We also derive asymptotic bounds on the cardinality of optimal codes correcting $t=\textrm{const}$ pairwise disjoint adjacent transpositions.

Submission history

From: Mladen Kovačević [view email]
[v1] Mon, 8 Sep 2025 13:46:50 UTC (31 KB)
[v2] Sat, 3 Jan 2026 10:17:24 UTC (35 KB)
[v3] Fri, 14 Aug 2026 18:11:08 UTC (53 KB)