Nonexistence of some ternary linear codes with minimum weight -2 modulo 9

Toshiharu Sawashima; Tatsuya Maruta

doi:10.3934/amc.2021052

Article Contents

2023, Volume 17, Issue 6: 1338-1357. Doi: 10.3934/amc.2021052

This issue Previous Article Constructions of irredundant orthogonal arrays Next Article Security analysis of public key encryption with filtered equality test

Nonexistence of some ternary linear codes with minimum weight -2 modulo 9

Toshiharu Sawashima and
Tatsuya Maruta^,

Department of Mathematical Sciences, Osaka Prefecture University, Sakai, Osaka 599-8531, Japan

^* Corresponding author: Tatsuya Maruta
^* Corresponding author: Tatsuya Maruta

Received: May 2021

Revised: September 2021

Early access: November 2021

Published: December 2023

The second author is partially supported by JSPS KAKENHI Grant Number 20K03722.

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

Abstract

One of the fundamental problems in coding theory is to find $ n_q(k,d) $, the minimum length $ n $ for which a linear code of length $ n $, dimension $ k $, and the minimum weight $ d $ over the field of order $ q $ exists. The problem of determining the values of $ n_q(k,d) $ is known as the optimal linear codes problem. Using the geometric methods through projective geometry and a new extension theorem given by Kanda (2020), we determine $ n_3(6,d) $ for some values of $ d $ by proving the nonexistence of linear codes with certain parameters.

Keywords:

Mathematics Subject Classification: Primary: 94B27, 94B05; Secondary: 51E20, 05B25.

Citation:

Full Text(HTML)

Table 1. $ p_{i,j} $ for $ (\varphi_0,\varphi_1) \in \mathcal{D}_5^+ $

$ \varphi_0 $	$ \varphi_1 $	$ p_{4,0} $	$ p_{1,3} $	$ p_{1,0} $	$ p_{2,1} $
$ 40 $	$ 27 $	$ 13 $	$ 9 $	$ 18 $	$ 0 $
		$ 4 $	$ 0 $	$ 9 $	$ 27 $
$ 31 $	$ 45 $	$ 10 $	$ 15 $	$ 15 $	$ 0 $
		$ 1 $	$ 6 $	$ 6 $	$ 27 $
$ 40 $	$ 36 $	$ 4 $	$ 3 $	$ 6 $	$ 27 $
$ 40 $	$ 45 $	$ 4 $	$ 6 $	$ 3 $	$ 27 $
$ 49 $	$ 36 $	$ 16 $	$ 12 $	$ 12 $	$ 0 $
		$ 7 $	$ 3 $	$ 3 $	$ 27 $

| Show Table

DownLoad: CSV

Table 2. $ q_{i,j} $ for $ (\varphi_0,\varphi_1) \in \mathcal{D}_5^+ $

$ \varphi_0 $	$ \varphi_1 $	$ q_{1,3} $	$ q_{0,2} $	$ q_{2,1} $
$ 40 $	$ 27 $	$ 4 $	$ 18 $	$ 18 $
$ 31 $	$ 45 $	$ 13 $	$ 18 $	$ 9 $
$ 40 $	$ 36 $	$ 10 $	$ 15 $	$ 15 $
$ 40 $	$ 45 $	$ 16 $	$ 12 $	$ 12 $
$ 49 $	$ 36 $	$ 13 $	$ 9 $	$ 18 $

| Show Table

DownLoad: CSV

Table 3. $r_{i,j}$ for $(\varphi_0,\varphi_1) \in \mathcal{D}_5^+$

$\varphi_0$	$\varphi_1$	$r_{1,0}$	$r_{0,2}$	$r_{2,1}$
40	27	22	9	9
31	45	13	18	9
40	36	16	12	12
40	45	10	15	15
49	36	13	9	18

| Show Table

DownLoad: CSV

Table 4. $ p_{i,j} $ for $ (\varphi_0,\varphi_1) \in \mathcal{D}_6^+ $

