IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. XX, NO. Y, MONTH 1999 1

The Weight Hierarchy of Product Codes

Hans Georg Schaathun

The author is with Department of Informatics, University of Bergen, Norway. Email: ⟨georg@ii.uib.no⟩.

May 15, 2000 DRAFT

Abstract The weight of a code is the number of coordinate positions where no codeword is zero. The rth minimum weight d_{r} is

the least weight of an r-dimensional subcode. Wei and Yang gave a conjecture about the minimum weights for some product codes. In this paper we will find a relation between product codes and the Segre embedding of a pair of projective systems, and we use this to prove the conjecture.

Keywords

product code, projective system (projective multiset), weight hierarchy, Segre embedding

I. Introduction

An [n, k] code is a k-dimensional subspace C ⊆ 𝕍 of some n-dimensional vector space 𝕍. It can be defined by a k × n matrix G, called the generator matrix. The message space 𝕄 is a k-dimensional vector space, and G gives a linear transformation 𝕄 → 𝕍.

The rows of G is a basis for C. The columns can be viewed as linear forms, i.e. vectors in 𝕄^{∗}, the dual space of 𝕄. This means that if a = (a_{1}, … a_{k}) is the rth column in G, then a = a_{1}x_{1} + … + a_{k}x_{k} is a linear form. If m ∈ 𝕄 is a message word, then a(m) is the rth coordinate in the corresponding code word.

We can now see that a linear code may be described by either a basis or a system of linear forms. By a system we will in this paper mean a collection with possible repetition of elements. Codes are considered to be equivalent if one can be obtained from the other by permuting coordinate positions, multiplying certain coordinates by a non-zero scalar, or deleting zero positions. This corresponds to reordering the vector system, replacing linear forms by proportional forms, and deleting zero forms. We conclude that the linear forms may be represented by projective points, and in this case we talk about a projective system (or projective multiset [1]) rather than a vector system.

Given a projective system X ⊆ ℙ^{k−1}, the value ν(x) of x ∈ ℙ^{k−1} is the number of occurrences of x in X. This gives a map ν : ℙ^{k−1} → {0, 1, 2, …}, called the value assignment describing X. If S ⊆ ℙ^{k−1}, let ν(S) = ∑_{x∈S} ν(x).

The weight w(C) of a code C is the number of coordinate positions where some codeword is non-zero. The rth minimum weight d_{r}(C) is the least weight of an r-dimensional subcode. Clearly d_{0} = 0, and d_{1} = d is the usual minimum distance. The sequence (d_{1}, d_{2}, … d_{k}) is known as the weight hierarchy, and equivalent codes have the same weight hierarchy. Since every code is equivalent to a code without zero positions, we assume that d_{k} = n for all codes encountered.

The weight hierarchy (d_{1}, d_{2}, … d_{k}) is also defined for a projective system X ⊆ ℙ^{k−1} described by ν in that

d_{r} := ν(ℙ^{k−1}) − max{ν(Π) | Π ⊆ ℙ^{k−1}, codim Π = r}.

The correspondence between projective systems and linear codes preserves weight hierarchies [2], [3].

A product code A ⊗ B is the tensor product of two linear codes, A and B. The tensor product is generated by the vectors on the form

x ⊗ y := (x_{i}y_{j} | 1 ≤ i ≤ n, 1 ≤ j ≤ m),

where x = (x_{1}, … x_{n}) ∈ A and y = (y_{1}, … y_{m}) ∈ B. Since a linear form can be viewed as a vector, we will also write g ⊗ h for two linear forms g and h. When A and B are [n_{A}, k_{A}] and [n_{B}, k_{B}] linear codes, A ⊗ B is an [n_{A}n_{B}, k_{A}k_{B}] code.

The weight hierarchy has been studied by several researchers during the last decade, and there have been attempts to give a formula to express the weight hierarchy of a product code in terms of the weight hierarchies of the component codes. Wei and Yang [5] gave a conjecture for the weight hierarchy of chained codes.

Definition 1 (Chain Condition) A code C is chained if there is a chain of subcodes

{0} = D_{0} ⊆ D_{1} ⊆ … ⊆ D_{k} = C,

such that dim D_{r} = r and w(D_{r}) = d_{r} for all r.

Definition 2: Given two linear codes A and B, let

