A class of linear codes with their complete weight enumerators over finite fields (Q2121001)

In this paper, the authors consider a class of linear trace codes over finite fields and explicitly compute their complete weight enumerators. They use this to produce optimal constant composition codes. \textit{Complete weight enumerators.} First, we briefly recall the definition of complete weight enumerators. Let \(\mathcal{C}\) be any linear \([n,k,d]\)-code over \(\mathbb{F}_q\). The number of nonzero coordinates in a codeword \(c \in \mathcal{C}\) is called the Hamming weight \(w(c)\) of \(c\). The \textit{weight distribution} of \(\mathcal{C}\) is the collection \((1, A_1, \ldots, A_n)\) where the number \(A_i=\#\{c \in \mathcal{C} : w(c)=i\}\) denotes the number of codewords in \(\mathcal{C}\) having weight \(i\), for each \(i=0,\ldots, n\). The \textit{weight enumerator} of \(\mathcal{C}\) is the polynomial \(W_\mathcal{C}(x) = 1 + A_1 x + A_2 x^2 + \cdots + A_n x^n\). The complete weight enumerator of \(\mathcal{C}\) gives the frequency of each symbol contained in each codeword. Assume that \(\mathbb{F}_{p^e} = \{w_0=0, w_1, \dots, w_{p^e-1}\}\). The composition of a vector \(v=(v_0, v_1, \ldots, v_{n-1}) \in (\mathbb{F}_{p^e})^n\) is defined as \(\mathrm{comp}(v) = (k_0, k_1, \ldots, k_{p^e-1})\), where \(k_j\) is the number of components \(v_i\) of \(v\) with \(0 \le i \le n-1\) that equal \(w_j\). Let \(A(k_0, k_1, \ldots, k_{p^e -1})\) be the number of codewords \(c \in \mathcal{C}\) with \(\mathrm{comp}(c)=(k_0, k_1,\ldots, k_{p^e-1})\). Then the \textit{complete weight enumerator} of the code \(\mathcal{C}\) is the polynomial \[ \mathrm{CWE}(\mathcal{C}) = \sum_{c \in \mathcal{C}} w_0^{k_0} w_1^{k_1} \cdots w_{p^e-1}^{k_{p^e-1}} = \sum_{(k_0, k_1, \ldots, k_{p^e-1}) \in B_n} A(k_0, k_1, \ldots, k_{p^e-1}) \, w_0^{k_0} w_1^{k_1} \cdots w_{p^e-1}^{k_{p^e-1}} \] where \(B_n = \{(k_0, k_1, \ldots, k_{p^e-1}) : 0 \le k_j \le n, \sum_{j =0}^{p^e-1} k_j = n\}\). The complete weight enumerators of linear codes not only give the weight enumerators but also the frequency of each symbol appearing in each codeword. \textit{The trace codes \(\mathcal{C}_D\).} The authors consider the following family of trace codes using the relative trace map instead of the absolute trace map as previously used in the works [\textit{J. Ahn} et al., Des. Codes Cryptography 83, No. 1, 83--99 (2017; Zbl 1379.94054); \textit{C. Li} et al., Des. Codes Cryptography 81, No. 1, 153--168 (2016; Zbl 1379.94058); \textit{Y. Liu} and \textit{Z. Liu}, Discrete Math. 341, No. 7, 1959--1972 (2018; Zbl 1439.94095); \textit{Q. Wang} et al., Discrete Math. 340, No. 3, 467--480 (2017; Zbl 1407.94183); \textit{S. Yang} et al., Finite Fields Appl. 48, 196--226 (2017; Zbl 1403.94115); \textit{S. Yang} and \textit{Z.-A. Yao}, Des. Codes Cryptography 82, No. 3, 663--674 (2017; Zbl 1370.94578); \textit{S. Yang} et al., Cryptogr. Commun. 9, No. 1, 133--149 (2017; Zbl 1416.94069)]. Let \(e,s,m,p \in \mathbb N\) with \(m=es>2\) and \(p\) an odd prime. Take finite field extensions \(\mathbb{F}_p \subset \mathbb{F}_{p^e} \subset \mathbb{F}_{p^m}\) and let \(\operatorname{Tr}_e^m\) denote the relative trace mapping from \(\mathbb{F}_{p^m}\) to \(\mathbb{F}_{p^e}\), that is \(\operatorname{Tr}_e^m(x) = \sum_{k=0}^{s-1} x^{p^{ke}}\). Consider the defining set \[ D= \{x \in \mathbb{F}_{p^m} : \operatorname{Tr}_e^m(x) =1, \operatorname{Tr}_e^m(x^2)=0\}=\{d_1,\ldots,d_n\} \subset (\mathbb{F}_{p^m})^n \tag{1} \] and define the linear \(p^e\)-ary code \[ \mathcal{C}_D = \{c_a = \big( \operatorname{Tr}_e^m(ad_1), \ldots, \operatorname{Tr}_e^m(ad_n) \big) : a \in \mathbb{F}_{p^m} \} \tag{2} \] of length \(n\). \textit{The results on complete weight enumerators.} The authors compute the complete weight numerators \(\mathrm{CWE}(\mathcal{C}_D)\) -- and the weight distribution -- of the codes \(\mathcal{C}_D\) defined in (2) in a standard way, by explicitly computing certain exponential sums involved associated to the set \(D\). The usual machinery in the subject like cyclotomic numbers, character Gauss sums and orthogonality of characters are recalled in Section 2 and used later in the computations in Section 3. Since \(m=es\), almost all the computations and results have to be divided into four cases: (a) \(2\mid s\) and \(p\mid s\), \qquad (b) \(2\mid s\) and \(p \nmid s\), \qquad (c) \(2\nmid s\) and \(p\mid s\), \qquad (d) \(2\nmid s\) and \(p \nmid s\). In Lemma 3.1, the numbers \[ N(\lambda,\mu)=\#\{x\in \mathbb{F}_{p^m} : \operatorname{Tr}_e^m(x^2)=\lambda, \operatorname{Tr}_e^m(x)=\mu \} \tag{3} \] are explicitly computed for any \(\lambda, \mu \in \mathbb{F}_{p^e}\), in the four cases mentioned above. In particular, \(N(0,1)\) gives the length \(n\) of the code \(\mathcal{C}_D\). In subsequent Lemmas 3.2, 3.3 and 3.4, the authors explicitly compute the numbers \[ \begin{aligned} \mathcal{N}_2 & = \sum_{x \in \mathbb{F}_{p^m}} \sum_{y \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(y(\operatorname{Tr}_e^m(x)-1))} \sum_{w \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(w(\operatorname{Tr}_e^m(ax)-c))}, \\ \mathcal{N}_3 & = \sum_{x \in \mathbb{F}_{p^m}} \sum_{z \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(z(\operatorname{Tr}_e^m(x^2))} \sum_{w \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(w(\operatorname{Tr}_e^m(ax)-c))}, \\ \mathcal{N}_4 & = \sum_{x \in \mathbb{F}_{p^m}} \sum_{y \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(y(\operatorname{Tr}_e^m(x)-1))} \sum_{z \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(z(\operatorname{Tr}_e^m(x^2))} \sum_{w \in \mathbb{F}_{p^e}^*} \zeta_p^{\operatorname{Tr}_1^e(w(\operatorname{Tr}_e^m(ax)-c))}, \end{aligned} \tag{4} \] where \(a\in \mathbb{F}_{p^m}^*\) and \(c\in \mathbb{F}_{p^e}^*\) and \(\zeta_p=e^{\frac{2\pi i}p}\). These computations are lengthy and technical. The key observation of the paper is the following. Let \(a\in \mathbb{F}_{p^m}^*\) and \(c\in \mathbb{F}_{p^e}^*\). For a codeword \(c_a \in \mathcal{C}_D\), let \(n\) be the length of \(c_a\) and denote by \(N_c(a)\) the number of components \(\operatorname{Tr}_e^m(ax)\) of \(c_a\) that are equal to \(c\), that is \[ N_c(a) = \#\{x \in \mathbb{F}_{p^m} : \operatorname{Tr}_e^m(x)=1, \operatorname{Tr}_e^m(x^2)=0 \text{ and } \operatorname{Tr}_e^m(ax)=c\}. \] Thus, these numbers can be computed in terms of \(\mathcal{N}_2\), \(\mathcal{N}_3\) and \(\mathcal{N}_4\) as follows \begin{align*} N_c(a) & = \tfrac{1}{p^{3e}} \sum_{x\in \mathbb{F}_{p^m}} \Big( \sum_{y \in \mathbb{F}_{p^e}} \zeta_p^{\operatorname{Tr}_1^e(y(\operatorname{Tr}_e^m(x)-1))} \Big) \Big( \sum_{z \in \mathbb{F}_{p^e}} \zeta_p^{\operatorname{Tr}_1^e(z(\operatorname{Tr}_e^m(x^2))} \Big) \Big( \sum_{w \in \mathbb{F}_{p^e}} \zeta_p^{\operatorname{Tr}_1^e(w(\operatorname{Tr}_e^m(ax)-c))} \Big) \\ & = \tfrac{n}{p^e} + \tfrac{1}{p^{3e}} \sum_{x\in \mathbb{F}_{p^m}} \sum_{y \in \mathbb{F}_{p^e}} \zeta_p^{\operatorname{Tr}_1^e(y(\operatorname{Tr}_e^m(x)-1))} \sum_{z \in \mathbb{F}_{p^e}} \zeta_p^{\operatorname{Tr}_1^e(z(\operatorname{Tr}_e^m(x^2))} \sum_{w \in \mathbb{F}_{p^e}} \zeta_p^{\operatorname{Tr}_1^e(w(\operatorname{Tr}_e^m(ax)-c))} \\ & = \tfrac{n}{p^e} + \tfrac{1}{p^{3e}} (\mathcal{N}_2 + \mathcal{N}_3 + \mathcal{N}_4). \end{align*} As a consequence, explicit computations of \(N_c(a)\) in some particular cases leads to the determination of the complete weight enumerators (theorems) and the weight distribution (corollaries) of codes \(\mathcal{C}_D\) defined in (2), as well as their parameters, respectively as follows: \begin{itemize} \item[(a)] Theorem 3.7 and Corollary 3.8 (and Tables 1, 2), for \(2\mid s\) and \(p\mid s\). \item[(b)] Theorem 3.10 and Corollary 3.11 (and Tables 3, 4), for \(2\mid s\) and \(p \nmid s\). \item[(c)] Theorem 3.14 and Corollary 3.15 (and Tables 5, 6), for \(2 \nmid s\) and \(p\mid s\). \item[(d)] Theorem 3.17 and Corollary 3.18 (and Tables 6, 7), for \(2\nmid s\) and \(p\nmid s\). \end{itemize} The code \(\mathcal{C}_D\) have parameters \([n,s]\) where the length is given by \(n=p^{m-2e}\) in the cases (a) and (c), \(n=p^{m-2e}-(-1)^{\frac{(p-1)^2m}{8}} p^{\frac{m-2e}{2}}\) in case (b) and \[ n=p^{m-2e} - \bar\eta(-s)(-1)^{m+e-2} (-1)^{\frac{(p-1)^2(m+e)}{8}} p^{\frac{m-3e}{2}} \] in case (d), where \(\eta\) is the quadratic character. Moreover, in the case \(2 \nmid s\) and \(p\mid s\), in Corollary 3.20 it is shown that \(\mathcal{C}_D\) is optimal with respect to the Griesmer bound only if \(s=3\). Furthermore, if \(s=p=3\) then \(\mathcal{C}_D\) is an MDS code with parameters \([3^e,3,3^e-2]\). In Tables 9 and 10, the authors compare the parameters of the codes \(\mathcal{C}_D\) with the corresponding ones in [\textit{S. Yang} et al., Finite Fields Appl. 48, 196--226 (2017; Zbl 1403.94115)], showing that their codes has better error-correcting capabilities than those in [\textit{S. Yang} et al., Finite Fields Appl. 48, 196--226 (2017; Zbl 1403.94115)]. Then, in Theorem 3.22, the authors give bounds for the minimum distance \(d^\perp\) of the dual code \(\mathcal{C}_D^\perp\) of \(\mathcal{C}_D\), obtaining that \[ 3\le d^\perp \le 4 \] if either (\(a\)) \(2\mid s\) and \(p\mid s\), or (\(b\)) \(2\mid s\), \(p \nmid s\) and \(e\ge 2\) or else (\(c\)) \(2\nmid s\) and \(e\ge 2\). \textit{Results on constant composition codes.} Finally, in Section 4, the authors use the complete weight enumerators of \(\mathcal{C}_D\) computed in Theorems 3.7, 3.10, 3.14 and 3.17 to construct some optimal constant composition codes. Constant composition codes are a subclass of constant weight codes. Let \(r\in \mathbb{N}\) and let \(A = \{a_0, a_1, \ldots, a_{r-1}\}\) be a code alphabet. Any subset \(C \subset S^n\) of size \(M\) and minimum distance \(d\) such that each word has the same composition \(v=(t_0, t_1, \ldots, t_{r-1})\) is known as an \((n, M, d,v)\) constant composition code over \(S\). For such kind of codes, there is the LFVC-bound [\textit{Y. Luo} et al., IEEE Trans. Inf. Theory 49, No. 11, 3010--3016 (2003; Zbl 1181.94132)]: for an \((n, M, d,v)\) constant composition code with \[ B:=nd-n^2+(t_0^2+\cdots+t_{r-1}^2)\ge 0 \quad \text{one has} \quad M\ge \frac{nd}{B}. \] Any constant composition code satisfying equality in the LFVC-bound is called \textit{optimal}. In Theorem 4.2 and 4.3, using the CWE's obtained in Theorems 3.10 and 3.17, optimal \((n, M, d,v)\) constant composition codes \(\tilde{\mathcal{C}}\) over \(\mathbb{F}_{p^e}\) are constructed where \begin{align*} n&=p^{m-2e}-p^{\frac{m-2e}{2}}, M=p^{\frac{m-2e}{2}}-1, d=p^{m-2e}-p^{m-3e}, t_0=p^{m-3e}-p^{\frac{m-2e}2}, t_i=p^{m-3e}, \\ n&=p^{m-2e}-p^{\frac{m-3e}{2}}, M=p^{\frac{m-e}{2}}-1, \ d=p^{m-2e}-p^{m-3e}, t_0=p^{m-3e}-p^{\frac{m-3e}2}, t_i=p^{m-3e}, \end{align*} for \(i=1,\ldots,r-1\), respectively (here, \(m=4e\) in the first case and \(m=3e\) in the second one). \textit{Final remarks.} The paper is well written and has some examples to illustrate the results. The computations are done in great detail.