Permutation Arrays with Large Hamming Distance

A permutation array (PA) is a set of permutations on a set Z_n = {0,1,...n-1} symbols. The Hamming distance between a pair of permutations in a PA is the number of disagreements between them. The Hamming distance of a PA A, denoted by hd(A)=d is the minimum Hamming distance between any pair of permutations in A. Let M(n,d) represent the maximum number of permutations on Z_n symbols with Hamming distance d. Except for special cases, M(n,d) is unknown. However, there exist combinatorial upper and lower bounds for M(n,d). We present several techniques aimed to improve existing lower bounds for M(n,d) as well as constructive methods to create new PAs.

The techniques are based on a) the idea of extending or increasing the number of symbols of known PAs, b) the contraction of existing PAs or reduction on the number of symbols of existing PAs, c) the search of permutation group cosets, d) a modified version of the Kronecker Product and e) the re-arrangement of multiple copies of PAs in a technique called tiling and its special case called doubling.