New upper bounds on the size of permutation codes under Kendall τ-metric

• Published in: Cryptography and communications 2023-09, Vol.15 (5), p.891-903
• Main Authors: Abdollahi, Alireza, Bagherian, Javad, Jafari, Fatemeh, Khatami, Maryam, Parvaresh, Farzad, Sobhani, Reza
• Format: Article
• Language: English
• Subjects: Circuits; Coding and Information Theory; Communications Engineering; Computer Science; Data Structures and Information Theory; Information and Communication; Integer programming; Mathematics of Computing; Networks; Permutations; Upper bounds
• ISSN: 1936-2447; 1936-2455
• DOI: 10.1007/s12095-023-00642-6

We give two methods that are 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 of all permutations on { 1 , ⋯ , 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 . Applying these methods, we reduce the known upper bound ( n - 1 ) ! - 1 for P ( n , 3) to ( n - 1 ) ! - ⌈ n 3 ⌉ + 2 ≤ ( n - 1 ) ! - 2 , whenever n ≥ 11 is prime. 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.