×

A bound on permutation codes. (English) Zbl 1295.05007

Summary: Consider the symmetric group \(S_n\) with the Hamming metric. A permutation code on \(n\) symbols is a subset \(C\subseteq S_n.\) If \(C\) has minimum distance \(\geq n-1,\) then \(| C|\leq n^2-n.\) Equality can be reached if and only if a projective plane of order \(n\) exists. Call \(C\) embeddable if it is contained in a permutation code of minimum distance \(n-1\) and cardinality \(n^2-n.\) Let \(\delta =\delta (C)=n^2-n-| C|\) be the deficiency of the permutation code \(C\subseteq S_n\) of minimum distance \(\geq n-1.\)We prove that \(C\) is embeddable if either \(\delta\leq 2\) or if \((\delta^2-1)(\delta +1)^2<27(n+2)/16.\) The main part of the proof is an adaptation of the method used to obtain the famous Bruck completion theorem for mutually orthogonal Latin squares.

MSC:

05A05 Permutations, words, matrices
05B40 Combinatorial aspects of packing and covering
51E26 Other finite linear geometries
94B60 Other types of codes
PDFBibTeX XMLCite
Full Text: Link

References:

[1] J. Bierbrauer, S. Black and Y. Edel: Some t-homogeneous sets of permutations, Designs, Codes and Cryptography 9 (1996), 29-38. · Zbl 0859.05033
[2] J. Bierbrauer and Y. Edel: Theory of perpendicular arrays, Journal of Combinatorial Designs 6 (1994), 375-406. the electronic journal of combinatorics 20(3) (2013), #P611 · Zbl 0824.05011
[3] M. Bogaerts: Isometries and construction of permutation arrays, IEEE IT Transactions 56 (2010), 3177-3179. · Zbl 1366.94659
[4] R. H. Bruck: Finite nets II. Uniqueness and embedding, Pacific J. Math. 13 (1963), 421-457. · Zbl 0124.00903
[5] W. Chu, C. Colbourn, P. Dukes: Constructions for permutation codes in powerline communications, Designs, Codes and Cryptography 32 (2004), 51-64. · Zbl 1065.94003
[6] H.C. Ferreira, A.J.H. Vinck: Inference cancellation with permutation trellis arrays, Proc. IEEE Vehtcular Technology Conf. 2000, 2401-2407.
[7] S. Huczynska: Powerline communication and the 36 officers problem, Phil. Trans.R. Soc.A 364 (2006), 3199-3214. · Zbl 1152.05301
[8] I. Janiszczak, R. Staszewski: An improved bound for permutation arrays of length 10, manuscript.
[9] T. Kløve, Classification of permutation codes of length 6 and minimum distance 5, Internat. Symposium on Info. Theory and its Applications, Honolulu 2000, 465-468.
[10] T. Kløve: A combinatorial problem motivated by a data transmission application, Chapman and Hall/ CRC Press 2004.
[11] Bill Martin and B.E. Sagan: A new notion of transitivity for groups and sets of permutations, Journal of the London Mathematical Society 73 (2006), 1-13. · Zbl 1089.05079
[12] K. Metsch: Improvement of Bruck’s completion theorem, Designs, Codes and Cryptography 1 (1991), 99-116. · Zbl 0760.05012
[13] J. Quistorff: A survey on packing and covering problems in the Hamming permutation space, Electron. J. Comb. (2006), A1. · Zbl 1099.05022
[14] D.R. de la Torre, C.J. Colbourn, A.C.H. Ling: An application of permutation arrays to block ciphers, Congr. Numer. 145 (2000), 5-7. · Zbl 0976.05015
[15] A.J. Han Vinck: Codes modulation for powerline communications, AE Internat. Journal of Electronics and Commun. 54 (2000), 45-49.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.