Article Contents
Article Contents

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

• * Corresponding author: Tatsuya Maruta

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

• 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.

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

 Citation:

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

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$

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

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$

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$

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

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

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]

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

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

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
•  [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 (xvt; xvt−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.

Tables(11)