1 Introduction

A linear code C of length n is defined as a subspace of GF(q)n, where GF(q) is a finite field with q elements, and the code C is called binary when q = 2. The t-wise intersecting codes and their wide applications were first introduced in [13], and then further studied by Cohen et al. [2, 3] and Encheva et al. [5]. The t-wise intersecting codes are a generalization of intersecting ones, which correspond to t = 2 and satisfy that any two non-zero codewords have intersecting supports. Finding the judgment criteria and a constructing method for t-wise intersecting codes is meaningful research work.

The importance of another concept, the trellis of a linear code [6, 15, 17], is in that it can be used to estimate the complexity of the Viterbi decoding algorithm.

A linear code with few weights [4] is useful in authentication codes, secret sharing schemes, and association schemes apart from its applications in consumer electronics, communication and data storage systems. Many recent papers are dedicated to constructing linear codes with few weights [7, 8, 16] by using the defining set and the technique of exponential sums.

The finite geometry method was first introduced in [1] and [14], and it has been effectively generalized at present to study codes with respect to the rank-metric in [12]. By using the finite geometry method, Liu and Wu [10] provided a technique of constructing codes with few weights, namely, the so-called relative two-weight and three-weight codes. Besides the applications already mentioned for codes with few weights, Liu and Wu further showed that relative two-weight and three-weight codes can be applied to the wire-tap channel of type II with the coset coding scheme. The geometry structures of relative two-weight and three-weight codes were given in [10]. By using these geometry structures, the t-wise intersection of relative three-weight codes was calculated in [9], and the trellis of relative two-weight codes was estimated in [11].

Based on the results of relative two-weight and three-weight codes, one can find that these codes have good geometric structures, and by using their geometric structures, one can easily construct these codes and determine some important parameters, say, generalized Hamming weights. In fact, by using the geometric structures and the combination techniques, the determination of the general support weight distribution of subcodes of relative two-weight and three-weight codes is also possible. All the present results and observations strongly motivate us to generalize relative two-weight and three-weight codes to codes with four weights, that is, relative four-weight codes. The paper will exactly aim at this goal, and we will define relative four-weight codes and then determine their geometric structures. Also, we will calculate the t-wise intersection and estimate the trellis of relative four-weight codes by using the geometric structures we have obtained.

The rest of the paper is organized as follows: Section 2 is devoted to basic definitions and results. The geometric construction of relative four-weight codes is presented in Section 3. The t-wise intersection of relative four-weight codes is determined in Section 4. The trellis is estimated in Section 5 and in the Appendix we will exhibit some key lemmas which are used to obtain the t-wise intersection of relative four-weight codes.

2 Definitions and foundations

The support of a codeword c, denoted by χ(c), is defined as the set of its non-zero coordinate positions. It is obvious that the Hamming weight of c, denoted by w(c), is w(c) = |χ(c)|. The intersection of the two codewords c and \(c^{\prime }\) is denoted by \(\chi (c)\cap \chi (c^{\prime })\). The t-wise intersection of a linear q-ary code C is defined as \(t=\min \limits \left \{|\cap ^{t}_{k=1}\chi (c_{k})| \mid c_{1},c_{2}, {\cdots } , c_{t} \text { are any } t \text { linearly independent codewords }\right \}\) and C is t-wise intersecting if t > 0. Let C1 be a k1-dimensional subcode of C and C2 be a k2-dimensional subcode of C satisfying \(C_{1}\subseteq C_{2}\subseteq C\), then C is called a relative three-weight code concerning C1 and C2, provided that C1 ∖{0}, C2 ∖ C1 and C ∖ C2 are all constant-weight codes.

Definition 2.1

Let C be an [n,k] code, and \(C_{1}\subseteq C_{2}\subseteq C_{3}\) be a k1, k2 and k3-dimensional subcode of C, respectively. Then, C is called a relative four-weight code with respect to C1, C2 and C3 and is denoted by C(w1,w2,w3,w4), if C1 ∖{0}, C2 ∖ C1, C3 ∖ C2 and C ∖ C3 are all constant-weight codes with weights w1, w2, w3 and w4, respectively.

Remark 2.2

In Definition 2.1, if the constant-weight codes C3 ∖ C2 and C ∖ C3 have the same weight, that is, w3 = w4, then a relative four-weight code reduces to a relative three-weight one defined in [10]. A relative four-weight code is thus a generalization of a relative three-weight one.

A subcode D of C is called a relative (r,r1,r2,r3) subcode of C with r1 ≤ r2 ≤ r3 ≤ r if D satisfies \(\dim D=r\), \(\dim (D\cap C_{1})=r_{1}\), \(\dim (D\cap C_{2})=r_{2}\) and \(\dim (D\cap C_{3})=r_{3}.\) Let <c1,c2,⋯ ,ct> be the subcode of C generated by c1,c2,⋯,ct. Define \(t^{\max \limits }_{i}=\max \limits \{\dim (\textless c_{1},c_{2},\cdots , c_{t}\textgreater \cap C_{i})\text { such that } c_{1},c_{2},\cdots , c_{t} \text { are any }\) t linearly independent codewords in C}, i = 1,2,3. Assume that, G to be a generator matrix of a k-dimensional q-ary linear code. The columns of G as points of the (k − 1)- dimensional projective space PG(k − 1,q) such a view point induces a map m(⋅) from PG(k − 1,q) to the set of non-negative integers: \(m:\mathbf {P}\mathbf {G}(k-1,q)\rightarrow \mathbb {N}\) where \(\mathbb {N}=\{0,1,2,\cdots \}\) and for any p ∈PG(k − 1,q), m(p) is the number of occurrence of p as a column of G. The value of p is denoted by m(p) and the m(⋅) is called a value assignment or value function. Define the value of \(S\subseteq \mathbf {P}\mathbf {G}(k-1,q)\) by m(S) = Σp∈Sm(p). In addition, let L ⊂{1,2,⋯ ,k} and p = {t1,t2,⋯ ,tk}∈PG(k − 1,q), then define PL(p) = (v1,v2,⋯ ,vk), where

$$ v_{i}= \left\{\begin{array}{ll} t_{i} & \text{if } i\in \mathrm{ L}\\ 0 & \text{otherwise.} \end{array}\right. $$

For a subset W ⊂PG(k − 1,q), define PL(W) = {PL(p)∣p ∈ W}. Clearly, PL(W) is a vector space, since W is a projective subspace of PG(k − 1,q). For a projective subspaces V of PG(k − 1,q) and integers l = 1,2,⋯ ,k − 1, we define Vl = {p ∈ V ∣p = 0,0,⋯ ,0,pl+ 1,⋯ ,pk}. That is, Vl is the set of points of V which are all 0 in the first l co-ordinates. Clearly Vl may be an empty set. If \(V^{l}\neq \varnothing \), then it is a projective subspaces of V. Let L1 = {1,2,⋯ ,k1}, L2 = {k1 + 1,k1 + 2,⋯ ,k2}, L3 = {k2 + 1,k2 + 2,⋯ ,k3}. For a non-negative integers ξ,η,γ,δ, we denote by \(P^{\xi }_{\eta \gamma \delta }\), a projective subspace of V of PG(k − 1,q) satisfying \(\dim {P_{L_{1}}}(V)=\xi -1\), \(\dim {P_{L_{2}}}(V^{k_{1}})=\eta -1\), \(\dim {P_{L_{3}}}(V^{k_{2}})=\gamma -1\) and \(\dim {P_{L}}(V^{k_{3}})=\delta -1.\) Hence, a projective subspace of dimension 0 is a set consisting of a single point and the empty set is viewed as a projective space of dimension − 1. Therefore, \(\dim (P^{\xi }_{\eta \gamma \delta })=\xi +\eta +\gamma +\delta -1.\)

Let

$$ \begin{array}{@{}rcl@{}} P^{1}_{000}&=& \{ p \in \mathbf{P}\mathbf{G}(k-1,q) \mid P_{L_{1}}(p)\neq 0 \} \\ P^{0}_{100}&=& \{ p \in \mathbf{P}\mathbf{G}(k-1,q) \mid P_{L_{1}}(p)=0, P_{L_{2}}(p)\neq 0 \quad \& \quad P_{L_{3}}(p)=0 \} \\ P^{0}_{010}&=& \{ p \in \mathbf{P}\mathbf{G}(k-1,q) \mid P_{L_{3}}(p)\neq 0\}\\ P^{0}_{001}&=&\{ p \in \mathbf{P}\mathbf{G}(k-1,q) \mid P_{L_{i}}(p) = 0 \text{ for } i = 1, 2, 3 \}. \end{array} $$

We will show that the values \(m(P^{1}_{000})\), \(m(P^{0}_{100})\), \(m(P^{0}_{010})\) and \(m(P^{0}_{001})\) play an important role in the characterization and construction of the relative four-weight codes.

Lemma 2.3

Let C1 be a k1-dimensional subcode of C, C2 be a k2-dimensional subcode and C3 be a k3-dimensional subcode satisfying C1 ⊂ C2 ⊂ C3 ⊂ C. There is a one-one correspondence between the non-zero codewords c1 ∈ C1, c2 ∈ C2 ∖ C1, c3 ∈ C3 ∖ C2 and c ∈ C ∖ C3 and the subspaces \(P^{k_{1}-1}_{(k_{2}-k_{1})(k_{3}-k_{2})(k-k_{3})}\), \(P^{k_{1}}_{(k_{2}-k_{1}-1)(k_{3}-k_{2})(k-k_{3})}\), \(P^{k_{1}}_{(k_{2}-k_{1})(k_{3}-k_{2}-1)(k-k_{3})}\) and \(P^{k_{1}}_{(k_{2}-k_{1})(k_{3}-k_{2})(k-k_{3}-1)}\), respectively. The one-one correspondence satisfies that if c1, c2, c3 and c correspond to \(P^{k_{1}-1}_{(k_{2}-k_{1})(k_{3}-k_{2})(k-k_{3})}\), \(P^{k_{1}}_{(k_{2}-k_{1}-1)(k_{3}-k_{2})(k-k_{3})}\), \(P^{k_{1}}_{(k_{2}-k_{1})(k_{3}-k_{2}-1)(k-k_{3})}\) and \(P^{k_{1}}_{(k_{2}-k_{1})(k_{3}-k_{2})(k-k_{3}-1)}\), respectively, then

$$ \begin{array}{@{}rcl@{}} m(\mathbf{P}\mathbf{G}(k-1,q))&=&n\\ n-w(c_{1})&=& m (P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})})\\ n-w(c_{2})&=&m (P^{k_{1}}_{({k_{2}-k_{1}}-1)(k_{3}-k_{2})(k-k_{3})})\\ n-w(c_{3})&=&m (P^{k_{1}}_{({k_{2}-k_{1}})(k_{3}-k_{2}-1)(k-k_{3})})\text{ and }\\ n-w(c)&=&m (P^{k_{1}}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3}-1)}). \end{array} $$

