Upper bounds on Weight Hierarchies of Extremal Non-Chain Codes

Hans Georg Schaathun^{∗}

27th May 1999

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 size of an r-dimensional subcode of C. The difference sequence (δ_{0}, δ_{1}, … δ_{k}) is defined by δ_{i} = d_{k−i} − d_{k−i−1}. An [n, k; q] code is extremal non-chain if for any r and s, where 1 ≤ r < s ≤ k, there are no subspaces R and S, such that R ⊂ S, dim R = r, dim S = s, w_{S}(R) = d_{r}, and w_{S}(S) = d_{s}.

We give upper bounds on difference sequences of such codes, give some general results about codes meeting these bounds with equality, and finally construct five-dimensional codes meeting the bounds with equality.

Keywords Weight hierarchy, chain condition, difference sequence

∗with Department of Informatics, University of Bergen, Bergen High Technology Center, N-5020 Bergen, Norway. Email: ⟨georg@ii.uib.no⟩.

Preface

In this report I present the most important results from my graduate thesis submitted December 1998. Chapter 2, however, has been almost completely rewritten to give stronger results. I am still not completely satisfied with Chapters 4 and 5, and I hope I some time can publish a more complete study of binary codes in the future.

Part II from my thesis is now omitted. It contained the description of the computer programs written and used during the project.

I would like to thank professor Torleiv Kløve for revising the text before publication. I have a special thanks for a very special group of friends where I found the strength to complete this work, and of course to the friend who brought us together, Jesus Christ.

georg, Bergen May 1999.

Contents

1 Introduction 1 1.1 Notations and definitions . . . . . . . . . . . . . . . . . . . . . 1 1.2 Historical overview . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Upper bounds on ENDS 9 2.1 The main theorem . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Structure of optimal codes . . . . . . . . . . . . . . . . . . . . 14 2.3 Upper bounds on the total value . . . . . . . . . . . . . . . . . 20

3 Construction of a non-binary ENDS 21 3.1 The assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Verifying the non-chain conditions . . . . . . . . . . . . . . . . 26 3.3 The conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Binary ENDS 31 4.1 General bounds . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Construction requirements . . . . . . . . . . . . . . . . . . . . 34 4.3 Lower bound on δ_{0} . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Binary Construction 39 5.1 The assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 39

A Index of Notations 45

Bibliography 47

Chapter 1

Introduction

In this first chapter, we start by developing notations and terminology suitable for studying weight hierarchies of codes of arbitrary dimension. In Section 1.2 we have a look at previous works on the topic, before we define the purpose of the report in Section 1.3.

1.1 Notations 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.

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

χ(C) =^{def} {i | ∃(x_{1}, x_{2}, … x_{k+1}) ∈ 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) =^{def} #χ(C).

For 0 ≤ r ≤ k + 1 the r-th generalised Hamming weight of C is defined by:

d_{r}(C) =^{def} min{w_{S}(D) | D is an [n, r; q] subcode of C}.
1

CHAPTER 1. INTRODUCTION

The sequence (d_{1}, d_{2}, … d_{k+1}) is called the weight hierarchy of C. We note that the minimum weight of the code is d = d_{1}. For completeness d_{0} = 0 is the support weight of the code consisting only of the zero codeword, 0.

We note that by adding a zero-position to C, we get an [n + 1, k + 1; q] code

C′ = {(c|0) | c ∈ C},

which has the same weight hierarchy as C. Therefore, without loss of generality, we can restrict our study to codes with no zero-position; that is, we assume that d_{k+1} = n.

The difference sequence (DS), (δ_{0}, δ_{1}, … δ_{k}), is defined by

δ_{j} =^{def} 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. Due to the strict monotonicity of the generalised Hamming weights, the elements of the difference sequence are positive.

We let G denote a generator matrix of C. For any x ∈ GF(q)^{k+1}, ν(x), the value (or multiplicity) of x, will be the number of occurrences of x as a column in G. We then extend the notion of value, so that the value of a set of vectors is the sum of the values of the vectors, i.e. define:

ν(U) =^{def} ∑_{x∈U} ν(x), ∀ U ⊆ GF(q)^{k+1}.

1.1.1 Codes in projective geometry

It is obvious that if y is a column in G and x = αy for some non-zero α ∈ GF(q), then we may replace y by x without affecting the weight hierarchy. Therefore, we will look at the vectors as projective points.

A value assignment is a function from a projective space to the set of natural numbers and zero, i.e.:

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

For any p ∈ PG(k, q), ν(p) will be called the value of p. The value assignment defines a generator matrix up to equivalence, and consequently it defines a code.

2

1.1. NOTATIONS AND DEFINITIONS

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-, 2and 3-spaces are called lines, planes and solids, respectively. A (k − 1)-space is called a prime or synonymously a hyperplane. The term hyperplane will in this report be used for 3-spaces in PG(4, q).

If Π_{r} and Π_{s} are subspaces of PG(k, q), we know that their intersection, Π_{r} ∩ Π_{s}, is also a subspace. The join of Π_{r} and Π_{s}, denoted Π_{r}Π_{s}, is the intersection of all subspaces containing the union, Π_{r} ∪ Π_{s}. Obviously Π_{r}Π_{s} is a subspace, and we know that

dim Π_{r} + dim Π_{s} = dim Π_{r}Π_{s} + dim Π_{r} ∩ Π_{s},

where dim Π denotes the dimension of Π.

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 say that the points p_{i} span the subspace. We reserve the notation for projectively independent points, so ⟨p_{0}, p_{1}, … p_{m}⟩ has dimension m.

We define the following shorthand notation:

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

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

It is a well known fact that the smallest subset of a projective space, intersecting any line in at least one point, is a prime. More generally we know that if L is a set of points in PG(n, q) such that, for any r-space Π_{r}, #(L ∩ Π_{r}) ≥ Q(s), then #L ≥ Q(n − r + s). Also #L = Q(n − r + s) if and only if L is a (n − r + s)-space. (See [Hir98] pp. 87-88 for a proof.)

A subset meeting any t-space in at least one point, without containing any (k − t)-space is called a t-blocking set. Beutelspacher [Beu80] proved that if L is a t-blocking set in PG(t + 1, q), then

#L ≥ Q(t) + q^{t−1}\sqrt{q}.

1.1.2 Subcodes and the value assignments

Helleseth et al. [HKY92] showed that there is a one-to-one correspondence between subcodes D of C of dimension r and subspaces U of GF(q)^{k+1} of dimension k + 1 − r, such that d_{k+1} − w_{S}(D) = ν(U).

3

Using our projective representation, we have equivalently a one-to-one correspondence between subcodes Dof dimension r and subspaces Π_{m} ∈ PG^{(m)}(k, q), where m = k − r, such that d_{k+1} − w_{S}(D) = ν(Π_{m}).

This means that the existence of a weight hierarchy (d_{1}, d_{2}, …, d_{k+1}) is equivalent to the existence of a value assignment ν, such that:

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

Given a value assignment, ν, we will refer to the difference sequence, (δ_{0}, … δ_{k}), defined by equation (1.1).

For a five-dimensional code, this is in particular:

max{ν(p) | p ∈ PG(4, q)} = δ_{0}  (1.2)
max{ν(ℓ) | ℓ ∈ PG^{(1)}(4, q)} = δ_{0} + δ_{1}  (1.3)
max{ν(P) | P ∈ PG^{(2)}(4, q)} = δ_{0} + δ_{1} + δ_{2}  (1.4)
max{ν(H) | H ∈ PG^{(3)}(4, q)} = δ_{0} + δ_{1} + δ_{2} + δ_{3}  (1.5)
ν(PG(4, q)) = δ_{0} + δ_{1} + δ_{2} + δ_{3} + δ_{4}.  (1.6)

Given a value assignment, ν, we will also refer to the sequence (δ_{0}, δ_{1}, … δ_{k}), as defined by equation (1.1) as the difference sequence of ν.

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

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

Knowing that any (k + 1)-dimensional code is represented by a value assignment on PG(k, q), we naturally ask whether the converse is true, that any value assignment, ν : PG(k, q) → ℕ_{0} defines a (k + 1)-dimensional code. This is of course not true, as an arbitrary value assignment may very well define a generator matrix of rank less than k + 1. This is what happens when the difference seqence of ν has a zero entry, which is impossible for the difference sequence of a code. However if the difference sequence of ν has only non-zero entries, it means that there exists k + 1 projectively independent points of positive value. Hence ν defines a matrix, G, with at least k + 1 linearly independent column vectors. Thus G has rank at least k + 1, and it is the generator matrix of some (k + 1)-dimensional code.

4

This also means that taking an m-space, Π_{m} ∈ PG^{(m)}(k, q), we can restrict the value assignment νto this subspace and study ν′ = ν |_{Π_{m}}: Π_{m} → ℕ_{0}. If the difference sequence of ν′ contains only non-zero entries, then ν′ defines a code D, equivalent to an m-dimensional subcode of C. Analogously to the sets M_{i} for C, we define the sets M_{i}(D) for D, i.e. M_{i}(D) is the set of m-spaces of maximum value in Π_{m}.

1.1.3 The Chain Condition

The chain condition was introduced by Wei and Yang [WY93], and it is defined as follows:

Definition 1 (The Chain Condition) A code C is said to satisfy the chain condition if

∀i = 0, 1, … 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 all are implications of the chain condition. For any i and j such that 1 ≤ i ≤ j ≤ k − 1, we have the condition:

(Ci.j) :∃α ∈ M_{i−1}, β ∈ M_{j}, s.t. α ⊂ β.

In particular, for a five-dimensional code, we have:

(C1.1) : ∃℘ ∈ M_{0} ∧ ∃ℓ ∈ M_{1}, s.t. ℘ ⊂ ℓ  (1.7)
(C1.2) : ∃℘ ∈ M_{0} ∧ ∃P ∈ M_{2}, s.t. ℘ ⊂ P  (1.8)
(C1.3) : ∃℘ ∈ M_{0} ∧ ∃H ∈ M_{3}, s.t. ℘ ⊂ H  (1.9)
(C2.2) : ∃ℓ ∈ M_{1} ∧ ∃P ∈ M_{2}, s.t. ℓ ⊂ P  (1.10)
(C2.3) : ∃ℓ ∈ M_{1} ∧ ∃H ∈ M_{3}, s.t. ℓ ⊂ H  (1.11)
(C3.3) : ∃P ∈ M_{2} ∧ ∃H ∈ M_{3}, s.t. P ⊂ H  (1.12)

