A Lower Bound on the Greedy Weights of Product Codes

Hans Georg Schaathun^{1}

Institutt for Informatikk, Universitas Bergensis, Høyteknologisenteret, N-5020 Bergen, Norway. Email: ⟨georg@ii.uib.no⟩.

Abstract

A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r − 1)-subcode. The r-th greedy weight e_{r} is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes.

Key words: product code, projective multiset, weight hierarchy, Segre embedding, greedy weights

1 Introduction

Generalised Hamming weights have received a lot of attention after Victor Wei’s paper [10] in 1991. Chen and Kløve [1,2] have introduced the greedy weights, inspired by [3]. The greedy weights coincide with the generalised Hamming weights if and only if the code satisfies the chain condition [11].

Recent works [7,5,9] have treated the generalised Hamming weights of product codes. In this paper we build on the technique from [7] to give a lower bound on the greedy weights of product codes, in terms of the greedy weights of the component codes. We also give an analogous result for the top-down greedy weights introduced in [8].

1 Part of the work was done at the ENST, 46 rue Barrault, 75013 Paris, France; with support from NFR under grant ?

Preprint submitted to Designs, Codes, and Cryptography 6 February 2001

The layout of the paper is as follows. In this section we will present some basic notation and the result on weight hiearchies. This result is included to show how parallel the new result is. In Section 2 we define the greedy weights and present the new result. Section 3 gives some preliminaries for the proof, which appears in Section 4.

1.1 Product Codes and Weight Hierarchies

An [n, k] code is a k-dimensional subspace C ≦ 𝕍 of some n-dimensional vector space 𝕍. The support of a vector c = (c_{1}, c_{2}, …, c_{n}) ∈ 𝕍 is the set

χ(c) := {i | c_{i} ≠ 0},

and the support of a subset S ⊆ 𝕍 is the set

χ(S) := ⋃_{c∈S} χ(c).

The weight hierarchy of the code C ≦ 𝕍 is the sequence

(d_{1}(C), d_{2}(C), …, d_{k}(C)),

where

d_{r}(C) := min{#χ(D) | D ≦ C, dim D = r}.

Clearly d_{1}(C) is the minimum distance, and for convenience we have d_{0}(C) = 0.

Let C_{1} be an [n_{1}, k_{1}] code and C_{2} an [n_{2}, k_{2}] code over the same field 𝔽. The product code C_{1} ⊗ C_{2} is the tensor product of C_{1} and C_{2} as vector spaces over 𝔽. In other words

C_{1} ⊗ C_{2} = ⟨a ⊗ b | a ∈ C_{1}, b ∈ C_{2}⟩,

where

a ⊗ b = (a_{i}b_{j} | 1 ≤ i ≤ n_{1}, 1 ≤ j ≤ n_{2}),
a = (a_{1}, a_{2}, …, a_{n_{1}}),
b = (b_{1}, b_{2}, …, b_{n_{2}}).

The product code is an [n_{1}n_{2}, k_{1}k_{2}] code.

Define

M_{t} := {i = (i_{1}, i_{2}, …, i_{t−1}) | 1 ≤ i_{j} ≤ k_{j}, 1 ≤ j < t}.

Definition 1 Let π be a map M_{t} → {0, 1, …, k_{t}}. We call π a (k_{1}, k_{2}, …, k_{t})- partition of r if (1) ∑_{i∈M_{t}} π(i) = r.

(2) π is a decreasing function in each coordinate, i.e.

π((i_{1}, …, i_{j}, …, i_{t−1})) ≤ π((i_{1}, …, i_{j} − 1, …, i_{t−1})),

for all j where 0 < j < t and 1 < i_{j}.

Wei and Yang [11] introduced an expression d_{r}^{∗} to serve as a bound. This expression was generalised for products of more than two codes in [5]:

d_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) := min {∇(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r)},

where

∇(π) = ∑_{i∈M_{t}} ∏_{j=1}^{t−1}(d_{i_{j}}(C_{j}) − d_{i_{j}−1}(C_{j}))d_{π(i)}(C_{t}).

The chain condition says that there exists a sequence of subcodes

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

such that D_{i} has dimension i and weight d_{i}(C). Many good codes satisfy the chain condition, such as the Hamming, Reed-Muller, MDS, and the extended Golay codes. Nevertheless, most codes do not satisfy this condition [3].

Theorem 2 If C_{1}, C_{2}, …, C_{t} are arbitrary linear codes, then