\begin{matrix}d_{r}^{∗}(A ⊗ B) = min \{ & ∑_{i=1}^{s}(d_{i}(A) − d_{i−1}(A))d_{t_{i}}(B)| \\ 1 ≤ t_{s} ≤ … ≤ t_{1} ≤ k_{B}, s ≤ k_{A}, ∑_{i=1}^{s} t_{i} = r\}. \end{matrix}

Wei and Yang conjectured that d_{r} = d_{r}^{∗} for the product of chained codes. Barbero and Tena [6] proved this for r ≤ 4. The main result of this paper is the following theorem, which implies the conjecture.

Theorem 1: For any two linear codes A and B, d_{r}(A ⊗ B) ≥ d_{r}^{∗}(A ⊗ B) for 0 ≤ r ≤ k_{A}k_{B}. If A and B are chained codes, then equality holds for all r.

II. Proof of the main result

We will prove Theorem 1 in terms of projective systems. Given two codes A and B, and the corresponding projective systems, we have to find the projective system corresponding to A ⊗ B. This will be the first step in the proof.

Lemma 1 (Basis lemma) If {x_{i} | i = 1, … k_{A}} and {y_{i} | i = 1, … k_{B}} are bases for A and B, then {x_{i} ⊗ y_{j} | 1 ≤ i ≤ k_{A}, 1 ≤ j ≤ k_{B}} is a basis for A ⊗ B.

This is a well-known fact, so we omit the proof. With regard to product codes, it basically says that we can form a generator matrix for A ⊗ B, by taking as rows all possible product x ⊗ y, where x is a row in a generator matrix of A, and y is a row in a generator matrix for B.

The following proposition says that we can equivalently form the generator matrix by taking products of columns.

Proposition 1: If A and B are linear codes defined by the vector systems Y_{A} and Y_{B}, then the vector system defining C := A ⊗ B is

Y_{C} = Y_{A} ⊙ Y_{B} := {x ⊗ y | x ∈ Y_{A}, y ∈ Y_{B}}.

Proof: For any vector x we write x[i] for its ith coordinate. Let {a_{i}} and {b_{j}} be bases for A and B respectively, and {c_{ij} = a_{i} ⊗ b_{j}} the induced basis for C. Let the code parameters be [n_{A}, k_{A}] for A, [n_{B}, k_{B}] for B, and [n_{C}, k_{C}] for C.

Now, a codeword c ∈ C is written as

c = ∑_{i=1}^{k_{A}} ∑_{j=1}^{k_{B}} m[i, j]c_{ij},

where m is a message word, i.e. a k_{C}-dimensional vector over the base field.

The coordinates are given as

\begin{aligned}c[a, b] & = ∑_{i=1}^{k_{A}} ∑_{j=1}^{k_{B}} m[i, j]c_{ij}[a, b] \\ & = ∑_{i=1}^{k_{A}} ∑_{j=1}^{k_{B}} m[i, j]a_{i}[a]b_{j}[b] = g_{ab}(m), \end{aligned}

where g_{ab} is a linear form in k_{C} variables. In fact g_{ab} = g_{a}^{A} ⊗ g_{b}^{B}, where g_{a}^{A} = ∑ a_{i}[a]x_{i} is the ath column of the generator matrix of A, and g_{b}^{B} = ∑ b_{i}[b]x_{i} the bth column of the generator matrix of B.

Corollary 1: If A and B are linear codes defined by the projective systems X_{A} and X_{B}, then C := A⊗B is defined by X_{C} = σ(X_{A}, X_{B}), where σ : ℙ^{k_{A}−1} × ℙ^{k_{B}−1} → ℙ^{k_{A}k_{B}−1} is the Segre embedding.

The Segre embedding is defined by (a, b) ↦ a ⊗ b, and it is well known that it is bijective on its image, which is called a Segre variety Y. In other words, a point c ∈ ℙ^{k_{A}k_{B}−1} can be decomposed as c = a ⊗ b, a ∈ ℙ^{k_{A}−1} and b ∈ ℙ^{k_{B}−1}, if and only if c ∈ Y. The decomposition is unique when it exists.

