Few-weight quaternary codes via simplicial complexes

1.   Introduction

Let $m$ be a positive integer, $q$ be a power prime, and $(V_m, \cdot)$ be an $m$-dimensional vector space over $\Bbb F_q$, where $\cdot$ denotes an inner product on $V_m$. For a linear code of length $n$ over $\Bbb F_q$, there is a generic construction as follows:

where, $D = \{d_1, \cdots, d_n\} \subseteq V_m$. The set $D$ is called the defining set of the code $\mathcal{C}_{D}.$ Although different orderings of the elements of $D$ result in different codes, these codes are permutation equivalent and have the same parameters. If the set $D$ is properly chosen, the code $\mathcal{C}_{D}$ may have good parameters. The following two situations are common:

(1) When $V_m = \Bbb F_{q^m}$, $x\cdot y = \mbox{Tr}_m(xy)$ for $x, y\in \Bbb F_{q^m}$ and $\mbox{Tr}_m$ is the trace function from $\Bbb F_{q^m}$ to $\Bbb F_{q}$. In this case, the corresponding code $\mathcal C_D$ in (1.1) is called a trace code over $\Bbb F_q$. This generic construction was first introduced by Ding et al. ^[3]. Many known codes have been produced by selecting a proper defining set, see ^[6,10] for examples. Note that defining sets here are almost all related with trace functions, and the computations of weight distributions of corresponding linear codes are heavily dependent on known results of exponential sums.

(2) When $V_m = \Bbb F_q^m$, ${\mathbf x}\cdot {\mathbf y} = \sum_{i = 1}^mx_iy_i$ for ${\mathbf x} = (x_1, \ldots, x_m), {\mathbf y} = (y_1, \ldots, y_m)\in \Bbb F_q^m.$ This standard construction in (1.1) can be also found in ^[7]. Recently, Zhou et al. ^[13] investigated four infinite families of binary linear codes and obtained some binary linear complementary dual or self-orthogonal codes based on the above generic construction.

Based on the construction for linear codes from functions, Hyun et al. ^[9] constructed some infinite families of binary optimal linear codes by choosing the support set of a Boolean function as the complement of some simplicial complexes. After that, a more general situation was considered by Hyun et al. ^[8] by using posets, and they presented some optimal and minimal binary linear codes not satisfying the condition of Ashikhmin-Barg ^[1]. Notice that linear codes from the generic construction via posets are all over prime fields and the main difficulty is to calculate the frequencies of their codewords. It seems that new techniques are required to go beyond prime fields. In this paper, we will provide such a technique for linear codes over the finite field $\Bbb F_4$.

The rest of this paper is organized as follows. In Section 2, we will recall some concepts of simplicial complexes, generating functions and investigate the structure of the finite field $\Bbb F_4$. In Section 3, we determine the weight distributions of these quaternary codes and find a class of minimal quaternary linear codes.

2.   Preliminaries

Let $\mathcal{C}$ be an $[n, k, d]$ linear code over $\Bbb F_q$. Assume that there are $A_i$ codewords in $\mathcal C$ with Hamming weight $i$ for $1\le i \le n$. Then $\mathcal C$ has weight distribution $(1, A_1, \ldots, A_n)$ and weight enumerator $1+A_1z+\cdots +A_nz^n$. Moreover, if the number of nonzero $A_{i}$'s in the sequence $(A_1, \ldots, A_n)$ is exactly equal to $t$, then the code is called $t$-weight. An $[n, k, d]$ code $\mathcal{C}$ is called distance optimal if there is no $[n, k, d+1]$ code (that is, this code has the largest minimum distance for given length $n$ and dimension $k$), and it is called almost optimal if an $[n, k, d + 1]$ code is distance optimal (refer to [7, Chapter 2]). On the other hand, the Griesmer bound ^[5] on an $[n, k, d]$ linear code over $\Bbb F_q$ is given by $\sum_{i = 0}^{k-1}\bigg\lceil {\frac{d}{q^i}} \bigg\rceil \le n,$ where $\lceil {\cdot} \rceil$ is the ceiling function. We say that a linear code is a Griesmer code if it meets the Griesmer bound with equality. One can verify that Griesmer codes are distance-optimal.

2.1.   Simplicial complexes and generating functions

