Upper bounds on Weight Hierarchies of Extremal Non-Chain Codes

Hans Georg Schaathun

Department of Informatics, Universitas Bergensis, Høyteknologisenteret, N-5020 Bergen, Norway

Abstract

The weight hierarchy of a linear [n, k; q] code C over GF(q) is the sequence (d_{1}, d_{2}, …, d_{k}) where d_{r} is the smallest support weight of an r-dimensional subcode of C. Linear codes may be classified according to a set of chain and non-chain conditions, the extreme cases being codes satisfying the chain condition (due to Wei and Yang) and extremal, non-chain codes (due to Chen and Kløve). This paper gives upper bounds on the weight hierarchies of the latter class of codes.

Key words: Weight hierarchy, chain condition, linear codes, projective multiset

1 Introduction

The concept of generalised Hamming weights was introduced as early as 1977 by Helleseth et al. [8] in their study of weight distributions of irreducible cyclic codes. The term ‘generalised Hamming weight’ was introduced by Wei in 1991 [14]. He used the parameters to analyse an application of codes on the Wire-Tap Channel of type II, which had been introduced in 1984 by Ozarow and Wyner [11]. During the nineties, several researchers have studied the generalised Hamming weights of linear codes.

The chain condition was introduced by Wei and Yang [15]. Chen and Kløve [2] introduced the opposite extreme, extremal non-chain codes. Known codes with high generalised Hamming weights tend to satisfy the chain condition. Cohen et al. [6] argue that some non-chain codes may have other advantages. Our interest is purely mathematical however.

Chen and Kløve found tight upper bounds for non-binary, four-dimensional, extremal non-chain codes [2]. Later they have also found all possible weight hierarchies of four-dimensional binary codes [5]. In this paper we generalise

Preprint submitted to Elsevier Preprint 9th October 2000

their upper bounds to arbitrary dimension, and these bounds are the best possible in dimension 5 and lower.

1.1 Notation and definitions

Throughout this paper C will denote an [n, k + 1; q] code, i.e. a linear code of length n and dimension k + 1 over the Galois field GF(q) with q elements. Codes of dimension k + 1 will be studied in a projective space PG(k, q) of dimension k and order q.

Given a code C we define the support χ(C) to be the set of positions where not all codewords of C are zero, i.e.

χ(C) := {i | ∃(x_{1}, x_{2}, …, x_{n}) ∈ C, s.t. x_{i} ≠ 0}.

The support weight of C is the size of χ(C), and we denote it w_{S}(C), i.e.

w_{S}(C) := #χ(C).

For 0 ≤ r ≤ k +1, the rth generalised Hamming weight d_{r} of C is the least support weight of an r-dimensional subcode of C. The sequence (d_{1}, d_{2}, …, d_{k+1}) is called the weight hierarchy of C. The minimum weight of the code is d = d_{1}.

We note that by adding a zero-position to C, we get an [n + 1, k + 1; q] code with the same weight hierarchy as C. Without loss of generality, we can restrict our study to codes without zero-positions. In other words, we assume that d_{k+1} = n.

Two linear codes are equivalent if one can be obtained from the other by permuting coordinate positions or by multiplying some coordinate by a nonzero scalar. We note that equivalent codes have the same weight hierarchy.

1.2 Codes in projective geometry

We let G denote a generator matrix of C. The value (or multiplicity) ν(x) of x ∈ GF(q)^{k+1} is the number of occurrences of x as a column in G. Replacing some column x with ax for some non-zero scalar a leads to an equivalent code. Thus we can consider the columns of G to be projective points, and an equivalence class of codes is uniquely determined by giving the map

ν : PG(k, q) ⟶ ℕ_{0} := {0, 1, …}.

This concept has been studied by several authors using different terminology. Dodunekov and Simonis [7] give an historic overview, and they prefer to call ν a projective multiset. In this paper we prefer to call it a value assignment, as did Chen and Kløve [2]. Tsfasman and Vladuţ [13] studied an equivalent concept called a projective system.

An arbitrary map ν : PG(k, q) ⟶ ℕ_{0} is called a value assignment even if it is not defined from a code. We call it non-degenerate if there are k + 1 projectively independent points p_{0}, p_{1}, …, p_{k} such that ν(p_{i}) ≥ 1 for all i. By taking ν(x) not necessarily distinct representatives for each projective point and taking an ordering on all these representatives, we get a matrix G. This matrix G is a generator matrix of a code if and only if its rank is k + 1, that is if ν is non-degenerate.

We define the value of a set of points as follows

ν(U) := ∑_{x∈U} ν(x), ∀ U ⊆ PG(k, q).

Let PG^{(m)}(k, q) be the set of m-spaces or m-dimensional subspaces of PG(k, q). Note that PG^{(0)}(k, q) is the collection of subsets of cardinality 1; both P ∈ PG(k, q) and {P } ∈ PG^{(0)}(k, q) will be called a point. The 1-, 2- and (k − 1)- spaces are called lines, planes, and hyperplanes, respectively. The only (−1)- space is the empty set.

The join of Π_{r} and Π_{s}, denoted Π_{r}Π_{s}, is the intersection of all subspaces containing the union Π_{r} ∪ Π_{s}. If p_{0}, p_{1}, …, p_{m} ∈ PG(k, q) are projectively independent points, we write ⟨p_{0}, p_{1}, …, p_{m}⟩ for their join. We define the following shorthand notation,

θ(n) := \frac{q^{n+1} − 1}{q − 1} = ∑_{i=0}^{n} q^{i},

and recall that θ(k) is the cardinality of PG(k, q).

1.3 Subcodes and the value assignments

From now on we let ν : PG(k, q) → ℕ_{0} be the value assignment corresponding to C. There is a one-to-one correspondence between subcodes of C of dimension r and subspaces of PG(k, q) of dimension k − r. We write D^{∗} for the projective subspace corresponding to a subcode D ⊆ C, and Π^{∗} for the subcode corresponding to Π ⊆ PG(k, q). If D_{1} ⊆ D_{2}, then D_{1}^{∗} ⊇ D_{2}^{∗}. It is known [9,13] that d_{k+1} − w_{S}(D) = ν(D^{∗}).

We define the weight hierarchy (d_{1}, …, d_{k+1}) of a value assignment ν by letting n − d_{r} be the greatest value of a subspace of codimension r in PG(k, q). Obviously the correspondence between value assignments and codes preserves the weight hierarchy. Note that a value assignment is non-degenerate if and only if d_{1} > 0. All value assignments encountered in this paper are non-degenerate.

The difference sequence (δ_{0}, δ_{1}, … δ_{k}) of a code or of a value assignment is defined by

δ_{j} := d_{k+1−j} − d_{k−j}, j = 0, 1, …, k.

We note that the difference sequence is easily computed from the weight hierarchy and vice versa. We say that the difference sequence (δ_{0}, δ_{1}, … δ_{k}) has dimension k + 1. The elements of the difference sequence of a code or nondegenerate value assignment are positive, due to the strict monotonicity of the generalised Hamming weights.

The existence of a linear code with weight hierarchy (d_{1}, d_{2}, …, d_{k+1}) is equivalent to the existence of a non-degenerate value assignment ν such that,

max{ν(Π_{m}) | Π_{m} ∈ PG^{(m)}(k, q)} = ∑_{i=0}^{m} δ_{i}, −1 ≤ m ≤ k.