$ \varphi_0 $	$ \varphi_1 $	$ p_{4,0} $	$ p_{1,3} $	$ p_{1,0} $	$ p_{2,1} $
$ 121 $	$ 81 $	$ 40 $	$ 27 $	$ 54 $	$ 0 $
		$ 13 $	$ 0 $	$ 27 $	$ 81 $
$ 94 $	$ 135 $	$ 31 $	$ 45 $	$ 45 $	$ 0 $
		$ 4 $	$ 18 $	$ 18 $	$ 81 $
$ 121 $	$ 108 $	$ 40 $	$ 36 $	$ 45 $	$ 0 $
		$ 13 $	$ 9 $	$ 18 $	$ 81 $
$ 112 $	$ 126 $	$ 10 $	$ 15 $	$ 15 $	$ 81 $
$ 130 $	$ 117 $	$ 16 $	$ 12 $	$ 12 $	$ 81 $
$ 121 $	$ 135 $	$ 40 $	$ 45 $	$ 36 $	$ 0 $
		$ 13 $	$ 18 $	$ 9 $	$ 81 $
$ 148 $	$ 108 $	$ 49 $	$ 36 $	$ 36 $	$ 0 $
		$ 22 $	$ 9 $	$ 9 $	$ 81 $

| Show Table

DownLoad: CSV

Table 5. $ q_{i,j} $ for $ (\varphi_0,\varphi_1) \in \mathcal{D}_6^+ $

$ \varphi_0 $	$ \varphi_1 $	$ q_{1,3} $	$ q_{0,2} $	$ q_{2,1} $
$ 121 $	$ 81 $	$ 13 $	$ 54 $	$ 54 $
$ 94 $	$ 135 $	$ 40 $	$ 54 $	$ 27 $
$ 121 $	$ 108 $	$ 31 $	$ 45 $	$ 45 $
$ 112 $	$ 126 $	$ 40 $	$ 45 $	$ 36 $
$ 130 $	$ 117 $	$ 40 $	$ 36 $	$ 45 $
$ 121 $	$ 135 $	$ 49 $	$ 36 $	$ 36 $
$ 148 $	$ 108 $	$ 40 $	$ 27 $	$ 54 $

| Show Table

DownLoad: CSV

Table 6. $r_{i,j}$ for $(\varphi_0,\varphi_1) \in \mathcal{D}_6^+$

$\varphi_0$	$\varphi_1$	$r_{1,0}$	$r_{0,2}$	$r_{2,1}$
121	81	67	27	27
94	135	40	54	27
121	108	49	36	36
112	126	40	45	36
130	117	40	36	45
121	135	31	45	45
148	108	40	27	54

| Show Table

DownLoad: CSV

Table 7. The spectra of some ternary linear codes of dimension 4 [31]

parameters	possible spectra
$ [4,4,1]_3 $	$ (a_0, a_1, a_2, a_3)=(8,16,12,4) $
$ [5,4,2]_3 $	$ (a_0, a_1, a_2, a_3)=(5,15,10,10) $
$ [7,4,3]_3 $	$ (a_0, a_1, a_2, a_3, a_4)=(3,8,9,15,5) $
	$ (a_1, a_2, a_3, a_4)=(14,9,9,8) $
	$ (a_0, a_1, a_2, a_3, a_4)=(2,9,12,10,7) $
	$ (a_0, a_1, a_2, a_3, a_4)=(4,4,15,11,6) $
$ [8,4,4]_3 $	$ (a_0, a_1, a_2, a_3, a_4)=(3,4,10,12,11) $
	$ (a_0, a_1, a_2, a_3, a_4)=(2,8,4,16,10) $
	$ (a_0, a_2, a_3, a_4)=(4,16,8,12) $