The negations of these conditions, (Ni.j) =^{def} ¬(Ci.j), will be called the nonchain conditions. The chain condition will be denoted by (C0).

Analogous to the definition by Chen and Kløve [CK97a], we will define extremal non-chain codes of arbitrary dimension k, 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).

5

1.2 Historical overview

The generalised Hamming weights were introduced as early as 1977 by Helleseth et al [HKM77], in their study of weight distributions of irreducible cyclic codes. Wei [Wei91] reintroduced the parameters in 1991 in another context, and called them ‘generalised Hamming weight’. He used the parameters to analyse codes applied on the wire-tap channel of type II, which is a cryptographic application of codes, introduced in 1984 by Ozarow and Wyner [OW84].

During the nineties, several researchers have studied the generalised Hamming weights of linear codes. The concept has also been extended in different ways to non-linear codes (e.g. citereu:gh:nl:95).

In 1993 Kløve [Klø93] studied weight hierarchies of binary codes of dimension 4, and all possible weight hierarchies of such codes were determined. Subsequent articles determine all possible weight hierarchies for threeand four-dimensional codes over several small fields (e.g. [CK96], [CK99b], [CS99]).

Also in 1993, Wei and Yang [WY93] introduced the chain condition. They showed that if a code, C, satisfies the chain condition, then so does its dual, C^{⊥}. Codes satisfying the chain condition have proved useful for several purposes, such as analysis of trellis complexity of linear codes (e.g. [KTFL93]) and analysis of weight hierarchies of product codes (e.g. [WY93]).

Weight hierarchies of chained codes of dimension 5 were studied by Encheva and Kløve [EK94], and Chen and Kløve have studied such codes of arbitrary dimension [CK98b].

Extremal non-chain codes were introduced by Chen and Kløve [CK97a], as the opposite extreme to chained codes. They found tight upper bounds for non-binary, four-dimensional codes. Later they have also found all possible ENDS for four-dimensional, binary codes [CK99a].

Chen and Kløve [CK97b], [CK98a] have also divided four-dimensional codes into classes according to which of the conditions, (C0), (C1.1), (C1.2) and (C2.2) (my notation), they satisfy. For non-binary codes, they have given good upper bounds for each class; and for binary codes, they determine all possible difference sequences.

6

1.3. THE PROBLEM

1.3 The problem

The aim of this report is to find good upper bounds on the difference sequences of extremal non-chain codes of dimension five and higher. We will then elaborate on socalled optimal non-chain codes, that is codes meeting the known bounds with equality. Several statements are made about the structure of such codes, and sample constructions are given in the five-dimensional case.

7

8

Upper bounds on ENDS

We will in this chapter start straight on the main theorem, to give upper bounds on all differences, except the last one. We will also give some lemmas about the structure of codes meeting this bound with equality, and finally we will bound the last difference.

2.1 The main theorem

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

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

The proof of this theorem is quite tediuos, and we will need a couple of lemmas and some new notation to complete it. Fortunately this process will also give us some knowledge about the structure of codes meeting the bound with equality.

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 non-chain code, C, is m-optimal if its difference sequence is an m-optimal ENDS.

Until the theorem is proved, we will also refer to any ENDS meeting the bound on δ_{m} from the theorem, as at most m-optimal, and if an ENDS is at least m-optimal, it is either m-optimal or it violates the bound on δ_{m}. An

9

CHAPTER 2. UPPER BOUNDS ON ENDS

extremal non-chain code is at most m-optimal if its differences sequence is at most m-optimal, and it is at least m-optimal if its difference sequence is.

Lemma 1 For any code with difference sequence, (δ_{0}, δ_{1}, … δ_{k}), we have δ_{k} ≤ qδ_{k−1}.

Proof: Take any Π_{k−2} ∈ M_{k−2}. There are q + 1 (k − 1)-spaces through Π_{k−2}, and for any 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. □

Definition 3 Given a k-dimensional code, C, we call the code defined by some Π_{k−1} ∈ M_{k−1}, a derived code, C_{(1)}, of C. We form a derived series of codes, {C_{(0)}, C_{(1)}, … C_{(k)}}, where C_{(0)} =^{def} C, and C_{(i)} is a derived code of C_{(i−1)}, for i = 1, … k.

It is noted that in general, the derived code and the derived series of codes are not unique.

Lemma 2 If (δ_{0}, δ_{1}, … δ_{k}) is the difference sequence of a code, C, and (δ_{0}^{(1)}, … δ_{k−1}^{(1)}) is the difference sequence of a derived code, C_{(1)}, then

δ_{k−1} ≤ δ_{k−1}^{(1)}.

Proof: Define

λ_{k−1} =^{def} ν(Π_{k−1}), Π_{k−1} ∈ M_{k−1}(C)
λ_{k−2} =^{def} ν(Π_{k−2}), Π_{k−2} ∈ M_{k−2}(C)
λ_{k−1}^{(1)} =^{def} ν(Π_{k−1}^{(1)}), Π_{k−1}^{(1)} ∈ M_{k−1}(C_{(1)})
λ_{k−2}^{(1)} =^{def} ν(Π_{k−2}^{(1)}), Π_{k−2}^{(1)} ∈ M_{k−2}(C_{(1)}).
10

2.1. THE MAIN THEOREM

By the definition of C_{(1)}, λ_{k−1} = λ_{k−1}^{(1)}, and since Π_{k−2}^{(1)} is also a subspace of the geometry defining C, λ_{k−2}^{(1)} ≤ λ_{k−2}. Now we have

δ_{k−1} = λ_{k−1} − λ_{k−2} ≤ λ_{k−1}^{(1)} − λ_{k−2}^{(1)} = δ_{k−1}^{(1)},

as required. □

Let D be the subcode of C, defined by some subspace Π_{m} ∈ M_{m}, and let (ε_{0}, ε_{1}, … ε_{m}) be its difference sequence. This resembles the definition of a derived code of C, and if m = k − 1, it is in fact a derived code.

Lemma 3 If C and D are defined as above, with the given difference sequences, then

δ_{m} ≤ ε_{m} − 1.

Proof: We can prove this as we proved Lemma 2, except that since C is extremal non-chain, so write

λ_{m} =^{def} ν(Π_{m}), Π_{m} ∈ M_{m}(C)
λ_{m−1} =^{def} ν(Π_{m−1}), Π_{m−1} ∈ M_{m−1}(C)
λ′_{m} =^{def} ν(Π′_{m}), Π′_{m} ∈ M_{m}(D)
λ′_{m−1} =^{def} ν(Π′_{m−1}), Π′_{m−1} ∈ M_{m−1}(D).

By the definition of D, λ_{m} = λ′_{m}, and since Π′_{m−1} is also a subspace of PG(k, q), and C is extremal non-chain, we have λ′_{m−1} ≤ λ_{m−1} − 1. Hence

δ_{m} = λ_{m} − λ_{m−2} ≤ λ′_{m} − (λ′_{m−1} + 1) = ε_{m} − 1.

□

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

Proof: A line consists of q+1 points, and by (N1.1), δ_{1}+δ_{0} ≤ (q+1)(δ_{0}−1), and 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 C is at most m-optimal for any m < m̄. The previous lemma proves it

11

for m = 1. We also assume that C is at least m̄-optimal. We shall prove that then it must be just m̄-optimal. Hence we assume that

δm̄ ≥ qm̄δ_{0} − Q(m̄)  (2.2)
δ_{i} ≤ q^{i}δ_{0} − Q(i), ∀i ≤ m̄ − 1.  (2.3)

We will study a derived series of codes, {D_{(0)}, … D_{(m̄)}}. Let Θ_{i} be the i-space defining D_{(i)}, i = 0, … m̄, and (ε_{0}^{(i)}, … ε_{m̄−i}^{(i)}) the difference sequence of D_{(i)}.

By equation (2.2) and Lemma 3, we get

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

Lemmas 2 and 1 give

ε_{m̄−1}^{(1)} ≥ q^{−1}εm̄ ≥ ⌈\frac{qm̄δ_{0} − Q(m̄)}{q}⌉ ≥ q^{m̄−1} − Q(m̄ − 1).  (2.4)

Repeating this argument, we obtain

ε_{0}^{(m̄)} ≥ qm̄εm̄ ≥ δ_{0} − 1.

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

ε_{0}^{(m̄)} = ν(Θm̄) = δ_{0} − 1.  (2.5)

We assume, for induction, that ε_{j}^{(m̄−j)} = q^{j}δ_{0} − Q(j) for any j < i. Repeating the argument of equation (2.4) i times, we get

ε_{i}^{(m̄−i)} ≥ q^{m̄−i}εm̄ ≥ q^{i}δ_{0} − Q(i).

Now ε_{i}^{(m̄−i)} = ν(Θ_{m̄−i}) − ν(Θ_{m̄−i+1}), but

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

since the code is extremal non-chain. We also have

ν(Θ_{m̄−i+1}) = ∑_{j=0}^{i−1} ε_{j}^{(m̄−i+1)} ≥ ∑_{j=0}^{i−1} ε_{j}^{(m̄−i+j+1)} = ∑_{j=0}^{i−1}[q^{j}δ_{0} − Q(j)],  (2.7)

12

according to the inductive hypothesis. Combining these expressions, we get an upper bound on ε_{i}^{(m̄−i)}:

\begin{aligned}ε_{i}^{(m̄−i)} & = ν(Θ_{m̄−i}) − ν(Θ_{m̄−i+1}) \\ & ≤ ∑_{j=0}^{i}[q^{j}δ_{0} − Q(j)] − ∑_{j=0}^{i−1}[q^{j}δ_{0} − Q(j)] = q^{i}δ_{0} − Q(i). \end{aligned}  (2.8)

Combining the upper and lower bounds, we conclude that

ε_{i}^{(m̄−i)} = q^{i}δ_{0} − Q(i),

for i = 0, … m̄ − 1, by induction. Applying Lemma 1, we get

ε(0) ; m̄ ≤ qε_{m̄−1}^{(1)} ≤ qm̄δ_{0} − Q(m̄) + 1,

and by Lemma 3 we have

δm̄ ≤ ε(0) ; m̄ − 1 ≤ qm̄δ_{0} − Q(m̄).

This is to say that C is at most m̄-optimal. The theorem follows by induction. □

