Constructing Permutation Arrays of Known Distance

Abstract

A permutation array (PA) is a set of permutations on n symbols. A PA is said to have distance d (under some metric) if every pair of distinct permutations in the array has distance at least d. Commonly used distance metrics include Hamming distance and Chebyshev distance. PAs of a known distance can be used to construct error-correcting codes and have applications in communication over noisy channels. Let M (n, d) represent the maximum size of a permutation array on n symbols with pairwise Hamming distance d. Let P (n, d) represent the maximum size of a permutation array on n symbols with pairwise Chebyshev distance d. Exact values of M (n, d) and P (n, d) are unknown for most values n and d with the exception of some special cases. While combinatorial upper and lower bounds exist for both M (n, d) and P (n, d), these can often be improved through empirical techniques. We present several such techniques to construct PAs under the Hamming and Chebyshev distance metrics, resulting in improved bounds for both M (n, d) and P (n, d).