Some new numerical schemes for finding the solutions to nonlinear equations

1.   Introduction

Recently, several infinite families of minimal and optimal linear codes are constructed via mathematical objects named simplicial complexes or down-sets by Hyun and Wu et al ^{[3,5,7,8,12,13]}. Simplicial complexes are extremely well-behaved with the $n$-variable generating function, which in turn enable us to compute the exponential sum rather efficiently. Let $n$ be a natural number and denote by $[n] = \{1, 2, \ldots, n\}$ the set of integers from $1$ to $n$. For $\Delta \subseteq \mathbb{P}([n])$, we say $\Delta$ is a simplicial complex if $u\in \Delta$ and $v\subseteq u$ imply $v\in \Delta$, where $\mathbb{P}([n])$ denotes the power set of $[n]$. The set-inclusion defines a partial order on $\Delta$. A maximal element of a simplicial complex $\Delta$ is an element of $\Delta$ that is not smaller than any other element in $\Delta$. For subsets $A_{i}$ of $[n]$, where $i\in [S]$, the notation $\langle A_{1}, A_{2}, \dots, A_{s} \rangle$ means it is a simplicial complex generated by $\{A_{1}, A_{2}, \ldots, A_{s}\}$, that is $\langle A_{1}, A_{2}, \ldots, A_{s}\rangle = \{ B : B \subseteq A_{i}, i\in [S]\}$. Especially, when $s = 1$, we write $\langle A_{1}\rangle$ simply as $\Delta_{A_{1}}$.

Ternary codes of small dimension have been investigated in many literatures, see for instance ^{[2,6,9,10,11]}. A class of group character ternary codes $C_{3}(1, n-1)$ with parameters $[2^{n-1}, n, 2^{n-2}]$, which are the analogue of the binary first-order Reed-Muller codes $\mathrm{RM}(1, n-1)$ are described and analyzed by Ding et al. ^[4]. In this paper, we describe a new class of $[2^{n-1}, n, 2^{n-2}]$ ternary codes, and determine their weigt distributions.

Minimal linear codes, though existing as special linear codes, have important applications in secret sharing and secure two-party computation. Construction of minimal linear codes with new and desirable parameters would be an interesting topic in coding theory and cryptography. We construct in this paper a family of minimal linear codes over $\mathbb{F}_{3}$, and compute their weight distributions. By a distance-optimal code, or simply an optimal code, we mean it has the highest minimum distance with a prescribed length and dimension. One class of these minimal codes we obtained is proved to be optimal.

2.   Linear Codes and $n$-variable generating functions

In this paper we study a linear code with more flexible lengths as follows. Let $P$ be a subset of $\mathbb{F}_{3}^{n}$, and we order the elements of $P$ to fix a coordinate position of vectors. A ternary code $C_{P}$ associated with $P$ is defined to be

It is straightforward that $C_{P}$ is a linear code of length $|P|$ and its dimension is at most $n$.

For a subset $P$ of $\mathbb{F}_{3}^{n}$ and $u\in \mathbb{F}_{3}^{n}$, we define the exponential sum with respect to $P$ by

where $\zeta$ is a primitive 3-rd root of the unity. Then the Hamming weight of a codeword $c_{P}(u)$ in $C_{P}$ is given as follows:

where $\delta$ is the Kronecker delta function and ${\mathrm{Re}}(\chi_{u}(P))$ is the real part of $\chi_{u}(P)$. The main difficulty of the computation of $w(c_{P}(u))$ lies in the fact that it is expressed as the exponential sum with respect to a subset $P$ which in turn is hard to compute for an arbitrary $P$.

When $P$ contains the zero-vector of $\mathbb{F}_{3}^{n}$, we are also interested in $C_{P^{c}}$ where $P^{c}$ denotes the complement of $P$, that is

Then the weight of $c_{P^{c}}(u)$ and that of $c_{P}(u)$ are related as follows:

For the purpose of computing the exponential sum $\chi_{u}(P)$, we introduce the following $n$-variable generating function associated with $P$ inspired by Adamaszek ^[1]:

where we denote $v = (v_{1}, v_{2}, \ldots, v_{n})$ if $v\in \mathbb{F}_{3}^{n}$. By convention, we define $\mathscr{H}_{P}(x_{1}, x_{2}, \ldots, x_{n}) = 0$ if $P = \emptyset$.

Example 1. Let $P = \{(1, -1, -1, \ldots, -1)\}$, then the generating function is