Let $\Bbb F_q$ be the finite field with order $q$. Assume that $m$ is a positive integer. The support $\mathrm{supp}({\mathbf v})$ of a vector ${\mathbf v} \in \Bbb F_q^m$ is defined by the set of nonzero coordinates. The Hamming weight $wt({\mathbf v})$ of ${\mathbf v}\in \mathbb{F}^m_q$ is defined by the size of $\mathrm{supp}({\mathbf v})$. For two subsets $A, B\subseteq [m]$, the set $\{x: x\in A\mbox{ and } x\notin B\}$ and the number of elements in the set $A$ are denoted by $A\backslash B$ and $|A|$, respectively.

For two vectors ${\mathbf u, v}\in \mathbb{F}_2^m$, we say ${\mathbf v}\subseteq {\mathbf u }$ if $\mathrm{supp}({\mathbf v})\subseteq \mathrm{supp}({\mathbf u})$. We say that a family $\Delta \subseteq \mathbb{F}_2^m$ is a simplicial complex if ${\mathbf u}\in \Delta$ and ${\mathbf v}\subseteq {\mathbf u}$ imply ${\mathbf v}\in \Delta$. For a simplicial complex $\Delta$, a maximal element of $\Delta$ is one that is not properly contained in any other element of $\Delta$. Let $\mathcal{F} = \{F_1, \ldots, F_l\}$ be the family of maximal elements of $\Delta$. For each $F\subseteq [m]$, the simplicial complex $\Delta_F$ generated by $F$ is defined to be the family of all subsets of $F$.

Let $X$ be a subset of $\mathbb{F}_2^m$. Hyun et al. ^[2] introduced the following $m$-variable generating function associated with the set $X$:

where ${\mathbf u} = (u_1, u_2, \ldots, u_m)\in \mathbb{F}_2^m$ and $\mathbb{Z}$ is the ring of integers.

The following lemma plays an important role in determining the weight distributions of the quaternary codes defined in (1.1).

Lemma 2.1. [2, Theorem 1] Let $\Delta$ be a simplicial complex of $\mathbb{F}_2^m$ with the set of maximal elements $\mathcal {F}$. Then

where $\cap S$ denotes the intersection of all elements in $S$. In particular, we also have $|\Delta| = \sum_{\emptyset\neq S\subseteq \mathcal{F}}(-1)^{|S|+1}2^{|\cap S|}$.

Example 2.2. Let $\Delta$ be a simplicial complex of $\mathbb{F}_2^4$ with the set of maximal elements $\mathcal {F} = \{(1, 1, 0, 0), (1, 0, 1, 1)\}$. Then

Example 2.3. Let $\Delta$ be a simplicial complex of $\mathbb{F}_2^4$ with the set of maximal elements $\mathcal {F} = \{(1, 1, 0, 0), (0, 0, 1, 1)\}$. Then

2.2.   The structure of $\Bbb F_4$

In the paper ^[12], the authors first constructed linear codes over the finite ring $\Bbb F_2+u\Bbb F_2$ with $u^2 = 0$ and obtained many optimal binary linear codes by Gray map. After that, Wu et al. ^[11] also considered the case of $\Bbb F_p+u\Bbb F_p$ with $u^2 = 0$ and $p$ is an odd prime number. Let $\mathbb Z_4$ be the ring of integers modulo $4$. For each $u \in \mathbb Z_4$ there is a unique representation $u = a + 2b$, where $a, b \in \Bbb F_2$. Here the element $2$ in $\mathbb Z_4$ plays a similar role, which like $u$ for the ring $\Bbb F_2+u\Bbb F_2$, and the only difference is the characteristics of the two rings.

For the finite field $\Bbb F_4$, as we known $\Bbb F_4\cong \Bbb F_2[x]/\langle x^2+x+1\rangle$, where $x^2+x+1$ is the only irreducible polynomial of degree two in $\Bbb F_2[x]$. Let $w$ be an element in some extend field of $\Bbb F_2$ such that $w^2+w+1 = 0$. Then we have $\Bbb F_4 = \Bbb F_2(w)$ and for each $u \in \mathbb F_4$ there is a unique representation $u = a + wb$, where $a, b \in \Bbb F_2$. Let $m$ be a positive integer, and $\mathbb F_4^m$ be the set of $m$-tuples over $\mathbb F_4$. Any vector $\mathbf x \in \mathbb F_4^m$ can be written as $\mathbf x = \mathbf a + w\mathbf b$, where $\mathbf a, \mathbf b\in\mathbb F_2^m$.

