Spreading speed revisited: Analysis of a free boundary model

1.   Introduction

Throughout this paper, we let $ q = 2^m $ for a positive integer $ m $. An $ [n, \kappa, d] $ linear code $ \mathcal{C} $ over the finite field $ \mathbb{F}_2 $ is a $ \kappa $-dimensional subspace of $ \mathbb{F}_2^n $ with minimum distance $ d $. A linear code $ \mathcal{C} $ is called projective if its dual code has minimum distance at least $ 3 $. For a codeword $ \mathit{c} \in \mathcal{C} $ the Hamming weight $ wt(\mathit{c}) $ is the number of nonzero coordinates in $ \mathit{c} $. Let $ A_i $ be the number of codewords with weight $ i $ in $ \mathcal{C} $ of length $ n $. The sequence $ (1, A_1, \ldots, A_n) $ is referred as the weight distribution of $ \mathcal{C} $. If the number of nonzero $ A_i $ in the sequence $ (A_1, \ldots, A_n) $ is equal to $ t $, we call $ \mathcal{C} $ a $ t $-weight code.

The weight distribution contains important information of a code. In classic coding theory, it gives the minimum distance of the code which determines the error correction capability of the code. In addition, the weight distribution allows the computation of the error probability of error detection and error correction with respect to some algorithms ^[2,16,31]. Thus, it is desirable to determine the weight distributions of linear codes. Moreover, linear codes with a few nonzero weights have many applications in constant composition codes ^[10], authentication codes ^[11] and secret sharing schemes ^[38] and some other fields. So it has provoked tremendous interests in determining the weight distributions of linear codes in literature. Different kinds of linear codes over finite fields and rings have been investigated explicitly for the past two decades, see ^{[5,9,13,15,17,18,19,24,27,29,30,34,35,39]}. In particular, Ding et al. ^[13] studied the weight distributions of a class of binary linear codes. Heng et al. dealt with projective binary linear codes from special Boolean functions in their recent work ^[18]. Huang et al. ^[19] constructed primitive binary LCD BCH codes and determined their parameters.

Let $ q = p^m $ for a prime $ p $. Choose a subset $ D = \{d_1, d_2, \ldots, d_n\} $ of $ \mathbb{F}_{q}^* $, where $ \mathbb{F}_{q}^* $ is the multiplicative group of $ \mathbb{F}_{q} $. Denote by $ \operatorname{Tr} $ the absolute trace function from $ \mathbb{F}_{q} $ to $ \mathbb{F}_p $. A linear code of length $ n $ is defined by

The set $ D $ is called the defining set. Ding ^[12] pointed out that the defining-set construction is a fundamental approach and is equivalent to the generator matrix construction of all linear codes. Therefore it has attracted extensive attention and many families of linear codes were proposed following this way ^{[1,13,14,21,22,23,33,36,37]}, most of which have good parameters. Particularly, Wu et al. ^[33] investigated three-weight binary linear codes from generalized Moisio's exponential sums. We refer the reader to ^[25,28] and the references therein for an overall survey on recent results and problems on constructions of linear codes from cryptographic functions.

In the rest of the paper, we always take $ p = 2 $ unless otherwise stated. In ^[13], a class of three-weight binary code $ \mathcal{C}_{D} $ of (1.1) is constructed using the defining set

where $ q = 2^m $ and $ 1 \leqslant h < m/2 $.

Let $ \alpha, \beta\in \mathbb{F}_q^* $, and $ u $ a positive integer less than $ m $. We consider a special case of the defining-set construction by defining a class of linear codes

where $ \mathit{c}(a, b) = (\operatorname{Tr}(ax+by))_{(x, y)\in D} $ and

The set $ D $ is also called the defining set of $ \mathcal{C}_{D} $. Clearly, this is an extension of the work in ^[13].

The purpose of this paper is to study the weight distributions of $ \mathcal{C}_{D} $ by employing Weil sums. These linear codes are projective with at most three nonzero weights and can be utilized to construct secret sharing schemes with good access structures.

Now we present the main results of this paper and their proofs are given in Section 3. Let $ v = \gcd(m, u) $ stand for the greatest common divisor of $ m $ and $ u $. Let $ g $ be a generator of the cyclic group $ \mathbb{F}_q^* $. Namely, $ \mathbb{F}_q^* = \langle g \rangle $. The weight distributions of $ \mathcal{C} _D $ are given in the following four theorems.

