Linear codes invariant under a linear endomorphism

Hassan Ou-azzou; Mustapha Najmeddine; Nuh Aydin; Peihan Liu; Brahim Ialou; El Mahdi Mouloua

doi:10.3934/amc.2024018

Article Contents

2025, Volume 19, Issue 2: 676-697. Doi: 10.3934/amc.2024018

This issue Previous Article New self-dual codes from TGRS codes with general $ \ell $ twists Next Article Endomorphism rings of supersingular elliptic curves over $ \mathbb{F}_p $ and binary quadratic forms

Linear codes invariant under a linear endomorphism

1.
Department of Mathematics, ENSAM–Meknes, Moulay Ismail University, Morocco
2.
Department of Mathematics, Kenyon College, Gambier, OH 43022, USA
3.
John A. Paulson School Of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02134, USA

^*Corresponding author: Hassan Ou-azzou
^*Corresponding author: Hassan Ou-azzou

Received: September 2023

Revised: January 2024

Early access: May 2024

Published: April 2025

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

Abstract

This paper deals with linear codes invariant under an endomorphism $ T, $ that we call $ T $-codes. Since any endomorphism can be represented by a matrix when a basis is fixed, we shall, for simplicity, consider linear codes invariant under right multiplication by a square matrix $ M \in \mathbb{M}_{n}( \mathbb{F}_{_q}) $, and we call them $ M $-codes. In particular, we distinguish three fundamental types: $ M $-cyclic codes, quasi $ M $-cyclic codes, and $ (M_1, M_2, \dots, M_r) $-multi-cyclic codes. The approach developed here allows us to realize cyclic codes and many of their generalizations as special cases. It also helps us better understand the structure of linear codes invariant under some special matrices, such as a permutation matrix or a monomial matrix. Next, we study the duality of $ M $-codes, where we show that the $ b $-dual of an $ M $-code is an $ M^{^{*}} $-code, where $ M^{^{*}} $ represents the adjoint matrix of $ M $ for a non-degenerate bilinear form $ b $, and we explore some important results on the duality of these codes. In order to use polynomial rings in the study of $ M $-codes, we establish a one-to-one correspondence between $ M $-codes and $ \mathbb{F}_{_q}[x] $-submodules of $ \prod_{i = 1}^{r}R_{_{f_i}}, $ where $ R_{_{f_i}} : = \mathbb{F}_{_q}[x]/\langle f_{i}(x)\rangle $ and $ ( f_{_1}(x), f_{_{2}}(x), \ldots, f_{_r}(x) ) $ is the sequence of invariant factors of $ M $. Finally, we investigate the structure of 1-generator $ M $-codes and provide BCH-like and Hartmann-Tzeng-like bounds for them. We construct optimal linear and new quantum codes by applying the method developed in this article.

Keywords:

Mathematics Subject Classification: Primary: 94Bxx, 94B15, 94B65, 11T71, 15-XX, 05-XX.

Citation:

Full Text(HTML)

Table 1. Some optimal or best known $f$-cyclic codes over $\mathbb{F}_{2} $

Parameters	Generator polynomial
$ [50, 3, 28]_2 $	$ x^{47} + x^{44} + x^{43} + x^{42} + x^{40} + x^{37} + x^{36} + x^{34} + x^{33} + x^{32} + x^{31} + x^{28} + x^{27} + x^{25} + x^{24} x^{21} + x^{19} + x^{16} + x^{14} + x^{12} + x^{9} + x^{8} + x^{7} + x^{6} + x^{4} + x^{3} + x^{2} + 1 $
$ [50, 28, 8]_2 $	$x^{22} + x^{21} + x^{20} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{10} + x^{9} + x^{7} + x^{6} + x^{3} + x^{2} + 1$
$[50, 34, 6]_2 $	$x^{16} + x^{12} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x + 1 $
$[50 , 35, 6]_2 $	$x^{15} + x^{14} + x^{13} + x^{12} + x^8 + x^5 + x^3 + 1$
$ [50, 36, 6]_2 $	$ x^{14} + x^{13} + x^{12} + x^{11} + x^{9} + x^{5} + x^{2} + 1 $
$[50, 39, 4]_2 $	$x^{11} + x^{10} + x^9 + x^5 + x^4 + x^2 + x + 1$
$ [50, 40, 4]_2 $	$ x^{10} + x^6 + x^5 + x^3 + x^2 + 1 $
$ [50, 41, 4]_2 $	$ x^9 + x^8 + x^7 + x^6 + x^4 + x^3 + x + 1 $
$[50, 42, 4]_2 $	$x^8 + x^6 + x^3 + 1$
$ [ 50, 43, 4]_2 $	$ x^7 + x^6 + x^5 + 1 $
$ [50, 45, 2]_2 $	$ x^5 + x^4 + x^2 + 1 $
$ [50, 46, 2]_2 $	$ x^4 + x + 1 $
$ [50, 47, 2]_2 $	$ x^3 + x^2 + x + 1 $
$ [50, 49, 2]_2 $	$ x + 1 $

