Upper Bounds for Chebyshev Permutation Arrays

We improve on known upper bounds for the size of permutation arrays under the Chebyshev metric, defined as follows. The Chebyshev distance between permutations $\pi$ and $\sigma$ on the symbols $\{1,2,\dots ,n\}$, denoted by $d(\pi ,\sigma )$, is $max\left\{\right|{\pi }_i-{\sigma }_i\left|\right|1\le i\le n\}$. For an array A (set) of such permutations, the Chebyshev distance of A, denoted by $d\left(A\right)$, is $min\left\{d\right(\pi ,\sigma \left)\right|\pi ,\sigma \in A,\pi \ne \sigma \}$. An array A of such permutations with $d\left(A\right)=d$ will be called an $(n,d)$-PA. Let $P(n,d)$ denote the maximum size of any $(n,d)$-PA. The function $P(n,d)$ has been the subject of previous research. In this paper, we consider strings on the symbols $\{0,1,2\}$, with the 0’s representing low symbols and the 2’s high symbols for the function $P(n,d)$. An array A of such strings of length n is separable if for any two strings in A, there is a position $1\le i\le n$ such that the $i^{th}$ symbol in one string is 0 and the $i^{th}$ symbol in the other is a 2. The maximum size of a separable array of strings of length n, with a occurrences of the symbol 0 and b occurrences of the symbol 2, is denoted by $R(n;a,b)$. We show that $R(n;k,k)$ is an upper bound for $P(n,n-k)$ when $k\le {\displaystyle \frac{n}{2}}$. We derive upper bounds for $R(n;a,b)$ by various recursive and combinatorial methods, from which follow upper bounds for the Chebyshev function $P(n,d)$, which improve upon previous such upper bounds in the literature.