Construction of extremal $ \mathbb{Z}_{4} $-codes using a neighborhood search algorithm

Dean Crnković; Matteo Mravić; Sanja Rukavina

doi:10.3934/amc.2023039

Article Contents

2025, Volume 19, Issue 1: 91-108. Doi: 10.3934/amc.2023039

This issue Previous Article The weight distributions of several classes of few-weight linear codes Next Article Message recovery attack on NTRU using a lattice independent from the public key

Construction of extremal $ \mathbb{Z}_{4} $-codes using a neighborhood search algorithm

Faculty of Mathematics, University of Rijeka, Radmile Matej$ \check{c} $ić 2, 51000 Rijeka, Croatia

^*Corresponding author: Sanja Rukavina
^*Corresponding author: Sanja Rukavina

Received: May 2023

Early access: October 2023

Published: February 2025

Abstract / Introduction Full Text(HTML) Figure(1) / Table(10) Related Papers Cited by

Abstract

In this paper, we present a method for constructing extremal $ \mathbb{Z}_{4} $-codes based on random neighborhood search. This method is used to find new extremal Type Ⅰ and Type Ⅱ $ \mathbb{Z}_{4} $-codes of lengths 32 and 40. For the length 32, at least 182 new Type Ⅱ extremal $ \mathbb{Z}_{4} $-codes of types $ 4^{k}2^{32-2k} $, $ k\in\left\{9,10,12,13,14,15,16\right\} $ are constructed. In addition, we obtained at least 762 new extremal Type Ⅰ $ \mathbb{Z}_{4} $-codes of types $ 4^{k}2^{32-2k} $, $ k\in\left\{7,9,10,12,13,14,15,16\right\} $. For the length 40, constructed extremal $ \mathbb{Z}_{4} $-codes are of types $ 4^{k}2^{40-2k} $, $ k\in\left\{7,10,11,15,16\right\} $. There are at least 40 new Type Ⅱ extremal $ \mathbb{Z}_{4} $-codes, and at least 4144 new Type Ⅰ extremal $ \mathbb{Z}_{4} $-codes.

Keywords:

Mathematics Subject Classification: Primary: 94B05; Secondary: 94B65.

Citation:

Full Text(HTML)

Figure 1. A comparison of the RS, NS-L, and NS-R algorithms

Download: Full-size image PowerPoint slide

Table 1. The type and the number of the known extremal Type Ⅱ $ \mathbb{Z}_{4} $-codes of length 32

Type	$ 4^{6} 2^{20} $	$ 4^{7} 2^{18} $	$ 4^{8} 2^{16} $	$ 4^{9} 2^{14} $	$ 4^{10} 2^{12} $	$ 4^{11} 2^{10} $
#	$ 1 $	$ 7 $	$ 27 $	$ 15 $	$ 5 $	$ 3 $
References	[17]	[1,2,17]	[1,17]	[1,2,17]	[1,2,17]	[17,27]

Type	$ 4^{12} 2^{8} $	$ 4^{13} 2^{6} $	$ 4^{14} 2^{4} $	$ 4^{15} 2^{2} $	$ 4^{16} $
#	$ 1 $	$ 220 $	$ 5148 $	$ 356 $	$ 134 $
References	[17]	[10,17]	[1,10,17]	[10,17]	[15,17]

| Show Table

DownLoad: CSV

Table 2. The type and the number of the known extremal Type Ⅱ $ \mathbb{Z}_{4} $-codes of length 40

Type	$ 4^{7} 2^{26} $	$ 4^{8} 2^{24} $	$ 4^{9} 2^{22} $	$ 4^{10} 2^{20} $	$ 4^{11} 2^{18} $	$ 4^{12} 2^{16} $	$ 4^{13} 2^{14} $
#	$ 3 $	$ 228 $	$ 100 $	$ 2 $	$ 3 $	$ 20 $	$ 15 $
References	[3,17]	[3,17]	[3,17]	[3,17]	[3,17]	[3,17]	[3,17,27]