Corollary 2: Let ν_{A}, ν_{B}, and ν_{C} be the value assignments describing X_{A} ⊆ ℙ^{k_{A}−1}, X_{B} ⊆ ℙ^{k_{B}−1}, and X_{C} ⊆ ℙ^{k_{A}k_{B}−1} respectively. We have:

\begin{aligned}ν_{C}(a ⊗ b) & = ν_{A}(a) · ν_{B}(b), \\ & ∀a ∈ ℙ^{k_{A}−1}, ∀b ∈ ℙ^{k_{B}−1}, \end{aligned}  (1)
ν_{C}(c) = 0, ∀c ∉ Y.

We define the difference sequence of a linear code or projective system to be (δ_{0}, δ_{1}, … δ_{k−1}), where

δ_{i} := d_{k−i} − d_{k−i−1}.

We note that in the projective system corresponding to C, the maximum value of an r-space is

Δ_{r}(C) := ∑_{i=0}^{r} δ_{i}(C) = d_{k}(C) − d_{k−r−1}(C).  (2)

We reformulate the expression for d_{r}^{∗}. First we note that we can fix s = k_{A} and allow the t_{i} to be zero:

\begin{matrix}d_{r}^{∗}(A ⊗ B) = min \{ & ∑_{i=1}^{k_{A}}(d_{i}(A) − d_{i−1}(A))d_{t_{i}}(B)| \\ 0 ≤ t_{k_{A}} ≤ … ≤ t_{1} ≤ k_{B}, ∑_{i=1}^{k_{A}} t_{i} = r\}. \end{matrix}

Now we write

\begin{matrix}d_{r}^{∗}(A ⊗ B) = min \{ & ∑_{i=1}^{k_{A}} δ_{k_{A}−i}(A)(d_{k}(B) − ∑_{j=0}^{k_{B}−t_{i}−1} δ_{j}(B))| \\ 0 ≤ t_{k_{A}} ≤ … ≤ t_{1} ≤ k_{B}, ∑_{i=1}^{k_{A}} t_{i} = r\}, \end{matrix}

\begin{matrix}d_{r}^{∗}(A ⊗ B) = d_{k}(A)d_{k}(B) − max \{ & ∑_{i=1}^{k_{A}} δ_{k_{A}−i}(A) ∑_{j=0}^{k_{B}−t_{i}−1} δ_{j}(B)| \\ 0 ≤ t_{k_{A}} ≤ … ≤ t_{1} ≤ k_{B}, ∑_{i=1}^{k_{A}} t_{i} = r\}. \end{matrix}

We define Δ_{r}^{∗} from d_{r}^{∗}, just as Δ_{r} is defined from d_{r}:

Δ_{r}^{∗}(A ⊗ B) := d_{k}(A)d_{k}(B) − d_{k_{C}−r−1}^{∗}(A ⊗ B).  (3)

We get:

\begin{matrix}Δ_{r}^{∗}(A ⊗ B) = max \{ & ∑_{i=0}^{k_{A}−1} δ_{i}(A) ∑_{j=0}^{k_{B}−t′_{i}−1} δ_{j}(B)| \\ 0 ≤ t′_{0} ≤ … ≤ t′_{k_{A}−1} ≤ k_{B}, ∑_{i=0}^{k_{A}−1} t′_{i} = k_{C} − r − 1\}, \end{matrix}

where t′_{i} = t_{k_{A}−i}. We rearrange the expression to get:

\begin{matrix}Δ_{r}^{∗}(A ⊗ B) = max \{ & ∑_{i=0}^{k_{A}−1} δ_{i}(A)Δ_{t′′_{i}−1}(B)| \\ 0 ≤ t′′_{k_{A}−1} ≤ … ≤ t′′_{0} ≤ k_{B}, ∑_{i=0}^{k_{A}−1} t′′_{i} = r + 1\}, \end{matrix}  (4)

where t′′_{i} = k_{B} − t′_{i}. Note that Δ_{i} = 0 for i < 0, and Δ_{i}^{∗}(A ⊗ B) > Δ_{i−1}^{∗}(A ⊗ B) for 0 ≤ i ≤ k_{C} − 1. Lemma 2: For any two linear codes A and B, the following are equivalent for r′ = 0, 1, … k_{A}k_{B} − 1:

