Nonexistence of perfect permutation codes under the Kendall $\tau$-metric

Abstract

In the rank modulation scheme for flash memories, permutation codes have been studied. In this paper, we study perfect permutation codes in $S_n$, the set of all permutations on n elements, under the Kendall $\tau$-metric. We answer one open problem proposed by Buzaglo and Etzion. That is, proving the nonexistence of perfect codes in $S_n$, under the Kendall $\tau$-metric, for more values of n. Specifically, we present the polynomial representation of the size of a ball in $S_n$ under the Kendall $\tau$-metric for some radius r, and obtain some sufficient conditions of the nonexistence of perfect permutation codes. Further, we prove that there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for some n and $t=2,3,4,5,~\text {or}~\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

1 Introduction

Flash memory is a non-volatile storage medium that is both electrically programmable and erasable. The rank modulation scheme for flash memories has been proposed in [7]. In this scheme, a permutation corresponds to a relative ranking of all the flash memory cells’ levels. A permutation code is a nonempty subset of $S_n$, where $S_n$ is the set of all the permutations over $\{1,2,\ldots ,n\}$. Permutation codes have been studied under various metrics, such as the $\ell _{\infty }$-metric [9, 13, 15], the Ulam metric [4], and the Kendall $\tau$-metric [1, 8, 12, 16].

In this paper, we will focus on permutation codes under the Kendall $\tau$-metric. The Kendall $\tau$-distance [15] between two permutations $\pi , \sigma \in S_n$ is the minimum number of adjacent transpositions required to obtain the permutation $\sigma$ from $\pi$, where an adjacent transposition is an exchange of two distinct adjacent elements. Permutation codes under the Kendall $\tau$-distance with minimum distance d can correct up to $\left\lfloor \frac{d-1}{2} \right\rfloor$ errors. Let $A_K(n,d)$ be the maximum size of a permutation code in $S_n$ with minimum Kendall $\tau$-distance at least d. The bounds on $A_K(n,d)$ were proposed in [2, 8, 11, 14]. Some t-error-correcting codes in $S_n$ were constructed in [1, 6, 8, 17, 18]. Buzaglo and Etzion [2] proved that there does not exist a perfect single-error-correcting code in $S_n$, where $n>4$ is a prime or $4\le n\le 10$. They further [2] proposed the open problem to prove the nonexistence of perfect codes in $S_n$, under the Kendall $\tau$-metric, for more values of n and/or other distances. In this paper, we give some sufficient conditions of the nonexistence of perfect permutation codes. Moreover, we prove that there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for some n and $t=2,3,4,5,~\text {or}~\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Specially, we prove that there does not exist a perfect two-error-correcting code in $S_n$, where $n+2>6$ is a prime. We also prove that there does not exist a perfect three-error-correcting code in $S_n$, where $n+1>6$ is a prime, or $n^2+2n-6$ has a prime factor $p>n$, or $4\le n\le 33$. We further prove that there does not exist a perfect four-error-correcting code in $S_n$, where $n+1>6$ or $n+2>7$ is a prime, or $n^2+3n-12$ has a prime factor $p>n$, or $5\le n\le 19$. We prove that there does not exist a perfect five-error-correcting code in $S_n$, where $n\ge 16$ or $n+7\ge 12$ is a prime or $n^3+3n^2-6n-28$ has a prime factor $p>n$. For $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$ and $n\ge 5$, we also prove that there does not exist a perfect t-error-correcting code in $S_n$ except for $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

The rest of this paper is organized as follows. In Sect. 2, we will give some basic definitions for the Kendall $\tau$-metric and for perfect permutation codes. In Sect. 3, we determine the size of some balls with radius r in $S_n$ under the Kendall $\tau$-metric. In Sect. 4, we present some sufficient conditions of the nonexistence of perfect permutation codes under the Kendall $\tau$-metric. In Sect. 5, we prove the nonexistence of a perfect t-error-correcting code in $S_n$ for some n and $t=2,3,4,5,~\text {or}~\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Section 6 concludes this paper.

2 Preliminaries

In this section we give some definitions and notations for the Kendall $\tau$-metric and perfect permutation codes. In addition, we summarize some important known facts.

Let [n] denote the set $\{1,2,\ldots ,n\}$. Let $S_n$ be the set of all the permutations over [n]. We denote by $\pi \triangleq [\pi (1),\pi (2),\ldots ,\pi (n)]$ a permutation over [n]. For two permutations $\sigma ,\pi \in S_n$, their multiplication $\pi \circ \sigma$ is denoted by the composition of $\sigma$ on $\pi$, i.e., $\pi \circ \sigma (i)=\sigma (\pi (i))$, for all $i\in [n]$. Under this operation, $S_n$ is a noncommutative group of size $|S_n|=n!$. Denote by $\epsilon _n\triangleq [1,2,\ldots ,n]$ the identity permutation of $S_n$. Let $\pi ^{-1}$ be the inverse element of $\pi$, for any $\pi \in S_n$. For an unordered pair of distinct numbers $i,j\in [n]$, this pair forms an inversion in a permutation $\pi$ if $i<j$ and simultaneously $\pi (i)>\pi (j)$.

Given a permutation $\pi =[\pi (1),\pi (2),\ldots ,\pi (i),\pi (i+1),\ldots \pi (n)]\in S_n$, an adjacent transposition is an exchange of two adjacent elements $\pi (i),\pi (i+1)$, resulting in the permutation $[\pi (1),\pi (2),\ldots ,\pi (i+1),\pi (i),\ldots \pi (n)]$ for some $1\le i\le n-1$. For any two permutations $\sigma ,\pi \in S_n$, the Kendall $\tau$-distance between two permutations $\pi , \sigma$, denoted by $d_K(\pi ,\sigma )$, is the minimum number of adjacent transpositions required to obtain the permutation $\sigma$ from $\pi$. The expression for $d_K(\pi ,\sigma )$ [8] is as follows:

$$\begin{aligned} d_{K}(\sigma ,\pi )=|\{(i,j):\sigma ^{-1}(i)<\sigma ^{-1}(j)\wedge \pi ^{-1}(i)>\pi ^{-1}(j)\}|. \end{aligned}$$

(1)

For $\pi \in S_n$, the Kendall $\tau$-weight of $\pi$, denoted by $w_K(\pi )$, is defined as the Kendall $\tau$-distance between $\pi$ and the identity permutation $\epsilon _n$. Clearly, $w_K(\pi )$ is the number of inversions in the permutation $\pi$. The Kendall $\tau$-metric is right invariant [3] as follows. For any three permutations $\pi ,\sigma ,\beta \in S_n$, we have

$$\begin{aligned} d_K(\pi ,\sigma )=d_K(\pi \circ \beta ,\sigma \circ \beta ). \end{aligned}$$

(2)

Definition 1

For $1\le d \le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, $C\subseteq S_n$ is an (n, d)-permutation code under the Kendall $\tau$-metric, if $d_{K}(\sigma ,\pi )\ge d$ for any two distinct permutations $\pi , \sigma \in C$.

For a permutation $\pi \in S_n$, the Kendall $\tau$-ball of radius r centered at $\pi$, denoted as $B_{K}^{n}(\pi ,r)$, is defined by $B_{K}^n(\pi ,r)\triangleq \{\sigma \in S_n|d_K(\sigma ,\pi )\le r\}$. For a permutation $\pi \in S_n$, the Kendall $\tau$-sphere of radius r centered at $\pi$, denoted as $S_{K}^{n}(\pi ,r)$, is defined by $S_{K}^n(\pi ,r)\triangleq \{\sigma \in S_n|d_K(\sigma ,\pi )= r\}$. The size of a Kendall $\tau$-ball or a $\tau$-sphere of radius r does not depend on the center of the ball or sphere under the Kendall $\tau$-metric. Thus, we denote the size of $B_{K}^{n}(\pi ,r)$ and $S_{K}^{n}(\pi ,r)$ as $B_K^n(r)$ and $S_K^n(r)$, respectively. We denote the largest size of an (n, d)-permutation code under the Kendall $\tau$-metric as $A_K(n,d)$. The sphere-packing bound for permutation codes under the Kendall $\tau$-metric is as follows:

Proposition 1

[8, Theorems 17 and 18]

$$\begin{aligned} A_{K}(n,d)\le \frac{n!}{B_K^n(\left\lfloor \frac{d-1}{2}\right\rfloor )}. \end{aligned}$$

When $d=2r+1$, an $(n,2r+1)$-permutation code C under the Kendall $\tau$-metric is called a perfect permutation code under the Kendall $\tau$-metric if it attains the sphere-packing bound, i.e., $|C|\cdot B_K^n(r)=n!$. That is, the balls with radius r centered at the codewords of C form a partition of $S_n$. A perfect $(n,2r+1)$-permutation code under the Kendall $\tau$-metric is also called a perfect r-error-correcting code under the Kendall $\tau$-metric.

In [2], Buzaglo and Etzion proved that there does not exist a perfect one-error-correcting code under the Kendall $\tau$-metric if $n>4$ is a prime or $4\le n\le 10$. Based on the above definitions and notations, we will prove the nonexistence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for some n and $t=2,3,4,5,~\text {or}~\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$ by using the sphere-packing upper bound and the properties of $B_K^n(r)$ and $S_K^n(r)$ in the following sections.

3 The size of a ball or a sphere with radius r in $S_n$ under the Kendall $\tau$-metric

In this section, we compute the size of a ball or a sphere with radius r in $S_n$ under the Kendall $\tau$-metric and give polynomial representations of $B_K^n(r)$ and $S_K^n(r)$ for some r, respectively. Since $B_K^n(r)$ does not depend on the center of the ball, we consider the ball $B_{K}^n(\epsilon _n,r)$ which is a ball with radius r centered at the identity permutation $\epsilon _n$ and denote by $S_{K}^n(\epsilon _n,r)\triangleq \{\sigma \in S_n|d_K(\sigma ,\epsilon _n)=w_{k}(\sigma )=r\}$ the sphere centered at $\epsilon _n$ and of radius r.

3.1 The size of a sphere of radius r in $S_n$ under the Kendall $\tau$-metric

