May  2019, 13(2): 313-328. doi: 10.3934/amc.2019021

Symmetries of weight enumerators and applications to Reed-Muller codes

1. 

Université Paris 8, LAGA, CNRS (UMR 7539), Université Paris 13, Sorbonne Paris Cité, F-93526 Saint-Denis, France

2. 

Universität Bern, Mathematisches Institut (MAI), Sidlerstrasse 5, CH-3012 Bern, Switzerland

Received  May 2018 Published  February 2019

Fund Project: The first author was partially supported by PEPS - Jeunes Chercheur-e-s - 2017

Gleason's 1970 theorem on weight enumerators of self-dual codes has played a crucial role for research in coding theory during the last four decades. Plenty of generalizations have been proved but, to our knowledge, they are all based on the symmetries given by MacWilliams' identities. This paper is intended to be a first step towards a more general investigation of symmetries of weight enumerators. We list the possible groups of symmetries, dealing both with the finite and infinite case, we develop a new algorithm to compute the group of symmetries of a given weight enumerator and apply these methods to the family of Reed-Muller codes, giving, in the binary case, an analogue of Gleason's theorem for all parameters.

Citation: Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
References:
[1] E. F. AssmusJr. and J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9781316529836. Google Scholar
[2]

J. Ax, Zeroes of polynomials over finite fields, Amer. J. Math., 86 (1964), 255-261. doi: 10.2307/2373163. Google Scholar

[3]

I. A. Berchenko and P. J. Olver, Symmetries of polynomials, J. Symb. Comp., 29 (2000), 485-514. doi: 10.1006/S0747-7171(99)90307-3. Google Scholar

[4]

K. Betsumiya and M. Harada, Classification of formally self-dual even codes of lengths up to 16, Des. Codes Cryptogr., 23 (2001), 325-332. doi: 10.1023/A:1011223128089. Google Scholar

[5] H. F. Blichfeldt, Finite Collineation Groups, The Univ. Chicago Press, Chicago, 1917. Google Scholar
[6]

M. Borello, On the automorphism groups of binary linear codes, Topics in Finite Fields, Contemporary Mathematics, 632 (2015), 29-41. doi: 10.1090/conm/632/12617. Google Scholar

[7]

W. BosmaJ. Cannon and C. Playoust, The Magma algebra system Ⅰ: The user language, J. Symbol. Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125. Google Scholar

[8]

N. D. Elkies, Linear codes and algebraic geometry in higher dimensions, Preprint, 2006.Google Scholar

[9]

A. M. Gleason, Weight polynomials of self-dual codes and the MacWilliams identities, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3 (1971), 211–215. Google Scholar

[10] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge university press, Cambridge, 2003. doi: 10.1017/CBO9780511807077. Google Scholar
[11]

N. Kaplan, Rational Point Counts for del Pezzo Surfaces over Finite Fields and Coding Theory, (Doctoral dissertation), Harvard University, 2013, Retrieved from: http://users.math.yale.edu/ nk354/papers/kaplanthesis.pdf. Google Scholar

[12]

G. T. Kennedy, Weight distributions of linear codes and the Gleason-Pierce theorem, J. Combin. Theory Ser. A, 67 (1994), 72-88. doi: 10.1016/0097-3165(94)90004-3. Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Ⅰ. North-Holland Publishing Co., Amsterdam-New York-Oxford. North-Holland Mathematical Library, 1977. Google Scholar

[14]

C. L. Mallows and N. J. A. Sloane, An upper bound for self-dual codes, Information and Control, 22 (1973), 188-200. doi: 10.1016/S0019-9958(73)90273-8. Google Scholar

[15]

O. Mila, Invariance for Weight Enumerators of Evaluation Codes and Counting $ {\mathbb{F}}_q$-rational Points on Hypersurfaces, (Master dissertation), EPFL, 2015, Retrieved from: http://archiveweb.epfl.ch/csag.epfl.ch/files/content/sites/csag/files/MasterOlivierMila.pdf.Google Scholar

[16]

G. Nebe, E. M. Rains and N. J. A. Sloane, Self-dual Codes and Invariant Theory, Vol. 17. Berlin: Springer, 2006. Google Scholar