The set of m-spaces of maximum value is denoted by M_{m},

M_{m}(ν) := {Π_{m} | Π_{m} ∈ PG^{(m)}(k, q) ∧ ν(Π_{m}) = ∑_{i=0}^{m} δ_{i}}, −1 ≤ m ≤ k.

When no ambiguity is expected, we write M_{m} = M_{m}(ν).

Given an m-space Π_{m} ∈ PG^{(m)}(k, q), we can restrict the value assignment ν to this subspace and study

ν′ = ν|_{Π_{m}} : Π_{m} → ℕ_{0}.

If Π_{m} ∈ M_{m}(ν), the monotonicity of the weight hierarchy ensures that any proper subspace of Π_{m} has lower value. In this case ν′ is non-degenerate, and thus defines a code D, which is actually the code obtained by puncturing C on each coordinate in χ(Π_{m}^{∗}). We write M_{i}(Π_{m}) M_{i}(ν|_{Π_{m}}) for −1 ≤ i ≤ m.

1.4 The Chain Condition

The chain condition was introduced by Wei and Yang [15], and it says that

∀ i s.t. 0 ≤ i ≤ k − 1 ∃ Π_{i} ∈ M_{i} s.t. Π_{0} ⊂ Π_{1} ⊂ … ⊂ Π_{k−1}.

We will refer to codes satisfying this condition as chained codes.

We define a number of subconditions, which are implications of the chain condition. For all i and j such that 0 ≤ i < j ≤ k − 1, we have the condition,

(Ci.j) : ∃Π_{i} ∈ M_{i} ∃Π_{j} ∈ M_{j} s.t. Π_{i} ⊂ Π_{j}.

The negations of these conditions, (Ni.j) := ¬(Ci.j), will be called non-chain conditions.

Analogous to the definition by Chen and Kløve [2], we define extremal nonchain codes of arbitrary dimension to be codes that satisfy all of the non-chain conditions (Ni.j). The difference sequence of an extremal non-chain code will be called an ENDS (extremal non-chain difference sequence).

2 Upper bounds

2.1 The general upper bound

Theorem 1 If (δ_{0}, δ_{1}, … δ_{k}) is an ENDS and 1 ≤ m ≤ k − 1, then

δ_{m} ≤ q^{m}δ_{0} − ∑_{i=0}^{m} q^{i}.

If this bound holds with equality for m = m̄ > 1, then it also holds with equality for m = m̄ − 1.

The proof of this theorem is quite tedious, and we have to start with some auxiliary results.

Definition 2 We say that an ENDS is m-optimal, 1 ≤ m ≤ k − 1, if it satisfies the bound on δ_{m} from Theorem 1 with equality. An extremal nonchain code C is m-optimal if its difference sequence is an m-optimal ENDS.

Lemma 3 Given an arbitrary code with difference sequence (δ_{0}, δ_{1}, … δ_{k}), we have δ_{k} ≤ qδ_{k−1}.

PROOF. Take some Π_{k−2} ∈ M_{k−2}. There are q + 1 (k − 1)-spaces through Π_{k−2}, and for every such subspace Π_{k−1} we have

ν(Π_{k−1}\Π_{k−2}) ≤ δ_{k−1}.

The geometry is partitioned into q +1 disjoint subsets of the form Π_{k−1}\Π_{k−2}, beside Π_{k−2}. Hence

∑_{i=0}^{k} δ_{i} ≤ (q + 1)δ_{k−1} + ∑_{i=0}^{k−2} δ_{i}.

The lemma follows immediately. □

Lemma 4 Let (δ_{0}, δ_{1}, … δ_{k}) be the difference sequence of some non-degenerate value assignment ν, and (δ′_{0}, …, δ′_{k−1}) the difference sequence of ν|_{Π_{k−1}} for some Π_{k−1} ∈ M_{k−1}. Then δ_{k−1} ≤ δ′_{k−1}.

PROOF. We have Π_{k−1} ∈ M_{k−1}(Π_{k−1}) ⊆ M_{k−1}(ν). Let Π_{k−2} ∈ M_{k−2}(ν) and Π′_{k−2} ∈ M_{k−2}(Π_{k−1}). Clearly ν(Π′_{k−2}) ≤ ν(Π_{k−2}). Hence

δ_{k−1} = ν(Π_{k−1}) − ν(Π_{k−2}) ≤ ν(Π_{k−1}) − ν(Π′_{k−2}) = δ′_{k−1},

as required. □

Lemma 5 Let ν be the value assignment of an extremal non-chain code with difference sequence (δ_{0}, δ_{1}, … δ_{k}). If Π_{m} ∈ M_{m} where 0 ≤ m ≤ k and ν|_{Π_{m}} has difference sequence (ε_{0}, ε_{1}, …, ε_{m}), then δ_{m} ≤ ε_{m} − 1.

PROOF. This goes almost like the proof of Lemma 4, except that since the code is extremal non-chain, we get a stronger bound. We have Π_{m} ∈ M_{m}(Π_{m}) ⊆ M_{m}(ν). Let Π_{m−1} ∈ M_{m−1}(ν) and Π′_{m−1} ∈ M_{m−1}(Π_{m}). Since the code is extremal non-chain, we have ν(Π′_{m}) < ν(Π_{m}). Hence

δ_{m} = ν(Π_{m}) − ν(Π_{m−1}) ≤ ν(Π_{m}) − (ν(Π′_{m−1}) + 1) = ε_{m} − 1,

as required. □

Lemma 6 If k ≥ 2 and (δ_{0}, δ_{1}, … δ_{k}) satisfies (N0.1), then δ_{1} ≤ qδ_{0} − (q + 1) and δ_{0} ≥ 2.

PROOF. A line consists of q+1 points, and by (N0.1), δ_{1}+δ_{0} ≤ (q+1)(δ_{0}−1). Hence δ_{1} ≤ qδ_{0} − (q + 1). Also if δ_{0} ≤ 1, then δ_{1} ≤ −1, which is absurd. □

Proof of Theorem 1. The proof goes by induction on m, so we assume that the theorem holds for every m < m̄. Lemma 6 proves it for m = 1. Now we consider a code C such that

δm̄ ≥ qm̄δ_{0} − θ(m̄)  (1)
δ_{m} ≤ q^{m}δ_{0} − θ(m), ∀m ≤ m̄ − 1.  (2)

Our aim is to prove that then we must have equality both in (1) and in (2). Take an arbitrary Θm̄ ∈ Mm̄(C), and let

Θ_{0} ⊂ Θ_{1} ⊂ … ⊂ Θ_{m̄−1} ⊂ Θm̄

be a chain such that Θ_{i} ∈ M_{i}(Θ_{i+1}) for 0 ≤ i ≤ m̄ − 1. Let (ε_{0}^{(i)}, …, ε_{i}^{(i)}) be the difference sequence of ν|_{Θ_{i}}. By Lemma 5 and (1), we get

ε(m̄) ; m̄ ≥ δm̄ + 1 ≥ qm̄δ_{0} − θ(m̄) + 1.  (3)

Lemma 4 and 3 give

ε_{m̄−1}^{(m̄−1)} ≥ ε_{m̄−1}^{(m̄)} ≥ ⌈\frac{ε(m̄) ; m̄}{q} ⌉ .  (4)

