Permutation Arrays with Large Hamming Distance




Journal Title

Journal ISSN

Volume Title



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.



Permutations, Magic squares, Kronecker products, Tiling (Mathematics), Coding theory


Copyright ©2017 is held by the author. Digital access to this material is made possible by the Eugene McDermott Library. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.