Type	$ 4^{14} 2^{12} $	$ 4^{15} 2^{10} $	$ 4^{16} 2^{8} $	$ 4^{17}2^{6} $	$ 4^{18}2^{4} $	$ 4^{19}2^{2} $	$ 4^{20} $
#	$ 5 $	$ 3 $	$ 1 $	$ 134 $	$ 902 $	$ 432 $	$ 94343 $
References	[3,17]	[3,17]	[17]	[10,17]	[3,10,17]	[10,17]	[20,27]

| Show Table

DownLoad: CSV

Table 3. The parameter $ r $ given by (6)

$ b_{i,j}=b_{j,i} $					$ b_{i,j}\neq b_{j,i} $
$ c_i $	$ c_j $	$ \|I\|\left( \text{mod }2\right) $	$ \|J\|\left( \text{mod }2\right) $	$ r $	$ c_i $	$ c_j $	$ \|I\|\left( \text{mod }2\right) $	$ \|J\|\left( \text{mod }2\right) $	$ r $
0	1, 3	0	$ * $	1	0	1, 3	0	$ * $	-1
0	1, 3	1	$ * $	-1	0	1, 3	1	$ * $	1
1, 3	0	$ * $	0	1	1, 3	0	$ * $	0	1
1, 3	0	$ * $	1	-1	1, 3	0	$ * $	1	-1
2	1, 3	0	$ * $	-1	2	1, 3	0	$ * $	1
2	1, 3	1	$ * $	1	2	1, 3	1	$ * $	-1
1, 3	2	$ * $	0	-1	1, 3	2	$ * $	0	-1
1, 3	2	$ * $	1	1	1, 3	2	$ * $	1	1

| Show Table

DownLoad: CSV

Table 4. Invariants of the known extremal Type Ⅱ $ \mathbb{Z}_{4} $-codes of length 32

The type	Reference	#	Invariants	The type	Reference	#	Invariants
$ 4^{7}2^{18} $	[1]	5	$ d=12 $	$4^{13}2^{6}$	[10]	219	$108251\leq W_{16}^E\leq 109467$
	[2]	1	$ A_4=4 $	$4^{13}2^{6}$	[17]	1	$W_{16}^E=115232$, $A_4=36$
	[17]	1	$ W_{16}^E=125080 $	$4^{15}2^{2}$	[10]	355	$d=8$
$ 4^{9}2^{14} $	[1]	12	$ d=8 $	$4^{15}2^{2}$	[17]	1	$A_4=72$
	[2]	2	$ d=8 $	$4^{16}$	[15]	54	$d=8$
	[17]	1	$ A_4=4 $			80	$W_{16}^E=110678$*
$ 4^{10}2^{12} $	[1]	3	$ d=12 $		[17]	80	$W_{16}^E=110984$*
	[2]	1	$ d=8 $				$W_{16}^E=113496$*
	[17]	1	$ A_4=10 $				$W_{16}^E=110928$*

| Show Table

DownLoad: CSV

Table 5. Extremal Type Ⅰ $ \mathbb{Z}_4 $-codes from $ C_{32,1},\ldots,C_{32,21} $ obtained by RS algorithm

The binary code	# of obtained extremal $ \mathbb{Z}_4 $-codes	# of nonequivalent codes	The type	The binary residue code
$ C_{32,3} $	13	$ \geq10 $	$ 4^{12}2^{8} $	[32, 12, 4]
$ C_{32,4} $	6	$ \geq6 $	$ 4^{15}2^{2} $	[32, 15, 4]
$ C_{32,8} $	35	$ \geq2 $	$ 4^{10}2^{12} $	[32, 10, 4]
$ C_{32,12} $	5	$ \geq5 $	$ 4^{13}2^{6} $	[32, 13, 4]
$ C_{32,15} $	210	$ \geq2 $	$ 4^{10}2^{12} $	[32, 10, 4]
$ C_{32,16} $	272	$ \geq240 $	$ 4^{16} $	[32, 16, 4]
$ C_{32,18} $	44	$ \geq1 $	$ 4^{10}2^{12} $	[32, 10, 4]
$ C_{32,19} $	188	$ \geq177 $	$ 4^{13}2^{6} $	[32, 13, 4]