Repeating this argument m̄ times and substituting from (3), we obtain

ε_{0}^{(0)} ≥ ⌈\frac{ε(m̄) ; m̄}{qm̄} ⌉ ≥ ⌈\frac{qm̄δ_{0} − θ(m̄) + 1}{qm̄}⌉ = δ_{0} − 1.

Clearly ε_{0}^{(0)} is the value of Θ_{0}, which is a point in Θm̄ ∈ Mm̄(C). Since C is extremal non-chain, we have ε_{0}^{(0)} ≤ δ_{0} − 1. We conclude that

ε_{0}^{(l)} = ν(Θ_{0}) = δ_{0} − 1, ∀l, 0 ≤ l ≤ m̄.  (5)

We assume for induction on j that for all j < i where 0 < i < m̄, we have

ε_{j}^{(l)} = ε_{j}^{(j)} = q^{j}δ_{0} − θ(j), ∀l, s.t. j ≤ l ≤ m̄.  (6)

First we prove that it also holds for l = j = i. Repeating the argument of (4) m̄ − i times, we get

ε_{i}^{(i)} ≥ ⌈\frac{ε(m̄) ; m̄}{q^{m̄−i}} ⌉ ≥ ⌈\frac{qm̄δ_{0} − θ(m̄) + 1}{q^{m̄−i}}⌉ = q^{i}δ_{0} − θ(i).  (7)

Now ε_{i}^{(i)} = ν(Θ_{i}) − ν(Θ_{i−1}). Since C is extremal non-chain, we get by (2) that

ν(Θ_{i}) ≤ ∑_{j=0}^{i} δ_{j} − 1 ≤ ∑_{j=0}^{i}[q^{j}δ_{0} − θ(j)],

and according to the induction hypothesis (6), we have

ν(Θ_{i−1}) = ∑_{j=0}^{i−1} ε_{j}^{(i−1)} = ∑_{j=0}^{i−1} ε_{j}^{(j)} = ∑_{j=0}^{i−1}[q^{j}δ_{0} − θ(j)].  (8)

Combining these expressions, we get an upper bound on ε_{i}^{(i)}:

\begin{aligned}ε_{i}^{(i)} & = ν(Θ_{i}) − ν(Θ_{i−1}) \\ & ≤ ∑_{j=0}^{i}[q^{j}δ_{0} − θ(j)] − ∑_{j=0}^{i−1}[q^{j}δ_{0} − θ(j)] = q^{i}δ_{0} − θ(i). \end{aligned}  (9)

Combining the upper and lower bounds (7) and (9), we conclude by induction that

ε_{i}^{(i)} = q^{i}δ_{0} − θ(i), i = 0, …, m̄ − 1.  (10)

From (8) and (2) we can see that

∑_{j=0}^{i−1} δ_{j} − 1 ≥ ν(Θ_{i−1}) = ∑_{j=0}^{i−1}[q^{j}δ_{0} − θ(j)] ≥ ∑_{j=0}^{i−1} δ_{j} − 1,

Hence δ_{i−1} = q^{i−1}δ_{0} − θ(i − 1). Also

ε_{i}^{(i)} + ν(Θ_{i−1}) = q^{i}δ_{0} − θ(i) + ν(Θ_{i−1}) = ν(Θ_{i}) ≤ ∑_{j=0}^{i} δ_{j} − 1.

Hence q^{i}δ_{0} − θ(i) ≤ δ_{i}, and combining with (2), we get δ_{i} = q^{i}δ_{0} − θ(i).

It follows from this argument that Θ_{i} ∈ M_{i}(Θ_{l}) and Θ_{i−1} ∈ M_{i−1}(Θ_{l}), for all l such that i ≤ l ≤ m̄, and hence ε_{i}^{(l)} = ε_{i}^{(i)}. It follows by induction that δ_{i} = q^{i}δ_{0} − θ(i) for i = 1, 2, …, m̄ − 1.

We have

ε(m̄) ; m̄ = ν(Θm̄) − ν(Θ_{m̄−1}) = ∑_{i=0}^{m̄} δ_{i} − ( ∑_{i=0}^{m̄−1} δ_{i} − 1) = δm̄ + 1,

and by Lemmas 3 and 4 and (10), we get

δm̄ + 1 = ε(m̄) ; m̄ ≤ qε_{m̄−1}^{(m̄)} ≤ qε_{m̄−1}^{(m̄−1)} = qm̄δ_{0} − θ(m̄) + 1.

Combining with the lower bound from (1) we get

δm̄ = ε(m̄) ; m̄ − 1 = qm̄δ_{0} − θ(m̄),

and the theorem follows by induction. □

[figure: T_{1}; S_{1}; P; L_{1}; L_{2}; Π_{1}; L_{1}; L_{2}]

Figure 1. Representation of PG(4, 2) for the proof of Theorem 9. Black lines are in Π_{3}, dashed lines in Π_{2}, and dotted lines are in neither. White points are in Π_{1}. The point L_{1} and Π_{1} span L_{1}, and L_{2} and Π_{1} span L_{2}.

Corollary 7 Let C be an m-optimal code with difference sequence (δ_{0}, δ_{1}, … δ_{k}) for some m such that 1 ≤ m ≤ k − 1. For every Π_{m} ∈ M_{m}, ν|_{Π_{m}} corresponds to a chained code with difference sequence (δ_{0} − 1, δ_{1}, δ_{2}, …, δ_{m−1}, δ_{m} + 1).

PROOF. In the proof of Theorem 1 we proved that Θ_{i} ∈ M_{i}(Θ_{m}) = M_{i}(Π_{m}), and we found the difference sequence as given in the corollary. □

Remark 8 We know from Lemma 6 that δ_{0} ≥ 2, so the difference sequence has only positive elements as expected. Writing

(ε_{0} = δ_{0} − 1, ε_{1} = δ_{1}, …, ε_{m−1} = δ_{m−1}, ε_{m} = δ_{m} + 1)

for the difference sequence of ν|_{Π_{m}}, we have ε_{i} = qε_{i−1} − 1 for i = 1, …, m − 1 and ε_{m} = qε_{m−1}.

2.2 Binary case

For binary codes we have a special bound, which also implies that binary codes cannot be (k − 1)-optimal if k ≥ 3.

Theorem 9 If (δ_{0}, δ_{1}, … δ_{k}), k ≥ 3, is a binary ENDS, then

δ_{k−1} ≤ 2^{k−2}δ_{1} − 2 − 2^{k−2}.

PROOF. Take Π_{k−1} ∈ M_{k−1} and Π_{k−2} ∈ M_{k−2}, and let

Π_{k−3}P i_{k−1} ∩ Π_{k−2}.

Because the code is extremal non-chain, Π_{k−3} is a (k − 3)-space. Also let {P } ∈ M_{0}.

Define

S := Π_{k−2}\Π_{k−3} = {S_{i} | i = 1, 2, …, 2^{k−2}},
ℓ_{i} := ⟨P, S_{i}⟩ = {P, S_{i}, T_{i}}, i = 1, 2, …, 2^{k−2}.

Every line through P meets Π_{k−1}, so the points T_{i} are in Π_{k−1}. Define the set

T := {T_{i} | i = 1, 2, …, 2^{k−2}}.

