REPORTS

IN INFORMATICS

ISSN 0333-3590

Duality and Weights of Linear Codes and Projective Multisets Hans Georg Schaathun

REPORT NO 211 May 2001

Department of Informatics UNIVERSITY OF BERGEN

Bergen, Norway

This report has URL

http://www.ii.uib.no/publikasjoner/texrap/ps/2001-211.ps

Reports in Informatics from Department of Informatics, University of Bergen,

Norway, is available at http://www.ii.uib.no/publikasjoner/texrap/.

Requests for paper copies of this report can be sent to:

Department of Informatics, University of Bergen, Høyteknologisenteret, P.O. Box 7800, N-5020 Bergen, Norway

Duality and Weights of Linear Codes and Projective Multisets

Hans Georg Schaathun

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

Abstract

A projective multiset is a collection of projective points, which are not necessarily distinct. A linear code can be represented as a projective multiset, by taking the columns of a generator matrix as projective points. Projective multisets have proved very powerful in the study of generalised Hamming weights.

In this paper we study relations between a code and its dual using the projective multisets, and we attack three different problems: the sub-chain conditions used by Chen and Kløve [CK97a, CK96, CK99b], the greedy weights from [CEZ99, CK01, CK99a], and the support weight distributions, all of which are studied with respect to duality relations.

Keywords

linear codes, projective multiset, weight hierarchy, greedy weights, dual code

10th May 2001 10th May 2001 10th May 2001

Dualitet og vekter for lineære kodar og projektive multimengder

Samandrag

Ei projektiv multimengt er ei samling av projektive punkt som ikkje treng vera ulike. Me kan representera ein kvar lineær kode som ei projektiv multimeng ved å taka søylene frå ein generatormatrise for koden. Projektive multimengder har vist seg å vera særs nyttige for å studera vekthierarkiet åt koden.

I denne rapporten vil me sjå på samanhengen mellom ein kode og den dual koden, med hjelp av projektive multimengder. Me skal sjå på tre ulike spørsmål: delkjedeføresetnadene som Chen og Kløve har nytta [CK97a, CK96, CK99b], på grådigvektene frå [CEZ99, CK01, CK99a] og på støttevektfordelingane. Heile tida er det dualitetssamanhengane me konsentrer oss om.

Stikkord

lineære kodar, projektive multimengder, vekthierarki, grådigvekter, dual kode

Chapter 1

Introduction

1.1 Background

1.1.1 Generalised Hamming Weights

A linear code is a normed space and the weights (or norms) of codewords are crucial for the code’s performance. One of the most important parameters of a code is the minimum distance or minimum weight of a codeword.

The concept of weights can be generalised to subcodes or even arbitrary subsets of the code. (This is often called support weights or support sizes.) One of the key papers is [Wei91], where Wei defined the rth generalised Hamming weight to be the least weight of a r-dimensional subcode. After Wei’s work, we have seen many attempts to determine the generalised Hamming weights of different classes of codes.

Weights are alpha and omega for codes. Yet we know very little about the weight structure of most useful codes. The generalised Hamming weights give some information, and several practical applications are known. Still they do not fully answer our questions.

One practical application of the generalised Hamming weights is to determine the trellis complexity of the code. Fujiwara et al. [FKLT93] first found this relation. Forney [For94b] discussed the relation in more detail and introduced the ordered and the inverse ordered dimension/length profiles to determine the trellis complexity. It was evident that the generalised Hamming weights could only give lower bounds on this complexity in the general case.

Several other parameters describing weights of subcodes have been introduced, and they can perhabs contribute to understanding the structure of linear codes. The support weight distribution appeared as early as 1977 in [HKM77]. The chain condition from [WY93] and the double chain condition from [For94a] are important for some applications. Chen and Kløve have introduced certain sub-chain conditions, which they use to classify codes in a series of papers, e.g. [CK97a, CK96, CK99b]. Cohen, Encheva, and Zemor

3

CHAPTER 1. INTRODUCTION

[CEZ99] have introduced a new set of parameters, which we will call CEZ weights. Inspired by these parameters, Chen and Kløve [CK01, CK99a] introduced the greedy weights.

It is well known that a code and its dual are closely related. Wei [Wei91] proved one relation between the generalised Hamming weights of a code and its dual. Kløve [Klø92] has generalised the MacWilliams identities to give a relation for the support weight distributions.

1.1.2 Projective Multisets

We consider a linear [n, k] code C. We usually define a linear code by giving the generator matrix G. The rows of G make a basis for C, and as such they are much studied. Many works consider the columns instead. This gives rise to the projective multisets [DS98]. The weight hierarchy is easily recognised in this representation [HKY92, TV95]. Other terms for projective multisets include projective systems [TV95] and value assignments [CK97a].

The great advantage of projective multisets is that they do not depend on the coordinate system. Codes, on the other hand, depends heavily on the coordinate system, because the coordinates determine the weights. Therefore the projective multiset approach has proved very useful in the study of generalised Hamming weights. Problems which appear as hard in terms of linear codes may be easy in terms of projective multisets, e.g. determining the weight hierarchy of product codes [Sch00b].

There are at least two ways to develop the correspondence between codes and multisets. Most coding theorists will probably just take the columns of some generator matrix (e.g. [HKY92, CK97a]). Some mathematicians (e.g. [DS98, TV95]) develop the projective multisets abstractly. They take the elements to be the coordinate forms on C

(c_{1}, c_{2}, …, c_{n}) ↦ c_{i}, 1 ≤ i ≤ n,

and get a multiset on the dual space of C (this is not the dual code). Hence their argument does not depend on the (non-unique) generator matrix of C.

We will need the abstract approach for our results, but we will try to carefully explain the connections between the two approaches, in the hope to reach more readers.

No one has so far been able to find any close relation between the two projective multisets corresponding to a code and its dual. We will not find any either. However we will find important duality results by using a relation between the dual code C^{⊥} and the projective multiset corresponding to C.

4

Preliminaries

2.1 Vectors, Codes, and Multisets

A multiset is a collection of elements, which are not necessarily distinct. More formally, we define a multiset γ on a set S as a map

γ : S → {0, 1, 2, …}.

The number γ(s) is the number of occurences of s in the collection γ. The map γ is always extended to the power set of S,

γ(S′) = ∑_{s∈S′} γ(s), ∀S′ ⊆ S.

The number γ(s), where s ∈ S or s ⊆ S, is called the value of s. The size of γ is the value γ(S).

We will be concerned with multisets of vectors and multisets of projective points (projective multisets). We will always keep the informal view of γ as a collection in mind.

We consider a fixed finite field 𝔽 with q elements. A message word is a k-tuple over 𝔽, while a codeword is an n-tuple over 𝔽. Let 𝕄 be a vector space of dimension k (the message space), and 𝕍 a vector space of dimension n (the channel space). The generator matrix G gives a linear, injective transformation G : 𝕄 → 𝕍, and the code C is simply the image under G.

As vector spaces, 𝕄 and C are clearly isomorphic. For every message word m, there is a unique codeword c = mG.

A codeword (c_{1}, c_{2}, …, c_{n}) = mG is given by the value c_{i} in each coordinate position i. If we know m, we obtain this value as the inner product of m and the ith column g_{i} of G, i.e.

c_{i} = g_{i} · m = ∑_{j=1}^{k} m_{j}g_{i,j},  (2.1)

5

CHAPTER 2. PRELIMINARIES

where

g_{i} = (g_{i,1}, g_{i,2}, …, g_{i,k}),
m = (m_{1}, m_{2}, …, m_{k}).

The columns g_{i} are elements of 𝕄. These vectors are not necessarily distinct, so they make a multiset

γ_{C} : 𝕄 → {0, 1, 2, …}.

If we reorder the columns of G, we get an equivalent code. Hence γ_{C} defines C up to equivalence. If we replace a column with a proportional vector, we also get an equivalent code. Therefore many papers consider γ_{C} as a multiset on the projective space ℙ(𝕄), and a projective multiset will also define the code up to equivalence.

Example 2.1 Let C be the [7, 4] Hamming code. The message space 𝕄 has dimension 4, while the channel space 𝕍 has dimension 7. A generator matrix is

G = [\begin{matrix}1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{matrix}] .

The corresponding vector multiset γ_{C} contains the vectors

(1000), (0100), (0010), (0001), (1101), (1011), (0111).

The first symbol of a codeword is determined by the first vector, (1000). For the message (0110), the first encoded symbol is c_{1} = (0110) · (1000) = 0. In fact, the corresponding codeword is c = (0110)G = (0110110).

We say that two multisets γ and γ′ on 𝕄 are equivalent if γ′ = γ ∘ ϕ for some automorphism ϕ on 𝕄. Such an automorphism is given by ϕ : g ↦ gA where A is a square matrix of full rank. Replacing all the g_{i} by g_{i}A in (2.1) is equivalent to replacing m by Am. In other words, equivalent multisets give different encoding, but they give the same code. This is an important observation, because it implies that the coordinate system on 𝕄 is not essential.

Now we seek a way to represent the elements of γ_{C} as vectors of 𝕍. Let b_{i} be the ith coordinate vector of 𝕍, that is the vector with 1 in

position i and 0 in all other positions. The set of all coordinate vectors is denoted by

B := {b_{1}, b_{2}, …, b_{n}}.
6

\underline{2.2. WEIGHTS}

If we know the codeword c corresponding to m, the ith coordinate position c_{i} is given as the inner product of b_{i} and c.

c_{i} = b_{i} · c = ∑_{j=1}^{n} c_{j}b_{i,j},  (2.2)

where

b_{i} = (b_{i,1}, b_{i,2}, …, b_{i,k}),
c = (c_{1}, c_{2}, …, c_{k}).

We note that b_{i} takes the role of g_{i}, and c takes the role of m from (2.1).

However, b_{i} is not the only vector of 𝕍 with this property. In fact, for any vector c′ ∈ C^{⊥}, we have (b_{i} + c′) · c = c_{i}. Therefore, we can consider the vector b_{i} as the coset b_{i} + C^{⊥} of C^{⊥}. The set of such cosets is usually denoted 𝕍/C^{⊥}, and it is a vector space of dimension

dim 𝕍/C^{⊥} = dim 𝕍 − dim C^{⊥} = n − (n − k) = k = dim 𝕄.

Hence 𝕄 ≅ 𝕍/C^{⊥} as vector spaces. Obviously b_{i} + C^{⊥} corresponds to g_{i}.

Example 2.1 (cont.) We still consider the [7, 4] Hamming code C and the codeword c = (0110110). The first coordinate is determined as

\begin{aligned}c_{1} & = (0110110) · [(1000000) + C^{⊥}] \\ & = (0110110) · (1000000) + (0110110) · C^{⊥} = 0 + 0 = 0. \end{aligned}

We let μ : 𝕍 → 𝕍/C^{⊥} be the natural endomorphism, i.e. μ : g ↦ g + C^{⊥}. This map is not injective, so if S ⊆ 𝕍, it is reasonable to view the image μ(S) as a multiset. Our analysis gives this lemma.

Lemma 2.1 A code C ⊆ 𝕍 is given by the vector multiset γ_{C} := μ(B) on 𝕍/C^{⊥} ≅ 𝕄.

Given a collection {s_{1}, s_{2}, …, s_{m}} of vectors and/or subsets of a vector space 𝕍, we write ⟨s_{1}, s_{2}, …, s_{m}⟩ for its span. In other words ⟨s_{1}, s_{2}, …, s_{m}⟩ is the intersection of all subspaces containing s_{1}, s_{2}, …, s_{m}.

Also note that we write A ⊂ B only if A is a proper subset of B. We write A ⊆ B if A is an arbitrary subset of B, possibly equal to B.

2.2 Weights

We define the support χ(c) of c ∈ C to be the set of coordinate positions not equal to zero, that is

χ(c) := {i | c_{i} ≠ 0}, where c = (c_{1}, c_{2}, …, c_{n}).
7

The support of a subset S ⊆ C is

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

The weight (or support size) w(S) is the cardinality of χ(S). The ith minimum support weight d_{i}(C) is the smallest weight of an i-dimensional subcode D_{i} ⊆ C. The subcode D_{i} will be called a minimum i-subcode. The weight hierarchy of C is (d_{1}(C), d_{2}(C), …, d_{k}(C)).

Lemma 2.2 (Helleseth-Kløve-Ytrehus 1992) There is a one-to-one correspondence between subcodes D ⊆ C of dimension r and subspaces U ⊆ 𝕄 of codimension r, such that γ_{C}(U) = n − w(D).

Proof: Since C and 𝕄 are isomorphic, a subcode D ⊆ C corresponds to a subspace M ⊆ 𝕄. From (2.1) we can see that i ∈ χ(D) if and only if g_{i} is not orthogonal on M. Hence we get that

γ_{C}(M^{⊥}) = n − w(D),  (2.3)