| Show Table

DownLoad: CSV

Table 2. Examples of best known linear codes, generated by $\langle f_1(x), f_2(x), ... \rangle$ with some additional desired properties

$[n, k, d]$	$f_i(x)$
$[36, 18, 8]_2^r$	$f_1=x^{13} + x^{11} + x^{10} + x^9 + x^2 + x + 1$, $f_2=x^{15} + x^{11} + x^8 + x^5 + x^3$
$[52, 26, 10]_2^L$	$ f_1=x^{22} + x^{19} + x^{18} + x^{17} + x^{15} + x^{13} + x^9 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$, $f_2=x^{24} + x^{18} + x^{17} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^7 + x^6 + x^4 + x^2 + x$
$[12, 6, 6]_3^*$	$f_1=x^5 + x^4 + x^3 + x^2 + x$, $f_2=2x^5 + 2x^3 + 2x^2 + 2x$
$[18, 6, 9]_3^\circ$	$f_1=2x^5 + x^4 + x^3 + x$ $f_2=2x^3 + 2x^2$, $f_3= 2x^5 + x^3 + 2x^2$, $f_4=x^4 + 2x^3 + x + 2$, $f_5=2x^4 + 2x + 2$, $f_6=2x^5 + 2x^4 + x^2 + x + 1$
$[20, 5, 12]_3^\circ$	$f_1= 2x^4 + 2$ $f_2=2x^3 + x^2 + 1$, $f_3= 2x^4 + x^3 + x^2 + 2x + 1$, $f_4=x^3 + x$, $f_5=2x^2 + x + 2$, $f_6=x^2$
$[14, 7, 6]_5$	$f_1= 3x^{10} + 4x^9 + x^7 + 2x^5 + 3x^4 + 2x^2 + x + 3$ $f_2=4x^{10} + x^8 + 2x^7 + x^5 + 2x^4 + x^2 + 4x + 2$
$[22, 11, 8]_5$	$f_1= 2x^5 + 2x^4 + 4x^3 + 4x^2 + 4x + 3$, $f_2=4x^6 + 3x^5 + 3x^4 + x^3 + 3x^2 + 3x + 1$

| Show Table

DownLoad: CSV

Table 3. Examples of best known linear codes, generated by $\langle g(x)\rangle$ with some additional desired properties

