Linear codes with complementary duals related to the complement of the Higman-Sims graph

Document Type : Research Paper


School of Mathematics‎, ‎Statistics and Computer Science‎, ‎University of KwaZulu-Natal‎, ‎Durban 4000‎, ‎South Africa.


‎In this paper we study codes $C_p(\overline{{\rm HiS}})$ where $p =3,7‎, ‎11$ defined by the 3‎- ‎7‎- ‎and 11-modular representations of the simple sporadic group ${\rm HS}$ of Higman and Sims of degree 100‎. ‎With exception of $p=11$ the codes are those defined by the row span of the adjacency matrix of the complement of the Higman-Sims graph over $GF(3)$ and $GF(7).$ We show that these codes have a similar decoding performance to that of their binary counterparts obtained from the Higman-Sims graph‎. ‎In particular‎, ‎we show that these are linear codes with complementary duals‎, ‎and thus meet the asymptotic Gilbert-Varshamov bound‎. ‎Furthermore‎, ‎using the codewords of weight 30 in $C_p(\overline{{\rm HiS}})$ we determine a subcode of codimension 1‎, ‎and thus show that the permutation module of dimension 100 over the fields of 3‎, ‎7 and 11-elements‎, ‎respectively is the direct sum of three absolutely irreducible modules of dimensions 1‎, ‎22 and 77‎. ‎The latter being also the subdegrees of the orbit decomposition of the rank-3 representation‎.


Main Subjects

E.F. Assmus Jr. and J.D. Key, Designs and Their Codes, Cambridge Tracts in Math. 103, Cambridge Univ. Press, Cambridge, 1992. (Second printing with corrections, 1993).
W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language, J. Symbolic Comput. 24 (1997) 235--265.
A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer-Verlag, New York, 2012.
A.E. Brouwer and C.J. van Eijl, On the p-rank of the adjacency matrices of strongly regular graphs, J. Algebraic Combin. 1 (1992) 329--346.
P.J. Cameron, Permutation Groups, London Math. Soc. Stud. Texts 45, Cambridge Univ. Press, Cambridge, 1999.
P.J. Cameron and J.H. van Lint, Designs, Graphs, Codes and Their Links, London Math. Soc. Stud. Texts 22, Cambridge Univ. Press, Cambridge, 1991.
C. Carlet and S. Guilley, Complementary dual codes for counter-measures to side-channel attacks, Adv. Math. Commun. 10 (2016), no. 1, 131--150
T. Connor and D. Leemans, An atlas of subgroup lattices of finite almost simple groups, 2014,, Accessed on July 2015.
J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker and R.A. Wilson, Atlas of Finite Groups, Oxford Univ. Press, Oxford, 1985.
M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at, 2007, Accessed on 25--03--2016.
P.R. Hafner, On the graphs of Hoffman-Singleton and Higman-Sims, Electron. J. Combin. 11 (2004), no. 1, Paper 77, 33 pages.
C. Jansen, The minimal degrees of faithful representations of the sporadic simple groups and their covering groups, LMS J. Comput. Math. 8 (2005) 122--144.
C. Jansen, K. Lux, R. Parker and R. Wilson, An Atlas of Brauer Characters, Appendix 2 by T. Breuer and S. Norton, London Math. Soc. Monogr. Ser. 11, The Clarendon Press, Oxford Univ. Press, New York, 1995,
M. Klin, C. Rucker, G. Rucker and G. Tinhofer, Algebraic combinatorics in mathematical chemistry. Methods and algorithms. I. Permutation groups and coherent (cellular)
algebras, MATCH Commun. Math. Comput. Chem. 40 (1999) 7--138.
W. Knapp and H.-J. Schaeffer, On the codes related to the Higman-Sims graph, Electron. J. Combin., 22 (2015), no. 1, Paper 1.19, 58 pages.
W. Knapp and P. Schmid, Codes with prescribed permutation group, J. Algebra 67 (1980) 415--435.
K. Lux and H. Pahlings, Representations of Groups: A Computational Approach, Cambridge Univ. Press, Cambridge, 2010.
S.S. Magliveras, The Subgroup Structure of the Higman-Sims Simple group, Bull. Amer. Math. Soc. 77 (1971), no. 4, 535--539.
J. Massey. Linear codes with complementary duals, Disc. Math. 106/107 (1992) 337--342.
The Modular Atlas Homepage, Character tables of endomorphism rings of multiplicity-free permutation modules, mfer/data/HS/HS21:pdf
J. Moori and B.G. Rodrigues, Some self-orthogonal codes related to Higman's geometry, Electron. J. Combin. 23 (2016), no.4, Paper 4.15, 12 pages.
C.E. Praeger and L.H. Soicher, Low rank representations and graphs for sporadic groups Aust. Math. Soc. Lect. Ser. 8, Cambridge Univ. Press, Cambridge, 1997.
N. Sendrier. Linear codes with complementary duals meet the Gilbert-Varshamov bound, Discrete Math., 285 (2004) 345--347.
V.D. Tonchev. Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs, IEEE Trans. Info. Theory, 43 (1997) 1021--1025.
R.A. Wilson. The Finite Simple Groups, Grad. Texts in Math. 251, Springer-Verlag, London, 2009.