In order to give the polynomial representation of $S_K^n(r)$, we require some notations and lemmas as follows. For a permutation $\pi =[\pi (1),\pi (2),\ldots ,\pi (n)]\in S_n$, the reverse of $\pi$ is the permutation $\pi ^r\triangleq [\pi (n),\pi (n-1),\ldots ,\pi (2),\pi (1)]$. For all $\pi \in S_n$, we have $w_K(\pi )\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. For convenience, we denote $S_{K}^n(r)=0$ for $r\ge \left( {\begin{array}{c}n\\ 2\end{array}}\right) +1$ or $r<0$.

Lemma 1

[2, Lemma 1] For every $\pi \in S_n$,

$$\begin{aligned} w_K(\pi )+w_K(\pi ^r)=d_{K}(\pi ,\pi ^r)=\left( {\begin{array}{c}n\\ 2\end{array}}\right) . \end{aligned}$$

(3)

By Lemma 1, we can obtain the following lemma.

Lemma 2

For any $0\le i\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$,

$$\begin{aligned} S_{K}^n(i)=S_{K}^n\big (\left( {\begin{array}{c}n\\ 2\end{array}}\right) -i\big ). \end{aligned}$$

(4)

Proof

Let $m=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. We just need to prove that $|S_{K}^n(\epsilon _n,i)|=|S_{K}^n(\epsilon _n,m-i)|$. First we define a function $f: S_{K}^n(\epsilon _n,i)\rightarrow S_{K}^n(\epsilon _n,m-i)$, where $f(\pi )=\pi ^r$ for any $\pi \in S_{K}^n(\epsilon _n,i)$.

If $\pi \in S_{K}^n(\epsilon _n,i)$, then $w_K(\pi )=i$. By (3), $w_K(\pi ^r)=\left( {\begin{array}{c}n\\ 2\end{array}}\right) -i=m-i$. Hence, $f(\pi ) \in S_{K}^n(\epsilon _n,m-i)$. Moreover, we can easily prove that the function f is reasonable and bijection. Thus, $S_{K}^n(i)=S_{K}^n\big (\left( {\begin{array}{c}n\\ 2\end{array}}\right) -i\big ).$ $\square$

Lemma 3

For any $0\le r\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, $S_K^n(r)$ is the number of permutations with r inversions in $S_n$.

Proof

Since $S_K^n(r)=|S_{K}^n(\epsilon _n,r)|=|\{\sigma \in S_n|d_K(\sigma ,\epsilon _n)=w_{k}(\sigma )=r\}|$, by (1), we clearly obtain that $S_K^n(r)$ is the number of permutations with r inversions in $S_n$.$\square$

When $i=0~\text {or}~1$, $S_{K}^n(0)=1$ and $S_{K}^n(1)=n-1$. By Lemma 3, it is known that $S_K^n(r)$ is the Triangle of Mahonian numbers which has some recursive structure in the following lemma. For the recursive structure of Mahonian numbers, we can see the Mahonian numbers sequence A008302 [10].

Lemma 4

[10, FORMULA] For all $1\le n$ and $1\le i\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$,

$$\begin{aligned} S_{K}^n(i)=\sum _{j=\max \{0,i-(n-1)\}}^{i}S_{K}^{n-1}(j). \end{aligned}$$

(5)

Moreover, for all $0\le i \le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, we have

$$\begin{aligned} S_{K}^n(i)=S_{K}^n(i-1)+S_{K}^{n-1}(i)-S_{K}^{n-1}(i-n), \end{aligned}$$

where $S_{K}^n(r)=0$ for $r<0$.

By Lemma 4, we clearly obtain that $S_{K}^{n}(i)$ is an increasing sequence for $0\le i\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Moreover, we give the formula of $S_{K}^n(i)$ by using some $S_{K}^m(j)$ for $m<n$ and $j<i$ in the following lemma.

Lemma 5

For all $4\le n$ and $3\le i\le n-1$, there exists a unique integer t such that $\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) <i\le \left( {\begin{array}{c}t\\ 2\end{array}}\right)$. Then, we have

$$\begin{aligned} S_{K}^n(i)=S_{K}^{t}(\left( {\begin{array}{c}t\\ 2\end{array}}\right) -i)+\sum _{l=t}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j)+\sum _{l=i}^{n-1}\sum _{j=0}^{i-1}S_{K}^{l}(j). \end{aligned}$$

Proof

When $3\le n$ and $2\le i\le n-1$, by (5), we have

$$\begin{aligned} S_{K}^n(i)-S_{K}^{n-1}(i)=\sum _{j=0}^{i-1}S_{K}^{n-1}(j). \end{aligned}$$

(6)

In (6), we set n to $i+1,\ldots ,n$ and obtain $n-i$ equations, respectively. Then by summing all the equations, we have

$$\begin{aligned} S_{K}^n(i)-S_{K}^{i}(i)=\sum _{l=i}^{n-1}\sum _{j=0}^{i-1}S_{K}^{l}(j). \end{aligned}$$

(7)

For j and i such that $0\le j< i\le l\le n-1$, if $S_{K}^l(j)$ and $S_{K}^i(i)$ are known, then by (7) we can compute $S_{K}^n(i)$. In the following, we will compute $S_{K}^i(i)$. When $5\le i$, then $i\le \left( {\begin{array}{c}i-1\\ 2\end{array}}\right)$. Hence, by (5), for $5\le i$, we obtain that

$$\begin{aligned} S_{K}^i(i)-S_{K}^{i-1}(i)=\sum _{j=1}^{i-1}S_{K}^{i-1}(j). \end{aligned}$$

For $5\le i$, we can find an integer t such that $\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) <i\le \left( {\begin{array}{c}t\\ 2\end{array}}\right)$ and $t< i$. We also obtain

$$\begin{aligned} 0\le \left( {\begin{array}{c}t\\ 2\end{array}}\right) -i<i. \end{aligned}$$

(8)

Similarly, when $5\le i$, in (5), we set n to $t+1,\ldots ,i$ and obtain $i-t$ equations, respectively. By summing all the equations, we have

$$\begin{aligned} S_{K}^i(i)-S_{K}^{t}(i)=\sum _{l=t}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j). \end{aligned}$$

(9)

Combining (4), (8), and (9), we have

$$\begin{aligned} S_{K}^i(i)=S_{K}^{t}(\left( {\begin{array}{c}t\\ 2\end{array}}\right) -i)+\sum _{l=t}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j), \end{aligned}$$

(10)

for $5\le i$.

When $i=4$, $S_{K}^{4}(4)=S_{K}^{4}(\left( {\begin{array}{c}4\\ 2\end{array}}\right) -4)=S_{K}^{4}(2)$. When $i=3$, we have $S_{K}^{3}(3)=S_{K}^{3}(\left( {\begin{array}{c}3\\ 2\end{array}}\right) -3)=S_{K}^{3}(0)=1$.

Therefore, if $i\in \{3,4\}$, we choose $t=i$, and the second term of Equation (10) is zero. Thus, in these cases, we still have the representation in (10).

By (7) and (10), we can obtain the expression of $S_{K}^n(i)$ in the above lemma. $\square$

Specifically, we give the polynomial representations of $S_{K}^n(2)$ and $S_{K}^n(3)$ for all $3\le n$ as follows.

Lemma 6

For all $3\le n$, we have

$$\begin{aligned}&S_{K}^n(2)=\frac{n(n-1)}{2}-1,\\&S_{K}^n(3)=\frac{n^3-7n}{6}. \end{aligned}$$

Proof

When $i=2$, by (7), we have

$$\begin{aligned} S_{K}^n(2)-S_{K}^{2}(2)=\sum _{l=2}^{n-1}\sum _{j=0}^{1}S_{K}^{l}(j). \end{aligned}$$

(11)

Since $S_{K}^n(0)=1$, $S_{K}^n(1)=n-1$ and $S_{K}^{2}(2)=0$, by (11), we have

$$\begin{aligned} S_{K}^n(2)=\sum _{l=2}^{n-1}\sum _{j=0}^{1}S_{K}^{l}(j)=\sum _{l=2}^{n-1}l=\frac{n(n-1)}{2}-1. \end{aligned}$$

(12)

Similarly, when $i=3$, by (7), we have

$$\begin{aligned} S_{K}^n(3)-S_{K}^{3}(3)=\sum _{l=3}^{n-1}\sum _{j=0}^{2}S_{K}^{l}(j). \end{aligned}$$

(13)

Since $S_{K}^n(0)=1$, $S_{K}^n(1)=n-1$, $S_{K}^{n}(2)=\frac{n(n-1)}{2}-1$, and $S_{K}^{3}(3)=1$, by (13), we have

$$\begin{aligned} S_{K}^n(3)=S_{K}^{3}(3)+\sum _{l=3}^{n-1}\sum _{j=0}^{2}S_{K}^{l}(j)=1+\sum _{l=3}^{n-1}\frac{l^2+l-2}{2}=\frac{n^3-7n}{6}. \end{aligned}$$

(14)

According to (12) and (14), we can obtain the expressions of $S_{K}^n(2)$ and $S_{K}^n(3)$, respectively. $\square$

Here, we easily obtain $S_{K}^2(0)=S_{K}^2(1)=1$. By Lemma 6, when $n=3$, we have $S_{K}^3(0)=1$, $S_{K}^3(1)=2$, $S_{K}^3(2)=2$, and $S_{K}^3(3)=1$. By Lemma 6 and Lemma 2, we have $S_{K}^{4}(0)=1$, $S_{K}^4(1)=3$, $S_{K}^4(2)=5$, $S_{K}^4(3)=6$, $S_{K}^4(4)=5$, $S_{K}^4(5)=3$, and $S_{K}^4(6)=1$.

If all the $S_{K}^n(j)$ for all n and $j\le i-1$ are known, by Lemma 5, we can compute $S_{K}^n(i)$ for $4\le n$ and $4\le i\le n-1$. Next we present an example to compute $S_{K}^n(i)$ in Lemma 5.

Example 1

When $i=4$, $\left( {\begin{array}{c}3\\ 2\end{array}}\right) <4\le \left( {\begin{array}{c}4\\ 2\end{array}}\right)$. Then, we obtain $t=4$ in Lemma 5. Furthermore, we have

