Self-dual additive $ \mathbb{F}_4 $-codes of lengths up to 40 represented by circulant graphs

Ken Saito

doi:10.3934/amc.2019014

Article Contents

2019, Volume 13, Issue 2: 213-220. Doi: 10.3934/amc.2019014

This issue Previous Article Next Article Comparison analysis of Ding's RLWE-based key exchange protocol and NewHope variants

Self-dual additive $ \mathbb{F}_4 $-codes of lengths up to 40 represented by circulant graphs

Ken Saito

Research Center for Pure and Applied Mathematics, Graduate School of Information Sciences, Tohoku University, Sendai 980–8579, Japan

Received: December 31, 2016

Published: January 2019

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

Abstract

In this paper, we consider additive circulant graph codes which are self-dual additive $ \mathbb{F}_4 $-codes. We classify all additive circulant graph codes of length $ n = 30, 31 $ and $ 34 \le n \le 40 $ having the largest minimum weight. We also classify bordered circulant graph codes of lengths up to 40 having the largest minimum weight.

Keywords:

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

Citation:

Full Text(HTML)

Table 1. Additive circulant graph codes

$ n $	$ d_{\rm max}^{\rm A}(n) $	$ {\rm num}^{\rm A}_{\rm I}(n) $	$ {\rm num}^{\rm A}_{\rm II}(n) $	Ref.	$ n $	$ d_{\rm max}^{\rm A}(n) $	$ {\rm num}^{\rm A}_{\rm I}(n) $	$ {\rm num}^{\rm A}_{\rm II}(n) $	Ref.
$ 1 $	$ 1 $	$ 1 $	-		$ 21 $	$ 7 $	$ 11 $	-	[10]
$ 2 $	$ 2 $	$ 0 $	1		$ 22 $	$ 8 $	$ 0 $	$ 14 $	[10]
$ 3 $	$ 2 $	$ 1 $	-		$ 23 $	$ 8 $	$ 2 $	-	[10]
$ 4 $	$ 2 $	$ 1 $	2		$ 24 $	$ 8 $	$ 5 $	$ 46 $	[10]
$ 5 $	$ 3 $	$ 1 $	-		$ 25 $	$ 8 $	$ 31 $	-	[10]
$ 6 $	$ 4 $	$ 0 $	1		$ 26 $	$ 8 $	$ 49 $	$ 161 $	[10]
$ 7 $	$ 3 $	$ 1 $	-		$ 27 $	$ 8 $	$ 140 $	-	[10]
$ 8 $	$ 4 $	$ 0 $	1		$ 28 $	$ 10 $	$ 0 $	$ 1 $	[10]
$ 9 $	$ 4 $	$ 1 $	-		$ 29 $	$ 11 $	$ 1 $	-	[10]
$ 10 $	$ 4 $	$ 3 $	5		$ 30 $	$ 12 $	$ 0 $	$ 1 $
$ 11 $	$ 4 $	$ 2 $	-		$ 31 $	$ 10 $	$ 5 $	-
$ 12 $	$ 6 $	$ 0 $	1		$ 32 $	$ 10 $	$ 2 $	$ 106 $	[10]
$ 13 $	$ 5 $	$ 2 $	-	[10]	$ 33 $	$ 10 $	$ 76 $	-	[10]
$ 14 $	$ 6 $	$ 0 $	3	[10]	$ 34 $	$ 10 $	$ 115 $	$ 851 $
$ 15 $	$ 6 $	$ 2 $	-	[10]	$ 35 $	$ 10 $	$ 595 $	-
$ 16 $	$ 6 $	$ 1 $	5	[10]	$ 36 $	$ 11 $	$ 1 $	$ 0 $
$ 17 $	$ 7 $	$ 1 $	-	[10]	$ 37 $	$ 11 $	$ 17 $	-
$ 18 $	$ 6 $	$ 16 $	36	[10]	$ 38 $	$ 12 $	$ 0 $	$ 22 $
$ 19 $	$ 7 $	$ 4 $	-	[10]	$ 39 $	$ 11 $	$ 276 $	-
$ 20 $	$ 8 $	$ 0 $	2	[10]	$ 40 $	$ 12 $	$ 0 $	$ 213 $

| Show Table

DownLoad: CSV

Table 2. Weight distributions of $ C(\Gamma_{31}^{(i)}) $ $ (i = 1, \ldots, 5) $