Proof

First, we start to prove fourth equation. Let c3 ∈ C3 ∖ C2, then the code c3 is given by \(c_{3}=(x_{1},\cdots ,x_{k_{1}},x_{k_{1}+1},\cdots ,x_{k_{2}},x_{k_{2}+1},\cdots ,x_{k_{3}},0,\cdots ,0)G\), where G is a generator matrix of C. Assume that the first k1 rows of G generate the subcode C1, the next (k2 − k1) rows of C1 and the first k1 rows of G together generate the subcode C2, the next (k3 − k2) rows of G and the first k2 rows of G together generate the subcode C3. Since c3 ∈ (C3 ∖ C2) there exists some j satisfying k2 + 1 ≤ j ≤ k3 such that xj≠ 0. Consider the space U of GF(q)k which is orthogonal to the vector \((x_{1},x_{2},\cdots ,x_{k_{1}},x_{k_{1}+1},{\cdots } ,x_{k_{2}},x_{k_{2}+1},\cdots ,x_{k_{3}},0,\cdots ,0 )\), Then, \(\dim {P_{L_{1}}(U)}=k_{1}-1\), \(\dim {P_{L_{2}}(U^{k_{2}})}=k_{2}-k_{1}-1\), \(\dim {P_{L_{3}}(U^{k_{2}})}=k_{3}-k_{2}-2\) and \(\dim {P(U^{k_{3}})}=k-k_{3}-1.\) This implies, U is exactly \(P^{k_{1}}_{(k_{2}-k_{1})(k_{3}-k_{2}-1)(k-k_{3})}\) corresponding to the codeword c3. Therefore, \(n-w(c_{3})=m(P^{k_{1}}_{(k_{2}-k_{1})(k_{3}-k_{2}-1)(k-k_{3})}).\) Now, the first equation has to be proved, since the columns of the generator matrix as the points of the projective space PG(k − 1,q) is clear. The proof of the other equation is similar to the above one, hence the proof can be skipped. □

3 Construction of relative four-weight codes

In this section, we will present the geometric construction of a relative four-weight code and determine the parameters of a relative four-weight code. Though relative four-weight codes have one weight more than relative three-weight codes, the relations of the projective subspaces become much more complicated than that of relative three-weight codes. The way to get the geometric structure of relative four-weight codes is by induction and by fully using the relations of different projective subspaces.

3.1 The determination of the geometric structure

Theorem 3.1

Consider C1 ⊂ C2 ⊂ C3 ⊂ C and C be n length linear code and let C1, C2 and C3 be generated by the first k1, k2 and k3 rows of G, respectively. Then, C is a relative four-weight code with respect to C1, C2 and C3 if and only if their following value functions are true

$$ \begin{array}{@{}rcl@{}} &&m(P^{1}_{000})~is~a~constant~for~all~points~P^{1}_{000},\\ &&m(P^{0}_{100})~is~a~constant~for~all~points~P^{0}_{100},\\ &&m(P^{0}_{010})~is~a~constant~for~all~points~P^{0}_{010}~and\\ &&m(P^{0}_{001})~is~a~constant~for~all~points~P^{0}_{001} \end{array} $$

Proof

Assume that the value function m(⋅) has same values on \(P^{1}_{000}\), \(P^{0}_{100}\), \(P^{0}_{010}\) and \(P^{0}_{001}\). This implies that the subspaces \(P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})}\) will have the same value. Since \(P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})}\) contains the same number of points from the set of points \(P^{1}_{000}\), \(P^{0}_{100} P^{0}_{010}\) and \(P^{0}_{001},\) respectively. It follows from Lemma 2.3 that all the non-zero codewords of C1 have the same weight. Similarly, we know that all the non-zero codewords of C2 ∖ C1 have the same weight and all the non-zero codewords of C3 ∖ C2 and C ∖ C3 have the same weight. Therefore, C is a relative four-weight code with respect to C1, C2 and C3.

Conversely, we assume that C is a relative four-weight code. In order to show that the value function has the same values on the points \(P^{1}_{000}\), \(P^{0}_{100}\), \(P^{0}_{010}\) and \(P^{0}_{001}\), respectively. We will prove the following general result

$$ m(P^{\xi}_{\eta\gamma\delta}) = \text{ constant for any fixed } (\xi,\eta,\gamma,\delta). $$
(3.1)

The (3.1) is true. If we denote ξ + η + γ + δ = k − j for any \(j \in \{0,1,\dots ,k-1\}\), the equation in (3.1) will be true. We can prove the theorem by induction on j.

For j = 0, we have ξ + η + γ + δ = k and \(P^{\xi }_{\eta \gamma \delta }=\mathbf {P}\mathbf {G}(k-1,q)\), so \(m(P^{\xi }_{\eta \gamma \delta }) =m(\mathbf {P}\mathbf {G}(k-1,q)) =n.\)

For j = 1, we have ξ + η + γ + δ = k − 1 and \(P^{\xi }_{\eta \gamma \delta }\) is equal to one of the four kinds of subspaces \(P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})}\), \(P^{k_{1}}_{({k_{2}-k_{1}}-1)(k_{3}-k_{2})(k-k_{3})}\), \(P^{k_{1}}_{({k_{2}-k_{1}})(k_{3}-k_{2}-1)(k-k_{3})}\) and \(P^{k_{1}}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3}-1)}\). It follows from Lemma 2.3, \(m(P^{\xi }_{\eta \gamma \delta })\) is a constant.

Now, we assume (3.1) is true for j < j0, that is, it is true for any fixed four quatral (ξ,η,γ,δ) satisfying ξ + η + γ + δ > k − j0. We will show (3.1) is true for j = j0 in the following. For any \(P^{\xi }_{\eta \gamma \delta }\) satisfying ξ + η + γ + δ = k − j0, there exists a \(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }}\) satisfying \(\xi ^{\prime }+\eta {'}+\gamma ^{\prime }+\delta ^{\prime }=k-(j_{0}-3)\) such that \(P^{\xi }_{\eta \gamma \delta }\subset P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }}.\) We may distinguish the parameter into the following cases.

(Case 1) :

1f \(\xi ^{\prime }=\xi +3\), then \(\eta ^{\prime }=\eta \), \(\gamma ^{\prime }=\gamma \) and \(\delta ^{\prime }=\delta \), since

\(m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})=(q+2)m(P^{\xi +1}_{\eta \gamma \delta })-qm(P^{\xi }_{\eta \gamma \delta })\),

\(m(P^{\xi }_{\eta \gamma \delta })=(\frac {q+2}{q})m(P^{\xi +1}_{\eta \gamma \delta })-\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\). Thus, \(m(P^{\xi }_{\eta \gamma \delta })\) is constant, by the inductive hypothesis.

(Case 2) :

If \(\xi ^{\prime }=\xi +2\), \(\eta ^{\prime }=\eta +1\), then \(\delta ^{\prime }=\delta \) and \(\gamma ^{\prime }=\gamma \), since

\(m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})=qm(P^{\xi +2}_{\eta \gamma \delta })+m(P^{\xi }_{(\eta +1)\gamma \delta }))-q m(P^{\xi }_{\eta \gamma \delta })\), \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi +2}_{\eta \gamma \delta })+\frac {1}{q}m(P^{\xi }_{(\eta +1)\gamma \delta }) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\) which is constant, by the inductive hypothesis.

(Case 3) :

If \(\delta ^{\prime }=\delta +2\), \(\eta ^{\prime }=\eta +1\), then \(\xi ^{\prime }=\xi \) and \(\gamma ^{\prime }=\gamma \), following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi }_{\eta \gamma (\delta +2})+\frac {1}{q}m(P^{\xi }_{(\eta +1)\gamma \delta }) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 4) :

If \(\gamma ^{\prime }=\gamma +2\), \(\eta ^{\prime }=\eta +1\), then \(\xi ^{\prime }=\xi \) and \(\delta ^{\prime }=\delta \), following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi }_{\eta (\gamma +2)\delta }+\frac {1}{q}m(P^{\xi }_{(\eta +1)\gamma \delta }) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 5) :

If \(\xi ^{\prime }=\xi +2\), \(\gamma ^{\prime }=\gamma +1\), then \(\eta ^{\prime }=\eta \) and \(\delta ^{\prime }=\delta \), following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi +2}_{\eta \gamma \delta })+\frac {1}{q}m(P^{\xi }_{(\eta +1)\gamma \delta }) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 6) :

If \(\gamma ^{\prime }=\gamma +2\), \(\delta ^{\prime }=\delta +1\), then \(\xi ^{\prime }=\xi \) and \(\eta ^{\prime }=\eta \), following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi }_{\eta (\gamma +2)\delta })+\frac {1}{q}m(P^{\xi }_{\eta \gamma (\delta +1)}) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 7) :

If \(\xi ^{\prime }=\xi +2 \delta ^{\prime }=\delta +1\), then \(\gamma ^{\prime }=\gamma \) and \(\eta ^{\prime }=\eta \), following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi +2}_{\eta \gamma \delta })+\frac {1}{q}m(P^{\xi }_{\eta \gamma (\delta +1)}) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 8) :

If \(\xi ^{\prime }=\xi +1\), \(\eta ^{\prime }=\eta +1\) and \(\delta ^{\prime }=\delta +1\), then \(\gamma ^{\prime }=\gamma \). Following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })= m(P^{\xi +1}_{\eta \gamma \delta })+\frac {1}{q}m(P^{\xi }_{\eta \gamma \delta })+m(P^{\xi }_{\eta \gamma (\delta +1)}) -\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 9) :

If \(\xi ^{\prime }=\xi +1\), \(\eta ^{\prime }=\eta +1\) and \(\gamma ^{\prime }=\gamma +1\), then \(\delta ^{\prime }=\delta \). Following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })=m(P^{\xi +1}_{\eta \gamma \delta })-\frac {1}{q}m(P^{\xi }_{(\eta +1)\gamma \delta })+m(P^{\xi }_{\eta \gamma (\delta +1)})- \frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 10) :

If \(\xi ^{\prime }=\xi +1\), \(\gamma ^{\prime }=\gamma +1\) and \(\delta ^{\prime }=\delta +1\), then \(\eta ^{\prime }=\eta \). Following the procedure in Case 2, we obtain \(m(P^{\xi }_{\eta \gamma \delta })=m(P^{\xi +1}_{\eta \gamma \delta })-\frac {1}{q}m(P^{\xi }_{\eta (\gamma +1)\delta })+m(P^{\xi }_{\eta \gamma (\delta +1)})- \frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 11) :