d_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≥ d_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}).

Equality holds if all the component codes satisfy the chain condition.

This theorem was finally proved in [9]. Partial results had appeared in [11,7,5].

2 Greedy weights

2.1 Definitions

The greedy weights were introduced in [1,2], inspired by some other parameters from [3]. The greedy weights are motivated by the following problem. Consider the Wire-Tap Channel of Type II [6] and a ‘greedy’ adversary. That is to say that the adversary will first read bits to get one information bit as soon as possible. Having obtained i information bits, he will try to get the (i + 1)-st bit as soon as possible. The r-th greedy weight is the least number of bits required to obtain r information bits by this approach.

The top-down greedy weights were introduced in [7], and it was shown that the greedy weights of C is determined by the top-down greedy weigths of the dual code.

A (bottom-up) greedy 1-subcode is a minimum 1-subcode. A (bottom-up) greedy r-subcode, r ≥ 2, is any r-dimensional subcode containing a (bottomup) greedy (r − 1)-subcode, such that no other such code has lower weight. The r-th greedy weight e_{r} is the weight of a greedy r-subcode

We have obviously that d_{1} = e_{1} and d_{k} = e_{k}, for any k-dimensional code. For most codes e_{2} > d_{2} [3]. The chain condition is satisfied if and only if e_{r} = d_{r} for all r.

A top-down greedy k-subcode is C. A top-down greedy r-subcode is a subcode of dimension r, contained in a greedy (r + 1)-space, such that no other such subscode has lower weight. The rth top-down greedy weight ẽ_{r} is the weight of a top-down greedy r-subcode.

Remark 3 The top-down greedy weights share many properties with the (bottom-up) greedy weights. For all codes ẽ_{r} ≥ d_{r}. The chain condition holds if and only if ẽ_{r} = d_{r} for all r. In general, ẽ_{r} may be equal to, greater than, or less than e_{r}.

2.2 The result

Define the greedy differences

ϵ_{i}(C) := e_{k−i}(C) − e_{k−1−i}(C),
ϵ̃_{i}(C) := ẽ_{k−i}(C) − ẽ_{k−1−i}(C).

We define the greedy analogues of ∇ as follows.

∇_{E}(π) := ∑_{i∈M_{t}} e_{π(i)}(C_{t}) ∏_{j=1}^{t−1} ϵ_{k_{j}−i_{j}}(C_{j}),

˜∇_{E}(π) := ∑_{i∈M_{t}} ẽ_{π(i)}(C_{t}) ∏_{j=1}^{t−1} ϵ̃_{k_{j}−i_{j}}(C_{j}).

We also define e_{r}^{∗} and ẽ_{r}^{∗} analogously to d_{r}^{∗}.

e_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) := min {∇_{E}(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r)},
ẽ_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) := min { ˜∇_{E}(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r)}.

Theorem 4 We have

e_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≥ e_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}),
ẽ_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≥ ẽ_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}).

Remark 5 The bound in the conjecture may or may not be met with equality. This is obvious if we consider chained component codes. Then d_{j}(C_{i}) = e_{j}(C_{i}), and d_{r} = e_{r}^{∗}. If the product code is chained, then e_{r} = d_{r} = e_{r}^{∗}. Otherwise e_{r} > d_{r} = e_{r}^{∗} for some r. It was shown in [7] that such a product code may or may not be chained.

3 Preliminaries

3.1 Projective multisets

A projective multiset is a collection of projective points which are not necessarily distinct. We usually define it as a map

γ : ℙ^{k−1} → {0, 1, 2, …},

where γ(x) is the number of times x occurs in the collection. This is extended for any S ⊆ ℙ^{k−1} such that

γ(S) = ∑_{x∈S} γ(x).

We call γ(S) the value of S.

Let C be a linear code and G a generator matrix for C. Codes obtained from C by permuting columns of G or by replacing some columns with proportional columns are equivalent to C. The projective multiset γ_{C} corresponding to C is the multiset of columns of G, considered as projective points. The multiset γ_{C} defines C up to equivalence.

Helleseth et al. [4] proved that there is a one-to-one correspondence between subcodes D ≦ C and subspaces Π ≦ ℙ^{k−1} such that

dim Π + dim D = k − 1,
γ_{C}(Π) + w(D) = n.

This implies that

d_{r}(C) = n − max{γ_{C}(Π) | Π ≦ ℙ^{k−1}, dim Π = k − 1 − r}.