Because the code is an ENDS, ν(ℓ_{i}) ≤ δ_{0} + δ_{1} − 1 for all i. Hence

ν(T_{i}) ≤ δ_{1} − ν(S_{i}) − 1, i = 1, 2, …, 2^{k−2},
ν(T ) ≤ 2^{k−2}δ_{1} − ν(S) − 2^{k−2}.

We know that

ν(Π_{k−2}) = ν(S) + ν(Π_{k−3}) = ∑_{i=0}^{k−2} δ_{i},

so

ν(T ) − ν(Π_{k−3}) ≤ 2^{k−2}δ_{1} − 2^{k−2} − ∑_{i=0}^{k−2} δ_{i}.

The join of {P } and Π_{k−2} is a (k − 1)-space, intersecting Π_{k−1} in a (k − 2)- space, namely T ∪Π_{k−3}. Let L_{1} and L_{2} be the other two distinct (k−2)-spaces such that Π_{k−3} ⊂ L_{i} ⊂ Π_{k−1} for i = 1, 2.

Now we have

\begin{aligned}∑_{i=0}^{k−1} δ_{i} = ν(Π_{k−1}) & = ν(L_{1}) + ν(L_{2}) − ν(Π_{k−3}) + ν(T ) \\ & ≤ 2 (∑_{i=0}^{k−2} δ_{i} − 1) + 2^{k−2}δ_{1} − 2^{k−2} − ∑_{i=0}^{k−2} δ_{i}. \end{aligned}

This is simplified to

δ_{k−1} ≤ 2^{k−2}δ_{1} − 2^{k−2} − 2,

and the theorem is proved. □

2.3 Bounds on the total value

Theorem 10 (Total value) If k ≥ 2, 1 ≤ m ≤ k − 1, and (δ_{0}, δ_{1}, … δ_{k}) satisfies (Nm − 1.m), then

ν(PG(k, q)) ≤ ∑_{i=0}^{m−1} δ_{i} + (δ_{m} − 1) ∑_{i=0}^{k−m} q^{i}.

PROOF. Let α ∈ M_{m−1}. In PG(k, q) there are θ(k − m) m-spaces containing α, and for every such m-space β ⊃ α, we know by condition (Nm − 1.m) that

ν(β\α) ≤ δ_{m} − 1.

Thus ν(PG(k, q)\α) ≤ (δ_{m} − 1)θ(k − m). By the definition of α, we know that

ν(α) = ∑_{i=0}^{m−1} δ_{i},

and the theorem follows. □

For an ENDS, several bounds may be derived from the above theorem. Corollary 11 is the best possible bound for (k −1)-optimal codes, while Corollary 12 is stronger for binary codes.

Corollary 11 If (δ_{0}, δ_{1}, … δ_{k}) is a difference sequence satisfying (N0.1) and k ≥ 2, then

ν(PG(k, q)) ≤ δ_{0} + (δ_{1} − 1) ∑_{i=0}^{k−1} q^{i} ≤ ∑_{i=0}^{k} q^{i}δ_{0} − (q + 2) ∑_{i=0}^{k−1} q^{i}.

The bound holds with equality if and only if every line through X ∈ M_{0} has value (q + 1)δ_{0} − (q + 2).

Corollary 12 If (δ_{0}, δ_{1}, … δ_{k}), k ≥ 2, satisfies (Nk − 2.k − 1), then δ_{k} ≤ qδ_{k−1} − (q + 1).

Theorem 13 Let 2 ≤ k ≤ 4. Then the given bounds on δ_{1} through δ_{k} are the best possible. In particular there exists a construction meeting the bounds with equality if and only if the following constraint on δ_{0} is met

δ_{0} ≥ 3 if q = 2 ∧ k = 2
δ_{0} ≥ 5 if q = 2 ∧ k = 3
δ_{0} ≥ 4 if q = 2 ∧ k = 4
δ_{0} ≥ 2 if q = 3 ∧ k = 2
δ_{0} ≥ 3 if q = 3 ∧ k = 3, 4
δ_{0} ≥ 2 if q ≥ 4 ∧ k = 2, 3
δ_{0} ≥ 3 if q ≥ 4 ∧ k = 4.

The theorem has been proved by giving explicit constructions. Chen and Kløve proved it for k = 3 and q ≥ 3 in [2] and for k = 3 and q = 2 in [5]. It was proved for k = 4 in [12]. The example below shows it for k = 2. For k ≤ 1, there are no non-chain conditions.

Example 14 An optimal ENDS in PG(2, q) is easily obtained as follows. Let ℓ be a line, and X ∉ ℓ a point. Let ν(X) = δ_{0}. Consider each line α ∋ X. If q ≥ 3, we choose two points in α\({X}∪ℓ) to have value δ_{0} −2. All remaining points have value δ_{0} − 1. Note that δ_{0} ≥ 2.

If q = 2, there is only one point in α\({X} ∪ ℓ), so that point must have value δ_{0} − 3, thus δ_{0} ≥ 3.

3 Structure of optimal codes

In this section we will find further necessary conditions for an extremal nonchain code to be m-optimal. For instance if H ∈ M_{3} is a 3-space of maximum value, then there are a line ℓ ⊆ H and a plane P ⊆ H such that

ν(p) = δ_{0} − 3 ∀p ∈ ℓ ∩ P
ν(p) = δ_{0} − 2 ∀p ∈ ℓ ∪ P, p ∉ ℓ ∩ P
ν(p) = δ_{0} − 1  otherwise.

The general result is stated in Theorem 26.

Lemma 15 If δ_{i} = qδ_{i−1} − 1 for i = 1, …, k, then

∑_{i=m}^{k} δ_{i} = θ(k − m)δ_{m} − ∑_{i=0}^{k−m−1} θ(i), 0 ≤ m ≤ k.

PROOF. The equality follows immediately from the fact that if 0 ≤ i ≤ m ≤ k, then

δ_{m} = q^{i}δ_{m−i} − θ(i − 1).

□

Lemma 16 If 0 ≤ a ≤ q − 1, then

θ(m) − a ∑_{i=0}^{m−1} θ(i) ≥ 1.

PROOF. We write

\begin{aligned}θ(m) − a ∑_{i=0}^{m−1} θ(i) & = θ(m) − \frac{a}{q − 1} ∑_{i=0}^{m−1}(q^{i+1} − 1) \\ & = θ(m) − \frac{a}{q − 1}(θ(m) − 1 − m) ≥ 1. \end{aligned}

□

Lemma 17 Let ν be a value assignment with difference sequence (δ_{0}, δ_{1}, …, δ_{k}) where δ_{i} = qδ_{i−1} −1 for i = 1, …, k −1. If Π_{m} ∈ M_{m}, then ν|_{Π_{m}} has difference sequence (δ_{0}, δ_{1}, …, δ_{m}).

PROOF. The proof is trivial for m = k, so assume m < k. Let

∅ = Θ_{−1} ⊂ Θ_{0} ⊂ Θ_{1} ⊂ … ⊂ Θ_{m} = Π_{m}

be a chain of subspaces such that Θ_{i} has the greatest value among the i-spaces containing Θ_{i−1} in Π_{m}. Define δ′_{i} = ν(Θ_{i}) − ν(Θ_{i−1}).

Let (δ′′_{0}, δ′′_{1}, …, δ′′_{m}) be the difference sequence of ν|_{Π_{m}}. It is sufficient to prove that δ′_{i} = δ_{i} for all i, because

