Concatenation Locality under Successive Adjacent Transpositions

@misc{ataba2026concatenation,
  title = {{Concatenation Locality under Successive Adjacent Transpositions}},
  author = {Adelin Ataba and Aryeh Lev Zabokritskiy},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.02192},
  eprint = {2611.02192},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.02192},
}

TY  - UNPB
TI  - Concatenation Locality under Successive Adjacent Transpositions
AU  - Adelin Ataba
AU  - Aryeh Lev Zabokritskiy
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.02192
UR  - https://arxiv.org/abs/2611.02192
AB  - We study codes correcting up to t≥1 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≥2t. For binary words and b≥2t+1, we give an explicit construction with total redundancy at most mtlog_2 b+O_t(m), matching the optimal per-block redundancy tlog_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 tlog_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.
ER  -