Extinction Depth and q-ary Error-Correcting Codes for the Limited Permutation Channel

In the radius-one limited permutation channel, errors consist of disjoint adjacent transpositions.

A correcting code must separate distinct codewords: their error balls may not contain a common received word.

Hamming distance does not ensure this, because disjoint swaps can make words differing in many positions confusable.

For block-concatenation codes, earlier work tested each possible collision only through the longer initial block.

This sufficient condition is not necessary: we exhibit a valid ternary block set that it does not certify.

We introduce extinction depth, which tracks unresolved first-block pairs through later block extensions, and prove that their extinction at one common finite horizon certifies correction at every length.

The criterion gives explicit $q=3$ and $q=5$ block sets with rates above $0.6777475$ and $0.6694926$.

No block-set-independent depth bound exists: we give an exact linear family, verify a quadratic formula for every $3\leq k\leq 60$, and derive a polynomial-time finite-graph test.

For growing alphabets, the normalized correction loss lies between $\ln\varphi$ and $\ln(1.82560995)$, while explicit finite-length covers improve finite-alphabet upper bounds.

We develop a parallel directed-extinction theory for detection, including an all-length block criterion, a set unresolved by the earlier test, and exact corridor depth $4k$.

Stable type lifting yields optimal first-order loss $\sqrt{2}$, and weak-zigzag codes improve the $q=3,4$ lower bounds.

Finally, window restriction, cancellation, and a bounded pending-input frontier extend the criterion and its finite-state verification to every fixed displacement radius $r$.