∑_{i=0}^{j} δ′_{i} ≤ ∑_{i=0}^{j} δ′′_{i} ≤ ∑_{i=0}^{j} δ_{i}, 0 ≤ j ≤ m.  (11)

Suppose for contradiction that there is an i such that δ_{i} ≠ δ′_{i}. Let l be the smallest such i. Note that δ′_{l} < δ_{l} by (11).

Since there are only θ(m − l) distinct l-spaces containing Θ_{l−1} in Π_{m}, we get

ν(Π_{m}) ≤ θ(m − l)δ′_{l} + ∑_{i=0}^{l−1} δ′_{i} ≤ θ(m − l)(δ_{l} − 1) + ∑_{i=0}^{l−1} δ_{i}.

Also note that by Lemma 15,

ν(Π_{m}) = θ(m − l)δ_{l} − ∑_{j=0}^{m−l−1} θ(j) + ∑_{i=0}^{l−1} δ_{i}.

Combine the two lines to get

θ(m − l)δ_{l} − ∑_{j=0}^{m−l−1} θ(j) + ∑_{i=0}^{l−1} δ_{i} ≤ θ(m − l)(δ_{l} − 1) + ∑_{i=0}^{l−1} δ_{i},

which is equivalent to

θ(m − l) − ∑_{j=0}^{m−l−1} θ(j) ≤ 0,

contradicting Lemma 16. □

Corollary 18 Any code with difference sequence (δ_{0}, δ_{1}, …, δ_{k}) such that δ_{i} = qδ_{i−1} − 1 for i = 1, …, k − 1 satisfies the chain condition.

Lemma 19 Let ν be a value assignment with difference sequence (δ_{0}, δ_{1}, … δ_{k}) such that δ_{k} = qδ_{k−1}. For every (k − 1)-space Π_{k−1} ⊃ Π_{k−2} ∈ M_{k−2}, we have Π_{k−1} ∈ M_{k−1}.

PROOF. Consider Π_{k−2} ∈ M_{k−2}. Let B_{0}, …, B_{q} be the (k − 1)-spaces such that Π_{k−2} ⊂ B_{j}, j = 0, …, q. We get

ν(PG(k, q)) = ∑_{j=0}^{q} ν(B_{j}\Π_{k−2}) + ν(Π_{k−2}) = ∑_{j=0}^{k} δ_{j}.

Since δ_{k} = qδ_{k−1}, we get that

(q + 1)δ_{k−1} = ∑_{j=0}^{q} ν(B_{j}\Π_{k−2}).

Comparing this with the fact that ν(B_{j}\Π_{k−2}) ≤ δ_{k−1} for all j, we get that B_{j} ∈ M_{k−1}, as required. □

We recall Corollary 7 and Remark 8 to get the following corollary.

Corollary 20 If (δ_{0}, δ_{1}, … δ_{k}) is a 1-optimal ENDS, k ≥ 2, and ℓ is line with value ν(ℓ) = δ_{0} + δ_{1}, then ν(p) = δ_{0} − 1 for all p ∈ ℓ.

Lemma 21 Let ν : PG(k, q) → ℕ_{0} be a value assignment with difference sequence (δ_{0}, δ_{1}, … δ_{k}) such that δ_{i} = qδ_{i−1} − 1, 1 ≤ i ≤ k. For every Π_{m−1} ∈ M_{m−1}, 0 ≤ m ≤ k, we have that

(a) the number of distinct m-spaces of maximum value through Π_{m−1} is at least

θ(k − m) − ∑_{j=0}^{k−m−1} θ(j).

(b) for m = k −1 there is a unique m-space Π_{m} ∉ M_{m} such that Π_{m−1} ⊂ Π_{m}, and

ν(Π_{m}) = ∑_{j=0}^{m} δ_{j} − 1.

PROOF. There are θ(k − m) m-spaces B_{i} ⊃ Π_{m−1}. We get that

ν(PG(k, q)) = ∑_{j=1}^{θ(k−m)} ν(B_{j}\Π_{m−1}) + ν(Π_{m−1}) = ∑_{j=0}^{k} δ_{j}.

and by Lemma 15,

∑_{j=1}^{θ(k−m)} ν(B_{j}\Π_{m−1}) = ∑_{j=m}^{k} δ_{j} = θ(k − m)δ_{m} − ∑_{j=0}^{k−m−1} θ(j).

Clearly

ν(B_{j}\Π_{m−1}) ≤ δ_{m}, 1 ≤ j ≤ θ(k − m).  (12)

Comparing the last two equations, we note that at least

θ(k − m) − ∑_{j=0}^{k−m−1} θ(j)

of the B_{i} give equality in (12). If m ≤ k − 1, then at least one of the B_{j} gives inequality. The case where m = k − 1, is just a special case where q of the B_{i} gives equality and one gives inequality. The exact value of the one with inequality is easily computed. □

Lemma 22 Let C be a code with difference sequence (δ_{0}, δ_{1}, … δ_{k}). If δ_{i} = qδ_{i−1} − 1 for i = 1, …, k, then there exists at most one point which is not contained in any element of M_{k−1}.

PROOF. Suppose there are two distinct points P, Q ∈ PG(k, q) which are not contained in any element of M_{k−1}. Consider a chain

Π_{0} ⊂ Π_{1} ⊂ … ⊂ Π_{k−1} ⊂ PG(k, q),

such that Π_{i} ∈ M_{i} for each i = 0, …, k − 1. Let ℓ spP, Q. Obviously there is a point S ∈ ℓ ∩ Π_{k−1}. By assumption P, Q ∉ Π_{k−1}, so S ≠ P and S ≠ Q.

We claim that we can assume that S ∉ Π_{k−2}. By Lemma 21b, there are q points in Π_{1} which are elements of M_{0}, so if S ∈ Π_{0}, we can replace Π_{0} by some other point which is in Π_{1} and in M_{0}. For all i such that 1 ≤ i ≤ k − 2, there are q i-spaces in M_{i} containing Π_{i−1} in Π_{i+1}. Thus if S ∈ Π_{i}\Π_{i−1}, we can replace Π_{i} with some other i-space, maintaining the chain. By induction we can assume that S ∉ Π_{k−2}, as required.

There are q + 1 distinct (k − 1)-spaces spanned by Π_{k−2} and a point on ℓ, and only one of these is not an element of M_{k−1} by Lemma 21b. Since ⟨P ⟩Π_{k−2} and ⟨Q⟩Π_{k−2} are two distinct (k − 1)-spaces, either P or Q is contained in some element of M_{k−1}. The lemma follows by contradiction. □

Lemma 23 Let ν be a value assignment with difference sequence (δ_{0}, δ_{1}, … δ_{k}) such that k ≤ 2 and δ_{i} = qδ_{i−1} − 1 for 1 ≤ i ≤ k. Then there exists a collection S containing exactly one i-space for each i = 0, …, k − 1 such that

ν(p) = δ_{0} − #{Π ∈ S | p ∈ Π}, ∀p ∈ PG(k, q).

PROOF. For k = 0 the result is trivial.

For k = 1 there are q + 1 points. By Lemma 21b there is one point P of value δ_{0} − 1 and q points of value δ_{0}. Hence S = {P } forms the required collection.