[17]

E. M. Rains and N. J. A. Sloane, Self-dual codes, In: Pless, V.S., Huffman, W.C. (Eds.), Handbook of Coding Theory, Elsevier, Amsterdam, (2002), 177–294. Google Scholar

[18]

N. Sloane, Is there a (72, 36) d = 16 self-dual code?, IEEE Transactions on Information Theory, 19 (1973), 251-251. doi: 10.1109/tit.1973.1054975. Google Scholar

[19]

N. J. A. Sloane, Gleason's Theorem on self-dual codes and its generalizations, preprint, arXiv: math/0612535.Google Scholar

show all references

References:
[1] E. F. AssmusJr. and J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9781316529836. Google Scholar
[2]

J. Ax, Zeroes of polynomials over finite fields, Amer. J. Math., 86 (1964), 255-261. doi: 10.2307/2373163. Google Scholar

[3]

I. A. Berchenko and P. J. Olver, Symmetries of polynomials, J. Symb. Comp., 29 (2000), 485-514. doi: 10.1006/S0747-7171(99)90307-3. Google Scholar

[4]

K. Betsumiya and M. Harada, Classification of formally self-dual even codes of lengths up to 16, Des. Codes Cryptogr., 23 (2001), 325-332. doi: 10.1023/A:1011223128089. Google Scholar

[5] H. F. Blichfeldt, Finite Collineation Groups, The Univ. Chicago Press, Chicago, 1917. Google Scholar
[6]

M. Borello, On the automorphism groups of binary linear codes, Topics in Finite Fields, Contemporary Mathematics, 632 (2015), 29-41. doi: 10.1090/conm/632/12617. Google Scholar

[7]

W. BosmaJ. Cannon and C. Playoust, The Magma algebra system Ⅰ: The user language, J. Symbol. Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125. Google Scholar

[8]

N. D. Elkies, Linear codes and algebraic geometry in higher dimensions, Preprint, 2006.Google Scholar

[9]

A. M. Gleason, Weight polynomials of self-dual codes and the MacWilliams identities, Actes du Congrès International des Mathématiciens (Nice, 1970), Tome 3 (1971), 211–215. Google Scholar

[10] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge university press, Cambridge, 2003. doi: 10.1017/CBO9780511807077. Google Scholar
[11]

N. Kaplan, Rational Point Counts for del Pezzo Surfaces over Finite Fields and Coding Theory, (Doctoral dissertation), Harvard University, 2013, Retrieved from: http://users.math.yale.edu/ nk354/papers/kaplanthesis.pdf. Google Scholar

[12]

G. T. Kennedy, Weight distributions of linear codes and the Gleason-Pierce theorem, J. Combin. Theory Ser. A, 67 (1994), 72-88. doi: 10.1016/0097-3165(94)90004-3. Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Ⅰ. North-Holland Publishing Co., Amsterdam-New York-Oxford. North-Holland Mathematical Library, 1977. Google Scholar

[14]

C. L. Mallows and N. J. A. Sloane, An upper bound for self-dual codes, Information and Control, 22 (1973), 188-200. doi: 10.1016/S0019-9958(73)90273-8. Google Scholar

[15]

O. Mila, Invariance for Weight Enumerators of Evaluation Codes and Counting $ {\mathbb{F}}_q$-rational Points on Hypersurfaces, (Master dissertation), EPFL, 2015, Retrieved from: http://archiveweb.epfl.ch/csag.epfl.ch/files/content/sites/csag/files/MasterOlivierMila.pdf.Google Scholar

[16]

G. Nebe, E. M. Rains and N. J. A. Sloane, Self-dual Codes and Invariant Theory, Vol. 17. Berlin: Springer, 2006. Google Scholar

[17]

E. M. Rains and N. J. A. Sloane, Self-dual codes, In: Pless, V.S., Huffman, W.C. (Eds.), Handbook of Coding Theory, Elsevier, Amsterdam, (2002), 177–294. Google Scholar

[18]