Let D′ ≦ D ≦ C, and let Π and Π′ be projective subspaces corresponding to D and D′ respectively. Then it follows by the proof in [4] that Π ≦ Π′.

If D is a (bottom-up) greedy (k−1−r)-subcode, then we call the corresponding subspace Π a (bottom-up) greedy r-space. A (bottom-up) greedy r-space can be equivalently defined by the following recursion. The only (bottom-up) greedy (k − 1)-space is ℙ^{k−1}. A (bottom-up) greedy r-space is r-space contained in a (bottom-up) greedy (r + 1)-space such that no other such subspace has higher value.

Analogously, a top-down greedy r-space correspond to a top-down greedy (k −1−r)-subcode. The only top-down greedy (−1)-space is the empty set. A top-down greedy r-space is an r-space containing a top-down greedy (r − 1)- space such that no other such subspace has higher value.

3.2 The product of Projective Multisets

The map (a, b) ↦ a ⊗ b, which was used to define the tensor product, is welldefined also for projective points. It defines the injective map known as the Segre embedding

σ : ℙ^{k_{1}−1} × ℙ^{k_{2}−1} ↪ P^{k_{1}k_{2}−1}.

The image under the Segre embedding is called the Segre variety. This embedding is well known in algebraic geometry.

Proposition 6 Let γ_{1} and γ_{2} be the projective multisets corresponding to the codes C_{1} and C_{2} respectively. Then γ := σ(γ_{1}, γ_{2}) is the projective multiset corresponding to C_{1} ⊗ C_{2}.

We give a precise explanation of σ(γ_{1}, γ_{2}). It means that γ(a⊗b) = γ_{1}(a)γ_{2}(b), and γ(x) = 0 for all x which is not on the Segre variety. Proposition 6 was proved in [7], but it should not be to hard to verify it by studying generator matrices of C_{1}, C_{2}, and C.

3.3 Redefining the problem

Analougously to the approach for weight hierarchies we will now reformulate the problem in terms of projective multisets.

For every π ∈ P(k_{1}, k_{2}, …, k_{t}; r), the dual partition [9] is defined as

π^{∗}(i) := k_{t} − π((k_{1} + 1, k_{2} + 1, …, k_{t−1} + 1) − i).

Note that π^{∗} ∈ P(k_{1}, k_{2}, …, k_{t}; k − r) where k = ∏_{i=1}^{t} k_{i}, and if ψ = π^{∗}, then π = ψ^{∗}.

We define, analogously to Δ_{i}(C) in [7],

E_{i}(C) := ∑_{j=0}^{i} ϵ_{i} = e_{k}(C) − e_{k−1−i}(C),  (1)

Ẽ_{i}(C) := ∑_{j=0}^{i} ϵ̃_{i} = ẽ_{k}(C) − ẽ_{k−1−i}(C).  (2)

Analougously to Δ(π) in [7] we define

E(π) := ∑_{i∈M_{t}} E_{π(i)−1}(C_{t}) ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j}),  (3)

Ẽ(π) := ∑_{i∈M_{t}} Ẽ_{π(i)−1}(C_{t}) ∏_{j=1}^{t−1} ϵ̃_{i_{j}−1}(C_{j}).  (4)

Lemma 7 The above definition is equivalent to

E(π) = n − ∇_{E}(π^{∗}),
Ẽ(π) = n − ˜∇_{E}(π^{∗}).

PROOF. We prove the first statement explicitely. The second statement is proved similarily by replacing ϵ_{i}(C_{j}) with ϵ̃_{i}(C_{j}).

First note that

∇_{E}(π^{∗}) = ∑_{i∈M_{t}} e_{π^{∗}(i)}(C_{t}) ∏_{j=1}^{t−1} ϵ_{k_{j}−i_{j}}(C_{j}) = ∑_{i∈M_{t}} e_{π^{∗}(k+1−i)}(C_{t}) ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j}),

where k denotes an all-k vector, and 1 an all-1 vector. Hence

∇_{E}(π^{∗}) = ∑_{i∈M_{t}} e_{k_{t}−π(i)}(C_{t}) ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j}).

We combine this with (3) to get

E(π) + ∇_{E}(π^{∗}) = ∑_{i∈M_{t}}(E_{π(i)−1}(C_{t}) + e_{k_{t}−π(i)}(C_{t})) ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j})

=n_{t} ∑_{i∈M_{t}} ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j}).

It only remains to prove that