Consider k = 2. There is a point ℘ ∈ M_{0}. Let ℓ_{0}, …, ℓ_{q} be the distinct lines such that ℘ ⊂ ℓ_{i} for all i. One of these lines, say ℓ_{0}, has value δ_{1} +δ_{0} −1, while the remaining q lines have value δ_{0} + δ_{1} by Lemma 21b. This means that for 1 ≤ i ≤ q, there is exactly one point α_{i} ∈ ℓ_{i} such that ν(α_{i}) = δ_{0} − 1. There are at most two points in ℓ_{0} with value δ_{0} − 1 or less. The remaining points have value δ_{0}. Obviously, every line in PG(2, q) has value at most δ_{0} + δ_{1}, and hence has at least one point of value δ_{0} −1 or less. A set of q +2 points cannot meet every line in a plane unless it contains a line [10, Lemma 13.4(iv)]. It follows that there must be a line Π_{1} such that ν(p) ≤ δ_{0} − 1 for all p ∈ Π_{1}. Since ν(ℓ_{0}) = δ_{1} + δ_{0} − 1, there is either one point Π_{0} = Π_{1} ∩ ℓ_{0} which has value δ_{0} − 2 or two distinct points Π_{0} and Π_{1} ∩ ℓ_{0} of value δ_{0} − 1. In either case {Π_{0}, Π_{1}} forms the required collection S. □

Definition 24 (Projections) We define the projection π_{p} of PG(k, q) through the point p ∈ PG(k, q):

π_{p} : PG(k, q) → PG(k − 1, q),

by mapping distinct lines through p in PG(k, q) to distinct points in PG(k−1, q) such that coplanar lines are taken to collinear points. We define the projected value assignment

ν_{p} : PG(k − 1, q) → ℕ_{0},
ν_{p} : X ↦ ν(π_{p}^{−1}(X)\{p}).

The code corresponding to ν_{p} is the subcode ⟨p⟩^{∗} of codimension 1 [7].

Lemma 25 Let ν : PG(k, q) → ℕ_{0}, q ≥ 3, be the value assignment of a code C with difference sequence (δ_{0}, δ_{1}, … δ_{k}) such that δ_{i} = qδ_{i−1} − 1 for i = 1, …, k. Then there exists a collection S containing exactly one i-space for each i = 0, …, k − 1 such that

ν(p) = δ_{0} − #{Π ∈ S | p ∈ Π}, ∀p ∈ PG(k, q).

PROOF. Lemma 23 proves it for k < 3. Now assume that the lemma holds for k < n, and consider

ν : PG(n, q) → ℕ_{0}, n ≥ 3 ∧ q ≥ 3.

For Π_{k} ∈ M_{k}, k < n, let S(Π_{k}) be the collection S corresponding ν|_{Π_{k}}. By Lemma 17 ν|_{Π_{k}} has difference sequence (δ_{0}, δ_{1}, … δ_{k}). Thus S(Π_{k}) exists by the induction hypothesis, and it has the property given in the lemma. We define σ_{i}(Π_{k}) to be the i-space in S(Π_{k}).

Claim I If Θ_{1} ∈ M_{n−2} and Θ_{2} ∈ M_{n−1} such that Θ_{1} ⊂ Θ_{2}, then

σ_{i}(Θ_{1}) = Θ_{1} ∩ σ_{i+1}(Θ_{2}), 0 ≤ i ≤ n − 3.

We can use either S(Θ_{1}) or S(Θ_{2}) to express the value of a point p ∈ Θ_{1}. Hence

#{Π ∈ S(Θ_{1}) | p ∈ Π} = #{Π ∈ S(Θ_{2}) | p ∈ Π}.  (13)

For all i, σ′_{i} := σ_{i+1}(Θ_{2}) ∩ Θ_{1} is either an (i + 1)-space if σ_{i+1}(Θ_{2}) ⊆ Θ_{1}, or else an i-space. Equation (13) can only be satisfied for all p ∈ Θ_{1} if dim σ′_{i} = i for all i. Hence we can let σ′_{i} for i ≥ 0 be the elements of S(Θ_{1}), and the claim follows.

Claim II If 1 ≤ i ≤ n − 2, then there is an (i + 1)-space σ_{i+1} such that σ_{i}(A) ⊂ σ_{i+1} for all A ∈ M_{n−1}.

Consider P ∈ M_{n−3}, α_{0} ∈ M_{n−2}, A_{1}, …, A_{q} ∈ M_{n−1}, and an (n − 1)-space A_{0} ∉ M_{n−1} such that P ⊂ α_{0} ⊂ A_{j} for 0 ≤ j ≤ q. Since q ≥ 3, there are at least two distinct (n − 2)-spaces α_{1}, α_{2} ∈ M_{n−2} such that P ⊂ α_{j} ⊂ A_{1} and α_{0} ≠ α_{j} for j = 1, 2. There are also at least two distinct (n − 2)-spaces β_{1}, β_{2} ∈ M_{n−2} such that P ⊂ β_{j} ⊂ A_{2} and α_{0} ≠ β_{j} for j = 1, 2. Define σ_{i+1} sigma_{i}(A_{1})σ_{i}(A_{2}). We have A_{1} ∩ A_{2} = α_{0} ∈ M_{n−2}, so

σ_{i−1}(α_{0}) = σ_{i}(A_{1}) ∩ α_{0} = σ_{i}(A_{2}) ∩ α_{0} = σ_{i}(A_{1}) ∩ σ_{i}(A_{2}),

by Claim I. Since dim σ_{i−1}(α_{0}) = i − 1, we get dim σ_{i+1} = i + 1. It remains to prove that M_{n−1} = 𝔖 where

𝔖 := {A ∈ M_{n−1} | σ_{i}(A) ⊂ σ_{i+1}, 1 ≤ i ≤ n − 2}.

Consider the spaces α_{1}β_{1} and α_{2}β_{1}. At least one of them is a space in M_{n−1}, denote it B_{1}. Similarly, let B_{2} be either α_{1}β_{2} or α_{2}β_{2} such that B_{2} ∈ M_{n−1}. We have the following

B_{1} ∩ A_{1} = α_{j} ∈ M_{n−2}, j = 1 ∨ j = 2,
B_{1} ∩ A_{2} = β_{1} ∈ M_{n−2},
B_{2} ∩ A_{1} = α_{j} ∈ M_{n−2}, j = 1 ∨ j = 2,
B_{2} ∩ A_{2} = β_{2} ∈ M_{n−2}.

It follows that σ_{i}(B_{1}) ∩ σ_{i}(A_{1}) = σ_{i−1}(α_{j}) for j = 1 or j = 2, and σ_{i}(B_{1}) ∩ σ_{i}(A_{2}) = σ_{i−1}(β_{1}). Hence σ_{i}(B_{1}) meets σ_{i+1} in two distinct (i − 1)-spaces, and consequently σ_{i}(B_{1}) ⊂ σ_{i+1}. A similar argument holds for B_{2}, and hence σ_{i}(B_{2}) ⊂ σ_{i+1}.

At least one of the (n − 2)-spaces A_{3} ∩ B_{1} or A_{3} ∩ B_{2} is an element α′ ∈ M_{n−2}, because P = A_{3} ∩ B_{1} ∩ B_{2} ∈ M_{n−3}. It follows that σ_{i}(A_{3}) meets σ_{i+1} in at least two distinct (i − 1)-spaces, σ_{i−1}(α′) and σ_{i−1}(α_{0}). We conclude that σ_{i}(A_{3}) ⊂ σ_{i+1}. So far we have shown that