In general, one can easily obtain the following result when $P = (\mathbb{F}_{3}^{*})^{n}$

3.   Another class of $[2^{n-1}, n, 2^{n-2}]$ ternary codes

For the vector space $\mathbb{F}_{3}^{n}$, we consider the subset $(\mathbb{F}_{3}^{*})^{n}$. We give as follows a bijection

where $\psi(u) = \{i : u_{i} = 1\}$. Through the given map $\psi$, a simplicial complex $\Delta$ of $\mathbb{P}([n])$ will be regarded as the simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$, and be identified as a subset of $\mathbb{F}_{3}^{n}$ in this section without any real ambiguity.

Example 2. Let $\Delta$ be the simplicial complex of $(\mathbb{F}_{3}^{*})^{4}$ generated by $\{1, 2\}$ and $\{3, 4\}$. Then

which is identified with

The indicator function $\mathbb{1}_{ \Delta}$ from $\mathbb{F}_{3}^{n}$ to $\mathbb{F}_{2}$ is defined by $\mathbb{1}_{ \Delta}(u) = 1$ only if $u\in \Delta$. The following lemma, which is a simple consequence of the Inclusion-exclusion principle, will be used in deriving an identity involving $\mathscr{H}_{ \Delta}(x_{1}, \ldots, x_{n})$.

Lemma 3.1. Let $\Delta = \langle A_{1}, A_{2}, \ldots, A_{t}\rangle$ be a simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$. Then

Proof. Since $\Delta$ is a simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$, we have $\Delta = \cup_{j = 1}^{t} \Delta_{A_{j}}$. The result follows from the Inclusion–exclusion principle.

Proposition 3.2. Let $\Delta$ be a simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$ with $\mathcal{F}$ the set of maximal elements of $\Delta$. Then we have

where we define $\prod_{i\in \emptyset}(1+x_{i}^{2}) = 1$ by convention.

Proof. Let $\Delta = \langle F_{1}, F_{2}, \ldots, F_{t}\rangle$, where $F_{i}\in \mathcal{F}$. Then we see that, by Lemma 3.1,

Example 3. Let $\Delta$ be a simplicial complex of $(\mathbb{F}_{3}^{*})^{3}$ with the set of maximal element $\mathcal{F} = \{ \{1, 2\}, \{3\}\}$. Proposition 3.2 shows that

Lemma 3.3. Let $\Delta$ be a simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$ with $\mathcal{F}$ the set of maximal elements of $\Delta$. For $u\in \mathbb{F}_{3}^{n}$, we have that

where we define $\prod_{i\in \emptyset}(\zeta^{u_{i}}+\zeta^{-u_{i}}) = \prod_{i \notin [n]} \zeta^{-u_{i}} = 1$ by convention.

Proof. According to Proposition 3.2, we get that

Since $\zeta^{u_{i}}+\zeta^{-u_{i}}$ is a real number for $u_{i}\in \mathbb{F}_{3}$, it follows that

Theorem 3.4. Let $\Delta$ be a simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$ with one maximal element $\{A\}$. If $|A| = n-1$, where $n\geq 2$, there are $\binom{n}{m}2^{m}$ codewords in the code $C_{ \Delta}$ which have the same Hamming weight

for any integer $0 \leq m \leq n$. Moreover, the minimum distance of $C_{ \Delta}$ is $W(2)$, which is$2^{n-2}$.

Proof. If $x\in \mathbb{F}_{3}$, then

and

Since $|A| = n-1$, denote $i_{0}\in [n]\setminus A$. By Lemma 3.3, for a non-zero vector $u = (u_{1}, u_{2}, \ldots, u_{n})$ in $\mathbb{F}_{3}^{n}$,

where $k = \#\{i : u_{i} = 0, i\in A \}$. According to equality (2.1), we obtain the Hamming weight of codeword $c_{ \Delta}(u)$ as follows

Let $m = \#\{i : u_{i}\neq 0, 1\leq i \leq n \}$, then there are $\binom{n}{m}2^{m}$ codewords which have the Hamming weight

The nonzero weights $W(m)$ in (3.1) are pairwise distinct and satisfy

Hence, the minimum distance of $C_{ \Delta}$ is $W(2)$.

Example 4. Let $C_{ \Delta}$ be a linear code defined in Theorem 3.4. If $n = 5$, the weight distribution of the corresponding code is given in Table 1.