Δ_{r}(A ⊗ B) ≤ Δ_{r}^{∗}(A ⊗ B), r = r′,  (5)
d_{r}(A ⊗ B) ≥ d_{r}^{∗}(A ⊗ B), r = k_{A}k_{B} − r′ − 1.  (6)

Equality in (5) is equivalent with equality in (6).

Proof: This is obvious from the definitions in Equations (2) and (3).

Proof of Theorem 1: First we prove that Δ_{r}(A ⊗ B) ≤ Δ_{r}^{∗}(A ⊗ B) for r = 0, 1, …, k_{A}k_{B} − 1. We consider the projective systems X_{A} ⊆ ℙ^{k_{A}−1}, X_{B} ⊆ ℙ^{k_{B}−1}, and X_{C} := X_{A} ⊙ X_{B} ⊆ ℙ^{k_{A}k_{B}−1}

corresponding to the codes A, B, and C := A ⊗ B. Let ν_{A}, ν_{B}, and ν = ν_{C} be the corresponding value assignments.

Let Π ⊆ ℙ^{k_{A}k_{B}−1} be a subspace of dimension r and value ν(Π) = Δ_{r}(C). Choose p_{i} ∈ ℙ^{k_{A}−1} for 0 ≤ i ≤ k_{A} − 1 such that p_{i} is projectively independent of {p_{j} | j < i}, and maximising the dimension of the set of points in Π with p_{i} as the left hand factor, for 0 ≤ i < k_{A}. Note that for sufficiently large i, p_{i} may not occur as a factor of any point in Π.

Let T_{i} ⊆ ℙ^{k_{B}−1} be the largest set such that p_{i} ⊗ T_{i} ⊆ Π. Due to the bilinearity of the Segre embedding, the T_{i} are subspaces. Write t_{i} := dim lin T_{i} = dim T_{i} + 1, where dim lin denotes the linear dimension. By the definition of the p_{i}, we have t_{i} ≥ t_{i+1}. Let S_{i} ⊆ Π be the set of points whose first factor is in ⟨{p_{j} | 0 ≤ j ≤ i}⟩.

Clearly ν(S_{0}) = ν_{A}(p_{0})ν_{B}(T_{0}) ≤ δ_{0}(A)Δ_{t_{0}−1}(B) from Corollary 2 (1). Now look at 𝔖_{i} := S_{i}\S_{i−1} ⊆ Π. For any point a ⊗ b ∈ 𝔖_{i}, we have

a ∈ 𝔄_{i} := ⟨{p_{j} | 0 ≤ j ≤ i}⟩\⟨{p_{j} | 0 ≤ j ≤ i − 1}⟩.  (7)

Let R(a) ⊆ Π be the subspace of points with a as the left hand factor. Note that R(p_{i}) = p_{i} ⊗ T_{i}. For any a ∈ 𝔄_{i}, we have dim R(a) ≤ dim R(p_{i}) = t_{i} − 1, by the definition of the p_{i}. Therefore ν(R(a)) ≤ ν_{A}(a)Δ_{t_{i}−1}(B), and

ν(𝔖_{i}) = ∑_{a∈𝔄_{i}} ν(R(a)) ≤ ν_{A}(𝔄_{i})Δ_{t_{i}−1}(B).  (8)

Obviously

ν(Π) = ∑_{i=0}^{k_{A}−1} ν(𝔖_{i}) ≤ ∑_{i=0}^{k_{A}−1} ν_{A}(𝔄_{i})Δ_{t_{i}−1}(B).  (9)

Now consider the sum

τ := ∑_{i=0}^{k_{A}−1} t_{i} = ∑_{i=0}^{k_{A}−1} dim lin R(p_{i}).

All the R(p_{i}) are disjoint, so their join Π′ has linear dimension τ. Since Π′ ⊆ Π, we have τ ≤ dim lin Π = r + 1.

Note that the Δ_{t_{i}−1}(B) is monotonically non-increasing in i, and that

ν_{A}( ⋃_{j=0}^{i} 𝔄_{j}) ≤ Δ_{i}(A).

Hence the highest possible value is obtained if ν_{A}(𝔄_{i}) = δ_{i}(A), in which case the right hand side of (9) is one of the expressions eligible for the maximisation in the expression (4) for Δ_{τ−1}^{∗}. The t′′_{i} in (4) are given by the t_{i} in this proof. In other words