Code	$ i $	$ A_i $	$ i $	$ A_i $	$ i $	$ A_i $	$ i $	$ A_i $
$ C(\Gamma_{31}^{(1)}) $	$ 0 $	$ 1 $	$ 15 $	$ 2000988 $	$ 21 $	$ 215937072 $	$ 27 $	$ 111769756 $
	$ 10 $	$ 1209 $	$ 16 $	$ 6017193 $	$ 22 $	$ 294597774 $	$ 28 $	$ 47879469 $
	$ 11 $	$ 7564 $	$ 17 $	$ 15948384 $	$ 23 $	$ 345959256 $	$ 29 $	$ 14851976 $
	$ 12 $	$ 34441 $	$ 18 $	$ 37215066 $	$ 24 $	$ 345825894 $	$ 30 $	$ 2973179 $
	$ 13 $	$ 154504 $	$ 19 $	$ 76416984 $	$ 25 $	$ 290407008 $	$ 31 $	$ 288332 $
	$ 14 $	$ 593991 $	$ 20 $	$ 137479482 $	$ 26 $	$ 201124125 $
$ C(\Gamma_{31}^{(2)}) $	$ 0 $	$ 1 $	$ 15 $	$ 1990944 $	$ 21 $	$ 215937072 $	$ 27 $	$ 111779800 $
	$ 10 $	$ 1209 $	$ 16 $	$ 6043977 $	$ 22 $	$ 294504030 $	$ 28 $	$ 47886165 $
	$ 11 $	$ 7192 $	$ 17 $	$ 15966240 $	$ 23 $	$ 345974880 $	$ 29 $	$ 14849000 $
	$ 12 $	$ 35185 $	$ 18 $	$ 37152570 $	$ 24 $	$ 345888390 $	$ 30 $	$ 2972435 $
	$ 13 $	$ 157480 $	$ 19 $	$ 76401360 $	$ 25 $	$ 290389152 $	$ 31 $	$ 288704 $
	$ 14 $	$ 587295 $	$ 20 $	$ 137573226 $	$ 26 $	$ 201097341 $
$ C(\Gamma_{31}^{(3)}) $	$ 0 $	$ 1 $	$ 15 $	$ 2004336 $	$ 21 $	$ 215937072 $	$ 27 $	$ 111766408 $
	$ 10 $	$ 1209 $	$ 16 $	$ 6008265 $	$ 22 $	$ 294629022 $	$ 28 $	$ 47877237 $
	$ 11 $	$ 7688 $	$ 17 $	$ 15942432 $	$ 23 $	$ 345954048 $	$ 29 $	$ 14852968 $
	$ 12 $	$ 34193 $	$ 18 $	$ 37235898 $	$ 24 $	$ 345805062 $	$ 30 $	$ 2973427 $
	$ 13 $	$ 153512 $	$ 19 $	$ 76422192 $	$ 25 $	$ 290412960 $	$ 31 $	$ 288208 $
	$ 14 $	$ 596223 $	$ 20 $	$ 137448234 $	$ 26 $	$ 201133053 $
$ C(\Gamma_{31}^{(4)}) $	$ 0 $	$ 1 $	$ 15 $	$ 2007374 $	$ 21 $	$ 216042968 $	$ 27 $	$ 111761262 $
	$ 10 $	$ 1395 $	$ 16 $	$ 6022649 $	$ 22 $	$ 294539618 $	$ 28 $	$ 47920265 $
	$ 11 $	$ 6758 $	$ 17 $	$ 15937968 $	$ 23 $	$ 345831660 $	$ 29 $	$ 14845156 $
	$ 12 $	$ 35557 $	$ 18 $	$ 37226350 $	$ 24 $	$ 345942454 $	$ 30 $	$ 2966421 $
	$ 13 $	$ 155620 $	$ 19 $	$ 76386604 $	$ 25 $	$ 290475952 $	$ 31 $	$ 290502 $
	$ 14 $	$ 587481 $	$ 20 $	$ 137474274 $	$ 26 $	$ 201025359 $
$ C(\Gamma_{31}^{(5)}) $	$ 0 $	$ 1 $	$ 15 $	$ 2004584 $	$ 21 $	$ 216058592 $	$ 27 $	$ 111758472 $
	$ 10 $	$ 1333 $	$ 16 $	$ 6030089 $	$ 22 $	$ 294526598 $	$ 28 $	$ 47920885 $
	$ 11 $	$ 6696 $	$ 17 $	$ 15945408 $	$ 23 $	$ 345818640 $	$ 29 $	$ 14845776 $
	$ 12 $	$ 36177 $	$ 18 $	$ 37213330 $	$ 24 $	$ 345949894 $	$ 30 $	$ 2966359 $
	$ 13 $	$ 156240 $	$ 19 $	$ 76373584 $	$ 25 $	$ 290483392 $	$ 31 $	$ 290440 $
	$ 14 $	$ 584691 $	$ 20 $	$ 137489898 $	$ 26 $	$ 201022569 $