Corollary 3.5. Let $\Delta$ be a simplicial complex of $(\mathbb{F}_{3}^{*})^{n}$ with one maximal element $\{A\}$. If $|A| = n-1$, where $n\geq 2$, then $C_{ \Delta}$ is a $[2^{n-1}, n, 2^{n-2}]$-code over $\mathbb{F}_{3}$.

Proof. Since $|A| = n-1$, the length of $C_{ \Delta}$ is $2^{n-1}$. It then remains to prove the dimension is $n$. Let ${\bf{e}}_{i}$ be the vector of $\mathbb{F}_{3}^{n}$ whose $i$-th coordinate is $1$ and other coordinates are all zero, ${\bf{w}}_{i}$ be the vector of $\mathbb{F}_{3}^{n}$ whose $i$-th coordinate is $1$ and other coordinates are all $-1$, where $1\leq i \leq n$. We denote by $A = \{i_{1}, i_{2}, \ldots, i_{n-1}\}$. Since $\Delta$ considered as a subset of $\mathbb{F}_{3}^{n}$ contains ${\bf{w}}_{i_{1}}, {\bf{w}}_{i_{2}}, \ldots, {\bf{w}}_{i_{n-1}}$, the codewords $c_{ \Delta}({\bf{e}}_{i})$ of $C_{ \Delta}$ are all nonzero. To finish the proof, we notice that $c_{ \Delta}({\bf{e}}_{i})$ are linearly independent which generate any codeword of $C_{ \Delta}$.

4.   Minimal ternary codes

For the set $[n]$, we define

to be the set of pairs of disjoint subsets of $[n]$. When $\Delta_{1}$ and $\Delta_{2}$ are two disjoint simplicial complexes of $\mathbb{P}([n])$, we consider the set

Since $\Delta_{1}\cap \Delta_{2} = \emptyset$, we have $\mathscr{C}_{2}(\Delta_{1}, \Delta_{2}) \subseteq \mathscr{C}_{2}([n])$. Considering the vector space $\mathbb{F}_{3}^{n}$, there is a bijection

where $\varphi_{1}(u) = \{i : u_{i} = 1\}$ and $\varphi_{2}(u) = \{ j : u_{j} = -1\}$. The set $\mathscr{C}_{2}(\Delta_{1}, \Delta_{2})$ given by two disjoint simplicial complexes, under the map $\varphi$, will be then identified with the subset of $\mathbb{F}_{3}^{n}$ without any real ambiguity.

Example 5. Let $\Delta_{1}, \Delta_{2}$ be simplicial complexes of $\mathbb{P}$(^[4]) generated by $\{1, 2\}$ and $\{3, 4\}$. Then $\mathscr{C}_{2}(\Delta_{1}, \Delta_{2})$ consists of elements

which are identified with elements of $\mathbb{F}_{3}^{n}$ as follows

Proposition 4.1. Let $\Delta_{1}, \Delta_{2}$ be simplicial complexes of $\mathbb{P}([n])$ with the family of maximal elements $\mathcal{F}_{1}$ and $\mathcal{F}_{2}$ respectively. If $\Delta_{1}\cap \Delta_{2} = \emptyset$, then we have

where we define $\prod_{i\in \emptyset }(1+x_{i}) = \prod_{j\in \emptyset}(1+x_{j}^{-1}) = 1$.

Proof.

where the last equality is derived from [3,Theorem 1].

Example 6. Let $\Delta_{1}, \Delta_{2}$ be simplicial complexes of $\mathbb{P}$(^[3]) with $\mathcal{F}_{1} = \{\{1\}\}$ and $\mathcal{F}_{2} = \{\{2\}\}$. Proposition 4.1 shows that $\mathscr{H}_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})}(x_{1}, \ldots, x_{n}) = (1+x_{1})(1+x_{2}^{-1})$. Let $u = (u_{1}, u_{2}, \ldots, u_{n})$, we have

It then follows from $(2.1)$ that

It follows from $(2.2)$ that for $u\in (\mathbb{F}_{3}^{n})^{*}$,

Theorem 4.2. Let $\Delta_{1} = \langle \{r\}, \{s\}\rangle$ and $\Delta_{2} = \langle\{t\}\rangle$ be simplicial complexes of $\mathbb{P}([n])$, where $1\leq r, s, t\leq n$ are pairwise distinct and $n\geq 3$. Then $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is a $[3^{n}-6, n, 3^{n}-3^{n-1}-5]$-code and its weight distribution is given in Table 2.