where M^{⊥} ⊆ 𝕄 is the subspace of vectors orthogonal on M. If dim D = r, then dim M^{⊥} = k − r. The lemma follows with U = M^{⊥}. □

Consider a chain of subcodes

{0} = D_{0} ⊂ D_{1} ⊂ D_{2} ⊂ … ⊂ D_{k} = C.

The proof of Lemma 2.2 implies that the corresponding subspaces of 𝕄 form a chain

𝕄 = U_{0} ⊃ U_{1} ⊃ U_{2} ⊃ … ⊃ U_{k} = {0},

where U_{i} corresponds to D_{i}.

We define d_{k−r}(γ_{C}) such that n − d_{k−r}(γ_{C}) is the largest value of an r-space Π_{r} ⊆ PG(k − 1, q). From Lemma 2.2 we get this corollary.

Corollary 2.1 If C is a linear code and γ_{C} is the corresponding multiset, then d_{i}(γ_{C}) = d_{i}(C).

Definition 2.1 (Chain Condition) We say that a code is chained if there is a chain 0 = D_{0} ⊆ D_{1} ⊆ … ⊆ D_{k} = C, where each D_{i} is a minimum i-subcode of C.

In terms of vector systems, the chain of subcodes corresponds to a chain of maximum value subspaces (by the proof of Lemma 2.2).

The difference sequence (δ_{0}, δ_{1}, …, δ_{k−1}) is defined by δ_{i} = d_{k−i}−d_{k−1−i}, and is occasionally more convenient than the weight hierarchy. The maximum value of an r-space is δ_{0} + δ_{1} + … + δ_{r−1}.

8

2.3. SUBMULTISETS

2.3 Submultisets

Viewing the multiset γ as a collection, we probably have an intuitive notion of a submultiset. The formal definition of a submultiset is this.

Definition 2.2 (Submultiset) Let γ be a multiset on S. A submultiset γ′ ⊆ γ is a map

γ′ : S → {0, 1, 2, …},

where γ′(s) ≤ γ(s) for all s ∈ S.

The most interesting kind of submultisets for our purposes are crosssections.

Definition 2.3 (Cross-sections) Let γ be a multiset on a vector space 𝕍, and U ⊆ 𝕍 a subspace. The cross-section γ|_{U} is the submultiset given by

γ|_{U}(x) := \begin{cases}γ(x), & if x ∈ U, \\ 0, & otherwise. \end{cases}

If U has dimension r in the definition, then we call γ|_{U} an r-dimensional cross-section. In some cases it is easier to deal with cross-sections and their sizes, than with subspaces and their values. In Lemma 2.2, we can consider the cross-section γ_{C}|_{U} rather than the subspace U. In particular, we have that n − d_{k−r}(γ_{C}) is the size of the largest r-dimensional cross-section of γ_{C}.

2.4 Duality

Consider a code C ⊆ 𝕍 and its orthogonal code C^{⊥} ⊆ 𝕍. Write (d_{1}, …, d_{k}) for the weight hierarchy of C, and (d_{1}^{⊥}, …, d_{n−k}^{⊥}) for the weight hierarchy of C^{⊥}. Let B be the set of coordinate vectors for 𝕍, and let μ be the natural endomorphism,

μ : 𝕍 → 𝕍/C^{⊥},
μ : v ↦ v + C^{⊥}.

According to Lemma 2.1, the vector multiset corresponding to C, is γ_{C} := μ(B).

Let B ⊆ B. Then μ(B) is a submultiset of γ_{C}. Every submultiset of γ_{C} is obtained this way. Obviously dim⟨B⟩ = #B. Let D := ⟨B⟩ ∩ C^{⊥} be the largest subcode of C^{⊥} contained in ⟨B⟩. Then D is the kernel of μ|_{⟨B⟩}, the restriction of μ to ⟨B⟩. Hence

dim⟨μ(B)⟩ = dim⟨B⟩ − dim D.  (2.4)

9

Clearly #B ≥ w(D).

With regard to the problem of support weights, we are not interested in arbitrary submultisets of γ_{C}. We are only interested in cross-sections. Therefore, we ask when μ(B) is a cross-section of μ(B). This is of course the case if and only if μ(B) equals the cross-section μ(B)|_{⟨μ(B)⟩}.

Let U ⊆ 𝕍/C^{⊥} be a subspace. We have μ(B)|_{U} = μ(B), where B = {b ∈ B | μ(b) ∈ U}. Hence we have μ(B) = μ(B)|_{⟨μ(B)⟩} if and only if there exists no point b ∈ B\B such that μ(b) ∈ ⟨μ(B)⟩.

It follows from (2.4) that a large cross-section μ(B) of a given dimension, must be such that ⟨B⟩ contains a large subcode of C^{⊥} of sufficiently small weight.

Define for any subcode D ⊆ C^{⊥},

β(D) := {b_{x} | x ∈ χ(D)} ⊆ B.

Obviously β(D) is the smallest subset of B such that D is contained in its span. It follows from the above argument that if D is a minimum subcode and μ(β(D)) is a cross-section, then μ(β(D)) is a maximum cross-section for C. Thus we are lead to the following two lemmas.

Lemma 2.3 If n − d_{r} = d_{i}^{⊥}, B ⊆ B, and #B = n − d_{r}, then μ(B) is a cross-section of maximum size and codimension r if and only B = β(D_{i}) for some minimum i-subcode D_{i} ⊆ C^{⊥}.

Lemma 2.4 Let r be an arbitrary number, 0 < r ≤ n − k. Let i be such that d_{i}^{⊥} ≤ n − d_{r} < d_{i+1}^{⊥}, and let D_{i} ⊆ C^{⊥} be a minimum i-subcode. Then μ(⟨B⟩) is a maximum r-subspace for any B ⊆ B such that D_{i} ⊆ ⟨B⟩ and #B = n − d_{r}.

As an example of our technique, we include two old results from [Wei91, WY93], with new proofs based on the argument above.

Proposition 2.1 (Wei 1991) The weight sets

{d_{1}, d_{2}, …, d_{k}} and {n + 1 − d_{1}^{⊥}, n + 1 − d_{2}^{⊥}, …, n + 1 − d_{n−k}^{⊥}}

are disjoint, and their union is {1, 2, …, n}.

Proof: Suppose for a contradiction that d_{i} = n−s and d_{j}^{⊥} = s+1 for some i, j, and s. Let D_{j} ⊆ C^{⊥} be a minimum j-subcode. Let B_{i} ⊆ B such that μ(B_{i}) is a maximum cross-section of codimension i. We have #β(D_{j}) = #B_{i} + 1 and thus dim⟨B_{i}⟩ ∩ C^{⊥} < j. Hence dim μ(B_{i}) ≥ dim μ(β(D_{j})). Thus μ(B_{i}) cannot be maximum cross-section, contrary to assumption. □

10

\underline{2.4. DUALITY}

Proposition 2.2 (Wei and Yang 1993) If a C is a chained code, then so is C^{⊥}, and vice versa.

Proof: Suppose C^{⊥} is a chained code. We prove that then C is a chained code. The converse follows by duality.

Let

{0} = D_{0} ⊂ D_{1} ⊂ … ⊂ D_{k} = C^{⊥}

be a chain of subcodes of minimum weight. Choose a coordinate ordering, such that

χ(D_{i}) = {1, 2, …, d_{i}^{⊥}}, ∀i.

For each r = 1, 2, …, n, let B_{r} ⊆ B be the set of the r first coordinate vectors. By our argument, μ(B_{r}) is a cross-section of maximum size except if d_{i}^{⊥} = r + 1 for some i; in which case there is no cross-section of maximum size and r elements. Obviously μ(B_{r}) ⊆ μ(B_{r+1}) for all r. □

11

12

Subchains

We define a number of sub-chain conditions, which are implications of the chain condition. Let M_{i}(C) be the set of maximum (i + 1)-spaces of γ_{C}. (The index i is the projective dimension. This notation has previously been used with projective multisets.) For any i and j such that 0 ≤ i < j ≤ k − 2, we have the condition:

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

or equivalently

(Ck − 1 − i.k − 1 − j) : ∃D_{j} ⊂ D_{i} ⊂ C, s.t. dim D_{i} = i, w(D_{i}) = d_{i},
dim D_{j} = j, w(D_{j}) = d_{j}.

The negations of these conditions, (Ni.j) := ¬(Ci.j), will be called the non-chain conditions. The chain condition will be denoted by (C0). The codes which satisfies all the non-chain conditions are called extremal nonchain codes.

The order of a condition (Ci.j) or (Ni.j) is the number j − i. For a code of dimension k, there are k − 2 first-order sub-chain conditions defined. Of order t, k−1−t conditions are defined. All together, there are (k−1)(k−2)/2 sub-chain conditions.

Codes may be classified according to which sub-chain conditions they satisfy [CK96, CK97a]. There are 2^{(k−1)(k−2)/2} different classes of codes of dimension k, not counting the class of chained codes.

For k = 4, possible weight hierarchies for each class have been studied by Chen and Kløve. In higher dimensions the number of classes grows too large. The only classes which have been investigated in the general case are the extreme cases, namely the chained codes [EK94, CK98] and the extremal non-chain codes [CK97a, CK99b, Sch00a].

13

CHAPTER 3. SUBCHAINS

3.1 Duality relations

We have seen that if C is chained, then so is C^{⊥}. We will later see that if C satisfies all the sub-chain conditions, but not the chain condition itself, then so does C^{⊥}. We call such codes Case B codes or just B-codes [CK97b]. Since the number of classes depends on the dimension, and since a code and its dual have different dimension in general, it is hard to see further duality results in the same genre. Even though we will discover more duality results in the sequel, we will not be able, in general, to determine the class of C^{⊥}, solely from knowing the class of C.

Lemma 3.1 If d_{s−1} = d_{s} − 1, then (Ck − 1 − s.k − s) holds. In fact, for any minimum s-subcode D, and any subcode D′ ⊂ D of weight w(D′) ≤ d_{s} − 1, we can find a minimum (s − 1)-subcode D′′, such that D′ ⊆ D′′ ⊂ D.

Proof: Let D and D′ be as described. Arbitrarily choose i ∈ χ(D)\χ(D′), and define D′′ := {x ∈ D | x_{i} = 0}. Clearly dim D′′ = s − 1, D′ ⊆ D′′ ⊂ D, and w(D′′) ≤ d_{s} − 1, which is also the least possible weight. Hence D′′ is a minimum (s − 1)-subcode. □

Corollary 3.1 If d_{s−i} = d_{s} − i for some s and i > 1, then (Ck − 1 − s.k − 1 + i − s) holds.

Lemma 3.2 If d_{k−1−r} = d_{k} − 1 − r where 0 ≤ r ≤ k − 3, then (Cr.s) holds for all s.

Proof: First observe that d_{k−1−r′} = d_{k} − 1 − r′ for all r′ ≤ r. Let D_{k−1−s} ⊆ C be a minimum (k − 1 − s)-subcode. By Lemma 3.1, we can form a chain

D_{k−1−s} ⊂ D_{k−1−r} ⊂ D_{k−r} ⊂ … ⊂ D_{k} = C

of minimum subcodes, proving the lemma. □

Lemma 3.3 Suppose C^{⊥} satisfies (Nn−k −1−j.n−k −1−i) where i < j, d_{i+1}^{⊥} > d_{i}^{⊥} +1, and d_{j+1}^{⊥} > d_{j}^{⊥} +1. Then C satisfies (Nk −1−r.k −1−s) where d_{i}^{⊥} = n−d_{r} and d_{j}^{⊥} = n − d_{s}.

By biduality, the lemma is equivalent to the following remark for which the proof will look a little cleaner.

Remark 3.1 Suppose C satisfies (Nk − 1 − j.k − 1 − i) where i < j, d_{i+1} > d_{i} + 1, and d_{j+1} > d_{j} + 1. Then C^{⊥} satisfies (Nn − k − 1 − r.n − k − 1 − s) where d_{i} = n − d_{r}^{⊥} and d_{j} = n − d_{s}^{⊥}.

14

3.1. DUALITY RELATIONS

Proof: Since the lemma is follows from the remark, we will prove the remark. Because d_{i+1} > d_{i} + 1 and d_{j+1} > d_{j} + 1, there are r and s such that d_{i} = n − d_{r}^{⊥} and d_{j} = n − d_{s}^{⊥}.

Suppose for a contradiction that C^{⊥} satisfies (Cn−k−1−r.n−k−1−s). Let D_{s} ⊂ D_{r} ⊆ C^{⊥} be minimum s- and r-subcodes. By Lemma 2.3, μ(β(D_{r})) and μ(β(D_{s})) are maximum cross-sections of codimensions i and j respectively, but μ(β(D_{r})) ⊂ μ(β(D_{s})); thus the lemma follows by contradiction. □