N. Sloane, Is there a (72, 36) d = 16 self-dual code?, IEEE Transactions on Information Theory, 19 (1973), 251-251. doi: 10.1109/tit.1973.1054975. Google Scholar

[19]

N. J. A. Sloane, Gleason's Theorem on self-dual codes and its generalizations, preprint, arXiv: math/0612535.Google Scholar

Table 1.  $\bar S(w_{\mathcal{RM}_2(r,m)}(x,y))$
$r\backslash m$ 1 2 3 4 5 6 7
0 $\infty$ $D_4$ $D_8$ $D_{16}$ $D_{32}$ $D_{64}$ $D_{128}$
1 $\infty$ $D_4$ $S_4$ $D_{8}$ $D_{16}$ $D_{32}$ $D_{64}$
2 $\infty$ $\infty$ $D_8$ $D_{8}$ $S_4$ $D_{4}$ $D_{8}$
3 $\infty$ $\infty$ $\infty$ $D_{16}$ $D_{16}$ $D_{4}$ $S_4$
4 $\infty$ $\infty$ $\infty$ $\infty$ $D_{32}$ $D_{32}$ $D_{8}$
5 $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $D_{64}$ $D_{64}$
6 $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $D_{128}$
$r\backslash m$ 1 2 3 4 5 6 7
0 $\infty$ $D_4$ $D_8$ $D_{16}$ $D_{32}$ $D_{64}$ $D_{128}$
1 $\infty$ $D_4$ $S_4$ $D_{8}$ $D_{16}$ $D_{32}$ $D_{64}$
2 $\infty$ $\infty$ $D_8$ $D_{8}$ $S_4$ $D_{4}$ $D_{8}$
3 $\infty$ $\infty$ $\infty$ $D_{16}$ $D_{16}$ $D_{4}$ $S_4$
4 $\infty$ $\infty$ $\infty$ $\infty$ $D_{32}$ $D_{32}$ $D_{8}$
5 $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $D_{64}$ $D_{64}$
6 $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $\infty$ $D_{128}$
Table 2.  $\bar S(w_{\mathcal{RM}_3(r,m)}(x,y))$
$r\backslash m$ 1 2 3 4
0 $D_3$ $D_9$ $D_{27}$ $D_{81}$
1 $D_3$ $C_3$ $C_9$ $C_{27}$
2 $\infty$ $C_3$ $C_3$ $C_{3}$
3 $\infty$ $D_9$ $C_3$
4 $\infty$ $\infty$ $C_9$
5 $\infty$ $\infty$ $D_{27}$ $C_{3}$
6 $\infty$ $\infty$ $\infty$ $C_{27}$
7 $\infty$ $\infty$ $\infty$ $D_{81}$
$r\backslash m$ 1 2 3 4
0 $D_3$ $D_9$ $D_{27}$ $D_{81}$
1 $D_3$ $C_3$ $C_9$ $C_{27}$
2 $\infty$ $C_3$ $C_3$ $C_{3}$
3 $\infty$ $D_9$ $C_3$
4 $\infty$ $\infty$ $C_9$
5 $\infty$ $\infty$ $D_{27}$ $C_{3}$
6 $\infty$ $\infty$ $\infty$ $C_{27}$
7 $\infty$ $\infty$ $\infty$ $D_{81}$
Table 3.  $\bar S(w_{\mathcal{RM}_4(r, m)}(x, y))$
$r\backslash m$ 1 2 3
0 $D_8$ $D_{16}$ $D_{64}$
1 $V_4$ $C_4$ $C_{16}$
2 $D_8$ $\{{\rm Id}\}$ $C_4$
3 $\infty$ $\{{\rm Id}\}$ $\{{\rm Id}\}$
4 $\infty$ $C_4$
5 $\infty$ $D_{16}$ $\{{\rm Id}\}$
6 $\infty$ $\infty$ $C_4$
7 $\infty$ $\infty$ $C_{16}$
8 $\infty$ $\infty$ $D_{64}$
$r\backslash m$ 1 2 3
0 $D_8$ $D_{16}$ $D_{64}$
1 $V_4$ $C_4$ $C_{16}$
2 $D_8$ $\{{\rm Id}\}$ $C_4$
3 $\infty$ $\{{\rm Id}\}$ $\{{\rm Id}\}$
4 $\infty$ $C_4$
5 $\infty$ $D_{16}$ $\{{\rm Id}\}$
6 $\infty$ $\infty$ $C_4$
7 $\infty$ $\infty$ $C_{16}$
8 $\infty$ $\infty$ $D_{64}$
[1]