Theorem 1.1. Let $ \mathcal{C} _D $ be defined by $(1.2)$ and $(1.3)$. If $ m/v $ is odd, then $ \mathcal{C} _D $ is a $ [2^{2m-1}-1, 2m, 2^{2m-2}-2^{m+v-2}] $ three-weight binary code with the weight distribution in Table 1.

Theorem 1.2. Suppose that $ m/v $ is even and $ \alpha, \beta \notin \langle g^{ 2^v+1 }\rangle $. Then $ \mathcal{C}_D $ is a $ [2^{2m-1}+2^{m-1}-1, 2m, 2^{2m-2}] $ two-weight binary code with the weight distribution in Table 2.

Theorem 1.3. Let $ m/v $ be even and $ \alpha, \beta \in \langle g^{ 2^v+1 }\rangle $. If $ u\neq m/2 $, then $ \mathcal{C} _D $ is a $ [2^{2m-1}+2^{m+2v-1}-1, 2m, 2^{2m-2}] $ three-weight binary code with the weight distribution in Table 3. If $ u = m/2 $, then $ \mathcal{C} _D $ is a simplex code with parameters $ [2^{2m }-1, 2m, 2^{2m-1}] $ and the only nonzero weight $ 2^{2m-1} $. Moreover, the simplex code meets the Griesmer bound.

Theorem 1.4. Suppose that $ m/v $ is even and only one of $ \alpha $ and $ \beta $ is in $ \langle g^{ 2^v+1 }\rangle $, then $ \mathcal{C} _D $ is a $ [2^{2m-1}-2^{m+v-1}-1, 2m, 2^{2m-2}-2^{m+v-1}] $ three-weight binary code with the weight distribution in Table 4.

Some examples are provided to illustrate our main results. All of the numerical results are verified by Magma programs.

Example 1. Let $ (m, u) = (3, 1) $. By Theorem 1.1, the binary code $ \mathcal{C}_D $ has parameters [31, 6, 12]. Its weight enumerator is $ 1+10 z^{12} + 47 z^{16} +6 z^{20} $.

Example 2. Let $ (m, u) = (2, 1) $ and $ \mathbb{F}_4^* = \langle g \rangle $. If we take $ \alpha = g^2 $ and $ \beta = g $, from Theorem 1.2 the binary code $ \mathcal{C}_D $ has parameters [9,4,4]. Its weight enumerator is $ 1+ 9 z^{4} +6 z^{6} $. It is optimal according to Markus Grassl's code tables available at http://www.codetables.de/.

Example 3. Let $ (m, u) = (4, 2) $. Write $ \mathbb{F}_{16}^* = \langle g \rangle $ and $ \alpha = \beta = g^5 $. By Theorem 1.3, the code $ \mathcal{C} _D $ has parameters [255,8,128] and it is an optimal simplex code with the only nonzero weight $ 128 $.

Example 4. Let $ (m, u) = (4, 1) $, $ \mathbb{F}_{16}^* = \langle g \rangle $, $ \alpha = g^3 $ and $ \beta = g $. By Theorem 1.4, the code $ \mathcal{C} _D $ has parameters [111,8,48]. Its weight enumerator is $ 1+ 36 z ^{48} + 192 z^{56} + 27 z ^{64} $.

2.   Preliminaries

In this section, we present some results on group characters and Weil sums. Let $ G $ be a finite abelian group (written multiplicatively). A character $ \chi $ of $ G $ is a homomorphism from $ G $ into the multiplicative group $ U $ of complex numbers of absolute value $ 1 $. That is, $ \chi $ is a mapping from $ G $ into $ U $ with $ \chi(xy) = \chi(x)\chi(y) $ for all $ x, y \in G $. Let $ q = 2^m $. For each $ b\in\mathbb{F}_q $, the function

defines an additive character of $ \mathbb{F}_q $, where $ \text{Tr} $ is the absolute trace function from $ \mathbb{F}_q $ to $ \mathbb{F}_2 $. The additive character $ \chi_0 $ is called trivial, whereas other characters $ \chi_b $ with $ b \in \mathbb{F}_q^* $ are called nontrivial. Especially $ \chi_1 $ is called the canonical additive character and is denoted by $ \chi $ for simplicity. See ^[26] for more information about characters over finite fields.