A_{1}, A_{2}, A_{3}, B_{1}, B_{2} ∈ 𝔖.

We note that if there are two distinct elements E_{1}, E_{2} ∈ 𝔖, and A ∈ M_{n−1} such that γ_{j} E_{j} ∩ A ∈ M_{n−2} for j = 1, 2 and γ_{1} ≠ γ_{2}, then σ_{i}(A) meets σ_{i+1} in two distinct (i − 1)-spaces σ_{i−1}(γ_{j}). Hence A ∈ 𝔖.

If there are three distinct elements E_{1}, E_{2}, E_{3} ∈ 𝔖 and A ∈ M_{n−3} such that the intersections E_{j} ∩ A are three distinct (n − 2)-spaces and

A ∩ ⋂_{j=1}^{3} E_{j} ∈ M_{n−3},

then at least two of the E_{j} meets A in distinct elements of M_{n−2}, and A ∈ 𝔖.

Consider an element A ∈ M_{n−1} such that

P ⊂ A ∉ {A_{1}, A_{2}, A_{3}, B_{1}, B_{2}}.

If α_{0} ⊄ A, then A meets A_{1}, A_{2}, and A_{3} in three distinct (n − 2)-spaces containing P, and thus A ∈ 𝔖. If α_{0} ⊂ A, then A meets A_{1}, B_{1}, and B_{2} in three distinct (n − 2)-spaces containing P and A ∈ 𝔖. Thus we have proved that if P ⊂ A ∈ M_{n−1}, then A ∈ 𝔖.

If A ∈ M_{n−1} such that P̄ P ∩ A ∈ M_{n−4}, then there is ξ ∈ M_{n−2} such that P ⊂ ξ and S := ξ ∩ A ∈ M_{n−3}. This is obvious from the fact that there are at least q^{2} − 1 (n − 2)-spaces of maximum value through P by Lemma 21, and at most q + 2 (n − 3)-spaces through P̄ in A that are not elements of M_{n−3}. Hence there are at least q^{2} − q − 3 ≥ 3 choices for ξ. There are at least three subspaces E_{j} ∈ M_{n−1}, j = 1, 2, 3, through ξ, and

A ∩ ⋂_{j=1}^{3} E_{j} = S ∈ M_{n−3}.

Hence A ∈ 𝔖.

Suppose for induction that if P ⊄ A ∈ M_{n−1} and there is R ⊆ P̄ P ∩ A such that R ∈ M_{j+1}, then A ∈ 𝔖. This was proved for j = n − 5 in the last paragraph. It even holds when n = 3, because if j = −2, then R = ∅ ∈ M_{−1}.

Consider A ∈ M_{n−1} such that there is R̄ ∈ M_{j} such that R̄ ⊂ P̄, but there is no R̄′ ∈ M_{j+1} such that R̄′ ⊆ P̄. Let R ∈ M_{j+1} be such that R̄ ⊂ R ⊂ P. We shall prove that there is ξ ∈ M_{n−2} such that R ⊂ ξ and ξ ∩ A ∈ M_{n−3}. This is sufficient because then there are q ≥ 3 elements of 𝔖 containing ξ by the induction hypothesis, and at least two of them meet A in elements of M_{n−2}.

We prove the existence of ξ by induction on m. Assume that

∃R_{m} ∈ M_{m}, s.t. R_{m} ∩ A ∈ M_{m−1}, j + 1 ≤ m ≤ n − 3.  (14)

Let R_{j+1} = R. By Lemma 21, there are at least

θ(n − (m + 1)) − ∑_{l=0}^{n−(m+1)−1} θ(l)

(m + 1)-spaces of maximum value through R_{m}. Of these at most

∑_{l=0}^{n−1−m−1} θ(l)

meet A in an m-space which does not have maximum value. Hence at least

θ(n − m − 1) − 2 ∑_{l=0}^{n−m−2} θ(l) ≥ 1

(m + 1)-spaces satisfy (14) by Lemma 16. By induction ξ R_{n−2} exists, and hence 𝔖 = M_{n−1}. This proves Claim II.

Claim III For all A ∈ M_{n−1}, 1 ≤ i ≤ n − 2, σ_{i}(A) = σ_{i+1} ∩ A.

By the previous claim it is sufficient to prove that σ_{i+1} ⊈ A. Assume for contradiction that the claim fails for some i, and let m be the largest such i. Let A ∈ M_{n−1} be such that σ_{m+1} ⊆ A. Let B ∈ M_{n−1} such that σ_{m}(A) ≠ σ_{m}(B). By Claim II we get that σ_{m}(B) ⊂ σ_{m+1} ⊆ A. Note that

#σ_{m}(B) = θ(m)
#(σ_{m}(A) ∩ σ_{m}(B)) ≤ θ(m − 1)
# ⋃_{j=0}^{m−1} σ_{j}(A) ≤ ∑_{j=0}^{m−1} θ(j).

Hence

#(σ_{m}(B)\ ⋃_{i=0}^{m} σ_{i}(A)) ≥ q^{m} − ∑_{j=0}^{m−1} θ(j) ≥ 1,

since q ≥ 3. It follows that there exists

p ∈ σ_{m}(B)\ ⋃_{i=0}^{m} σ_{i}(A).

Since the claim is assumed to hold for i > m, we have that

\begin{aligned}ν(p) & = δ_{0} − #\{i | p ∈ σ_{i}(B) ∧ 0 ≤ i ≤ n − 2\} \\ & ≤ δ_{0} − 1 − #\{i | p ∈ σ_{i+1} ∧ m + 1 ≤ i ≤ n − 2\} \end{aligned}

\begin{aligned}ν(p) & = δ_{0} − #\{i | p ∈ σ_{i}(A) ∧ 0 ≤ i ≤ n − 2\} \\ & = δ_{0} − #\{i | p ∈ σ_{i+1} ∧ m + 1 ≤ i ≤ n − 2\}, \end{aligned}

and these two equations contradict each other, proving Claim III.

We write

U := {σ_{0}(A) | A ∈ M_{n−1}}.

Lemma 22 says that at most one point is not contained in any element of M_{n−1}. This means that we can form the set

S′ = U ∪ {σ_{i} | i = 2, …, n − 1},

giving the value of all points but at most one by the formula

ν(p) = δ_{0} − #{Π ∈ S′ | p ∈ Π}.

Claim IV There is a line σ_{1} such that σ_{0}(A) ⊂ σ_{1} for all A ∈ M_{n−1}.

Take a point {F } ∈ M_{0} such that

F ∈ Π_{0} ⊂ Π_{1} ⊂ … ⊂ Π_{n−3} = P

is a chain of subspaces of maximum value. The projected value assignment ν_{F} defines an (n − 1)-dimensional subcode code with weight d_{n−1}. The difference sequence of ν_{F} is (δ_{1}, …, δ_{n}), because π_{F} (Π_{i}) ∈ M_{i−1}(ν_{F}) for 0 ≤ i ≤ n. By the induction hypothesis, there is a collection S(PG(n − 1, q)) of i-spaces σ_{i}(PG(n − 1, q)) for i = 0, …, n − 2 such that