∑_{i∈M_{t}} ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j}) = n_{1} · n_{2} · . . . · n_{t−1}.  (5)

This is obviously true if t = 2, so we prove it by induction. We have

\begin{aligned}∑_{i∈M_{t}} ∏_{j=1}^{t−1} ϵ_{i_{j}−1}(C_{j}) & = ∑_{i_{t−1}=1}^{k_{t−1}} ϵ_{i_{t−1}−1}(C_{t−1}) ∑_{i∈M_{t−1}} ∏_{j=1}^{t−2} ϵ_{i_{j}−1}(C_{j}) \\ & = n_{t−1} ∑_{i∈M_{t−1}} ∏_{j=1}^{t−2} ϵ_{i_{j}−1}(C_{j}). \end{aligned}

Hence (5) follows by induction, and the lemma is proved. □

Similarily to e_{r}^{∗} and ẽ_{r}^{∗}, we define E_{r}^{∗} and Ẽ_{r}^{∗}, which will give bounds on E_{r} and Ẽ_{r}.

E_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) := max{E(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1)},
Ẽ_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) := max{Ẽ(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1)}.

Lemma 8 The following two statements are equivalent

e_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≥ e_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}),
E_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≤ E_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}).

Also the following two equations are equivalent

ẽ_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≥ ẽ_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}),
Ẽ_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≤ Ẽ_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}).

PROOF. By Lemma 7, we get that

E_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) + e_{r}^{∗}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) = n.

By definition E_{r} + e_{r} = n. Hence the first equivalence follows. The second equivalence is proved in the same way. □

3.4 The associated partition

Let γ_{i} be the projective multiset corresponding to C_{i}. Let C = C_{1}⊗C_{2}⊗…⊗C_{t}, where dim C = k, and let C′ = C_{2} ⊗ … ⊗ C_{t} with dim C′ = k′. Let γ and γ′ be the projective multiset corresponding to C and C′ respectively.

The associated partition was introduced in [9]. We define it first in the case where t = 2.

Definition 9 Let Π ≦ ℙ^{k−1}. For 0 ≤ i ≤ k_{1} − 1, let θ_{i}(Π) be the set of points p ∈ ℙ^{k_{2}−1} such that there is an i-space Φ_{Π}^{i}(p) ≦ ℙ^{k_{1}−1} with Φ_{Π}^{i}(p) ⊗ p ⊆ Π. The associated partition of Π is given by

π(Π)(i) = dim⟨θ_{i−1}(Π)⟩ + 1.

Obviously θ_{i}(Π) ⊆ θ_{i−1}(Π). Hence π(Π) is in deed a partition.

The i-th subpartition π|_{i} of π, is defined by

π|_{i}(i_{2}, i_{3}…. , i_{t−1}) = π(i, i_{2}, i_{3}, …, t_{t−1}).

We can no define the associated partition for arbitrary t by recursion.

Definition 10 Let Π ≦ ℙ^{k−1}. For 0 ≤ i ≤ k_{1} −1, let θ_{i}(Π) be the set of points p ∈ ℙ^{k′−1} such that there is an i-space Φ_{Π}^{i}(p) ≦ ℙ^{k_{1}−1} with Φ_{Π}^{i}(p) ⊗ p ⊆ Π. We define the associated partition π(Π) by its subpartitions π(Π)|_{i} = π(⟨θ_{i−1}(Π)⟩).

It is clear that π(Π) ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1) for some r where dim Π ≥ r [9]. We define Θ_{i}(Π) := ⟨θ_{i}(Π)⟩. For every point p ∈ ℙ^{k′−1} we let Φ_{Π}(p) = Φ_{Π}^{i}(p) for the largest i for which this is defined.

We define a partial ordering on the set of partitions, such that π ≤ π′ if and only if π(i) ≤ π′(i) for all i ∈ M_{t}.

4 The proof

4.1 The Simple Case

We start with the simple case where t = 2. We proceed by induction on t in Section 4.2.

Definition 11 Let Π ≦ ℙ^{k−1} and π = π(Π) ∈ P(k_{1}, k_{2}; r + 1). We call Π a normal subspace associated with π if

(1) all the Θ_{i}(Π) are greedy subspaces;

(2) for each i and for all x ∈ Θ_{i}\Θ_{i+1} with γ_{2}(x) > 0, Φ_{Π}(x) is a greedy i-space; and

(3) dim Π = r.

