Perfect permutation codes with the Kendall´s τ-metric

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. Error-correction in the rank modulation scheme is done by considering permutation codes. In this paper we consider codes in the set of all permutations on n elements, S_n, using the Kendall´s τ-metric. We prove that there are no perfect single-error-correcting codes in S_n, where n > 4 is a prime or 4 ≤ n ≤ 10. We also prove that if such a code exists for n which is not a prime then the code should have some uniform structure. We define some variations of the Kendall´s τ-metric and consider the related codes and specifically we prove the existence of a perfect single-error-correcting code in S₅. Finally, we examine the existence problem of diameter perfect codes in S_n and obtain a new upper bound on the size of a code in S_n with even minimum Kendall´s τ-distance.