$$\begin{aligned} S_{K}^n(4)=S_{K}^{4}(\left( {\begin{array}{c}4\\ 2\end{array}}\right) -4)+\sum _{l=4}^{3}\sum _{j=i-l}^{i-1}S_{K}^{l}(j)+\sum _{l=4}^{n-1}\sum _{j=0}^{3}S_{K}^{l}(j). \end{aligned}$$

By Lemma 6, we have $S_{K}^{4}(\left( {\begin{array}{c}4\\ 2\end{array}}\right) -4)=S_{K}^{4}(2)=5$. Thus,

$$\begin{aligned} S_{K}^n(4)=5+\sum _{l=4}^{n-1}\big (1+(l-1)+\frac{l(l-1)}{2}-1+\frac{l^3-7l}{6}\big )=\frac{n(n+1)(n^2+n-14)}{24}. \end{aligned}$$

In the following, we also give the formula of $S_{K}^n(i)$ for all $5\le n$ and $n\le i\le \left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$.

Lemma 7

For all $5\le n$ and $n\le i\le \left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$, there exists a unique integer t such that $\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) <i\le \left( {\begin{array}{c}t\\ 2\end{array}}\right)$ and $t\ge 4$. Then, we have

$$\begin{aligned} S_{K}^n(i)=S_{K}^{t}(\left( {\begin{array}{c}t\\ 2\end{array}}\right) -i)+\sum _{l=t}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j)-\sum _{l=n}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j). \end{aligned}$$

(15)

Proof

When $5\le n$ and $n\le i\le \left( {\begin{array}{c}n-1\\ 2\end{array}}\right)$, in (5), we set n to $n+1,\ldots ,i$, respectively. Then we obtain $n-i$ equations and sum all the equations. Thus, we have

$$\begin{aligned} S_{K}^i(i)-S_{K}^{n}(i)=\sum _{l=n}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j). \end{aligned}$$

(16)

By (10) and (16), we have

$$\begin{aligned} S_{K}^n(i)=S_{K}^{t}(\left( {\begin{array}{c}t\\ 2\end{array}}\right) -i)+\sum _{l=t}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j)-\sum _{l=n}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j). \end{aligned}$$

When $i=n$, the third term (i.e., $\sum _{l=n}^{i-1}\sum _{j=i-l}^{i-1}S_{K}^{l}(j)$) is zero. $\square$

Example 2

When $i=5$ and $n=5$, we have $\left( {\begin{array}{c}3\\ 2\end{array}}\right) <5\le \left( {\begin{array}{c}4\\ 2\end{array}}\right)$. Then, we obtain $t=4$ in Lemma 7. Furthermore, by (15), we have

$$\begin{aligned} S_{K}^5(5)=S_{K}^{4}(\left( {\begin{array}{c}4\\ 2\end{array}}\right) -5)+\sum _{l=4}^{4}\sum _{j=5-l}^{4}S_{K}^{l}(j). \end{aligned}$$

Thus, $S_{K}^5(5)=S_{K}^{4}(1)+\sum _{j=1}^{4}S_{K}^{4}(j)=3+(3+5+6+5)=22$.

For every $6\le n$, due to $i=5\le n-1$, $S_{K}^n(5)$ can be computed by Lemma 5.

Hence, if $S_{K}^n(j)$ are known for all $1\le j\le i-1$ and n, we will compute $S_{K}^n(i)$ for all n in the next two steps. For $5\le i$, there exists a unique integer t such that $\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) <i\le \left( {\begin{array}{c}t\\ 2\end{array}}\right)$. Then, for every $2\le l\le t-1$, $S_{K}^l(i)=0$. First, when $t\le l\le i$, if $i>\left\lfloor \left( {\begin{array}{c}l\\ 2\end{array}}\right) /2\right\rfloor$, we have $S_{K}^l(i)=S_{K}^l(\left( {\begin{array}{c}l\\ 2\end{array}}\right) -i)$ where $\left( {\begin{array}{c}l\\ 2\end{array}}\right) -i<i$; otherwise, by Lemma 7, we compute $S_{K}^l(i)$ for $i\le \left\lfloor \left( {\begin{array}{c}l\\ 2\end{array}}\right) /2\right\rfloor$. Second, when $i+1\le l$, we compute $S_{K}^l(i)$ by Lemma 5.

When $i=5$, we can compute $S_{K}^n(5)$ for all n. Here, $t=4$. Then, $S_{K}^4(5)=S_{K}^4(\left( {\begin{array}{c}4\\ 2\end{array}}\right) -5)=S_{K}^4(1)=3$ and $S_{K}^5(5)=22$ by Lemma 7 in Example 2. In the following, we will give the formula of $S_{K}^n(5)$ for all $6\le n$ by Lemma 5.

Example 3

When $i=5$ and $6\le n$, by Lemma 5 and (7), we have

$$\begin{aligned} S_{K}^n(5)=S_{K}^{5}(5)+\sum _{l=5}^{n-1}\sum _{j=0}^{4}S_{K}^{l}(j). \end{aligned}$$

By Examples 1 and 2 and Lemma 6, we have

$$\begin{aligned} S_{K}^n(5)&=22+\sum _{l=5}^{n-1}\big (1+(l-1)+\frac{l(l-1)}{2}-1+\frac{l^3-7l}{6}+\frac{l(l+1)(l^2+l-14)}{24}\big )\\&=\frac{(n-1)(n^4+6n^3-9n^2-74n-120)}{120} \end{aligned}$$

for all $5\le n$.

By Lemmas 2, 5, and 7, we can compute the value of $S_{K}^n(i)$ for all $6\le i$ and n as follows.

Proposition 2

When $6\le i$, we can compute $S_{K}^n(i)$ for all $5\le n$ by using Lemmas 2, 5, and 7.

Proof

For all $0\le i\le 5$ and $3\le n$, all the $S_{K}^n(i)$ are computed. We can compute $S_{K}^n(i)$ for all n by using $S_{K}^n(j)$ for all $1\le j\le i-1$ and n.

First, we find an integer t such that $\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) <i\le \left( {\begin{array}{c}t\\ 2\end{array}}\right)$. For every $t\le l\le i$, if $i>\left\lfloor \left( {\begin{array}{c}l\\ 2\end{array}}\right) /2\right\rfloor$, we have $S_{K}^l(i)=S_{K}^l(\left( {\begin{array}{c}l\\ 2\end{array}}\right) -i)$ where $\left( {\begin{array}{c}l\\ 2\end{array}}\right) -i<i$; else if $i\le \left\lfloor \left( {\begin{array}{c}l\\ 2\end{array}}\right) /2\right\rfloor$, we compute $S_{K}^l(i)$ by Lemma 7. Second, for every $i+1\le l$, we compute $S_{K}^l(i)$ by Lemma 5. So, we can obtain $S_{K}^n(i)$ for all $5\le n$ and $6\le i$. $\square$

3.2 The size of a ball of radius r in $S_n$ under the Kendall $\tau$-metric

In this subsection, we will give the polynomial representation of the size of a ball with radius r in $S_n$ under the Kendall $\tau$-metric by using $S_K^n(r)$. We easily obtain the following lemma about the relationship between $B_K^n(r)$ and $S_K^n(r)$.

Lemma 8

For any $0\le r\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, we have

$$\begin{aligned} B_{K}^n(r)=\sum _{l=0}^{r}S_{K}^{n}(l). \end{aligned}$$

Given $S_K^n(i)$ for all $0\le i\le r-1$, by Lemmas 5, 7 and 8, we easily obtain the recursion formula of $B_K^n(r)$ in the following theorem.

Theorem 1

Suppose $S_K^n(i)$ are known for all $0\le i\le r-1$ and $5\le n$. If $4\le r\le \left\lfloor \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) }{2}\right\rfloor$, there exists a unique integer t such that $\left( {\begin{array}{c}t-1\\ 2\end{array}}\right) <r\le \left( {\begin{array}{c}t\\ 2\end{array}}\right)$. When $4\le r \le n-1$, we have

$$\begin{aligned} B_{K}^n(r)=\sum _{l=0}^{r-1}S_{K}^{n}(l)+S_{K}^{t}(\left( {\begin{array}{c}t\\ 2\end{array}}\right) -r)+\sum _{l=t}^{r-1}\sum _{j=r-l}^{r-1}S_{K}^{l}(j)+\sum _{l=r}^{n-1}\sum _{j=0}^{r-1}S_{K}^{l}(j). \end{aligned}$$

When $n\le r\le \left\lfloor \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) }{2}\right\rfloor$, we have

$$\begin{aligned} B_{K}^n(r)=\sum _{l=0}^{r-1}S_{K}^{n}(l)+S_{K}^{t}(\left( {\begin{array}{c}t\\ 2\end{array}}\right) -r)+\sum _{l=t}^{r-1}\sum _{j=r-l}^{r-1}S_{K}^{l}(j)-\sum _{l=n}^{r-1}\sum _{j=r-l}^{r-1}S_{K}^{l}(j). \end{aligned}$$

Specially, we have $B_{K}^n(0)=1$ and $B_{K}^n(1)=n$. When $r=2$, for all $n\ge 2$, we have

$$\begin{aligned} B_{K}^n(2)=\sum _{l=0}^{2}S_{K}^{n}(l)=(1+n-1+\frac{n(n-1)}{2}-1)=\frac{(n+2)(n-1)}{2}. \end{aligned}$$

(17)

When $r=3$, for all $n\ge 3$, we have

$$\begin{aligned} B_{K}^n(3)=\sum _{l=0}^{3}S_{K}^{n}(l)=(1+n-1+\frac{n(n-1)}{2}-1+\frac{n^3-7n}{6})=\frac{(n+1)(n^2+2n-6)}{6}.\qquad \end{aligned}$$

(18)

Example 4

When $r=4$ and $4\le n$, by Example 1 and Theorem 1, we have

$$\begin{aligned} B_{K}^n(4)&=\sum _{l=0}^{3}S_{K}^{n}(l)+S_{K}^{4}(\left( {\begin{array}{c}4\\ 2\end{array}}\right) -4)+\sum _{l=4}^{3}\sum _{j=4-l}^{4-1}S_{K}^{l}(j)+\sum _{l=4}^{n-1}\sum _{j=0}^{3}S_{K}^{l}(j)\nonumber \\&=\frac{(n+2)(n+1)(n^2+3n-12)}{24}. \end{aligned}$$

(19)

Moreover, when $r=5$ and $5\le n$, by Example 3 and Theorem 1, we have