Lemma 12 Let Π be a normal r-space, and let Π′′ < Π. Then, for any partition π′ ∈ P(k_{1}, k_{2}; r) such that π(Π′′) ≤ π′ < π(Π), we have γ(Π′′) ≤ E(π′). Equality holds if and only if Π′′ is a normal subspace associated with π′.

PROOF. We write Θ′′_{i} = Θ_{i}(Π′′) and Θ_{i} = Θ_{i}(Π). Observe that

γ(Π′′) = ∑_{i=0}^{k_{1}−1} ∑_{x∈Θ′′_{i}\Θ′′_{i+1}} γ_{2}(x)γ_{1}(Φ_{Π′′}(x)).  (6)

We choose a partition π′ according to the lemma. There is a unique s such that π′(s + 1) = π(s + 1) − 1. Let Θ′_{s} be an arbitrary subspace such that

Θ′′_{s} ≦ Θ′_{s} < Θ_{s},
dim Θ′_{s} = dim Θ_{s} − 1 = π′(s + 1) − 1.

Since Θ_{s} is a greedy subspace, we get that γ(Θ′_{s}) ≤ E_{π′(s+1)−1}(C_{2}). Write Θ′_{i} = Θ_{i} for all i ≠ s. Thus we get, for all i,

Θ′′_{i} ⊂ Θ′_{i},  (7)
γ_{2}(Θ′′_{i}) ≤ γ_{2}(Θ′_{i}) ≤ E_{π′(i+1)−1}(C_{2}).  (8)

If y ∈ Θ_{s}\Θ′_{s}, then Φ_{Π′′}(y) < Φ_{Π}(y). Since Φ_{Π}(y) is a greedy s-space, we get that

γ_{1}(Φ_{Π′′}(y)) ≤ E_{s−1}(C_{1}).

Clearly Φ_{Π′′}(x) ≦ Φ_{Π}(x) for all x ∈ ℙ^{k_{2}−1}. Furthermore, we have

γ_{1}(Φ_{Π}(x)) ≤ E_{i}(C_{1}), ∀x ∈ Θ_{i}\Θ_{i+1}.

Hence we get for any i that

γ_{1}(Φ_{Π′′}(x)) ≤ E_{i}(C_{1}), ∀x ∈ Θ′_{i}\Θ′_{i+1}.  (9)

Thus we get from (6) that

γ(Π′′) ≤ ∑_{i=0}^{k_{1}−1} ∑_{x∈Θ′′_{i}\Θ′′_{i+1}} γ_{2}(x)E_{i}(C_{1}).  (10)

This may be simplified further to

γ(Π′′) ≤ ∑_{i=0}^{k_{1}−1} E_{i}(C_{1})γ_{2}(Θ′′_{i}\Θ′′_{i+1})

= ∑_{i=0}^{k_{1}−1} E_{i}(C_{1})(γ_{2}(Θ′′_{i}) − γ_{2}(Θ′′_{i+1}))

= ∑_{i=0}^{k_{1}−1} E_{i}(C_{1})γ_{2}(Θ′′_{i}) − ∑_{i=1}^{k_{1}} E_{i−1}(C_{1})γ_{2}(Θ′′_{i}).

Now observe that Θ′′_{k_{1}} is the empty set, and ϵ_{0}(C_{1}) = E_{0}(C_{1}). Hence

γ(Π′′) ≤ ∑_{i=0}^{k_{1}−1} ϵ_{i}(C_{1})γ_{2}(Θ′′_{i}) ≤ ∑_{i=1}^{k_{1}} ϵ_{i−1}(C_{1})E_{π′(i)−1}(C_{2}) = E(π′),

by (8). This proves the bound in the lemma.

It remains to prove that equality depends on Π′′ being a normal subspace associated with π′. Assume therefore that γ(Π′′) = E(π′). Then we must have equality in (8), which requires equality in (7). It follows that π(Π′′) = π′. Another necessary condition for equality in (8), is that all the Θ′_{i} are greedy subspaces. This proves Property 1 in Definition 11.

We must also have equality in (10), which in turn depends on equality in (9) for all x with γ_{2}(x) > 0. This proves Property 2 in the definition.

Finally we observe that dim Π′′ ≤ r −1 since it is a proper subspace of Π. Also dim Π′′ ≥ Σπ′ − 1 = r − 1. Hence dim Π′′ = r − 1, which is the third property in the definition. The lemma follows by induction. □