If \(\xi ^{\prime }=\xi \), \(\eta ^{\prime }=\eta +1\), \(\gamma ^{\prime }=\gamma +1\) and \(\delta ^{\prime }=\delta +1\), following the procedure in Case 2, then we obtain \(m(P^{\xi }_{\eta \gamma \delta })=m(P^{\xi }_{(\eta +1)\gamma \delta })-\frac {1}{q}m(P^{\xi }_{\eta (\gamma +1)\delta })+m(P^{\xi }_{\eta \gamma (\delta +1)})- \frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 12) :

If \(\xi ^{\prime }=\xi \), \(\eta ^{\prime }=\eta \), \(\gamma ^{\prime }=\gamma \), then \(\delta ^{\prime }=\delta +3\). Following the procedure in Case 1, we obtain \(m(P^{\xi }_{\eta \gamma \delta })=(\frac {q+2}{q})m(P^{\xi }_{\eta \gamma (\delta +1)})-\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 13) :

If \(\xi ^{\prime }=\xi \), \(\eta ^{\prime }=\eta \), \(\delta ^{\prime }=\delta \), then \(\gamma ^{\prime }=\gamma +3\). Following the procedure in Case 1, we obtain \(m(P^{\xi }_{\eta \gamma \delta })=(\frac {q+2}{q})m(P^{\xi }_{\eta (\gamma +1)\delta })-\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

(Case 14) :

If \(\xi ^{\prime }=\xi \), \(\gamma ^{\prime }=\gamma \), \(\delta ^{\prime }=\delta \), then \(\eta ^{\prime }=\eta +3\). Following the procedure in Case 1, we obtain \(m(P^{\xi }_{\eta \gamma \delta })=(\frac {q+2}{q})m(P^{\xi }_{(\eta +1)\gamma \delta })-\frac {1}{q} m(P^{\xi ^{\prime }}_{\eta ^{\prime }\gamma ^{\prime }\delta ^{\prime }})\), which is constant.

Hence, this is true for j = j0. The theorem is proved by the induction hypothesis.

□

Remark 3.2

Theorem 3.1 may be viewed as an effective generalization of the main result in [10], and it plays a key role in constructing a relative four-weight code and the calculation of the t-wise intersection and the trellis in later sections.

3.2 The parameters of a relative four-weight code

From Theorem 3.1, we can construct a generator matrix G for a relative four-weight code as follows: choose the appropriate k-dimensional column vectors over GF(q)(or equivalently, points of PG(k − 1,q)) and use them as the columns of G, such that \(m(P^{1}_{000})\), \(m(P^{0}_{100})\), \(m(P^{0}_{010})\) and \(m(P^{0}_{001})\) are all constant, respectively. Then, the code C by G is a generator matrix for relative four-weight code. Let k1, k2 and k3 be any positive integers such that k1 < k2 < k3 ≤ k. Taking L1 = {1,2,⋯ ,k1}, L2 = {k1 + 1,⋯ ,k2} and L3 = {k2 + 1,⋯ ,k3}. We know that, there are exactly \(\frac {q^{k}-q^{k-k_{1}}}{q-1}\) points \(P^{1}_{000}\), \(\frac {q^{k-k_{1}}-q^{k-k_{2}}}{q-1}\) points \(P^{0}_{100}\), \(\frac {q^{k-k_{2}}-q^{k-k_{3}}}{q-1}\) points \(P^{0}_{010}\) and \(\frac {q^{k-k_{3}}-1}{q-1}\) points \(P^{0}_{001}\) and G is a generator matrix with n columns, the length of C is given by n, where

$$ \begin{array}{@{}rcl@{}} n&=&\frac{q^{k}-q^{k-k_{1}}}{q-1}m(P^{1}_{000})+\frac{q^{k-k_{1}}-q^{k-k_{2}}}{q-1}m(P^{0}_{100})+\frac{q^{k-k_{2}}-q^{k-k_{3}}}{q-1}m(P^{0}_{010}) +\frac{q^{k-k_{3}}-1}{q-1}m(P^{0}_{001}).\\ \end{array} $$

From Lemma 2.3, we get

$$ \begin{array}{@{}rcl@{}} w(c_{1})&=&n-m(P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})}). \end{array} $$

It is clear that the projective subspace \(P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})}\) contains \(\frac {q^{k-1}-q^{k-k_{1}}}{q-1}\) points \(P^{1}_{000}\), \(\frac {q^{k-k_{1}}-{q^{k-k_{2}}}}{q-1}\) points \(P^{0}_{100}\), \(\frac {q^{k-k_{2}}-{q^{k-k_{3}}}}{q-1}\) points \(P^{0}_{010}\) and \(\frac {q^{k-k_{3}}-1}{q-1}\) points \(P^{0}_{001}\). Thus,

$$ \begin{array}{@{}rcl@{}} m(P^{k_{1}-1}_{({k_{2}-k_{1}})(k_{3}-k_{2})(k-k_{3})})&=&\frac{q^{k-1}-q^{k-k_{1}}}{q-1}m(P^{1}_{000})+\frac{q^{k-k_{1}}-{q^{k-k_{2}}}}{q-1}m(P^{0}_{100})\\ &&+\frac{q^{k-k_{2}}-{q^{k-k_{3}}}}{q-1}m(P^{0}_{010})+\frac{q^{k-k_{3}}-1}{q-1}m(P^{0}_{001}). \end{array} $$

From the above two equations, we have

$$ \begin{array}{@{}rcl@{}} w_{1}&=&w(c_{1})\\ &=&q^{k-1}m(P^{1}_{000}), \text{ for all } c_{1}\in C_{1}. \end{array} $$

Similarly, apply the above method, and we arrive

$$ \begin{array}{@{}rcl@{}} w_{2}&=&(q^{k-1}-q^{k-k_{1}-1})m(P^{1}_{000}))+(q^{k-k_{1}-1})m(P^{0}_{100}),\\ w_{3}&=&(q^{k-1}-q^{k-k_{1}-1})m(P^{1}_{000})+(q^{k-k_{1}-1}-q^{k-k_{2}-1})m(P^{0}_{100})\\ &&+(q^{k-k_{2}-1})m(P^{0}_{010}),\\ \end{array} $$

and

$$ \begin{array}{@{}rcl@{}} w_{4}&=&(q^{k-1}-q^{k-k_{1}-1})m(P^{1}_{000})+(q^{k-k_{1}-1}-q^{k-k_{2}-1})m(P^{0}_{100})+(q^{k-k_{2}-1}-q^{k-k_{3}-1})m(P^{0}_{010})\\ &&+(q^{k-k_{3}-1})m(P^{0}_{001}).\\ \end{array} $$

Lemma 3.3

Let C(w1,w2,w3,w4) be a relative four-weight code with respect to a k1-dimensional subcode C1, k2-dimensional subcode C2 and k3-dimensional subcode C3, and let G and m(⋅) be generator matrix and value function, respectively. Then, m(⋅) satiesfies

