Upper bounds on Weight Hierarchies of Extremal Non-Chain Codes

A Study in a Projective Geometry

Thesis for the degree of Candidatus Scientiarum

Industrial and Applied Mathematics and Informatics Applicable Algebra and Coding Theory

Hans Georg Schaathun

20th December 1998

Department of Informatics

Universitas Bergensis

Book I: The book of results

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

This thesis establish upper bounds for weight hierarchies of such codes, of arbitrary dimension. Constructions are provided to prove the bounds tight for five-dimensional codes.

Contents

Preface 3

I The Mathematics 5

1 Introduction 7 1.1 Notations and definitions . . . . . . . . . . . . . . . . . . . . . 7 1.2 Historical overview . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Projective Geometry 13 2.1 Blocking sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Upper bounds on ENDS 21 3.1 Bounds on subspace values . . . . . . . . . . . . . . . . . . . . 21 3.2 Construction requirements . . . . . . . . . . . . . . . . . . . . 27 3.3 Bounds on the total value . . . . . . . . . . . . . . . . . . . . 29

4 Construction of a non-binary ENDS 31 4.1 The assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.2 Verifying the non-chain conditions . . . . . . . . . . . . . . . . 37 4.3 The conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5 Binary ENDS 43 5.1 General bounds . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Construction requirements . . . . . . . . . . . . . . . . . . . . 46 5.3 Lower bound on δ_{0} . . . . . . . . . . . . . . . . . . . . . . . . 47

1

\underline{CONTENTS}

6 Binary Construction 51 6.1 The assignment . . . . . . . . . . . . . . . . . . . . . . . . . . 51

II The Computer 57

7 Programs 59 7.1 Program overview . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.2 Design and implementation . . . . . . . . . . . . . . . . . . . 60 7.3 Description of components . . . . . . . . . . . . . . . . . . . . 61

8 Projective Geometry Modules 63 8.1 Geometrical representations . . . . . . . . . . . . . . . . . . . 63 8.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 8.3 More details on the implementation . . . . . . . . . . . . . . . 66

9 Value assignment modules 69 9.1 Value assignments . . . . . . . . . . . . . . . . . . . . . . . . . 69 9.2 Details on the implementation . . . . . . . . . . . . . . . . . . 72

10 Using vsh 75 10.1 A non-binary construction . . . . . . . . . . . . . . . . . . . . 75 10.2 A binary construction . . . . . . . . . . . . . . . . . . . . . . 79