| Show Table

DownLoad: CSV

Table 6. Extremal $ \mathbb{Z}_{4} $-codes of length 32 obtained with the NS-R algorithm from $ C_{32,1},\ldots,C_{32,21} $

The binary code	# of obtained extremal $ \mathbb{Z}_{4} $-codes	# of nonequivalent Type Ⅰ	# of nonequivalent Type Ⅱ	The type	The binary residue code
$ C_{32,2} $	6137	$ \geq3 $	$ \geq1 $	$ 4^{9}2^{14} $	$ [32,9,8] $
$ C_{32,3} $	161	$ \geq88 $	$ \geq35 $	$ 4^{12}2^{8} $	$ [32,12,4] $
$ C_{32,4} $	42	$ 24 $	$ 18 $	$ 4^{15}2^{2} $	$ [32,15,4] $
$ C_{32,5} $	1664	$ \geq2 $	$ \geq1 $	$ 4^{9}2^{14} $	$ [32,9,4] $
$ C_{32,6} $	27	$ 0 $	$ \geq27 $	$ 4^{15}2^{2} $	$ [32,15,4] $
$ C_{32,7} $	3035	$ \geq3 $	$ \geq1 $	$ 4^{9}2^{14} $	$ [32,9,8] $
$ C_{32,8} $	532	$ \geq21(1) $	$ \geq6 $	$ 4^{10}2^{12} $	$ [32,10,4] $
$ C_{32,9} $	11	$ 0 $	$ 11 $	$ 4^{16} $	$ [32,16,4] $
$ C_{32,10} $	44687	$ \geq3 $	$ \geq1 $	$ 4^{7}2^{18} $	$ [32,7,8] $
$ C_{32,11} $	409	$ 0 $	$ \geq1 $	$ 4^{10}2^{12} $	$ [32,10,8] $
$ C_{32,12} $	7	$ 2 $	$ 5 $	$ 4^{13}2^{6} $	$ [32,13,4] $
$ C_{32,13} $	11	$ 0 $	$ 11 $	$ 4^{16} $	$ [32,16,4] $
$ C_{32,14} $	722	$ \geq2 $	$ \geq1 $	$ 4^{10}2^{12} $	$ [32,10,8] $
$ C_{32,15} $	3456	$ \geq99(1) $	$ \geq24 $	$ 4^{10}2^{12} $	$ [32,10,4] $
$ C_{32,16} $	17	$ 8(1) $	$ 9 $	$ 4^{16} $	$ [32,16,4] $
$ C_{32,17} $	4800	$ \geq2 $	$ \geq1 $	$ 4^{7}2^{18} $	$ [32,7,4] $
$ C_{32,18} $	24	$ \geq5 $	$ \geq1 $	$ 4^{10}2^{12} $	$ [32,10,4] $
$ C_{32,19} $	109	$ \geq55(2) $	$ \geq49 $	$ 4^{13}2^{6} $	$ [32,13,4] $
$ C_{32,20} $	1483	$ \geq7 $	$ \geq5 $	$ 4^{10}2^{12} $	$ [32,10,4] $
$ C_{32,21} $	8	$ 0 $	$ 8 $	$ 4^{16} $	$ [32,16,4] $

| Show Table

DownLoad: CSV

Table 7. The number of codewords of Euclidean weight 16 in extremal Type Ⅱ $ \mathbb{Z}_{4} $-codes