ν(Π) ≤ Δ_{τ−1}^{∗}(A ⊗ B) ≤ Δ_{r}^{∗}(A ⊗ B).

It remains to show that if A and B are chained codes, equality is obtained. In fact we know this from [5], because d_{r}^{∗} was proved to give an upper bound on d_{r}, but we give a direct proof for completeness.

Consider a set {t_{i} = t′′_{i}} attaining maximum in the definition of Δ_{r}^{∗}(A ⊗ B). Since A is chained, we can take a set {p_{i}} such that ν_{A}(⟨{p_{j} | j ≤ i}⟩) = Δ_{i}(A). Because B is chained, we can find sets T_{i} such that ν_{B}(T_{i}) = Δ_{t_{i}−1}, for 0 ≤ i ≤ k_{A} − 1, and T_{0} ⊇ T_{1} ⊇ … ⊇ T_{k_{A}−1}. Also let R(a) = a ⊗ T_{i} for all a ∈ 𝔄_{i}, as defined in Equation (7). We see that the join Π′ of all the R(p_{i}) has dimension dim Π′ = r := ∑_{i=0}^{k_{A}−1} t_{i}−1, where t_{i} := dim lin T_{i}. Since the T_{i} form a chain of inclusions, all R(a) ⊆ Π′ by the bilinearity of the Segre embedding.

Now we must find the value of Π′. By definition ν_{B}(T_{i}) = Δ_{t_{i}−1}(B), and ν_{A}(𝔄_{i}) = δ_{i}(A). Hence we have equality in (8) and ν(Π′) = Δ_{r}^{∗}(A ⊗ B) from (9).

III. Further results

Theorem 2: For any two codes A and B, d_{r}(A ⊗ B) = d_{r}^{∗}(A ⊗ B) for r ∈ {0, 1, 2, k − 2, k − 1, k}.

For r = 0 this is trivial, and for r = 1 and r = k it is well known. Wei and Yang [5] proved it for r = 2. We prove it for r = k − 1 and r = k − 2 below, but first we need some basic properties of the Segre variety.

A Segre variety Y is the intersection of hypersurfaces of degree two. Hence any line meeting Y in at least three points is entirely contained in Y.

Lemma 3: Let Y be a Segre variety, and let ℓ ⊆ ℙ^{k_{A}k_{B}−1} be a line. Then the line ℓ factors into a point ℘ in one component, and a line ℓ′ in the other component; that is ℓ = ℘ ⊗ ℓ′ or ℓ = ℓ′ ⊗ ℘.

The converse, that a product ℓ′ ⊗ ℘ or ℘ ⊗ ℓ′ is a line ℓ ∈ Y, is obviously true by bilinearity.

We believe that Lemma 3 is obvious from known results in algebraic geometry (e.g. [7, Example 8.4.2]). We include the following simple proof for the benefit of those who are not familiar with algebraic geometry.

Proof: Consider a line ℓ meeting Y in at least three distinct points, a ⊗ b, c ⊗ d, and e ⊗ f. If the component points are not distinct, say a = c, then we get a line, say a ⊗ ⟨b, d⟩ ⊆ Y, by bilinearity. Hence we assume that the six component points are distinct.

Consider the nine points

a ⊗ b, a ⊗ d, a ⊗ f, c ⊗ b, c ⊗ d, c ⊗ f, e ⊗ b, e ⊗ d, e ⊗ f.

They are all linearly independent, unless either a, c, and e, or b, d, and f are linearly dependent. By symmetry, we can assume without loss of generality that a, c, and e are collinear. It follows that any three points with the same right hand component must be linearly dependent, by bilinearity.

This gives three disjoint lines; all of which meets ℓ. The linear span of such a configuration can have dimension at most 4. If b, d, and f are linearly independent, the dimension is 5 by Lemma 1, since a and c are distinct. The contradiction shows that b, d, and f are collinear, and hence that any three points with the same first component are collinear.

Since all points with a common component are collinear, we can visualise them as a 3 × 3 grid of points. There is also a diagonal line in this grid, ℓ. It is easily verified that this configuration is contained in a plane, and hence any pair of lines intersect. The line with a as first component cannot intersect the line with c as first component unless a = c, so this is a contradiction.

Proof of Theorem 2: We prove that for two linear codes A and B