3.   Weight distributions of quaternary codes

In this section, we will construct some quaternary codes via simplicial complexes and determine the weight distributions of these codes.

There is a bijection between $\mathbb{F}_2^m$ and $2^{[m]}$ being the power set of $[m] = \{1, \ldots, m\}$, defined by ${\mathbf v}\mapsto$ supp$({\mathbf v})$. Throughout this paper, we will identify a vector in $\mathbb{F}_2^m$ with its support.

Let $A, B$ be two subsets of $[m]$ and $D = \Delta_A^c+w\Delta_B = \Bbb F_2^m\backslash \Delta_A+w\Delta_B\subset \Bbb F_4^m$, where $w$ is an element in some extension field of $\Bbb F_2$ such that $w^2+w+1 = 0$. We define a quaternary code as follows:

First of all, from (3.1), it is easy to check that the code $\mathcal{C}_D$ is a linear quaternary code. The length of the code $\mathcal{C}_{D}$ is $|D|$. If $\mathbf{a} = \mathbf{0}$, then the Hamming weight of the codeword $c_{\mathbf{a}}$ is equal to $\mbox{wt}(c_{\mathbf{a}}) = 0$. Next we assume that $\mathbf{a}\neq \mathbf{0}$. Suppose that $\mathbf{a} = \boldsymbol{\alpha}+w\boldsymbol{\beta}$, $\mathbf{d} = {\mathbf d_1}+w{\mathbf d_2}$, where ${\boldsymbol{\alpha} = (\alpha_1, \cdots, \alpha_m), \boldsymbol{\beta} = (\beta_1, \cdots, \beta_m)}\in \Bbb F_2^m$, ${\mathbf d_1}\in \Delta_A^c$, and ${\mathbf d_2}\in \Delta_B$. Then

By the definition of Hamming weight of vector $\mathbf{x} = \mathbf y+w\mathbf z\in \Bbb F_4^m$ with $\mathbf{y, z}\in \Bbb F_2^m$, $\mbox{wt}(\mathbf x) = 0$ if and only if $\mathbf y = \mathbf z = \mathbf0$. Hence

Theorem 3.1. Let $A, B$ be two subsets of $[m]$ and $D = \Delta_A^c+w\Delta_B\subset \Bbb F_4^m$. Then $\mathcal{C}_D$ in (3.1) is a $[(2^m-2^{|A|})2^{|B|}, m]$ quaternary code and its weight distribution is presented in Table 1.

Proof. It is easy to check that the length of the code $\mathcal{C}_D$ is $|D| = (2^m-2^{|A|})2^{|B|}$. To compute the weight and frequency of a codeword, we need to introduce the following notation.

For $X$ a subset of $\mathbb{F}_2^m$, we use $\chi(\mathbf {u}|X)$ to denote a Boolean function in $m$-variable, and $\chi(\mathbf {u}|X) = 1$ if and only if $\mathbf {u}\bigcap X = \emptyset$. For a vector $\mathbf {u} = (u_1, \ldots, u_m)\in \Bbb F_2^m$ and a nonempty simplicial complex $\Delta_A$, by Lemma 2.1 we have

By (3.3) and (3.4)

where $\delta$ is the Kronecker delta function.

Next we need to consider the following cases:

Case 1. $\boldsymbol{\alpha} = \mathbf 0$ and $\boldsymbol{\beta}\neq \mathbf 0$. Then

(1) Note that $\chi(\boldsymbol{\beta}|B) = 0$ and $\chi(\boldsymbol{\beta}|A) = 0$ if and only if $\boldsymbol{\beta}\cap (A\cap B)\neq \emptyset$. The number of such $\boldsymbol{\beta}$ is $2^{m-|A\cap B|}(2^{|A\cap B|}-1) = 2^m-2^{m-|A\cap B|}.$