11 Man pages 81 vsh(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 gen(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 pgc(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 pgtest(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 pidcheck(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 vdg(1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 valex(4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

III The Appendices 93

A Index of Notations 95

Bibliography 97

2

Preface

This is my thesis for the Cand. Scient. degree. I have been working on it for about 18 months, so now it is time to submit it, even though the work is not quite finished. I have some results, that’s true; but there are many more questions. I hope, however, that someone might enjoy the results I present here; and I look forward to returning to the remaining questions at some later time.

I wish to thank the people who have been working or studying at the institute the last couple of years. They have made it a very pleasant place to be. I would specially like to thank my supervisor, prof. Torleiv Kløve, for suggesting such a thrilling problem to work with, and for good help and advice on finding and verifying solutions.

This thesis is submitted for a degree in Industrial and Applied Informatics and Mathematics, and so it has got two parts. The first part includes the mathematical results which have been the object of the work. I have done my best to keep the mathematics pure. The other part is a set of computer programs, which have been applied to find and verify some of the mathematical results. The ‘industry’ I leave for someone else …

Two more volumes accompany the thesis. Book II contains the source code for the computer programs, and Book III contains data listings from the programs. The data listings may be used to verify the constructions given in the thesis.

georg

Bergen, December 1998

3

4

Part I The Mathematics

5

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 thesis in Section 1.3.

1.1 Notations and definitions

Throughout this paper C will denote a [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}.
7

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 size 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 monotonicity of the generalised Hamming weights, the elements of the difference sequence are strictly 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.

8

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 thesis be used for 3-spaces in PG(4, q).

In PG(4, q) we have that PG^{(1)}(4, q) is the set of lines, PG^{(2)}(4, q) is the set of planes, and PG^{(3)}(4, q) is the set of hyperplanes.

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).

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).

Using our projective representation, we have equivalently a one-to-one correspondence between subcodes, D, of 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)

9

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

max{ν(p) | p ∈ PG(k, q)} = δ_{0}  (1.2)
max{ν(ℓ) | ℓ ∈ PG^{(1)}(k, q)} = δ_{0} + δ_{1}  (1.3)
max{ν(P) | P ∈ PG^{(2)}(k, q)} = δ_{0} + δ_{1} + δ_{2}  (1.4)
max{ν(H) | H ∈ PG^{(3)}(k, 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}}.

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)
10

1.2. HISTORICAL OVERVIEW

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).

1.2 Historical overview

The generalised Hamming weights were introduced as early as 1977 by Helleseth et al [HKM77], though they used the term ‘minimum support weights’. Apparently the minimum support weights didn’t come to much use until Wei [Wei91] reintroduced the parameters in 1991, 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.

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], [CK98b], [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 [CK98c].

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

Chen and Kløve [CK97b], [CK98a] have also divided four-dimensional

11

codes into classes according to which of the conditions, (C0), (C1.1), (C1.2) and (C2.1) (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.

1.3 The problem

The aim of this thesis is to find good upper bounds on the difference sequences of extremal non-chain codes of dimension five and higher. We also want to prove the bounds good, by giving five-dimensional constructions meeting them with equality.

In the process several computer programs are written to aid the study of projective geometries and value assignments.

12

Projective Geometry

Before we start examining value assignments, we will introduce some facts from the theory of projective geometries over finite fields.

2.1 Blocking sets

We know that the smallest subset of a projective space, intersecting any line in at least one point, is a prime. More generally, we can state the following lemma, which is proved in [Hir98].

Lemma 1 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.

It is also interesting to know the minimum size of a subset, L, meeting any r-space in at least one point, without containing a (k − r)-space. We introduce the concept of t-blocking sets.

Definition 2 (t-blocking set) A subset L ⊂ PG(k, q), is called t-blocking set, if it meets any t-space in PG(k, q), but no (k − t)-space is contained in L.

A lot of work is done on 1-blocking sets, which is also named blocking sets. Hirschfeld [Hir98] gives a summary for blocking sets in the projective plane, and Beutelspacher [Beu80] has treated t-blocking sets in projective geometries of arbitrary dimension.

13

CHAPTER 2. PROJECTIVE GEOMETRY

[figure: ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; ⋄; p; a; b; m_{3}; m_{2}; m_{1}; p′]

Figure 2.1: PG(2, 4) as in the proof of Lemma 2. Black points are in L, white points are not. M = {p′, m_{1}, m_{2}, m_{3}}

In the rest of this chapter we introduce a few weak bounds on the size of t-blocking sets in geometries of dimensions 2 and 3. Even though stronger bounds are known ([Beu80], [Hir98]), they are not needed for our purpose, and they would require proofs beyond the scope of this thesis.

2.1.1 The projective plane

Lemma 2 If L ⊂ PG(2, q), such that for any line ℓ, ∅ ≠ L ∩ ℓ, then there is a line ℓ′, such that #(L ∩ ℓ′) ≥ 3.

Proof: By Lemma 1, there are more than two points in L, so let ℓ be a line spanned by two points in L. Obviously #(L ∩ ℓ) ≥ 2.

Assume for a contradiction that no line has more than two points in L. Then ℓ has exactly two points, a and b, in L. Let p ∈ ℓ\L be another point on the line. There are q more lines through p, so let M ⊂ L be a set including exactly one point on each of these lines, and fix one point p′ ∈ M. Since no line has more than two points in L, there are q − 1 distinct lines spanned by

14

2.1. BLOCKING SETS

p′ and one more point in M, intersecting ℓ in q − 1 distinct points, different from p. Thus at least one line is incident with a or b and thus has at least three points in L, proving the lemma by contradiction. □

Corollary 1 For any L ⊂ PG(2, 2) such that any line intersects L in at least one point, there is a line ℓ ⊂ L.

Lemma 3 If L is a blocking set in PG(2, q), then #L ≥ q + 3.

Proof: Lemma 2 says that there is a line, ℓ, such that #(ℓ ∩ L) ≥ 3. Since ℓ ⊄ L, there is a point p ∈ ℓ\L. There are q lines through p beside ℓ, intersecting L in q distinct points. Thus #(L ∩ ℓ) ≥ 3 and #(L\ℓ) ≥ q, and we have #L ≥ q + 3, as required. □

Hirschfeld [Hir98] states that the bound is really

#L ≥ q + \sqrt{q} + 1,

which is tight for q square. We note that for q ∈ {3, 4}, this this gives the same bound as our lemma, if we replace the square root with its ceiling:

q = 3 : #L ≥ 3 + 2 + 1 = 6  (2.1)
q = 4 : #L ≥ 4 + 2 + 1 = 7.  (2.2)

To prove that the bound is tight for q = 3, take two distinct lines, ℓ_{1} and ℓ_{2}, and let p_{1} ∈ ℓ_{1}\ℓ_{2} and p_{2} ∈ ℓ_{2}\ℓ_{1} be two points. Let c be a point on ⟨p_{1}, p_{2}⟩, different from p_{1} and p_{2}. The set L =^{def} ({c} ∪ ℓ_{1} ∪ ℓ_{2})\{p_{1}, p_{2}} is a blocking set of six points, meeting the bound with equality.

Table 2.1 gives a representation of PG(2, 4). It is easily verified that

L =^{def} {A, B, C, F, G, J, K},

satisfies the properties of a blocking set, and the cardinality is indeed 7.

2.1.2 The projective solid

Lemma 4 If L ⊂ PG(3, q) so that any line, ℓ ∈ PG^{(1)}(3, q), intersects L in at least two points, then #L ≥ 2q^{2} + 2q + 2.

15

Lines in PG(2, 4)

ℓ_{0} = {A, B, C, D, E} ℓ_{1} = {A, F, G, H, I} ℓ_{2} = {A, J, K, L, M}
ℓ_{3} = {A, N, O, P, Q} ℓ_{4} = {A, R, S, T, U} ℓ_{5} = {B, F, J, N, R}
ℓ_{6} = {B, G, K, O, S} ℓ_{7} = {B, H, L, P, T } ℓ_{8} = {B, I, M, Q, U}
ℓ_{9} = {C, F, K, P, U} ℓ_{10} = {C, G, J, Q, T } ℓ_{11} = {C, H, M, N, S}
ℓ_{1}1 = {C, I, L, O, R} ℓ_{12} = {D, F, L, Q, S} ℓ_{14} = {D, G, M, P, R}
ℓ_{15} = {D, H, J, O, U} ℓ_{16} = {D, I, K, N, T } ℓ_{17} = {E, F, M, O, T }
ℓ_{18} = {E, G, L, N, U} ℓ_{19} = {E, H, K, Q, R} ℓ_{20} = {E, I, J, P, S}

Table 2.1: A representation of PG(2, 4).

Proof: If L = PG(3, q), then #L = q^{3} + q^{2} + q + 1 > 2q^{2} + 2q + 2.

If L ≠ PG(3, q) take p ∉ L. There are q^{2} + q + 1 lines through p, each of which intersects L in at least two points, for a total of #L ≥ 2q^{2} + 2q + 2 points, as required. □

Lemma 5 If L ⊂ PG(3, q) is a 2-blocking set, then #L ≥ q^{2} + 3q.

Before we start with the proof, recall that a t-arc is a set of t points in a plane, no three of which are collinear. Proof: Suppose L is a 2-blocking set in PG(3, q), and #L < q^{2} + 3q.

By Lemma 4, if all lines have at least two points in L, then #L ≥ 2q^{2} + 2q+2 ≥ q^{2} +3q, so there must be a line, ℓ, with only one point, p, in common with L.

There are q + 1 distinct planes Φ_{i} ⊃ ℓ, i = 0, 1, … q. By Lemma 3, each plane, Φ_{i}, has either a line, ϕ_{i}, or at least q + 3 points in L. When ϕ_{i} exists, it lies in the same plane as ℓ, and so it intersects it. The point of intersection is p, as the only point in both ℓ and L. This way each plane contributes with at least q points beside p, and if ϕ_{i} does not exist, Φ_{i} contributes with two points extra. Let r be the number of indices, 0 ≤ i ≤ q, for which ϕ_{i} does not exist. Then

q^{2} + 3q − 1 ≥ #L ≥ 1 + (q + 1)q + r · 2 = q^{2} + q + 1 + 2r,

so r ≤ q − 1. Thus at least two of the planes, Φ_{i}, contains a line, ϕ_{i}, through p in L. Let α ≠ β be two of these lines. The plane spanned by α and β will be denoted by Δ. Obviously

#(L ∩ Δ) ≥ 2q + 1.  (2.3)
16

For any plane, P, there is a point c ∈ P\L. There are q^{2} lines containing c and not contained in P, and consequently there are at least q^{2} points in L\P. In particular we have

#(L\Δ) ≥ q^{2}.  (2.4)

Assume that any line in Δ has at least two points in L. Then in particular any line through p must have at least one more point beside p in common with L. There are q−1 such lines beside α and β. So #(Δ∩L) ≥ 2q+1+q−1 = 3q. Thus #L ≥ q^{2} + 3q, contrary to assumption.

We can then conclude that there is a line, γ ⊂ Δ, meeting L in exactly one point. All the lines γ, α and β are in Δ, so they must intersect. Both α and β are entirely in L, so γ must intersect both of them in the very same point; that is p ∈ γ. There are q planes Γ_{i}, i = 1, 2, … q, such that γ ⊂ Γ_{i} ≠ Δ. Now we will show that at least two of the planes Γ_{i} have a line each in L, and we use the same kind of argument as we used for the planes Φ_{i}.

By Lemma 3, each plane, Γ_{i}, has either a line, γ_{i}, or at least q+3 points in L. i.e. #((Γ_{i}\Δ)∩L) ≥ q for all i. Let s be the number of indices, 1 ≤ i ≤ q, for which γ_{i} does not exist. Then #(L\Δ) ≥ q^{2} + 2s. We use equation (2.3) to get

q^{2} + 3q − 1 ≥ #L ≥ q^{2} + 2s + #(L ∩ Δ) ≥ q^{2} + 2q + 1 + 2s.

We conclude that s ≤ q/2 − 1, so at least two of the planes Γ_{i} have lines γ_{i} in L. Let η ≠ ζ be two of these lines. Both the lines η and ζ intersect γ in a point in L, that is η ∩ ζ = {p}. This gives us a total of four lines through p, in L: α, β, η and ζ.

Let a be a point on α. There are q distinct lines in Δ, incident with a but not p. Because they intersect α and β in distinct points, they have at least two points in L. If all these lines have three points in L, we have a total of 3q + 1 points in Δ ∩ L, which gives #L ≥ q^{2} + 3q + 1, contrary to assumption. Hence there is a line ψ ∋ a, with exactly two points in L.

Now consider q distinct planes, Ψ_{i}, i = 1, 2, … q, such that ψ ⊂ Ψ_{i} ≠ Δ. The four lines, α, β, η and ζ, intersect Ψ_{i} in four distinct points. If three of these points are collinear, three of the lines are contained in the same plane Θ. Then there are at least 3q + 1 points in Θ ∩ L and q^{2} points in Θ\L, for a total of q^{2} + 3q + 1 in L, contrary to assumption.

17

We conclude that each plane, Ψ_{i}, has a four-arc in L. So it has at least q + 3 points in L, for even if it does have a line in L, the four-arc guarantees two more points that are not on the line. The intersection of Ψ_{i} and Δ has exactly two points, a and b, in L. This gives

#(L ∩ (Ψ_{i}\Δ)) ≥ q + 1, 1 ≤ i ≤ q
#(L ∩ Δ) ≥ 2q + 1;

thus

#L ≥ q(q + 1) + 2q + 1 = q^{2} + 3q + 1,

proving the lemma by contradiction. □

Lemma 6 If L ⊂ PG(3, q) is a 1-blocking set, then #L ≥ q + 3.

Proof: Suppose that L is a blocking set with no more than q + 2 points.

By Lemma 1, there are at least 3 points in L. Any set of three points is contained in a plane, so obviously there is a plane, P, meeting L in at least three points. There is a line, ℓ ⊂ P, which does not meet L, because q + 2 points cannot make a 1-blocking set in P. There are q planes different from P, through ℓ, and each of these planes has a point in L. This gives at least three points in P ∩ L and q points in L\P, for a total of q + 3 points, proving the lemma by contradiction. □

Beutelspacher [Beu80] states that if L is t-blocking set in PG(t + 1, q), then

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

For q = 2, the bound from Lemma 5 is tight:

Lemma 7 There is a 2-blocking set L ⊂ PG(3, 2), such that #L = 10.

Proof: Take two distinct planes A, B, and two points a ∈ A\B, b ∈ B\A.

Let c ∈ ⟨a, b⟩\{a, b}. Let L =^{def} (A ∪ B ∪ {c})\{a, b}.

We have #(A\{a}) = #(B\{b}) = 6 and #(A ∩ B) = 3, so #L = 2 · 6 − 3 + 1 = 10 as required.

18

[figure: c; b; a; A; B]

Figure 2.2: The construction for Lemma 7. Black points are in L, white points are not.

Neither A nor B is in L, and any other plane intersects A ∪ B in at most five points. Including c it can at most intersect L in six out of its seven points, so it is not entirely included in L.

Any line in PG(3, 2) intersects A in at least one point, which is either a or in L. Any line through a also intersects B in at least one point, which is either b or in L. The line ⟨a, b⟩ intersects L in c. Hence L is a 2-blocking set of cardinality 10. □

19

20

Upper bounds on ENDS

Chen and Kløve [CK97a] give upper bounds for the difference sequence of extremal non-chain codes of dimension 4, and they show that the bounds are tight for non-binary codes. In this chapter, we will generalise their bounds to arbitrary dimension. The next chapter then provides a construction proving the bounds tight for five-dimensional, non-binary codes.

We start by proving upper bounds on the subspace values, i.e. on δ_{1} through δ_{k−1}. In the second section we will prove certain properties for value assignments meeting the bounds with equality. We round off the chapter with upper bounds on the total value, ν(PG(k, q)).

3.1 Bounds on subspace values

We start by proving two lemmas, generalising Theorem 2 from [CK97a]. We will see that they make it possible to find a general statement on upper bounds for all differences except the last, δ_{k}, in Theorem 1.

Lemma 8 Given (δ_{0}, δ_{1}, … δ_{k}) satisfying (Nl.m), where 1 ≤ l ≤ m ≤ k−1. If Π_{m} ∈ M_{m}, and

λ =^{def} max{ν(p)|p ∈ Π_{m}},

then

∑_{i=l}^{m} δ_{i} ≤ λ ∑_{i=l}^{m} q^{i} − 1.

21

CHAPTER 3. UPPER BOUNDS ON ENDS

Proof: Let Π_{l−1} be a (l − 1)-space in Π_{m}. By condition (Nl.m), we have

ν(Π_{l−1}) ≤ ∑_{i=0}^{l−1} δ_{i} − 1,

and hence

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

□

For l = m = 1, we get the following corollary, by noting that λ ≤ δ_{0} − 1 and that δ_{1} ≥ 1.

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

Lemma 9 Given (δ_{0}, δ_{1}, … δ_{k}) satisfying (Nl+2.m), where 0 ≤ l ≤ m−2, and m ≤ k−1. If Π_{m} ∈ M_{m} and

λ_{l} =^{def} max{ν(Π_{l}) | Π_{l} ⊂ Π_{m}, Π_{l} ∈ PG^{(l)}(k, q)},

then

δ_{m} ≤ ( ∑_{i=1}^{m−(l+1)} q^{i}) · (∑_{i=0}^{l+1} δ_{i} − 1 − λ_{l}) − ∑_{i=l+2}^{m−1} δ_{i} − 1.

Proof: Let Π_{l} be a l-space in Π_{m}, such that λ_{l} = ν(Π_{l}). For any (l + 1)- space, Π_{l+1}, such that Π_{l} ⊂ Π_{l+1} ⊂ Π_{m}, we have by condition (Nl + 2.m) that

ν(Π_{l+1}\Π_{l}) ≤ ∑_{i=0}^{l+1} δ_{i} − 1 − λ_{l}.

Let S be the set of (l + 1)-spaces containing Π_{l} in Π_{m}, i.e.

S =^{def} {Π_{l+1} ∈ PG^{(l+1)}(k, q) | Π_{l} ⊂ Π_{l+1} ⊂ Π_{m}}.

22

3.1. BOUNDS ON SUBSPACE VALUES

There are Q(m − (l + 1)) such subspaces. Thus we have the following expression for the value of Π_{m}:

∑_{i=0}^{m} δ_{i} = ν(Π_{l}) + ∑_{Π_{l+1}∈S} ν(Π_{l+1}\Π_{l}) ≤ λ_{l} + ( ∑_{i=0}^{m−(l+1)} q^{i}) · (∑_{i=0}^{l+1} δ_{i} − 1 − λ_{l}),

which gives the required expression:

δ_{m} ≤ ( ∑_{i=1}^{m−(l+1)} q^{i}) · (∑_{i=0}^{l+1} δ_{i} − 1 − λ_{l}) − ∑_{i=l+2}^{m−1} δ_{i} − 1.

□

Corollary 3 If (δ_{0}, δ_{1}, … δ_{k}) satisfies (Nm.m), where 2 ≤ m ≤ k − 1, then

δ_{m} ≤ q ∑_{i=0}^{m−1} δ_{i} − qλ − (q + 1),

where

λ =^{def} max{ν(Π_{m−2}) | Π_{m−2} ⊂ Π_{m} ∈ M_{m}, Π_{m−2} ∈ PG^{(m−2)}(k, q)}.

We now have the required tools to prove our first main result, which is a generalisation of Corollary 2 from [CK97a].

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

δ_{j} = q^{j}δ_{0} − ∑_{i=0}^{j} q^{i}, ∀ j, s.t. 2 ≤ j ≤ m − 1,  (3.1)

then

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

23

This gives unconditional bounds for δ_{1} and δ_{2}. We have no bound on δ_{i} for i ≥ 3, unless the bounds on δ_{j}, 2 ≤ j ≤ i − 1, are satisfied with equality. Proof: The case with m = 1 is covered by Corollary 2. Assume for induction that it holds for any m < m̄.

(The inductive hypothesis is not strictly necessary. The proof of the bound on δ_{1}, and the conditions for the values of δ_{2}, … δ_{m̄−1} from equation (3.1) are be sufficient, but we use the inductive hypothesis to emphasise the point where condition (3.1) is necessary.)

Fix Πm̄ ∈ Mm̄, and define for n = 0, 1, …, m̄ − 2,

λ_{n} =^{def} max{ν(Π_{n}) | Π_{n} ⊂ Πm̄, Π_{n} ∈ PG^{(n)}(k, q)}.

Because the code is an ENDS, we have that

λ_{n} ≤ ∑_{i=0}^{n} δ_{i} − 1, 0 ≤ n ≤ m̄ − 2.  (3.3)

If

λ_{m̄−2} = ∑_{i=0}^{m̄−2} δ_{i} − 1,

the bound follows from Corollary 3 and the inductive hypothesis:

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

In this case the bound may be satisfied with equality.

If λ_{0} ≤ δ_{0} − 2, then by Lemma 8, we have

δm̄ ≤ qm̄δ_{0} − 2qm̄ − 1 ≤ qm̄δ_{0} − qm̄ − \frac{qm̄ − 1}{q − 1} − 1 − 1 = qm̄δ_{0} − Q(m̄) − 2,

and the bound holds with inequality. We note that the possibilities when m̄ = 2 are exhausted. For m̄ ≥ 3, however, we have to consider the possibility that

λ_{0} = δ_{0} − 1 ⋀ λ_{m̄−2} ≤ ∑_{i=0}^{m̄−2} δ_{i} − 2.

24

This gives equality in equation (3.3) for n = 0, and inequality for n = m̄ − 2. Let l be the highest value of n for which equality holds, thus 0 ≤ l ≤ m̄ − 3 and

λ_{l} = ∑_{i=0}^{l} δ_{i} − 1 ⋀ λ_{l+1} ≤ ∑_{i=0}^{l+1} δ_{i} − 2.

Let Π_{l} ⊂ Πm̄ be an l-space, such that ν(Π_{l}) = λ_{l}. Let S be the set of (l + 1)-spaces, Π_{l+1}, such that Π_{l} ⊂ Π_{l+1} ⊂ Π_{m}. There are Q(m̄ − (l + 1)) such subspaces. Hence we have an expression for the value of Πm̄:

∑_{i=0}^{m̄} δ_{i} = ∑_{Π_{l+1}∈S} ν(Π_{l+1}\Π_{l}) + λ_{l}

≤ (λ_{l+1} − λ_{l})Q(m̄ − (l + 1)) + λ_{l}

≤ (δ_{l+1} − 1) ∑_{i=0}^{m̄−(l+1)} q^{i} + λ_{l}.

We rearrange terms and simplify, using the inductive hypothesis, to get:

\begin{matrix}δm̄ ≤ & ( ∑_{i=0}^{m̄−(l+1)} q^{i}) · (δ_{l+1} − 1) − ∑_{i=0}^{m̄−1} δ_{i} + ∑_{i=0}^{l} δ_{i} − 1 \\ ≤ & ( ∑_{i=1}^{m̄−(l+1)} q^{i}) · (q^{l+1}δ_{0} − Q(l + 1)) − Q(m̄ − (l + 1)) − ∑_{i=l+2}^{m̄−1} δ_{i} − 1. \end{matrix}

Now we insert the assumed expressions for δ_{i} from equation (3.1) in the subtracted sum and rearrange the terms.

δm̄ ≤ ∑_{i=l+2}^{m̄−1} Q(i) − ∑_{i=l+2}^{m̄−1} q^{i}δ_{0} − 1 + ∑_{i=l+2}^{m̄} q^{i}δ_{0} −

∑_{i=1}^{m̄−(l+1)} q^{i}Q(l + 1) − Q(m̄ − (l + 1))

= {qm̄δ_{0} − q^{m̄−l}Q(l) − Q(m̄ − (l + 1))} +

{q^{m̄−l}Q(l) + ∑_{i=l+2}^{m̄−1} Q(i) − ∑_{i=1}^{m̄−(l+1)} q^{i}Q(l + 1) − 1}

25

We note that the expression in the first pair of braces is the bound we want to prove, so we have to show that the second expression is negative.

q^{m̄−l}Q(l) + ∑_{i=l+2}^{m̄−1} Q(i) − ∑_{i=1}^{m̄−(l+1)} q^{i}Q(l + 1) − 1

= ∑_{j=1}^{m̄−(l+2)} [ ∑_{i=0}^{l+1+j} q^{i} − ∑_{i=j}^{l+1} q^{i}] + q^{m̄−l}Q(l) − q^{m̄−(l+1)}Q(l + 1) − 1

= ∑_{j=1}^{m̄−(l+2)} ∑_{i=0}^{j−1} q^{i} − q^{m̄−l−1} = ∑_{j=0}^{m̄−(l+3)} ∑_{i=0}^{j} q^{i} − q^{m̄−l−1} − 1

= ∑_{i=0}^{m̄−(l+3)}(m̄ − (l + 3) − i + 1) · q^{i} − q^{m̄−l−1} − 1
= − θ(m̂, q),

where

θ(m̂, q) =^{def} qm̂ − ∑_{i=0}^{m̂−2}(m̂ − 1 − i) · q^{i} + 1,

and

m̂ =^{def} m̄ − l − 1.

It remains to prove that θ(m̂, q) is positive; in fact we will prove that θ(m̂, q) ≥ m̂ + q, and we do this by induction on m̂. First we note that θ(1, q) = q + 1, then assume that θ(m̂, q) ≥ m̂ + q, and we observe that:

θ(m̂ + 1, q) = q^{m̂+1} − ∑_{i=0}^{m̂−1}(m̂ − i) · q^{i} + 1

= q [qm̂ − ∑_{i=1}^{m̂−1}(m̂ − i) · q^{i−1} + 1] − q − m̂ + 1

= q [qm̂ − ∑_{i=0}^{m̂−2}(m̂ − 1 − i) · q^{i} + 1] − (m̂ + q) + 1

= qθ(m̂, q) − (m̂ + q) + 1

≥ (q − 1)(m̂ + q) + 1 ≥ m̂ + q + 1.

26

3.2. CONSTRUCTION REQUIREMENTS

Hence θ(m̂, q) is positive and consequently the bound of the theorem holds with inequality. □

3.2 Construction requirements

Ultimately we want to construct codes meeting the bounds with equality. In this section we prove some properties of such codes.

Lemma 10 If (δ_{0}, δ_{1}, … δ_{k}), k ≥ 2, is an ENDS, meeting the bounds on δ_{1} from Theorem 1 with equality, and ℓ ∈ M_{1} is a line of maximum value, then

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

Proof: If δ_{1} = qδ_{0} − (q + 1), then ν(ℓ) = (q + 1)(δ_{0} − 1). There are q + 1 points on ℓ, none of which may have value greater than δ_{0} − 1. Hence all points on ℓ must have value exactly δ_{0} − 1. □

Lemma 11 Let (δ_{0}, δ_{1}, … δ_{k}), k ≥ 3, be an ENDS, and let P ∈ M_{2} be a plane of maximum value. If the bound on δ_{1} and δ_{2} are tight, then there is ℓ ⊂ P, such that

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

Proof: No point in P can have higher value than δ_{0} − 1, or it would be in M_{0}, so let δ_{0} − 1 be the default value for points in P. Let L be the set of all points with value δ_{0} − 2 or less. The total value of P is

\begin{aligned}δ_{0} + δ_{1} + δ_{2} & = δ_{0} + qδ_{0} − (q + 1) + q^{2}δ_{0} − (q^{2} + q + 1) \\ & = q^{2}(δ_{0} − 1) + (q + 1)(δ_{0} − 2), \end{aligned}

so #L ≤ q + 1.

Any line, α, in P must meet L in at least one point, or otherwise α ∈ M_{1}. Hence by Lemma 1, L = ℓ is a line and thus there are exactly q + 1 points in L, each of which has value exactly δ_{0} − 2 as required. □

27

Lemma 12 Let (δ_{0}, δ_{1}, … δ_{k}) be an ENDS for q ≥ 3 and k ≥ 4, and let H ∈ M_{3} be a hyperplane of maximum value. If the bounds on δ_{1}, δ_{2} and δ_{3} from Theorem 1 are satisfied with equality, 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) = δ_{0} − 1, ∀p ∈ H\(P ∪ ℓ).

Proof: Clearly δ_{0} − 1 is the maximum value of any point in H. We call it the default value. Let L be the set of points of reduced value, i.e. the points having value less than δ_{0} − 1.

The total value of H is

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

hence #L ≤ q^{2} + 2q + 2.

Because the code is an ENDS, any line in H has value at most δ_{0}+δ_{1}−1 = (q+1)(δ_{0}−1)−1, and so has at least one point of reduced value. Hence L is a 2-blocking set or it contains a plane. If it is a 2-blocking set, #L ≥ q^{2}+3q, by Lemma 5, which is impossible for q ≥ 3. Thus there is a plane, P, contained in L.

Say that the default values of points in P is δ_{0} − 2. Let α ≠ P be another plane in H. Obviously P ∩ α is a line, so assuming default values,

ν(α) = (q^{2} + q + 1)δ_{0} − q^{2} − 2q − 2 = δ_{2} + δ_{1} + δ_{0}.

Thus α ∈ M_{2}, which is impossible. Hence we have to reduce the value further for at least one point in α, i.e. in each plane different from P.

We have established the default values of δ_{0} −2 for points in P, and δ_{0} −1 for points in H\P. We let K be the set of points, whose values we decrease further, i.e. such that points in P ∩ K have value at most δ_{0} − 3 and points in K\P have value at most δ_{0} − 2.

From equation (3.4) we get that

(q^{2} + 2q + 2) ≥ #P + #K.

Hence #K ≤ q + 1.

28

3.3. BOUNDS ON THE TOTAL VALUE

We had to reduce the values of all planes except possibly P, so K must meet all such planes. First we assume that K does not meet P. Then we can add one point, ℘, from P to K, to get K′ = ℘ ∪ K with at most q + 2 points. By Lemma 6, K′ cannot be a 1-blocking set, so it contains a line, ψ. There are q points in ϕ ∩ K and at most 1 point in K\ϕ, and thus K is contained in some plane, Γ.

The intersection β =^{def} Γ ∩ P has no point in K. There are a total of q + 1 ≥ 4 planes through β, including P and Γ. Since K ⊂ Γ, there are several planes which does not meet K. The contradiction shows that K meets P, and thus K is a line, ℓ, by Lemma 1.

There are exactly q + 1 points in ℓ = K, so we cannot reduce the value of any point in K by more than one. This proves the lemma. □

Corollary 4 If (δ_{0}, δ_{1}, … δ_{k}) is a non-binary ENDS for k ≥ 4, then δ_{0} ≥ 3.

We will return to binary codes later, and prove that they cannot meet the bounds of Theorem 1 with equality.

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

29

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 4. When we take up the study of binary codes, we will derive another bound from the theorem.

Corollary 5 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}.

30

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 5. Assuming that q ≥ 3 and δ_{0} ≥ 3, we want to construct a value assignment, ν : PG(4, q) → ℕ_{0}, meeting these bounds with equality. That is

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

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}