In ^[7], Coulter determined the value of Weil sums $ S_u(\alpha, \beta) $ defined by

for all $ \alpha, \beta \in \mathbb{F}_q $, where $ q = 2^m $ and $ u $ is a positive integer. Recall that $ v = \gcd(m, u) $ is the greatest common divisor of $ m $ and $ u $.

Lemma 2.1 (Theorem 4.1, ^[7]). If $ m/v $ is odd, then

Lemma 2.2 (Theorem 4.2, ^[7]). Let $ \beta \in \mathbb{F}_q^* $ and suppose $ m/v $ is odd. Then $ S_u(\alpha, \beta) = S_u(1, \beta \gamma^{-1}) $, where $ \gamma \in \mathbb{F}_q^* $ is the unique element satisfying $ \gamma^{2^u+1} = \alpha $. Further, we have

where and hereafter $ \operatorname{Tr}_v $ is the trace function from $ \mathbb{F}_q $ to $ \mathbb{F}_{2^v} $.

Lemma 2.3 (Theorem 5.2, ^[7]). Let $ m/v $ be even so that $ m = 2k $ for some integer $ k $. Then

where $ g $ is a generator of $ \mathbb{F}_q^* $.

When $ m/v $ is even, the evaluation of $ S_u(\alpha, \beta) $ for $ p = 2 $, where $ \beta \neq 0 $, was due to Coulter ^[7], and it can be similarly proved as the case of an odd prime $ p $, see the poofs of Theorems 1 and 2 in ^[6].

Lemma 2.4 (Theorem 5.3, ^[7]). Let $ \beta \in \mathbb{F}_q^* $ and suppose $ m/v $ is even such that $ m = 2k $ for some integer $ k $. Let $ f_\alpha (x) = \alpha^{2^u} x^{2^{2u}} + \alpha x \in \mathbb{F}_q[x] $. There are two cases.

$ (i) $ If $ \alpha \neq g^{t(2^v+1)} $ for any integer $ t $ then $ f_\alpha $ is a permutation polynomial. Let $ x_0 \in \mathbb{F}_q $ be the unique element satisfying $ f_\alpha(x_0) = \beta^{2^u} $. Then

$ (ii) $ If $ \alpha = g^{t(2^v+1)} $ for some integer $ t $ then $ S_u(\alpha, \beta) = 0 $ unless the equation $ f_\alpha(x) = \beta^{2^u} $ is solvable. If the equation is solvable, with solution $ x_0 $ say, then

3.   The proofs of the main results

In this section, we always fix $ \alpha, \beta \in \mathbb{F}_{q}^* $ and let $ g $ be a generator of $ \mathbb{F}_q^* $.

3.1.   Auxiliary results

The code length is defined by

Lemma 3.1. The code length $ n $ of $(3.1)$ is given as follows.

$ (i) $ If $ m/v $ is odd, then $ n = 2^{2m-1}-1 $.

$ (ii) $ If $ m/v $ is even, then

Proof. It follows from the orthogonal property of additive characters that

Thus we obtain the desired conclusions from Lemmas 2.1 and 2.3.

The Pless power moments are useful tools when we calculate the weight distribution of a given code. Recall that the code $ \mathcal{C}_{D} $ is defined by (1.2) and (1.3) with length $ n $ and dimension $ \kappa = \dim_{\mathbb{F}_2}(\mathcal{C}_{D}) $. The weight distributions of $ \mathcal{C}_{D} $ and its dual $ \mathcal{C}_{D}^{\bot} $ are denoted by $ (1, A_1, \ldots, A_n) $ and $ (1, A_1^{\bot}, \ldots, A_n^{\bot}) $, respectively. As we will prove later in Theorem 4.1, the minimum weight of the dual code $ \mathcal{C}^\bot_D $ is at least $ 3 $. So $ A_1^{\bot} = 0 $, $ A_2^{\bot} = 0 $ and consequently the first three Pless power moments are given by [20Y, p.260]:

3.2.   The proofs of Theorems 1.1, 1.2, 1.3 and 1.4