ν_{F} (p) = δ_{1} − #{Π ∈ S(PG(n − 1, q)) | p ∈ Π}.

Clearly F ∉ Π for any Π ∈ S′. Hence π_{F} (σ_{i}) is an i-space. We get the following formula for the values of every point but at most one in PG(n − 1, q):

\begin{aligned}ν_{F} (p) & = qδ_{0} − #\{Π ∈ S′ | p ∈ π_{F} (Π)\} \\ & = δ_{1} − #\{Π ∈ S′\\{σ_{n−1}\} | p ∈ π_{F} (Π)\}. \end{aligned}

It follows that

π_{F} (σ_{i}) = σ_{i}(PG(n − 1, q)), 2 ≤ i ≤ n − 2
π_{F} (U) ⊆ σ_{1}(PG(n − 1, q)) ∪ σ_{0}(PG(n − 1, q)).

We have U ∩ α_{0} = ∅ by Claim I. It follows that σ_{0}(A_{i}) for i = 1, …, q are q distinct elements of U. Let U′ U\A_{0} be the set of these q points.

Now consider V = σ_{1}(PG(n − 1, q)) ∪ σ_{0}(PG(n − 1, q)), the inverse image of which must consist of points in U and points not contained in any element of M_{n−1}. In fact π_{F} (U′) ⊂ σ_{1}(PG(n − 1, q)). Hence U′ are coplanar points.

There are more chains

F ≠ F′ ∈ Π′_{0} ⊂ Π′_{1} ⊂ … ⊂ Π′_{n−3} ⊂ α_{0}

of subspaces of maximum value. By projecting through such a point F′, we can show that U′ is also contained in a plane which is not equal to the first. Hence U′ is contained in a line, which we denote σ_{1}, and π_{F} (σ_{1}) = σ_{1}(PG(n − 1, q))

We shall prove that U ∩ A_{0} ⊂ σ_{1}, and consequently that U ⊆ σ_{1}. This is trivial if U ∩ A_{0} = ∅. Otherwise consider an arbitrary point R ∈ U ∩ A_{0}. By the definition of U, there is G ∈ M_{n−1} such that R ∈ G. By Lemma 17 there is a subspace ρ ⊂ G such that ρ ∈ M_{n−2}. By the argument used to prove Lemma 22, we can choose ρ such that R ∉ ρ. Projecting through a couple of distinct points contained in M_{0} and in ρ, as we did in the previous paragraph, will show that R ∈ σ_{1}, as required. This proves Claim IV.

Claim V There is a point σ_{0} which is not contained in any element of M_{n−1}, and S := {σ_{i} | i = 0, …, n − 1} forms the required collection such that

ν(p) = δ_{0} − #{Π ∈ S | p ∈ Π}, ∀p ∈ Π_{n}.  (15)

First assume that σ_{0} does exist. We have proved that (15) holds for all points except possibly for σ_{0}. If it does fail for σ_{0}, it must give us a wrong value for ν(PG(n, q)), but

ν(PG(n, q)) = θ(n)δ_{0} − ∑_{Π∈S} #Π = θ(n)δ_{0} − ∑_{i=0}^{n−1} θ(i) = ∑_{i=0}^{n} δ_{i},

by Lemma 15, and that is correct. If σ_{0} did not exist, we would have no point in S, and the total value would not be correct. This completes the proof of Claim V and the lemma. □

Theorem 26 Let C be a chained, non-binary code with difference sequence (δ_{0}, δ_{1}, … δ_{k}). If

δ_{i} = qδ_{i−1} − 1, i = 1, …, k − 1,
δ_{k} = qδ_{k−1},

then there exists a collection S of exactly one i-space in PG(k, q) for each i = 1, …, k − 1, such that

ν(p) = δ_{0} − #{Π ∈ S | p ∈ Π}, ∀p ∈ PG(k, q).

PROOF. Lemma 25 says that for each Π_{k−1} ∈ M_{k−1}, there is a set S(Π_{k−1}) such that

ν(p) = δ_{0} − #{Π ∈ S(Π_{k−1}) | p ∈ Π}, ∀p ∈ Π_{k−1}.

Let σ_{i} denote the i-space in S. If k ≥ 3 we use the same argument as in the proof of Lemma 25, to show that

σ_{i} = ⋃_{Π∈M_{k−1}} σ_{i−1}(Π), i = 1, 2, …, k − 1.

Because every point is contained in some Π_{k−1} ∈ M_{k−1}, there is no point in S.

The cases for k ≤ 2 are just as simple as the proof of Lemma 23. □

This theorem will of course apply to every subspace Π_{m} ∈ M_{m}(C) for an moptimal, extremal non-chain code C, and this fact has been most useful to limit the search for m-optimal constructions

Corollary 27 If (δ_{0}, δ_{1}, … δ_{k}) is a 3-optimal ENDS where k ≥ 4 and q ≥ 3, then δ_{0} ≥ 3.

PROOF. Let Π_{3} ∈ M_{3}, and apply the theorem on ν|_{Π_{3}}. There is p ∈ Π_{3}, such that ν(p) = (δ_{0} − 1) − 2. □

4 Acknowledgement

The author wishes to thank prof. Torleiv Kløve for helpful comments and for suggesting the problem in the first place. An anonymous referee has also been to much help through very thorough comments and by pointing to the work by Dodunekov and Simonis [7].

References

[1] A. Beutelspacher. Blocking sets and partial spreads in finite projective spaces. Geometrica Dedicata, 9:425–449, 1980.

[2] 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, 8:379–386, 1997.

[3] Wende Chen and Torleiv Kløve. Bounds on the weight hierarchies of linear codes of dimension 4. IEEE Trans. Inform. Theory, 43(6):2047–2054, 1997.

[4] Wende Chen and Torleiv Kløve. Classification of the weight hierarchies of binary linear codes of dimension 4. Technical Report 147, Department of Informatics, University of Bergen, March 1998.

[5] Wende Chen and Torleiv Kløve. Weight hierarchies of extremal non-chain binary codes of dimension 4. IEEE Trans. Inform. Theory, 45(1):276–289, 1999.

[6] G. D. Cohen, S. B. Encheva, and G. Zémor. Antichain codes. Proc. IEEE Intern. Symp. Inform. Theory, page 232, August 1998. Full paper to appear in Designs, Codes and Cryptography.

[7] S. Dodunekov and J. Simonis. Codes and projective multisets. Electron. J. Combin., 5(1), 1998. Research Paper 37.

[8] T. Helleseth, T. Kløve, and J. Mykkeltveit. The weight distribution of irreducible cyclic codes with block lengths n_{1}((q^{l} − 1)/n). Discrete Mathematics, 18:179– 211, 1977.

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

[10] J. W. P. Hirschfeld. Projective Geometries over Finite Fields. Oxford University Press, second edition, 1998.

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

[12] Hans  Georg  Schaathun.  Upper

bounds on weight hierarchies of extremal non-chain codes. Technical Report 171, Department of Informatics, University of Bergen, 1999. Also available at http://www.ii.uib.no/∼georg/sci/inf/coding/public/.

[13] Michael A. Tsfasman and Serge G. Vlăduţ. Geometric approach to higher weights. IEEE Trans. Inform. Theory, 41(6, part 1):1564–1588, 1995.

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

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