$$\begin{aligned} B_{K}^n(5)&=\sum _{l=0}^{4}S_{K}^{n}(l)+S_{K}^{n}(5)\nonumber \\&=\frac{(n+7)n(n^3+3n^2-6n-28)}{120}. \end{aligned}$$

(20)

When $r\ge 6$, we can compute $B_{K}^n(r)$ by using Proposition 2 and Theorem 1.

4 Some sufficient conditions of the nonexistence of perfect permutation codes

In this section, we will give some sufficient conditions of the nonexistence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

4.1 The first sufficient condition of the nonexistence of perfect permutation codes

In this subsection, we present a sufficient condition of the nonexistence of a perfect t-error-correcting code under the Kendall $\tau$-metric by using the sphere-packing upper bound.

Lemma 9

For any $0\le t\le \left\lfloor \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1}{2}\right\rfloor$, if there exists a perfect t-error-correcting code C in $S_n$ under the Kendall $\tau$-metric. Then, we must have

$$\begin{aligned} B_{K}^n(t)\cdot |C|=n!. \end{aligned}$$

That is, the necessary condition of the existence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric is $B_{K}^n(t)|n!$.

Proof

By the sphere-packing upper bound in Proposition 1, if there exists a perfect t-error-correcting code C in $S_n$ under the Kendall $\tau$-metric, we must have $B_{K}^n(t)\cdot |C|=n!$. Thus, $B_{K}^n(t)|n!$. So, the necessary condition of the existence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric is $B_{K}^n(t)|n!$. $\square$

According to Lemma 9, we have the following theorem which illustrate the nonexistence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

Theorem 2

For any $0\le t\le \left\lfloor \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1}{2}\right\rfloor$, if $B_{K}^n(t)$ has a prime factor $p>n$, then there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

Proof

By Lemma 9, the necessary condition of the existence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric is $B_{K}^n(t)|n!$. Since $B_{K}^n(t)$ has a prime factor $p>n$, we have $B_{K}^n(t)\not \mid n!$. So, we prove the above result.$\square$

4.2 The second sufficient condition of the nonexistence of perfect permutation codes

In this subsection, we give another sufficient condition of the nonexistence of a perfect t-error-correcting code under the Kendall $\tau$-metric by using some properties of $B_K^n(r)$ and $S_K^n(r)$. For convenience, we define $S_{n,i}\triangleq \{\pi \in S_n|\pi (i)=1\}$ for any $1\le i\le n$. That is, $\pi$ is an element of $S_{n,i}$ if 1 appears in the i-th position of $\pi$. Clearly, $|S_{n,i}|=(n-1)!$.

For $\pi \in S_{n,k}$, let $T_{n,(k,j)}^{(t)}(\pi )\triangleq B_K^{n}(\pi ,t)\cap S_{n,j}$ for all $0\le t\le \left\lfloor \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1}{2}\right\rfloor$. In the following, we prove that the size of $T_{n,(k,j)}^{(t)}(\pi )$ does not depend on $\pi$. For convenience, we denote the size of $T_{n,(k,j)}^{(t)}(\pi )$ as $T_{n,(k,j)}^{(t)}$.

Lemma 10

For all $1\le k,j\le n$ and any $\pi \in S_{n,k}$, the size of $T_{n,(k,j)}^{(t)}(\pi )$ does not depend on $\pi$.

Proof

For any two distinct permutations $\pi , \sigma \in S_{n,k}$, we prove $|T_{n,(k,j)}^{(t)}(\pi )|=|T_{n,(k,j)}^{(t)}(\sigma )|$. First, we have $T_{n,(k,j)}^{(t)}(\pi )=\{\beta \in S_n|d_{K}(\pi ,\beta )\le t,\beta (j)=1\}$. By (2), we get

$$\begin{aligned} T_{n,(k,j)}^{(t)}(\pi )&=\{\beta \in S_n|d_{K}(\pi ,\beta )\le t,\beta (j)=1\}\\&=\{\beta \in S_n|d_{K}(\epsilon _n,\beta \circ \pi ^{-1})\le t,\beta (j)=1\}\\&=\{\beta \in S_n|d_{K}(\sigma ,\beta \circ \pi ^{-1}\circ \sigma )\le t,\beta (j)=1\}. \end{aligned}$$

Hence, $|T_{n,(k,j)}^{(t)}(\pi )|=|\{\beta \in S_n|d_{K}(\sigma ,\beta \circ \pi ^{-1}\circ \sigma )\le t,\beta (j)=1\}|=|\{\beta \circ \pi ^{-1}\circ \sigma \in S_n|d_{K}(\sigma ,\beta \circ \pi ^{-1}\circ \sigma )\le t,\beta (j)=1\}|$. Since $\beta \circ \pi ^{-1}\circ \sigma (j)=\sigma (\pi ^{-1}(\beta (j)))=1$, we have $|\{\beta \circ \pi ^{-1}\circ \sigma \in S_n|d_{K}(\sigma ,\beta \circ \pi ^{-1}\circ \sigma )\le t,\beta (j)=1\}|=|\{\beta \circ \pi ^{-1}\circ \sigma \in S_n|d_{K}(\sigma ,\beta \circ \pi ^{-1}\circ \sigma )\le t,\beta \circ \pi ^{-1}\circ \sigma (j)=1\}|$. Let $\gamma =\beta \circ \pi ^{-1}\circ \sigma$. Then, we obtain that $|T_{n,(k,j)}^{(t)}(\pi )|=|\{\beta \circ \pi ^{-1}\circ \sigma \in S_n|d_{K}(\sigma ,\beta \circ \pi ^{-1}\circ \sigma )\le t,\beta \circ \pi ^{-1}\circ \sigma (j)=1\}|=|\{\gamma \in S_n|d_{K}(\sigma ,\gamma )\le t,\gamma (j)=1\}|=|T_{n,(k,j)}^{(t)}(\sigma )|$. Thus, the size of $T_{n,(k,j)}^{(t)}(\pi )$ does not depend on $\pi$.$\square$

Similarly, the exchange between k and j in $T_{n,(k,j)}^{(t)}$ does not change the size of $T_{n,(k,j)}^{(t)}$.

Lemma 11

For all $1\le k,j\le n$, we have

$$\begin{aligned} T_{n,(k,j)}^{(t)}=T_{n,(j,k)}^{(t)}. \end{aligned}$$

Proof

By Lemma 10, we only prove $|T_{n,(k,j)}^{(t)}(\pi )|=|T_{n,(j,k)}^{(t)}(\sigma )|$ for any $\pi \in S_{n,k}$ and $\sigma \in S_{n,j}$. According to the definition of $T_{n,(k,j)}^{(t)}(\pi )$, we have

$$\begin{aligned} T_{n,(k,j)}^{(t)}(\pi )&=\{\beta \in S_n|d_{K}(\pi ,\beta )\le t,\beta (j)=1\}\\&=\{\beta \in S_n|d_{K}(\pi \circ \beta ^{-1},\epsilon _n)\le t,\beta (j)=1\}\\&=\{\beta \in S_n|d_{K}(\pi \circ \beta ^{-1}\circ \sigma ,\sigma )\le t,\beta (j)=1\}. \end{aligned}$$

Then, we get $\pi \circ \beta ^{-1}\circ \sigma (k)=\sigma (\beta ^{-1}(\pi (k)))=\sigma (j)=1$. Given $\pi \in S_{n,k}$ and $\sigma \in S_{n,j}$, we obtain $|\{\beta \in S_n|d_{K}(\pi \circ \beta ^{-1}\circ \sigma ,\sigma )\le t,\beta (j)=1\}|=|\{\pi \circ \beta ^{-1}\circ \sigma \in S_n|d_{K}(\pi \circ \beta ^{-1}\circ \sigma ,\sigma )\le t,\pi \circ \beta ^{-1}\circ \sigma (k)=1\}|$, i.e., $|T_{n,(k,j)}^{(t)}(\pi )|=|T_{n,(j,k)}^{(t)}(\sigma )|$.$\square$

Assume that there exists a perfect t-error-correcting code $C^{(t)}\subset S_n$. For any $1\le i\le n$, we define $C_{n,i}^{(t)}\triangleq C^{(t)}\cap S_{n,i}$ and $x_i \triangleq |C_{n,i}^{(t)}|$. Since $C^{(t)}$ is a perfect t-error-correcting code, it follows that for any two distinct permutations $\pi ,\sigma \in C^{(t)}$ we have $B_K^{n}(\pi ,t)\cap B_K^{n}(\sigma ,t)=\emptyset$. Moreover, we get $\bigcup _{\pi \in C^{(t)}}B_K^{n}(\pi ,t)=S_n$. Clearly, we can obtain the following lemma.

Lemma 12

For all $1\le i\le n$, we have $\bigcup _{1\le k\le n,\pi \in C_{n,k}^{(t)}}T_{n,(k,i)}^{(t)}(\pi )=S_{n,i}$.

Proof

For each permutation $\sigma \in S_{n,i}$, there must exist a codeword $\pi \in C^{(t)}$ such that $\sigma \in B_K^{n}(\pi ,t)$, where $\pi (k)=1$ for some $k\in [n]$. By the definition of $T_{n,(k,i)}^{(t)}(\pi )$, we have $\sigma \in T_{n,(k,i)}^{(t)}(\pi )$. Hence, $\bigcup _{1\le k\le n,\pi \in C_{n,k}^{(t)}}T_{n,(k,i)}^{(t)}(\pi )=S_{n,i}$.$\square$

For any two distinct permutations $\pi \in C_{n,k}^{(t)}$ and $\sigma \in C_{n,j}^{(t)}$, the relationship between $T_{n,(k,i)}^{(t)}(\pi )$ and $T_{n,(j,i)}^{(t)}(\sigma )$ is given as follows.

Lemma 13

For any two distinct permutations $\pi \in C_{n,k}^{(t)}$ and $\sigma \in C_{n,j}^{(t)}$, we have $T_{n,(k,i)}^{(t)}(\pi )\bigcap T_{n,(j,i)}^{(t)}(\sigma )=\emptyset$ for all $1\le i \le n$.

Proof