Lemma 3.4 If d_{i}^{⊥} = n − d_{r}, then r = k + i − d_{i}^{⊥}.

Proof: By Proposition 2.1, we have that

{d_{1}, …, d_{r}, n + 1 − d_{n−k}^{⊥}, …, n + 1 − d_{i}^{⊥}} = {1, 2, …, n + 1 − d_{i}^{⊥}}.

Clearly r+n−k−i+1 is the cardinality on the left hand side, while n+1−d_{i}^{⊥} is the cardinality on the right hand side. Hence r +n−k −i+1 = n+1−d_{i}^{⊥}, and the lemma follows. □

Proposition 3.1 If d_{i+1}^{⊥} > d_{i}^{⊥}+1 and d_{j+1}^{⊥} > d_{j}^{⊥}+1, then C^{⊥} satisfies (Cn−k−1−j.n−k−1−i) if and only if C satisfies (Cd_{i}^{⊥} − i − 1.d_{j}^{⊥} − j − 1).

Proof: The if-part follows directly from Lemmas 3.3 and 3.4. The onlyif-part follows by duality. □

Lemma 3.5 Suppose C satisfies (Nk −1−r.k −1−s) for some r and s. Let r′′ ≥ r be the least integer such that d_{r′′+1} > d_{r′′} + 1, and let s′′ ≥ s be the least integer such that d_{s′′+1} > d_{s′′} + 1. Then C also satisfies (Nk − 1 − r′.k − 1 − s′) for all s′ and r′ such that r ≤ r′ ≤ r′′ and s ≤ s′ ≤ s′′.

Note that by Lemma 3.2, there must exist such an r′′ < k, and by Corollary 3.1 there exists such an s′′ < r′. Proof: First consider the case where d_{s+1} = d_{s} + 1. Suppose for a contradiction that (Ck − 1 − r.k − 2 − s) holds. Then there is a minimum r-subcode D and a minimum (s + 1)-subcode D′ ⊂ D. By Lemma 3.1, there is a minimum s-subcode D′′ ⊂ D′ ⊂ D. Hence (Nk −1−r.k −2−s) holds by contradiction. By iterating the argument, we find that (Nk −1−r.k −1−s′) holds for s′ = s, s + 1, …, s′′.

Then consider the case where d_{r+1} = d_{r} + 1. Suppose for a contradiction that (Ck − 2 − r.k − 1 − s) holds. Then there is a minimum s-subcode D and a minimum (r + 1)-subcode D′ ⊃ D. By Lemma 3.1, there is a minimum r-subcode D′′ such that D ⊂ D′′ ⊂ D′, contradicting (Nk − 1 − r.k − 1 − s). Hence (Nk − 2 − r.k − 1 − s) holds. By iterating the argument we prove (Nk − 1 − r′.k − 1 − s) for r′ = r, r + 1, …, r′′.

15

i  [0,22] 23 [24,35] 36 [37,43] 44 [45,47] 48 [49,50] 51
d_{k−1−i} [56,34] 32 [31,20] 18 [17,11] 9 [8,6] 4 [3,2] 0

j

[0, 22] (Y^{2})  -  -  -  -  -  -  -  -  -
23  Y^{3}  -  -  -  -  -  -  -  -  -
[24, 35]  Y^{3}  Y^{2} (Y^{2})  -  -  -  -  -  -  -
36  Y^{3}  N^{1}  Y^{5}  -  -  -  -  -  -  -
[37, 43]  Y^{3}  Y^{5}  Y^{2} (Y^{2})  -  -  -  -  -
44  Y^{3}  N^{1}  N^{1}  -  -  -  -  -
[45, 47]  Y^{3}  Y^{4}  Y^{4}  Y^{2} (Y^{2})  -  -  -
48  Y^{3}  N^{1}  N^{1}  N^{1}  -  -  -
[49, 50]  Y^{3}  Y^{4}  Y^{4}  Y^{4}  Y^{4}  Y^{2} (Y^{2}) -
51  -  -  -  -  -  -  -  -  -  -

Table 3.1: The sub-chain conditions satisfied for C^{⊥}. The entry is Y if (Ci.j) is satisfied. Entry - means that he sub-chain condition is not defined, while an entry in parenthesis means that the sub-chain condition is undefined for some values of i and j.

By combining the two first results, we get that C satisfies (Nk−1−r′.k− 1 − s′). □

Corollary 3.2 If C satisfies (Ck − 1 − r.k − 1 − s) for some r and s. Let r′′ ≤ r be the greatest integer such that d_{r′′−1} < d_{r′′} − 1, and let s′′ ≤ s be the greatest integer such that d_{s′′−1} < d_{s′′} −1. Then C also satisfies (Ck−1−r′.k−1−s′) for all r′ and s′ such that r′′ ≤ r′ ≤ r and s′′ ≤ s′ ≤ s.

Theorem 3.1 If C satisfies all the sub-chain conditions, then so does C^{⊥}.

Proof: Suppose for a contradiction that C satisfies all sub-chain conditions, while C^{⊥} satisfies (Nn − k − 1 − j.n − k − 1 − i) for some i and j. By Lemma 3.5, C^{⊥} satisfies (Nn − k − 1 − j′.n − k − 1 − i′), where d_{i′+1}^{⊥} > d_{i′}^{⊥} + 1 and d_{j′+1}^{⊥} > d_{j′}^{⊥} + 1. By Lemma 3.3, C satisfies (Nk − 1 − r.k − 1 − s) where d_{i′}^{⊥} = n − d_{r} and d_{j′}^{⊥} = n − d_{s}. The lemma follows by contradiction. □

Corollary 3.3 If C is a B-code, then so is C^{⊥}.

3.2 A duality example

In [Sch00a] we learnt that an optimal, binary, extremal non-chain code C has difference sequence (4, 5, 9, 14, 25). This gives a weight hierarchy of (25, 39, 48, 53, 57). The orthogonal code C^{⊥} has weight hierarchy

(2, 3, 4, 6, 7, …, 9, 11, 12, …, 18, 20, 21, …, 32, 34, 35, …, 57),
16

3.2. A DUALITY EXAMPLE

by Proposition 2.1, and its dimension is 52. We will determine the non-chain conditions satisfied by C^{⊥}, cf. Table 3.1.

We observe that d_{i+1}^{⊥} > d_{i}^{⊥} + 1 for

i ∈ {i_{0} = 0, i_{1} = 3, i_{2} = 7, i_{3} = 15, i_{4} = 28}.

Note that i_{j+1} = i_{j} + δ_{j} − 1. We also see that d_{0}^{⊥} = 0, d_{3}^{⊥} = 4, d_{7}^{⊥} = 9, d_{15}^{⊥} = 18, and d_{28}^{⊥} = 32.

By Proposition 3.1 we get,

C^{⊥} satisfies (N51 − i_{2}.51 − i_{1}) = (N44.48)
⟸ C satisfies (N4 − 3 − 1.9 − 7 − 1) = (N0.1).
C^{⊥} satisfies (N51 − i_{3}.51 − i_{1}) = (N36.48)
⟸ C satisfies (N4 − 3 − 1.18 − 15 − 1) = (N0.2).
C^{⊥} satisfies (N51 − i_{4}.51 − i_{1}) = (N23.48)
⟸ C satisfies (N4 − 3 − 1.32 − 28 − 1) = (N0.3).

And similarily, C^{⊥} satisfies (N36.44), (N23.44), and (N23.36). This gives us the entries in the table, marked with superscript 1.

Now consider an arbitrary pair (r, s) where 0 ≤ s < r < n − k − 1 = 51 and ask, does C^{⊥} satisfy (C51 − r.51 − s)?

Define i_{5} := n − k = 52 for convenience. If i_{j} ≤ s < r < i_{j+1}, for some j = 0, 1, 2, 3, 4, then d_{s}−d_{r} = s−r, so (C51−r.51−s) holds by Corollary 3.1. In the table, the Y-s marked with a superscript ‘2’ follows. From Lemma 3.2, we get the sub-chain conditions with Y^{3} in the table.

To find further entries, we need more knowledge about C. It was found in [Sch00a, Cor. 7] that any maximum cross-section of dimension 2 has difference sequence (δ_{0} − 1, δ_{1}, δ_{2} + 1), and a maximum cross-section of dimension 1 has difference sequence (δ_{0} − 1, δ_{1} + 1). Hence if D_{2} and D_{3} are minimum 2- and 3-subcodes of C, there are subcodes

E_{3} ⊃ D_{2}, dim E_{3} = 3, w(E_{3}) = d_{3} + 1,
E_{4} ⊃ D_{2}, dim E_{4} = 4, w(E_{4}) = d_{4} + 1,
E′_{4} ⊃ D_{3}, dim E′_{4} = 4, w(E′_{4}) = d_{4} + 1.

Define β^{⊥} analogously to β:

β(D) := {b_{x} | x ∈ χ(D)} ⊆ B.

The cross-sections μ(β^{⊥}(D_{2})) ⊂ μ(β^{⊥}(E_{3})) gives us (C36.45). Similarily, we get (C36.49) and (C44.49). From Corollary 3.2, we get all the Y-s marked with superscript ‘4’.

Finally consider [Sch00a, Thm. 10]. A 2-space Π_{2} of maximum value must be contained in a 3-space Π_{3} and value δ_{0} + δ_{1} + δ_{2} + δ_{3} − 1. Hence

17

a minimum 2-subcode D_{2} ⊂ C contains a 1-subcode of weight d_{1} + 1, and for C^{⊥}, we get (C24.36). From Corollary 3.2, we get the Y-s marked with a superscript ‘5’.

This is as far as we get with the results we have found. Since there are several non-equivalent optimal extremal non-chain codes, the remaining sub-chain conditions may depend on the actual choice of C.

3.3 Bounds on the Difference Sequences

Proposition 3.2 (Chen and Kløve [CK96]) Let (δ_{0}, δ_{1}, δ_{2}, δ_{3}) be a Case B difference sequence. Then

(C0.1) ⇒ δ_{3} ≤ qδ_{2} − (q + 1)
(C0.2) ⇒ δ_{2} ≤ qδ_{1} − (q + 1)
(C1.2) ⇒ δ_{1} ≤ qδ_{0} − (q + 1).

Lemma 3.6 If (δ_{0}, …, δ_{k−1}) is a Case B difference sequence, then δ_{i} ≤ qδ_{i−1} for all i.

Proof: An i-space Π_{i} of value δ_{0} + … + δ_{i}, contains an (i − 2)-space Π_{i−2} of value δ_{0} + … + δ_{i−2}, for 1 ≤ i ≤ k − 1. There are q + 1 (i − 1)-spaces containing Π_{i−2} in Π_{i}. Hence

γ(Π_{i}) ≤ (q + 1)δ_{i−1} + δ_{i−2} + δ_{i−3} + … + δ_{0},  (3.1)

and the lemma follows. □

We note that these bounds are considerably weaker than the bounds for k = 4 in the proposition. The reason is that for k = 4, γ(Π_{i−1}) < δ_{0} +…+δ_{i−1}, lest the chain condition is satisfied. This holds for k = 4 only. Moreover, if a code satisfies the bounds in Lemma 3.6 with equality for all i, then it is a simplex code and hence satisfies the chain condition.

Problem 3.1 Translate the bounds above to bounds for the dual code.

18

Greedy Weights

Cohen, Encheva, and Zemor [CEZ99] introduced a new set of parameters, which we will call CEZ weights (g_{1}, …, g_{k}). Chen and Kløve [CK99a, CK01] introduced a similar set of parameters, called the greedy weights, which we will denote (e_{1}, …, e_{k}). The second greedy weight coincides with the second CEZ weight, and it has been studied in detail. Only a little is known about the higher greedy weights.

The results of this chapter appears in a more compact form in [Sch01].

4.1 Definitions

Definition 4.1 (CEZ r-subcode) A CEZ r-subcode, r ≥ 1, is an r-dimensional subcode containing a minimum (r − 1)-subcode, such that no other such code has lower weight.

Definition 4.2 (CEZ weights) The rth CEZ weight, g_{r}, is the weight of a CEZ r-subcode.

Definition 4.3 (Greedy r-subcode) A (bottom-up) greedy 1-subcode is a minimum 1-subcode. A (bottom-up) greedy r-subcode, r ≥ 2, is any r-dimensional subcode containing a (bottomup) greedy (r − 1)-subcode, such that no other such code has lower weight.

Definition 4.4 (Greedy subspace) Given a vector multiset γ, a (bottom-up) greedy hyperplane is a hyperplane of maximum value. A (bottom-up) greedy space of codimension r, r ≥ 1, is a subspace of codimension r contained in a (bottom-up) greedy space of codimension r − 1, such that no other such subspace has higher value.

A greedy r-subcode corresponds to a greedy subspace of codimension r, and the r-th greedy weight may be defined from either, as follows.