The construction was first made in PG(4, 3) and PG(4, 4) using a computer program. This process is described in detail in Chapter 10.

31

CHAPTER 4. CONSTRUCTION OF A NON-BINARY ENDS

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

Figure 4.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.

4.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.

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.

32

4.1. THE ASSIGNMENT

4.1.1 Defining subspaces of maximum values

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

ν(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 Lemma 11:

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

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.

4.1.2 Lines through X

For any line, α ∋ X, we have

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

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

Figure 4.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.

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⟩.

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⟩.

34

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 4.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.

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
35

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 4.1: A general value assignment for PG(4, q), q ≥ 3, δ_{0} ≥ 3.

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, ν(α) < ν(ℓ).

4.1.3 Finishing touches

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

36

4.2. VERIFYING THE NON-CHAIN CONDITIONS

4.2 Verifying the non-chain conditions

4.2.1 The point

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

M_{0} = {{X}}.

4.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 4.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.

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.

4.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),
37

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,  (4.1)

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

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,  (4.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.  (4.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 (4.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 (4.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 4.3). The fact that A ∉ γ implies that G ∉ γ, so there are but two possible choices for γ.

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.

38

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

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

4.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

39

gives

ν(ℵ ∩ ⟨A, B, C⟩) ≤ (q + 1)δ_{0} − 2q − 3.  (4.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.  (4.5)

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).  (4.6)

We sum up equations (4.4), (4.5), and (4.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 4.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.

4.3 The conclusion

Our construction proves the following theorem.

40

4.3. THE CONCLUSION

Theorem 3 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})

41

42

Binary ENDS

We remember from Chapter 3, several bounds on the differences. We know from the work of Chen and Kløve [CK99], 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 5.2 we will prove some special properties for codes meeting the bounds with equality. Finally we establish a lower bound on δ_{0} in Section 5.3.

5.1 General bounds

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

Theorem 4 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}},  (5.1)
ℓ_{i} =^{def} ⟨P, S_{i}⟩ = {P, S_{i}, T_{i}}, i = 1, 2, …, 2^{k−2}.  (5.2)
43