| Show Table

DownLoad: CSV

Table 3. Bordered circulant graph codes

$ n $	$ d_{\rm max}^{\rm B}(n) $	$ {\rm num}^{\rm B}(n) $	Ref.	$ n $	$ d_{\rm max}^{\rm B}(n) $	$ {\rm num}^{\rm B}(n) $	Ref.
-	-	-	-	$ 21 $	$ 6 $	$ 34 $
$ 2 $	$ 2 $	$ 1 $	[6]	$ 22 $	$ 8 $	$ 3 $	[6]
$ 3 $	$ 2 $	$ 1 $	[6]	$ 23 $	$ 7 $	$ 20 $
$ 4 $	$ 2 $	$ 1 $		$ 24 $	$ 8 $	$ 11 $
$ 5 $	$ 2 $	$ 2 $		$ 25 $	$ 8 $	$ 18 $
$ 6 $	$ 4 $	$ 1 $	[6]	$ 26 $	$ 8 $	$ 14 $
$ 7 $	$ 3 $	$ 1 $		$ 27 $	$ 8 $	$ 70 $
$ 8 $	$ 4 $	$ 1 $	[6]	$ 28 $	$ 8 $	$ 102 $
$ 9 $	$ 4 $	$ 1 $	[6]	$ 29 $	$ 9 $	$ 1 $
$ 10 $	$ 4 $	$ 1 $		$ 30 $	$ 12 $	$ 1 $
$ 11 $	$ 4 $	$ 3 $		$ 31 $	$ 10 $	$ 1 $
$ 12 $	$ 4 $	$ 1 $		$ 32 $	$ 10 $	$ 41 $
$ 13 $	$ 5 $	$ 1 $		$ 33 $	$ 10 $	$ 31 $
$ 14 $	$ 6 $	$ 2 $	[6]	$ 34 $	$ 10 $	$ 368 $
$ 15 $	$ 6 $	$ 1 $	[6]	$ 35 $	$ 10 $	$ 381 $
$ 16 $	$ 6 $	$ 3 $		$ 36 $	$ 10 $	$ 249 $
$ 17 $	$ 6 $	$ 4 $		$ 37 $	$ 11 $	$ 1 $
$ 18 $	$ 8 $	$ 1 $	[6]	$ 38 $	$ 12 $	$ 4 $
$ 19 $	$ 6 $	$ 25 $		$ 39 $	$ 11 $	$ 22 $
$ 20 $	$ 8 $	$ 2 $	[6]	$ 40 $	$ 12 $	$ 27 $

| Show Table

DownLoad: CSV

Table 4. Weight distributions of $ \overline{C}(\Gamma_{n-1}) $ $ (n = 29, 30, 31, 37) $

Code	$ i $	$ A_i $	$ i $	$ A_i $	$ i $	$ A_i $	$ i $	$ A_i $
$ \overline{C}(\Gamma_{28}) $	$ 0 $	$ 1 $	$ 14 $	$ 960696 $	$ 20 $	$ 70176246 $	$ 26 $	$ 13926402 $
	$ 9 $	$ 196 $	$ 15 $	$ 1404096 $	$ 21 $	$ 80787000 $	$ 27 $	$ 7162400 $
	$ 10 $	$ 4130 $	$ 16 $	$ 6819393 $	$ 22 $	$ 90249720 $	$ 28 $	$ 879975 $
	$ 11 $	$ 4704 $	$ 17 $	$ 9807336 $	$ 23 $	$ 88070976 $	$ 29 $	$ 169548 $
	$ 12 $	$ 69027 $	$ 18 $	$ 29368108 $	$ 24 $	$ 55981758 $
	$ 13 $	$ 127932 $	$ 19 $	$ 37819264 $	$ 25 $	$ 43082004 $
$ \overline{C}(\Gamma_{29}) $	$ 0 $	$ 1 $	$ 16 $	$ 12038625 $	$ 22 $	$ 341403660 $	$ 28 $	$ 18581895 $
	$ 12 $	$ 118755 $	$ 18 $	$ 61752600 $	$ 24 $	$ 312800670 $	$ 30 $	$ 378018 $
	$ 14 $	$ 1151010 $	$ 20 $	$ 195945750 $	$ 26 $	$ 129570840 $
