Upper bounds on the size of permutation codes with a Hamming distance of five

Abstract

In this paper, we study the largest size A(n, d) of permutation codes of length n, i.e., subsets of the set Sn of all permutations on n letters with the minimum distance at least d under the Hamming metric. In Abdollahi et al. (Cryptogr. Commun. 15, 891–903 2023) we have developed a method using the representation theory of symmetric groups to find upper bounds on the size of permutation codes in Sn with the minimum distance of d under the Kendall τ-metric. The latter method is used for the permutation codes under the metric induced by Cayley graphs of Sn. Since the metric induced by any Cayley graph of Sn is not equivalent to the Hamming metric, we can not use the method for the Hamming metric. In this paper we find a trick by which we can again use the method to find upper bounds for A(n,2t+1). We present three practical results that prove the non-existence of perfect 2-error-correcting codes in Sn under the Hamming metric for numerous values of n. Specifically, we prove that 91 and 907 are the only values for n≤1000 for which Sn may contain a perfect 2-error-correcting code under the Hamming metric. Additionally, we prove that for any integer n such that n2-n+2 is divisible by a prime exceeding n-⌊n7⌋, (Formula presented.) The result improves the known upper bounds of A(n, 5) for all integers n≥35 such that n2-n+2 is divisible by a prime exceeding n-⌊n7⌋. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2025.