$[n, k, d]$	$f(x)$	$g(x)$
$[32, 26, 4]_5^L$	$2x^{32} + 2x^{31} + 3x^{30} + 3x^{29} + 2x^{27} + 4x^{26} + 2x^{25} + 4x^{24} + 2x^{23} + x^{22} + 3x^{21} + 4x^{20} + 4x^{19} + 4x^{18} + x^{17} + 2x^{15} + 2x^{12} +3x^{11} + 3x^{10} + 2x^8 + 4x^7 + x^6 + 4x^5 + 2x^4 + 4x^3 + x^2 + 1$	$ x^6 + x^5 + 4x^3 + 4x^2 + 4$
$[33, 27, 4]_5$	$x^{33} + x^{32} + 2x^{31} + 2x^{30} + 2x^{29} + 4x^{28} + x^{27} + 2x^{26} + 2x^{25} +4x^{24} + x^{23} + x^{22} + 4x^{21} + 2x^{20} + 2x^{18} + 2x^{17} + 2x^{16} + 3x^{15} +3x^{13} + 4x^{11} + 2x^{10} + 4x^9 + 3x^8 + x^6 + 4x^5 + 2x^4 + x^3 + 2x^2+ 3x + 3$	$ x^6 + 2x^4 + 2x^2 + x + 4$
$[33, 29, 3]_5^L$	$x^{33} + x^{32} + 2x^{31} + 2x^{30} + 2x^{29} + 4x^{28} + x^{27} + 2x^{26} + 2x^{25} +4x^{24} + x^{23} + x^{22} + 4x^{21} + 2x^{20} + 2x^{18} + 2x^{17} + 2x^{16} + 3x^{15} +3x^{13} + 4x^{11} + 2x^{10} + 4x^9 + 3x^8 + x^6 + 4x^5 + 2x^4 + x^3 + 2x^2+ 3x + 3$	$ x^4 + 3x^3 + 4x^2 + x + 2$
$[36, 30, 4]_5$	$4x^{36} + x^{34} + 2x^{33} + x^{32} + 4x^{31} + x^{30} + 4x^{29} + 2x^{28} + 3x^{27} +2x^{26} + 2x^{25} + x^{23} + 4x^{21} + x^{20} + x^{19} + 2x^{18} + x^{16} + x^{15} + 3x^{14} + 4x^{13} + x^{12} + 3x^{11} + 3x^{10} + 3x^9 + 3x^8 + 4x^6 + 3x^5 + x^4 + 2x^3 + x + 3$	$ x^6 + x^2 + x + 4$
$[38, 34, 3]_5^L$	$2x^{38} + 3x^{37} + x^{36} + 3x^{35} + 3x^{34} + 3x^{33} + 3x^{32} + 2x^{30} + 2x^{29} + x^{28} + x^{27} + 4x^{26} + 3x^{24} + 4x^{23} + x^{22} + x^{20} + 3x^{18} + 4x^{17} + 4x^{16} + 4x^{13} + 2x^{12} + 4x^9 + x^7 + 3x^6 + 2x^5 + 3x^4 + 4x + 4$	$x^4 + x^3 + 4x^2+ x + 2$
$[38, 32, 4]_5^L$	$2x^{38} + 3x^{37} + x^{36} + 3x^{35} + 3x^{34} + 3x^{33} + 3x^{32} + 2x^{30} + 2x^{29} + x^{28} + x^{27} + 4x^{26} + 3x^{24} + 4x^{23} + x^{22} + x^{20} + 3x^{18} + 4x^{17} + 4x^{16} + 4x^{13} + 2x^{12} + 4x^9 + x^7 + 3x^6 + 2x^5 + 3x^4 + 4x + 4$	$ x^6 +3x^5 + x^4 + 3x^3 + 4x^2 + 3$
$[38, 26, 7]_5^L$	$2x^{38} + 3x^{37} + x^{36} + 3x^{35} + 3x^{34} + 3x^{33} + 3x^{32} + 2x^{30} + 2x^{29} + x^{28} + x^{27} + 4x^{26} + 3x^{24} + 4x^{23} + x^{22} + x^{20} + 3x^{18} + 4x^{17} + 4x^{16} + 4x^{13} + 2x^{12} + 4x^9 + x^7 + 3x^6 + 2x^5 + 3x^4 + 4x + 4$	$ x^{12} + 2x^{10} + x^9 + 4*x^8 + x^7 + 2x^6 + x^5 + 4x^4 + 3x^3 + 2x + 4$

| Show Table

DownLoad: CSV

Table 4. New quantum codes from polycyclic codes