Since $\pi ,\sigma \in C^{(t)}$ and $\pi \ne \sigma$, $B_K^{n}(\pi ,t)\bigcap B_K^{n}(\sigma ,t)=\emptyset$. Clearly, due to the definition of $T_{n,(k,i)}^{(t)}(\pi )$, we have $T_{n,(k,i)}^{(t)}(\pi )\bigcap T_{n,(j,i)}^{(t)}(\sigma )=\emptyset$ for all $1\le i \le n$.$\square$

By Lemmas 12 and 13, for all $1\le i\le n$, we obtain that

$$\begin{aligned} \left| \bigcup _{1\le k\le n,\pi \in C_{n,k}^{(t)}}T_{n,(k,i)}^{(t)}(\pi )\right| =\sum _{k=1}^{n}\sum _{\pi \in C_{n,k}^{(t)}}T_{n,(k,i)}^{(t)}=\sum _{k=1}^{n}T_{n,(k,i)}^{(t)}x_k=|S_{n,i}|=(n-1)!, \end{aligned}$$

(21)

where $|C_{n,k}^{(t)}|=x_k$.

Let $\varvec{x}=(x_1,x_2,\ldots ,x_n)$ and let $\varvec{I}$ be the all-ones column vector. By (21), we have a matrix form as

$$\begin{aligned} A\varvec{x}^T=(n-1)!\cdot \varvec{I}, \end{aligned}$$

(22)

where $A=(a_{i,j})$ is an $n\times n$ matrix and $a_{i,j}=T_{n,(j,i)}^{(t)}$.

Furthermore, we discuss the sum of every row in A as follows.

Lemma 14

For all $1\le i\le n$, we have

$$\begin{aligned} \sum _{k=1}^{n}T_{n,(k,i)}^{(t)}=B_{K}^{n}(t). \end{aligned}$$

Proof

For all $1\le i\le n$ and $\pi \in S_{n,i}$, $B_{K}^{n}(\pi ,t)=B_{K}^{n}(\pi ,t)\bigcap S_n=B_{K}^{n}(\pi ,t) \bigcap \big (\bigcup _{k=1}^{n}S_{n,k}\big )=\bigcup _{k=1}^{n}\big (B_{K}^{n}(\pi ,t)\bigcap S_{n,k}\big )$. Since all the sets of $S_{n,k}$ are pairwise disjoint, we have

$$\begin{aligned} B_{K}^{n}(t)&=|B_{K}^{n}(\pi ,t)|=\left| \bigcup _{k=1}^{n}\big (B_{K}^{n}(\pi ,t)\bigcap S_{n,k}\big )\right| \\&=\sum _{k=1}^{n}\left| B_{K}^{n}(\pi ,t)\bigcap S_{n,k}\right| \\&\overset{(a)}{=}\sum _{k=1}^{n}T_{n,(i,k)}^{(t)}\\&\overset{(b)}{=}\sum _{k=1}^{n}T_{n,(k,i)}^{(t)}, \end{aligned}$$

where $\overset{(a)}{=}$ follows from the definition of $T_{n,(i,k)}^{(t)}$ and $\overset{(b)}{=}$ follows from Lemma 11.$\square$

By Lemma 14, we obtain that the sum of every row in A is equal to $B_{K}^{n}(t)$. Then, it follows that the linear equation system defined in (22) has a solution $\varvec{y}=\frac{(n-1)!}{B_{K}^{n}(t)}\cdot \varvec{I}$. In order to discuss the solutions of (22), we need the following lemma that is an immediate conclusion of the well known Gerschgorin circle theorem [5].

Lemma 15

Let $B=(b_{i,j})$ be an $n\times n$ matrix. If $|b_{i,i}|>\sum _{j\ne i}|b_{i,j}|$ for all i, $1\le i\le n$, then B is nonsingular.

Theorem 3

For any $0\le t\le \left\lfloor \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1}{2}\right\rfloor$, if $T_{n,(i,i)}^{(t)}\ge \frac{B_{K}^{n}(t)}{2}-1$ for all $1\le i\le n$ and $B_{K}^{n}(t)$ has a prime factor $p\ge n$, then there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

Proof

If $T_{n,(i,i)}^{(t)}\ge \frac{B_{K}^{n}(t)}{2}-1$ for all $1\le i\le n$, by Lemma 15, then A is a nonsingular matrix. Hence, $\varvec{y}$ is the unique solution of (22). That is, we have $\varvec{x}=\varvec{y}=\frac{(n-1)!}{B_{K}^{n}(t)}\cdot \varvec{I}$. If $B_{K}^{n}(t)$ has a prime factor $p\ge n$ and A is nonsingular, then $\frac{(n-1)!}{B_{K}^{n}(t)}$ is not an integer and perfect t-error-correcting codes do not exist. Hence, we prove the above result.$\square$

4.3 The third sufficient condition of the nonexistence of perfect permutation codes

In this subsection, we give the third sufficient condition of the nonexistence of a perfect t-error-correcting code under the Kendall $\tau$-metric by using some upper bounds on $A_K(n,2t+1)$.

Lemma 16

[14, Theorem 23] If $A_K(n,2t+1)\ge M$, then

$$\begin{aligned} \left( {\begin{array}{c}\left\lceil \frac{M}{2}\right\rceil \\ 2\end{array}}\right) (2t+2)+\left( {\begin{array}{c}\left\lfloor \frac{M}{2}\right\rfloor \\ 2\end{array}}\right) (2t+2)+ \left\lceil \frac{M}{2}\right\rceil \left\lfloor \frac{M}{2}\right\rfloor (2t+1)\le \left( {\begin{array}{c}n\\ 2\end{array}}\right) \left\lceil \frac{M}{2}\right\rceil \left\lfloor \frac{M}{2}\right\rfloor . \end{aligned}$$

Lemma 17

[2, Theorem 10] If $\frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) <d\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, then

$$\begin{aligned} A_K(n,d)=2. \end{aligned}$$

By Lemma 16, we present some sufficient conditions of the nonexistence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric as follows.

Theorem 4

For any $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right) \le 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, if $B_{K}^n(t)\cdot \frac{4t+4}{4t+3-\left( {\begin{array}{c}n\\ 2\end{array}}\right) }<n!$, then there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric. Moreover, for $\frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, if $2B_{K}^n(t)<n!$, then there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

Proof

By Lemma 16, if $A_K(n,2t+1)$ is even, then we have

$$\begin{aligned} A_K(n,2t+1)\le \frac{4t+4}{4t+3-\left( {\begin{array}{c}n\\ 2\end{array}}\right) } \end{aligned}$$

(23)

for any $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right) \le 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. If $A_K(n,2t+1)$ is odd, then we obtain

$$\begin{aligned} A_K(n,2t+1)\le \frac{\left( {\begin{array}{c}n\\ 2\end{array}}\right) +1}{4t+3-\left( {\begin{array}{c}n\\ 2\end{array}}\right) } \end{aligned}$$

(24)

for any $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right) \le 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. When $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right) \le 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, then $4t+3>\left( {\begin{array}{c}n\\ 2\end{array}}\right) +1$. Hence, by (23) and (24), for any $\frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right) \le 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, we have $A_K(n,2t+1)\le \frac{4t+4}{4t+3-\left( {\begin{array}{c}n\\ 2\end{array}}\right) }$. Moreover, the necessary condition of the existence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric is $B_{K}^n(t)\cdot A_K(n,t)=n!$. So, if $B_{K}^n(t)\frac{4t+4}{4t+3-\left( {\begin{array}{c}n\\ 2\end{array}}\right) }<n!$, then there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

When $\frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, by Lemma 17, we have $A_K(n,2t+1)=2$. Thus, if $2B_{K}^n(t)<n!$, then there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric. So, we prove the above result.$\square$

5 The nonexistence of a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric

In the section, we will discuss the nonexistence of a perfect t-error-correcting code in $S_n$ for some n and t by using Theorems 2, 3 and 4.

5.1 The nonexistence of a perfect t-error-correcting code in $S_n$ by using the first condition

In this subsection, we use Theorem 2 to prove the nonexistence of perfect t-error-correcting code in $S_n$ for some n and $t=2,3,4,5.$

When $t=2$, by (17), we have $B_{K}^n(2)=\frac{(n+2)(n-1)}{2}$. By Theorem 2, we can prove the nonexistence of a perfect two-error-correcting code in $S_n$, where $n+2>6$ is a prime.

When $t=3$, by (18), we have $B_{K}^n(3)=\frac{(n+1)(n^2+2n-6)}{6}$. First, if $n+1>6$ is a prime, then $B_{K}^n(3)$ have a prime factor $n+1>n$. Second, we compute $n^2+2n-6$ for $4\le n\le 33$ and obtain that $(n+1)(n^2+2n-6)$ has a prime factor $p>n$ except for $n=13$ and $n=26$. If $n=13$, $B_{K}^{13}(3)=441=9\times 7^2$. Thus, $441\not \mid 13!$. If $n=26$, $B_{K}^{26}(3)=3249=9\times 19^2$. Hence, $3249\not \mid 26!$. So, by Theorem 2, we can prove the nonexistence of a perfect three-error-correcting code in $S_n$, where $n+1>6$ is a prime, or $n^2+2n-6$ has a prime factor $p>n$, or $4\le n \le 33$.

When $t=4$, by (19), we have $B_{K}^n(4)=\frac{(n+1)(n+2)(n^2+3n-12)}{24}$. First, if $n+1>6$ or $n+2>7$ is a prime, then $B_{K}^n(3)$ have a prime factor $p>n$. Second, we compute $n^2+3n-12$ for $5\le n\le 19$ and obtain that $(n ^2+3n-12)(n+1)(n+2)$ has a prime factor $p>n$ except for $n=13$. If $n=13$, $B_{K}^{13}(4)=1715=5\times 7^3$. Thus, $1715\not \mid 13!$. So, by Theorem 2, we can prove the nonexistence of a perfect four-error-correcting code in $S_n$, where $n+1>6$ or $n+2>7$ is a prime, or $n^2+3n-12$ has a prime factor $p>n$, or $5\le n \le 19$.

When $t=5$, by (20), $B_{K}^n(5)=\frac{(n+7)n(n^3+3n^2-6n-28)}{120}$. By Theorem 2, we can prove the nonexistence of a perfect five-error-correcting code in $S_n$, where $n+7\ge 12$ is a prime or $n^3+3n^2-6n-28$ has a prime factor $p> n$.

