On the existence of PD-sets: Algorithms arising from automorphism groups of codes

Nicola Pace; Angelo Sonnino

doi:10.3934/amc.2020065

Article Contents

2021, Volume 15, Issue 2: 267-277. Doi: 10.3934/amc.2020065

This issue Previous Article Verifying solutions to LWE with implications for concrete security Next Article Two classes of near-optimal codebooks with respect to the Welch bound

On the existence of PD-sets: Algorithms arising from automorphism groups of codes

Nicola Pace^1, , and
Angelo Sonnino^2,

1.
Chair of Operations Research - Technische Universität München, Arcisstr. 21, 80333 Munich, Germany
2.
Dipartimento di Matematica, Informatica ed Economia - Università degli Studi della Basilicata, Viale dell'Ateneo Lucano, 10, 85100 Potenza, Italy

^* Corresponding author: Nicola Pace
^* Corresponding author: Nicola Pace

Received: February 2017

Revised: June 2018

Early access: January 2020

Published: May 2021

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

This paper deals with the problem of determining whether a PD-set exists for a given linear code $ \mathcal C $ and information set $ I $. A computational approach is proposed and illustrated with two exceptional codes with automorphism groups isomorphic to the sporadic simple groups $ \mathrm{M}_{12} $ and $ \mathrm{M}_{22} $, respectively. In both cases, the existence of a PD–set is proven. In general, the algorithm works well whenever the code $ \mathcal C $ has a very large automorphism group.

Keywords:

Mathematics Subject Classification: Primary: 94B05, 94B35; Secondary: 20B25.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	R. Abbott, J. Bray, S. Linton, S. Nickerson, S. Norton, R. Parker, I. Suleiman, J. Tripp, P. Walsh and R. Wilson, Atlas of finite group representations - version 3, http://brauer.maths.qmul.ac.uk/Atlas/.
[2]	J. Bierbrauer, S. Marcugini and F. Pambianco, The Pace code, the Mathieu group ${M}_12$ and the small Witt design ${S}(5, 6, 12)$, Discrete Math., 340 (2017), 1187-1190. doi: 10.1016/j.disc.2016.12.018.
[3]	W. Bosma, J. J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[4]	M. Braun, A. Kohnert and A. Wassermann, Optimal linear codes from matrix groups, IEEE Trans. Inform. Theory, 51 (2005), 4247-4251. doi: 10.1109/TIT.2005.859291.
[5]	W. Burnside, Theory of Groups of Finite Order, 2nd edition, Cambridge University Press, Cambridge, 1911. doi: 10.1017/CBO9781139237253.
[6]	P. Camion, Linear codes with given automorphism groups, Discrete Math., 3 (1972), 33-45. doi: 10.1016/0012-365X(72)90023-4.
[7]	H. Chabanne, Permutation decoding of abelian codes, IEEE Trans. Inform. Theory, 38 (1992), 1826-1829. doi: 10.1109/18.165460.
[8]	A. Cossidente, C. Nolè and A. Sonnino, Cap codes arising from duality, Bull. Inst. Combin. Appl., 67 (2013), 33-42.
[9]	A. Cossidente and A. Sonnino, A geometric construction of a $[110, 5, 90]_9$–linear code admitting the Mathieu group ${M}_11$, IEEE Trans. Inform. Theory, 54 (2008), 5251-5252. doi: 10.1109/TIT.2008.929966.
[10]	A. Cossidente and A. Sonnino, Finite geometry and the Gale transform, Discrete Math., 310 (2010), 3206-3210. doi: 10.1016/j.disc.2009.08.019.
[11]	A. Cossidente and A. Sonnino, Some recent results in finite geometry and coding theory arising from the Gale transform, Rend. Mat. Appl. (7), 30 (2010), 67-76.
[12]	A. Cossidente and A. Sonnino, Linear codes arising from the Gale transform of distinguished subsets of some projective spaces, Discrete Math., 312 (2012), 647-651. doi: 10.1016/j.disc.2011.05.022.
[13]	A. Cossidente and A. Sonnino, On graphs and codes associated to the sporadic simple groups HS and ${M}_{22}$, Australas. J. Combin., 60 (2014), 208-216.
[14]	D. Crnković, S. Rukavina and L. Simčić, Binary doubly-even self-dual codes of length 72 with large automorphism groups, Math. Commun., 18 (2013), 297-308.
[15]	W. Fish, Binary codes and partial permutation decoding sets from the Johnson graphs, Graphs Combin., 31 (2015), 1381-1396. doi: 10.1007/s00373-014-1485-2.
[16]	W. Fish, J. D. Key and E. Mwambene, Partial permutation decoding for simplex codes, Adv. Math. Commun., 6 (2012), 505-516. doi: 10.3934/amc.2012.6.505.
[17]	W. Fish, K. Kumwenda and E. Mwambene, Codes related to line graphs of triangular graphs and permutation decoding, Quaest. Math., 35 (2012), 489-505. doi: 10.2989/16073606.2012.742287.
[18]	M. Giulietti, G. Korchmáros, S. Marcugini and F. Pambianco, Transitive $A_6$-invariant $k$-arcs in $PG(2, q)$, Des. Codes Cryptogr., 68 (2013), 73-79. doi: 10.1007/s10623-012-9619-0.
[19]	D. M. Gordon, Minimal permutation sets for decoding the binary Golay codes, IEEE Trans. Inform. Theory, 28 (1982), 541-543. doi: 10.1109/TIT.1982.1056504.
[20]	M. Grassl, Bounds on the Minimum Distance of Linear Codes and Quantum Codes, Online available at http://www.codetables.de. Accessed on January 3, 2020.
[21]	R. Hill, On the largest size of cap in $s_{5, 3}$, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur., 54 (1974), 378-384.
[22]	R. Hill, A First Course in Coding Theory, Oxford Applied Mathematics and Computing Science Series, The Clarendon Press, Oxford University Press, New York, 1986.
[23]	W. C. Huffman, Codes and groups, in Handbook of Coding Theory (eds. V. S. Pless and W. C. Huffman), vol. 2, part 2, North-Holland, Amsterdam, 1998, chapter 17, 1345–1440.
[24]	L. Indaco and G. Korchmáros, 42-arcs in $PG(2, q)$ left invariant by $PSL(2, 7)$, Des. Codes Cryptogr., 64 (2012), 33-46. doi: 10.1007/s10623-011-9532-y.
[25]	J. D. Key, Permutation decoding for codes from designs, finite geometries and graphs, in Information Security, Coding Theory and Related Combinatorics (eds. D. Crnkovič and V. Tonchev), vol. 29 of NATO Sci. Peace Secur. Ser. D Inf. Commun. Secur., IOS, Amsterdam, 2011,172–201.
[26]	J. D. Key and J. Limbupasiriporn, Permutation decoding of codes from Paley graphs, Congr. Numer., 170 (2004), 143-155.
[27]	J. D. Key, T. P. McDonough and V. C. Mavron, Partial permutation decoding for codes from finite planes, European J. Combin., 26 (2005), 665-682. doi: 10.1016/j.ejc.2004.04.007.
[28]	J. D. Key, T. P. McDonough and V. C. Mavron, Information sets and partial permutation decoding for codes from finite geometries, Finite Fields Appl., 12 (2006), 232-247. doi: 10.1016/j.ffa.2005.05.007.
[29]	J. D. Key, J. Moori and B. G. Rodrigues, Permutation decoding for the binary codes from triangular graphs, European J. Combin., 25 (2004), 113-123. doi: 10.1016/j.ejc.2003.08.001.
[30]	J. D. Key, J. Moori and B. G. Rodrigues, Binary codes from graphs on triples and permutation decoding, Ars Combin., 79 (2006), 11-19.
[31]	J. D. Key, J. Moori and B. G. Rodrigues, Partial permutation decoding of some binary codes from graphs on triples, Ars Combin., 91 (2009), 363-371.
[32]	J. D. Key, J. Moori and B. G. Rodrigues, Codes associated with triangular graphs and permutation decoding, Int. J. Inf. Coding Theory, 1 (2010), 334-349. doi: 10.1504/IJICOT.2010.032547.
[33]	J. D. Key and B. G. Rodrigues, Codes from lattice and related graphs, and permutation decoding, Discrete Appl. Math., 158 (2010), 1807-1815. doi: 10.1016/j.dam.2010.07.003.
[34]	J. D. Key and P. Seneviratne, Binary codes from rectangular lattice graphs and permutation decoding, European J. Combin., 28 (2007), 121-126. doi: 10.1016/j.ejc.2005.09.001.
[35]	J. D. Key and P. Seneviratne, Permutation decoding for binary codes from lattice graphs, Discrete Math., 308 (2008), 2862-2867. doi: 10.1016/j.disc.2006.06.049.
[36]	W. Knapp and H.-J. Schaeffer, On the codes related to the Higman-Sims graph, Electron. J. Combin., 22 (2015), Paper 1.19, 58 pp.
[37]	W. Knapp and P. Schmid, Codes with prescribed permutation group, J. Algebra, 67 (1980), 415-435. doi: 10.1016/0021-8693(80)90169-6.
[38]	A. Kohnert, Constructing two-weight codes with prescribed groups of automorphisms, Discrete Appl. Math., 155 (2007), 1451-1457. doi: 10.1016/j.dam.2007.03.006.
[39]	A. Kohnert and A. Wassermann, Construction of binary and ternary self-orthogonal linear codes, Discrete Appl. Math., 157 (2009), 2118-2123. doi: 10.1016/j.dam.2007.10.030.
[40]	A. Kohnert and J. Zwanzger, New linear codes with prescribed group of automorphisms found by heuristic search, Adv. Math. Commun., 3 (2009), 157-166. doi: 10.3934/amc.2009.3.157.
[41]	G. Korchmáros and N. Pace, Infinite family of large complete arcs in $ {\rm{PG}} (2, q^n)$, with $q$ odd and $n>1$ odd, Des. Codes Cryptogr., 55 (2010), 285-296. doi: 10.1007/s10623-009-9343-6.
[42]	H.-J. Kroll and R. Vincenti, PD-sets for the codes related to some classical varieties, Discrete Math., 301 (2005), 89-105. doi: 10.1016/j.disc.2004.11.020.
[43]	H.-J. Kroll and R. Vincenti, Antiblocking systems and PD-sets, Discrete Math., 308 (2008), 401-407. doi: 10.1016/j.disc.2006.11.056.
[44]	H.-J. Kroll and R. Vincenti, PD-sets for binary RM-codes and the codes related to the Klein quadric and to the Schubert variety of $ \rm PG(5, 2)$, Discrete Math., 308 (2008), 408-414. doi: 10.1016/j.disc.2006.11.057.
[45]	F. J. MacWilliams, Permutation decoding of systematic codes, Bell System Tech. J., 43 (1964), 485-505. doi: 10.1002/j.1538-7305.1964.tb04075.x.
[46]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. I, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977, North-Holland Mathematical Library, Vol. 16.
[47]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. II, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977, North-Holland Mathematical Library, Vol. 16.
[48]	P. M. Neumann, A lemma that is not Burnside's, Math. Sci., 4 (1979), 133-141.
[49]	N. Pace, New ternary linear codes from projectivity groups, Discrete Math., 331 (2014), 22-26. doi: 10.1016/j.disc.2014.04.027.
[50]	N. Pace, On small complete arcs and transitive $A_5$-invariant arcs in the projective plane $PG(2, q)$, J. Combin. Des., 22 (2014), 425-434. doi: 10.1002/jcd.21372.
[51]	N. Pace and A. Sonnino, On linear codes admitting large automorphism groups, Des. Codes Cryptogr., 83 (2017), 115-143. doi: 10.1007/s10623-016-0207-6.
[52]	B. G. Rodrigues, Self-orthogonal designs and codes from the symplectic groups $s4(3)$ and $s4(4)$, Discrete Math., 308 (2008), 1941-1950. doi: 10.1016/j.disc.2007.04.047.
[53]	P. Seneviratne, Codes associated with circulant graphs and permutation decoding, Des. Codes Cryptogr., 70 (2014), 27-33. doi: 10.1007/s10623-012-9637-y.
[54]	A. Sonnino, Transitive PSL(2, 7)-invariant 42-arcs in 3-dimensional projective spaces, Des. Codes Cryptogr., 72 (2014), 455-463. doi: 10.1007/s10623-012-9778-z.
[55]	B. Stroustrup, The C++ Programming Language, 4th edition, Addison-Wesley, Upper Saddle River, NJ, 2013.
[56]	L. M. G. M. Tolhuizen and W. J. van Gils, A large automorphism group decreases the number of computations in the construction of an optimal encoder/decoder pair for a linear block code, IEEE Trans. Inform. Theory, 34 (1988), 333-338. doi: 10.1109/18.2646.
[57]	J. Wolfmann, A permutation decoding of the (24, 12, 8) Golay code, IEEE Trans. Inform. Theory, 29 (1983), 748-750. doi: 10.1109/TIT.1983.1056726.