$[[n, k, d]]_{q}$	Ref.	Multinomial	$g_1$	$h_2$
$*[[30, 28, 2]]_{5}$	[8,13]	$3x^{30} + 3x^{29} + 3x^{28} + 2x^{27} + 4x^{26} + 2x^{25} + 3x^{24} + x^{23} + 2x^{22} + x^{20} + 3x^{19} + 2x^{17} + x^{15} + 2x^{14} + 3x^{13} + 2x^{12} + 3x^{11} +3x^{10} + 4x^9 + 2x^8 + x^5 +3x^4 + 2x^3 + 4x + 4.$	$x^3 + 3x^2 + 4x + 3.$	$x^{29} + 4x^{28} + 3x^{27} + 3x^{26} + 2x^{25} + x^{23} + 4x^{21} + 2x^{20} + 3x^{19} + 4x^{16} + 2x^{15} + 3x^{14} + 3x^{13} + 4x^{11} + 3x^{10} + 3x^8 + 3x^7 + 4x^6 + 2x^5 + 3x^4 + 4x^2 + 2x + 4.$
$[[33, 14, 4]]_{5}$	[8,13]	$4x^{33} + 4x^{32} + x^{30} + 2x^{29} + 4x^{28} + 4x^{26} + 4x^{25} + 3x^{24} + 4x^{23} + x^{22} + x^{21} + 4x^{20} + 2x^{19} + x^{17} + 4x^{16} + x^{15} + 3x^{14} + 3x^{13} + 4x^{12} + 2x^{11} + 3x^9 + 4x^8 + 2x^7 + 3x^6 + 3x^4 + 4x^3 + 4x^2 + x.$	$x^6 + x^5 + x^4 + 2x^3 + 2x^2.$	$x^{20} + 2x^{19} + x^{17} + x^{16} + 4x^{15} + x^{14} + 3x^{13} + 3x^{12} + 4x^{11} + 4x^6 + x^3 + 3x^2 + 3x + 4.$
$[[33, 24, 3]]_{5}$	[8,13]	$4x^{33} + 4x^{32} + x^{30} + 2x^{29} + 4x^{28} + 4x^{26} + 4x^{25} + 3x^{24} + 4x^{23} + x^{22} + x^{21} + 4x^{20} + 2x^{19} + x^{17} + 4x^{16} + x^{15} + 3x^{14} + 3x^{13} + 4x^{12} + 2x^{11} + 3x^9 + 4x^8 + 2x^7 + 3x^6 + 3x^4 + 4x^3 + 4x^2 + x.$	$x^4 + 3x^3 + 3x^2 + x + 2.$	$x^{28} + 4x^{27} +4x^{26} + 2x^{25} + x^{24} + 3x^{23} + 4x^{21} + 4x^{20} + 3x^{19} + x^{16} + 3x^{13} + 2x^{11} + 4x^{10} + 4x^9 + 3x^8 + 4x^7 + x^6 + 3x^5 + x^4 + x^3 + 4x^2 + 3.$
$[[38, 24, 4]]_{5}$	[8,13]	$3x^{38} + 3x^{35} + 4x^{33} + 2x^{32} + 3x^{31} + 3x^{30} + x^{29} + 2x^{27} + x^{25}+ 3x^{24} + 4x^{23} + x^{22} + 4x^{21} + 2x^{20} + 3x^{19} + x^{18} + 2x^{17} + 3x^{16}+ 4x^{14} + 4x^{11} + x^{10} + x^9 + 2x^8 + 3x^7 + x^6 + 2x^5 + x^4 + 2x^3 + 2x^2 + 4x + 4.$	$x^6 + 3x^4 + 2x^3 + x^2 + 4x + 1.$	$x^{30} + 3x^{29} + 4x^{28} + 4x^{27} + x^{26} + x^{23} + 3x^{22} + 2x^{21} + 4x^{20 }+ 2x^{19} + 2x^{18} + 2x^{17} + 4x^{16} + 3x^{15} + x^{14} + 2x^{13} + 3x^{12} + x^{11} + 2x^{10} + x^7 + 2x^6 + 3x^5 + 2x^4 + 3x^3 + x^2 + x + 3.$
$[[38, 17, 5]]_{5}$	[8,13]	$3x^{38} + 3x^{35} + 4x^{33} + 2x^{32} + 3x^{31} + 3x^{30} + x^{29} + 2x^{27} + x^{25}+ 3x^{24} + 4x^{23} + x^{22} + 4x^{21} + 2x^{20} + 3x^{19} + x^{18} + 2x^{17} + 3x^{16}+ 4x^{14} + 4x^{11} + x^{10} + x^9 + 2x^8 + 3x^7 + x^6 + 2x^5 + x^4 + 2x^3 + 2x^2 + 4x + 4.$	$x^{10} + 2x^9 + 4x^8 + 2x^7 + 3x^5 + 2x^4 + 4x^3 + 4x^2 + 3x + 1.$	$x^{27} + 4x^{26} + 3x^{25} + x^{23} + 2x^{21} + 3x^{20} + 3x^{19} + x^{18} + 2x^{17} + 3x^{16} + x^{14} + 3x^{13} + 4x^{12} + 4x^{11} + 4x^{10} + 4x^8 + 2x^6 + 4x^4 + 4x^3 + 4x^2 + 3x + 1.$
^*This code is optimal since attains the equality in the quantum singleton bound $ k+2d = n+2$.

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Alahmadi, S. Dougherty, A. Leroy and P. Solé, On the duality and the direction of polycyclic codes, Adv. Math. Commun., 10 (2016), 921-929. doi: 10.3934/amc.2016049.
[2]	N. Aydin, T. H. Guidotti, P. Liu, A. S. Shaikh and R. O. VandenBerg, Some generalizations of the ASR search algorithm for quasitwisted codes, Involve, J. Math., 13 (2020), 137-148. doi: 10.2140/involve.2020.13.137.
[3]	N. Aydin, T. Guidotti and P. Liu, Good classical and quantum codes from multi-twisted codes, Algebra and Coding Theory, Contemp. Math., American Mathematical Society, 785 (2023), 7-21. doi: 10.1090/conm/785/15771.
[4]	N. Aydin, P. Liu and B. Yoshino, Polycyclic codes associated with trinomials: Good codes and open questions, Des. Codes Cryptogr., 90 (2022), 1241-1269. doi: 10.1007/s10623-022-01038-y.
[5]	N. Aydin, I. Siap and D. K. Ray-Chaudhuri, The structure of 1-generator quasi-twisted codes and new linear codes, Des. Codes Cryptogr., 24 (2001), 313-326. doi: 10.1023/A:1011283523000.
[6]	N. Aydin, Some new linear codes from skew cyclic codes and computer algebra challenges, Appl. Algebra Eng. Commun. Comput., 30 (2019), 185-191. doi: 10.1007/s00200-019-00383-1.
[7]	N. Aydin and A. Halilović, A generalization of quasi-twisted codes: Multi-twisted codes, Finite Fields Appl., 45 (2017), 96-106. doi: 10.1016/j.ffa.2016.12.002.
[8]	N. Aydin, P. Liu and B. Yoshino, A database of quantum codes, (2021), http://quantumcodes.info/.
[9]	B. Chen, Y. Fan, L. Lin and H. Liu, Constacyclic codes over finite fields, Finite Fields Appl., 18 (2012), 1217-1231. doi: 10.1016/j.ffa.2012.10.001.
[10]	A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Physical Review, 54 (1996), 1098. doi: 10.1103/PhysRevA.54.1098.
[11]	A. R. Calderbank, E. M. Rains, P. M. Shor and N. J. A. Sloane, Quantum error correction via codes over GF(4), IEEE Transactions on Information Theory, 44 (1998), 1369-1387. doi: 10.1109/18.681315.
[12]	E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill Book Company, New York, 1968.
[13]	J. Bierbrauer and Y. Edel, Some good quantum twisted codes, (2020), https://www.mathi.uni-heidelberg.de/yves/Matritzen/QTBCH/QTBCHIndex.html.
[14]	D. Boucher and F. Ulmer, Coding with skew polynomial rings, Journal of Symbolic Computation, 44 (2009), 1644-1656. doi: 10.1016/j.jsc.2007.11.008.
[15]	M. Esmaeili and S. Yari, Generalized quasi-cyclic codes: structural properties and code construction, Applicable Algebra in Engineering Communication and Computing, 20 (2009), 159-173. doi: 10.1007/s00200-009-0095-3.
[16]	M. I. García-Planas, M. D. Magret and L. E. Um, Monomial codes seen as invariant subspaces, Open Mathematics, 15 (2017), 1099-1107. doi: 10.1515/math-2017-0093.
[17]	M. Grassl, Code Tables: Bounds on the parameters of codes, [online server], http://www.codetables.de/.
[18]	C. R. P. Hartmannn and K. K. Tzeng, Generalizations of the BCH-bound, Information and Control, 20 (1972), 489-498. doi: 10.1016/S0019-9958(72)90887-X.
[19]	H. K. Hoffman and R. Kunze, Linear Algebra, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1971.
[20]	W. C. Huffuman and V. Pless, Fundermentals of Error Correcting Codes, Cambridge University Press, 2003. doi: 10.1017/CBO9780511807077.
[21]	A. Kleppner, The cyclic decomposition theorem, Integral Equations and endomorphism Theory, 25 (1996), 490-495. doi: 10.1007/BF01203029.
[22]	S. Li, M. Xiong and G. Ge, Pseudo-cyclic codes and the construction of quantum MDS code, IEEE Trans. Inf. Theory, 62 (2016), 1703-1710. doi: 10.1109/TIT.2016.2535180.
[23]	R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, Cambridge University Press, Cambridge, 1986.
[24]	S. Ling and P. Sole, On the algebraic structure of quasi-cyclic codes Ⅰ: Finite fields, IEEE Transactions on Information Theory, 47 (2001), 2751-2760. doi: 10.1109/18.959257.
[25]	S. R. Lopez-Permouth, B. R. Parra-Avila and S. Szabo, Dual generalizations of the concept of cyclicity of codes, Advances in Mathematics of Communications, 3 (2009), 227-234. doi: 10.3934/amc.2009.3.227.
[26]	Magma computer algebra system, online, (2022), http://magma.maths.usyd.edu.au/.
[27]	H. Ou-azzou and M. Najmeddine, On the algebraic structure of polycyclic codes, Filomat, 35 (2021), 3407-3421. doi: 10.2298/FIL2110407O.
[28]	Oystein Ore, Theory of monomial groups, Transactions of the American Mathematical Society, 51 (1942), 15-64. doi: 10.1090/S0002-9947-1942-0005739-6.
[29]	E. Prange, Cyclic Error-correcting Codes in Two Symbols, Air Force Cambridge Research Center, 1957.
[30]	D. Radkova and A. J. Van Zanten, Constacyclic codes as invariant subspaces, Linear Algebra and its Applications, 430 (2009), 855-864. doi: 10.1016/j.laa.2008.09.036.
[31]	C. Roos, A generalization of the BCH bound for cyclic codes including the Hartmannn-Tzeng bound, Journal of Combinatorial Theory, Serie A, 33 (1982), 229-232. doi: 10.1016/0097-3165(82)90014-0.
[32]	I. Siap and N. Kulhan, The structure of generalized quasi-cyclic codes, Applied Mathematics E-Notes, 5 (2005), 24-30.
[33]	M. Shi, X. Li, Z. Sepasdar and P. Sole, Polycyclic codes as invariant subspaces, Finite Fields Their Applications, 68 (2020), 101760, 14 pp. doi: 10.1016/j.ffa.2020.101760.
[34]	M. Shi, L. Xu and P. Solé, Construction of isodual codes from polycirculant matrices, Designs, Codes and Cryptography, 88 (2020), 2547-2560. doi: 10.1007/s10623-020-00799-8.
[35]	M. Shi and Y. Zhang, Quasi-twisted codes with constacyclic constituent codes, Finite Fields and Their Applications, 39 (2016), 159-178. doi: 10.1016/j.ffa.2016.01.010.
[36]	A. M. Steane, Error-correcting codes in quantum theory, Physical Review Letters, 77 (1996), 793-797. doi: 10.1103/PhysRevLett.77.793.
[37]	SageMath, the Sage Mathematics Software System (Version 8.7), The Sage Developers, 2019, https://www.sagemath.org.
[38]	E. G. Séguin, The algebraic structure of codes invariant by a permutation, Information Theory and Applications II, 1133 (1996), 1-18. doi: 10.1007/BFb0025131.