New Upper Bounds on the Size of Permutation Codes under Kendall $τ$-Metric
Preprint
Abstract
We first give two methods based on the representation theory of symmetric groups to study the largest size $P(n,d)$ of permutation codes of length $n$ i.e. subsets of the set $S_n$ all permutations on $\{1,\dots,n\}$ with the minimum distance (at least) $d$ under the Kendall $τ$-metric. The first method is an integer programming problem obtained from the transitive actions of $S_n$. The second method can be applied to refute the existence of perfect codes in $S_n$.\\ Here we reduce the known upper bound $(n-1)!-1$ for $P(n,3)$ to $(n-1)!-\lceil\frac{n}{3}\rceil+2\leq (n-1)!-2$, whenever $n\geq 11$ is any prime number. If $n=6$, $7$, $11$, $13$, $14$, $15$, $17$, the known upper bound for $P(n,3)$ is decreased by $3,3,9,11,1,1,4$, respectively.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- New bounds of permutation codes under Hamming metric and Kendall’s $\tau $ τ -metricDesigns, Codes and Cryptography, 2016
- Bounds on the Size of Permutation Codes With the Kendall $\tau $ -MetricIEEE Transactions on Information Theory, 2015
- Codes in Permutations and Error Correction for Rank ModulationIEEE Transactions on Information Theory, 2010
- Correcting Charge-Constrained Errors in the Rank-Modulation SchemeIEEE Transactions on Information Theory, 2010
- Upper Bounds on Permutation Codes via Linear ProgrammingEuropean Journal of Combinatorics, 1999
- Codes, transforms and the spectrum of the symmetric groupPacific Journal of Mathematics, 1990