Δ_{0}(A ⊗ B) = Δ_{0}^{∗}(A ⊗ B) = δ_{0}(A)δ_{0}(B),  (10)
Δ_{1}(A ⊗ B) = Δ_{1}^{∗}(A ⊗ B).  (11)

We consider the projective systems X_{A} ⊆ ℙ^{k_{A}−1}, X_{B} ⊆ ℙ^{k_{B}−1}, and X_{C} ⊆ ℙ^{k_{A}k_{B}−1} corresponding to A, B, and C := A ⊗ B, and the describing value assignments ν_{A}, ν_{B}, and ν_{C}. Equation (10) is obvious from Corollary 2.

Now consider a line ℓ ⊆ ℙ^{k_{A}k_{B}−1} such that ν_{C}(ℓ) = Δ_{1}(C).

If ℓ meets the Segre variety in at most two points, we have

\begin{matrix}ν_{C}(ℓ) = Δ_{1}(C) \\ ≤ max\{δ_{0}(A)(δ_{0}(B) + δ′_{0}(B)), (δ_{0}(A) + δ′_{0}(A))δ_{0}(B)\}, \end{matrix}

where δ′_{0} is the second highest value of any point. Clearly δ′_{0} ≤ δ_{1}, so this gives

Δ_{1}(C) ≤ Δ_{r}^{∗}(A ⊗ B).

Otherwise ℓ is entirely contained in the Segre variety, and we can write ℓ = a ⊗ ℓ_{1} or ℓ = ℓ_{2} ⊗ b. Clearly the highest possible value in each case is obtained if ν_{A}(a) = δ_{0}(A), ν_{B}(b) = δ_{0}(B), ν_{A}(ℓ_{2}) = Δ_{1}(A), and ν_{B}(ℓ_{1}) = Δ_{1}(B). Then ν_{C}(a ⊗ ℓ_{1}) = δ_{0}(A)Δ_{1}(B) and ν_{C}(ℓ_{2} ⊗ b) = Δ_{1}(A)δ_{0}(B), and the maximum of these is Δ_{1}^{∗}(A ⊗ B). Equation (11) follows.

Corollary 3: For any product code A⊗B of dimension at most 5, d_{r}(A⊗B) = d_{r}^{∗}(A⊗B), 0 ≤ r ≤ k_{A}k_{B}. The following examples show that for a six-dimensional product code this may or may not hold for

r = 3 = k − 3.

Example 1: Consider the binary [4, 3] code A given by a value assignment ν_{A}. Let a ∈ ℙ^{2} be a point and ℓ_{A} ∌ a a line, such that the describing value assignment is given by ν_{A}(p) = 1 for p ∈ ℓ_{A} or p = a, and ν_{A}(p) = 0 otherwise. This is a chained code with difference sequence is (1, 2, 1).

Then take the binary [17, 3] code B given by a value assignment ν_{B}. Let b ∈ ℙ^{2} be a point and ℓ_{B} ∌ b a line, such that the describing value assignment is given by ν_{B}(b) = 5, ν_{B}(p) = 4 for p ∈ ℓ_{B}, and ν_{B}(p) = 0 otherwise. This is a non-chain code with difference sequence (5, 7, 5).

Now consider C := A ⊗ B. To find Δ_{2}^{∗}(C) we consider the possible choices for {t′′_{i}} in Equation (4):

{3, 0, 0} : δ_{0}(A)Δ_{2}(B) = 17
{2, 1, 0} : δ_{0}(A)Δ_{1}(B) + δ_{1}(A)Δ_{0}(B) = 22
{1, 1, 1} : Δ_{2}(A)Δ_{0}(B) = 20.

The maximum is Δ_{2}^{∗}(C) = 22, and we conclude that d_{3}^{∗} = 4 · 17 − 22 = 46.

The construction to obtain a plane P of value 22, assumes that all factorisable points in P are contained in the union of two lines. The best we can do with this approach is to take P := ⟨a′ ⊗ ℓ_{B} ∪ ℓ_{A} ⊗ b′⟩ where a′ ∈ ℓ_{A} and b′ ∈ ℓ_{B}. This gives Δ_{2}(C) = ν(P) = 20 < 22. Hence d_{3}(C) = 48 > 46. To get a value of Δ_{2}^{∗}(C) = 22, we should have had ν_{B}(b′) = 6, i.e. that ℓ_{B} contains a point of maximum value.