Definition 13 A greedy basis of ℙ^{k_{i}−1} is a basis p_{0}, p_{1}, …, p_{k_{1}−1} such that ⟨p_{0}, p_{1}, …, p_{r}⟩ is a greedy r-space.

Lemma 14 Given a fixed greedy basis for each space ℙ^{k_{1}−1} and ℙ^{k_{2}−1}, there is a well-defined normal subspace Π_{π} associated with every partition π, such that if π′ ≤ π, then Π_{π′} ≦ Π_{π}.

PROOF. Let b_{0}, b_{1}, …, b_{k_{2}−1} be the greedy basis for ℙ^{k_{2}−1}. Write

Ψ_{i} = ⟨b_{0}, b_{1}, …, b_{i}⟩.

Let p_{0}, p_{1}, …, p_{k_{1}−1} be the greedy basis for ℙ^{k_{1}−1}. We define Π_{π} by the following formula,

Π_{r} = ⟨p_{i} ⊗ Ψ_{π_{r}(i+1)−1} | 0 ≤ i < k_{1}⟩.

It is straight forward to verify the properties of Π_{r}. □

Proposition 15 If Π ≦ ℙ^{k−1} is a greedy subspace of dimension r, then Π is a normal subspace and γ(Π) = E(π) where π = π(Π) ∈ P(k_{1}, k_{2}; r + 1)

We omit the proof, which is exactly identical to that of Proposition 20.

Corollary 16 For all codes C_{1} and C_{2}, we have

E_{r}(C_{1} ⊗ C_{2}) ≤ max{E(π) | π ∈ P(k_{1}, k_{2}; r + 1)}.

4.2 The General Case

We generalise the results from the last section by induction on t. We define normal subspaces recursively as follows.

Definition 17 Let Π ≦ ℙ^{k−1} and π = π(Π) ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1). We call Π a normal subspace associated with π if

(1) for each i, Θ_{i}(Π) is a normal subspace associated with π|_{i+1};

(2) for each i and for all x ∈ Θ_{i}\Θ_{i+1} with γ′(x) > 0, Φ_{Π}(x) is a greedy i-space; and

(3) dim Π = r.

Lemma 18 Let Π be a normal r-space, and let Π′′ < Π be a subspace. Then for any partition π′ ∈ P(k_{1}, k_{2}, …, k_{t}; r) such that π(Π′′) ≤ π′ ≤ π(Π), we have γ(Π′′) ≤ E(π′). Equality holds if and only if Π′′ is a normal subspace associated with π′.

PROOF. This was proved for t = 2 in Lemma 12. We assume that it holds for t − 1 and prove it for t.

We write Θ′′_{i} = Θ_{i}(Π′′) and Θ_{i} = Θ_{i}(Π). Observe that

γ(Π′′) = ∑_{i=0}^{k_{1}−1} ∑_{x∈Θ′′_{i}\Θ′′_{i+1}} γ′(x)γ_{1}(Φ_{Π′′}(x)).  (11)

We choose an arbitrary partition π′ according to the lemma. We write u_{i} := Σπ|_{i+1} − 1 and u′_{i} := Σπ′|_{i+1} − 1 for brevity. There is a unique s such that u′_{s} = u_{s} − 1. Let Θ′_{s} be an arbitrary subspace such that

Θ′′_{s} ≦ Θ′_{s} < Θ_{s},
dim Θ′_{s} = dim Θ_{s} − 1 = u′_{s}.

Since Θ_{s} is a normal subspace, we get that γ(Θ′_{s}) ≤ E_{u′_{s}}(C′), by the induction hypothesis. Write Θ′_{i} = Θ_{i} for all i ≠ s. Thus we get, for all i,

Θ′′_{i} ⊂ Θ′_{i},  (12)
γ′(Θ′′_{i}) ≤ γ′(Θ′_{i}) ≤ E_{u′_{i}}(C′).  (13)

If y ∈ Θ_{s}\Θ′_{s}, then Φ_{Π′′}(y) < Φ_{Π}(y). Since Φ_{Π}(y) is a greedy subspace of dimension s, we get that

γ_{1}(Φ_{Π′′}(y)) ≤ E_{s−1}(C_{1}).

Clearly Φ_{Π′′}(x) ≦ Φ_{Π}(x) for all x ∈ ℙ^{k′−1}. Furthermore, we have

γ_{1}(Φ_{Π}(x)) ≤ E_{i}(C_{1}), ∀x ∈ Θ_{i}\Θ_{i+1}.