The residue code	$ W_{16}^E $
$ C_{32,9} $	110632, 110664, 110708, 110756, 110772, 110800, 110808, 110844, 110948, 110980, 111424
$ C_{32,13} $	110440, 110480, 110536, 110608, 110784, 110784, 110888, 111016, 111032, 111200, 111240
$ C_{32,16} $	112984, 113128, 113400, 113608, 113752, 113816, 113896, 114024, 114360
$ C_{32,21} $	110346, 110374, 110546, 110574, 110626, 110714, 110770, 110918

| Show Table

DownLoad: CSV

Table 8. Weight distributions of doubly even binary codes of length 40

Code	Reference	[n, k, d]	0	4	8	12	16	20
$ C_{40,1} $	[17]	$ \left[40,7,12\right] $	1			1	11	102
$ C_{40,2} $	[17]	$ \left[40,7,16\right] $	1				15	96
$ C_{40,3} $	[17]	$ \left[40,10,4\right] $	1	6	1	10	150	688
$ C_{40,4} $	[3]	$ \left[40,10,12\right] $	1			18	223	540
$ C_{40,5} $	[17]	$ \left[40,11,4\right] $	1	10	6	22	313	1344
$ C_{40,6} $	[3]	$ \left[40,11,12\right] $	1			34	479	1020
$ C_{40,7} $	[3]	$ \left[40,11,12\right] $	1			42	447	1068
$ C_{40,8} $	[17]	$ \left[40,15,4\right] $	1	37	175	688	5296	20374
$ C_{40,9} $	[3]	$ \left[40,15,8\right] $	1		10	634	7589	16300
$ C_{40,10} $	[3]	$ \left[40,15,8\right] $	1		6	658	7529	16380
$ C_{40,11} $	[17]	$ \left[40,16,4\right] $	1	47	313	1548	10694	40330
$ C_{40,12},C_{40,13} $	[20]	$ [40,20,8] $	1	0	285	21280	239970	525504
$ C_{40,14} $	[20]	$ [40,20,4] $	1	190	4845	38760	125970	709044

| Show Table

DownLoad: CSV

Table 9. Extremal $ \mathbb{Z}_4 $-codes of length 40 obtained with the modified search algorithm from $ C_{40,1},\ldots,C_{40,14} $

The binary code	The type	# of obtained extremal $ \mathbb{Z}_4 $ codes	# of nonequivalent Type Ⅰ	# of nonequivalent Type Ⅱ
$ C_{40,1} $	$ 4^{7}2^{26} $	488	$ \geq4 $	$ \geq1 $
$ C_{40,2} $	$ 4^{7}2^{26} $	959	$ \geq3 $	$ 0 $
$ C_{40,3} $	$ 4^{10}2^{20} $	17	$ \geq6 $	$ 0 $
$ C_{40,4} $	$ 4^{10}2^{20} $	129	$ \geq3 $	$ \geq3 $
$ C_{40,5} $	$ 4^{11}2^{18} $	7	$ 7 $	$ 0 $
$ C_{40,6} $	$ 4^{11}2^{18} $	31	$ 0 $	$ \geq5 $
$ C_{40,7} $	$ 4^{11}2^{18} $	13	$ 0 $	$ \geq4 $
$ C_{40,8} $	$ 4^{15}2^{10} $	37	$ \geq17 $	$ 0 $
$ C_{40,9} $	$ 4^{15}2^{10} $	7	$ 0 $	$ 7 $
$ C_{40,10} $	$ 4^{15}2^{10} $	9	$ 0 $	$ 9 $
$ C_{40,11} $	$ 4^{16}2^{8} $	104	$ \geq14 $	$ \geq1 $
$ C_{40,12} $	$ 4^{20} $	7	$ 0 $	$ 7 $
$ C_{40,13} $	$ 4^{20} $	1	$ 0 $	$ 1 $
$ C_{40,14} $	$ 4^{20} $	4194	$ \geq4090 $	$ \geq3 $

| Show Table

DownLoad: CSV

Table 10. The number of codewords of Euclidean weight 16 ($ W_{16}^E $) in extremal Type Ⅱ $ \mathbb{Z}_{4} $-codes of length 40