19

CHAPTER 4. GREEDY WEIGHTS

Definition 4.5 (Greedy weights) The rth (bottom-up) greedy weight e_{r} is the weight of a (bottom-up) greedy r-subcode. For a vector multiset, n−e_{r} is the value of a (bottom-up) greedy space of codimension r.

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

We introduce a third set of parameters, the top-down greedy weights. It is in a sense the dual of the greedy weights, and we will see later on that top-down greedy weights can be computed from the greedy weights of the orthogonal code, and vice versa.

Definition 4.6 (Top-Down Greedy Subspace) A top-down greedy 0-space of a vector multiset is {0}. A top-down greedy r-space is an r-space containing a top-down greedy (r − 1)-subspace such that no other such subspace has higher value.

Definition 4.7 (Top-Down Greedy Weights) The r-th top-down greedy weight ẽ_{r} is n − γ_{C}(Π), where Π is a top-down greedy subspace of codimension r.

We will occasionally speak of (top-down) greedy cross-sections, which is just γ_{C}|_{U} for some (top-down) greedy space U.

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

Example 4.1 We take an example of a B-code from [CK96]. The projective multiset is presented in Figure 4.1. A chain of greedy subspaces is

∅ ⊂ ⟨A⟩ ⊂ ⟨A, L⟩ ⊂ ⟨A, B, C⟩ ⊂ PG(4, q),

and a chain of top-down greedy subspaces is

∅ ⊂ ⟨C⟩ ⊂ ⟨C, D⟩ ⊂ ⟨A, C, D⟩ ⊂ PG(4, q).

In the binary case, we get greedy weights (4, 6, 9, 12), and top-down greedy weights (3, 6, 10, 12). The weight hierarchy is (3, 6, 9, 12).

20

4.2. BASIC PROPERTIES

[figure: A; J; I; L; C; B; D; G; H; F]
γ(p) = for
0  p ∈ ⟨A, B, C⟩\{A, D}, p ∈ {F, H, I, J}
1  p ∈ ⟨B, F ⟩\{B, F, H}, p ∈ ⟨G, I⟩\{G, H, I}, p = D
3  p = C
2  otherwise

Figure 4.1: Case B, Construction 1 from [CK96].

4.2 Basic properties

Theorem 4.1 (Monotonicity) If (e_{1}, e_{2}, …, e_{k}) are greedy weights for some code C, then 0 = e_{0} < e_{1} < e_{2} < … < e_{k}. Similarily, if (ẽ_{1}, ẽ_{2}, …, ẽ_{k}) are top-down greedy weights for some code C, then 0 = ẽ_{0} < ẽ_{1} < ẽ_{2} < … < ẽ_{k}.

Proof: Let

{0} = Π_{0} ⊂ Π_{1} ⊂ … ⊂ Π_{k} = 𝕄,

be a chain of greedy subspaces. We are going to show that γ_{C}|_{Π_{i}} contains more points than γ_{C}|_{Π_{i−1}} for all i. It is sufficient to show that γ_{C}|_{Π_{i}} contains a set of points spanning Π_{i}.

Since γ_{C} is non-degenerate, it contains a set of points spanning Π_{k}. Suppose that γ_{C}|_{Π_{r}} contains a set of points spanning Π_{r}. Consider Π_{r−1}. Suppose dim⟨γ_{C}|_{Π_{r−1}}⟩ < r − 1. Obviously there is a point x ∈ γ_{C}|_{Π_{r}} − γ_{C}|_{Π_{r−1}}. Hence we can replace Π_{r−1} by ⟨γ_{C}|_{Π_{r−1}}, x⟩ and get a subspace Π′_{r−1} ⊂ Π_{r} with larger value. This contradicts the assumption that Π_{r−1} is a greedy subspace.

We can replace the Π_{i} with a chain of top-down greedy subspaces, and repeat the proof to prove the second statement of the lemma. □

Monotonicity also holds for the weight hierarchy by a similar argument [Wei91], but in general it does not hold for the CEZ weights.

21

Example 4.2 Consider the [16, 4; 5]_{2} code defined by the following generator matrix

G = [\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{matrix}] .

The weight hierarchy of the code is (5, 9, 11, 16), the greedy weights are (5, 11, 14, 16), and the top-down greedy weights are (6, 9, 11, 16).

We can see that the fourth row generates a minimum one-subcode of weight 5. The first three rows generates a chained code with weight hierarchy (6, 9, 11), and this is also a CEZ 3-subcode. A CEZ 2-subcode is generated by the fourth and first rows, and has weight 11. Hence g_{2} = g_{3} = 11.

In general the rth CEZ weight may be less than, equal to, or greater than the rth greedy weight. For a chained code e_{r} = g_{r}. For a B-code, d_{r} = g_{r} for all r, but e_{r} > g_{r} = d_{r} for some r. In the following example, g_{3} > e_{3}.

Example 4.3 A binary code with g_{3} > e_{3} is given by the generator matrix

G = [\begin{matrix}G_{1} & 0 \\ 0 & G_{2} \end{matrix}] ,

where

G_{1} = [\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}] ,

G_{2} = [\begin{matrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}] .

The code given by G_{1} satisfies the chain condition and has weight hierarchy (6, 12, 16), while G_{2} gives a chained code with (7, 11, 17) as a weight hierarchy.

The code given by G has weight hierarchy (6, 11, 16, 23, 27, 33). The greedy weights differs from the weight hierarchy only in e_{2} = 12, and the CEZ weights differs from the greedy weights only in g_{3} = 17 > e_{3} = d_{3} = 16.

4.3 Duality

By using the same approach as in Section 2.4, we will find duality results on the greedy weights. And we start by making a top-down greedy analogue of Lemma 3.1.

22

Lemma 4.1 Suppose ẽ_{i+1} > ẽ_{i} + 1 where 0 ≤ i ≤ k, and define s := n − ẽ_{i} + i − k. Then U is a top-down greedy cross-section of codimension i if and only if U = μ(β(D_{s})) for some greedy s-subcode D_{s} ⊆ C.

Proof: Let ī be the largest value of i ≤ k − 1 such that ẽ_{i+1} > ẽ_{i} + 1. Then δ_{j} = 1 for 0 ≤ j ≤ k − 1 − (ī + 1). It follows that any subset B_{j} of j ≤ k − 1 − ī elements, gives rise to a top-down greedy cross-section μ(B_{j}) of dimension j (and size j). The codimension of such a μ(B_{j}) is k − j ≥ ī + 1.

Hence μ(B_{k−ī}) is a top-down greedy cross-section of codimension ī, if and only if it is a maximum value cross-section of codimension ī. Hence, for i = ī, the lemma follows from Lemma 2.3.

Suppose ẽ_{m+1} > ẽ_{m} +1, and assume the lemma holds for all i, ī ≥ i > m. We will prove the lemma by induction. Define

j := max{j > m | ẽ_{j} − ẽ_{m+1} = j − (m + 1)}.

Clearly, ẽ_{j+1} − ẽ_{j} > 1.

Now consider a top-down greedy subspace μ(B) of codimension m, where B ⊆ B. Clearly there is B′ ⊂ B such that μ(B′) is a top-down greedy subspace of codimension j. By the induction hypothesis, B′ = β(D_{r}) for some greedy r-subcode D_{r} ⊆ C^{⊥} where r = n − k − ẽ_{j} + j. Also,

#B′ = w(D_{r}) = e_{r}^{⊥} = n − ẽ_{j}.

Note that we can make top-down greedy cross-sections of codimension x for m < x ≤ j by adding j − x random elements b_{y} to B′. This implies also that there cannot be a subcode D_{r+1} of dimension r + 1 such that D_{r} ⊂ D_{r+1} ⊆ C and w(D_{r+1}) ≤ w(D_{r}) + 1 + j − x. Hence

e_{r+1}^{⊥} ≥ n − ẽ_{j} + 1 + j − m.  (4.2)

Let B′′ = B_{k−(m+1)} ⊆ B be such that μ(B′′) is a top-down greedy crosssection of codimension m+1 with B′ ⊂ B′′ ⊂ B. Note that D_{r} = ⟨B′′⟩∩C^{⊥}.

Let

z := #B − #B′′ = (n − ẽ_{m}) − (n − ẽ_{m+1}) = ẽ_{m+1} − ẽ_{m}.

Write D := ⟨B⟩ ∩ C^{⊥}. Since dim μ(B) − dim μ(B′′) = 1, we must have B = β(D), and there must be a chain of z subcodes

D_{r} ⊂ D_{r+1} ⊂ D_{r+2} ⊂ … ⊂ D_{r+z−1} = D

where D_{i} has dimension i for r ≤ i < r + z and w(D_{i}) = w(D_{i+1}) − 1 for r < i ≤ r + z − 2. Moreover, by the bound (4.2), we get

w(D_{i}) = n − ẽ_{j} + 1 + j − m + i − r − 1 = e_{i}^{⊥}.

23

And in particular

w(D) = w(D_{r+z−1}) = n − ẽ_{j} + j − m + z − 1 = e_{r+z−1}^{⊥}.

It remains to show that s = r + z − 1 (where s is given in the lemma). Consider

\begin{aligned}r + z − 1 − s & = (n − k − ẽ_{j} + j) + (ẽ_{m+1} − ẽ_{m}) − 1 − (n − k − ẽ_{m} + m) \\ & = j − ẽ_{j} + ẽ_{m+1} − (m + 1) = 0, \end{aligned}

by the definition of j. □

Corollary 4.1 If i and s are as given in Lemma 4.1, then e_{s}^{⊥} = n − ẽ_{i}.

Theorem 4.2 (Duality) Let (e_{1}, … e_{k}) be the greedy weight hierarchy of a code C, and (ẽ_{1}^{⊥}, …, ẽ_{n−k}^{⊥}) the top-down greedy weight hierarchies for C^{⊥}. Then

{ẽ_{1}, ẽ_{2}, …, ẽ_{k}} and {n + 1 − e_{1}^{⊥}, n + 1 − e_{2}^{⊥}, …, n + 1 − e_{n−k}^{⊥}}

are disjoint sets whose union is {1, … n}.

Proof: Let i_{1} < i_{2} < … be the values of i for which ẽ_{i} > ẽ_{i−1}. Going to the proof of Lemma 4.1, with m = i_{x}, we get j = i_{x+1}. The proof showed that n − ẽ_{y} + 1 ≠ e_{s}^{⊥} for all s, for all y, i_{x} ≤ y < i_{x+1}. This holds for all x, hence the theorem. □

Since the CEZ weights does not form a monotonous sequence in general, an analogue of Theorem 4.2 would not make sense for CEZ weights.

4.4 Bounds on greedy weights

It is known that for any chained code, d_{r} − d_{r−1} ≤ q(d_{r+1} − d_{r}). The same relation holds for the top-down and bottom-up greedy weights of arbitrary codes.

Proposition 4.1 For any sequence of bottom-up greedy weights (e_{1}, … e_{k}) or top-down greedy weights (ẽ_{1}, …, ẽ_{k}), we have

e_{r} − e_{r−1} ≤ q(e_{r+1} − e_{r}),
ẽ_{r} − ẽ_{r−1} ≤ q(ẽ_{r+1} − ẽ_{r}),

for 1 ≤ r < k.

24

4.4. BOUNDS ON GREEDY WEIGHTS

Proof: Let Π_{r+1} ⊂ Π_{r} ⊂ Π_{r−1} be a chain of greedy subspaces of codimensions r + 1, r, and r − 1 respectively. Clearly γ_{C}(Π_{r−1}\Π_{r}) = e_{r} − e_{r−1} and γ_{C}(Π_{r}\Π_{r+1}) = e_{r+1} − e_{r}.

There are q subspaces containing Π_{r+1} in Π_{r−1} in addition to Π_{r}, and each of them has value at most e_{r}. Hence e_{r+1} − e_{r} ≤ q(e_{r} − e_{r−1}).

The proof for the top-down greedy weights is similar. □ The following is another analogue of known results on weight hierearchies

of chained codes.

Proposition 4.2 Any set (e_{1}, e_{2}, … e_{k}) of greedy weights can be split for any i, 1 ≤ i < k, into two sets of greedy weights, (e_{1}, … e_{i}) and (e_{i+1} − e_{i}, e_{i+2} − e_{i}, … e_{k} − e_{i}).

Proof: If C is a code with greedy weights (e_{1}, e_{2}, … e_{k}), and let

{0} = D_{0} ⊂ D_{1} ⊂ D_{2} ⊂ … ⊂ D_{k} = C

be a chain of greedy subcodes.

The subcode D_{i} is an [e_{i}, i] code with greedy weights (e_{1}, … e_{i}).

If C is punctured on χ(D_{i}), we get an [e_{k} − e_{i}, k − i] code with greedy weights (e_{i+1} − e_{i}, e_{i+2} − e_{i}, … e_{k} − e_{i}). □