$ [9,4,5]_3 $	$ (a_0,a_1,a_3, a_4)=(1,9,12,18) $
$ [10,4,6]_3 $	$ (a_1, a_4)=(10,30) $
$ [14,4,8]_3 $	$ (a_1, a_2, a_3, a_4, a_5, a_6)=(1,4,4,8,9,14) $
	$ (a_1, a_2, a_4, a_5, a_6)=(2,4,10,12,12) $
	$ (a_1, a_2, a_3, a_4, a_5, a_6)=(2,2,5,7,11,13) $
	$ (a_1, a_2, a_3, a_4, a_5, a_6)=(3,1,2,12,9,13) $
	$ (a_1, a_2, a_3, a_4, a_5, a_6)=(3,3,3,6,10,15) $
	$ (a_0, a_2, a_3, a_4, a_5, a_6)=(1,3,4,9,10,13) $
	$ (a_0, a_2, a_3, a_5, a_6)=(1,3,10,10,16) $
	$ (a_2, a_3, a_5, a_6)=(3,12,10,15) $
	$ (a_0, a_2, a_4, a_5, a_6)=(1,4,15,6,14) $
	$ (a_0,, a_3, a_5, a_6)=(1,13,13,13) $
$ [15,4,9]_3 $	$ (a_0, a_3, a_6)=(1,13,26) $
	$ (a_3, a_6)=(15,25) $
$ [19,4,12]_3 $	$ (a_{1},a_{4},a_{7})=(1,9,30) $
$ [25,4,16]_3 $	$ (a_{0},a_{7},a_{8},a_{9})=(1,4,18,17) $
$ [26,4,17]_3 $	$ (a_0,a_8,a_{9}) = (1,13,26) $
$ [27,4,18]_3 $	$ (a_0,a_{9}) = (1,39) $
$ [31,4,20]_3 $	$ (a_4,a_9,a_{10},a_{11})=(1,9,12,18) $
	$ (a_{7},a_{8},a_{10},a_{11})=(2,6,11,21) $
$ [32,4,21]_3 $	$ (a_{8},a_{11})=(8,32) $

| Show Table

DownLoad: CSV

Table 8. The spectra of some ternary linear codes of dimension 5

parameters	possible spectra	reference
$ [11,5,6]_3 $	$ (a_{2},a_{5})=(55,66) $	[31]
$ [20,5,12]_3 $	$ (a_{2},a_{5},a_{8})=(10,36,75) $	[31]
$ [25,5,15]_3 $	$ (a_4,a_7,a_{10})=(15,40,66) $	[2]
	$ (a_1,a_4,a_7,a_{10})=(1,12,43,65) $
$ [29,5,18]_3 $	$ (a_{2},a_{5},a_{8},a_{11})=(1,18,18,84) $	[2]
$ [55,5,36]_3 $	$ (a_{10},a_{19}) = (11,110) $	[7]
$ [68,5,44]_3 $	$ (a_{14},a_{15},a_{23},a_{24}) = (1,15,39,65) $	[27]
	$ (a_{14},a_{15},a_{23},a_{24}) = (4,12,36,69) $
$ [69,5,45]_3 $	$ (a_{15},a_{24}) = (16,105) $	[30]
$ [79,5,52]_3 $	$ (a_0,a_{25},a_{26},a_{27})=(1,13,54,53) $	[5]
$ [80,5,53]_3 $	$ (a_0,a_{26},a_{27})=(1,40,80) $	[5]
$ [81,5,54]_3 $	$ (a_0,a_{27})=(1,120) $	[5]
$ [87,5,57]_3 $	$ (a_9,a_{24},a_{27},a_{30})=(1,1,41,78) $	[6]
$ [90,5,59]_3 $	$ (a_{10},a_{27},a_{28},a_{30},a_{31}) = (1,10,20,30,60) $	[26]
	$ (a_{9},a_{27},a_{28},a_{30},a_{31}) = (1,3,27,36,54) $
$ [91,5,60]_3 $	$ (a_{10},a_{28},a_{31}) = (1,30,90) $	[32]

| Show Table

DownLoad: CSV

Table 9. All solutions of (15) with $ w = 8 $