Hence we get for any i that

γ_{1}(Φ_{Π′′}(x)) ≤ E_{i}(C_{1}), ∀x ∈ Θ′_{i}\Θ′_{i+1}.  (14)

From (11) we find that

γ(Π′′) ≤ ∑_{i=0}^{k_{1}−1} ∑_{x∈Θ′′_{i}\Θ′′_{i+1}} γ′(x)E_{i}(C_{1}).  (15)

This may be simplified further to

γ(Π′′) ≤ ∑_{i=0}^{k_{1}−1} E_{i}(C_{1})γ′(Θ′′_{i}\Θ′′_{i+1})

= ∑_{i=0}^{k_{1}−1} E_{i}(C_{1})(γ′(Θ′′_{i}) − γ′(Θ′′_{i+1}))

= ∑_{i=0}^{k_{1}−1} E_{i}(C_{1})γ′(Θ′′_{i}) − ∑_{i=1}^{k_{1}} E_{i−1}(C_{1})γ′(Θ′′_{i}).

Now observe that Θ′′_{k_{1}} is the empty set, and ϵ_{0}(C_{1}) = E_{0}(C_{1}). Hence

γ(Π′′) ≤ ∑_{i=0}^{k_{1}−1} ϵ_{i}(C_{1})γ′(Θ′′_{i}) ≤ ∑_{i=1}^{k_{1}} ϵ_{i−1}(C_{1})E_{u′_{i}}(C′) = E(π′),

by (13) and the induction hypothesis. This proves the bound in the lemma.

It remains to prove that equality depends on Π′′ being a normal subspace associated with π′. Assume therefore that γ(Π′′) = E(π′). Then we must have equality in (13), which requires equality in (12). It follows that π(Π′′) = π′. Another necessary condition for equality in (13), is that all the Θ′_{i} are greedy subspaces. By the induction hypothesis it follows that Θ_{i} is a normal subspace associated with π′|_{i+1}, which is Property 1 in Definition 17

We must also have equality in (15), which in turn depends on equality in (14). Hence Φ_{Π′′}(x) must be a greedy subspace for all x ∈ ℙ^{k′−1} such that γ′(x) > 0. This proves Property 2 in Definition 17.

Finally we observe that dim Π′′ ≤ r −1 since it is a proper subspace of Π. Also dim Π′′ ≥ Σπ′ − 1 = r − 1. Hence dim Π′′ = r − 1, which is the third property in the definition. The lemma follows by induction. □

Lemma 19 Given a fixed greedy basis for each space ℙ^{k_{i}−1}, there is a welldefined normal subspace Π_{π} associated with every partition π, such that if π′ ≤ π, then Π_{π′} ≦ Π_{π}.

PROOF. This holds for t = 2 by Lemma 14. We prove it for all t by induction. Therefore we assume that for every π_{r} ∈ P(k_{2}, k_{3}, …, k_{t}; r+1), there is a welldefined normal subspace Ψ_{π_{r}} ≦ ℙ^{k′−1} associated with π_{r}. Let p_{0}, p_{1}, …, p_{k_{1}−1} be a greedy basis for ℙ^{k_{1}−1}.

The Π_{π} may be given by the following formula,

Π_{π} = ⟨p_{i−1} ⊗ Ψ_{π|_{i}} | 1 ≤ i ≤ k_{1}⟩.

It is straight forward to verify the properties of this subspace. □

Proposition 20 If Π ≦ ℙ^{k−1} is a greedy subspace of dimension r, then Π is a normal subspace and γ(Π) = E(π) where π = π(Π) ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1).

PROOF. Note that ℙ^{k−1} is a normal subspace associated with π where π(i) = k_{t} for all i ∈ M_{t}. Also ℙ^{k−1} is the unique greedy (k−1)-space. Hence the lemma holds for r = k − 1. Assume that the lemma holds for r. We will prove that then it also holds for r − 1.

Let Π and Π′ be greedy subspaces of dimensions r and r − 1 respectively, such that Π′ < Π. By the inductive hypothesis, Π is a normal subspace associated with some partition π. Also write π′ = π(Π′). By Lemma 12, γ(Π′) ≤ E(π′′) for every partition π′′ ∈ P(k_{1}, k_{2}, …, k_{t}; r) with π′ ≤ π′′ < π.