Example 2: Take the previous example and reduce the length of B by setting ν_{B}(b) = 3, and ν_{B}(p) = 2 for p ∈ ℓ_{B}. Now B is a [9, 3] non-chain code with difference sequence (3, 3, 3). This gives the following choices for the maximisation of Δ_{2}^{∗}(C):

{3, 0, 0} : δ_{0}(A)Δ_{2}(B) = 9
{2, 1, 0} : δ_{0}(A)Δ_{1}(B) + δ_{1}(A)Δ_{0}(B) = 12
{1, 1, 1} : Δ_{2}(A)Δ_{0}(B) = 12.

The maximum is Δ_{2}^{∗}(C) = 12, and this is realised by the plane a ⊗ ℙ^{2}. Hence we get d_{3}(C) = d_{3}^{∗}(C) = 4 · 9 − 12 = 24.

Remark 1: Even if A and B are chained codes, A ⊗ B may be non-chain.

We give an example to show this remark.

Example 3: Define two value assignments ν_{A} and ν_{B} on ℙ^{2}, defining two binary, chained codes A and B. Let a, b, c ∈ ℙ^{2} be projectively independent points, and define the value assignments as follows:

ν_{A}(a) = ν_{A}(b) = 3
ν_{A}(c) = 1
ν_{A}(p) = 0, ∀p ∉ {a, b, c}
ν_{B}(a) = 3
ν_{B}(p) = 1, ∀p ≠ a.

The product C = A ⊗ B corresponds to a value assignment ν on ℙ^{8}. All points of positive value in ℙ^{8} are located in three disjoint planes, Π_{a}, Π_{b}, and Π_{c}, consisting of the points with a, b, or c respectively as the first factor. We have

ν(a ⊗ a) = ν(b ⊗ a) = 9
ν(a ⊗ p) = ν(b ⊗ p) = 3, ∀p ≠ a
ν(c ⊗ a) = 3
ν(c ⊗ p) = 1, ∀p ≠ a.

We see that the only line of maximum value is ℓ := ⟨a ⊗ a, b ⊗ a⟩, and the planes of maximum value are Π_{a} and Π_{b}, neither of which contains ℓ. Hence C is non-chain.

Acknowledgement

The author wishes to thank prof. Trygve Johnsen and prof. Torleiv Kløve for comments and hints.

References

[1] S. Dodunekov and J. Simonis, “Codes and projective multisets,” Electron. J. Combin., vol. 5, no. 1, 1998, Research Paper 37.

[2] Tor Helleseth, Torleiv Kløve, and Øyvind Ytrehus, “Generalized Hamming weights of linear codes,” IEEE Trans. Inform. Theory, vol. 38, no. 3, pp. 1133–1140, 1992.

[3] Michael A. Tsfasman and Serge G. Vlăduţ, “Geometric approach to higher weights,” IEEE Trans. Inform. Theory, vol. 41, no. 6, part 1, pp. 1564–1588, 1995, Special issue on algebraic geometry codes.

[4] Tor Helleseth and Torleiv Kløve, “The weight hierarchies of some product codes,” IEEE Trans. Inform. Theory, vol. 42, no. 3, pp. 1029–1034, 1996.

[5] Victor K. Wei and Kyeongcheol Yang, “On the generalized Hamming weights of product codes,” IEEE Trans. Inform. Theory, vol. 39, no. 5, pp. 1709–1713, 1993.

[6] Angela I. Barbero and Juan G. Tena, “Weight hierarchy of a product code,” IEEE Trans. Inform. Theory, vol. 41, no. 5, pp. 1475–1479, September 1995.

[7] William Fulton, Intersection Theory, Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag, 2nd edition edition, 1998.

[8] Wende Chen and Torleiv Kløve, “Bounds on the weight hierarchies of extremal non-chain codes of dimension 4,” Applicable Algebra in Engineering, Communication and Computing, vol. 8, pp. 379–386, 1997.

[9] Hans Georg Schaathun, “Upper bounds on weight hierarchies of extremal non-chain codes,” Tech. Rep. 171, Department of Informatics, University of Bergen, 1999, Also available at http://www.ii.uib.no/∼georg/sci/inf/coding/public/.