In this subsection, we will prove the weight distributions of $ \mathcal{C}_D $ given in Theorems 1.1, 1.2, 1.3 and 1.4. The code length $ n $ is given in Lemma 3.1. Assume that $ (a, b)\neq (0, 0) $ unless otherwise stated. We define

Then the Hamming weight of $ \mathit{c}(a, b) $ is expressed as

By (3.2) and the orthogonal property of additive characters,

Now we are going to determine the values of $ N_0(a, b) $ given by (3.4). There are four cases to consider according to the parity of $ m/v $ and the values of $ \alpha $ and $ \beta $.

In the first case, if $ m/v $ is odd, the length is $ n = 2^{2m-1}-1 $. At first glance, when $ a = 0 $ and $ b\neq 0 $, we have $ S_u(\alpha, 0) = 0 $ by Lemma 2.1. So $ N_0(a, b) = 2^{2m-2} $. Similarly when $ a\neq 0 $ and $ b = 0 $, $ N_0(a, b) = 2^{2m-2} $. Assume that $ a \in \mathbb{F}_q^* $, we have from Lemma 2.2 that

where $ \gamma \in \mathbb{F}_q^* $ is the unique element satisfying $ \gamma^{2^u+1} = \alpha $. Thus it follows from (3.4), Lemmas 2.1 and 2.2 that

Hence, by (3.3), the weight $ wt(\mathit{c}(a, b)) $ of the codeword $ \mathit{c}(a, b) $ satisfies

Put

We now determine the number $ A_{w_i} $ of codewords with weight $ w_i $ in $ \mathcal{C}_D $. The first three Pless power moments yield the following system of equations:

where $ n = 2^{2m-1}-1 $. Solving the system of equations in (3.5) leads to the weight distribution given in Table 1. This proves Theorem 1.1.

In the second case, if $ m/v $ is even and $ \alpha, \beta \notin \langle g^{ 2^v+1 }\rangle $, the length is $ n = 2^{2m-1}+2^{m-1}-1 $. It follows from Lemmas 2.3 and 2.4 that

where $ a\neq 0 $ and $ x_0 $ satisfies $ f_\alpha(x_0) = a^{2^u} $. By (3.4),

From (3.3), the weight $ wt(\mathit{c}(a, b)) $ belongs to the set

Let

Again by solving the system of equations

where $ n = 2^{2m-1}+2^{m-1}-1 $, we get the weight distribution given in Table 2. This finishes the proof of Theorem 1.2.

In the third case, if $ m/v $ is even and $ \alpha, \beta \in \langle g^{ 2^v+1 }\rangle $, the length is $ n = 2^{2m-1}+2^{m+2v-1}-1 $. Again from Lemma 2.3, we have

Let $ a \neq 0 $.

It follows from Lemma 2.4 that $ S_u(\alpha, a) = 0 $ or if the equation $ f_{\alpha}(x) = a^{2^u} $ is solvable with a solution $ x_0 \in \mathbb{F}_q $, then

By (3.3) and (3.4), the weight $ wt(\mathit{c}(a, b)) $ belongs to the set

Write

The first three Pless power moments are given by (3.5), where $ n = 2^{2m-1}+ 2^{m+2v-1} -1 $. Solving these equations yields the weight distribution given in Table 3. This completes the proof of Theorem 1.3.

The last case is that $ m/v $ is even and $ \alpha \in \langle g^{ 2^v+1 }\rangle $, $ \beta \notin \langle g^{ 2^v+1 }\rangle $ (or $ \beta\in \langle g^{ 2^v+1 }\rangle $, $ \alpha \notin \langle g^{ 2^v+1 }\rangle $). In this case, $ n = 2^{2m-1}- 2^{m+ v-1} -1 $. After a similar argument as we have done in the previous case, we obtain from (3.3) and (3.4) that $ wt(\mathit{c}(a, b)) $ belongs to the set

Set

From the first three Pless power moments (3.5), we get the weight distribution given in Table 4, completing the proof of Theorem 1.4.

4.   The dual of the code $ \mathcal{C}_D $

For the dual $ \mathcal{C}^{\bot}_{D} $ of the code $ \mathcal{C}_{D} $, we have the following conclusion.