(2) Note that $\chi(\boldsymbol{\beta}|B) = 1$ and $\chi(\boldsymbol{\beta}|A) = 1$ if and only if $\boldsymbol{\beta}\cap (A\cup B) = \emptyset$. The number of such $\boldsymbol{\beta}$ is $2^{m-|A\cup B|}-1.$

(3) Note that $\chi(\boldsymbol{\beta}|B) = 1$ and $\chi(\boldsymbol{\beta}|A) = 0$ if and only if $\boldsymbol{\beta}\cap B = \emptyset$ and $\boldsymbol{\beta}\cap A\neq \emptyset$. The number of such $\boldsymbol{\beta}$ is $(2^{m-| B|}-1)-(2^{m-|A\cup B|}-1) = 2^{m-| B|}-2^{m-|A\cup B|}.$

(4) The number of $\boldsymbol{\beta}$ such that $\chi(\boldsymbol{\beta}|B) = 0$ and $\chi(\boldsymbol{\beta}|A) = 1$ is $2^m-1-(2^m-2^{m-|A\cap B|})-(2^{m-|A\cup B|}-1)-(2^{m-| B|}-2^{m-|A\cup B|}) = 2^{m-|A\cap B|}-2^{m-| B|}.$

Case 2. $\boldsymbol{\alpha}\neq \mathbf 0$ and $\boldsymbol{\beta} = \mathbf 0$. Then

Similar to Case 1, the numbers of such $\boldsymbol{\alpha}$ can be determined.

Case 3. $\boldsymbol{\alpha = }\boldsymbol{\beta}\neq \mathbf 0$. Then

Similar to Case 1, the numbers of such $\boldsymbol{\alpha}$ can be determined.

Case 4. $\boldsymbol{\alpha}\neq 0, \boldsymbol{\beta}\neq 0,$ and $\boldsymbol{\alpha}\neq \boldsymbol{\beta}$. Then

Let $T = \chi(\boldsymbol{\alpha}|A)\chi(\boldsymbol{\alpha}|B)+\chi(\boldsymbol{\beta}|A)\chi(\boldsymbol{\alpha+\beta}|B)+\chi(\boldsymbol{\alpha+\beta}|A)\chi(\boldsymbol{\alpha}|B)$. We divide the proof into the following subcases:

(1) $T = 3$. In this case we have $\mbox{wt}(c_{\mathbf{a}}) = \frac34(2^m-2^{|A|})2^{|B|}+\frac342^{|A|+|B|}$ and

which is equivalent to

The number of such $(\boldsymbol{\alpha}, \boldsymbol{\beta})$ is $(2^{m-|A\cup B|}-1)(2^{m-|A\cup B|}-2).$

(2) $T = 2$. Suppose that $\chi(\boldsymbol{\alpha}|A)\chi(\boldsymbol{\alpha}|B) = 0$. We have

Hence $\boldsymbol{\alpha}\cap A\neq \emptyset$. Note that the support of the vector $\boldsymbol{\alpha+\beta}$ is equal to $(\mbox{supp}(\boldsymbol{\alpha}) \cup \mbox{supp}(\boldsymbol{\beta}))\backslash (\mbox{supp}(\boldsymbol{\alpha}) \cap \mbox{supp}(\boldsymbol{\beta}))$. From $\boldsymbol{\alpha}\cap A\neq \emptyset$ and $\boldsymbol{\beta}\cap A = \emptyset$, we have $(\boldsymbol{\alpha+\beta})\cap A\neq \emptyset$, which is a contradiction with $(\boldsymbol{\alpha+\beta})\cap A = \emptyset.$ Similarly, we have that there is no $(\boldsymbol{\alpha}, \boldsymbol{\beta})$ such that $T = 2$.

(3) $T = 1$. In this case we have $\mbox{wt}(c_{\mathbf{a}}) = \frac34(2^m-2^{|A|})2^{|B|}+\frac142^{|A|+|B|}$. Because $\boldsymbol{\alpha}, \boldsymbol{\beta}, \boldsymbol{\alpha+\beta}$ have the same status, without loss of generality, we suppose that $\chi(\boldsymbol{\beta}|A)\chi(\boldsymbol{\beta}|B) = 1$. Then we have