CHAPTER 5. BINARY ENDS

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

Figure 5.1: Representation of PG(4, 2) for Theorem 4. 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}}.  (5.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}.

44

5.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 6 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 4, 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 2, to get a bound expressed in terms of δ_{k−1}. This bound coincides with the one given in [CK99].

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

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

Proof: From Theorem 2, 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,

45

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  (5.4)
δ_{2} ≤ 4δ_{0} − 7  (5.5)
δ_{3} ≤ 4δ_{1} − 6  (5.6)
δ_{4} ≤ 2δ_{3} − 3  (5.7)

The two first bounds, (5.4) and (5.5), follow directly from Theorem 1, the third, (5.6), comes from Theorem 4, and the fourth one, (5.7), comes from Theorem 5.

5.2 Construction requirements

Lemma 13 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 10, ν(N) = δ_{0} − 1, and

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

so ν(O) ≤ δ_{0}−3. Hence δ_{2} < 4δ_{0}−7 by Lemma 11. 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

46

5.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 4 and 1,

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

and the lemma follows by contradiction. □

5.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 [CK99] 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 thesis, but we introduce two lemmas which will be used to prove that δ_{0} ≥ 4 for any binary, five-dimensional ENDS in the theorem at the end of this section.

Lemma 14 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. □

47

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

