New upper bounds on the size of permutation codes under Kendall \(\tau\)-metric (Q6086190)

The Kendall \(\tau\)-distance plays an important role in understanding the performance of specific codes used in flash memory storage. More precisely, for any two permutations \(\rho\) and \(\pi\), their \(\tau\)-distance is the minimum number of adjacent transpositions needed to write \(\rho \pi^{-1}\) as their product. A permutation code with minimum \(\tau\)-distance \(d\) can correct up to \(\frac{d-1}{2}\) errors caused by charge-constrained errors (occurring in flash memories). In this interesting paper the authors advances significantly current knowledge on these codes, thanks mainly to the following two results: \begin{itemize} \item[2.1] (existence of optimal codes) if \(d\) is such that graphical codes of minimum distance at least \(d\) exist, then those with minimum distance exactly \(d\) do exist. \item[1.1] (bounds on the size of optimal codes with \(\tau\)-distance \(d\) and length \(n\)) For all primes \(p\geq 11\), \[ P( p, 3)\leq (p-1)!-\frac{p}{3}+2\leq (p-1)!-2 \] \end{itemize} Some computational experiments complete the paper.