Remark 4.3 Also the top-down greedy weights have the property described by Proposition 4.2. The proof is similar.

The generalised Hamming weights are likely to increase by this construction, and hence the greedy gains are likely to decrease. In any case the greedy gains cannot increase.

25

26

Support Weight Distribution

Identification of self-dual codes with high minimum weight is a classic problem in coding theory. Dougherty and Gulliver [DG01] have studied the support weight distributions of such codes. Possibly, some existence or nonexistence results may be obtained through higher weights, even though it will not be in this paper…

5.1 Preliminaries

Let PG(k − 1, q) denote the projective geometry of dimension k − 1 over the finite field 𝔽 with q elements. Let PG^{r}(k − 1, q) denote the set of r-spaces in PG(k − 1, q). For simplicity, we will not make a distinction between a point x and the 0-space {x}. The linear dimension of PG(k − 1, q) is k = dim lin PG(k − 1, q). In this chapter we will consider γ_{C} as a multiset on PG(k − 1, q) = ℙ(𝕄) rather than on 𝕄. We recall from the introduction that this projective multiset preserves all properties related to the code.

From elementary projective geometry, we get number of distinct r-spaces as follows

#PG^{r}(k − 1, q) = \left[{k \atop r + 1}\right] := ∏_{i=0}^{r} \frac{q^{k−i} − 1}{q^{r+1−i} − 1}.

The number of r-spaces containing a given m-space is given by \left[{k−m−1 \atop r−m}\right].

Definition 5.1 A projective multiset (or a code) is called r-DMDS (r-dual MDS) or (k − 1 − r)-MDS if Δ_{r} = r + 1. A projective multiset (or code) is barely r-DMDS if it is r-DMDS and not (r + 1)-DMDS.

An equivalent and more classic definition is that a code is r-MDS if it meets the r-th generalised singleton bound with equality, i.e. if d_{r} = d_{k} − k + r. Note that any i-DMDS code is (i − 1)-DMDS, and being 0-DMDS is equivalent with being a projective code.

27

CHAPTER 5. SUPPORT WEIGHT DISTRIBUTION

5.1.1 Support Weight Distribution

Let 𝔙_{i}^{r}(C) be the set of all r-spaces of value i, i.e.

𝔙_{i}^{r}(C) = {Π ≦ PG(k − 1, q) | γ_{C}(Π) = i, dim Π = r}.

We define the value distribution of γ_{C} to be

V_{i}^{r}(γ_{C}) = V_{i}^{r}(C) := #𝔙_{i}^{r}(C).  (5.1)

Let 𝔄_{i}^{r}(C) be the set of r-dimensional subcodes of C with weight i. The support weight distribution of C is given by

A_{i}^{r}(C) := #𝔄_{i}^{r}(C).

By Lemma 2.2, there is a one-to-one correspondence between 𝔙_{i}^{r}(C) and 𝔄_{n−i}^{k−1−r}(C). Hence

V_{i}^{r}(γ_{C}) = V_{i}^{r}(C) = A_{n−i}^{k−1−r}(C).

We will mostly abbreviate and write V_{i}^{r} = V_{i}^{r}(C), A_{i}^{r} = A_{i}^{r}(C), Ã_{i}^{r} = A_{i}^{r}(C^{⊥}), and Ṽ_{i}^{r} = V_{i}^{r}(C^{⊥}).

Trivially, we have

V_{0}^{−1} = A_{n}^{k} = 1,  (5.2)
V_{n}^{k−1} = A_{0}^{0} = 1.  (5.3)

Define

m_{i} = m_{i}(C) := d_{i}(C^{⊥}) − i − 1.

Obviously m_{0} = −1 and m_{n−k} = k − 1. We will determine V_{i}^{r} for m_{j} ≤ r < m_{j+1} for each j = 0 and j = 1. We start with a relatively simple result.

Lemma 5.1 If m_{j+1} > m_{j}, then

V_{m_{j}+j+1}^{m_{j}} = Ã_{m_{j}+j+1}^{j},
V_{i}^{m_{j}} = 0, i > m_{j} + j + 1.

Proof: Consider an m_{j}-space Π for some j where m_{j+1} > m_{j}. From Lemma 2.3 we know that Π has value d_{j}^{⊥} = m_{j} +j +1 if and only it contains x_{i} for all i ∈ χ(D) where D ≦ C^{⊥} is a j-dimensional subcode of weight d_{j}^{⊥}. This gives the first equation. The second equation is obvious. □

In this chapter, we will see that A_{i}^{r}(C) can be computed for all r ≥ k + 2 − d_{2}(C^{⊥}) if we know the complete (first) weight enumerator for C^{⊥}. The result will be summarised in Theorem 5.2.

28

5.2. IN THE RANGE M_{0} ≤ R < M_{1}

5.1.2 Making new codes from others

Consider an m-space Π_{m} ≦ PG(k − 1, q). Let

π_{Π_{m}} : PG(k − 1, q)\Π_{m} → PG(k − 2 − m, q)

be the projection map through Π_{m}. Let C′ be the code corresponding to γ_{C′} := γ_{C} ∘π^{−1}. Note that C′ has parameters [n−γ_{C}(Π_{m}), k−1−m]. Every r-space in PG(k − 2 − m, q) is the image of an (r + m + 1)-space containing Π_{m} in PG(k − 1, q). Hence

Δ_{r}(C′) ≤ Δ_{r+m+1}(C) − γ_{C}(Π_{m}).

Hence, if Π_{m} has maximum value, then C′ is (m_{1} −m−2)-DMDS. Note that C′ can be viewed as a subcode of C [DS98].

5.2 In the range m_{0} ≤ r < m_{1}

Note that any code is (barely) R-DMDS where R = m_{1} − 1. We write V_{i}^{r}(n, k) = V_{i}^{r}(C) for some R-DMDS [n, k] code C, where r ≤ R. We will see that this number is well-defined and independent of C.

When a code is R-DMDS, it means that for all r ≤ R, any (r + 1)-subset of γ spans an r-space of PG(k − 1, q). It follows immediately that

V_{r+1}^{r}(n, k) = \binom{n}{r + 1},  (5.4)
V_{j}^{r}(n, k) = 0, ∀j > r + 1.  (5.5)

Lemma 5.2 For 0 ≤ r < m_{1}, V_{j}^{r}(n, k) is well-defined, and we have

V_{0}^{r}(n, k) = \left[{k \atop r + 1}\right] − ∑_{j=1}^{r+1} V_{j}^{r}(n, k),  (5.6)

V_{j}^{r}(n, k) = \binom{n}{j}V_{0}^{r−j}(n − j, k − j),  0 < j ≤ r + 1,  (5.7)
V_{j}^{r}(n, k) = 0,  j > r + 1.  (5.8)

Proof: Equation (5.8) comes from (5.5). For j = r + 1, we get from (5.2) that (5.7) reduces to

V_{r+1}^{r}(n, k) = \binom{n}{r + 1},

which has been proved in (5.4). If we can prove (5.7) for 0 < j ≤ r, then (5.6) follows by definition. Thus the lemma becomes trivial for r = 0, and

29

we can proceed by induction. Hence assume (5.7) hold for r − 1, and that 0 < j ≤ r. Then also (5.6) holds for r − 1.

An r-space Π_{r} of value j contains a unique (j − 1)-space Π of value j. There are a total V_{j}^{j−1} such subspaces in the geometry, by the induction hypothesis. We consider the projection π_{Π}, which defines an (m_{1} − 1 − j)- DMDS code C′ by γ_{C} ∘ π_{Π}^{−1}.

These r-spaces correspond to the (r − j)-spaces in im π_{Π}. Hence Π_{r} has value j if and only if π_{Π}(Π_{r}) has zero value. The number of such (r − j)- spaces is V_{0}^{r−j}(n − j, k − j) by the induction hypothesis. Hence

V_{j}^{r}(n, k) = V_{j}^{j−1}(n, k)V_{0}^{r−j}(n − j, k − j).

By application of (5.4), we get (5.7). The result follows by induction. □

Lemma 5.3 [Aig79, p. 77] We have for all natural numbers n that

∑_{k=0}^{n}(−1)^{k}\binom{n}{k} = 0.

Lemma 5.4 For 0 ≤ r < m_{1}, V_{0}^{r}(n, k) is well-defined, and we have

V_{0}^{r}(n, k) = ∑_{j=0}^{r+1}(−1)^{j} \left[{k − j \atop r + 1 − j}\right] \binom{n}{j}.

Proof: For r = −10 and r = 0, the lemma reduces to

V_{0}^{−1}(n, k) = 1,

V_{0}^{0}(n, k) = \left[{k \atop 1}\right] − n,

which matches (5.2) and (5.6). We assume that the lemma holds for r − 1 and proceed by induction.

We have from Lemma 5.2, that

\begin{aligned}V_{0}^{r}(n, k) & = \left[{k \atop r + 1}\right] − ∑_{j=1}^{r+1} V_{j}^{r}(n, k) \\ & = \left[{k \atop r + 1}\right] − ∑_{j=1}^{r+1} \binom{n}{j}V_{0}^{r−j}(n − j, k − j), \end{aligned}

If we combine with the induction hypothesis, we get

V_{0}^{r}(n, k) = \left[{k \atop r + 1}\right] − ∑_{j=1}^{r+1} \binom{n}{j} ∑_{i=0}^{r−j+1}(−1)^{i} \left[{k − j − i \atop r − j + 1 − i}\right] \binom{n − j}{i}.

30

We set m = i + j and rewrite to get

V_{0}^{r}(n, k) = \left[{k \atop r + 1}\right] − ∑_{m=1}^{r+1} \left[{k − m \atop r + 1 − m}\right] ∑_{i=0}^{m−1}(−1)^{i}\binom{n}{m − i}\binom{n − m + i}{i}

= \left[{k \atop r + 1}\right] − ∑_{m=1}^{r+1} \left[{k − m \atop r + 1 − m}\right] ∑_{i=0}^{m−1}(−1)^{i}\binom{n}{m}\binom{m}{i}.

By Lemma 5.3, we get

− ∑_{i=0}^{m−1}(−1)^{i}\binom{n}{m}\binom{m}{i} = (−1)^{m}\binom{n}{m}\binom{m}{m} = (−1)^{m}\binom{n}{m}.

Hence

V_{0}^{r}(n, k) = \left[{k \atop r + 1}\right] + ∑_{m=1}^{r+1} \left[{k − m \atop r + 1 − m}\right] (−1)^{m}\binom{n}{m}

= ∑_{j=0}^{r+1} \left[{k − j \atop r + 1 − j}\right] (−1)^{j}\binom{n}{j},

as required. The lemma follows by induction. □ The following theorem is a direct result of Lemmata 5.2 and 5.4.

Theorem 5.1 For 0 ≤ r < m_{1}, V_{j}^{r}(n, k) is well-defined, and we have

V_{j}^{r}(n, k) = \binom{n}{j} ∑_{i=0}^{r−j+1}(−1)^{i} \left[{k − j − i \atop r − j + 1 − i}\right] \binom{n − j}{i}.

5.3 In the range m_{1} ≤ r < m_{2}

5.3.1 Some notation

In this section we consider m_{1} ≤ r < m_{2}. We know that V_{i}^{r} = 0 for all i > r + 2.

Consider an r-space Π of value r + 2. The cross-section γ_{C}|_{Π} defines an [r + 2, r + 1] code C′. Let s := m_{1}(C′). We say that Π has type s. Clearly m_{1} ≤ s ≤ r. The set of r-spaces of type s is denoted by 𝔖(r, s).

Given an r-space Π′ of value i ≤ r + 1; we say that Π′ is Type I if it contains a (i − 2)-space Π′′ of value i for some i. This (i − 2)-space is unique when it exists. Clearly Π′′ has type s for some s, and then we say that Π′ is Type I(s).

If Π′ is not Type I, we say that it is Type II, and then it contains a unique (i − 1)-space of value i. Let 𝔘_{i}^{r}(X) be the set of r-spaces of value i and Type X, where X is I, II, or I(s) for some s. Write U_{i}^{r}(X) := #𝔘_{i}^{r}(X).

31

5.3.2 Subspaces of Maximum Value

If C is an [n, n − 1] code, there is a unique s such that δ_{s}(C) = 2, and δ_{i}(C) = 1 for i ≠ s. Clearly m_{1}(C) = s. In this case, we call C an [n, n − 1] code of type s.

Lemma 5.5 Let γ_{C} be a projective multiset defining an [n, n − 1] code C of type s. Then there is a unique s-space Π_{s} of value s + 2.

Proof: There exists at least one such s-space since Δ_{s}(C) = s + 2. Suppose there are two distinct s-spaces Θ_{1} and Θ_{2} of value s + 2. Let i be the dimension of Θ := Θ_{1} ∩ Θ_{2}. Clearly i < s and thus γ_{C}(Θ) ≤ i + 1. We get