$ \overline{C}(\Gamma_{30}) $	$ 0 $	$ 1 $	$ 15 $	$ 1296630 $	$ 21 $	$ 195080760 $	$ 27 $	$ 129747510 $
	$ 10 $	$ 1931 $	$ 16 $	$ 7888953 $	$ 22 $	$ 310437330 $	$ 28 $	$ 38102265 $
	$ 11 $	$ 3534 $	$ 17 $	$ 11648880 $	$ 23 $	$ 342154620 $	$ 29 $	$ 18540660 $
	$ 12 $	$ 51285 $	$ 18 $	$ 45631390 $	$ 24 $	$ 334681590 $	$ 30 $	$ 2109261 $
	$ 13 $	$ 85620 $	$ 19 $	$ 62449660 $	$ 25 $	$ 312351600 $	$ 31 $	$ 382350 $
	$ 14 $	$ 830385 $	$ 20 $	$ 156683394 $	$ 26 $	$ 177324039 $
$ \overline{C}(\Gamma_{36}) $	$ 0 $	$ 1 $	$ 17 $	$ 9143640 $	$ 24 $	$ 8309464632 $	$ 31 $	$ 11671999680 $
	$ 11 $	$ 360 $	$ 18 $	$ 67292720 $	$ 25 $	$ 10288765008 $	$ 32 $	$ 4976806725 $
	$ 12 $	$ 11520 $	$ 19 $	$ 102308360 $	$ 26 $	$ 16810527456 $	$ 33 $	$ 3176508888 $
	$ 13 $	$ 19068 $	$ 20 $	$ 516207384 $	$ 27 $	$ 18804288888 $	$ 34 $	$ 730497264 $
	$ 14 $	$ 318384 $	$ 21 $	$ 741731364 $	$ 28 $	$ 20519937680 $	$ 35 $	$ 305859096 $
	$ 15 $	$ 533376 $	$ 22 $	$ 2581317216 $	$ 29 $	$ 20147052420 $	$ 36 $	$ 28393304 $
	$ 16 $	$ 5746818 $	$ 23 $	$ 3466908864 $	$ 30 $	$ 14172955632 $	$ 37 $	$ 4357724 $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	B. Alspach and T. D. Parsons, Isomorphism of circulant graphs and digraphs, Discrete Math., 25 (1979), 97-108. doi: 10.1016/0012-365X(79)90011-6.
[2]	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.
[3]	A. R. Calderbank, E. M. Rains, P. W. Shor and N. J. A. Sloane, Quantum error correction via codes over GF(4), IEEE Trans. Inform. Theory, 44 (1998), 1369-1387. doi: 10.1109/18.681315.
[4]	S. Cichacz and D. Froncek, Distance magic circulant graphs, Discrete Math., 339 (2016), 84-94. doi: 10.1016/j.disc.2015.07.002.
[5]	L. E. Danielsen and M. G. Parker, On the classification of all self-dual additive codes over GF(4) of length up to $12$, J. Combin. Theory Ser. A, 113 (2006), 1351-1367. doi: 10.1016/j.jcta.2005.12.004.
[6]	L. E. Danielsen and M. G. Parker, Directed graph representation of half-rate additive codes over GF(4), Des. Codes Cryptogr., 59 (2011), 119-130. doi: 10.1007/s10623-010-9469-6.
[7]	B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Combinatorial Theory, 9 (1970), 297-307. doi: 10.1016/S0021-9800(70)80068-0.
[8]	M. Grassl and M. Harada, New self-dual additive $\mathbb{F}_4$-codes constructed from circulant graphs, Discrete Math., 340 (2017), 399-403. doi: 10.1016/j.disc.2016.08.023.
[9]	F. J. MacWilliams, A. M. Odlyzko, N. J. A. Sloane and H. N. Ward, Self-dual codes over $GF(4)$, J. Combin. Theory Ser. A, 25 (1978), 288-318. doi: 10.1016/0097-3165(78)90021-3.
[10]	Z. Varbanov, Additive circulant graph codes over GF(4), Math. Maced., 6 (2008), 73-79.
[11]	Z. Varbanov, T. Todorov and M. Hristova, A method for constructing DNA codes from additive self-dual codes over GF(4), ROMAI J., 10 (2014), 203-211.