January 01, 1970
Ternary maximal self-orthogonal codes have been classified for lengths up to \(24\). In this note, we provide a complete classification of ternary maximal self-orthogonal codes of length \(25\).
Let \(\mathbb{F}_3 = \{0, 1, 2\}\) denote the finite field of order 3. A ternary \([n,k]\) code \(C\) is a \(k\)-dimensional vector subspace of \(\mathbb{F}_3^n\). The parameters \(n\) and \(k\) are called the length and the dimension of \(C\), respectively. The weight \(\mathop{\mathrm{wt}}(x)\) of a vector \(x \in \mathbb{F}_3^n\) is the number of non-zero components of \(x\). A vector in \(C\) is called a codeword of \(C\). The minimum non-zero weight of all codewords in \(C\) is called the minimum weight of \(C\). A ternary \([n,k,d]\) code is a ternary \([n,k]\) code with minimum weight \(d\).
The dual code \(C^{\perp}\) of a ternary code \(C\) of length \(n\) is defined as: \[C^{\perp}= \{x \in \mathbb{F}_3^n \mid x \cdot y = 0 \text{ for all } y \in C\},\] where \(x \cdot y\) denotes the standard inner product of \(x\) and \(y\). A ternary code \(C\) is self-orthogonal if \(C\subset C^\perp\), and \(C\) is self-dual if \(C = C^\perp\). A ternary self-dual code of length \(n\) exists if and only if \(n \equiv 0 \pmod 4\) with \(n >0\). A ternary self-orthogonal code \(C\) is maximal if \(C\) is the only self-orthogonal code containing \(C\). A self-dual code is automatically maximal. A maximal self-orthogonal code of length \(n\) has dimension \((n-1)/2\) if \(n\) is odd and \(n/2-1\) if \(n \equiv 2 \pmod 4\) (see [1]).
Two ternary codes \(C\) and \(C'\) are equivalent if there is a monomial matrix \(P\) such that \(C' = C \cdot P\), where \(C \cdot P = \{ x P\:|\: x \in C\}\). Ternary maximal self-orthogonal codes were classified in [1] for lengths up to \(12\). This classification was extended to lengths \(13\), \(14\), \(15\) and \(16\) in [2], and lengths \(17\), \(18\), \(19\) and \(20\) in [3] (see [4] for lengths \(18\) and \(19\)). Subsequently, ternary self-dual codes of length 24 were classified in [5]. Building on this classification, ternary maximal self-orthogonal codes of lengths \(21\), \(22\) and \(23\) were classified in [6].
In this note, we establish the following theorem, which is another consequence of the classification of ternary self-dual codes of length \(24\).
Theorem 1. There are \(139613\) inequivalent ternary maximal self-orthogonal \([25,12]\) codes. Of these, \(26\), \(118984\) and \(20603\) have minimum weights \(9\), \(6\) and \(3\), respectively.
This completes the classification of ternary maximal self-orthogonal codes for all lengths up to \(25\). To summarize, Table ¿tbl:Tab:C? lists the number \(N(n)\) of inequivalent ternary maximal self-orthogonal codes of length \(n\) together with the corresponding references for \(3 \le n \le 25\) (see Proposition 4 for lower bounds on \(N(26)\), \(N(27)\), \(N(28)\), \(N(29)\) and \(N(30)\)).
In this section, we present the methodology used to establish the classification given in Theorem 1.
A shortened code \(C'\) of a ternary code \(C\) is the set of all codewords in \(C\) which are \(0\) in a fixed coordinate with that coordinate deleted. A shortened code \(C'\) of a ternary self-orthogonal \([n,k,d]\) code \(C\) is a ternary self-orthogonal \([n-1,k,d]\) code if the deleted coordinate is a zero coordinate, and a ternary self-orthogonal \([n-1,k-1,d']\) code with \(d' \ge d\) otherwise (see e.g., [7]).
We consider the inverse operation of shortening, which is referred to as lengthening. A ternary self-orthogonal \([n,k,d]\) code gives \(n\) shortened codes and at least \(k\) codes among them are self-orthogonal \([n-1,k-1,d']\) codes with \(d' \ge d\). Hence, by applying the inverse operation of shortening, any ternary self-orthogonal \([n,k,d]\) code can be constructed from some ternary self-orthogonal \([n-1,k-1,d']\) code with \(d' \ge d\) as follows. Let \(C'\) be a ternary self-orthogonal \([n-1,k-1,d']\) code with \(d' \ge d\). Up to equivalence, we may assume that \(C'\) has a generator matrix of the form \(\left(\begin{array}{cc} I_{k-1} & A \end{array}\right)\), where \(I_{k-1}\) denotes the identity matrix of order \(k-1\). Then, up to equivalence, a ternary self-orthogonal \([n,k,d]\) code constructed from \(C'\) by applying the inverse operation of shortening, has the following generator matrix: \[\label{eq:gm} G(A,b)= \left(\begin{array}{c|ccc|cccccccc} 1&0 & \cdots& 0 &b_1 &\cdots&b_{n-k}\\ \hline 0& & & & & &\\ \vdots& &I_{k-1}& & &A &\\ 0& & & & & & \end{array}\right),\tag{1}\] where \(b=(b_1,b_2,\ldots,b_{n-k}) \in\mathbb{F}_3^{n-k}\) satisfies the following condition:
Here \(\mathbf{0}\) denotes the zero vector. It is sufficient to consider the vectors \(b \in\mathbb{F}_3^{n-k}\) satisfying the following condition:
since ternary codes with generator matrices \(G(A,b)\) and \(G(A,2b)\) are equivalent.
Suppose that \(k \ge 2\) if \(n\) is even, \(n \ge 2k\), \(\varepsilon=1\) if \(n \equiv 0 \pmod 4\) and \(\varepsilon=-1\) if \(n \equiv 2 \pmod 4\). The number \(T(n,k)\) of all distinct ternary self-orthogonal \([n,k]\) codes is given by: \[\label{eq:mf} T(n,k)= \begin{cases} \displaystyle \frac{(3^{n-k}-\varepsilon3^{\frac{n}{2}-k}+\varepsilon3^{\frac{n}{2}}-1) \prod_{i=1}^{k-1}(3^{n-2i}-1)}{\prod_{i=1}^{k}(3^i-1)} &\text{if n is even,} \\ \displaystyle \frac{\prod_{i=0}^{k-1}(3^{2(\frac{n-1}{2}-i)}-1)}{\prod_{i=1}^{k}(3^i-1)} &\text{if n is odd} \end{cases}\tag{2}\] (see [8]). The automorphism group \(\mathop{\mathrm{Aut}}(C)\) of a ternary code \(C\) is the group of all monomial matrices \(P\) with \(C = C \cdot P\). Let \({\boldsymbol{C}_{n,k}}\) be a set of all inequivalent ternary self-orthogonal \([n,k]\) codes. It is trivial that \[T(n,k)=\sum_{C \in {\boldsymbol{C}_{n,k}}} \frac{2^n n!}{|\mathop{\mathrm{Aut}}(C)|},\] and this is called the mass formula for ternary self-orthogonal \([n,k]\) codes.
For equivalence testing and automorphism group computation of ternary codes, we employ the approach given in [9] as follows.
Let \(C\) be a ternary \([n,k]\) code and let \(C(i)\) be the set of codewords of weight \(i\) in \(C\). Take a subset \(W(C)\) of \(\{1,2,\ldots,n\}\) such that \[\left\langle x \,\middle|\, x \in \mathop{\cup}_{i \in W(C)} C(i) \right\rangle =C.\] Define the vertex-colored digraph \(\Gamma_{W(C)}(C)\) with the following vertex set: \[\left(\mathop{\cup}_{i \in W(C)} C(i) \right)\cup (\{1,2,\dots,n\}\times (\mathbb{F}_3 \setminus\{0\}))\] and the following arc set: \[\begin{align} & \left\{(c,(j,c_j)), ((j,c_j),c) \,\middle|\, c=(c_1,c_2,\ldots,c_{n}) \in \mathop{\cup}_{i \in W(C)} C(i), 1 \le j \le n, c_j\ne 0\right\} \\& \cup \{((j,y),(j, 2y))\mid 1 \le j \le n,\;y \in \mathbb{F}_3 \setminus \{0\}\}. \end{align}\] Let \(C\) and \(C'\) be two ternary \([n,k,d]\) codes. Suppose that \(W(C) = W(C')\). Then \(C\) and \(C'\) are equivalent if and only if \(\Gamma_{W(C)}(C)\) and \(\Gamma_{W(C')}(C')\) are isomorphic as vertex-colored digraphs. The order of the automorphism group of \(\Gamma_{W(C)}(C)\) is the same as \(|\mathop{\mathrm{Aut}}(C)|\). We use nauty [10] for isomorphism testing and automorphism group computation of vertex-colored digraphs.
In our calculations in Section 3, we took \(W(C)=\{9\}\), \(\{12\}\) or \(\{24\}\) in most cases. However, in one particular case, it was necessary to take \(W(C)=\{9,24\}\) in order to carry out the computation of the automorphism group. This can also be carried out using the functions provided in Magma [11].
In this section, we present the classification results obtained by the methodology described in the previous section. Computer calculations in this section were performed using by programs written in C/C++ with nauty [10] and NTL [12] as well as programs written in Magma [11].
There are two inequivalent ternary (extremal) self-dual \([24,12,9]\) codes [13]. There are \(166\) inequivalent ternary self-dual \([24, 12, 6]\) codes and there are \(170\) inequivalent ternary self-dual \([24, 12, 3]\) codes [5]. Note that \(9\) is the largest minimum weight among all ternary self-dual \([24,12]\) codes.
The dual distance of a ternary code \(C\) is defined as the minimum weight of \(C^\perp\). It is trivial that any ternary maximal self-orthogonal \([25,12]\) code with dual distance \(1\) is equivalent to the ternary code constructed as: \[\{(x_1,x_2,\ldots,x_{24},0) \mid (x_1,x_2,\ldots,x_{24}) \in C\},\] where \(C\) is a self-dual code of length \(24\). Then we have the following:
Proposition 2. There are two, \(166\) and \(170\) inequivalent ternary maximal self-orthogonal \([25,12,d]\) codes with dual distances \(1\) for \(d=9\), \(6\) and \(3\), respectively.
To find all ternary maximal self-orthogonal \([25,12]\) codes, which require checking for equivalence by the lengthening operation, a classification of ternary self-orthogonal \([24,11]\) codes is necessary. Moreover, any ternary self-orthogonal \([24,11]\) code is contained in some ternary self-dual \([24,12]\) code (see e.g., [1]). By enumerating all ternary self-orthogonal \([24,11]\) subcodes of all inequivalent ternary self-dual \([24,12]\) codes, we obtained candidates, which were then subjected to equivalence testing. After the equivalence testing described in the previous section, we completed the classification of ternary self-orthogonal \([24,11]\) codes, as summarized in the following proposition.
Proposition 3. There are \(1373\), \(2745294\) and \(339492\) inequivalent ternary self-orthogonal \([24,11,d]\) codes for \(d=9\), \(6\) and \(3\), respectively.
Let \({\boldsymbol{C}_{24,11}}\) denote the set of all inequivalent ternary self-orthogonal \([24,11]\) codes. As a check, we verified the mass formula: \[\begin{align} \sum_{C \in {\boldsymbol{C}_{24,11}}}\frac{2^{24}24!}{|\mathop{\mathrm{Aut}}(C)|} &=12850554292569078425974899530137600000\\ &=T(24,11), \end{align}\] (see 2 for the value \(T(24,11)\)). The mass formula confirms that there are no other ternary self-orthogonal \([24,11]\) codes, and thus the classification is complete.
By applying the lengthening operation to the ternary self-orthogonal \([24,11]\) codes given in Proposition 3, we obtained candidates for ternary maximal self-orthogonal \([25,12]\) codes, which were then subjected to equivalence testing. We tested the equivalence of these codes together with those given in Proposition 2 using the method described in the previous section. After performing the equivalence testing, we completed the classification of ternary maximal self-orthogonal \([25,12]\) codes, as stated in Theorem 1.
In Tables ¿tbl:Tab:Aut9?, ¿tbl:Tab:Aut6? and ¿tbl:Tab:Aut3?, we list the orders \(|\mathop{\mathrm{Aut}}|\) of automorphism groups of self-orthogonal \([25,12,d]\) codes, together with the number \(N\) of codes having each order for \(d=9\), \(6\) and \(3\), respectively.
As a check, we verified the mass formula: \[\begin{align} \sum_{C \in {\boldsymbol{C}_{25,12}}}\frac{2^{25}25!}{|\mathop{\mathrm{Aut}}(C)|} &=25701205307660304745058529866383360000 \\ &=T(25,12), \end{align}\] where \({\boldsymbol{C}_{25,12}}\) denotes the set of all inequivalent ternary maximal self-orthogonal \([25,12]\) codes (see Tables ¿tbl:Tab:Aut9?, ¿tbl:Tab:Aut6? and ¿tbl:Tab:Aut3? for the orders \(|\mathop{\mathrm{Aut}}(C)|\) and see 2 for the value \(T(25,12)\)). The mass formula confirms that there are no other ternary maximal self-orthogonal \([25,12]\) codes, and thus the classification is complete. The ternary maximal self-orthogonal codes of length \(25\) are available electronically from https://www.math.is.tohoku.ac.jp/~mharada/T25/.
We derive a (not necessarily tight) lower bound on the number of inequivalent ternary maximal self-orthogonal codes of larger lengths by using the mass formula. This is a classical technique in the study of self-dual codes (see e.g., [14]), and we adapt it to the setting of ternary maximal self-orthogonal codes. Let \(C\) be a ternary self-orthogonal \([n,k]\) code. Since \(\{I_n,2I_n\}\) is a subgroup of the automorphism group \(\mathop{\mathrm{Aut}}(C)\) of \(C\), we have that \(|\mathop{\mathrm{Aut}}(C)| \ge 2\). Let \({\boldsymbol{C}_{n,k}}\) denote a set of all inequivalent ternary self-orthogonal \([n,k]\) codes. Since the mass formula gives that \[T(n,k) =\sum_{C \in {\boldsymbol{C}_{n,k}}} \frac{2^n n!}{|\mathop{\mathrm{Aut}}(C)|} \le |{\boldsymbol{C}_{n,k}}| 2^{n-1} n!,\] we have that \[|{\boldsymbol{C}_{n,k}}| \ge \left\lceil \frac{T(n,k)}{2^{n-1}n!} \right\rceil,\] where \(\lceil x \rceil\) denotes the smallest integer greater than or equal to \(x\). We computed the values: \[\left\lceil \frac{T(n,k)}{2^{n-1}n!} \right\rceil = \begin{cases} 757009213 &\text{if } (n,k)=(26,12), \\ 56074757 &\text{if } (n,k)=(27, 13),\\ 2002670 &\text{if } (n,k)=(28,14), \\ 82575085630 &\text{if } (n,k)=(29, 14), \\ 4936926278278054 &\text{if } (n,k)=(30, 14). \end{cases}\] These values yield the lower bounds shown below.
Proposition 4. Let \(N(n)\) denote the number of inequivalent ternary maximal self-orthogonal codes of length \(n\). Then \[\begin{array}{ll} N(26) \ge 757009213, & N(27) \ge 56074757, \\ N(28) \ge 2002670, & N(29) \ge 82575085630\text{ and } \\ N(30) \ge 4936926278278054. \end{array}\]
Finally, we turn to an application of a classification of ternary maximal self-orthogonal codes of length \(25\). By applying the method given in [4] to this classification, it is a worthwhile project to complete a classification of weighing matrices of order \(25\) and weight \(9\).
Acknowledgments. This work is supported by JSPS KAKENHI Grant Numbers 23H01087 and 25K07111. In this research work, we used the supercomputer of ACCMS, Kyoto University.