Theorem 2 Let Cbe an m-optimal for some m, such that 2 ≤ m ≤ k − 1. Then Cis also (m − 1)-optimal, and the subcode Ddefined by Π_{m} ∈ M_{m}, is a chained code with difference sequence (δ_{0} − 1, δ_{1}, δ_{2}, …, δ_{k−1}, δ_{k} + 1).

Remark 2.1.1 We know from Lemma 4 that δ_{0} ≥ 2, so the difference sequence has only positive elements as expected. Writing (ε_{0}, … ε_{m}) for the difference sequence of D, we have ε_{i} = qε_{i−1} − 1 for i = 1, … m − 1 and ε_{k} = qε_{k−1}.

Proof: We consider the chain

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

Equations (2.6) and (2.7) impose upper and lower bounds on ν(Θ_{i}), for i = 1, … m̄ − 1, and the value of Θm̄, is given in equation (2.5). The very same equations also bounds ∑_{j=0}^{i} δ_{i} − 1. This gives

ν(Θ_{i}) = ∑_{j=0}^{i} δ_{j} − 1 = ∑_{j=0}^{i}{q^{m̄−i}δ_{0} − Q(m̄ − i)}, i = 1, … m̄.  (2.9)

13

Since C is extremal non-chain, we can conclude that Θ_{i} ∈ M_{m̄−i}(D) for i = 1, … m̄, and hence D is chained.

Equation (2.9) also says that

δ_{i} = ν(Θ_{i}) − ν(Θ_{i+1}) = q^{m̄−i}δ_{0} − Q(m̄ − i), i = 1, … m̄ − 1,

hence C is also i-optimal for i < m. We also have

ε_{i} = ν(Θ_{i}) − ν(Θ_{i+1}) = δ_{i}, i = 1, … m̄ − 1.

Now we get

ν(Θ_{0}) = ∑_{j=0}^{m̄} δ_{i} = ∑_{j=0}^{m̄}{qm̄δ_{0} − Q(m̄)} + 1.

Hence

ε_{m} = ν(Θ_{0}) − ν(Θ_{1}) = q^{m}δ_{0} − Q(m) + 1 = δ_{m} + 1.

The expression for ε_{0} comes from equation (2.5), completing the difference sequence of D. □

2.2 Structure of optimal codes

Lemma 5 Let D be a chained code defined by a value assignment, ν : PG(m, q) → ℕ_{0}, with difference sequence (ε_{0}, … ε_{m}) such that ε_{i} = qε_{i−1}−1 for i = 1, … m−1 and ε_{m} = qε_{m−1}. For any Π_{i−1} ∈ M_{i−1}(D) and any Π_{i+1} ∈ M_{i+1}(D), 1 ≤ i ≤ m − 2, such that Π_{i−1} ⊂ Π_{i+1} ⊂ Π_{m}, there are exactly q i-spaces, Π_{i}, of maximum value, such that Π_{i−1} ⊂ Π_{i} ⊂ Π_{i+1}. The last one of the possible i-spaces, Π′_{i}, has value exactly ∑_{j=0}^{i} ε_{j} − 1. For any (m − 1)-space, Π_{m−1} ⊃ Π_{m−2} ∋ M_{m−2}(D), we have Π_{m−1} ∈ M_{m−1}(D).

Proof: Consider Π_{i−1} ∈ M_{i−1}(D) and Π_{i+1} ∈ M_{i+1}(D), 1 ≤ i ≤ m − 2, such that Π_{i−1} ⊂ Π_{i+1} ⊂ Π_{m}.

Let A_{0}, … A_{q} be the i-spaces, such that Π_{i−1} ⊂ A_{j} ⊂ Π_{i+1}, j = 0, … q. We have

ν(Π_{i+1}) = ∑_{j=0}^{q} ν(A_{j}\Π_{i−1}) + ν(Π_{i−1}) = ∑_{j=0}^{i+1} ε_{j} − 1.

14

2.2. STRUCTURE OF OPTIMAL CODES

For any i, ν(A_{j}\Π_{i−1}) ≤ ε_{i}, and ε_{i+1} = qε_{i} − 1, hence

(q + 1)ε_{i} − 1 = ∑_{j=0}^{q} ν(A_{j}\Π_{i−1}),

hence exactly one of the A_{j} is not in M_{i}(D), and it has value exactly ∑_{k=0}^{i} ε_{i}− 1.

Finally consider Π_{m} ∈ M_{m}(D) and Π_{m−2} ∈ M_{m−2}(D), and let β_{0}, …, β_{q} be the (m − 1)-spaces such that Π_{i−1} ⊂ β_{j} ⊂ Π_{i+1}, j = 0, … q. We get

ν(Π_{m}) = ∑_{j=0}^{q} ν(β_{j}\Π_{m−2}) + ν(Π_{m−2}) = ∑_{j=0}^{m} ε_{j}.

For any i, ν(β_{j}\Π_{m−2}) ≤ ε_{m−1} = ε_{m−1}, and ε_{m} = qε_{m−1}, hence

(q + 1)ε_{m−1} = ∑_{j=0}^{q} ν(β_{j}\Π_{m−2}),

which is possible only if β_{j} ∈ M_{m−1}(D) for j = 0, … q. □

Corollary 1 If (δ_{0}, δ_{1}, … δ_{k}), where k ≥ 2, is a 1-optimal ENDS, and ℓ is line with value v(ℓ) = δ_{0} + δ_{1}, then

ν(p) = δ_{0} − 1, ∀p ∈ ℓ.

Lemma 6 Let D be a chained code, defined by a value assignment ν : PG(n, q) → ℕ_{0}, with difference sequence (ε_{0}, … ε_{n}), where ε_{i} = qε_{i−1} − 1 for i = 1, … n. Then there exists at most one point which is not contained in any element of M_{n−1}(D).

Proof: Suppose there are two points, P, Q ∈ Π_{n}, which are not contained in any element of M_{n−1}(D). Let ℓ =^{def} ⟨P, Q⟩, and L ∈ M_{n−1}(D). Obviously, there is a point S ∈ ℓ ∩ L. By assumption P, Q ∉ L, so S ≠ P and S ≠ Q.

There is a subspace K ∈ M_{n−2}(D), such that S ∉ K ⊂ L. We have to prove this, so find a chain

Π_{0} ⊂ Π_{1} ⊂ … ⊂ Π_{n−1} = L ⊂ Π_{n},
15

such that Π_{i} ∈ M_{i}(D) for each i = 0, … n − 1. By Lemma 5, there are q points in Π_{1}, that are elements of M_{0}(D), so if Π_{0} = S, we can replace Π_{0} by some other point which is in Π_{1} and in M_{0}(D). For any i, 1 ≤ i ≤ n − 1, there are q i-spaces in M_{i}(D), containing Π_{i−1} in Π_{i+1}, so if S ∈ Π_{i}\Π_{i−1}, we can replaces Π_{i}, by some other i-space, maintaining the chain. Hence we can assume that S ∉ Π_{n−2} and set K =^{def} Π_{n−2}.

There are q + 1 distinct (n − 1)-spaces spanned by K and a point on ℓ, and only one of these is not an element of M_{n−1}(D). Since {P }K and {Q}K are two distinct (n − 1)-spaces, either P or Q is contained in some element of M_{n−1}(D), and the lemma follows by contradiction. □

Definition 4 We define the projection, π_{p}, of a subspace Π_{n} through the point p ∈ Π_{n}:

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

by mapping ditinct lines through p in Π_{n} to distinct points in PG(n − 1, q), such that coplanar lines are taken to collinear points. We define the projected value assignment ν_{p} : PG(n−1, q) → ℕ_{0}, by letting ν_{p}(X) = ν(π_{p}^{−1}(X)\{p}), for any X ∈ PG(n − 1, q).

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

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

The result also holds for q = 2 if n ≤ 2. It has not been determined whether it holds for q = 2 in arbitrary dimension. Proof: For n = 0 the result is trivial, and for n = 1 it follows immediately from Corollary 1.

For n = 2, consider P ∈ M_{2}(D). There is a point ℘ ⊂ P, such that P ∈ M_{0}(D). Let ℓ_{0}, … ℓ_{q} be distinct lines such that ℘ ⊂ ℓ_{i} ⊂ P, for all i. One of these lines, say ℓ_{0}, has value ε_{1} + ε_{0} − 1, while the remaining q lines have value ε_{0} + ε_{1}. This means that for 1 ≤ i ≤ q, there is exactly one point, α_{i} ∈ ℓ_{i}, such that ν(α_{i}) = ε_{0} −1. There is at most two points in ℓ_{0} with value ε_{0} − 1 or less. The remaining points have value ε_{0}. Obviously, any line in P

16

has value at most ε_{0} + ε_{1}, and hence has at least one point of value ε_{0} − 1 or less. Since there is a total of no more than q + 2 such points, there is a line, Π_{1}, formed by q + 1 of them. 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}, P} forms the required set S.

Now assume that the lemma holds for n < n̄, and consider

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

For any Π_{n} ∈ M_{n}, n < n̄, let S(Π_{n}) be the set S, defined in the lemma, corresponding to Π_{n}. We also define σ_{i}(Π_{n}) to be the i-space in S(Π_{n}).

Clearly if Θ_{1}, Θ_{2} ∈ M_{n̄−1} are subspaces of Πn̄, then for any p ∈ Θ =^{def} Θ_{1} ∩ Θ_{2}, we have #{Π ∈ S(Θ_{1}) | p ∈ Π} = #{Π ∈ S(Θ_{2}) | p ∈ Π}. This also means that if Θ ∈ M_{n̄−2}(D), then

S(Θ) = {Π ∩ Θ | Π ∈ S(Θ_{1})} = {Π ∩ Θ | Π ∈ S(Θ_{2})}.

Since the elements of S(Θ) are projective spaces of different dimensions, we can conclude that

σ_{i−1}(Θ) = σ_{i}(Θ_{1}) ∩ Θ = σ_{i}(Θ_{2}) ∩ Θ, i = 0, … n̄ − 1.

In the following analysis, 1 ≤ i ≤ n̄ − 2. Consider P ∈ M_{n̄−3}(D), α_{0} ∈ M_{n̄−2}(D), and A_{1}, … A_{q} ∈ M_{n̄−1}(D) and A_{0} ∉ M_{n̄−1}(D), such that

P ⊂ α_{0} ⊂ A_{j} ⊂ Πn̄, j = 0, … q.

