On Bounds And Constructions For Permutation Arrays

A permutation code(array) of length n and minimum distance d, denoted by (n,d)permutation code, is a set of permutations C from some fixed set of n elements such thatthe Hamming distance between distinct members x, y∈C is at least d. Let P(n,d) denotethe maximum size of an (n,d) permutation code. A (n,d) permutation code C such that|C| = P(n,d) is called optimal. The study of the numbers P(n,d) is considered to be theessential problem of permutation code.Permutation codes are somewhat studied in the 1970s. Vinck (Coded modulation forpowerline communications, Proc. Int. J. Elec. Commun., vol. 54, no. 1, 2000) renewedinterest in permutation codes by proposing it as an error correcting code for powerline com-munications. In this paper, we focus on the most essential problems on theory of permutationcodes– the bounds and constructions. Our main results are listed as followed:1. We prove a relation between P(n,d) and PΩ(n,d).2. We give some elementary properties of P(n,d,w), and then use them to show newupper bounds on P(n, 2k) and P(n, 2k + 1). For constantα,βsatisfying certainconditions, whenever d =βnα, the new upper bounds are asymptotically better thanthe previous ones.3. Based on the graph theorem framework presented by Jiang and Vardy, we give threeimprovements over the Gilbert-Varshamov lower bounds on P(n,d).4. By considering the covered balls intersection, we give two improvements over theGilbert-Varshamov lower bounds on P(n,d).5. By presenting constructions of (n-1,d-3) and (n-1,d-2) permutation codes from(n,d) permutation codes, some new lower bounds for permutation codes are given forspecial cases for n and d.6. We present two constructions of permutation codes from factional polynomials overfinite field, which produce some new lower bounds for permutation codes.7. We show a relation between permutation group with degree n and minimal degree dand (n,d) permutation codes, which leads to some new lower bounds for permutationcodes.8. We present three new constructions of permutation codes from binary codes, in whichthe first two constructions lead to some interested inequalities on P(n,d),DP(n,d)and CP(n,d), and the third construction gives larger permutation codes from knownbinary codes using preserve-distance mapping compared to direct construction. 9. The generalized code is the generalized form of concrete code, including permutationcodes, binary codes, et. al.. We give a new simple proof of Gilbert-Varshamov boundfor generalized codes, and present a simple random construction algorithm with lowercomplexity which is proved to obtain large code with significant probability, while theprevious Altruisitic algorithm is too complexity to be realized. Compared with semi-random construction presented by Keevash and Ku, the simple random constructionalgorithm does not require the strict conditions for realization and needs less timewhen it is applied to the constructions of permutation codes.10. The binary code has closed relations with permutation code. We give several newinequalities for distance distributions of binary codes, and presented an new proof ofthe improved Johnson bound which is simpler than the original one.