The binary code	The type	$ W_{16}^E $ of the known extremal $ \mathbb{Z}_{4} $-codes	$ W_{16}^E $ of the constructed extremal $ \mathbb{Z}_{4} $-codes
$ C_{40,1} $	$ 4^{7}2^{26} $	-	14598
$ C_{40,4} $	$ 4^{10}2^{20} $	32566	32822, 32694, 32950
$ C_{40,6} $	$ 4^{11}2^{18} $	34574	34446, 34574, 34702, 34638, 34510
$ C_{40,7} $	$ 4^{11}2^{18} $	33406	33406, 33726, 33214, 33342
$ C_{40,9} $	$ 4^{15}2^{10} $	34657	35015, 34733, 34779, 34633, 34899, 34869, 34685
$ C_{40,10} $	$ 4^{15}2^{10} $	34935	34745, 34845, 34723, 34675, 34839, 34797, 34855, 34729, 34879
$ C_{40,11} $	$ 4^{16}2^{8} $	27298	27098
$ C_{40,12} $	$ 4^{20} $	34730	34552, 34540, 34584, 34596, 34794, 34850, 34992
$ C_{40,13} $	$ 4^{20} $	34694	34570
$ C_{40,14} $	$ 4^{20} $	25918	24030, 25214, 26014

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Ban, Construction of Extremal Type II Z4-Codes, PhD Thesis, University of Zagreb, Croatia, 2019.
[2]	S. Ban, D. Crnković, M. Mravić and S. Rukavina, New extremal Type Ⅱ $ \mathbb{Z}_{4}$ -codes of length 32 obtained from Hadamard matrices, Discrete Math. Algorithms Appl., 11 (2019), 1950057, 18 pp. doi: 10.1142/s1793830919500575.
[3]	S. Ban and S. Rukavina, On some new extremal Type Ⅱ $\mathbb{Z}_{4} $-codes of length 40, Math. Commun., 25 (2020), 253-268.
[4]	K. Betsumiya, M. Harada and A. Munemasa, A complete classification of doubly even self-dual codes of length 40, Electron. J. Comb., 19 (2012), Paper 18, 12 pp. doi: 10.37236/2593.
[5]	R. A. L. Betty and A. Munemasa, Classification of Self-dual Codes of Length 20 over $ \mathbb{Z }_4$ and Length at Most 18 over $\mathbb{F}_2+u\mathbb{F}_2 $, Cryptography and Coding (ed. Albrecht, M.), IMACC 2019, Lecture Notes in Computer Science, Springer, Cham., 11929 (2019), 64-77.
[6]	R. A. L. Betty and A. Munemasa, Classification of Extremal Type Ⅱ $\mathbb{Z }_4 $-codes of Length 24, WCC 2022: The Twelfth International Workshop on Coding and Cryptography, University of Rostock, Germany, (2022), https://www.wcc2022.uni-rostock.de/storages/uni-rostock/Tagungen/WCC2022/Papers/WCC_2022_paper_8.pdf.
[7]	A. Bonnecaze, P. Solé, C. Bachoc and B. Mourrain, Type Ⅱ codes over $ \mathbb{Z}_{4}$, IEEE Trans. Inf. Theory, 43 (1997), 969-976. doi: 10.1109/18.568705.
[8]	W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. Ⅰ. The user language, J. Symbolic Comput., 24 (1997), 235-265. doi: 10.1006/jsco.1996.0125.
[9]	S. Bouyuklieva, I. Bouyukliev and M. Harada, Some extremal self-dual codes and unimodular lattices in dimension 40, Finite Fields Their Appl., 21 (2013), 67-83. doi: 10.1016/j.ffa.2013.01.009.
[10]	K. H. Chan, Three New Methods for Construction of Extremal Type II $\mathbb{Z}_{4} $-Codes, Ph.D thesis, University of Illinois at Chicago, 2012.
[11]	J. H. Conway and N. J. A. Sloane, Self-dual codes over the integers modulo 4, J. Comb. Theory, Ser. A, 62 (1993), 30-45. doi: 10.1016/0097-3165(93)90070-O.
[12]	D. Crnković and M.-O. Pavčević, Some new symmetric designs with parameters (64, 28, 12), Discrete Math., 237 (2001), 109-118. doi: 10.1016/S0012-365X(00)00364-2.
[13]	J. Fields, P. Gaborit, J. S. Leon and V. Pless, All self-dual $ \mathbb{Z}_{4}$ codes of length 15 or less are known, IEEE Trans. Inf. Theory, 44 (1998), 311-322. doi: 10.1109/18.651058.
[14]	P. Gaborit, Mass formulas for self-dual codes over $ \mathbb{Z}_{4}$ and $\mathbb{F}_q+u\mathbb{F}_q $ rings, IEEE Trans. Inform. Theory, 42 (1996), 1222-1228. doi: 10.1109/18.508845.
[15]	P. Gaborit and M. Harada, Construction of extremal type Ⅱ codes over $\mathbb{Z}_4 $, Des. Codes, Cryptogr., 16 (1999), 257-269. doi: 10.1023/A:1008335912135.
[16]	M. Harada, Extremal type Ⅱ $\mathbb{Z}_{4} $-codes of lengths 56 and 64, J. Comb. Theory, Ser. A., 117 (2010), 1285-1288. doi: 10.1016/j.jcta.2009.09.003.
[17]	M. Harada, On the residue codes of extremal type Ⅱ $ \mathbb{Z}_{4}$-codes of lengths 32 and 40, Discrete Math., 311 (2011), 2148-2157. doi: 10.1016/j.disc.2011.06.022.
[18]	M. Harada, Extremal Type Ⅰ $ \mathbb{Z}_k$-codes and k-frames of odd unimodular lattices, IEEE Trans. Inf. Theory, 61 (2015), 72-81.
[19]	M. Harada, Note on the residue codes of self-dual $ \mathbb{Z}_4$-codes having large minimum Lee weights, Adv. Math. Commun., 10 (2016), 695-706. doi: 10.3934/amc.2016035.
[20]	M. Harada, Extremal type Ⅱ $ \mathbb{Z}_4$-codes constructed from binary doubly even self-dual codes of length $40$, Discrete Math., 340 (2017), 253-268. doi: 10.1016/j.disc.2017.06.009.
[21]	M. Harada, Construction of extremal type Ⅱ $\mathbb{Z}_2k $-codes, Finite Fields Appl., 87 (2023), 102154, 17 pp. doi: 10.1016/j.ffa.2022.102154.
[22]	M. Harada, M. Kitazume, A. Munemasa and B. Venkov, On some self-dual codes and unimodular lattices in dimension 48, Eur. J. Comb., 26 (2005), 543-557. doi: 10.1016/j.ejc.2004.06.013.
[23]	M. Harada and A. Munemasa, On the classification of self-dual $ \mathbb{Z}_k$-codes, Cryptography and Coding (ed. Parker, M. G.), IMACC 2009, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, 5921 (2009), 78-90. doi: 10.1007/978-3-642-10868-6_6.
[24]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003. doi: 10.1017/CBO9780511807077.
[25]	Z. Janko, Coset enumeration in groups and constructions of symmetric designs, Ann. Discrete Math., 52 (1992), 275-277.
[26]	V. Pless, J. S. Leon and J. Fields, All $ \mathbb{Z}_{4}$ codes of type Ⅱ and length 16 are known, J. Comb. Theory, Ser. A, 78 (1997), 32-50.
[27]	V. Pless, P. Solé and Z. Qian, Cyclic self-dual $\mathbb{Z}_{4} $-codes, Finite Fields Appl., 3 (1997), 48-69. doi: 10.1006/ffta.1996.0172.