$$ m(p)= \left\{\begin{array}{ll} \frac{w_{1}}{q^{k-1}}, & \text{ for } p \in S_{1},\\ \frac{q^{k_{1}}w_{2}-(q^{k_{1}}-1)w_{1}}{q^{k-1}}, & \text{ for } p\in S_{2},\\ \frac{q^{k_{2}}w_{3}-(q^{k_{1}}-1)w_{1}-(q^{k_{2}}-q^{k_{1}})w_{2}}{q^{k-1}}, & \text{ for } p\in S_{3},\\ \frac{q^{k_{3}}w_{4}-(q^{k_{1}}-1)w_{1}-(q^{k_{2}}-q^{k_{1}})w_{2}-(q^{k_{3}}-q^{k_{2}})w_{3}}{q^{k-1}}, & \text{ for } p\in S_{4}, \end{array}\right. $$
(3.2)

where Si ⊂PG(k − 1,q) for 1 ≤ i ≤ 4 and \(S_{1}=\{p \mid P_{L_{1}}\neq 0\}\), \(S_{2}=\{p \mid P_{L_{1}}=0,~ P_{L_{2}}\neq 0~~ \& ~~ P_{L_{3}}=0 \}\), \(S_{3}=\{p \mid P_{L_{3}}\neq 0\}\) and \(S_{4}=\{p \mid P_{L_{1}}= P_{L_{2}}= P_{L_{3}}=0\}\), where L1 = {1,2,⋯ ,k1}, L2 = {k1 + 1,⋯ ,k2} and L3 = {k2 + 1,⋯ ,k3}.

Proof

From the above geometric construction, we have

$$ \begin{array}{@{}rcl@{}} w_{1} = w(c_{1})=q^{k-1}m(P^{1}_{000}), \text{ for all } c_{1}\in C_{1}.\\ \end{array} $$

Then, it will be

$$ \begin{array}{@{}rcl@{}} m(P^{1}_{000})&=&\frac{w_{1}}{q^{k-1}},\\ \end{array} $$

again, we have

$$ \begin{array}{@{}rcl@{}} w_{2}&=&(q^{k-1}-q^{k-k_{1}-1})m(P^{1}_{000})+(q^{k-k_{1}-1})m(P^{0}_{100}). \\ \end{array} $$

Substituting the value of \(m(P^{1}_{000})\) into the above equation, we get

$$ \begin{array}{@{}rcl@{}} m(P^{0}_{100}) = \frac{q^{k_{1}}w_{2}-w_{1}(q^{k_{1}}-1)}{q^{k-1}}. \end{array} $$

Similarly,

$$ \begin{array}{@{}rcl@{}} w_{3} = (q^{k-1}-q^{k-k_{1}-1})m(P^{1}_{000})+(q^{k-k_{1}-1}-q^{k-k_{2}-1})m(P^{0}_{100}) +(q^{k-k_{2}-1})m(P^{0}_{010}). \end{array} $$

Substituting the values of \(m(P^{1}_{000})\) and \(m(P^{0}_{010})\) into the above equation, and after simplification, we arrive

$$ \begin{array}{@{}rcl@{}} m(P^{0}_{010})&=&\frac{q^{k_{2}}w_{3}-(q^{k_{1}}-1)w_{1}-(q^{k_{2}}-q^{k_{1}})w_{2}}{q^{k-1}}. \end{array} $$

Again,

$$ \begin{array}{@{}rcl@{}} w_{4}&=&(q^{k-1}-q^{k-k_{1}-1})m(P^{1}_{000})+(q^{k-k_{1}-1}-q^{k-k_{2}-1})\\ &&m(P^{0}_{100})+(q^{k-k_{2}-1}-q^{k-k_{3}-1})m(P^{0}_{010})+(q^{k-k_{3}-1})m(P^{0}_{001}), \end{array} $$

and substituting the above all value functions, finally we get

$$ \begin{array}{@{}rcl@{}} m(P^{0}_{001})&=&\frac{q^{k_{3}}w_{4}-(q^{k_{1}}-1)w_{1}-(q^{k_{2}}-q^{k_{1}})w_{2}-(q^{k_{3}} -q^{k_{2}})w_{3}}{q^{k-1}}. \end{array} $$

□

Example 3.4

Consider a value function

$$ m(p)= \left\{\begin{array}{ll} 1 & \text{if } p\in S_{1},\\ 3 & \text{if } p\in S_{2},\\ 4 & \text{if } p\in S_{3},\\ 6 & \text{if } p\in S_{4}, \end{array}\right. $$

for q = 2 and let k = 5, k1 = 2, k2 = 3, k3 = 4. Then, we have w1 = 16, w2 = 24, w3 = 26 and w4 = 28, where L1 = {1,2}, L2 = {3} and L3 = {4}.

By the above procedure, we generate the generator matrix G as follows.

$$ \left[{\begin{array}{ccccccccccccccccccccccccc} 1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&1&1&1&1&1&1&1&1&0\\ 0&0&0&1&1&1&1&1&1&1&1&1&1&1&1&1&1&0&1&1&1&1&1&0&0\\ 1&1&1&0&0&1&1&0&1&1&1&1&1&1&1&1&0&1&0&1&1&1&0&1&1\\ 1&1&1&1&1&1&1&1&1&1&1&0&1&1&0&1&0&1&1&1&1&1&1&1&0\\ 0&0&0&0&0&0&0&0&1&1&1&1&1&1&1&1&0&0&0&0&0&0&0&0&0 \end{array} }\right. $$
$$ \left.{\begin{array}{cccccccccccccccccccccccccccccc} 0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0&0&1&1&1&1&1&0&0&0\\ 1&0&0&0&0&0&0&0&0&1&1&1&1&1&0&0&1\\ 0&1&1&0&0&0&0&0&0&0&1&1&0&1&1&1&0\\ 0&0&0&1&1&1&1&1&1&1&1&1&1&1&0&0&0 \end{array} }\right]. $$

Note that each of the 24 points \(P^{1}_{000}\) appears in G once; each of the 4 points \(P^{0}_{100}\) appears three times; each of the 2 points \(P^{0}_{010}\) appears in G four times and there is only one point \(P^{0}_{001}\) which appears in G for six times.

Remark 3.5

Based on the above geometric construction and by borrowing the method in [10], one can show that relative four-weight codes will behave similarly as relative three-weight codes in that they are optimal in certain cases in the wire-tap channel II. Further, since relative four-weight codes have only four-weights and the weight distribution is clear also based on the geometric structure, they can also be applied to secret sharing schemes based on linear codes [4], and we omit these detailed arguments.

4 The intersection of relative four-weight codes

The t-wise intersection of a linear code is in general difficult to calculate. By using the geometric structure, the t-wise intersection of binary relative three-weight codes is obtained in [9]. Since we have gotten the geometric structure of a relative four-weight code, we also expect to calculate the t-wise intersection of a relative four-weight code. However, a relative four-weight code has more complicated structure than a relative three-weight code, which leads to the complexity of t linearly independent codewords. It is thus tedious to get the t-wise intersection of a relative four-weight code, and we will have to classify the analysis into many cases, and in each case we will generalize the method in [9] by developing the skill of the matrix operation. The novelty of our work is in that in each case we will construct an invertible matrix which is a product of invertible matrices and expanding the generator matrix, which leads to the t-wise intersection of binary relative four-weight codes.

Lemma 4.1

[9] The t-wise intersection of a linear constant-weight code w is equal to \((\frac {q-1}{q})^{t-1}w.\)

As in the case of relative three-weight codes, it is a key to construct the generator matrix of linearly independent codewords. By organize the t linearly independent codewords c1,c2,c3,⋯ ,ct into a matrix form Tt×n, we can get the t-wise intersection of four-weight codes as below.

$$ \begin{bmatrix} c_{1}\\ c_{2}\\ \vdots\\ c_{t} \end{bmatrix} =X_{t\times k}G =(X_{t\times k_{1}},X_{t\times (k-k_{1})}) \begin{bmatrix} G_{k_{1}\times n}\\ G_{(k-k_{1})\times n} \end{bmatrix} $$
$$ \begin{array}{@{}rcl@{}} =(X_{t\times k_{2}},X_{t\times (k-k_{2})}) \begin{bmatrix} G_{k_{2}\times n}\\ G_{(k-k_{2})\times n}\\ \end{bmatrix} \end{array} $$
$$ \begin{array}{@{}rcl@{}} =(X_{t\times k_{3}},X_{t\times (k-k_{3})}) \begin{bmatrix} G_{k_{3}\times n}\\ G_{(k-k_{3})\times n}\\ \end{bmatrix}. \end{array} $$

Note that rank(Xt×k) = t, and that the block matrices \(G_{k_{1}\times n}\), \(G_{k_{2}\times n}\) and \(G_{k_{3}\times n}(k_{1}<k_{2}<k_{3})\) are generator matrices of C1, C2 and C3, respectively.

Lemma 4.2

Let C be a relative four-weight code and it has the subcode D = <c1,c2,⋯ ,ct> is a relative (t,t1,t2,t3) code, then \(rank(X_{t\times (k-k_{1})})=t-t_{1}\), \(rank(X_{t\times (k-k_{2})})=t-t_{2}\) and \(rank(X_{t\times (k-k_{3})})=t-t_{3}.\)

Proof

Since < c1,c2,⋯ ,ct > is a relative (t,t1,t2,t3) subcode, there is an invertible matrix Yt×t such that

$$ \begin{array}{@{}rcl@{}} Y_{t\times t}X_{t\times k}&=& (Y_{t\times t}X_{t\times k_{1}},Y_{t\times t}X_{t\times (k-k_{1})})\\ &=&(Y_{t\times t}X_{t\times k_{2}},Y_{t\times t}X_{t\times (k-k_{2})})\\ &=&(Y_{t\times t}X_{t\times k_{3}},Y_{t\times t}X_{t\times (k-k_{3})})\\ &=& \begin{bmatrix} X^{\prime}_{t_{1}\times k_{1}} & 0_{t_{1}\times (k-k_{1})} \\ X^{\prime}_{(t-t_{1})\times k_{1}} & X^{\prime}_{(t-t_{1})\times (k-k_{1})} \\ \end{bmatrix}\\ &=& \begin{bmatrix} X^{\prime}_{t_{2}\times k_{2}} & 0_{t_{1}\times (k_{2}-k_{1})} & 0_{t_{1}\times (k-k_{2})} \\ X^{\prime\prime}_{(t_{2}-t_{1})\times k_{1}} & X^{\prime\prime}_{(t_{2}-t_{1})\times (k_{2}-k_{1})} & 0_{(t_{2}-t_{1})\times (k-k_{2})} \\ X^{\prime\prime}_{(t-t_{2})\times k_{1}} & X^{\prime\prime}_{(t-t_{2})\times (k_{2}-k_{1})} & X^{\prime\prime}_{(t-t_{2})\times (k-k_{2})} \\ \end{bmatrix}\\ &=& \begin{bmatrix} X^{\prime}_{t_{3}\times k_{3}} & 0_{t_{1}\times (k_{2}-k_{1})} & 0_{t_{1}\times (k_{3}-k_{2})} & 0_{t_{1}\times (k-k_{3})} \\ X^{\prime\prime}_{(t_{2}-t_{1})\times k_{1}} & X^{\prime\prime}_{(t_{2}-t_{1})\times (k_{2}-k_{1})} & 0_{(t_{2}-t_{1})\times (k_{2}-k_{1})} & 0_{(t_{2}-t_{1})\times (k-k_{3})} \\ X^{\prime\prime}_{(t_{3}-t_{2})\times k_{1}} & X^{\prime\prime}_{(t_{3}-t_{2})\times (k_{2}-k_{1})} & X^{\prime\prime}_{(t_{3}-t_{2})\times (k_{3}-k_{2})} & 0_{(t_{3}-t_{2})\times (k-k_{3})}\\ X^{\prime\prime\prime}_{(t-t_{3})\times k_{1}} & X^{\prime\prime\prime}_{(t-t_{3})\times (k_{2}-k_{1})} & X^{\prime\prime\prime}_{(t-t_{3})\times (k_{3}-k_{2})} & X^{\prime\prime\prime}_{(t-t_{3})\times (k-k_{3})} \end{bmatrix}, \end{array} $$

with \(rank(X^{\prime }_{t_{{1}\times k_{1}}})=t_{1}\), \(rank(X^{\prime }_{(t-t_{1})\times (k-k_{1})})=t-t_{1}\), \(rank(X^{\prime \prime }_{(t-t_{2})\times (k-k_{2})})=t-t_{2}\) and \(rank(X^{\prime \prime \prime }_{(t-t_{3})\times (k-k_{3})})=t-t_{3}.\) Therefore, we have

$$ \begin{array}{@{}rcl@{}} rank(X_{t\times (k-k_{1})})&=&rank(Y_{t\times t})X_{t\times (k-k_{1})}\\ &=&rank(X^{\prime}_{(t-t_{1})\times (k-k_{1})})\\ &=&t-t_{1},\\ rank(X_{t\times (k-k_{2})})&=&rank(Y_{t\times t})X_{t\times (k-k_{2})}\\ &=&rank(X^{\prime\prime}_{(t-t_{2})\times (k-k_{2})})\\ &=&t-t_{2},\\ rank(X_{t\times (k-k_{3})})&=&rank(Y_{t\times t})X_{t\times (k-k_{3})}\\ &=&rank(X^{\prime\prime\prime}_{(t-t_{3})\times (k-k_{3})})\\ &=&t-t_{3}. \end{array} $$

□

The t-wise intersecting of the relative four-weight code C(w1,w2,w3,w4) is closely related to the size of w1, w2, w3 and w4. Denote mj = m(pj) for j = 1,2,3,4, where pj ∈ Sj for every j. The above notation is same as in Lemma 3.3 and from (3.2), we get the following

$$ \begin{array}{@{}rcl@{}} w_{1} &=& m_{1}q^{k-1},\\ w_{1}-w_{2}&=&q^{k-k_{1}-1}(m_{1}-m_{2}),\\ w_{2}-w_{3}&=&q^{k-k_{2}-1}(m_{2}-m_{3}),\\ w_{3}-w_{4}&=&q^{k-k_{3}-1}(m_{3}-m_{4}). \end{array} $$

We move towards the calculation of the t-wise intersection of relative four-weight codes. It is based on the relation among w1, w2, w3 and w4. According to these relations, we altogether get twenty four cases, in which cases 1 and 2 are completely different from the rest of the cases. So that, they required a separate calculation analysis. The remaining cases can be grouped into six major classes. The first major class cases (3, 4, 5, 6 and 7) with first key lemma, the second major class cases (8, 9 and 10) with second key lemma, the third major class cases (11, 12, 13, 14 and 15) with third key lemma, the fourth major class cases (16, 17 and 18) with fourth key lemma, the fifth major class cases (19, 20 and 21) with fifth key lemma and the sixth major class cases (22, 23 and 24) with sixth key lemma followed by the other cases, can be proved respectively. To avoid the tedious procedure, all the key lemmas are presented in the Appendix to make the work easier.

Now, we classify the cases of the calculation of the t-wise intersection as follows.

Theorem 4.3

The t-wise intersection of relative four-weight codes C(w1,w2,w3,w4) is equal to

  1. 1.

    \((\frac {1}{2})^{t-1}w_{1},~~ w_{4}>w_{3}>w_{2}>w_{1}.\)

  2. 2.

    \(\left \{\begin {array}{ll}(\frac {1}{2})^{t-1}w_{1} -(\frac {1}{2})^{t-t^{\max \limits }_{1}-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3})\\ -(\frac {1}{2})^{t-t^{\max \limits }_{3}-1}(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{2}>w_{3}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t^{\max \limits }_{1}-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3})\\ -(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{1}>w_{2}>w_{3}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t^{\max \limits }_{1}-1}(w_{1}-w_{2})-(w_{2}-w_{3})\\ -(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{1}>w_{2}>w_{3}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(w_{1}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{2}>w_{3}>w_{4}. \end {array}\right . \end {array}\right .\)

  3. 3.

    \(\left \{\begin {array}{ll} \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{2}>w_{1}>w_{4}>w_{3} \end {array}\right .\\ \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t&\\ w_{2}>w_{1}>w_{4}>w_{3} \end {array}\right . \end {array}\right .\)

  4. 4.

    \(\left \{\begin {array}{ll} \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{2}>w_{4}>w_{1}>w_{3} \end {array}\right .\\ \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t&\\ w_{2}>w_{4}>w_{1}>w_{3} \end {array}\right . \end {array}\right .\)

  5. 5.

    \(\left \{\begin {array}{ll} \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{2}>w_{4}>w_{3}>w_{1} \end {array}\right .\\ \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t&\\ w_{2}>w_{4}>w_{3}>w_{1} \end {array}\right . \end {array}\right .\)

  6. 6.

    \(\left \{\begin {array}{ll} \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{4}>w_{2}>w_{3}>w_{1} \end {array}\right .\\ \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t&\\ w_{4}>w_{2}>w_{3}>w_{1} \end {array}\right . \end {array}\right .\)

  7. 7.

    \(\left \{\begin {array}{ll} \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{4}>w_{2}>w_{1}>w_{3} \end {array}\right .\\ \min \limits \{(\frac {1}{2})^{t-1}w_{1}-(w_{4}-w_{3});(\frac {1}{2})^{t-1}w_{1}\}, & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t&\\ w_{4}>w_{2}>w_{1}>w_{3} \end {array}\right . \end {array}\right .\)

  8. 8.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+ (\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t_{2}-1}(w_{3}-w_{2}), & \text {if } t_{2}^{\max \limits }<t, t_{1}^{\max \limits }<t \text { and } w_3>w_4>w_2>w_1 \\ (\frac {1}{2})^{t-1}w_{1}+ (\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text {if }t_{2}^{\max \limits }=t, t_{1}^{\max \limits }<t \text { and } w_3>w_4>w_2>w_1\\ (\frac {1}{2})^{t-1}w_{1} +(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text {if } t_{2}^{\max \limits }=t_{1}^{\max \limits }=t \text { and } w_3>w_4>w_2>w_1. \end {array}\right .\)

  9. 9.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+ (\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t_{2}-1}(w_{3}-w_{2}), & \text {if } t_{2}^{\max \limits }<t, t_{1}^{\max \limits }<t \text { and } w_3>w_2>w_1>w_4 \\ (\frac {1}{2})^{t-1}w_{1}+ (\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text {if } t_{2}^{\max \limits }=t, t_{1}^{\max \limits }<t \text { and } w_3>w_2>w_1>w_4\\ (\frac {1}{2})^{t-1}w_{1} +(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text {if } t_{2}^{\max \limits }=t_{1}^{\max \limits }=t \text { and } w_3>w_2>w_1>w_4.\ \end {array}\right .\)

  10. 10.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+ (\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t_{2}-1}(w_{3}-w_{2}), & \text {if }t_{2}^{\max \limits }<t, t_{1}^{\max \limits }<t \text { and } w_3>w_2>w_4>w_1 \\ (\frac {1}{2})^{t-1}w_{1}+ (\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text {if }t_{2}^{\max \limits }=t, t_{1}^{\max \limits }<t \text { and } w_3>w_2>w_4>w_1\\ (\frac {1}{2})^{t-1}w_{1} +(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text {if }t_{2}^{\max \limits }=t_{1}^{\max \limits }=t \text { and } w_3>w_2>w_4>w_1. \end {array}\right .\)

  11. 11.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{3}>w_{2}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{1}>w_{3}>w_{2}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t ,~t_{1}^{\max \limits }<t&\\ w_{1}>w_{3}>w_{2}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{4}) -(w_{1}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{3}>w_{2}>w_{4}. \end {array}\right . \end {array}\right .\)

  12. 12.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{3}>w_{4}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~ t_{2}^{\max \limits }<t &\\ w_{1}>w_{3}>w_{4}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=~t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{1}>w_{3}>w_{4}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{4}) -(w_{1}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{3}>w_{4}>w_{2}. \end {array}\right . \end {array}\right .\)

  13. 13.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{3}>w_{1}>w_{2}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }<t &\\ w_{3}>w_{1}>w_{2}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{3}>w_{1}>w_{2}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{4}) -(w_{1}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{3}>w_{1}>w_{2}>w_{4}. \end {array}\right . \end {array}\right .\)

  14. 14.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{3}>w_{1}>w_{4}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{3}>w_{1}>w_{4}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{3}>w_{1}>w_{4}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{4}) -(w_{1}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{3}>w_{1}>w_{4}>w_{2}. \end {array}\right . \end {array}\right .\)

  15. 15.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{3}>w_{4}>w_{1}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{3}>w_{4}>w_{1}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ +(w_{3}-w_{4})-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{3}>w_{4}>w_{1}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{4}) -(w_{1}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{3}>w_{4}>w_{1}>w_{2}. \end {array}\right . \end {array}\right .\)

  16. 16.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{4}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{1}>w_{4}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{1}>w_{4}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{4}>w_{3}>w_{2}. \end {array}\right . \end {array}\right .\)

  17. 17.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{4}>w_{1}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{4}>w_{1}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{4}>w_{1}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{4}>w_{1}>w_{3}>w_{2}. \end {array}\right . \end {array}\right .\)

  18. 18.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{4}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{2}^{\max \limits }-1}(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t \\ w_{1}>w_{4}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~t_{1}^{\max \limits }<t&\\ w_{1}>w_{4}>w_{3}>w_{2} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{3}-w_{2})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{4}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{4}>w_{3}>w_{2}. \end {array}\right . \end {array}\right .\)

  19. 19.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{4}>w_{2}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2} -w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t&\\ w_{1}>w_{4}>w_{2}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{2}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t,~ t_{1}^{\max \limits }<t&\\ w_{1}>w_{4}>w_{2}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{1}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{4}>w_{2}>w_{3}. \end {array}\right . \end {array}\right .\)

  20. 20.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{1}>w_{2}>w_{4}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}),& \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{1}>w_{2}>w_{4}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{2}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t ,~t_{1}^{\max \limits }<t&\\ w_{1}>w_{2}>w_{4}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{1}),& \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{1}>w_{2}>w_{4}>w_{3}. \end {array}\right . \end {array}\right .\)

  21. 21.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{4}>w_{1}>w_{2}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(\frac {1}{2})^{t-t_{2}-1}(w_{2}-w_{3}),& \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{4}>w_{1}>w_{2}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{3})\\ -(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{1}-w_{2})-(w_{2}-w_{3}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t ,~t_{1}^{\max \limits }<t&\\ w_{4}>w_{1}>w_{2}>w_{3} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}+(w_{4}-w_{1}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{4}>w_{1}>w_{2}>w_{3}. \end {array}\right . \end {array}\right .\)

  22. 22.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}) \\ -(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{2}>w_{1}>w_{3}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}) \\ -(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{2}>w_{1}>w_{3}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(w_{2}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t ,~t_{1}^{\max \limits }<t&\\ w_{2}>w_{1}>w_{3}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(w_{2}-w_{1})-(w_{2}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{2}>w_{1}>w_{3}>w_{4}. \end {array}\right . \end {array}\right .\)

  23. 23.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}) \\ -(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{2}>w_{3}>w_{1}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}) \\ -(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{2}>w_{3}>w_{1}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(w_{2}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t ,~t_{1}^{\max \limits }<t&\\ w_{2}>w_{3}>w_{1}>w_{4} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(w_{2}-w_{1})-(w_{2}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{2}>w_{3}>w_{1}>w_{4}. \end {array}\right . \end {array}\right .\)

  24. 24.

    \(\left \{\begin {array}{ll} (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}) \\ -(\frac {1}{2})^{t-t_{3}^{\max \limits }-1}(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }<t\\ w_{2}>w_{3}>w_{4}>w_{1} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t^{\max \limits }_{2}-1}(w_{2}-w_{3}) \\ -(w_{3}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t,~t_{2}^{\max \limits }<t &\\ w_{2}>w_{3}>w_{4}>w_{1} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(\frac {1}{2})^{t-t_{1}^{\max \limits }-1}(w_{2}-w_{1})-(w_{2}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t ,~t_{1}^{\max \limits }<t&\\ w_{2}>w_{3}>w_{4}>w_{1} \end {array}\right .\\ (\frac {1}{2})^{t-1}w_{1}-(w_{2}-w_{1})-(w_{2}-w_{4}), & \left \{\begin {array}{ll} t_{3}^{\max \limits }=t_{2}^{\max \limits }=t_{1}^{\max \limits }=t\\ w_{2}>w_{3}>w_{4}>w_{1}. \end {array}\right . \end {array}\right .\)

Proof

Now, we are ready to prove the theorem by considering first two cases independently and the remaining cases can be proved by major classes as explained above.

Case 1: Since w4 > w3 > w2 > w1, we prove that m4 > m3 > m2 > m1 holds, then its generator matrix G of the code C can be written as G = (G1,G2,G3,G4), where G1 consists of all points in PG(k − 1,2) with each point repeating m1 times and all the points in S2 ∪ S3 ∪ S4 constitute the columns of G2 with each point repeating m2 − m1 times. Columns of the generator matrix G3 consist of all points of S3 and each point repeats m3 − m2 times and columns of the generator matrix G4 include of all points of S4 and each point repeats m4 − m3 times. Then, G1 generates a k-dimensional constant-weight code \(C^{\prime }\) with weight m12k− 1 and length l1 = m1(2k − 1), G2 generates a (k − k1)-dimensional weight code \(C^{\prime \prime }\) with weight \((m_{2}-m_{1})2^{k-k_{1}-1}\) and length \(l_{2}=(m_{2}-m_{1})(2^{k-k_{1}}-1)\), G3 generates a (k − k2)-dimensional weight code \(C^{\prime \prime \prime }\) with weight \((m_{3}-m_{2})2^{k-k_{2}-1}\) and length \(l_{3}=(m_{3}-m_{2})(2^{k-k_{2}}-1)\) and G4 generates a (k − k3)-dimensional weight code \(C^{\prime \prime \prime \prime }\) with weight \((m_{4}-m_{3})2^{k-k_{3}-1}\) and length \(l_{4}=(m_{4}-m_{3})(2^{k-k_{3}}-1)\). Let c1,⋯ ,ct be any t linearly independent codewords in C such that

\(\begin {pmatrix} c_{1}\\ \vdots \\ c_{t}\\ \end {pmatrix}=X_{t\times k}G\), \(\begin {pmatrix} c_{1}^{\prime }\\ \vdots \\ c_{t}^{\prime }\\ \end {pmatrix}=X_{t\times k}G_{1}\), \(\begin {pmatrix} c_{1}^{\prime \prime }\\ \vdots \\ c_{t}^{\prime \prime }\\ \end {pmatrix}=X_{t\times k}G_{2}\), \(\begin {pmatrix} c_{1}^{\prime \prime \prime }\\ \vdots \\ c_{t}^{\prime \prime \prime }\\ \end {pmatrix}=X_{t\times k}G_{3}\) and \(\begin {pmatrix} c_{1}^{\prime \prime \prime \prime }\\ \vdots \\ c_{t}^{\prime \prime \prime \prime }\\ \end {pmatrix}=X_{t\times k}G_{4}\). It can be concluded that each above codeword ci(i = 1,2,⋯ ,t) can be divided into four sectors. That is, \(c_{i}=(c_{i}^{\prime },c_{i}^{\prime \prime },c_{i}^{\prime \prime \prime },c_{i}^{\prime \prime \prime \prime })\) with \(c_{i}^{\prime }\in C^{\prime }\), \(c_{i}^{\prime \prime }\in C^{\prime \prime }\), \(c_{i}^{\prime \prime \prime }\in C^{\prime \prime \prime }\) and \(c_{i}^{\prime \prime \prime \prime }\in C^{\prime \prime \prime \prime }.\) Obviously, the codewords \(c_{1}^{\prime },\cdots ,c_{t}^{\prime }\) are linearly independent. Moreover based on Lemma 4.2, the rank of the codewords \(c_{1}^{\prime \prime },\cdots , c_{t}^{\prime \prime }\), \(c_{1}^{\prime \prime \prime },\cdots ,c_{t}^{\prime \prime \prime }\) and \(c_{1}^{\prime \prime \prime \prime },\cdots ,c_{t}^{\prime \prime \prime \prime }\) are (t − t1), (t − t2) and (t − t3), respectively. From Lemma 4.1, we conclude that \(inter_{1}=(\frac {1}{2})^{t-1}m_{1}2^{k-1}\), \(0\leq inter_{2}\leq (\frac {1}{2})^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}\), \(0\leq inter_{3}\leq (\frac {1}{2})^{t-t_{2}-1}(m_{3}-m_{2})2^{k-k_{2}-1}\) and \(0\leq inter_{4}\leq (\frac {1}{2})^{t-t_{3}-1}(m_{4}-m_{3})2^{k-k_{3}-1}.\) Therefore, inter = inter1 + inter2 + inter3 + inter4. Thus, \(inter=(\frac {1}{2})^{t-1}m_{1}2^{k-1}\) is reachable, whenever \(c_{1}^{\prime \prime }=0\), \(c_{1}^{\prime \prime \prime }=0\) and \(c_{1}^{\prime \prime \prime \prime }=0\) are equivalent to c1 ∈ C1, c1 ∈ C2 and c1 ∈ C3, respectively. Since dim(C1) ≥ 1, we can select an arbitrary non-zero codeword c1 from C1 and expand it to t linearly independent codewords c1,⋯ ,ct in C. Therefore, the t-wise intersection of binary relative four-weight code is \((\frac {1}{2})^{t-1}m_{1}2^{k-1}=(\frac {1}{2})^{t-1}w_{1}\).

Case 2: If w1 > w2 > w3 > w4 then m1 > m2 > m3 > m4, similar to the analysis in Case 1, these matrices G1, G2, G3 and G4 can be introduced. G4 = (G,G1,G2,G3) and G1 includes all the points in S2 ∪ S3 ∪ S4, which constitute the columns of G1 with each point repeating m1 − m2 times and the columns of G2 consist of all points of S3 with each point repeating m2 − m3 times. Columns of the generator matrix G3 consist of all points of S4 and each point repeats m3 − m4 times and columns of the generator matrix G4 consist of all points in PG(k − 1,2) with each point repeating m1 times. Then, G1 generates a (k − k1)-dimensional constant-weight code \(C^{\prime }\) with weight \((m_{1}-m_{2})2^{k-k_{1}-1}\) and length \(l_{1}=(m_{1}-m_{2})(2^{k-k_{1}}-1)\), G2 generates a (k − k2)-dimensional weight code \(C^{\prime \prime }\) with weight \((m_{2}-m_{3})2^{k-k_{2}-1}\) and length \(l_{2}=(m_{2}-m_{3})(2^{k-k_{2}}-1)\), G3 generates a (k − k3)-dimensional weight code \(C^{\prime \prime \prime }\) with weight \((m_{3}-m_{4})2^{k-k_{3}-1}\) and length \(l_{3}=(m_{3}-m_{4})(2^{k-k_{3}}-1)\) and G4 generates a k-dimensional weight code \(C^{\prime \prime \prime \prime }\) with weight m12k− 1 and length l4 = m1(2k − 1). Let ci be an arbitrary codeword of the t linearly independent codewords c1,⋯ ,ct ∈ C with the matrix form \(\begin {pmatrix} c_{1}\\ \vdots \\ c_{t}\\ \end {pmatrix}=X_{t\times k}G\). Then, we have \(c_{i}^{\prime \prime \prime \prime }=(c_{i},c_{i}^{\prime },c_{i}^{\prime \prime },c_{i}^{\prime \prime \prime })\) for any i ∈{1,2,⋯ ,t} with \(c_{i}^{\prime }\in C^{\prime }\), \(c_{i}^{\prime \prime }\in C^{\prime \prime }\), \(c_{i}^{\prime \prime \prime }\in C^{\prime \prime \prime }\) and \(c_{i}^{\prime \prime \prime \prime }\in C^{\prime \prime \prime \prime }\). Besides \(rank(c_{1}^{\prime \prime \prime \prime },\cdots ,c_{t}^{\prime \prime \prime \prime })=t\), whereas \(rank(c_{1}^{\prime },\cdots ,c_{t}^{\prime })=t-t_{1}\), \(rank(c_{1}^{\prime \prime },\cdots ,c_{t}^{\prime \prime })=t-t_{2}\) and \(rank(c_{1}^{\prime \prime \prime },\cdots ,c_{t}^{\prime \prime \prime })=t-t_{3}\) by Lemma 4.2. Furthermore, inter = inter4 − inter1 − inter2 − inter3 with \(0\leq inter_{1}\leq (\frac {1}{2})^{t-t_{1}-1}(m_{1}-m_{2})2^{k-k_{1}-1}\), \(0\leq inter_{2}\leq (\frac {1}{2})^{t-t_{2}-1}(m_{2}-m_{3})2^{k-k_{2}-1}\), \(0\leq inter_{3}\leq (\frac {1}{2})^{t-t_{3}-1}(m_{3}-m_{4})2^{k-k_{3}-1}\) and \(inter_{4}=(\frac {1}{2})^{t-1}m_{1}2^{k-1}\), by Lemma 4.1.

Next, we state that

$$ \begin{array}{@{}rcl@{}} inter &=&\left( \frac{1}{2}\right)^{t-1}m_{1}2^{k-1} - \left( \frac{1}{2}\right)^{t-t_{1}-1}(m_{1} - m_{2})2^{k-k_{1}-1} - \left( \frac{1}{2}\right)^{t-t_{2}-1}(m_{2} - m_{3})2^{k-k_{2}-1}\\ &&-\left( \frac{1}{2}\right)^{t-t_{3}-1}(m_{3}-m_{4})2^{k-k_{3}-1}\\ \end{array} $$

can reachable when < c1,c2,⋯ ,ct > is a relative (t,t1,t2,t3) subcode (t1 ≤ t2 < t3 < t). Let c1,⋯ ,ct be arbitrary t linearly independent codewords and < c1,⋯ ,ct > is a relative (t,t1,t2,t3) subcode of C. According to the proof of Lemma 2.3, there exists an invertible matrix Yt×t, Zt×t and Wt×t such that

$$ \begin{array}{@{}rcl@{}} W_{t\times t}Z_{t\times t}Y_{t\times t}X_{t\times k}&=& \begin{bmatrix} X^{\prime\prime\prime\prime}_{t_{1}\times k_{3}} & X^{\prime\prime\prime\prime}_{t_{1}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{t_{1}\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{t_{1}\times (k-k_{3})} \\ X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times k_{1}} & X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{(t_{2}-t_{1})\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times (k-k_{3})} \\ X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times k_{1}} & X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{(t_{3}-t_{2})\times (k-k_{3})}\\ X^{\prime\prime\prime}_{{(t-t_{3})}\times k_{1}} & X^{\prime\prime\prime}_{{(t-t_{3})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime} _{(t-t_{3})\times (k_{3}-k_{2})} & X^{\prime\prime\prime}_{(t-t_{3})\times (k-k_{3})}\\ \end{bmatrix}, \end{array} $$

with each row of \(X^{\prime \prime \prime \prime }_{t_{1}\times (k-k_{3})}\), \(X^{\prime \prime \prime \prime }_{{(t_{2}-t_{1})}\times (k-k_{3})}\) and \(X^{\prime \prime \prime \prime }_{(t_{3}-t_{2})\times (k-k_{3})}\) is the same as the last row of \(X^{\prime \prime \prime }_{(t-t_{3})\times (k-k_{3})}\). Similarly with each row of \(X^{\prime \prime \prime \prime }_{t_{1}\times (k_{3}-k_{2})}\) and \(X^{\prime \prime \prime \prime }_{({t_{2}-t_{1})}\times (k_{3}-k_{2})}\) is the same as the last row of \(X^{\prime \prime \prime \prime }_{{(t-t_{3})}\times (k_{3}-k_{2})}\). Denote c1,⋯ ,ct the rows of matrix Wt×tZt×tYt×tXt×kG. Then, we conclude that these t linearly independent codewords have the intersection

$$ \begin{array}{@{}rcl@{}} inter&=&inter_{4}-inter_{1}-inter_{2}-inter_{3}\\ &=&\left( \frac{1}{2}\right)^{t-1}m_{1}2^{k-1} - \left( \frac{1}{2}\right)^{t-t_{1}-1}(m_{1} - m_{2})2^{k-k_{1}-1} - \left( \frac{1}{2}\right)^{t-t_{2}-1}(m_{2} - m_{3})2^{k-k_{2}-1}\\&&-\left( \frac{1}{2}\right)^{t-t_{3}-1}(m_{3}-m_{4})2^{k-k_{3}-1}\\ &=&\left( \frac{1}{2}\right)^{t-1}w_{1}-\left( \frac{1}{2}\right)^{t-t_{1}-1}(w_{1}-w_{2})-\left( \frac{1}{2}\right)^{t-t_{2}-1}(w_{2}-w_{3})-\left( \frac{1}{2}\right)^{t-t_{3}-1}(w_{3}-w_{4}).\\ \end{array} $$

Thus, for all parameters t1, t2 and t3, we get the t-wise intersection of binary relative four-weight codes in the case w1 > w2 > w3 > w4,

$$ \begin{array}{@{}rcl@{}} \min_{t_{1},t_{2},t_{3}} inter= \left\{\begin{array}{ll} (\frac{1}{2})^{t-1}w_{1}- (\frac{1}{2})^{t-t_{1}-1}(w_{1}-w_{2})-(\frac{1}{2})^{t-t_{2}-1}(w_{2}-w_{3})\\ -(\frac{1}{2})^{t-t_{3}-1}(w_{3}-w_{4}), & \text{if }t_{3}^{\max}<t\\ (\frac{1}{2})^{t-1}w_{1}- (\frac{1}{2})^{t-t_{1}-1}(w_{1}-w_{2})-(\frac{1}{2})^{t-t_{2}-1}(w_{2}-w_{3})\\ -(w_{3}-w_{4}), & \text{if } t_{3}^{\max}=t \text{ and } t_{2}^{\max}<t\\ (\frac{1}{2})^{t-1}w_{1}- (\frac{1}{2})^{t-t_{1}-1}(w_{1}-w_{2})-(w_{2}-w_{3})\\ -(w_{3}-w_{4}), & \text{if }t_{3}^{\max}= t_{2}^{\max}=t \text{ and } t_{1}^{\max}<t\\ (\frac{1}{2})^{t-1}w_{1}- (w_{1}-w_{4}) ,& \text{if } t_{3}^{\max}= t_{2}^{\max}= t_{1}^{\max}=t. \end{array}\right. \end{array} $$

Hereafter, we have to prove the major classes one by one which consist of all the remaining cases.

Major class 1: In this major class, it can be considered that all the five cases (3, 4, 5, 6 and 7) have similar proof. Although the cases seem to be different, the condition will be same that is m1 < m2, m2 > m3 and m3 < m4. Using the first key lemma stated in the Appendix and the procedure adopted in Case 2, we can estimate the intersection of the relative (t,t1,t2,t3)(t1 < t2 ≤ t3 < t) subcode,

$$ \begin{array}{@{}rcl@{}} inter &=&\left( \frac{1}{2}\right)^{t-1}m_{1}2^{k-1}+\left( \frac{1}{2}\right)^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}\\ &&-\left( \frac{1}{2}\right)^{t-t_{2}-1}(m_{2}-m_{3})2^{k-k_{2}-1}-\left( \frac{1}{2}\right)^{t-t_{3}-1}(m_{4}-m_{3})2^{k-k_{3}-1}.\\ \end{array} $$

According to Lemma 1.1 in the Appendix, for any t linearly independent codewords with property that their generating subspace is relative (t1,t2,t3) subcode of C, if the corresponding inter4≠ 0, we have, inter = inter1 + inter2 − inter3 − inter4, with the \(inter_{1}=(\frac {1}{2})^{t-1}m_{1}\), \(inter_{2}=(\frac {1}{2})^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}\) and \(inter_{3}=(\frac {1}{2})^{t-t_{2}-1}(m_{3}-m_{2})2^{k-k_{2}-1}.\) When \(inter_{4}=(\frac {1}{2})^{t-t_{3}-1}(m_{4}-m_{3})2^{k-k_{3}-1}\) is reachable, inter will have its minimum value.

For any given t codewords with the aforementioned properties, there exists three invertible matrices Yt×t, Zt×t and Wt×t such that

$$ \begin{array}{@{}rcl@{}} W_{t\times t}Z_{t\times t}Y_{t\times t}X_{t\times k}&=& \begin{bmatrix} X^{\prime\prime\prime\prime}_{t_{1}\times k_{3}} & X^{\prime\prime\prime\prime}_{t_{1}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{t_{1}\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{t_{1}\times (k-k_{3})} \\ X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times k_{1}} & X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{(t_{2}-t_{1})\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times (k-k_{3})} \\ X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times k_{1}} & X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{(t_{3}-t_{2})\times (k-k_{3})}\\ X^{\prime\prime\prime}_{{(t-t_{3})}\times k_{1}} & X^{\prime\prime\prime}_{{(t-t_{3})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime} _{(t-t_{3})\times (k_{3}-k_{2})} & X^{\prime\prime\prime}_{(t-t_{3})\times (k-k_{3})}\\ \end{bmatrix}, \end{array} $$

where each row of \(X^{\prime \prime \prime \prime }_{t_{1}\times (k-k_{3})}\), \(X^{\prime \prime \prime \prime }_{(t_{2}-t_{1})\times (k-k_{3})}\) and \(X^{\prime \prime \prime \prime }_{(t_{3}-t_{2})\times (k-k_{3})}\) is equal to the last row of the matrix \(X^{\prime \prime \prime }_{(t-t_{3})\times (k-k_{3})}\) and each rows of \(X^{\prime \prime \prime \prime }_{t_{1}\times (k_{3}-k_{2})}\), \(X^{\prime \prime \prime \prime }_{(t_{2}-t_{1})\times (k_{3}-k_{2})}\) and \(X^{\prime \prime \prime \prime }_{(t_{3}-t_{2})\times (k_{3}-k_{2})}\) are the same as the last row of \(X^{\prime \prime \prime }_{(t-t_{3})\times (k_{3}-k_{2})}\). Thus, taking the rows of matrix Wt×tZt×tYt×tXt×kG to be new t linearly independent codewords and still denoting them by c1,⋯ ,ct, we can conclude that intersection, \(inter=(\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t_{2}-1}(w_{3}-w_{2})-(\frac {1}{2})^{t-t_{3}-1}(w_{4}-w_{3}).\)

In addition, if inter4 = 0, we will have inter = inter1 − inter2 + inter3 − inter4, with \(inter_{1}=(\frac {1}{2})^{t-1}m_{1}\), inter2 = 0 and inter3 = 0. Thus, the minimum value of inter is \((\frac {1}{2})^{t-1}m_{1}2^{k-k_{1}}\), when inter2 = inter3 = 0. Next, we state that inter2 = inter3 = 0 can be reached, since dim(C1) ≥ 1, we select t linearly independent codewords c1 ∈ C1, and expand to it t linearly independent codewords c1,⋯ ,ct. It can be checked that inter2 = inter3 = 0. Thus, if inter4 = 0, the minimum intersection of t linearly independent codewords will be \(inter=(\frac {1}{2})^{t-1}m_{1}2^{k-1}.\) Summarizing the above discussion, we conclude that all t linearly independent codewords (c1,c2,⋯ ,ct) with t1 < t2 ≤ t3 < t subcodes of C will have minimum intersection

$$ \begin{array}{@{}rcl@{}} inter&=&\min\left\{\left( \frac{1}{2}\right)^{t-1}m_{1}2^{k-1}+\left( \frac{1}{2}\right)^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}-\left( \frac{1}{2}\right)^{t-t_{2}-1}(m_{2}-m_{3})2^{k-k_{2}-1}\right.\\ &&\left.-\left( \frac{1}{2}\right)^{t-t_{3}-1}(m_{4}-m_{3})2^{k-k_{3}-1};\left( \frac{1}{2}\right)^{t-1}m_{1}2^{k-1}\right\}\\ &=&\left\{\left( \frac{1}{2}\right)^{t-1}w_{1}+\left( \frac{1}{2}\right)^{t-t_{1}-1}(w_{2}-w_{1})-\left( \frac{1}{2}\right)^{t-t_{2}-1}(w_{2}-w_{3})\right.\\ &&\left.-\left( \frac{1}{2}\right)^{t-t_{3}-1}(w_{4}-w_{3});\left( \frac{1}{2}\right)^{t-1}w_{1}\right\}.\\ \end{array} $$

Therefore, the t-wise intersection of binary relative four-weight codes, for m1 < m2, m2 > m3 and m3 < m4, is

$$ \begin{array}{@{}rcl@{}} \min\limits_{t_{1},t_{2},t_{3}} inter= \left\{\begin{array}{ll} \{(\frac{1}{2})^{t-1}w_{1}- (\frac{1}{2})^{t-t^{\max}_{3}-1}(w_{4}-w_{3});~(\frac{1}{2})^{t-1}w_{1}\} ,& \text{if } t_{3}^{\max}<t\\ \{(\frac{1}{2})^{t-1}w_{1}- ((w_{4}-w_{3});~(\frac{1}{2})^{t-1}w_{1}\} ,& \text{if } t_{3}^{\max}=t. \end{array}\right. \end{array} $$

Major class 2: In this the cases 8, 9 and 10 are considered. Since the condition m1 < m2, m2 < m3 and m3 > m4 is same for all the three cases, we will get similar result as in Case 2. Following the second key lemma in the A, the intersection will be

$$ \begin{array}{@{}rcl@{}} inter &=&\left( \frac{1}{2}\right)^{t-1}m_{1}2^{k-1}+\left( \frac{1}{2}\right)^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}\\ &&-\left( \frac{1}{2}\right)^{t-t_{2}-1}(m_{3}-m_{2})2^{k-k_{2}-1}-\left( \frac{1}{2}\right)^{t-t_{3}-1}(m_{3}-m_{4})2^{k-k_{3}-1}.\\ \end{array} $$

Next, it is stated that the equations inter4 = 0, \(inter_{3}=(\frac {1}{2})^{t-t_{2}-1}(m_{3}-m_{2})2^{k-k_{2}-1}\) and \(inter_{2}=(\frac {1}{2})^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}\) are reachable whenever < c1,c2,⋯ ,ct > is a relative (t,t1,t2,t3)(t1 < t2 < t3 ≤ t) subcode. Any t linearly independent codewords, < c1,⋯ ,ct > is a relative (t,t1,t2,t3) subcode of C. So that we can always find that there are invertible matrices Yt×t, Zt×t and Wt×t, such as,

$$ \begin{array}{@{}rcl@{}} W_{t\times t}Z_{t\times t}Y_{t\times t}X_{t\times k}&=& \begin{bmatrix} X^{\prime\prime\prime\prime}_{t_{1}\times k_{3}} & X^{\prime\prime\prime\prime}_{t_{1}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{t_{1}\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{t_{1}\times (k-k_{3})} \\ X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times k_{1}} & X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{(t_{2}-t_{1})\times (k_{3}-k_{2})} & X^{\prime\prime\prime\prime}_{{(t_{2}-t_{1})}\times (k-k_{3})} \\ X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times k_{1}} & X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime\prime}_{{(t_{3}-t_{2})}\times (k_{3}-k_{2})} & 0_{(t_{3}-t_{2})\times (k-k_{3})}\\ X^{\prime\prime\prime}_{{(t-t_{3})}\times k_{1}} & X^{\prime\prime\prime}_{{(t-t_{3})}\times (k_{2}-k_{1})} & X^{\prime\prime\prime} _{(t-t_{3})\times (k_{3}-k_{2})} & X^{\prime\prime\prime}_{(t-t_{3})\times (k-k_{3})}\\ \end{bmatrix}, \end{array} $$

where each row of \(X^{\prime \prime \prime \prime }_{t_{1}\times (k-k_{3})}\) and \(X^{\prime \prime \prime \prime }_{(t_{2}-t_{1})\times (k_{3}-k_{2})}\) is equal to the last row of the matrix \(X^{\prime \prime \prime }_{(t-t_{3})\times (k-k_{3})}\) and each row of \(X^{\prime \prime \prime \prime }_{t_{1}\times (k_{3}-k_{2})}\) and \(X^{\prime \prime \prime \prime }_{(t_{2}-t_{1})\times (k_{3}-k_{2})}\) is the same as the last row of \(X^{\prime \prime \prime }_{(t-t_{3})\times (k_{3}-k_{2})}\). Then, considering the rows of matrix Wt×tZt×tYt×tXt×kG a new t linearly independent codewords but still denoting them by c1,⋯ ,ct, we can infer that inter4 = 0, \(inter_{1}=(\frac {1}{2})^{t-1}m_{1}2^{k-1}\), \(inter_{2}=(\frac {1}{2})^{t-t_{1}-1}(m_{2}-m_{1})2^{k-k_{1}-1}\) and \(inter_{3}=(\frac {1}{2})^{t-t_{2}-1}(m_{3}-m_{2})2^{k-k_{2}-1}.\) Hence, all the t linearly independent codewords of which generating subspaces are relative (t,t1,t2,t3)(t1 < t2 < t3 ≤ t) subcodes, have the minimum intersection \(inter=(\frac {1}{2})^{t-1}w_{1}+(\frac {1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(\frac {1}{2})^{t-t_{2}-1}(w_{3}-w_{2}).\) Therefore, the t-wise intersection of binary relative four- weight codes in major class 2 is

$$ \begin{array}{@{}rcl@{}} \min\limits_{t_{1},t_{2},t_{3}} inter= \left\{\begin{array}{ll} (\frac{1}{2})^{t-1}w_{1}+ (\frac{1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(\frac{1}{2})^{t-t_{2}-1}(w_{3}-w_{2}), & \text{if } t_{2}^{\max}<t \text{ and } t_{1}^{\max}<t\\ (\frac{1}{2})^{t-1}w_{1}+ (\frac{1}{2})^{t-t_{1}-1}(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text{if } t_{2}^{\max}=t \text{ and } t_{1}^{\max}<t\\ (\frac{1}{2})^{t-1}w_{1} +(w_{2}-w_{1})-(w_{3}-w_{2}) ,& \text{if } t_{2}^{\max}=t_{1}^{\max}=t. \end{array}\right. \end{array} $$

Similar to this, by using the corresponding key lemmas stated in the Appendix, we can also prove the major classes 3, 4, 5 and 6 in the same method so, we omit the detailed proof. □

Remark 4.4

While generalizing the above theorem for any q > 2, we may also obtain the t-wise intersection of any q-ary relative four-weight code for cases 1, 2 and major class 2. For major class 1, it is more complicated to generalize the t-wise intersection of q-ary (q > 2)code, since we are not able to arrive a similar result as in Lemma 1.1 (Refer to the Appendix) which can be used to prove that major class.

5 The trellis of relative four-weight codes

A trellis of a k-dimensional block code C is a directed graph. The set of nodes (or called states) of the graph can be partitioned into subsets S0 = {S0},S1,...,Sn− 1, Sn = {Sn}. An edge from a state in Si− 1 terminates at a state in Si,1 ≤ i ≤ n. For binary codes, each edge is labeled by 0 or 1, such that C is the set of edge label sequences obtained by traversing all paths from S0 to Sn. For a linear code, each Si is a vector space.

Given a trellis of the code, the maximum-likelihood soft-decision decoding is achieved by applying the well-known Viterbi algorithm. The complexity of this decoding is determined by the trellis complexity.

Define

$$ s^{*}(C)=\max\limits_{0\leq i\leq n}dim\{S_{i}\} $$
(5.1)

and

$$ s(C)=\min\limits_{\pi}S^{*}\{\pi(C)\}, $$
(5.2)

where the minimization is performed over all permutations π acting on the coordinate positions of C.

Let Si,0 be the state in Si that corresponds to all zero path from S0. Then, the sets of label sequences associated with the sets of paths from S0 to Si,0 and from Si,0 to Sn, are called the past subcode \(C_{p}^{(i)}\) and the future subcode \(C_{f}^{(i)}\), respectively.

It is mandatory to recall χ(c) stands for support of the codeword c in other words, the set of the non-zero co-ordinate positions of c, whereas {1,⋯ ,n} the set of the coordinate positions and i− = {1,...,i}, i+ = {i + 1,...,n} for 1 ≤ i ≤ n are well known. Using these notations, we may also describe \(C_{p}^{(i)}\) and \(C_{f}^{(i)}\) as follows:

$$ \begin{array}{@{}rcl@{}} \left.\begin{aligned} C_{p}^{(i)}&=&\{c\in C,\chi(c)\subseteq i^{-}\}\\ C_{f}^{(i)}&=&\{c\in C,\chi(c)\subseteq i^{+}\} \end{aligned} \right\} \end{array} $$
(5.3)

Note that

$$ dim(S_{i}) = k - dim(C_{p}^{(i)})-dim(C_{f}^{(i)}). $$
(5.4)

The following lemma is a relation between trellis complexity and intersection of binary relative four-weight codes.

Lemma 5.1

Let C be a binary relative four-weight code. If the intersection of any two non-zero codewords is at least three, then s(C) ≥ k − 2.

Proof

We prove this lemma by contradiction. Suppose s(C) ≤ k − 3.

Then, according to the definition of (5.1) and (5.2), there exists a permutation π0 of a co-ordinate position of the code C such that s(C) = s∗(π0(C)) ≤ k − 3. Thus, for any co-ordinate position 1 ≤ i ≤ n, by using the (5.4), we have

$$ \begin{array}{@{}rcl@{}} dim(\pi_{0}(C_{p})^{(i)})+dim(\pi_{0}(C_{f})^{(i)})\geq 3. \end{array} $$
(5.5)

If there exists some i such that dim(π0(Cp)(i)) > 0 and dim(π0(Cf)(i)) > 0, then there are non-zero codewords c1 ∈ π0(Cp)(i), c2 ∈ π0(Cf)(i) and, they have no intersection by (5.3). This contradiction shows that C is intersecting. This implies that dim(π0(Cp)(i)) > 0 and dim(π0(Cf)(i)) > 0 are not possible. Hence, only one of the following can occur.

  1. 1.

    If dim(π0(Cp)(i)) = 0, then dim(π0(Cf)(i)) > 0.

  2. 2.

    If dim(π0(Cp)(i)) > 0, then dim(π0(Cf)(i)) = 0.

The above facts yield that C is a mimimum code with a distance d. We can find i0 > d − 1 such that dim(π0(Cp)(d− 1)) = 0 and dim(π0(Cf)(d− 1)) > 0 or dim(π0(Cp)(n−d+ 1)) > 0 and dim(π0(Cf)(n−d+ 1)) = 0.

We state that \(dim(\pi _{0}(C_{p})^{(i_{0}+1)})=1.\) Otherwise there exists two linearly independent codewords c1 and c2 such that \(c_{1},c_{2}\in \pi _{0}(C_{p})^{(i_{0}+1)}. \) Thus, we can find non-zero codewords c1 and c2 intersect exactly at the (i0 + 1)th co-ordinate position due to \(dim(\pi _{0}(C_{p})^{(i_{0})})=0.\) We can thus find a non-zero element α ∈GF(q) such that \(0\neq c_{1}+\alpha c_{2}\in \pi _{0}(C_{p})^{(i_{0})},\) which is a contradiction to \(dim(\pi _{0}(C_{p})^{(i_{0})})=0.\) This argument shows that \(dim(\pi _{0}(C_{p})^{(i_{0}+1)})=1.\)

Finally, we get

$$ \begin{array}{@{}rcl@{}} s(C)&=&s^{*}(\pi_{0}(C))\\ &\geq &k-{dim(\pi_{0}(C_{p})^{(i_{0}+1)}+dim(\pi_{0}(C_{f})^{(i_{0}+1)})}\\ &=&k-2. \end{array} $$

Which is a contradiction to s(C) ≤ k − 3. □