By Lemma 14, there exists, for every such partition π′′, a normal subspace Π_{π′′} associated with π′′, and γ(Π_{π′′}) = E(π′′), such that Π_{π′′} < Π′′ for some greedy r-space Π′′. Since Π′ is a greedy subspace, we must thus have γ(Π′) = E(π′) and Σπ′ = r. The lemma follows by induction. □

Corollary 21 For any family codes C_{1}, C_{2}, …, C_{t}, we have

E_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≤ max{E(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1)}.

This proves the first bound of Theorem 4.

4.3 Top-down Greedy Weights

The proof for top-down greedy weights is very similar to that for bottom-up greedy weights (and just as long). We will only list the definitions and the main lemmata for the induction step. The proofs can be filled in by following the pattern of the preceeding sections.

Definition 22 Let Π ≦ ℙ^{k−1} and π = π(Π) ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1). We call Π a top-down normal subspace associated with π if

(1) for each i, Θ_{i}(Π) is a top-down normal subspace associated with π|_{i+1} (or if t = 2, a top-down greedy i-space).

(2) for each i and for all x ∈ Θ_{i}\Θ′_{i} with γ′(x) > 0, Φ_{Π}(x) is a top-down greedy i-space.

(3) dim Π = r.

Lemma 23 Let Π be a top-down normal r-space, and let Π′′ > Π. Then for any partition π′ ∈ P(k_{1}, k_{2}, …, k_{t}; r + 2) such that π(Π′′) ≥ π′ ≥ π(Π), we have γ(Π′′) ≤ E(π′). Equality holds if and only if Π′′ is a top-down normal subspace associated with π′.

Definition 24 A top-down greedy basis ℙ^{k_{i}−1} is a basis p_{0}, p_{1}, …, p_{k_{1}−1} such that ⟨p_{i} | 0 ≤ i ≤ r⟩ is a top-down greedy r-space.

Lemma 25 Given a fixed top-down greedy basis for each space ℙ^{k_{i}−1}, there is a well-defined top-down normal subspace Π_{π} associated with every partition π, such that if π′ ≤ π, then Π_{π′} ≦ Π_{π}.

Proposition 26 If Π ≦ ℙ^{k−1} is a top-down greedy subspace of dimension r, then Π is a normal subspace and γ(Π) = Ẽ(π) where

π = π(Π) ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1).

Corollary 27 For any family codes C_{1}, C_{2}, …, C_{t}, we have

Ẽ_{r}(C_{1} ⊗ C_{2} ⊗ … ⊗ C_{t}) ≤ max{Ẽ(π) | π ∈ P(k_{1}, k_{2}, …, k_{t}; r + 1)}.

This proves the second bound of Theorem 4.

References

[1] Wende Chen and Torleiv Kløve. On the second greedy weight for linear codes of dimension 3. To appear in Discrete Mathematics.

[2] Wende Chen and Torleiv Kløve. On the second greedy weight for binary linear codes. In M. Fossorier et al., editor, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, volume 1719 of Springer Lecture Notes in Computer Science, pages 131–141, 1999.

[3] Gérard D. Cohen, Sylvia B. Encheva, and Gilles Zémor. Antichain codes. Des. Codes Cryptogr., 18(1-3):71–80, 1999.

[4] Tor Helleseth, Torleiv Kløve, and Øyvind Ytrehus. Generalized Hamming weights of linear codes. IEEE Trans. Inform. Theory, 38(3):1133–1140, 1992.

[5] Conchita Martínez-Pérez and Wolfgang Willems. On the weight hierarchy of product codes. Preprint submitted to IEEE Trans. Inf. Theory, 2000.

[6] L. H. Ozarow and A. D. Wyner. Wire-tap channel II. AT&T Bell Laboratories Technical Journal, 63(10):2135–2157, December 1984.

[7] Hans Georg Schaathun. The weight hierarchy of product codes. IEEE Trans. Inform. Theory, 46(7):2648–2651, November 2000.

[8] Hans Georg Schaathun. Greedy weights and duality for linear codes. Submitted to AAECC-14, 2001.

[9] Hans Georg Schaathun and Wolfgang Willems. A lower bound for the weight hierarchies of product codes. Submitted to Discrete Applied Mathematics, 2001.

[10] Victor K. Wei. Generalized Hamming weights for linear codes. IEEE Trans. Inform. Theory, 37(5):1412–1418, 1991.

[11] Victor K. Wei and Kyeongcheol Yang. On the generalized Hamming weights of product codes. IEEE Trans. Inform. Theory, 39(5):1709–1713, 1993.