γ(⟨Θ_{1}, Θ_{2}⟩) ≥ 2(s + 2) − (i + 1) = 2s − i + 3,

but

dim⟨Θ_{1}, Θ_{2}⟩ = 2s − i = 2s − i,

so

γ(⟨Θ_{1}, Θ_{2}⟩) ≤ Δ_{2s−i}(C) = 2s − i + 2.

The lemma follows by contradiction. □

There is only one [n, n − 1] code of Type s up to equivalence. The corresponding projective multiset is obtained by taking a frame for a projective s-space and then add projectively independent points to obtain an (n − 2)- space.

Lemma 5.6 For any code C, if m_{1} ≤ s ≤ r < m_{2}, we have

#𝔖(r, s) = Ã_{s+2}^{1}\binom{n − s − 2}{r − s}.

Proof: The number of maximum r-spaces of type r is

#𝔖(s, s) = Ã_{s+2}^{1},  (5.9)

by Lemma 2.3.

An r-space Π_{r} of type s contains a unique s-space Π_{s} of value s + 2 by Lemma 5.5. Hence there is a one-to-one correspondence between r-spaces of type s and pairs (Π_{s}, S) where Π_{s} ∈ 𝔖(s, s) and S ⊂ γ_{C}\Π_{s} is a set of r − s points. There are Ã_{s+2}^{1} ways to choose Π_{s} by (5.9) and \binom{n−s−2}{r−s} ways to choose S. Hence we get the result. □

Lemma 5.7 If m_{1} ≤ r < m_{2}, then

V_{r+2}^{r} = ∑_{s=m_{1}}^{r} Ã_{s+2}^{1}\binom{n − s − 2}{r − s},
V_{i}^{r} = 0, i > r + 2.

32

Proof: An r-space of value r + 2 has type s for some s where m_{1} ≤ s ≤ r. Thus we can take the sum of the equation in Lemma 5.6. Hence the result. □

5.3.3 When n = k + 1

In this section we study an [n, n − 1] code C of type s. We will need the number F(j, n, s) := U_{j}^{n−3}(II) for C in the later sections.

We obviously have that F(j, n, s) = 0 if n < j + 2. When n = s + 2, C is a MDS, so

F(j, s + 2, s) = V_{j}^{s−1}(s + 2, s + 1).  (5.10)

Lemma 5.8 For any [n, n − 1] code of type s, if j ≤ n − 2, then U_{j}^{j−1}(II) is given by

F(i, n, s) = ∑_{j=0}^{i} V_{j}^{s−1}(s + 2, s + 1)\binom{n − s − 2}{i − j}(q − 1)^{n−2−s+i−j}.

Proof: Note that if n = s + 2, the lemma reduces to (5.10).

We consider the projective space PG(n − 2, s). We want to find the number F(i, n, s) of hyperplanes of value i and Type II. Consider an arbitrary such hyperplane Π. There is a unique s-space Θ ≦ PG(n−2, s) of value s+2. Every hyperplane must meet Θ in a subspace of dimension s − 1 or more. Since Π has Type II, Θ′ := Θ∩Π is exactly an (s−1)-space. Let j = γ_{C}(Θ′).

Given j, there are F(j, s + 2, s) ways to choose Θ′. Let Π′ ≦ Π be the smallest subspace of value i and containing Θ′. Given Θ′ we find Π′ by choosing i − j points among the n − s − 2 points of positive value not contained in Θ. Given i, there are thus

F(j, s + 2, s)\binom{n − s − 2}{i − j} = V_{j}^{s−1}(s + 2, s + 1)\binom{n − s − 2}{i − j}

ways to choose Π′.

Consider now the projection π_{Π′}. The multiset γ′′ := γ_{C} ∘ π_{Π′}^{−1} defines an [n−i, n−1−s−i+j] code. There is but one point x of value γ′′(x) = s+2−j, namely x = π_{Π′}(Θ). The remaining points have value 0 or 1. We define a new projective multiset γ′ by γ′(x) = 1 and γ′(y) = γ′′(y) for y ≠ x. The corresponding code is a projective [n′, n′] code where n′ = n − i − s − 1 + j.

Finding Π ≧ Π′ of value i is the same as finding a hyperplane of zero value for γ′, which is the same as counting one-dimensional subcodes of weight n′ for the [n′, n′] code. This number is (q − 1)^{n′−1}. The lemma follows by summing over all j. □

33

5.3.4 Other subspaces

Now we return to the general [n, k] code C, in order to determine V_{j}^{r} for j ≤ r + 1.

Proposition 5.1 For m_{1} ≤ r < m_{2} and r ≥ i − 2, we have

U_{i}^{r}(I(s)) = V_{0}^{r+1−i}(n − i, k + 1 − i)Ã_{s+2}^{1}\binom{n − s − 2}{i − s − 2},
U_{i}^{r}(I) = V_{0}^{r+1−i}(n − i, k + 1 − i)V_{i}^{i−2}.

For r < i − 2, we have U_{i}^{r}(I) = U_{i}^{r}(I(s)) = 0.

Proof: We have from Lemma 5.6, we have that

U_{i}^{i−2}(I(s)) = Ã_{s+2}^{1}\binom{n − s − 2}{i − 2 − s}.

An r-space of value i and Type s contains a unique (i − 2)-space Π′ of value i and Type s by Lemma 5.4. There are U_{i}^{i−2}(I(s)) ways to choose Π′.

Consider then the multiset γ′ := γ_{C} ∘π_{Π′}^{−1} obtained by projection through Π′. We know that γ′ defines an [n − i, k + 1 − i] code C′. Finding an r-space Π ≧ Π′ of value i corresponds to finding an (r + 1 − i)-space of value 0 for γ′. Furthermore γ′ defines a code with

Δ_{m_{2}−i}(C′) ≤ Δ_{m_{2}−1}(C) − i = m_{2} + 1 − i.

Hence C′ is (m_{2}−i)-DMDS, and since r+1−i ≤ m_{2}−i, there are V_{0}^{r+1−i}(n− i, k + 1 − i) ways to choose Π ≧ Π′. This proves the first equation, and the second one follows by summing over all s. □

Proposition 5.2 If m_{1} < j ≤ m_{2}, we have

U_{j}^{j−1}(II) = \binom{n}{j} − U_{j}^{j−2}(I) − ∑_{s=m_{1}}^{j−1}(s + 2)U_{j+1}^{j−1}(I(s)).

For i > j, we have U_{i}^{j−1}(II) = 0.

Proof: We consider all the \binom{n}{j} possible ways to chose a set S of j points of positive value. To find U_{j}^{j−1}(II), we must subtract the number of cases where these j points generate a subspace of type I.

Since j − 1 < m_{2}, we have three cases:

1. dim⟨S⟩ = j − 1 and γ_{C}(⟨S⟩) = j. (Type II)

34

2. dim⟨S⟩ = j − 2 and γ_{C}(⟨S⟩) = j. (Type I)

3. dim⟨S⟩ = j − 1 and γ_{C}(⟨S⟩) = j + 1. (Type I)

The number of sets S giving the first case is U_{j}^{j−1}(II), while for the second case, it is U_{j}^{j−2}(I). The third case is more difficult, because S does not contain all points of positive value in ⟨S⟩. Suppose ⟨S⟩ has type s. Then ⟨S⟩ can be chosen in U_{j+1}^{j−1}(I(s)) different ways. There is one point x ∉ S of positive value in ⟨S⟩, and x must be contained in the unique s-space Π_{s} ≦ ⟨S⟩ of value s + 2. Moreover x can be any point of positive value in Π_{s}, hence there are s + 2 different choices for S giving the same ⟨S⟩ of the third case. This gives the lemma. □

Let

𝔘(r_{1}, v_{1}, X_{1}; r_{2}, v_{2}, X_{2}) = {(Π_{1}, Π_{2}) | Π_{1} ≦ Π_{2}, Π_{j} ∈ 𝔘_{v_{j}}^{r_{j}}(X_{j}), j = 1, 2}.

As for 𝔙, we will write v_{j} = ∗ resp. X_{j} = ∗, when we allow any value of v_{j} resp. X_{j}.

Lemma 5.9 If m_{1} ≤ r < m_{2} and 0 ≤ j ≤ r, then