Since q ≥ 3, there are at least two distinct (n̄ − 2)-spaces, α_{1}, α_{2} ∈ M_{n̄−2}(D), 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}(D), such that P ⊂ β_{j} ⊂ A_{2} and

α_{0} ≠ β_{j}, j = 1, 2. Define σ′_{i+1} =^{def} σ_{i}(A_{1})σ_{i}(A_{2}).

Consider the spaces α_{1}β_{1} and α_{2}β_{1}. At least one of them is a space in M_{n̄−1}(D), denote it B_{1}. Similarily, let B_{2} be either α_{1}β_{2} or α_{2}β_{2}, such that B_{2} ∈ M_{n̄−1}(D). Now B_{1} meets A_{1} and A_{2} in distinct elements of M_{n̄−2}(D), and hence σ_{i}(B_{1}) meets σ_{i}(A_{1}) and σ_{i}(A_{2}) in (n̄ − 2)-spaces which are also distinct. Therefore σ_{i}(B_{1}) ⊂ σ′_{i+1}. The same 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 of M_{n̄−2}(D), which means that σ_{i}(A_{3}) meets σ′_{i+1} in at least two distinct (i − 1)-spaces. We conclude that A_{3} ⊂ σ′_{i+1}.

17

Now take any A ∈ M_{n̄−1}(D), not equal to any of A_{1}, A_{2}, A_{3}, B_{1}, or B_{2}. Either A meets A_{1}, A_{2}, and A_{3} in three distinct (n̄ − 2)-spaces, or it meets A_{1}, B_{1}, and B_{2} in three distinct (n̄ − 2)-spaces. In any case, we find at least two distinct subspaces γ_{1}, γ_{2} ∈ M_{n̄−2}(D), such that P ⊂ γ_{j} ⊂ A, and such that σ_{i−1}(γ_{j}) ⊂ σ′_{i+1}, j = 1, 2. We conclude that σ_{i}(A) ⊂ σ′_{i+1}.

We will now prove that the points σ_{0}(A) for all A ⊂ Πn̄, A ∈ M_{n̄−1}(D) span a line, σ′_{i}. We write

U =^{def} {σ_{0}(A) | A ∈ M_{n̄−1}(D)}.

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

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

giving the value of any point, except at most one, by the formula

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

Take a point F ∈ M_{0}(D), such that F ∈ P, and consider the projection through F, π_{F}. It is easily checked that the projected value assignment, ν_{F}, defines an (n̄ − 1)-dimensional code with difference sequence (ε_{1}, … ε_{n}). Hence by the inductive hypothesis, there is a set S(PG(n̄ − 1, q)) of i-spaces σ_{i}(PG(n̄ − 1, q)), i = 0, … n̄ − 1, such that

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

Of course, σ_{i}(PG(n̄−1, q)) must be the image of σ′_{i+1} for i = 2, … n̄−2, and U must be contained in the inverse image of σ_{1}(PG(n̄−1, q))∪σ_{0}(PG(n̄−1, q)). Clearly U consists of one point from each of the subspaces A_{1}, … A_{q}, so let U′ ⊂ U 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}(D). Clearly V is either q +1 points, if σ_{0}(PG(n̄−1, q)) ∈ σ_{1}(PG(n̄− 1, q)), or otherwise q + 2 points. Hence σ_{1}(PG(n̄ − 1, q)) ∪ σ_{0}(PG(n̄ − 1, q)) is the image of at most q+2 points, and U cannot contain more than two points from A_{0}; and U′ is mapped to σ_{1}(PG(n̄ − 1, q)), and thus U′ are coplanar points. We can make more projections through different points F_{1} ∈ M_{0}(D), F_{1} ∈ M_{0}(D), to prove that U′ is also contained in a plane which is equal to the first. Hence U′ is contained in a line, which we denote σ′_{1}.

18

We have to prove that #(U ∩ A_{0}) ≤ 1. Suppose U ∩ A_{0} contains two such points R_{1} and R_{2}. These two points cannot be in the same element G ∈ M_{n̄−1}(D), because G meets each of the σ′_{i} in an (i − 1)-space of S(G). Hence R_{1} and R_{2} would be two distinct points in S(G), which is absurd.

We conclude that there are F_{1}, F_{2} ∈ M_{n̄−1}(D), such that R_{1} ∈ F_{1}\F_{2} and R_{2} ∈ F_{2}\F_{1}. Now we can project through a couple of distinct points which are in F_{1} ∩ F_{2} and in M_{0}(D), and by the argument of the previous paragraph, we will find that R_{1}, R_{2} ∈ σ′_{1}, which is absurd. Hence there is at most one point in U ∩ A_{0}, and if such a point exist, it is in σ′_{1}. Otherwise the point in A_{0} ∩ σ′_{1} is not contained in any element of M_{n̄−1}(D).

We claim that there must be a point, σ′_{0}, which is not contained in any element of M_{n̄−1}(D), and that the set S =^{def} {σ′_{i} | i = 0, … n̄ − 1} forms the required set, such that

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

We have proved that this fails for at most one point, and if it does fail for such a point, it must give us a wrong value for ν(PG(n̄, q)), but

ν(PG(n, q)) = ∑_{i=0}^{n̄}[q^{i}ε_{0} − Q(i − 1)],

where Q(−1) = 0, and we claim that

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

which is easily verified to be 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. □

Theorem 3 Let D be a chained code defined by a value assignment, ν : PG(m, q) → ℕ_{0}, with difference sequence (ε_{0}, … ε_{m}) such that ε_{i} = qε_{i−1} − 1 for i = 1, … m. Then there exists a collection S, of exactly one i-space in Π_{m}, for each i = 1, … m, such that ν(p) = δ_{0} − #{Π ∈ S | p ∈ Π}, for any p ∈ Π_{m}.

Proof: The proof goes exactly as for Lemma 7, except that any point is contained in some element of M_{n̄−1}(D), and consequently there is no point in the collection, S. □

19

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

2.3 Upper bounds on the total value

We have established bounds for all differences but the last. The following is an extension of Theorem 3 in [CK97a].

Theorem 4 If (δ_{0}, δ_{1}, … δ_{k}), k ≥ 2, satisfies (Nm.m), then

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

Proof: Let α ∈ M_{m−1}. In PG(k, q), there are Q(k−m) m-spaces containing α, and for any such m-space, β ⊂ α, we know by condition (Nm.m) that

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

Thus ν(PG(k, q)\α) ≤ (δ_{m} − 1)Q(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. The bound in the following corollary is tight for the code constructed in Chapter 3. When we take up the study of binary codes, we will derive another bound from the theorem.

Corollary 2 For any (δ_{0}, δ_{1}, … δ_{k}), k ≥ 2, if (N1.1) is satisfied, 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}.

20

Construction of a non-binary ENDS

We recall the upper bounds on δ_{1} through δ_{3} given by Theorem 1, and the bound on ν(PG(4, q)) from Corollary 2. Assuming that q ≥ 3 and δ_{0} ≥ 3, we want to construct a value assignment, ν : PG(4, q) → ℕ_{0}, meeting these bounds with equality. This means that the maximum values of subspaces are:

ν(℘) = δ_{0}, ∀℘ ∈ M_{0}
ν(ℓ) = (q + 1)(δ_{0} − 1), ∀ℓ ∈ M_{1}
ν(P) = (q^{2} + q + 1)δ_{0} − q^{2} − 2q − 2, ∀P ∈ M_{2}
ν(H) = (q^{3} + q^{2} + q + 1)δ_{0} − q^{3} − 2q^{2} − 3q − 3, ∀H ∈ M_{3}

3.1 The assignment

As reference points, we chose five points, A, B, C, D and E, spanning PG(4, q).

Consider the line ⟨D, E⟩. It has q+1 points, which we name ρ_{0} = D, ρ_{1} = E, ρ_{2}, ρ_{3}, …, ρ_{q}. These points define q + 1 hyperplanes with ⟨A, B, C⟩ as a subspace, and we call them G_{i} =^{def} ⟨A, B, C, ρ_{i}⟩ for i = 0, 1, …, q. We define F =^{def} ρ_{2} and G =^{def} ρ_{3}. We also establish names for the affine spaces we get by removing ⟨A, B, C⟩ from G_{i}:

A_{i} =^{def} G_{i}\⟨A, B, C⟩, i = 0, 1, …, q.

21

CHAPTER 3. CONSTRUCTION OF A NON-BINARY ENDS

[figure: D; E; F; G; X; A; W; Y; V; B; C]

Figure 3.1: Parts of our optimal construction in PG(4, q), q ≥ 3. Black lines are in ⟨A, D, G⟩, dotted and dashed lines are not.

During the construction we will pay special attention to the points in G_{0}, G_{1}, G_{2} and G_{3}. The remaining hyperplanes G_{i} will become isomorphic to G_{0} with respect to the value assignment.

3.1.1 Defining subspaces of maximum values

First we decide that G_{0} be in M_{3}, and assign values satisfying the requirements from Theorem 3:

ν(p) = δ_{0} − 3, ∀p ∈ ⟨A, B⟩
ν(p) = δ_{0} − 2, ∀p ∈ ⟨A, B, C⟩\⟨A, B⟩
ν(p) = δ_{0} − 1, ∀p ∈ ⟨A, B, C, D⟩\⟨A, B, C⟩

We go on by constructing a plane in M_{2}. For this, we choose P =^{def} ⟨C, D, G⟩ and assign values such that it satisfies the requirements from Conjecture 3:

ν(p) = δ_{0} − 2, ∀p ∈ ⟨C, G⟩
ν(p) = δ_{0} − 1, ∀p ∈ ⟨C, D, G⟩\⟨C, G⟩
22

3.1. THE ASSIGNMENT

We note that P has but one point, C, in common with ⟨A, B, C⟩, which also means that it intersects each of the affine spaces, A_{i}, in q points.

Now we choose a point for M_{0}. We want to place it in G_{1}, particularly on the line ⟨A, E⟩. We will have to refer to two distinct points on this line, so let:

X, Y ∈⟨A, E⟩\{A, E}, X ≠ Y

Let ℘ =^{def} {X} ∈ M_{0} and assign ν(X) = δ_{0}.

It remains to choose a line, ℓ, for M_{1}, so let ℓ =^{def} ⟨F, Y ⟩. We know that each point on ℓ must have value δ_{0} − 1.