Proof. The length of $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is $| \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}| = 3^{n}-6$ and its dimension is $n$ according to the proof of [5,Lemma 3.6-(ⅱ)]. Since $\Delta_{1} = \langle \{r\}, \{s\}\rangle$ and $\Delta_{2} = \langle\{t \}\rangle$, by Proposition 4.1, the generating function is

Set $\mathscr{B}_{i}: = \{ (u_{r}, u_{s}, i) : u_{r}, u_{s}\in \mathbb{F}_{3}\setminus\{-i\}\}$. Let $u = (u_{1}, u_{2}, \ldots, u_{n})$, we have

It then follows from $(2.1)$ that

It follows from $(2.2)$ that for $u\in (\mathbb{F}_{3}^{n})^{*}$,

The frequency of each codeword of $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is computed by counting the vector $u$ on its dimension.

Remark 1. Let $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ be a linear code defined in Theorem $4.2$.

$1).$ Since $n\geq 3$, then

where $d$ and $d_{max}$ are the minimum and maximum weights. Hence, $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is minimal.

$2).$ In [5,Theorem 4.7], for instance, if $p = 3$ and $r = 1$, they obtain a linear code with the same parameters as $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ but with different weight distribution.

Theorem 4.3. Let $\Delta_{1} = \langle \{r, s\}\rangle$ and $\Delta_{2} = \langle\{t\}\rangle$ be simplicial complexes of $\mathbb{P}([n])$, where $1\leq r, s, t\leq n$ are pairwise distinct and $n\geq 3$. Then $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is an optimal $[3^{n}-8, n, 3^{n}-3^{n-1}-6]$-code and its weight distribution is given in Table 3.

Proof. The length of $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is $| \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}| = 3^{n}-8$ and its dimension is $n$ according to the proof of [5,Lemma 3.6-(ⅱ)]. Since $\Delta_{1} = \langle \{r, s\}\rangle$ and $\Delta_{2} = \langle\{t \}\rangle$, by Proposition 4.1, the generating function is

Set $\mathscr{M}_{i} = \{ (u_{r}, u_{s}, i) : u_{r}+u_{s}\neq 0, u_{r}, u_{s} \in \mathbb{F}_{3}\setminus \{i\}\}$. Let $u = (u_{1}, u_{2}, \ldots, u_{n})$, we have

It then follows from $(2.1)$ that

It follows from $(2.2)$ that for $u\in (\mathbb{F}_{3}^{n})^{*}$,

The frequency of each codeword of $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is computed by counting the vector $u$ on its dimension. To check the optimality, we assume that there is a $[3^{n}-8, n, 3^{n}-3^{n-1}-5]$-code. Applying the Griesmer bound, we get that

which is a contradiction, so $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is optimal.

Remark 2. Let $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ be a linear code defined in Theorem $4.3$.

$1).$ Since $n\geq 3$, then

where $d$ and $d_{max}$ are the minimum and maximum weights. Hence, $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ is minimal.

$2).$ The codes produced by our construction and the codes in ^[5] for $p = 3$ have totally different parameters. Meanwhile, with a slight change of $\Delta_{1}$, the codes here and the codes in Theorem 4.2 are different.

5.   Conclusions

The ternary codes $C_{ \Delta}$ described in Theorem 3.4 have the same parameters and weight distributions as the group character codes $C_{3}(1, n-1)$. Thus, the ternary codes $C_{ \Delta}$ may be viewed as the analogue of the group character codes $C_{3}(1, n-1)$. As a result, the codes $C_{ \Delta}$ is good for practical error detection. As pointed in ^[4], the weight distribution of the codes $C_{ \Delta}$ is given by the eigenvalues of the Hamming scheme. It may be interesting to investigate the relationship between these codes and the Hamming scheme.

The ternary codes $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ described in Theorem 4.2 and 4.3 have few weights and are minimal. Thus, the dual codes of $C_{ \mathscr{C}_{2}(\Delta_{1}, \Delta_{2})^{c}}$ may be utilized to construct secret sharing schemes.

Acknowledgments

This work was supported by University Natural Science Research Project of Anhui Province under Grant No. KJ2019A0845, National Natural Science Foundation of China under Grant No.12101174 and Scientific Research Foundation of Hefei University under Grant No.18-19RC57, 18-19RC59.

Conflict of interest

All authors declare no conflicts of interest in this paper.