Theorem 4.1. Let $ m \geqslant 2 $ and $ \alpha, \beta\in \mathbb{F}_q^* $. The dual $ \mathcal{C}^{\bot}_D $ of the code $ \mathcal{C}_D $ is a binary code with parameters $ [n, n-2m, d^\bot] $, where $ n $ is given in Lemma 3.1 and $ d^\bot = 3 $ if $ m $ is even and $ 3 \leqslant d^\bot \leqslant 4 $ if $ m $ is odd.

Proof. The dimension of the code $ \mathcal{C}^{\bot}_D $ is obvious. Since $ D $ does not contain the zero element of $ \mathbb{F}_q^2 $, the minimum distance of $ \mathcal{C}^{\bot}_D $ cannot be one. Similarly, since $ D $ is not a multiset, any two elements $ d_i $ and $ d_j $ of $ D $ must be distinct if $ i \neq j $. Hence, the minimum distance $ \mathcal{C}^{\bot}_D $ cannot be $ 2 $. So we have $ d^\bot \geqslant 3 $.

When $ m $ is even, we assume that $ (x_1, 0), \, (0, y_2) \in D $. We claim that $ (x_1, y_2) $ is in $ D $. Actually,

Therefore, the minimum distance of $ \mathcal{C}^{\bot}_D $ is $ 3 $.

When $ m $ is odd, $ n = 2^{2m-1}-1 $ by Theorem 1.1. Let $ D = \{d_i = (d_{1i}, d_{2i}):i = 1, 2, \ldots, n\} $. Consider the sums $ d_i+d_j $ for $ i\neq j $. The total number of such sums is equal to $ (2^{2m-1}-1)(2^{2m-2}-1) > 2^{2m} $ for $ m \geqslant 2 $. Hence, there must be four distinct integers $ i, j, k, l \in \{1, 2, \ldots, n\} $ such that $ d_i + d_j = d_k + d_l $. This means that $ \mathcal{C}^{\bot}_D $ has a codeword with Hamming weight $ 4 $. So we have $ 3 \leqslant d^\bot \leqslant 4 $, completing the whole proof.

When $ m $ is odd, the code $ \mathcal{C}^{\bot}_D $ is at least almost optimal. This is because the minimum weight of any binary code with length $ 2^{2m-1} - 1 $ and dimension $ 2^{2m-1} - 1 - 2m $ is at most 4 according to the sphere packing bound.

Example 5. Let $ (m, u) = (2, 1) $, $ \alpha = g^2 $ and $ \beta = g $, where $ \mathbb{F}_4^* = \langle g \rangle $. Magma programs show that the binary code $ \mathcal{C}^{\bot}_D $ has parameters [9,5,3] and it is optimal. If we take $ \alpha = \beta = g^3 $, then $ \mathcal{C}^{\bot}_D $ has parameters $ [15,11,3] and it is optimal, too.

Example 6. Let $ (m, u) = (3, 1) $. Then the binary code $ \mathcal{C}^{\bot}_D $ has parameters [31,25,3] and it is almost optimal, while the optimal binary code has parameters [31,25,4].

5.   Conclusions

In this paper, a class of projective binary codes with two or three weights were constructed from a proper defining set. Their weight distributions were determined by applying Weil sums and the first three Pless power moments. Furthermore, we determined the parameters of their dual codes. Some optimal and almost optimal codes were also constructed. Due to ^[38], a linear code over $ \mathbb{F}_2 $ is suitable to construct secret sharing schemes with interesting access structures if

where $ w_{\min} $ and $ w_{\max} $ denote the minimum and maximum nonzero weights of the code, respectively. For the linear codes $ \mathcal{C}_{D} $ in Theorems 1.1-1.4, the inequality (5.1) always holds if $ m \geqslant 2v+2 $. So they can be used in secret sharing schemes with good access structures. Additionally, projective two-weight codes in Theorem 1.2 can be applied in strongly regular graphs ^[4,8] and projective three-weight codes in Theorems 1.1, 1.3 and 1.4 are related to association schemes with three classes ^[3].

Acknowledgment

The authors would like to thank the referee for his/her thorough review with constructive suggestions and valuable comments. The work is partly supported by the National Natural Science Foundation of China under Grant 12071247, Grant 11701317, Grant U1811461 and Grant 11971496.

Conflict of interest

The authors declare that there is no conflict of interests regarding the publication of this paper.