$ t $	solution	line in $ \Sigma^* $	#	$ L_e $
0	$ (c_{13},c_{22},c_{24})=(1,1,1) $	$ (2,1) $	$ x_1 $	56
	$ (c_{14},c_{22},c_{23})=(1,1,1) $	$ (1,3) $	$ x_2 $	46
	$ (c_{16},c_{19},c_{24})=(1,1,1) $	$ (2,1) $	$ x_3 $	38
	$ (c_{17},c_{18},c_{24})=(1,1,1) $	$ (0,2) $	$ x_4 $	36
	$ (c_{16},c_{20},c_{23})=(1,1,1) $	$ (1,3) $	$ x_5 $	34
	$ (c_{17},c_{19},c_{23})=(1,1,1) $	$ (1,3) $	$ x_6 $	31
	$ (c_{18},c_{23})=(2,1) $	$ (0,2) $	$ x_7 $	30
	$ (c_{17},c_{20},c_{22})=(1,1,1) $	$ (1,3) $	$ x_8 $	28
	$ (c_{18},c_{19},c_{22})=(1,1,1) $	$ (2,1) $	$ x_9 $	26
	$ (c_{19},c_{20})=(1,2) $	$ (1,3) $	$ x_{10} $	22
1	$ (c_{16},c_{23})=(1,2) $	$ (1,3) $	$ x_{11} $	28
	$ (c_{17},c_{22},c_{23})=(1,1,1) $	$ (1,3) $	$ x_{12} $	22
	$ (c_{18},c_{22})=(1,2) $	$ (2,1) $	$ x_{13} $	17
	$ (c_{19},c_{20},c_{23})=(1,1,1) $	$ (1,3) $	$ x_{14} $	16
	$ (c_{20},c_{22})=(2,1) $	$ (1,3) $	$ x_{15} $	13
2	$ (c_{19},c_{23})=(1,2) $	$ (1,3) $	$ x_{16} $	10
	$ (c_{20},c_{22},c_{23})=(1,1,1) $	$ (1,3) $	$ x_{17} $	7
3	$ (c_{20},c_{24})=(1,2) $	$ (0,2) $	$ x_{18} $	6
	$ (c_{22},c_{24})=(2,1) $	$ (2,1) $	$ x_{19} $	2
	$ (c_{22},c_{23})=(1,2) $	$ (1,3) $	$ x_{20} $	1
4	$ (c_{23},c_{24})=(1,2) $	$ (0,2) $	$ x_{21} $	0

| Show Table

DownLoad: CSV

Table 10. All solutions of (25) with $ w = 49 $

$ t $	solution	line in $ \Sigma^* $	#	$ L_e $
8	$ (c_{77},c_{89},c_{92})=(1,1,1) $	$ (1,3) $	$ x_1 $	198
	$ c_{86}=3 $	$ (1,3) $	$ x_2 $	135
9	$ (c_{77},c_{92})=(1,2) $	$ (1,3) $	$ x_3 $	183
	$ (c_{86},c_{89})=(2,1) $	$ (1,3) $	$ x_4 $	111
	$ c_{87}=3 $	$ (1,0) $	$ x_5 $	108
13	$ (c_{85},c_{94})=(1,2) $	$ (4,0) $	$ x_6 $	57
	$ (c_{88},c_{91},c_{94})=(1,1,1) $	$ (4,0) $	$ x_7 $	39
	$ c_{91}=3 $	$ (4,0) $	$ x_8 $	30
16	$ c_{94}=3 $	$ (4,0) $	$ 36 $	3
17	$ c_{95}=3 $	$ (1,3) $	$ 26 $	0
18	$ c_{96}=3 $	$ (1,0) $	$ 44 $	0

| Show Table

DownLoad: CSV

Table 11. Values and bounds for $ n_3(6,d) $ for $ d \leq 351 $