By the above discussion, we have the following theorem.

Theorem 5

When $t=2$, there does not exist a perfect two-error-correcting code in $S_n$, where $n+2>6$ is a prime. When $t=3$, there does not exist a perfect three-error-correcting code in $S_n$, where $n+1>6$ is a prime, or $n^2+2n-6$ has a prime factor $p>n$, or $4\le n \le 33$. When $t=4$, there does not exist a perfect four-error-correcting code in $S_n$, where $n+1>6$ or $n+2>7$ is a prime, or $n^2+3n-12$ has a prime factor $p>n$, or $5\le n \le 19$. When $t=5$, there does not exist a perfect five-error-correcting code in $S_n$, where $n+7\ge 12$ is a prime or $n^3+3n^2-6n-28$ has a prime factor $p> n$.

5.2 The nonexistence of a perfect t-error-correcting code in $S_n$ by using the second condition

In this subsection, we use Theorem 3 to prove the nonexistence of perfect t-error-correcting code in $S_n$ for some n, t. When $t=1~\text {or}~5$, $B_{K}^{n}(t)$ has a factor n. Buzaglo and Etzion [2] proved that A is nonsingular for $n>4$ and therefore, there is no perfect single-error-correcting codes in $S_n$ if $n\ge 4$ is a prime. In the following, we discuss the condition of $T_{n,(i,i)}^{(5)}\ge \frac{B_{K}^{n}(5)}{2}-1$ for all $1\le i\le n$ which makes A nonsingular.

First, due to $B_{K}^n(5)=\frac{n(n+7)(n^3+3n^2-6n-28)}{120}$, we obtain that $B_{K}^{n}(5)$ has a prime factor $p>n$ for all $5\le n\le 16$ except for $B_{K}^{7}(5)=7^3$ and $B_{K}^{11}(5)=2^4\times 3\times 5\times 11$. By Theorem 2, we obtain that there is no perfect five-error-correcting codes in $S_n$ for $5\le n\le 10$ or $12\le n\le 16$. Second, we only consider the condition of $T_{n,(i,i)}^{(5)}\ge \frac{B_{K}^{n}(5)}{2}-1$ for all $1\le i\le n$, where $n\ge 17$.

When $i=1$ and $\pi \in S_{n,1}$, we obtain all the elements of $T_{n,(1,1)}^{(5)}(\pi )$ by only moving the right $n-1$ elements at most 5 adjacent transpositions. Hence, we have

$$\begin{aligned} T_{n,(1,1)}^{(5)}=B_K^{n-1}(5). \end{aligned}$$

In order to compute $T_{n,(i,i)}^{(5)}$ for $2\le i\le n$, we need the following lemmas.

Lemma 18

For all $1\le i\le n$, we have

$$\begin{aligned} T_{n,(i,i)}^{(5)}=T_{n,(n+1-i,n+1-i)}^{(5)}. \end{aligned}$$

Proof

Choose $\pi \in S_{n,i}$ and $\pi ^r\in S_{n,n+1-i}$. By Lemma 10, we obtain that

$$\begin{aligned} T_{n,(i,i)}^{(5)}=|T_{n,(i,i)}^{(5)}(\pi )|=|\{\beta \in S_n|d_{K}(\pi ,\beta )\le 5,\beta (i)=1\}|, \end{aligned}$$

and

$$\begin{aligned} T_{n,(n+1-i,n+1-i)}^{(5)}&=|T_{n,(n+1-i,n+1-i)}^{(5)}(\pi ^r)|\\&=|\{\beta \in S_n|d_{K}(\pi ^r,\beta )\le 5,\beta (n+1-i)=1\}|. \end{aligned}$$

We just need to prove that $|T_{n,(i,i)}^{(5)}(\pi )|=|T_{n,(n+1-i,n+1-i)}^{(5)}(\pi ^r)|$. First we define a function $f: T_{n,(i,i)}^{(5)}(\sigma )\rightarrow T_{n,(n+1-i,n+1-i)}^{(5)}(\sigma ^r)$, where $f(\sigma )=\sigma ^r$ for any $\sigma \in T_{n,(i,i)}^{(5)}(\pi )$.

If $\beta \in T_{n,(i,i)}^{(5)}(\pi )$, then $d_K(\beta ,\pi )\le 5$ and $\beta (i)=1$. Hence, $d_K(\pi ^r,\beta ^r)\le 5$ and $\beta ^r(n+1-i)=1$. Then, $\beta ^r\in T_{n,(n+1-i,n+1-i)}^{(5)}(\pi ^r)$. Moreover, we can easily prove that the function f is reasonable and bijection. Thus, $T_{n,(i,i)}^{(5)}=T_{n,(n+1-i,n+1-i)}^{(5)}$ for all $1\le i\le n$.$\square$

Lemma 19

For $\pi ,\sigma \in S_{n,i}$ and $2\le i\le n-1$, let $\pi =[a_1,\ldots a_{i-1},1,a_{i+1},\ldots ,a_n]$ and $\sigma =[b_1,\ldots b_{i-1},1,b_{i+1},\ldots ,b_n]$. If the number of different elements between $\{a_1,\ldots ,a_{i-1}\}$ and $\{b_1,\ldots ,b_{i-1}\}$ is t, then $d_{K}(\pi ,\sigma )\ge t^2+t$.

Proof

Assume that the former t elements between $[a_1,\ldots a_{i-1}]$ and $[b_1,\ldots b_{i-1}]$ are different. Then, for all $1\le j,k\le t$, we have that $\{a_j,b_k\}$, $\{1,a_j\}$ and $\{1,b_j\}$ in $\pi$ and $\sigma$ are different ordered pairs. Thus, we have $d_{K}(\pi ,\sigma )\ge t^2+t$.$\square$

By Lemma 18, we only consider $T_{n,(i,i)}^{(5)}$ for $2\le i\le n-2$. By Lemma 19, for $\pi =[a_1,\ldots a_{i-1},1,a_{i+1},\ldots ,a_n]\in S_{n,i}$, we can divide $T_{n,(i,i)}^{(5)}(\pi )$ into two disjoint subsets as follows. For convenience, we denote by $Fr_i(\pi )=\cup _{j=1}^{i-1}\{\pi (j)\}$ a set of the former $i-1$ elements of $\pi$, i.e., $Fr_i(\pi )=\{a_1,\ldots a_{i-1}\}$. Moreover, we denote by $L_i(\pi )=\{\beta |\beta (i)=1, Fr_i(\beta )=Fr_i(\pi ),~\text {and}~d_K(\beta ,\pi )\le 5\}$ and $R_i(\pi )=\{\beta |\text {the number of different elements between}\, Fr_i(\pi )\hbox { and }Fr_i(\beta )\hbox { is} 1,~\beta (i)=1, \text {and}~d_K(\beta ,\pi )\le 5\}$.

Lemma 20

Let $2\le i\le n-2$. For any $\pi \in S_{n,i}$, we obtain that $T_{n,(i,i)}^{(5)}(\pi )=L_i(\pi )\cup R_i(\pi )$ and $L_i(\pi )\cap R_i(\pi )=\emptyset$.

Proof

By the definitions of $L_i(\pi )~\text {and}~R_i(\pi )$, we clearly have $L_i(\pi )\cap R_i(\pi )=\emptyset$. Choose $\beta \in T_{n,(i,i)}^{(5)}(\pi )$ and let t be the number of different elements between $Fr_i(\pi )$ and $Fr_i(\beta )$. By Lemma 19, we obtain that $d_K(\beta ,\pi )\ge t^2+t$. Since $\beta \in T_{n,(i,i)}^{(5)}(\pi )$, we have $d_K(\beta ,\pi )\le 5$ and $t\le 1$. Hence, if $t=1$, then $\beta \in R_i(\pi )$. If $t=0$, then $\beta \in L_i(\pi )$. So, we obtain that $T_{n,(i,i)}^{(5)}(\pi )=L_i(\pi )\cup R_i(\pi )$ and $L_i(\pi )\cap R_i(\pi )=\emptyset$. $\square$

Example 5

Let $n=11$ and $\pi =[3,2,1,4,5,6,7,8,9,10,11]$. Consider $T_{11,(3,3)}^{(5)}(\pi )$, we obtain the two kinds of permutations in $T_{11,(3,3)}^{(5)}(\pi )$. By using an adjacent transpositions on the former 2 elements of $\pi$, we obtain the first kind of permutation $\sigma =[2,3,1,4,5,6,7,8,9,10,11]$. By using three adjacent transpositions on the elements $\{3,1,4\}$ of $\sigma$, we obtain the second kind of permutation $\sigma '=[2,4,1,3,5,6,7,8,9,10,11]$ (i.e., $[2,3,1,4,5,6,7,8,9,10,11]\rightarrow [2,3,4,1,5,6,7,8,9, 10,11]\rightarrow [2,4,3,1,5,6,7, 8,9,10,11]\rightarrow [2,4,1,3,5,6,7,8,9,10,11])$.

By Lemma 10, the size of $L_i(\pi )$ and $R_i(\pi )$ does not depend on $\pi \in S_{n,i}$. Then, we denote by $L_i$ and $R_i$ the size of $L_i(\pi )$ and $R_i(\pi )$, respectively. The values of $L_i$ and $R_i$ is given in the following lemma and the proof of the next lemma is given in Appendix A.

Lemma 21

For $2\le i\le n-1$, we obtain that

$$\begin{aligned} L_i=\sum _{t=0}^{5}S_{K}^{i-1}(t)B_K^{n-i}(5-t) \end{aligned}$$

and

