Bounds on Codes Correcting Adjacent Transpositions

[2509.06692] Bounds on Codes Correcting Adjacent Transpositions Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Information Theory arXiv:2509.06692 (cs) [Submitted on 8 Sep 2025 ( v1 ), last revised 14 Aug 2026 (this version, v3)] Title: Bounds on Codes Correcting Adjacent Transpositions Authors: Mladen Kovačević , Han Mao Kiah , Keshav Goyal View a PDF of the paper titled Bounds on Codes Correcting Adjacent Transpositions, by Mladen Kova\v{c}evi\'c and 2 other authors 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. Comments: Substantially revised version; proofs and presentation tightened; the zero-error construction in Section 3.2 replaced by an improved construction; new Section 3.3 provides an upper bound Subjects: Information Theory (cs.IT) ; Discrete Mathematics (cs.DM) MSC classes: 94B25, 94B50, 94B65, 68P30, 68R05 Cite as: arXiv:2509.06692 [cs.IT] (or arXiv:2509.06692v3 [cs.IT] for this version) https://doi.org/10.48550/arXiv.2509.06692 Focus to learn more arXiv-issued DOI via DataCite 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) Full-text links: Access Paper: View a PDF of the paper titled Bounds on Codes Correcting Adjacent Transpositions, by Mladen Kova\v{c}evi\'c and 2 other authors View PDF HTML (experimental) TeX Source view license Ancillary-file links: Ancillary files ( details ) : EXPECTED_OUTPUT.txt README.md verify_section32.py Current browse context: cs.IT < prev | next > new | recent | 2025-09 Change to browse by: cs cs.DM math math.IT References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• On neighbor distances and symmetry in group codes#490081
• On the lengths of MDS codes with a two-transitive permutation automorphism group#972228
• Improved Johnson-type Bounds for Insertion-Deletion Codes#615029
• Improved Johnson-type Bounds for Insertion-Deletion Codes#614062
• Rank and classification of $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard codes#973837