δ_{1} ≥ 2  (5.8)
δ_{2} ≥ δ_{0} + 1.  (5.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 6 If (δ_{0}, δ_{1}, δ_{2}, δ_{3}, δ_{4}) is a binary ENDS, then δ_{0} ≥ 4.

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

We have from Theorem 5 that

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

and from Lemma 14 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.
48

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. □

49

50

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 5 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.

6.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 6.1. All points are shown in Figure 6.1. Figure 6.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.

51

CHAPTER 6. 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 6.1: The lines in PG(4, 2), with the value of each point in parenthesis after the point.

52

[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 6.1: Representation of PG(4, 2) for construction.

53

CHAPTER 6. BINARY CONSTRUCTION

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

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

54

ν(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 6.2: A value assignment in PG(4, 2).

Now we assign the following values:

ν(X) = 4  (6.1)
ν(p) = 3, ∀p ∈ ℓ  (6.2)
ν(p) = 2, ∀p ∈ ⟨C, I⟩  (6.3)
ν(p) = 3, ∀p ∈ P\⟨C, I⟩  (6.4)

This gives us sufficient information to limit our search, so that it may feasibly be done by trial and error on a computer. The value assignment shown in Table 6.2, has been found by a computer program as described in Section 10.2. 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 7 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

55

56

Part II The Computer

57

Programs

This and the following chapters describe a set of computer programs, which have been used to validate the results and create sample constructions for the thesis.

We start in this chapter by giving an overview, and describing some general modules. In the Chapters 8 and 9, we will look at modules related to projective geometries and value assignments, respectively. Chapter 10 provides an example of how to use vsh(1). Unix manual pages for the programs and file formats can be found in Chapter 11.

The header files provides a comment for every function, and is suggested for an overview of functions.

A key task of the system is to determine the difference sequence of a value assignment, as well as which of the conditions (Ci.j) and (C0) are satisfied. We call this to classify the value assignment.

7.1 Program overview

• vsh(1) is an interactive program to inspect value assignments and their properties. The program is command driven, and it can also run in batch. It has been the most useful tool so far.

• pgc(1) creates the projective geometry and sets up the data structure for gen(1).

• gen(1) searches a large set of possible value assignments and classifies them.

59

CHAPTER 7. PROGRAMS

• vdg(1) translates the binary output from gen(1) to readable output. It can also classify value assignments given on file.

• pidcheck(1) is yet another companion of gen(1), written to restart gen(1) automatically when it is accidentally killed. It is supposed to be run by cron(8).

• pgtest(1) is not a very refined tool. It was first created to test functions and debug the data structure, but it can indeed do some computations in projective geometry, and it can translate between different file formats.

7.2 Design and implementation

The original idea was to search a large number of value assignments for ‘good’ difference sequences. Efficiency was the main goal in the early stages of programming. The data structure is large, because recomputation of data is costly. The choice of C as the programming language was also made to get efficiency. Despite all efforts, feasible applications have not been found for codes of dimension 5 or higher.

When the idea of extensive searches was abandoned, a program to classify a given value assignment was desired. The first implementation was vdg(1), which takes the value assignments from file. A much better solution for our purposes has been to use an interactive program, so that values may quickly be changed and the assignment reclassified. This idea is implemented in vsh(1).

When vsh(1) was written, a lot of C code existed, and it was a natural choice to use it to test the new ideas. Significant extensions became necessary, however, and the system has grown a bit too large to be easily maintained in C. To work in large geometries, it is no longer practical to look up incidences in arrays, because the data structure grows too large. For instance, it takes vsh(1) about five minutes on a 300MHz Ultra Sparc to build the data structure for PG(5, 3), using about 34Mb of memory.

If a similar project is undertaken in the future, vsh(1) should probably be reimplemented from scratch. With a reasonable representation of points and subspaces, any incidence relations can be computed at need. Efficiency is not likely to be a problem for any interactive program. Another suggested feature is some way to extract subspaces from a construction, and classify

60

7.3. DESCRIPTION OF COMPONENTS

the subcodes they define; and conversely to take a construction and use it as a subspace in a new construction. Better object-orientation is expected to make both features possible.

The system is divided into a number of modules, but the modularisation is only partial. To keep things as simple as possible, principles of encapsulation are frequently violated. Some modules fail to deallocate memory. This has been done deliberately when the consequences are believed to be negligible.

The system is not robust, and hardly any error checking is made. In vsh(1) one can easily experience segmentation violation by giving invalid arguments to commands.

7.3 Description of components

7.3.1 Miscellaneous modules

aux (aux.h,aux.c) contains functions to write standardised messages on stdout, sending e-mail reports, and reading and writing short integers on file in hardware independent binary format.

prep (prep.h,prep.c) sets up the global data structure used by gen(1) and vdg(1).

vsh (vsh.c,vsh.h) is the main function for vsh(1).

lex (lex.l,vsh.h) provides the command parser for vsh(1), implemented in flex(1).

pgc (pgc.c) is the main function for pgc(1).

gen (gen.c) is the main function for gen(1).

signal (signal.h,signal.c) controls the signal handling for gen(1).

vdg (vdg.c) is the main function for vdg(1).

pgtest (pgtest.c) is the main function for pgtest(1).

61

7.3.2 Common header files

• common.h contains common macros and definitions, and it includes other common header files.

• errors.h defines error messages and exit codes.

• gen.h contains configuration settings intended to be specified at compile time.

7.3.3 Implementation of pidcheck

This program is intended to be run by crontab(1), and automatically restart programs when they accidentally get killed. Simple scripts have been used to install a cron job before the main process (i.e. gen(1)) was started. The main process (e.g. gen(1)) creates a file named ‘active’, with all data needed by pidcheck(1).

To check if the process is still running, pidcheck uses sigsend(2) with the null signal.

The pidcheck(1) program does not share any modules with the other programs. The following modules are used by pidcheck(1):

logenv (logenv.h,logenv.c) reads the active file and exports the data to the environment for pidcheck(1). It can also read the same data from the environment.

pidcheck (pidcheck.c) contains the main function.

62

Projective Geometry Modules

8.1 Geometrical representations

A coordinate representation of a point in PG(k, q), is a vector in a (k + 1)- dimensional vector field over GF(q). Each projective point has q − 1 representatives. When a unique representative is needed, we use the vector with one as the first non-zero coordinate. We call this the normal representative.

We represent the elements of a Galois field by numbers of type char. A vector over a small field, is represented by an array of k + 1 chars.

Occasionally an ordering of the points is necessary. We order the points according to their coordinates, i.e. (x_{0}, … x_{k}) comes before (y_{0}, … y_{k}) if for some i, 0 ≤ i ≤ k, x_{i} < y_{i} and x_{j} = y_{j} for all j < i; according to the numeric values of the coordinates. This ordering induces a numbering, where the first point in the order is point no. 0. This provides us with an alternate and more compact representation of the points, called the number representation.

8.2 Overview

8.2.1 The simple representation

When gen(1) does an exhaustive search, we want it to look up subspace relations as fast as possible. Therefore we use the number representation of points, and keep all relations between subspaces and superspaces in arrays. This is handled by the module pg.

63

CHAPTER 8. PROJECTIVE GEOMETRY MODULES

Module: pg

Files: pg.h,pg.c

This module defines the t_pg struct, which contains the tables of subspace relations. To avoid repeating expensive exponentiations, there are also tables for the number of points in any subspace, the number of subspaces of any given dimensions, and the number of m-spaces containing a given n-space.

The tables of subspace relations are loaded from file, while the others are computed using functions in the module. All functions to create the files are in the module pginit. Points are represented by the data type t_ps, using the number representation described above.

The subspace relations are stored in the member ps of t_pg. This member is a four-dimensional array of type t_ps. If ps[i][j][k][l] is equal to m, it means that j-space no. m is a superspace of i-space no. k. The different superspaces of the same i-space are sorted, so that ps[i][j][k][l] is less than ps[i][j][k][l+1]. This member must in most cases be directly referenced, while the other members should be accessed using the macros defined

in pg.h.

8.2.2 The coordinate representation

Using the coordinate representation of points, all other properties of the geometry can be computed. The following modules take care of the basic operations required.

Module: gf

Files: gf.h,gf.c

This module handles multiplication and addition in small Galois Fields. The multiplication and addition tables are hard coded in the module, as we don’t expect to need fields of order greater than five.

The field elements are represented as chars, 0, 1, …, q − 1, where q is the order of the field. When q is prime, arithmetic operations modulo q are used. Otherwise the different symbols are arbitrarily chosen, except that 1 and 0 are the multiplicative and additive identities, respectively.

Module: points

Files: points.h,points.c

This module provides data types for projective points, represented by numbers or by coordinates.

64

8.2. OVERVIEW

There are two functions to translate a normal representative to a number. They work recursively, so that pg_getno() translate the first coordinates up to the first non-zero entry, and then pt_vno() take the last coordinates, as if it were an affine coordinate vector. In the same way, pt_fromno() and pt_nov() translate from numbers to coordinates.

The module provides functions for addition and scalar multiplication of vectors, and the function pt_normalize(), which is used to replace an arbitrary representative vector by the normal representative.

Finally there is a printing routine, writing the coordinates in ASCII.

Module: base

Files: base.h,base.c

This module defines the struct t_bas for a basis of points. The functions include bas_comb(bas,d,k,q) to form a linear combination of the points in a t_bas. The integer d is written in radix q, so that d = ∑_{i=0}^{m} d_{i}q^{i} and the point returned is found by adding d_{0} times the last point in the basis, d_{1} times the second last, and so on, up to d_{m} times the first point in the basis, where m is the dimension of the basis. The normal representative of the new point is returned.

8.2.3 The complete incidence tables

These modules find subspaces by use of the coordinate representation of points. They are required to create the arrays used in the simple representation.

Module: subspace

Files: subspace.h,subspace.c

The struct t_msp defines a subspace, represented by a basis (of type t_bas) and by a unique number assigned when the space is created.

The member pt is a character array with an entry for each point, marking it either TRUE, for a member, or FALSE for a non-member. Thus we can quickly determine whether a given point is contained in the subspace or not. The member bas is a basis of type t_bas.

There is a function to determine if a given space is a subspace of another. This works by testing if each point in the basis of the first space is contained in the other one.

65

Module: pgmsp

Files: pgmsp.h,pgmsp.c

This module defines the t_s struct, containing pointers to t_msp structs for every subspace in the geometry. The module also provides different printing routines for vsh(1), depending on a global variable of type t_s. These functions should be able to produce lists of superspaces containing a given subspace and vice versa.

Module: pginit

Files: pginit.h,pginit.c

This module contains the functions to create subspace tables and store them on file. Refer to Section 8.3.1 for details on the implementation.

Module: pgaux

Files: pginit.h,pgaux.c

This module defines a quasi-queue of points, t_ptq, which is used by pginit. It has an array with an entry for each point, marking it either TRUE for a member or FALSE for a non-member. It has functions to return and remove the next point, and to simply remove a set of points.

8.3 More details on the implementation

8.3.1 Creating the geometry

The projective geometry is created by using the pg_create() function. The main part of the algorithm is as follows:

1. s := new instance of t_s.

2. ptno := the number of points in PG(k, q).

3. j := 0

4. for p := 0 … ptno − 1:

(a) Create a t_bas, bas, of dimension 0 with p as the only point.

(b) s.s[0][p] := a new instance of t_msp, spanned by bas.

5. for m := 0 … k − 2:

(a) elno := number of m-spaces in PG(k, q).

(b) For i := 0 … elno − 1.

66

8.3. MORE DETAILS ON THE IMPLEMENTATION

i. Q := a queue containing all points. ii. Remove from Q, all points in s.s[m][i]. iii. Remove from Q, all points contained in some previously cre-

ated (m + 1)-space, Π ⊃ s.s[m][i]. iv. For each point p ∈ Q:

A. Let s.s[m + 1][j] be the subspace spanned by the points

in the basis of s.s[m][i] and the point p. B. Remove the points in s.s[m + 1][j] from Q. C. For e := i + 1 … elno − 1:

• If s.s[m + 1][j] ⊃ s.s[m][e], insert s.s[m + 1][j] in the

array, pg.ps, as a superspace of s.s[m][e]. D. Insert s.s[m + 1][j] in the array in pg as a superspace of

s.s[m][i]. E. ++ j

Now we have recorded for each m-space, Π, the (m+1)-spaces containing Π. It remains to record the m′-spaces containing Π for m′ > m + 1. We do this the trivial way, by checking for every possible combination of an m-space and an m′-space.

67

68

Value assignment modules

The simplest data structure for a value assignment, is a struct, t_v, with a pointer to an array with an element storing the value for each point. However, to classify the value assignment, we need a more complicated structure, t_val, storing also the values for each subspace.

9.1 Value assignments

The discussion of the value assignment modules is split into two subsections. The so-called basic modules are the ones used by gen(1), and they do not use global variables. The so-called complex modules depend on global variables, especially a t_s variable.

9.1.1 Basic modules

Module: val

Files: val.h,val.c

This module defines the t_val struct which stores the value assignment, including the values of subspaces. There are functions for file handling and printing of ASCII representations. Values of individual points may be set, subspace values may be recomputed; the value assignment can be classified, and one can step through all possible value assignments.

The t_val struct has a pointer to a set of t_mval structs, storing the maximum values of subspaces, and references to subspaces attaining the maximum value. The v member is a pointer to t_v, storing the value assignment

69

CHAPTER 9. VALUE ASSIGNMENT MODULES

and its classification. The member val is a two-dimensional array of values for all points and subspaces, such that val[0] points to the value assignment stored as a member of v. There is also a boolean array marking whether the value of each point is fixed or not. Most functions changing values, will not change fixed values.

The module contains several I/O functions, to read and write binary files and to print ASCII output, even though these mainly use the corresponding functions related to the t_v structure, using the member v.

Module: valv

Files: val.h,valv.c

The t_v struct defined in this module, contains the data we want to store about each value assignment, that is the class number and difference sequence as well as the value of each point. Functions for file handling are included, as well as a comparison function, v_compare(), for use with the binary search trees. The value assignment and the classification can also be printed nicely in ASCII.

The constructor, v_alloc(), allocates memory in such a way that memory cannot be deallocated. It will also fail if several t_pg instances are used simultaneously. If one switches between two geometries, v_alloc() must be called with a t_pg NULL pointers to reinitialise itself. However, we don’t really want to do that, due to the memory leak.

Module: valaux

Files: valaux.h,valaux.c

This module contains two auxiliary data structures: t_ds, which stores a difference sequence, and t_mval, which stores the maximum value as well as a stack (of type t_stack) of all subspaces attaining this value. There are functions to produce ASCII prints of the data.

Module: vtree

Files: vtree.h,vtree.c

This module defines the t_vt struct, which uses a binary search tree (tsearch(3C)) to store value assignments of type t_v. The ordering in the search tree is induced by the function v_compare() from the valv module.

A value assignment is inserted by the vt_insert() function, taking a pointer to t_val as an argument. If there already is a value assignment with the same difference sequence of the same class, nothing is done, otherwise the t_v struct is extracted from t_val and inserted in the tree. Then new memory is allocated for a t_v instance, and the pointer from t_val is

70

9.1. VALUE ASSIGNMENTS

set to point to the new memory. This is handled by the val_freev() function from the val module.

There are also I/O functions for binary data files and ASCII prints.

Module: stack

Files: stack.c,stack.h

This is a simple array implementation of a stack of subspaces, t_stack, with the additional possibility of traversing the stack without popping, and to discard all elements and replace them with a single new one.

Module: valex

Files: valex.l,val.h

This is a parser to read value assignments from file. It is implemented in flex(1). The file format is described in the man page for valex(4) (see Chapter 11).

9.1.2 More complex modules

Module: pgval

Files: pgval.h,pgval.c

This module provides vsh(1) with functions to look up in the geometry and print points and values for subspaces. The implementation resemble that of pgmsp, and the two modules depend on the same global variables. This module includes a function to reinitialise the global variables for vsh(1).

Module: valmsp

Files: valmsp.h,valmsp.c

This module depends on a global t_s variable, s, and it provides vsh(1) with functions to set and fix values of all points in a given subspace. It also provides the val_incprobe() function used by the ‘probe’ command in vsh(1).

Module: nametab

Files: nametab.h,nametab.c

The symbolic names used in vsh(1) are defined by this module. Lowercase letters represents a pair (m, s) identifying m-space number s, while uppercase letters represent a number p, identifying point number p. There are functions to assign values to these names, and to take a name and fill the data it represents into an argument vector as used by vsh(1).

71

9.2 Details on the implementation

9.2.1 Exhaustive search

When gen(1) searches for value assignments, it initialises the data structure with the val_stepinit() function, and traverses the possible value assignments step by step with the val_stepval() function.

During this search, we try to exclude some assignments which are equivalent to assignments we do check. We do this by choosing a set of projectively independent ‘control points’ spanning the space, in such a way that the space spanned by the first m control points include exactly the points up to, but not including the next control point. We assume that each control point has at least as high value as any of the succeeding points. We also assume that the first q + 1 points are sorted by decreasing value.

Since differences must be positive, we initialise all control points, but the first one with 1. The value of the first control point, point no. 0, is set to δ_{0}.

When we step through the assignment, we start at the last point and increase its value by one. The maximum allowed value of a point is the value of the last control point in front of it, and when this maximum is exceeded, the value is reset to 0 (or 1 for a control point), and the value of the predecessor is increased instead.

If only the value of the last point is changed, we only add one to the value of each subspace containing it. Otherwise we recompute all subspace values using val_sumval().

9.2.2 Allocating memory

Because we keep value assignments in a search tree, a lot of memory is allocated for t_v structs. To reduce the number of calls to malloc(3), the v_alloc() function allocates a large amount of memory when it is first called. On later calls, it returns blocks from this memory. When needed, more memory is allocated with malloc(3).

No function to deallocate the memory used by t_v is provided, but for the original application, that would not be necessary. New applications may suffer from memory leak.

The number of size_t units required for a t_v struct, is kept in the variable v_size. To provide aligned pointers, we assume that by adding sizeof(void*) to a pointer aligned for any use, we get a pointer which is

72

9.2. DETAILS ON THE IMPLEMENTATION

also aligned for any use. Therefore we make sure that v_size is a multiple of sizeof(void*).

9.2.3 Classification

The class number of a value assignment is an integer with one bit for each of the conditions, (Ci.j), which is defined, including the chain condition, (C0). We associate with each bit, starting with the least significant one, a condition in the following order:

(C1.1), (C1.2), … (C1.k − 1), (C2.1), … (Ck − 1.1), (C0).

The most significant bit is related to the chain condition. If (C0) is true, the corresponding bit is 1, while all other bits are 0. Hence a five-dimensional, chained code is class no. 64.

If (C0) is false, the corresponding bit is 0, and any other bit is 1 if and only if the corresponding condition is true. Thus extremal non-chain codes are always class no. 0.

The classification algorithm (val_getclass()), initialises the class number to 0, and then starts searching for subspaces satisfying the first condition. As soon as a pair of subspaces satisfying the condition is found, the corresponding bit is turned on, and the algorithm proceeds with the next condition.

If all the conditions (Ci.j) are true, the algorithm checks separately for the chain condition with the function val_chained().

Classification also requires us to find the difference sequence, but that’s a straight forward calculation, as long as we continuously keep track of maximum subspace values.

73

74

Using vsh

This chapter shows how vsh(1) was used to create the construction of Chapters 4 and 6. It is hoped that it can serve two purposes, by being a realistic example of how to use vsh(1), and by outlining the line of thought behind the constructions. Keep in mind, though, that the sessions described are quite experimental in nature, and thus educational clarity may have suffered to the benefit of realism.

10.1 A non-binary construction

10.1.1 Description

For easy reference, the points have the same names in this chapter, as they have in Chapter 4. We use δ_{0} = 3 as the maximum value for any point.

We start by loading the geometry with ‘pg’ and clearing the assignment with ‘clear’. The latter also defines a maximal set of projectively independent points, A, B, C, D and E.

vsh:1> pg 4 3
vsh:2> clear

Our first task is to define the values of points in a hyperplane of maximum value. The command ‘spdef’ defines a subspace by spanning a set of points, thus we let a = ⟨A, B⟩, b = ⟨A, B, C⟩, and h = ⟨A, B, C, D⟩.

vsh:3> spdef a A B
vsh:4> spdef b A B C
vsh:5> spdef h A B C D

75

CHAPTER 10. USING VSH

We give the value 0 to points in a, 1 to points in b and 2 to points in h. We assign values to the smaller sets first, because ‘spset’ don’t change the values of points that already have a value.

vsh:6> spset a 0
vsh:7> spset b 1
vsh:8> spset h 2

The hyperplane h meets the requirements of Lemma 12.

Now we turn to a line of maximum weight. The ‘line’ command assigns names the points on line spanned by two given points. The commands below will name the points on ⟨D, E⟩, starting with F, and the points on ⟨A, E⟩, starting with X.

vsh:9> line F D E
vsh:10> line X A E

Now D, E, F, G are distinct points on the same line, and A, E, X, Y are distinct points on another line. We let l be the line spanned by the points Y and F and give all its points the value 2.

vsh:11> spdef l Y F
vsh:12> spset l 2

Thus l meets the requirements of Lemma 11.

We let X be the point of maximum value, and assign a fixed value to it:

vsh:13> setfix X 3

We need the numbers of the points on some of the lines through X. This can be found with the ‘span’ command, listing the points with values in the subspace spanned by the given points.

vsh:14> span X F
1-space[ 536] (0):   15:2*   41:3*   67:2*   96:-
vsh:15> span X G
1-space[ 509] (0):   14:2*   41:3*   69:-    94:-

The total value of the subspace is printed in parenthesis. It is zero because we haven’t asked to get it computed yet, neither can it be computed as long as several points (e.g. no. 69 and 96 above) have no value.

Information about a particular subspace is printed with the ‘space’ command:

vsh:16> space l
Points in 1-space #510:
14 42 67 95
vsh:17> span X 95
1-space[ 482] (0):   13:2*   41:3*   68:-    95:2*

76

10.1. A NON-BINARY CONSTRUCTION

The output tells us that point no. 95 is the last point on l, that is the intersection of l and ⟨A, B, C, G⟩. The line spanned by X and point no. 95 (W) contains point no. 68 (V), to which we will assign a value of 0.

vsh:18> setfix 68 0

We define a plane x = ⟨A, B, X⟩ and assign the value 2 to all its points, which have no value yet.

vsh:19> spdef x A B X
vsh:20> spset x 2

Before we can run ‘probe’ with success, we have to establish a plane of maximum value. We define the line m = ⟨C, G⟩ and the plane p = ⟨C, D, G⟩. The points on m get the value 1 and the remaining points in p get the value

2. Then p meets the requirements of Lemma 11.

vsh:21> spdef m C G
vsh:22> spdef p C D G
vsh:23> spset m 1
vsh:24> spset p 2

We define the hyperplane g, and assign all its points on g get the fixed value 0.

vsh:25> spdef g A B C G
vsh:26> spset g 0

We can inspect the entire value assignment with ‘pvp’:

vsh:27> pvp
;
   0:0*    1:0*    2:0*    3:0*    4:1*    5:1*    6:1*    7:1*    8:1*    9:1*
  10:1*   11:1*   12:1*   13:2*   14:2*   15:2*   16:2*   17:2*   18:2*   19:2*
  20:2*   21:2*   22:2*   23:2*   24:2*   25:2*   26:2*   27:2*   28:2*   29:2*
  30:2*   31:2*   32:2*   33:2*   34:2*   35:2*   36:2*   37:2*   38:2*   39:2*
  40:2*   41:3*   42:2*   43:2*   44:2*   45:2*   46:2*   47:2*   48:2*   49:2*
  50:-    51:-    52:-    53:-    54:-    55:-    56:-    57:-    58:2*   59:-
  60:-    61:-    62:-    63:-    64:-    65:-    66:-    67:2*   68:0*   69:-
  70:-    71:-    72:-    73:-    74:-    75:-    76:2*   77:-    78:-    79:-
  80:-    81:-    82:-    83:-    84:-    85:2*   86:-    87:-    88:-    89:-
  90:-    91:-    92:-    93:-    94:1*   95:2*   96:0*   97:0*   98:0*   99:0*
 100:0*  101:0*  102:0*  103:1*  104:0*  105:0*  106:0*  107:0*  108:0*  109:0*
 110:0*  111:0*  112:1*  113:0*  114:0*  115:0*  116:0*  117:0*  118:0*  119:0*
 120:0*

A lot of points have no value yet, so we set a default of 1 value with ‘cset’, but these values are not fixed, as a second run of ‘pvp’ shows.

77

vsh:28> cset 4 0 1 0
vsh:29> pvp
;
   0:0*    1:0*    2:0*    3:0*    4:1*    5:1*    6:1*    7:1*    8:1*    9:1*
  10:1*   11:1*   12:1*   13:2*   14:2*   15:2*   16:2*   17:2*   18:2*   19:2*
  20:2*   21:2*   22:2*   23:2*   24:2*   25:2*   26:2*   27:2*   28:2*   29:2*
  30:2*   31:2*   32:2*   33:2*   34:2*   35:2*   36:2*   37:2*   38:2*   39:2*
  40:2*   41:3*   42:2*   43:2*   44:2*   45:2*   46:2*   47:2*   48:2*   49:2*
  50:1    51:1    52:1    53:1    54:1    55:1    56:1    57:1    58:2*   59:1
  60:1    61:1    62:1    63:1    64:1    65:1    66:1    67:2*   68:0*   69:1
  70:1    71:1    72:1    73:1    74:1    75:1    76:2*   77:1    78:1    79:1
  80:1    81:1    82:1    83:1    84:1    85:2*   86:1    87:1    88:1    89:1
  90:1    91:1    92:1    93:1    94:1*   95:2*   96:0*   97:0*   98:0*   99:0*
 100:0*  101:0*  102:0*  103:1*  104:0*  105:0*  106:0*  107:0*  108:0*  109:0*
 110:0*  111:0*  112:1*  113:0*  114:0*  115:0*  116:0*  117:0*  118:0*  119:0*
 120:0*

Now we count the points and find that we have fixed the values of 82 points.

vsh:30> count
82 fixed values.

As all points have got a value, it is possible to classify the assignment:

vsh:31> veval
#0 ( 3, 5, 14, 41, 73 )

It tells us that the assignment has class no. 0 (ENDS), as required. The difference sequence is as desired, except for the last element, δ_{4}.

We use probe to increase the values. Each point is examined, and the value is increased by one if it won’t make the assignment change class. Fixed values are not increased. The output lists a lot of points getting an increased value.

vsh:32> probe
Increasing value of point #50.
Increasing value of point #52.
[...]
Increasing value of point #93.

A second classification confirms that we have the desired difference sequence.

vsh:33> veval
#0 ( 3, 5, 14, 41, 100 )

78

10.2. A BINARY CONSTRUCTION

Finally we print the assignment, and we list the subspaces of the different dimensions using ‘max’.

vsh:34> pvp
;
   0:0*    1:0*    2:0*    3:0*    4:1*    5:1*    6:1*    7:1*    8:1*    9:1*
  10:1*   11:1*   12:1*   13:2*   14:2*   15:2*   16:2*   17:2*   18:2*   19:2*
  20:2*   21:2*   22:2*   23:2*   24:2*   25:2*   26:2*   27:2*   28:2*   29:2*
  30:2*   31:2*   32:2*   33:2*   34:2*   35:2*   36:2*   37:2*   38:2*   39:2*
  40:2*   41:3*   42:2*   43:2*   44:2*   45:2*   46:2*   47:2*   48:2*   49:2*
  50:2    51:1*   52:2    53:2    54:2    55:2    56:2    57:2    58:2*   59:1*
  60:1*   61:1*   62:1*   63:1*   64:1*   65:1*   66:1*   67:2*   68:0*   69:1*
  70:2    71:2    72:2    73:2    74:2    75:2    76:2*   77:2    78:1*   79:2
  80:2    81:2    82:2    83:2    84:2    85:2*   86:2    87:1*   88:2    89:2
  90:2    91:2    92:2    93:2    94:1*   95:2*   96:0*   97:0*   98:0*   99:0*
 100:0*  101:0*  102:0*  103:1*  104:0*  105:0*  106:0*  107:0*  108:0*  109:0*
 110:0*  111:0*  112:1*  113:0*  114:0*  115:0*  116:0*  117:0*  118:0*  119:0*
 120:0*
vsh:35> max 0
[3]: 41
vsh:36> max 1
[8]: 955 930 902 871 846 818 734 703
678 650 619 594 566 510
vsh:37> max 2
[22]: 481
vsh:38> max 3
[63]: 0
vsh:39>

We note that there are several lines of maximum values, but only one point, one plane and one hyperplane, consistent with the analysis of Chapter

4. In the supplements of the thesis, a complete listing of subspaces is provided, as it is created by the ‘printall’ command in vsh(1).

10.2 A binary construction

We will try to construct an optimal, binary, five-dimensional ENDS, for δ_{0} = 4; i.e. we want the difference sequence (4, 5, 9, 14, 25).

We recall the argument in Chapter 6. The names of the points correspond to numbers in the computer representation as follows:

A ∼ 0, B ∼ 1, … Y ∼ 24, Z ∼ 25, Γ ∼ 26, Δ ∼ 27, Θ ∼ 28, Λ ∼ 29, Ξ ∼ 30.

We write a valex file with the following definition:

79

; Lemma 14: probe to get ENDS ( 4, 5, 9, 14, 25 )
  @fix=1
  2:2 8:2 9:2
  0:3 1:3 7:3 10:3
  5:2 6:2
  23:4
  @fix=0
  19:3 27:3
  15:1 16:2 17:2 18:1 20:2 21:2 22:2
  3:1 4:3

The first line assigns values to the points in ℓ, the second and third lines give values to the remaining points in P. The fourth line gives a value to the point X. These values are completely determined by the theoretical analysis in Chapter 6, so they are fixed.

The last three lines give values to points in H, and make sure that the value of H is higher than the value of any other hyperplane. The remaining points will be initialised with value of zero by command no. 3 below. Now we can run the following:

vsh:1> open sk1
vsh:2> next
New value assignment:
; Lemma 14: probe to get ENDS ( 4, 5, 9, 14, 25 )
End of assignment.
vsh:3> cset 4 0 0 0
vsh:4> veval
#0 ( 4, 5, 9, 13, 17 )
vsh:5> qprobe
vsh:6> veval
#0 ( 4, 5, 9, 14, 25 )
vsh:7> pvp
;
   0:3*    1:3*    2:2*    3:1*    4:3*    5:3     6:2*    7:3*    8:2*    9:2*
  10:3*   11:1    12:1    13:1    14:1    15:1*   16:2*   17:2*   18:1*   19:3*
  20:2*   21:2*   22:2*   23:4*   24:1    25:1    26:1    27:3*   28:1    29:0*
  30:0*

We get the desired difference sequence, and the value assignment given in Chapter 6. The supplements include a complete listing of subspaces, also for this binary construction.

80

Chapter 11 Man pages

81

CHAPTER 11. MAN PAGES

82

83

84

85

86

87

88

89

90

91

92

Part III The Appendices

93

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 8).

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

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

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

• ℘, ℓ, 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 9).

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

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

• G – a generator matrix for C.

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

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

95 APPENDIX A. INDEX OF NOTATIONS

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

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

• λ, λ_{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.

96

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 of dimension 3. Journal of Statistical Planning and Inference, 1998.

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

[CK99] Wende Chen and Torleiv Kløve. Weight hierarchies of extremal non-chain binary codes of dimension 4. IEEE Trans. Inform. Theory, January 1999.

97

[Cla91] W. E. Clark. Blocking sets in finite projective spaces and uneven binary-codes. Discrete Mathematics, 94(1):65–68, 1991.

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

[Hei97] U. Heim. Proper blocking sets in projective spaces. Discrete Mathematics, 174(1-3):167–176, 1997.

[Hir84] J. W. P. Hirschfeld. Linear codes and algebraic curves. Research notes in mathematics, 114:35–53, 1984.

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

[HKYL95] Tor Helleseth, Torleiv Kløve, Øyvind Ytrehus, and Vladimir I. Levenshtein. Bounds on the minimum support weights. IEEE Trans. Inform. Theory, 41(2):432–440, March 1995.

[HS91] J. W. P. Hirschfeld and T. Szönyi. Construction of large arcs and blocking sets in finite planes. European Journal of Combinatorics, 12:499–511, 1991.

[Klø92] Torleiv Kløve. Support weight distribution of linear codes. Discrete Mathematics, 106/107:311–316, 1992.

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

98

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

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

99