$$\begin{aligned} R_i= {\left\{ \begin{array}{ll} B_K^{n-2}(2)+B_K^{n-2}(1)+B_K^{n-2}(0)~~ \text {if}\,i=2\hbox { or }n-1,\\ B_K^{n-3}(2)+3B_K^{n-3}(1)+3~~ \text {if}\,i=3\hbox { or }n-2,\\ \sum _{t=0}^{2}S_{K}^{i-1}(t)B_K^{n-i}(2-t)+2\sum _{t=0}^{1}S_{K}^{i-1}(t)B_K^{n-i}(1-t)+2~~\text {if}\, 4\le i\le n-3, \end{array}\right. } \end{aligned}$$

where $S_K^{i-1}(t)=0$ for all $t\ge \left( {\begin{array}{c}i-1\\ \lfloor \frac{i-1}{2}\rfloor \end{array}}\right)$.

By Lemma 21, when $i=3,4~\text {and}~5$, we have

$$\begin{aligned}&T_{n,(2,2)}^{(5)}=B_K^{n-2}(5)+B_K^{n-2}(2)+B_K^{n-2}(1)+1, \end{aligned}$$

(25)

$$\begin{aligned}&T_{n,(3,3)}^{(5)}=B_K^{n-3}(5)+B_K^{n-3}(4)+B_K^{n-3}(2)+3B_K^{n-3}(1)+3, \end{aligned}$$

(26)

$$\begin{aligned}&T_{n,(i,i)}^{(5)}=\sum _{t=0}^{5}S_{K}^{i-1}(t)B_K^{n-i}(5-t)+\sum _{t=0}^{2}S_{K}^{i-1}(t)B_K^{n-i}(2-t)+2\sum _{t=0}^{1}S_{K}^{i-1}(t)B_K^{n-i}(1-t)+2, \nonumber \\ \end{aligned}$$

(27)

for all $4\le i\le n-3$, where $S_K^{i-1}(t)=0$ for all $t\ge \left( {\begin{array}{c}i-1\\ \lfloor \frac{i-1}{2}\rfloor \end{array}}\right)$. By (17)–(20) and (25)–(27), we compute the size of $T_{n,(i,i)}^{(5)}$ as follows. For all $1\le i\le n$, we have

$$\begin{aligned} T_{n,(i,i)}^{(5)}= {\left\{ \begin{array}{ll} \frac{1}{120}(n^5+5n^4-15n^3-65n^2-46n+120)\quad \text {if}\,i=1\hbox { or }n,\\ \frac{1}{120}(n^5-25n^3+60n^2-36n)\quad \text {if}\,i=2\hbox { or }n-1,\\ \frac{1}{120}(n^5-45n^3+120n^2+164n-480)\quad \text {if}\,i=3\hbox { or }n-2,\\ \frac{1}{120}(n^5-45n^3+60n^2+344n-240)\quad \text {if}\,i=4\hbox { or }n-3,\\ \frac{1}{120}(n^5-45n^3+60n^2+224n)\quad \text {if}\,i=5\hbox { or }n-4,\\ \frac{1}{120}(n^5-45n^3+60n^2+224n-120)\quad \text {if}\,6\le i\le n-5, \end{array}\right. } \end{aligned}$$

(28)

where $16\le n$.

By (28), then we have

$$\begin{aligned} T_{n,(i,i)}^{(5)}-\frac{B_K^{n}(5)}{2}-1= {\left\{ \begin{array}{ll} \frac{1}{240}n^5-\frac{1}{16}n^3-\frac{1}{4}n^2+\frac{13}{30}n~~ \text {if}\,i=1\hbox { or }n,\\ \frac{1}{240}n^5-\frac{1}{24}n^4-\frac{13}{48}n^3+\frac{19}{24}n^2+\frac{31}{60}n-1\quad \text {if}\,i=2\hbox { or }n-1,\\ \frac{1}{240}n^5-\frac{1}{24}n^4-\frac{7}{16}n^3+\frac{31}{24}n^2+\frac{131}{60}n-5\quad \text {if}\,i=3\hbox { or }n-2,\\ \frac{1}{240}n^5-\frac{1}{24}n^4-\frac{7}{16}n^3+\frac{19}{24}n^2+\frac{221}{60}n-3\quad \text {if}\,i=4\hbox { or }n-3,\\ \frac{1}{240}n^5-\frac{1}{24}n^4-\frac{7}{16}n^3+\frac{19}{24}n^2+\frac{161}{60}n-1\quad \text {if}\,i=5\hbox { or }n-4,\\ \frac{1}{240}n^5-\frac{1}{24}n^4-\frac{7}{16}n^3+\frac{19}{24}n^2+\frac{161}{60}n-2\quad \text {if}\,6\le i\le n-5. \end{array}\right. } \end{aligned}$$

(29)

By simple computations, for all $n\ge 16$, we obtain that

$$\begin{aligned} T_{n,(i,i)}^{(5)}-\frac{B_K^{n}(5)}{2}-1>0, \end{aligned}$$

(30)

for all $1\le i\le n$.

By (30) and Theorem 3, if $n\ge 16$ and $t=5$, we have A is nonsingular. Thus there does not exist a perfect five-error-correcting code in $S_n$ if $n\ge 16$ is a prime. By the above discussion and Theorem 5, we have the following theorem.

Theorem 6

There does not exist a perfect five-error-correcting code in $S_n$, where $n\ge 16$ is a prime or $n+7\ge 12$ is a prime or $n^3+3n^2-6n-28$ has a prime factor $p> n$.

5.3 The nonexistence of a perfect t-error-correcting code in $S_n$ by using the third condition

In this subsection, we use Theorem 4 to prove the nonexistence of perfect t-error-correcting code in $S_n$ for some n and $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right)< 2t+1< \left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

Assume that $\frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. If $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, by Lemma 2 or Corollary 8 [2], we have $2B_K^{n}(t)=n!$ and there exists a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric. Otherwise, by Lemma 17, we obtain that $2B_K^{n}(t)<n!$ and there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for all $\frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$ except for $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

Let $2t+1=\alpha \left( {\begin{array}{c}n\\ 2\end{array}}\right)$ for $\frac{5}{8}\le \alpha \le \frac{2}{3}$. If $A_K(n,2t+1)$ is even, by (23), we have

$$\begin{aligned} A_K(n,2t+1)<1+\frac{1}{2\alpha -1}\le 5. \end{aligned}$$

If $A_K(n,2t+1)$ is odd, by (24), we obtain

$$\begin{aligned} A_K(n,2t+1)<\frac{1}{2\alpha -1}\le 4. \end{aligned}$$

Hence, we have that

$$\begin{aligned} A_K(n,2t+1)\le 4 \end{aligned}$$

(31)

for all $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

In order to prove the nonexistence of perfect t-error-correcting code in $S_n$ for all $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, we need some lemmas in the following. The proof of the next lemma is given in Appendix B.

Lemma 22

Let p, q be two integers such that $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Then, we have

$$\begin{aligned} S_K^{n}(p)+S_K^{n}(q)+p-2<S_K^n(p+q) \end{aligned}$$

for all $n\ge 6$.

By Lemma 22, we can obtain the following lemma.

Lemma 23

For any $n\ge 5$, we obtain that

$$\begin{aligned} 4B_K^n\left( \left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor \right) <n!. \end{aligned}$$

(32)

Proof

By Lemma 2, we have $B_K^n{\left( \left\lfloor \frac{1}{2}(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1)\right\rfloor \right) \le \frac{1}{2}n!}$. In order to obtain the result in (32), we only need to prove that

$$\begin{aligned} \sum \limits _{i=0}^{\left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor }S_K^n(i)< \sum \limits _{i=\left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor +1}^{\left\lfloor \frac{1}{2}(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1)\right\rfloor }S_K^n(i) \end{aligned}$$

(33)

for all $n\ge 6$.

Assume that $\left( {\begin{array}{c}n\\ 2\end{array}}\right) =6m$ for some $m\ge 3$. Then $\left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor =2m-1$ and $\left\lfloor \frac{1}{2}(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1)\right\rfloor =3m-1$. Hence, we have

$$\begin{aligned} \sum \limits _{i=0}^{\left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor }S_K^n(i)= \sum \limits _{i=0}^{2m-1}S_K^{n}(i) \end{aligned}$$

and

$$\begin{aligned} \sum \limits _{i=\left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor +1}^{\left\lfloor \frac{1}{2}(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -1)\right\rfloor }S_K^n(i)= \sum \limits _{i=2m}^{3m-1}S_K^{n}(i). \end{aligned}$$

By Lemma 22, we have $S^{n}(m+t)+S^{n}(m-t)+m-t-2<S^{n}(2m)$ for all $1\le t\le m-1$. Hence, we obtain $S^{n}(m+t)+S^{n}(m-t)\le S^{n}(2m)$ for all $1\le t\le m-1$. Since $S^{n}(t)$ is a strictly increasing sequence for $1\le t\le 3m$, then $S^{n}(0)+S^{n}(m)\le S^{n}(2m)$. So, we have

$$\begin{aligned} \left( S^{n}(0)+S^{n}(m)\right) +\sum \limits _{t=1}^{m-1}\left( S^{n}(m+t)+S^{n}(m-t)\right) \le mS^{n}(2m)<\sum \limits _{i=2m}^{3m-1}S_K^{n}(i). \end{aligned}$$

(34)

Therefore, when $\left( {\begin{array}{c}n\\ 2\end{array}}\right) =6m$ and $n\ge 6$, by (34), we can obtain this result of (33).

Similarly, when $n\ge 6$ and $\left( {\begin{array}{c}n\\ 2\end{array}}\right) =6m+s$ for any $1\le s\le 5$, we also have the result in (33). Thus, when $n\ge 6$, we obtain $4B_K^n\left( \left\lfloor \frac{1}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor \right) <n!$. Moreover, when $n=5$, we have $4B_K^5\left( \left\lfloor \frac{1}{3}\left( {\begin{array}{c}5\\ 2\end{array}}\right) -\frac{1}{2}\right\rfloor \right) =4B_K^5(2)=64<5!$. So, when $n\ge 5$, we prove the above lemma. $\square$

By (31) and Lemma 23, we can prove the following theorem.

Theorem 7

Let $n\ge 5$. For any $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right)< 2t+1< \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric. For $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, there exists a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric.

Proof

When $\frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right)< 2t+1< \left( {\begin{array}{c}n\\ 2\end{array}}\right)$, by the above discussion, we have that there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric except for $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. When $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, by (31), we have $A_K(n,2t+1)\le 4$. Furthermore, by Lemma 23, we obtain $A_K(n,2t+1)\cdot B_K^n(t)<n!$ for $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Thus, there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for all $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \frac{2}{3}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. So, when $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right)< 2t+1<\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric. For $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, by Lemmas 2 and 17, we have $A_K(n,d)=2$ and $2B_K^{n}(t)=n!$. Therefore, there exists a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. $\square$