The number of such $(\boldsymbol{\alpha}, \boldsymbol{\beta})$ is $(2^{m-|A|}-1)(2^{m-| B|}-2)-(2^{m-|A\cup B|}-1)(2^{m-|A\cup B|}-2).$

(4) $T = 0$. In this case we have $\mbox{wt}(c_{\mathbf{a}}) = \frac34(2^m-2^{|A|})2^{|B|}$. The number of such $(\boldsymbol{\alpha}, \boldsymbol{\beta})$ is $(2^m-1)(2^m-2)-(2^{m-|A\cup B|}-1)(2^{m-|A\cup B|}-2)-(2^{m-|A|}-1)(2^{m-| B|}-2)+(2^{m-|A\cup B|}-1)(2^{m-|A\cup B|}-2) = (2^m-1)(2^m-2)-(2^{m-|A|}-1)(2^{m-| B|}-2).$

This completes the proof.

Corollary 3.2. Let $B$ be a subset of $[m]$ and $D = \Bbb F_2^m+w\Delta_B\subset \Bbb F_4^m$. Then $\mathcal{C}_D$ is a $[2^{m+|B|}, m, 2^{m+|B|-1}]$ two-weight quaternary code and its weight distribution is presented in Table 2.

Corollary 3.3. Let $A$ be a subset of $[m]$ and $D = \Delta_A^c+w\Bbb F_2^m\subset \Bbb F_4^m$. Then $\mathcal{C}_D$ is a $[2^m(2^m-2^{|A|}), m, 3\times2^{2m-2}-3\times2^{|A|+m-2}]$ two-weight quaternary code and its weight distribution is presented in Table 3.

We give the following examples to illustrate our main results.

Example 3.4. Let $m = 4$, $|B| = 2$, and $D = \Bbb F_2^m+w\Delta_B\subset \Bbb F_4^m$. By Corollary 3.3, $\mathcal{C}_D$ is a [64,4,32] quaternary code and its weight distribution is given by $1+9z^{32}+246z^{48}$.

Example 3.5. Let $m = 4$, $|A| = 3$, and $D = \Delta_A^c+w\Bbb F_2^m\subset \Bbb F_4^m$. By Corollary 3.3 and database in ^[4], $\mathcal{C}_D$ is a [128,4,96] quaternary optimal code and its weight distribution is given by $1+252z^{96}+3z^{128}$.

Proposition 3.6. The code in Corollary 3.3 is a Griesmer code.

Proof. By Corollary 3.3, the parameters of the code are

By the Griesmer bound, we have

where $X = 3$ and $Y = 0$ if $m+|A|-2$ is even; and $X = 6$ and $Y = 1$ if $m+|A|-2$ is odd. Then

This completes the proof.

For two vectors ${\mathbf u, v}\in \Bbb F_q^m$, we say that ${\mathbf u}$ covers ${\mathbf v}$ if $\mathrm{supp}({\mathbf v})\subseteq\mathrm{supp}({\mathbf u})$. A nonzero codeword ${\mathbf u}$ in a linear code $\mathcal{C}$ is said to be minimal if ${\mathbf u}$ covers the zero vector and the ${\mathbf u}$ itself but no other codewords in the code $\mathcal{C}$. A linear code $\mathcal{C}$ is said to be minimal if every nonzero codeword in the code $\mathcal{C}$ is minimal.

The following lemma developed by Aschikhmin and Barg ^[1] is a useful criterion for a linear code to be minimal.

Lemma 3.7. A linear code $\mathcal{C}$ over $\Bbb F_q$ with minimum distance $w_{\min}$ is minimal provided that $w_{\min}/{w_{\max}} > {(q-1)}/q$, where $w_{\max}$ denotes the maximum nonzero Hamming weight in the code $\mathcal{C}$.

Corollary 3.8. Let $A$ be a proper subset of $[m]$ and $D = \Delta_A^c+w\Bbb F_2^m\subset \Bbb F_4^m$ in Corollary 3.3. Then the code $\mathcal C_D$ is minimal.

Proof. The result follows from Lemma 3.7 and

Acknowledgments

This work was supported by National Natural Science Foundation of China (12071138, 61772015 and 11961050) and the Guangxi Natural Science Foundation (2020GXNSFAA159053).

Conflict of interest

Authors declare no conflict of interest in this paper.