Having established members of the sets M_{0}, M_{1}, M_{2}, M_{3}, we turn to the problem of giving the remaining points values just low enough to satisfy the non-chain conditions. We keep in mind that X will be the only point in M_{0}, so for the remainder of the chapter we will assign no value greater than δ_{0} − 1.

3.1.2 Lines through X

For any line, α ∋ X, we have

ν(α) ≤ (q + 1)(δ_{0} − 1) − 1 = δ_{0} + q(δ_{0} − 1) − 2,

because the DS is an ENDS. Hence α must have a point of value δ_{0} − 3 or less, or at least two points of value δ_{0} − 2.

First consider the lines through X, that does not intersect ⟨A, B, C⟩. We can handle a lot of these lines by assigning the value δ_{0} − 3 to all points in A_{3} that have not got any value yet:

ν(p) = δ_{0} − 3, ∀p ∈ A_{3}\(P ∪ ℓ).

Let α_{i} for i = 1, 2, …, q be the (distinct) lines through X meeting A_{3} in a point of value δ_{0} − 2, i.e. meeting ⟨C, G⟩\{C}. The lines, α_{i}, meet A_{2} in distinct points. Let T be the set of these points:

T =^{def} ⋃_{i=1}^{q}(α_{i} ∩ A_{2}) = A_{2} ∩ ⟨X, C, G⟩.

23

[figure: A; Y; X; E; M; N; C; B]

Figure 3.2: The hyperplane G_{1} in our optimal construction for PG(4, q). Black lines are in the plane ⟨A, C, E⟩, dotted lines are not.

Let S ⊂ A_{2} be the set of points in A_{2}, to which we have already assigned values. Thus

S =^{def} A_{2} ∩ (P ∪ ℓ) = A_{2} ∩ ⟨C, D, G⟩.

Obviously the plane ⟨X, C, G⟩ does not meet S, and consequently T does not meet S. We assign the value δ_{0} − 2 to each point in T :

ν(p) = δ_{0} − 2, ∀p ∈ A_{2} ∩ ⟨X, C, G⟩.

Now ν(α_{i}) < ν(ℓ) for any i.

There is one point of value δ_{0} − 1 in A_{3}, namely the point on ℓ. We call this point W, and let V be the point where the line ⟨W, X⟩ intersects A_{2}. We refer to Figure 3.2, and note that V ∈ ⟨A, F ⟩\{F }, and consequently V ∉ T ∪ S. Hence V has no value, and we can assign a value of δ_{0} − 3, so that ν(⟨W, X⟩) < ν(ℓ):

W ∈ ℓ ∩ G_{3}
V ∈ ⟨W, X⟩ ∩ G_{2}
ν(V) = δ_{0} − 3.
24

This concludes the study of lines through X, that does not intersect ⟨A, B, C⟩. Now we turn to lines through X that does intersect ⟨A, B, C⟩. In other words, we are to consider the values of points in A_{1}.

Let M ≠ E be a point in A_{1} ∩ P.

M ∈ P ∩ A_{1}\{E}.

Define ψ =^{def} ⟨A, B, M⟩. We have assigned values to {X, Y } ⊂ ⟨A, E⟩ and to ⟨C, E⟩ ⊂ P. The remaining points in A_{1} have no value yet. We note that ⟨A, E⟩ ∩ ψ = {A} and ⟨C, E⟩ ∩ ψ = {M}. Hence the only points in ψ with assigned values are M and the points on ⟨A, B⟩. We assign the value δ_{0} − 2 to the remaining points in ψ:

ν(p) = δ_{0} − 2, ∀p ∈ ⟨A, B, M⟩\(⟨A, B⟩ ∪ {M}).

Finally consider the line ⟨M, X⟩. We have assigned values to M and X, and also to ⟨M, X⟩ ∩ ⟨A, B, C⟩. The remaining points on ⟨M, X⟩ have no value, hence there is at least one point N ∈ ⟨M, X⟩ with no value yet. We give it the value δ_{0} − 2:

N ∈⟨M, X⟩\({M, X} ∪ ⟨A, B, C⟩)
ν(N) = δ_{0} − 2

Now consider any line α, such that X ∈ α ⊂ G_{1}. If α meets ⟨A, B⟩, it has a point of value δ_{0} − 3, and so ν(α) < ν(ℓ). Otherwise α meets ⟨A, B, C⟩ in a point of value δ_{0} − 2, but then it also meets ⟨A, B, M⟩ in some distinct point, ρ. Either ν(ρ) = δ_{0} − 2, or ρ = M, and N ∈ α. In either case α has at least two points of value δ_{0} − 2, and consequently ν(α) < ν(ℓ).

The preceding argument proves that for any line, α ∋ X, ν(α) < ν(ℓ).

3.1.3 Finishing touches

All remaining points get the value δ_{0} − 1. We summarise the assignment in a table 3.1. The total value is easily verified by summing the values in the table.

25

value of p  p in  number of new points
δ_{0}  {X}  1
δ_{0} − 3  ⟨A, B⟩  q + 1
δ_{0} − 2  ⟨A, B, C⟩\⟨A, B⟩  q^{2}
δ_{0} − 1  A_{0}  q^{3}
∪_{i≥4}A_{i}  (q − 3)q^{3}
⟨C, D, G⟩\⟨C, G⟩  2q
⟨F, Y ⟩  2
A_{2}\({V } ∪ ⟨X, C, G⟩)  q^{3} − 2q − 1
A_{1}\({N} ∪ ⟨A, B, M⟩  q^{3} − q^{2} − q − 1
δ_{0} − 2 A_{2} ∩ ⟨X, C, G⟩ q
⟨C, G⟩  q
⟨A, B, M⟩\(⟨A, B⟩ ∪ {M}) q^{2} − 1
{N}  1
δ_{0} − 3 A_{3}\(P ∪ ℓ) q^{3} − q − 1
{V }  1

Table 3.1: A general value assignment for PG(4, q), q ≥ 3, δ_{0} ≥ 3.

3.2 Verifying the non-chain conditions

3.2.1 The point

The only point of value δ_{0} or more is X, so

M_{0} = {{X}}.

3.2.2 Lines

We know that ν(ℓ) = (q+1)(δ_{0}−1). Any line, α′ ∌ X, consists of q+1 points of value at most δ_{0} − 1, so ν(α′) ≤ (q + 1)(δ_{0} − 1) = ν(ℓ), with equality if and only if any point on α′ has value δ_{0} − 1. In Section 3.1.2, we proved that any line, α, containing X have value ν(α) < ν(ℓ). This proves that ℓ ∈ M_{1}, and (N1.1) follows.

We observe that any line, ℓ′ ∈ M_{1}, does not meet ⟨A, B, C⟩, because no point in ⟨A, B, C⟩ has value δ_{0} − 1. This implies that ℓ′ ⊄ G_{i} for any i.

26

3.2. VERIFYING THE NON-CHAIN CONDITIONS

There may be several lines of value δ_{1} + δ_{0}, and we don’t give any expression for number of such lines, except that at least one such line exists.

3.2.3 Planes

The study of planes is quite tedious. We will go as far as to prove that P is the only plane of maximum value. We suppose for a contradiction that γ ≠ P is a plane, such that ν(γ) ≥ ν(P).

First assume that X ∈ γ. We have showed that any line, through X, has value at most (q + 1)δ_{0} − q − 2; and there are q + 1 such lines in γ. Hence

\begin{aligned}ν(γ) & ≤ (q + 1)[(q + 1)δ_{0} − q − 2 − δ_{0}] + δ_{0} \\ & ≤ (q^{2} + q + 1)δ_{0} − q^{2} − 3q − 2 < ν(P), \end{aligned}

contrary to assumption; hence X ∉ γ. Condition (N1.2) follows immediately.

Suppose that γ ⊂ G_{i} for some i. The intersection γ ∩ ⟨A, B, C⟩ is a line with one point of value δ_{0} − 3, and q points of value at most δ_{0} − 2. The remaining q^{2} points have value at most δ_{0} − 1, since X ∉ γ. Hence the total value is

ν(γ) ≤ (q^{2} + q + 1)δ_{0} − q^{2} − 2q − 3 < ν(P),

contrary to assumption. We conclude that γ ⊄ G_{i} for any i.

Consider the possibility that ⟨C, G⟩ ⊂ γ. All points on ⟨C, G⟩ have value δ_{0} − 2, so ν(⟨C, G⟩) = (q + 1)δ_{0} − 2q − 2. There is a point of intersection in γ ∩ ⟨A, B, M⟩. If γ should meet ⟨A, B⟩, γ would be in G_{3}, which it is not. If M ∈ γ, then γ = P, contrary to assumption. Thus γ meets ⟨A, B, M⟩ in a point of value δ_{0} − 2. There are q^{2} − 1 more points in γ\⟨C, G⟩, and since X ∉ γ, no point has value greater than δ_{0} − 1. This gives a total value of ν(γ) ≤ (q^{2} + q + 1)δ_{0} − 2q − 3 < ν(P), which is impossible.

As ⟨C, G⟩ ⊄ γ, the intersection γ ∩ A_{3} has at most two points of value δ_{0} − 2 or more. One of them may be W, with value δ_{0} − 1; and the other may be on the line ⟨C, G⟩ and have value δ_{0} − 2. Hence

ν(γ ∩ A_{3}) ≤ qδ_{0} − 3q + 3,  (3.1)

with equality if and only if W ∈ γ, and γ meets ⟨C, G⟩ in a point different from C.

27

[figure: D; A; X; Y; E; F; G; C; Θ; Ξ; W; M]

Figure 3.3: There are two choices for γ: ⟨M, W, Ξ⟩ and ⟨M, W, Θ⟩. The planes ⟨C, G, X⟩ and γ meet in a line.

Each of the other affine spaces, A_{i} for i ≠ 1, meet γ in q points of value at most δ_{0} − 1. Hence

ν(γ ∩ A_{i}) ≤ qδ_{0} − q, ∀i ≠ 3,  (3.2)

with equality if and only if any point in γ ∩ A_{i} has value δ_{0} − 1.

Finally γ meets ⟨A, B, C⟩ in a point, Ψ, of value at most δ_{0} − 2. Thus the total value

ν(γ) ≤ (q^{2} + q + 1)δ_{0} − q^{2} − 3q + 1.  (3.3)

For q = 3 this is exactly the value of P, so equality is necessary. For q ≥ 4, ν(γ) < ν(P), contrary to assumption. Thus γ can only exist if q = 3.

To get equality in (3.3), ν(Ψ) = δ_{0} − 2, so γ cannot meet ⟨A, B⟩. Also all points in γ\G_{3} must have value δ_{0}−1, thus the intersection of γ and ⟨A, B, M⟩ is M. We also need equality in (3.1), so W ∈ γ, and γ meets ⟨C, G⟩\{C}.

This shows that γ ⊂ ⟨W, M, C, G⟩ = ⟨C, D, G, X⟩. Let Π_{3} =^{def} ⟨C, D, G, X⟩,

which is a three-space (see figure 3.3). The fact that A ∉ γ implies that G ∉ γ, so there are but two possible choices for γ.

28

We know that ⟨C, G, X⟩ ∩ G_{2} is a line, β, of points of value δ_{0} − 2. Both β and γ are in Π_{3}, so they meet in some point of value δ_{0} − 2. However C ∉ γ, and all points in γ ∩ A_{2} have value δ_{0} − 1, and thus we have a contradiction.

This shows that no other plane has as high value as P, so M_{2} = {P}. Any line in P contains a point of value δ_{0} − 2, so (N2.2) is satisfied.

3.2.4 Hyperplanes

We have assigned the value δ_{0} − 1 to any point in A_{0} and in A_{i} for i > 3. As stated, G_{0} has the desired maximum value and so have G_{i} for i > 3. Each of A_{1}, A_{2}, and A_{3}, have several points of value less than δ_{0} − 1 and at most one, namely X, of value higher than δ_{0} − 1. Hence G_{1}, G_{2}, G_{3} ∉ M_{3}.

We will prove that the hyperplanes of maximum values are exactly G_{0} and G_{i} for i > 3. Suppose for a contradiction that there is a hyperplane, ℵ ≠ G_{i} for all i, such that ν(ℵ) ≥ ν(G_{0}).

First we assume that X ∈ ℵ. We have proved that any line through X has value at most (q + 1)(δ_{0} − 1) − 1, and ℵ contains q^{2} + q + 1 such lines, and has the value

\begin{aligned}ν(ℵ) & ≤ (q^{3} + q^{2} + q)(δ_{0} − 1) − 2(q^{2} + q + 1) + δ_{0} \\ & = (q^{3} + q^{2} + q + 1)δ_{0} − (q^{3} + 3q^{2} + 3q + 3) < ν(G_{0}), \end{aligned}

contrary to assumption. Thus we conclude that X ∉ ℵ. Condition (N1.3) follows immediately.

Now ℵ ∩ G_{3} is a plane, α ≠ ⟨A, B, C⟩, which intersects ⟨A, B, C⟩ in a line with one point of value δ_{0} − 3 and q points of value at most δ_{0} − 2, which gives

ν(ℵ ∩ ⟨A, B, C⟩) ≤ (q + 1)δ_{0} − 2q − 3.  (3.4)

Now consider values of points in A_{3}. Most of the points in A_{3} have value δ_{0} − 3. Exceptions are the q points in (⟨C, G⟩\{C}) ⊂ P with value δ_{0} − 2, and the point W ∈ ℓ which has value δ_{0} − 1. Thus the intersection α ∩ A_{3} has at most q + 1 points of value greater than or equal to δ_{0} − 2, out of which one, W, can have value δ_{0} − 1 and the remaining q points can have value δ_{0} − 2. This gives

ν(ℵ ∩ A_{3}) ≤ q^{2}δ_{0} − 3q^{2} + q + 2.  (3.5)
29

There are q^{3} points in ℵ\G_{3}, and since X ∉ ℵ, all these points have value δ_{0} − 1 or less. Hence

ν(ℵ\G_{3}) ≤ q^{3}(δ_{0} − 1).  (3.6)

We sum up equations (3.4), (3.5), and (3.6), to get

ν(ℵ) ≤ Q(3)δ_{0} − q^{3} − 3q^{2} − q − 1 ≤ Q(3)δ_{0} − q^{3} − 2q^{2} − 3q − 4 < ν(G_{0}),

contrary to assumption.

We conclude that

M_{3} = {G_{0}, G_{i} | i > 3}.

We showed in Section 3.2.2, that for any ℓ′ ∈ M_{1}, ℓ′ ⊄ G_{i} for any i; hence (N2.3) follows. Obviously P ⊄ G_{i} for any i, and there is no other plane in M_{2}; this proves (N3.3).

We have proved that all the non-chain conditions hold, so the construction is an ENDS.

3.3 The conclusion

Our construction proves the following theorem.

Theorem 5 If q ≥ 3 and δ_{0} ≥ 3, there exists a five-dimensional, extremal non-chain code with the difference sequence:

δ_{1} = qδ_{0} − (q + 1)
δ_{2} = q^{2}δ_{0} − (q^{2} + q + 1)
δ_{3} = q^{3}δ_{0} − (q^{3} + q^{2} + q + 1)
δ_{4} = q^{4}δ_{0} − (q^{4} + 2q^{3} + q^{2})

30

Binary ENDS

We remember from Chapter 2, several bounds on the differences. We know from the work of Chen and Kløve [CK99a], that binary four-dimensional codes must meet stronger bounds. In this chapter we will prove such upper bounds for arbitrary dimension. A five-dimensional code meeting the bounds with equality, will be provided in the next chapter.

We start with the general bounds. In Section 4.2 we will prove some special properties for codes meeting the bounds with equality. Finally we establish a lower bound on δ_{0} in Section 4.3.

4.1 General bounds

The following is a generalisation of Lemma 1 part ii) from [CK99a], and it gives a stronger bound for the second to the last difference, δ_{k−1}.