6 Conclusions

Permutation codes under the Kendall $\tau$-metric have attracted lots of research interest due to their applications in flash memories. In this paper, we considered the nonexistence of perfect codes under the Kendalls $\tau$-metric. We gave the polynomial representations of the size of a ball or a sphere with radius r when $t=2,3,4,~\text {or}~5$. Moreover, we presented three sufficient conditions of the nonexistence of perfect permutation codes under the Kendall $\tau$-metric. Finally, we used these sufficient conditions to prove that there does not exist a perfect t-error-correcting code in $S_n$ under the Kendall $\tau$-metric for some n and $t=2,3,4,5$, or $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Specifically, we proved that there does not exist a perfect two-error-correcting code in $S_n$, where $n+2>6$ is a prime. We also proved that there does not exist a perfect three-error-correcting code in $S_n$, where $n+1>6$ is a prime or $n^2+2n-6$ has a prime factor $p>n$ or $4\le n \le 33$. We further proved that there does not exist a perfect four-error-correcting code in $S_n$, where $n+1>6$ or $n+2>7$ is a prime or $n^2+3n-12$ has a prime factor $p>n$ or $5\le n \le 19$. We proved that there does not exist a perfect five-error-correcting code in $S_n$, where $n\ge 16$ or $n+7\ge 12$ is a prime or $n^3+3n^2-6n-28$ has a prime factor $p>n$. For $\frac{5}{8}\left( {\begin{array}{c}n\\ 2\end{array}}\right) < 2t+1\le \left( {\begin{array}{c}n\\ 2\end{array}}\right)$ and $n\ge 5$, we proved that there does not exist a perfect t-error-correcting code in $S_n$ except for $2t+1=\left( {\begin{array}{c}n\\ 2\end{array}}\right)$.

Appendices

Appendix A

The purpose of this appendix is to prove Lemma 21 given in Section 5.2.

Proof

We choose any permutation $\beta \in L_i(\pi )$. Then $\beta$ is obtained by applying some t adjacent transpositions and at most $5-t$ adjacent transpositions on the former $i-1$ elements of $\pi$ and the latter $n-i$ elements of $\pi$, respectively, where $0\le t\le 5$. Thus, these operations can produce $S_{K}^{i-1}(t)B_K^{n-i}(5-t)$ permutations. If $t\ge \left( {\begin{array}{c}i-1\\ \lfloor \frac{i-1}{2}\rfloor \end{array}}\right)$, we have $S_{K}^{i-1}(t)=0$. So, the size of the first kind of permutations is $\sum _{t=0}^{5}S_{K}^{i-1}(t)B_K^{n-i}(5-t)$.

Next, we choose $\pi =[2,1,3,\ldots ,n]\in S_{n,2}$ such that $\pi (i)=i$ for all $i\ge 3$. By Lemma 10, we obtain $R_2=|R_2(\pi )|$. If $\sigma \in R_2(\pi )$, then we have $\sigma (1)=3,4,~\text {or}~5$. When $\sigma (1)=3$, we can obtain that elements 2 and 3 are exchanged and this operation needs at least 3 adjacent transpositions. Then the number of this kind of permutations in $R_2(\pi )$ is $B_K^{n-2}(2)$. When $\sigma (1)=4$, we have that elements 2 and 4 are exchanged and this operation needs at least 4 adjacent transpositions. Hence, the number of this kind of permutations in $R_2(\pi )$ is $B_K^{n-2}(1)$. When $\sigma (1)=5$, we obtain that elements 2 and 5 are exchanged and this operation needs at least 5 adjacent transpositions. Hence, the number of this kind of permutations in $R_2(\pi )$ is $B_K^{n-2}(0)$. So when $i=2$, we obtain that $R_2=B_K^{n-2}(2)+B_K^{n-2}(1)+B_K^{n-2}(0)$. By Lemma 18, when $i=n-1$, we also get $R_{n-1}=B_K^{n-2}(2)+B_K^{n-2}(1)+B_K^{n-2}(0)$.

Similarly, when $i=3$ or $n-2$, we can obtain that $R_i=B_K^{n-3}(2)+3B_K^{n-3}(1)+3$. When $4\le i\le n-3$, we can prove that $R_i=\sum _{t=0}^{2}S_{K}^{i-1}(t)\cdot B_K^{n-i}(2-t)+2\sum _{t=0}^{1}S_{K}^{i-1}(t)B_K^{n-i}(1-t)+2$.$\square$

Appendix B

The purpose of this appendix is to prove Lemma 22 given in Sect. 5.3.

Proof

In order to obtain this result, we first prove that when $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, then

$$\begin{aligned} S_K^{n}(p)+S_K^{n}(q-1)<S_K^n(q)+S_K^n(p-1) \end{aligned}$$

(35)

by induction for all $n\ge 6$.

When $n=6$, we obtain $\left( {\begin{array}{c}6\\ 2\end{array}}\right) =15$. By Lemma 4, we compute $S_K^6(t)$ to obtain that $S_K^6(0)=1,S_K^6(1)=5,S_K^6(2)=14,S_K^6(3)=29,S_K^6(4)=49,S_K^6(5)=71,S_K^6(6)=90,S_K^6(7)=101$. Hence, when $n=6$, we clearly have that $S_K^{6}(p)+S_K^{6}(q-1)<S_K^6(q)+S_K^6(p-1)$ for $1\le p<q\le 7$ and $p+q\le 7$. So when $n=6$, $S_K^6(t)$ satisfies the condition in (35).

Now we assume that $S_K^m(t)$ satisfies the condition in (35) for some integers $m\ge 6$, that is, if $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right)$, then

$$\begin{aligned} S_K^{m}(p)+S_K^{m}(q-1)<S_K^m(q)+S_K^m(p-1). \end{aligned}$$

(36)

When $n=m+1$, by Lemma 4, we obtain

$$\begin{aligned} S_K^{m+1}(q)=S_K^{m+1}(q-1)+S_K^m(q)-S_K^m(q-m-1)\\ S_K^{m+1}(p)=S_K^{m+1}(p-1)+S_K^m(p)-S_K^m(p-m-1) \end{aligned}$$

for $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}m+1\\ 2\end{array}}\right)$. Hence, we have

$$\begin{aligned}&S_K^{m+1}(q)+S_K^{m+1}(p-1)+S_K^m(p)+S_K^m(q-m-1)=S_K^{m+1}(q-1)\nonumber \\&\qquad +S_K^{m+1}(p)+S_K^m(q)+S_K^m(p-m-1). \end{aligned}$$

(37)

Using the induction hypothesis on $S_K^m(q)$, we can obtain some results as follows. When $p\ge m+1$, then $1\le p-m<q$ and $p+q-m-1<\frac{1}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right) -\frac{m}{2}-1$. Thus, by (36), we have

$$\begin{aligned} S_K^m(p-m)+S_K^m(q-1)<S_K^m(q)+S_K^m(p-m-1). \end{aligned}$$

(38)

Since $q-1\ge \max \{p,q-m-1\}$, by (36), then $S_K^m(p)+S_K^m(q-m-1)<S_{K}^m(p-m)+S_K^m(q-1)$. Hence, by (38), we obtain $S_K^m(p)+S_K^m(q-m-1)<S_{K}^m(q)+S_K^m(p-m-1)$.

When $p<m+1$, then $S_K^m(p-m-1)=0$. If $q<m+1$, we also have $S_K^m(q-m-1)=0$. Since $p<q$, then $S_K^m(p)<S_K^m(q)$. If $q\ge m+1$, then $1\le p,q-m$ and $p+q-m<\frac{1}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right) -\frac{m}{2}$. Hence, by (36), we obtain $S_K^m(p)+S_K^m(q-m)\le S_K^m(p+q-m)$. Assume $q\le \frac{1}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right)$, then $p+q-m\le q$. Since $S_K^m(t)$ is an increasing sequence for all $0\le t\le \frac{n}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right)$, then $S_K^m(p+q-m)\le S_K^m(q)$. Assume $\frac{1}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right) <q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}m+1\\ 2\end{array}}\right)$, then $\left( {\begin{array}{c}m\\ 2\end{array}}\right) -q<\frac{1}{2}\left( {\begin{array}{c}m\\ 2\end{array}}\right)$. By Lemma 2, $S_K^m(q)=S_{K}^{m}(\left( {\begin{array}{c}m\\ 2\end{array}}\right) -q)$. Since $p+q-m<\left( {\begin{array}{c}m\\ 2\end{array}}\right) -q<\left( {\begin{array}{c}m\\ 2\end{array}}\right)$, we also have $S_K^m(p)+S_K^m(q-m-1)<S_K^m(p)+S_K^m(q-m)\le S_K^m(p+q-m)<S_K^m(\left( {\begin{array}{c}m\\ 2\end{array}}\right) -q)=S_K^m(q)$. By the above discussion, we always have $S_K^m(p)+S_K^m(q-m-1)<S_K^{m}(q)+S_K^m(p-m-1)$ for $0\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}m+1\\ 2\end{array}}\right)$. By (37), we obtain that

$$\begin{aligned} S_K^{m+1}(q-1)+S_K^{m+1}(p)<S_K^{m+1}(q)+S_K^{m+1}(p-1), \end{aligned}$$

for $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}m+1\\ 2\end{array}}\right)$. So, by induction, if $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$, then

$$\begin{aligned} S_K^{n}(p)+S_K^{n}(q-1)<S_K^n(q)+S_K^n(p-1). \end{aligned}$$

(39)

By (39), we obtain

$$\begin{aligned} S_K^{n}(p+q-t)+S_K^{n}(t)<S_K^{n}(p+q-t+1)+S_K^{n}(t-1) \end{aligned}$$

for all $1\le t\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Hence, we can get

$$\begin{aligned} S_K^{n}(p)+S_K^{n}(q)+p-1<S_K^{n}(p+q)+S_K^{n}(0) \end{aligned}$$

for $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. Since $S_K^{n}(0)=1$, then we have

$$\begin{aligned} S_K^{n}(p)+S_K^{n}(q)+p-2<S_K^{n}(p+q) \end{aligned}$$

for $1\le p<q$ and $p+q\le \frac{1}{2}\left( {\begin{array}{c}n\\ 2\end{array}}\right)$. $\square$