$ d $	$ g_3(6,d) $	$ n_3(6,d) $	$ d $	$ g_3(6,d) $	$ n_3(6,d) $	$ d $	$ g_3(6,d) $	$ n_3(6,d) $
1	6	6	61	94	96	121	184	185
2	7	7	62	95	97	122	185	186
3	8	9	63	96	98	123	186	187
4	10	10	64	99	100-101	124	188	189
5	11	11	65	100	101-102	125	189	190
6	12	12	66	101	103	126	190	191
7	14	15	67	103	105	127	193	194-195
8	15	17	68	104	106	128	194	195-196
9	16	18	69	105	107	129	195	196-197
10	19	20	70	107	109	130	197	199
11	20	21	71	108	110	131	198	200
12	21	22	72	109	111	132	199	201
13	23	24	73	112	114	133	201	203
14	24	25	74	113	115	134	202	204
15	25	26	75	114	116	135	203	205
16	27	29	76	116	118	136	207	208-209
17	28	30	77	117	119	137	208	209-210
18	29	31	78	118	120	138	209	210-211
19	32	33-34	79	120	122	139	211	212-213
20	33	34-35	80	121	123	140	212	213-214
21	34	36	81	122	124	141	213	214-215
22	36	38	82	127	127-128	142	215	216-217
23	37	39	83	128	128-129	143	216	217-218
24	38	40	84	129	129-130	144	217	218-219
25	40	42	85	131	131-132	145	220	221-222
26	41	43	86	132	133	146	221	222-223
27	42	44	87	133	134	147	222	223-224
28	46	46-47	88	135	136	148	224	225-226
29	47	48	89	136	137	149	225	227
30	48	49	90	137	138	150	226	228
31	50	51	91	140	140-142	151	228	230
32	51	52	92	141	141-143	152	229	231
33	52	53	93	142	143-144	153	230	232
34	54	54	94	144	145-146	154	233	234
35	55	55	95	145	146-147	155	234	235
36	56	56	96	146	147-148	156	235	236

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	I. G. Bouyukliev, What is Q-Extension?, Serdica J. Computing, 1 (2007), 115-130.
[2]	I. Bouyukliev and J. Simonis, Some new results for optimal ternary linear codes, IEEE Trans. Inform. Theory, 48 (2002), 981-985. doi: 10.1109/18.992814.
[3]	R. Daskalov and E. Metodieva, The nonexistence of ternary $[284, 6,188]$ codes, Probl. Inform. Trans., 40 (2004), 135-146. doi: 10.1023/B:PRIT.0000043927.19508.8b.
[4]	R. Daskalov and E. Metodieva, The nonexistence of ternary [105, 6, 68] and [230, 6,152] codes, Discrete Math., 286 (2004), 225-232. doi: 10.1016/j.disc.2004.06.002.
[5]	N. Hamada, A characterization of some [n, k, d; q]-codes meeting the Griesmer bound using a minihyper in a finite projective geometry, Discrete Math., 116 (1993), 229-268. doi: 10.1016/0012-365X(93)90404-H.
[6]	N. Hamada and T. Helleseth, The uniqueness of [87, 5, 57;3] codes and the nonexistence of [258, 6,171;3] codes, J. Statist. Plann. Inference, 56 (1996), 105-127. doi: 10.1016/S0378-3758(96)00013-4.
[7]	R. Hill, Caps and codes, Discrete Math., 22 (1978), 111-137. doi: 10.1016/0012-365X(78)90120-6.
[8]	R. Hill, Optimal linear codes, Cryptography and Coding, 33 (1992), 75-104.
[9]	R. Hill, An extension theorem for linear codes, Des. Codes Cryptogr., 17 (1999), 151-157. doi: 10.1023/A:1008319024396.
[10]	R. Hill and P. Lizak, Extensions of linear codes, Proc. IEEE Int. Symposium on Inform. Theory, (1995), 345. doi: 10.1109/ISIT.1995.550332.
[11]	R. Hill and D. E. Newton, Optimal ternary linear codes, Des. Codes Cryptogr., 2 (1992), 137-157. doi: 10.1007/BF00124893.
[12]	W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003. doi: 10.1017/CBO9780511807077.
[13]	C. M. Jones, Optimal Ternary Linear Codes, PhD thesis, University of Salford, 2000.
[14]	H. Kanda, A new extension theorem for ternary linear codes and its application, Finite Fields Appl., 67 (2020), 101711. doi: 10.1016/j.ffa.2020.101711.
[15]	K. Kumegawa, T. Okazaki and T. Maruta, On the minimum length of linear codes over the field of 9 elements, Electron. J. Combin., 24 (2017), #P1.50. doi: 10.37236/6394.
[16]	I. N. Landjev, The nonexistence of some optimal ternary linear codes of dimension five, Des. Codes Cryptogr., 15 (1998), 245-258. doi: 10.1023/A:1008317124941.
[17]	I. N. Landjev and T. Maruta, On the minimum length of quaternary linear codes of dimension five, Discrete Math., 202 (1999), 145-161. doi: 10.1016/S0012-365X(98)00354-9.
[18]	I. Landgev, T. Maruta and R. Hill, On the nonexistence of quaternary $[51, 4, 37]$ codes, Finite Fields Appl., 2 (1996), 96-110. doi: 10.1006/ffta.1996.0007.
[19]	I. Landjev and P. Vandendriessche, A study of (xv_t; xv_t−1)-minihypers in PG(t, q), J. Combin. Theory Ser. A, 119 (2012), 1123-1131. doi: 10.1016/j.jcta.2012.02.009.
[20]	T. Maruta, On the achievement of the Griesmer bound, Des. Codes Cryptogr., 12 (1997), 83-87. doi: 10.1023/A:1008250010928.
[21]	T. Maruta, On the nonexistence of $q$-ary linear codes of dimension five, Des. Codes Cryptogr., 22 (2001), 165-177. doi: 10.1023/A:1008317022638.
[22]	T. Maruta, The nonexistence of some ternary linear codes of dimension 6, Discrete Math., 288 (2004), 125-133. doi: 10.1016/j.disc.2004.07.003.
[23]	T. Maruta, Extendability of ternary linear codes, Des. Codes Cryptogr., 35 (2005), 175-190. doi: 10.1007/s10623-005-6400-7.
[24]	T. Maruta, Griesmer bound for linear codes over finite fields, Available from: http://mars39.lomo.jp/opu/griesmer.htm.
[25]	T. Maruta and K. Okamoto, Some improvements to the extendability of ternary linear codes, Finite Fields Appl., 13 (2007), 259-280. doi: 10.1016/j.ffa.2005.09.005.
[26]	T. Maruta and Y. Oya, On optimal ternary linear codes of dimension 6, Adv. Math. Commun., 5 (2011), 505-520. doi: 10.3934/amc.2011.5.505.
[27]	T. Maruta and Y. Oya, On the minimum length of ternary linear codes, Des. Codes Cryptogr., 68 (2013), 407-425. doi: 10.1007/s10623-011-9593-y.
[28]	T. Sawashima and T. Maruta, Nonexistence of some ternary linear codes, Discrete Math., 344 (2021), 112572. doi: 10.1016/j.disc.2021.112572.
[29]	M. Takenaka, K. Okamoto and T. Maruta, On optimal non-projective ternary linear codes, Discrete Math., 308 (2008), 842-854. doi: 10.1016/j.disc.2007.07.044.
[30]	M. van Eupen and R. Hill, An optimal ternary $[69, 5, 45]$ code and related codes, Des. Codes Cryptogr., 4 (1994), 271-282. doi: 10.1007/BF01388456.
[31]	M. van Eupen and P. Lisonêk, Classification of some optimal ternary linear codes of small length, Des. Codes Cryptogr., 10 (1997), 63-84. doi: 10.1023/A:1008292320488.
[32]	Y. Yoshida and T. Maruta, Ternary linear codes and quadrics, Electronic J. Combin., 16 (2009), #R9, 21pp. doi: 10.37236/98.