Bram van Asch, Frans Martens. Lee weight enumerators of self-dual codes and theta functions. Advances in Mathematics of Communications, 2008, 2 (4) : 393-402. doi: 10.3934/amc.2008.2.393

[2]

Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333

[3]

Stefka Bouyuklieva, Iliya Bouyukliev. Classification of the extremal formally self-dual even codes of length 30. Advances in Mathematics of Communications, 2010, 4 (3) : 433-439. doi: 10.3934/amc.2010.4.433

[4]

Masaaki Harada, Katsushi Waki. New extremal formally self-dual even codes of length 30. Advances in Mathematics of Communications, 2009, 3 (4) : 311-316. doi: 10.3934/amc.2009.3.311

[5]

Steven T. Dougherty, Joe Gildea, Abidin Kaya, Bahattin Yildiz. New self-dual and formally self-dual codes from group ring constructions. Advances in Mathematics of Communications, 2020, 14 (1) : 11-22. doi: 10.3934/amc.2020002

[6]

Gabriele Nebe, Wolfgang Willems. On self-dual MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 633-642. doi: 10.3934/amc.2016031

[7]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010

[8]

Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041

[9]

Masaaki Harada, Akihiro Munemasa. Classification of self-dual codes of length 36. Advances in Mathematics of Communications, 2012, 6 (2) : 229-235. doi: 10.3934/amc.2012.6.229

[10]

Stefka Bouyuklieva, Anton Malevich, Wolfgang Willems. On the performance of binary extremal self-dual codes. Advances in Mathematics of Communications, 2011, 5 (2) : 267-274. doi: 10.3934/amc.2011.5.267

[11]

Nikolay Yankov, Damyan Anev, Müberra Gürel. Self-dual codes with an automorphism of order 13. Advances in Mathematics of Communications, 2017, 11 (3) : 635-645. doi: 10.3934/amc.2017047

[12]

Masaaki Harada. New doubly even self-dual codes having minimum weight 20. Advances in Mathematics of Communications, 2020, 14 (1) : 89-96. doi: 10.3934/amc.2020007

[13]

Long Yu, Hongwei Liu. A class of $p$-ary cyclic codes and their weight enumerators. Advances in Mathematics of Communications, 2016, 10 (2) : 437-457. doi: 10.3934/amc.2016017

[14]

W. Cary Huffman. Self-dual $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes with an automorphism of prime order. Advances in Mathematics of Communications, 2013, 7 (1) : 57-90. doi: 10.3934/amc.2013.7.57

[15]

Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251

[16]

Hyun Jin Kim, Heisook Lee, June Bok Lee, Yoonjin Lee. Construction of self-dual codes with an automorphism of order $p$. Advances in Mathematics of Communications, 2011, 5 (1) : 23-36. doi: 10.3934/amc.2011.5.23

[17]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[18]

Katherine Morrison. An enumeration of the equivalence classes of self-dual matrix codes. Advances in Mathematics of Communications, 2015, 9 (4) : 415-436. doi: 10.3934/amc.2015.9.415

[19]

Minjia Shi, Daitao Huang, Lin Sok, Patrick Solé. Double circulant self-dual and LCD codes over Galois rings. Advances in Mathematics of Communications, 2019, 13 (1) : 171-183. doi: 10.3934/amc.2019011

[20]

Suat Karadeniz, Bahattin Yildiz. New extremal binary self-dual codes of length $68$ from $R_2$-lifts of binary self-dual codes. Advances in Mathematics of Communications, 2013, 7 (2) : 219-229. doi: 10.3934/amc.2013.7.219

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (53)
  • HTML views (291)
  • Cited by (0)

Other articles
by authors

[Back to Top]