Symmetries of weight enumerators and applications to Reed-Muller codes

Martino Borello; Olivier Mila

doi:10.3934/amc.2019021

Article Contents

2019, Volume 13, Issue 2: 313-328. Doi: 10.3934/amc.2019021

This issue Previous Article Further results on optimal $ (n, \{3, 4, 5\}, \Lambda_a, 1, Q) $-OOCs Next Article Constructions of optimal balanced $ (m, n, \{4, 5\}, 1) $-OOSPCs

Symmetries of weight enumerators and applications to Reed-Muller codes

Martino Borello^1, and
Olivier Mila^2,

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: April 30, 2018

Published: January 2019

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

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94B05; Secondary: 13A50, 94B60.

Citation:

Full Text(HTML)

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}$

| Show Table

DownLoad: CSV

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}$

| Show Table

DownLoad: CSV

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}$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	E. F. Assmus, Jr. and J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9781316529836.
[2]	J. Ax, Zeroes of polynomials over finite fields, Amer. J. Math., 86 (1964), 255-261. doi: 10.2307/2373163.
[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.
[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.
[5]	H. F. Blichfeldt, Finite Collineation Groups, The Univ. Chicago Press, Chicago, 1917.
[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.
[7]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system Ⅰ: The user language, J. Symbol. Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[8]	N. D. Elkies, Linear codes and algebraic geometry in higher dimensions, Preprint, 2006.
[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.
[10]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge university press, Cambridge, 2003. doi: 10.1017/CBO9780511807077.
[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.
[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.
[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.
[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.
[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.
[16]	G. Nebe, E. M. Rains and N. J. A. Sloane, Self-dual Codes and Invariant Theory, Vol. 17. Berlin: Springer, 2006.
[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.
[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.
[19]	N. J. A. Sloane, Gleason's Theorem on self-dual codes and its generalizations, preprint, arXiv: math/0612535.