Theorem 6 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} =^{def} Π_{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 =^{def} Π_{k−2}\Π_{k−3} = {S_{i} | i = 1, 2, …, 2^{k−2}},  (4.1)
ℓ_{i} =^{def} ⟨P, S_{i}⟩ = {P, S_{i}, T_{i}}, i = 1, 2, …, 2^{k−2}.  (4.2)
31

CHAPTER 4. BINARY ENDS

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

Figure 4.1: Representation of PG(4, 2) for Theorem 6. Black lines are in Π_{3}, dashed lines in Π_{2}, and dotted lines are in neither. White points are in Π_{1}. The points L_{1} and L_{2}, with Π_{1}, span L_{1} and L_{2} respectively.

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

T =^{def} {T_{i} | i = 1, 2, …, 2^{k−2}}.  (4.3)

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},

and

ν(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}.

32

4.1. GENERAL BOUNDS

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 lemma is proved. □

Corollary 3 No extremal non-chain, binary code of dimension four or more, can meet the bound on δ_{k−1} from Theorem 1 with equality.

Proof: Theorem 6, combined with the bound on δ_{1} from Theorem 1, gives

δ_{k−1} ≤ 2^{k−2}δ_{1} − 2 − 2^{k−2}
≤ 2^{k−1}δ_{0} − 2^{k−2} · 3 − 2 − 2^{k−2} = 2^{k−1}δ_{0} − q^{k} − 2
= 2^{k−1}δ_{0} − (q^{k} − 1) − 3 = [2^{k−1}δ_{0} − Q(k − 1)] − 3,

which is a stronger bound than the bound from Theorem 1. □

For the last difference, δ_{k}, we use Theorem 4, to get a bound expressed in terms of δ_{k−1}. This bound coincides with the one given in [CK99a].

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

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

Proof: From Theorem 4, we have for m = k − 1,

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

33

and the lemma follows immediately. □

For the remaining differences we use the bounds known from Theorem 1. We will see that for five-dimensional codes they are tight.

For a five-dimensional ENDS, we get the following bounds:

δ_{1} ≤ 2δ_{0} − 3  (4.4)
δ_{2} ≤ 4δ_{0} − 7  (4.5)
δ_{3} ≤ 4δ_{1} − 6  (4.6)
δ_{4} ≤ 2δ_{3} − 3  (4.7)

The two first bounds, (4.4) and (4.5), follow directly from Theorem 1, the third, (4.6), comes from Theorem 6, and the fourth one, (4.7), comes from Theorem 7.

4.2 Construction requirements

Lemma 8 If (δ_{0}, δ_{1}, δ_{2}, δ_{3}, δ_{4}) is a binary ENDS, and δ_{1} = 2δ_{0} − 3 and δ_{2} = 4δ_{0} − 7, then for any ℘ ∈ M_{0}, any ℓ ∈ M_{1}, and any P ∈ M_{2}, we have:

ℓ ∩ P = (ℓ℘) ∩ P = {X} ∈ PG^{(0)}(4, 2).

Proof: We will first prove that that ℓ ∩ P is a point. Because the code is an ENDS, ℓ ⊄ P, so ℓ ∩ P is either a point or the empty set. Suppose for a contradiction that ℓ ∩ P = ∅.

We let ℘ = {P } be a point of maximum value, and α =^{def} ℓ℘. In PG(4, 2) any two planes must meet, and ℓ ⊂ α does not meet P, so α and P meet in a point, O. Let ⟨O, P ⟩ = {N, O, P }. Since ℓ doesn’t meet P, and P ∉ ℓ, N ∈ ℓ.

By Lemma 1, ν(N) = δ_{0} − 1, and

m({N, O, P }) ≤ δ_{1} + δ_{0} − 1 = 3δ_{0} − 4,

so ν(O) ≤ δ_{0}−3. Hence δ_{2} < 4δ_{0}−7 by Theorem 3. It follows by contradiction that ℓ ∩ P is a point, X.

It remains to prove that (℘ℓ) ∩ P is a point. We have showed that there is a point X ∈ ℓ ∩ P ⊂ (℘ℓ) ∩ P. Suppose for a contradiction that (℘ℓ) ∩ P is a line. Then ℵ =^{def} (℘ℓ)P is a 3-space. We consider the code defined by

34

4.3. LOWER BOUND ON δ_{0}

the value assignment restricted to ℵ, i.e. ν|_{ℵ}. Obviously ℘, ℓ and P are contained in ℵ, and having maximum values in the original geometry, they have in particular maximum value in ℵ. Hence the difference sequence of ν|_{ℵ} is (δ_{0}, δ_{1}, δ_{2}, δ′_{3}), for some δ′_{3}.

There are no subspaces satisfying either of the conditions, (Ci.j), in PG(k, 2), so in particular no such subspaces can exist in ℵ. Hence ν|_{ℵ} define a four-dimensional ENDS, and by Theorems 6 and 1,

δ_{2} ≤ 2δ_{1} − 4 ≤ 4δ_{0} − 10,