U_{j}^{r}(II) = \frac{q − 1}{q^{r+1−j} − 1}(U_{j}^{r−1}(II)\frac{q^{k−r} − 1}{q − 1} − ∑_{v=j+1}^{r+2} #𝔘(r − 1, j, II; r, v, ∗)).

Proof: We will count the number of elements of 𝔘(r − 1, j, II; r, j, II) in two different ways. Consider a pair

(Π′, Π) ∈ 𝔘(r − 1, j, II; r, j, II).

There are U_{j}^{r}(II) ways to choose Π. For Π′, we can choose any (r − 1)-space containing the unique (j − 1)-space of value j in Π. Hence

#𝔘(r − 1, j, II; r, j, II) = U_{j}^{r}(II) \left[{r + 1 − j \atop r − j}\right] = U_{j}^{r}(II)\frac{q^{r+1−j} − 1}{q − 1}. (5.11)

This gives the first of our two expressions.

Now we observe that

#𝔘(r − 1, j, II; r, ∗, ∗) = ∑_{v=j}^{r+2} #𝔘(r − 1, j, II; r, v, ∗).  (5.12)

This number can equivalently be obtained by counting the number of (r−1)- spaces of value j and Type II, and the number of r-spaces containing each such space. This gives

#𝔘(r − 1, j, II; r, ∗, ∗) = U_{j}^{r−1}(II) \left[{k − r \atop 1}\right] = U_{j}^{r−1}(II)\frac{q^{k−r} − 1}{q − 1}. (5.13)

35

Clearly we have that

#𝔘(r − 1, j, II; r, j, I) = 0,

and if we combine this with with (5.12) and (5.13), we get

#𝔘(r − 1, j, II; r, j, II) = U_{j}^{r−1}(II)\frac{q^{k−r} − 1}{q − 1} − ∑_{v=j+1}^{r+2} #𝔘(r − 1, j, II; r, v, ∗),

which is our second expression for #𝔘(r − 1, j, II; r, j, II). Combining this with (5.11), we get the lemma. □

Lemma 5.10 If j < v − 1, then

#𝔘(r − 1, j, II; r, v, I(s)) = U_{v}^{r}(I(s))F(j, v, s)q^{r+2−v}.

Proof: Consider a pair

(Π′, Π) ∈ 𝔘(r − 1, j, II; r, v, I(s)).

There are U_{v}^{r}(I(s)) ways to choose Π. There is a unique (v − 2)-space Θ ≦ Π of value v and type s. The intersection Θ′ := Π′ ∩ Θ is a (v − 3)-space of value j. There are F(j, v, s) ways to choose Θ′.

Consider the projection π_{Θ′}. Finding Π′ is the same as finding a hyperplane in im π_{Θ′} not meeting π_{Θ′}(Θ), which is a point. There are (q^{r+3−v} − 1)/(q − 1) hyperplanes in im π_{Θ′}, of which (q^{r+2−v} − 1)/(q − 1) meet π_{Θ′}(Θ). Hence there are q^{r+2−v} hyperplanes not meeting π_{Θ′}(Θ). □

Lemma 5.11 If j < v, then

#𝔘(r − 1, j, II; r, v, II) = U_{v}^{r}(II)V_{j}^{v−2}(v, v)q^{r+1−v}.

Proof: Consider a pair

(Π′, Π) ∈ 𝔘(r − 1, j, II; r, v, II).

There are U_{v}^{r}(II) ways to choose Π. There is a unique (v − 1)-space Θ ≦ Π of value v, and γ_{C}|_{Θ} defines a [v, v] code. The intersection Θ′ := Π′ ∩ Θ is a (v − 2)-space of value j. There are V_{j}^{v−2}(v, v) ways to choose Θ′.

Consider the projection π_{Θ′}. Finding Π′ is the same as finding a hyperplane in im π_{Θ′} not meeting π_{Θ′}(Θ), which is a point. There are q^{r+1−v} such hyperplanes. □

We define for brevity:

𝔉(r, j) := ∑_{v=j+1}^{r+2} #𝔘(r − 1, j, II; r, v, ∗).

36

Proposition 5.3 We have

𝔉(r, j) = ∑_{v=j+2}^{r+2} q^{r+2−v}[U_{v−1}^{r}(II)V_{j}^{v−3}(v − 1, v − 1) + ∑_{s=m_{1}}^{r} U_{v}^{r}(I(s))F(j, v, s)].

Proof: First note that

#𝔘(r − 1, j, II; r, r + 2, II) = 0,

because U_{r+2}^{r}(II) = 0, and that

#𝔘(r − 1, j, II; r, j + 1, I) = 0,

because there is no subspace of value j in a subspace of value j +1 and Type I. Now the result follows from Lemmata 5.10 and 5.11. □

Proposition 5.4 If m_{1} ≤ r < m_{2} and 0 ≤ j ≤ r, then

U_{j}^{r}(II) = \frac{q^{k−r} − 1}{q^{r+1−j} − 1}U_{j}^{r−1}(II) − \frac{q − 1}{q^{r+1−j} − 1}𝔉(r, j),

where 𝔉(r, j) is given by Proposition 5.3.

Proof: This is simply a rephrase of Lemma 5.9. □

If we combine all the results of this chapter, we get the following theorem as a conclusion.

Theorem 5.2 For k ≥ r > k+2−d_{2}(C^{⊥}), it is possible to compute A_{i}^{r}(C) for all i provided we know the (first) weight enumerator of C^{⊥}. We have for k + 1 − d_{1}(C^{⊥}) < r ≤ k, that

A_{i}^{r}(C) = \binom{n}{n − i} ∑_{j=0}^{k+i−r−n}(−1)^{n−i} \left[{k − n + i − j \atop k − r − n + i − j}\right] \binom{i}{j},

and for k + 2 − d_{2}(C^{⊥}) < r ≤ k + 1 − d_{1}(C^{⊥}), that

A_{i}^{r}(C) = U_{n−i}^{k−1−r}(II) + U_{n−i}^{k−1−r}(I),

where U_{n−i}^{k−1−r}(II) and U_{n−i}^{k−1−r}(I) are given by Propositions 5.1, 5.2 and 5.4.

Example 5.1 Employing the theorem above on the binary [24, 12] Golay code, which is selfdual, with a simple Maple program, gives us the third through the twelveth support weight enumerator in about 15 seconds.

37

Problem 5.1 Simplify the recursion formulæ from Proposition 5.4.

Problem 5.2 Study the r-th support weight distribution for r ≤ k + 2 − 2 − d_{2}(C^{⊥}).

Problem 5.3 Does there exist a [72, 36, 16] Type II self-dual code?

The latter problem is a popular one [Dou01] and has been studied for quite some time. For instance, the first and second support weight distributions of such a code have been uniquely determined [DG01]; and the results of this chapter determine the 15th through the 36th support weight distribution, see Appendix A. If even more support weight distributions are determined, that might help us towards an answer to Problem 5.3.

38

Appendix A

The [72, 36, 16] selfdual code

We present below the support weight distributions for the tentative [72, 36, 16] selfdual Type II code, as far as we know them. All entries not mentioned are zero. The weight enumerator is copied from [Dou01], while the second support weight enumerator is copied from [DG01].

A_{0}^{0} = 1
A_{16}^{1} = 249849
A_{20}^{1} = 18106704
A_{24}^{1} = 462962955
A_{28}^{1} = 4397342400
A_{32}^{1} = 16602715899
A_{36}^{1} = 25756721120
A_{40}^{1} = 16602715899
A_{44}^{1} = 4397342400
A_{48}^{1} = 462962955
A_{52}^{1} = 18106704
A_{56}^{1} = 249849
A_{72}^{1} = 1
A_{24}^{2} = 96191865
A_{26}^{2} = 4309395552
A_{28}^{2} = 119312891460
A_{30}^{2} = 2379079500864
A_{32}^{2} = 37327599503964
A_{34}^{2} = 466987648992480
A_{36}^{2} = 4687779244903412
A_{38}^{2} = 37810235197002240
A_{40}^{2} = 244777798274765679
A_{42}^{2} = 1269000323938260672
A_{44}^{2} = 5251816390965277320
A_{46}^{2} = 17262594429823645056
A_{48}^{2} = 44763003632389491540
A_{50}^{2} = 90768836016453484224
A_{52}^{2} = 142313871132195291144
A_{54}^{2} = 170060449665123790080
39

APPENDIX A. THE [72, 36, 16] SELFDUAL CODE

A_{56}^{2} = 152060783100409784007
A_{58}^{2} = 99349931253373567200
A_{60}^{2} = 45970401654169517364
A_{62}^{2} = 14440224673488398400
A_{64}^{2} = 2900924791551272475
A_{66}^{2} = 340809968304405600
A_{68}^{2} = 20197782231604740
A_{70}^{2} = 451381581930240
A_{72}^{2} = 1617151596337
A_{i}^{3} through A_{i}^{13} are undetermined.
A_{48}^{14} = 96191865
A_{49}^{14} through A_{72}^{14} are undetermined.
A_{50}^{15} = 8136215755668
A_{51}^{15} = 835119760789303704
A_{52}^{15} = 20695392862851155911308
A_{53}^{15} = 337488222974050367616584880
A_{54}^{15} = 4437610578986313918980616085260
A_{55}^{15} = 50740517953635873912087857906170968
A_{56}^{15} = 520959409608056571069230661760967830704
A_{57}^{15} = 4867575269161335905011089825963182224795968
A_{58}^{15} = 41573154133969089965956554893213195162353269960
A_{59}^{15} = 324505801293722544021315422435073624777366156041520
A_{60}^{15} = 2308334716013902739199118677866796247405721152584958488
A_{61}^{15} = 14893968203696075514117480615392622172247938033503672101664
A_{62}^{15} = 86628304494310959793323245627958517370084055051020281657482648
A_{63}^{15} = 450673256748353559429749774852476667854661123964195396889869033840
A_{64}^{15} = 2076892031101546850443892260521140339911626429772444095683679500936955
A_{65}^{15} = 8376328244723302150121186081915229431227501946784404628530079618046755648
A_{66}^{15} = 29111038655486724663350051448822691581823120122090198330775681371586691001444
A_{67}^{15} = 85423516086539348299055453412621287083086791971673934245233718275777555180260408
A_{68}^{15} = 205815710542321982631446960027809207590898134248774656817597548572093093599846974620
A_{69}^{15} = 390955887552635541236585848892614762863964952845915619050959818230962372587006641925040
A_{70}^{15} = 549020397860648429789443201587269945311522797548469762349426407872640455474846051226742428
A_{71}^{15} = 506754042154015135916241032444295211826500698538596221007902411825622743857192540814883977016
A_{72}^{15} = 230622466665508101211452817597506326599621375196004079893797046073742090590843322302999731529896
A_{51}^{16} = 955318756392
A_{52}^{16} = 324059272405010604
A_{53}^{16} = 15507021624137440467840
A_{54}^{16} = 474561851584824561663788760
A_{55}^{16} = 11623944276671500692050896514520
A_{56}^{16} = 246640448766609422872631592826550472
A_{57}^{16} = 4683361304329775589374273112371482518144
A_{58}^{16} = 80635773988140643861996146466370423309909280
A_{59}^{16} = 1263805770070201211502013880815196449094128891920
A_{60}^{16} = 18015403670949619263428884402772581298962323539986680
A_{61}^{16} = 232711045434432236271252106923163167735800166402446504832
A_{62}^{16} = 2708415090939376443146130682207339409482354901831610456796944
A_{63}^{16} = 28187716077651800977996031264247825047154509950110064644392239920
A_{64}^{16} = 259837403400795815247993702001608422833802173004246279362250513350155
A_{65}^{16} = 2096064138326431421431102911130575786290570655358368733211779984837941120
A_{66}^{16} = 14569963294458664326355487170744990843837617978935772288101581858605054795552

40

A_{67}^{16} = 85510894526060064479316734488318369938132499492635355684079016542478398862657864^{A_{68}^{16} = 412061904138340651838258915451864484939896797157076661122864740989298055974944944860}^{A_{69}^{16} = 1565488852371982431316111853396983584332969710134675077027530620252550946995296142083840}^{A_{70}^{16} = 4396915838403660911650398295638009077743887167941233305415838283721851832492505632039216600}^{A_{71}^{16} = 8116969816624838830801088499939113019151857945741585158878344261113649308345975704397677746552}^{A_{72}^{16} = 7388140606757652316551184042840864111185122735762129471990462501850454686856236449205248928744000}^{A_{52}^{17} = 91785145914}^{A_{53}^{17} = 119568071490464520}^{A_{54}^{17} = 10876487640570887324220}^{A_{55}^{17} = 621102090153359698291706760}^{A_{56}^{17} = 28238160854835833114504984355630}^{A_{57}^{17} = 1108157813543413273298620857135636384}^{A_{58}^{17} = 38775184810475101465606055160117405564240}^{A_{59}^{17} = 1225103937489704214641684550738372081401867040}^{A_{60}^{17} = 35065204191503035433370193365900354965138410343220}^{A_{61}^{17} = 907681334214185700293457448447939059762410127375389040}^{A_{62}^{17} = 21148992310071639157319140376118406012552458647322343552104}^{A_{63}^{17} = 440433013676879236893987806136656868350246431929409050119051760}^{A_{64}^{17} = 8121963269773109567799825717572208415238032374371172660779462080935}^{A_{65}^{17} = 131053992016717789535549409271373358424539240220722655090265729644991520}^{A_{66}^{17} = 1822065408520163738870424152706593276741607710040279908656389811919195138640}^{A_{67}^{17} = 21388164637920075231207019666260593943281471778008463404787560606822242957167264}^{A_{68}^{17} = 206136296922893252992206955250803722581601758817278054057532415849969910288340400530}^{A_{69}^{17} = 1566313196283169849483675135686582410839308059520962831364429490936069174691076805799880}^{A_{70}^{17} = 8798562961666445456747404278061261720915854841679239454779813701598944111469025441396899260}^{A_{71}^{17} = 32485657545476650031612695113466571071302528277208662980584517567048303332047772821412291200200}^{A_{72}^{17} = 59137996348791480849060255032023289944440456051110588987685446949657888979888248008238833107438014}^{A_{53}^{18} = 6925814280}^{A_{54}^{18} = 41633686367645680}^{A_{55}^{18} = 7110932897974106927880}^{A_{56}^{18} = 754211539074414108843640980}^{A_{57}^{18} = 63423329995483370407100946178080}^{A_{58}^{18} = 4586415483573974202270056789964917760}^{A_{59}^{18} = 294491637031994357741746928793608969561760}^{A_{60}^{18} = 16991872114526357377832602307286644766060020160}^{A_{61}^{18} = 883153875916679200824308045231692663084215252606960}^{A_{62}^{18} = 41235857517984555417125494178003297994637730835282021600}^{A_{63}^{18} = 1719181014229697928550610723912656541514431874535650095049840}^{A_{64}^{18} = 63437583041281769529506728331921094069086081087366311606734599715}^{A_{65}^{18} = 2047734190087446156226619336717829362574563088117977106772182932353440}^{A_{66}^{18} = 56947146431648042555284114475173533510040271560465073966856530321990843520}^{A_{67}^{18} = 1337025481114032804475407227912070643719333896897402714590595228271479469161760}^{A_{68}^{18} = 25773033739728957466090285585751484952239752000452490075248549223383319255973025920}^{A_{69}^{18} = 391676899706127013929640460362950859336670545531213587469157046725259559288883299918920}^{A_{70}^{18} = 4400439592836837299246023837545459158635871405367790475261082954710874322561885273696843440}^{A_{71}^{18} = 32494457316844752298076258429576263703774764892173813459037207008732793326399448966741347425480}^{A_{72}^{18} = 118308708473155269143397725363882277259301381884130516531324599186219552091966687573978561521721500}^{A_{54}^{19} = 384767460}^{A_{55}^{19} = 13574257257634920}^{A_{56}^{19} = 4316206916914350046380}^{A_{57}^{19} = 846886496449285260356087040}

41

A_{58}^{19} = 131233166977718046462446926047600^{A_{59}^{19} = 17414637704801820936631501490357356320}^{A_{60}^{19} = 2042031288996709121057764826604429828234240}^{A_{61}^{19} = 213954556825326687015667926161154093640360076160}^{A_{62}^{19} = 20058455043744581476101383609751327099066200223761880}^{A_{63}^{19} = 1675813186831380943456808190917907739002715900630197527600}^{A_{64}^{19} = 123795878807600707307440810319393871453070674355820642453803155}^{A_{65}^{19} = 7996062460977456467892397150554581634041075528321961532379112284160}^{A_{66}^{19} = 444847808116364032687377195597980218086416295591279898660806284876131440}^{A_{67}^{19} = 20891182380925593819234824942951053265676087818348503044342559215487248051360}^{A_{68}^{19} = 805464144296283149963944417065653745157738116758483751382579578660879181446345600}^{A_{69}^{19} = 24482327701704645379861600978300646757824190363649601336301075270215315143208155347840}^{A_{70}^{19} = 550121049456142694540804092824457463039087484159955274973975043170152032668212699144161380}^{A_{71}^{19} = 8124668030867761175493346519394193672775568892371150395514245480042371731236933254379668840360}^{A_{72}^{19} = 59162365588290038169002475595445183255308173092215076405922725794471995564584722587245822485012180}^{A_{55}^{20} = 13991544}^{A_{56}^{20} = 4116828755139210}^{A_{57}^{20} = 2423095728924282545760}^{A_{58}^{20} = 876125201411206748940166800}^{A_{59}^{20} = 249132645773956065096294312470400}^{A_{60}^{20} = 60373928711899357166115488370776253864}^{A_{61}^{20} = 12855466935359326733412979662187747242762720}^{A_{62}^{20} = 2429558609423662256153967965565013819100016795120}^{A_{63}^{20} = 407560773638120830432182276682869813750267376837348400}^{A_{64}^{20} = 60332885353747115256639703916764423504767542486653695702375}^{A_{65}^{20} = 7801520140136982410773959180903464522826423028907298435900497184}^{A_{66}^{20} = 868474625815693886589642068437345973569656109416851619631668662596080}^{A_{67}^{20} = 81591548827415604283291460517070570249601961602450727858618564013861519680}^{A_{68}^{20} = 6292334521624135504056733679163987077407503895228538269661654631512658991108200}^{A_{69}^{20} = 382538558559786908366159620988199617590593109278610028977498671506309947031037386400}^{A_{70}^{20} = 17191922201551296946518243693371987771220599732236378317275013023571410496010973434667664}^{A_{71}^{20} = 507818871649045277137743892531559339004807871879265361952440021302382025712661148215752870040}^{A_{72}^{20} = 7395754138992062767165073548024989279036655414231847889717712633092017708102568224224186795595410}^{A_{56}^{21} = 249849}^{A_{57}^{21} = 1155454037311920}^{A_{58}^{21} = 1253342414351456000280}^{A_{59}^{21} = 831593711629646072913592080}^{A_{60}^{21} = 431840549770885657380316677169740}^{A_{61}^{21} = 190034512033664652674144671680143310000}^{A_{62}^{21} = 72987933430548113778873059230321635511170216}^{A_{63}^{21} = 24681948601782709462798632222776706930368480508560}^{A_{64}^{21} = 7336312588942781029178877652684396433834734422473374785}^{A_{65}^{21} = 1901007774469869451492941803338030657122180265578389984202384}^{A_{66}^{21} = 423659289812754351626523310378051584332740109457096029436165094824}^{A_{67}^{21} = 79642923395455817476522802592633904845542678453505245985611012739481776}^{A_{68}^{21} = 12287119705186101373602247311798665937572373207577164033222701773452990985740}^{A_{69}^{21} = 1494158707905644163319152654253046264157869423103703516968503414581351822280340240}^{A_{70}^{21} = 134308241442925257842455305756017932523251311927455723328985345845608694256324607454744}^{A_{71}^{21} = 7934700134435878836803084652541750287234936131259378422913302029253174371234965973816624560}^{A_{72}^{21} = 231121835284777594218855048972987718277278310423314110893791759777383698164381844279451258558337}^{A_{58}^{22} = 298824321028320}

42

A_{59}^{22} = 594810682155739042560^{A_{60}^{22} = 720722153715960241404009360}^{A_{61}^{22} = 679626421233088297530861028154880}^{A_{62}^{22} = 539460163619348009370967813245123472416}^{A_{63}^{22} = 370737669218995290083738328766314722100829440}^{A_{64}^{22} = 222140821896565637575344265656888306297475297705515}^{A_{65}^{22} = 115576889635959843004105607031405291101815909909094461440}^{A_{66}^{22} = 51616038165707818604575677452179944869536268129017593003114528}^{A_{67}^{22} = 19425399673106467616261561281351231423026565802847758813299382546688}^{A_{68}^{22} = 5996739341801833254394502799238819699716186522429063866167915524084701520}^{A_{69}^{22} = 1458807474274935694248129189661888570951667979871963305802487494967448601489920}^{A_{70}^{22} = 262293202477786767915228435310314911360247931388743671982896823329387253859888407776}^{A_{71}^{22} = 30993562655595250684084192315862416382973105089564202967667861412021536780860502900776704}^{A_{72}^{22} = 1805615660099799480678377543995155866286673312952856452476682325361880846652010900891809063048}^{A_{59}^{23} = 70907466006720}^{A_{60}^{23} = 257752202034594037680}^{A_{61}^{23} = 567128671469266235025191040}^{A_{62}^{23} = 964637187271445621561210667564480}^{A_{63}^{23} = 1370067051623001214368046118674792595520}^{A_{64}^{23} = 1668331649381212214710316799778759304872697355}^{A_{65}^{23} = 1749799307595981303431361322399826099996026884768000}^{A_{66}^{23} = 1569055898022959582391861068325862169487550137176286794880}^{A_{67}^{23} = 1183326208451856065567822523424297219779222605525102438914123584}^{A_{68}^{23} = 731314993762926869281687982061476092598790571255070643647455064570160}^{A_{69}^{23} = 355983235665301246921672306141218063791685737048505127574592174050016282240}^{A_{70}^{23} = 128042668716808741402719295208229716872299993582219489257739403751835102167739840}^{A_{71}^{23} = 30263716064760017255210031753637537337305748737891555684390998966529565863207816462272}^{A_{72}^{23} = 3526408527632137907192496430987527549817601918166775464693608229569926436720097112958762664}^{A_{60}^{24} = 15363284301456}^{A_{61}^{24} = 101410883776966458240}^{A_{62}^{24} = 402479509536933710964001920}^{A_{63}^{24} = 1224940071724941735103512403145600}^{A_{64}^{24} = 3082661718337655095313351385199012513995}^{A_{65}^{24} = 6570684316332491611646511428899742774136285696}^{A_{66}^{24} = 11877470900891506544000753226591760128252098775089280}^{A_{67}^{24} = 17985666166434936407014876845922346782352291237739025213440}^{A_{68}^{24} = 22274464294187982917454699968087160477342780767918297230530727440}^{A_{69}^{24} = 21706364722734954590825880701863936589013405925361475113864697590252160}^{A_{70}^{24} = 15622642759603072389961907160242716412744410064104796821287090195243960377856}^{A_{71}^{24} = 7386830397599179405305844437539147469225746695414990937783319107993006642618002560}^{A_{72}^{24} = 1721676464793356621161715318290305354795049188795204288082316098435741951465188883835176}^{A_{61}^{25} = 3022285436352}^{A_{62}^{25} = 35984539855593385056}^{A_{63}^{25} = 255542899871141573632061120}^{A_{64}^{25} = 1378059844639369297327302184026795}^{A_{65}^{25} = 6070483161742780561969328853572357845248}^{A_{66}^{25} = 22300546195846170183101713089951783230283831168}^{A_{67}^{25} = 68073994879855908408998019500164984822904598995587584}^{A_{68}^{25} = 169277193401243625371989610389769324899893520427783229191040}^{A_{69}^{25} = 330566630153615798530535038522231019057820395322264414149476418880}^{A_{70}^{25} = 476300637733489528581152795309074569926757123049671665290624066329698976}

43

A_{71}^{25} = 450637169770252784461655810642696029489430742230783725703397951289987366234944^{A_{72}^{25} = 210114731242900445669191776227735398929809650224403244319102449183461598303399669992}^{A_{62}^{26} = 536211932256}^{A_{63}^{26} = 11423668723226439680}^{A_{64}^{26} = 143742982384058854513351635}^{A_{65}^{26} = 1356860056204626258313938304992960}^{A_{66}^{26} = 10301435325549384980023245134493634623456}^{A_{67}^{26} = 63906103715955245958961737997262837332643204928}^{A_{68}^{26} = 320348526030712310558843008602968463997834034293357680}^{A_{69}^{26} = 1256087103712942021279932667433866746008751885481624671670080}^{A_{70}^{26} = 3626791885255381424209226617138549544452069177675727293829008128768}^{A_{71}^{26} = 6869469870277425395453042962839815435697833172794724311330204957907261120}^{A_{72}^{26} = 6409068744122857856120010263013527236791953146280100898021270419908460285743632}^{A_{63}^{27} = 85113005120}^{A_{64}^{27} = 3212907582455465895}^{A_{65}^{27} = 70765801250744192697387360}^{A_{66}^{27} = 1151275687058983060973498185137360}^{A_{67}^{27} = 14760272345639051315407932428261666561568}^{A_{68}^{27} = 150367375577101990878630478403539285621926891240}^{A_{69}^{27} = 1188540051648965494113817895237600007847921318069702560}^{A_{70}^{27} = 6890538483621415394685790708206371345765953408784619850326480}^{A_{71}^{27} = 26153780421491506597795603793530083337777166470215471441231813003936}^{A_{72}^{27} = 48849589312499574871626141593375345932676699295912895852595530922711656036}^{A_{64}^{28} = 11969016345}^{A_{65}^{28} = 790869653037289584}^{A_{66}^{28} = 30021860528280425439641160}^{A_{67}^{28} = 824794699514729501324520716996880}^{A_{68}^{28} = 17365030352313510603336673070018042863380}^{A_{69}^{28} = 278942446335605189120732454037106056803642900240}^{A_{70}^{28} = 3259996395109724020118515034055203624965270667207730504}^{A_{71}^{28} = 24844764904317181905905028952088885958618809694615361611519600}^{A_{72}^{28} = 92991243776109801330933044962995602584482340533370848828042067783638}^{A_{65}^{29} = 1473109704}^{A_{66}^{29} = 167760239587681356}^{A_{67}^{29} = 10754100285250493678782968}^{A_{68}^{29} = 485173405635479551900917214591230}^{A_{69}^{29} = 16106696732104692843724862597286619453560}^{A_{70}^{29} = 382549688318630339293134860142522838754859526860}^{A_{71}^{29} = 5877177353957714156300364040693775490298389029001828168}^{A_{72}^{29} = 44168476736557842173284414737652738964785924854544892650432509}^{A_{66}^{30} = 156238908}^{A_{67}^{30} = 30046610998847520}^{A_{68}^{30} = 3162970820156241228133230}^{A_{69}^{30} = 225007968705266501624605825024320}^{A_{70}^{30} = 11044592710252478399955496406370814096668}^{A_{71}^{30} = 344833543642750346105055568743354072701556509088}^{A_{72}^{30} = 5224157988006590715514217776937286064546419583814819661}^{A_{67}^{31} = 13991544}^{A_{68}^{31} = 4418619333465330}^{A_{69}^{31} = 733442526440062448961840}^{A_{70}^{31} = 77145591439271388704096972230920}

44

A_{71}^{31} = 4977844753921999415126317357027735827096^{A_{72}^{31} = 153259357638819211161560924059620517872586611225}^{A_{68}^{32} = 1028790}^{A_{69}^{32} = 512303694892080}^{A_{70}^{32} = 125733006047537340149376}^{A_{71}^{32} = 17384922262407929012308656532080}^{A_{72}^{32} = 1106187740237242534328800688995825752093}^{A_{69}^{33} = 59640}^{A_{70}^{33} = 43911745452828}^{A_{71}^{33} = 14167099359548493975288}^{A_{72}^{33} = 1931658043126770604897085373879}^{A_{70}^{34} = 2556}^{A_{71}^{34} = 2473901157312}^{A_{72}^{34} = 787061077970013304047}^{A_{71}^{35} = 72}^{A_{72}^{35} = 68719476663}^{A_{72}^{36} = 1}

45

46

Bibliography

[Aig79] Martin Aigner. Combinatorial Theory. Springer-Verlag, 1979.

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

[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(6):2047–2054, 1997.

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

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

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

[CK01] Wende Chen and Torleiv Kløve. On the second greedy weight for linear codes of dimension 3. Discrete Math., 2001. To appear.

[DG01] Steven Dougherty and Aaron Gulliver. Higher weights of selfdual codes. In Daniel Augot, editor, Workshop on Coding and Cryptography, January 2001.

47

[Dou01] Steven Dougherty. Does there exist a [72,36,16] Type II code?,

2001. http://academic.scranton.edu/faculty/doughertys1/
72.htm.

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

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

[FKLT93] T Fujiwara, T Kasami, S Lin, and T Takata. 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.

[For94a] G. David Forney, Jr. Density/length profiles and trellis complexity of lattices. IEEE Trans. Inform. Theory, 40(6):1753–1772, 1994.

[For94b] G. David Forney, Jr. Dimension/length profiles and trellis complexity of linear block codes. IEEE Trans. Inform. Theory, 40(6):1741–1752, 1994.

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

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

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

[Sch00a] Hans Georg Schaathun. Upper bounds on weight hierarchies of extremal non-chain codes. Discrete Math., 2000. To appear in the Tverberg Anniversary Volume.

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

[Sch01] Hans Georg Schaathun. Duality and greedy weights for linear codes and projective multisets. Springer Lecture Notes in Computer Science. Springer-Verlag, 2001. Proceedings of AAECC-14.

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

48

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

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

49