and the lemma follows by contradiction. □

4.3 Lower bound on δ_{0}

In practice our construction of a binary, five-dimensional ENDS requires δ_{0} ≥ 4, so it is interesting to know if any smaller value for δ_{0} is possible. We remember that Chen and Kløve [CK99a] showed that δ_{0} ≥ 5 for fourdimensional codes, and they did so by first proving lower bounds on the other differences. A complete study of lower bounds is beyond the scope of this report, but we introduce two lemmas which will be used to prove that δ_{0} ≥ 4 for any binary, five-dimensional ENDS.

Lemma 9 If (δ_{0}, δ_{1}, δ_{2}, δ_{3}, δ_{4}) is a binary ENDS, and

λ = min{ν(p) | p ∈ ℓ},

for some ℓ ∈ M_{1}, then

δ_{4} ≥ δ_{2} + δ_{0} + 1 + λ.

Proof: Let ℘ ∈ M_{0}, ℓ ∈ M_{1}, P ∈ M_{2}, and H ∈ M_{3} be subspaces of maximum value. We know that H has value δ_{0} + δ_{1} + δ_{2} + δ_{3}, and its complement, H^{C}, has value δ_{4}.

The intersection P ∩H is a line of value at most δ_{1}+δ_{0}−1, so ν(P ∩H^{C}) ≥ δ_{2} + 1. We know that ℓ has two points in H^{C}, at most one of which may coincide with a point in P, and the other has value at least λ. Finally ℘ ⊂ H^{C}, so δ_{4} ≥ δ_{2} + δ_{0} + 1 + λ, as required. □

35

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

δ_{1} ≥ 2  (4.8)
δ_{2} ≥ δ_{0} + 1.  (4.9)

Proof: Assume δ_{1} = 1. Let ℘ ∈ M_{0} be a point of maximum value. Obviously ℘ cannot be the only point of positive value, so let ρ ≠ ℘ be another such point. The line ℘ρ has value at least δ_{0} + 1 = δ_{1} + δ_{0}, so it is a line of maximum value, and the code is no ENDS. We conclude that δ_{1} ≥ 2.

Let ℓ ∈ M_{1} and ℘ ∈ M_{0} be a line and a point of maximum value. If δ_{2} ≤ δ_{0}, then

ν(ℓ℘) ≥ 2δ_{0} + δ_{1} ≥ δ_{2} + δ_{1} + δ_{0},

and the code is no ENDS, contrary to assumption. We conclude that δ_{2} ≥ δ_{0} + 1. □

Theorem 8 If (δ_{0}, δ_{1}, δ_{2}, δ_{3}, δ_{4}) is a binary ENDS, then δ_{0} ≥ 4.

Proof: We let ℓ and λ be defined as in Lemma 9.

We have from Theorem 7 that

δ_{4} ≤ 16δ_{0} − 39,

and from Lemma 9 that

δ_{4} ≥ δ_{2} + δ_{0} + 1 + λ.

Combining these inequalities, we have

15δ_{0} ≥ 40 + δ_{2} + λ.

This gives

δ_{0} ≥ 2 + \frac{10 + δ_{2} + λ}{15}.

So either δ_{0} ≥ 4, or δ_{0} = 3 and δ_{2} + λ ≤ 5.

We consider δ_{0} = 3. Then δ_{2} ≥ δ_{0} + 1 = 4, so that λ ≤ 1. We have upper and lower bounds for the value of ℓ:

5 ≤ δ_{0} + δ_{1} = ν(ℓ) ≤ 2(δ_{0} − 1) + λ = 4 + λ ≤ 5.
36

It follows that δ_{1} = 2 and λ = 1, and 4 ≤ δ_{2} ≤ 5 − λ = 4, so δ_{2} = 4.

If P ∈ M_{2} is a plane of maximum value, then ν(P) = δ_{2} + δ_{1} + δ_{0} ≥ 4 + 2 + 3 = 9. There are seven points in P, so at least one point has value at least ⌈9/7⌉ = 2, and no point has value more that δ_{0} − 1 = 2. We let P ∈ P be a point of value 2. There are three lines through P in P, each of which has value at most 4, or otherwise it would be in M_{1}. Thus the value of P is at most 3 · 2 + 2 = 8, which is impossible. Hence δ_{0} ≥ 4, as required. □

37

38

Binary Construction

In this chapter we construct a value assignment for a five-dimensional, binary code, with the difference sequence (4, 5, 9, 14, 25), which meets the bounds from Chapter 4 with equality. It is easily verified that by uniformly increasing the values of all points, we can get any value for δ_{0} ≥ 4, and equality is maintained.

5.1 The assignment

There are 31 points in PG(4, 2), and we name them

A, B, C, …, Y, Z, Γ, Δ, Θ, Λ, Ξ.

The geometry is defined by the list of lines in Table 5.1. All points are shown in Figure 5.1. Figure 5.2 is a simplified version, showing the points treated specially in the text. We note that the five points A, C, G, K and W span PG(4, 2).

We arbitrarily choose H =^{def} ⟨A, C, G, W ⟩ as a hyperplane of maximum value, and P =^{def} ⟨A, C, K⟩ as a plane of maximum value. We define the hyperplanes G =^{def} ⟨A, C, G, K⟩ and I =^{def} ⟨A, C, G, Δ⟩. Thus P ⊂ G and the intersection of the three hyperplanes G, H, and I, is the plane ⟨A, C, G⟩.

We let the line of maximum value, ℓ, intersect each of the hyperplanes G, H, and I in one point. We make sure that it intersects P, and let ℓ =^{def} ℓ_{95} = {H, T, Δ}. As a point of maximum value, we choose X which is in I.

39

CHAPTER 5. BINARY CONSTRUCTION

ℓ_{i} ν(ℓ_{i})  the points
ℓ_{0}  8  A(3), B(3), C(2)
ℓ_{1}  7  A(3), D(1), E(3)
ℓ_{2}  8  A(3), F (3), G(2)
ℓ_{3}  8  A(3), H(3), I(2)
ℓ_{4}  8  A(3), J(2), K(3)
ℓ_{5}  5  A(3), L(1), M(1)
ℓ_{6}  5  A(3), N(1), O(1)
ℓ_{7}  6  A(3), P (1), Q(2)
ℓ_{8}  6  A(3), R(2), S(1)
ℓ_{9}  8  A(3), T (3), U(2)
ℓ_{10}  7  A(3), V (2), W (2)
ℓ_{11}  8  A(3), X(4), Y (1)
ℓ_{12}  5  A(3), Z(1), Γ(1)
ℓ_{13}  7  A(3), Δ(3), Θ(1)
ℓ_{14}  3  A(3), Λ(0), Ξ(0)
ℓ_{15}  7  B(3), D(1), F (3)
ℓ_{16}  8  B(3), E(3), G(2)
ℓ_{17}  8  B(3), H(3), J(2)
ℓ_{18}  8  B(3), I(2), K(3)
ℓ_{19}  5  B(3), L(1), N(1)
ℓ_{20}  5  B(3), M(1), O(1)
ℓ_{21}  6  B(3), P (1), R(2)
ℓ_{22}  6  B(3), Q(2), S(1)
ℓ_{23}  8  B(3), T (3), V (2)
ℓ_{24}  7  B(3), U(2), W (2)
ℓ_{25}  8  B(3), X(4), Z(1)
ℓ_{26}  5  B(3), Y (1), Γ(1)
ℓ_{27}  6  B(3), Δ(3), Λ(0)
ℓ_{28}  4  B(3), Θ(1), Ξ(0)
ℓ_{29}  5  C(2), D(1), G(2)
ℓ_{30}  8  C(2), E(3), F (3)
ℓ_{31}  8  C(2), H(3), K(3)
ℓ_{32}  6  C(2), I(2), J(2)
ℓ_{33}  4  C(2), L(1), O(1)
ℓ_{34}  4  C(2), M(1), N(1)
ℓ_{35}  4  C(2), P (1), S(1)
ℓ_{36}  6  C(2), Q(2), R(2)
ℓ_{37}  7  C(2), T (3), W (2)
ℓ_{38}  6  C(2), U(2), V (2)

ℓ_{i} ν(ℓ_{i})  the points
ℓ_{39}  7  C(2), X(4), Γ(1)
ℓ_{40}  4  C(2), Y (1), Z(1)
ℓ_{41}  5  C(2), Δ(3), Ξ(0)
ℓ_{42}  3  C(2), Θ(1), Λ(0)
ℓ_{43}  5  D(1), H(3), L(1)
ℓ_{44}  4  D(1), I(2), M(1)
ℓ_{45}  4  D(1), J(2), N(1)
ℓ_{46}  5  D(1), K(3), O(1)
ℓ_{47}  5  D(1), P (1), T (3)
ℓ_{48}  5  D(1), Q(2), U(2)
ℓ_{49}  5  D(1), R(2), V (2)
ℓ_{50}  4  D(1), S(1), W (2)
ℓ_{51}  8  D(1), X(4), Δ(3)
ℓ_{52}  3  D(1), Y (1), Θ(1)
ℓ_{53}  2  D(1), Z(1), Λ(0)
ℓ_{54}  2  D(1), Γ(1), Ξ(0)
ℓ_{55}  7  E(3), H(3), M(1)
ℓ_{56}  6  E(3), I(2), L(1)
ℓ_{57}  6  E(3), J(2), O(1)
ℓ_{58}  7  E(3), K(3), N(1)
ℓ_{59}  6  E(3), P (1), U(2)
ℓ_{60}  8  E(3), Q(2), T (3)
ℓ_{61}  7  E(3), R(2), W (2)
ℓ_{62}  6  E(3), S(1), V (2)
ℓ_{63}  8  E(3), X(4), Θ(1)
ℓ_{64}  7  E(3), Y (1), Δ(3)
ℓ_{65}  4  E(3), Z(1), Ξ(0)
ℓ_{66}  4  E(3), Γ(1), Λ(0)
ℓ_{67}  7  F (3), H(3), N(1)
ℓ_{68}  6  F (3), I(2), O(1)
ℓ_{69}  6  F (3), J(2), L(1)
ℓ_{70}  7  F (3), K(3), M(1)
ℓ_{71}  6  F (3), P (1), V (2)
ℓ_{72}  7  F (3), Q(2), W (2)
ℓ_{73}  8  F (3), R(2), T (3)
ℓ_{74}  6  F (3), S(1), U(2)
ℓ_{75}  7  F (3), X(4), Λ(0)
ℓ_{76}  4  F (3), Y (1), Ξ(0)
ℓ_{77}  7  F (3), Z(1), Δ(3)

ℓ_{i}  ν(ℓ_{i})  the points
ℓ_{78}  5  F (3), Γ(1), Θ(1)
ℓ_{79}  6  G(2), H(3), O(1)
ℓ_{80}  5  G(2), I(2), N(1)
ℓ_{81}  5  G(2), J(2), M(1)
ℓ_{82}  6  G(2), K(3), L(1)
ℓ_{83}  5  G(2), P (1), W (2)
ℓ_{84}  6  G(2), Q(2), V (2)
ℓ_{85}  6  G(2), R(2), U(2)
ℓ_{86}  6  G(2), S(1), T (3)
ℓ_{87}  6  G(2), X(4), Ξ(0)
ℓ_{88}  3  G(2), Y (1), Λ(0)
ℓ_{89}  4  G(2), Z(1), Θ(1)
ℓ_{90}  6  G(2), Γ(1), Δ(3)
ℓ_{91}  8  H(3), P (1), X(4)
ℓ_{92}  6  H(3), Q(2), Y (1)
ℓ_{93}  6  H(3), R(2), Z(1)
ℓ_{94}  5  H(3), S(1), Γ(1)
ℓ_{95}  9  H(3), T (3), Δ(3)
ℓ_{96}  6  H(3), U(2), Θ(1)
ℓ_{97}  5  H(3), V (2), Λ(0)
ℓ_{98}  5  H(3), W (2), Ξ(0)
ℓ_{99}  4  I(2), P (1), Y (1)
ℓ_{100}  8  I(2), Q(2), X(4)
ℓ_{101}  5  I(2), R(2), Γ(1)
ℓ_{102}  4  I(2), S(1), Z(1)
ℓ_{103}  6  I(2), T (3), Θ(1)
ℓ_{104}  7  I(2), U(2), Δ(3)
ℓ_{105}  4  I(2), V (2), Ξ(0)
ℓ_{106}  4  I(2), W (2), Λ(0)
ℓ_{107}  4  J(2), P (1), Z(1)
ℓ_{108}  5  J(2), Q(2), Γ(1)
ℓ_{109}  8  J(2), R(2), X(4)
ℓ_{110}  4  J(2), S(1), Y (1)
ℓ_{111}  5  J(2), T (3), Λ(0)
ℓ_{112}  4  J(2), U(2), Ξ(0)
ℓ_{113}  7  J(2), V (2), Δ(3)
ℓ_{114}  5  J(2), W (2), Θ(1)
ℓ_{115}  5  K(3), P (1), Γ(1)
ℓ_{116}  6  K(3), Q(2), Z(1)

ℓ_{i}  ν(ℓ_{i})  the points
ℓ_{117}  6  K(3), R(2), Y (1)
ℓ_{118}  8  K(3), S(1), X(4)
ℓ_{119}  6  K(3), T (3), Ξ(0)
ℓ_{120}  5  K(3), U(2), Λ(0)
ℓ_{121}  6  K(3), V (2), Θ(1)
ℓ_{122}  8  K(3), W (2), Δ(3)
ℓ_{123}  5  L(1), P (1), Δ(3)
ℓ_{124}  4  L(1), Q(2), Θ(1)
ℓ_{125}  3  L(1), R(2), Λ(0)
ℓ_{126}  2  L(1), S(1), Ξ(0)
ℓ_{127}  8  L(1), T (3), X(4)
ℓ_{128}  4  L(1), U(2), Y (1)
ℓ_{129}  4  L(1), V (2), Z(1)
ℓ_{130}  4  L(1), W (2), Γ(1)
ℓ_{131}  3  M(1), P (1), Θ(1)
ℓ_{132}  6  M(1), Q(2), Δ(3)
ℓ_{133}  3  M(1), R(2), Ξ(0)
ℓ_{134}  2  M(1), S(1), Λ(0)
ℓ_{135}  5  M(1), T (3), Y (1)
ℓ_{136}  7  M(1), U(2), X(4)
ℓ_{137}  4  M(1), V (2), Γ(1)
ℓ_{138}  4  M(1), W (2), Z(1)
ℓ_{139}  2  N(1), P (1), Λ(0)
ℓ_{140}  3  N(1), Q(2), Ξ(0)
ℓ_{141}  6  N(1), R(2), Δ(3)
ℓ_{142}  3  N(1), S(1), Θ(1)
ℓ_{143}  5  N(1), T (3), Z(1)
ℓ_{144}  4  N(1), U(2), Γ(1)
ℓ_{145}  7  N(1), V (2), X(4)
ℓ_{146}  4  N(1), W (2), Y (1)
ℓ_{147}  2  O(1), P (1), Ξ(0)
ℓ_{148}  3  O(1), Q(2), Λ(0)
ℓ_{149}  4  O(1), R(2), Θ(1)
ℓ_{150}  5  O(1), S(1), Δ(3)
ℓ_{151}  5  O(1), T (3), Γ(1)
ℓ_{152}  4  O(1), U(2), Z(1)
ℓ_{153}  4  O(1), V (2), Y (1)
ℓ_{154}  7  O(1), W (2), X(4)

Table 5.1: The lines in PG(4, 2), with the value of each point in parenthesis after the point.

40

[figure: A; F; G; C; B; D; E; W; J; K; I; Γ; Δ; Ξ; X; H; T; V; U; P; S; R; Q; L; Θ; M; Z; O; Λ; N; Y]

Figure 5.1: Representation of PG(4, 2) for construction.

41

CHAPTER 5. BINARY CONSTRUCTION

[figure: A; F; G; C; B; D; E; W; J; K; I; Γ; Δ; Ξ; X; H; T]

Figure 5.2: Simplified sketch of PG(4, 2) for construction.

42

ν(A) = 3 ν(B) = 3 ν(C) = 2 ν(D) = 1 ν(E) = 3 ν(F) = 3
ν(G) = 2 ν(H) = 3 ν(I) = 2 ν(J) = 2 ν(K) = 3 ν(L) = 1
ν(M) = 1 ν(N) = 1 ν(O) = 1 ν(P) = 1 ν(Q) = 2 ν(R) = 2
ν(S) = 1 ν(T) = 3 ν(U) = 2 ν(V) = 2 ν(W) = 2 ν(X) = 4
ν(Y) = 1 ν(Z) = 1 ν(Γ) = 1 ν(Δ) = 3 ν(Θ) = 1 ν(Λ) = 0

ν(Ξ) = 0

Table 5.2: A value assignment in PG(4, 2).

Now we assign the following values:

ν(X) = 4  (5.1)
ν(p) = 3, ∀p ∈ ℓ  (5.2)
ν(p) = 2, ∀p ∈ ⟨C, I⟩  (5.3)
ν(p) = 3, ∀p ∈ P\⟨C, I⟩  (5.4)

This gives us sufficient information to limit our search, so that it may feasibly be done by trial and error on a computer. It can be verified that it is extremal non-chain, and that its difference sequence is indeed (4, 5, 9, 14, 25). We summarise the result in the following theorem:

Theorem 9 If δ_{0} ≥ 3, there exists a binary, five-dimensional, extremal non-chain code with the difference sequence:

δ_{1} = 2δ_{0} − 3
δ_{2} = 4δ_{0} − 7
δ_{3} = 4δ_{1} − 6
δ_{4} = 2δ_{3} − 3

43

44

Appendix A

Index of Notations

• GF(q) – the Galois Field of order q.

• PG(n, q) – the Projective space of dimension n over GF(q).

• PG^{(m)}(k, q) – the set of m-spaces in PG(n, q) (page 2).

• ν(x) – the value assignment function (page 2).

• d_{r} – the rth generalized Hamming weight (page 1).

• (δ_{0}, δ_{1}, … δ_{k}) – the difference sequence. (page 2).

• ℘, ℓ, P – a point, a line and a plane.

• H – a hyperplane in PG(4, q).

• Π_{m} – an m-space.

• ⟨x_{1}, x_{2}, …⟩ – the space spanned by the vectors or points x_{1}, x_{2}, … (page 3).

• C – a [n, k + 1; q] code.

• χ(C) – the support of C (page 1).

• G – a generator matrix for C.

• (C0) – the chain condition (page 5).

• (Ci.j) – the subconditions of the chain condition (page 5).

45 APPENDIX A. INDEX OF NOTATIONS

• (Ni.j) – the non-chain conditions (page 5).

• M_{i} – the set of i-spaces of maximum value (page 4).

• λ, λ_{i} – maximum values, i.e. λ, λ_{i} ∈ ℕ_{0}.

• k – the dimension of a projective geometry.

• k + 1 – the dimension of a code.

• q – the order of a field.

• L, K – sets of projective points.

46

Bibliography

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

[CK96] Wende Chen and Torleiv Kløve. The weight hierarchies of q-ary codes of dimension 4. IEEE Trans. Inform. Theory, 42(6):2265– 2272, November 1996.

[CK97a] 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.

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

[CK98a] 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.

[CK98b] Wende Chen and Torleiv Kløve. Weight hierarchies of linear codes satisfying the chain condition. Designs, Codes and Cryptography, 11, 1998.

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

[CK99b] Wende Chen and Torleiv Kløve. Weight hierarchies of linear codes of dimension 3. Journal of Statistical Planning and Inference, 1999.

47

BIBLIOGRAPHY

[CS99] Wende Chen and Xushun Sun. Weight hierarchies of 7-ary codes of dimension 3 and improved genetic algorithm. Third Shanghai Conference on the Sciences, Codes and Finite Geometry, May 1999. In Chinese, abstract in English.

[EK94] Sylvia Encheva and Torleiv Kløve. Codes satisfying the chain condition. IEEE Trans. Inform. Theory, 40:175–180, 1994.

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

[HKM77] 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.

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

[Klø93] Torleiv Kløve. Minimum support weights of binary codes. IEEE Trans. Inform. Theory, 39(2), March 1993.

[KTFL93] T Kasami, T Takata, T Fujiwara, and S Lin. On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes. IEEE Trans. Inform. Theory, 39(1):242–245, 1993.

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

[Sch98] Hans Georg Schaathun. Upper bounds on weight hierarchies of extremal non-chain codes. Master’s thesis, Universitas Bergensis, 1998. Available at http://www.ii.uib.no/ georg/sci/inf/coding/.

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

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

48