THE UMQJUENESS C’F TEE NGRDSTROM - ROBiNSON AND THE GOLAY EMMY CODES Thesis for the Degree of Ph. D. Mimi-mm STATE UNIVERSEW STEPHEN LEE SNOVER 1973' ¢ h"% . VJ 5 r .A T . J t ." -" 1 t . - “5‘1“ 69453 If .r r . _ Valve-racy This is to certify that the thesis entitled The Uniqueness of the Nordstrom-Robinson and Golay Binary Codes presented by Stephen Lee Snover has been accepted towards fulfillment of the requirements for Ph. D. dggree in Mathematics at. “M. 'KM‘L Major professor Date Q10»: [7. I 1 73_ 0-7 639 mm; & sales 1 roux amnm me. . new? muons 1. ABSTRACT THE UNIQUENESS OF THE NORDSTROM—ROBINSON AND THE GOLAY BINARY CODES BY Stephen Lee Snover In this thesis a code is considered to be any collection of vectors in V(n,2), the vector space of n-dimensions over GF(2) . Two codes are considered to be equivalent if one can be obtained from the other by (a) a translation, i.e. adding a fixed vector of V(n,2) to each code vector and/or (b) a permutation of the n fixed basis vectors of V(n,2), i.e. the n coordinate positions of all the vectors. The notation (n,M,d) refers to a code of M vectors chosen from V(n,2) so that the minimum Hamming distance between any pair of code vectors is d It is shown in this thesis that the codes given by the notation (15,256,5) , (16,256,6) , (23,212,7) , and (24,212,8) are unique up to equivalence, and are the Nordstrom-Robinson code, its parity check extension code, the Golay binary code, and its extension, resp. Note that the uniqueness of the Golay code is proved without assuming linearity. The key to the uniqueness proof lies in the fact that the minimun non-zero weight vectors in each of these codes are elements in a t-design: the sets of weight 5 and 6 Stephen Lee Snover vectors in the Nordstrom-Robinson code and its extension give rise to 4—(2,5,15) and 4—(3,6,l6) designs while the sets of weight 7 and 8 code vectors in the Golay code and its extension form S(4,7,23) and S(5,8,24) Steiner systems. After discussing a new tool for the analysis of t-designs, called generalized block intersection numbers and a new definition, t-designs with d;;d i.e. t-designs which can 0’ be embedded in codes with minimum distance do, it is shown that the structure of each of these designs fixes the structure of the corresponding code. It follows that the proof of the uniqueness of the code up to an equivalence is reduced to showing that the corresponding minimum weight vector t—design is unique up to a permutation of the n coordinate positions. The 4—(3,6,16) design with d;z6 generated by the weight 6 vectors in the extended Nordstrom—Robinson (l6,256,6) code is called the XNR-design and plays a fundamental role in showing the uniqueness of all the designs in question. In the first place, the XNR—design is shown to be unique by showing that any such design may always be embedded in V(4,2) and then by showing that within V(4,2) the design can only be constructed in one way, up to an automorphism of V(4,2) . Since the constructive proof of the XNR—design within V(4,2) actually involves PG(3,2) , the uniqueness of both the Nordstrom-Robinson code and its extension follows. T. S 2 n4. . i n e r... a. r1. 9 .1. fil. G. I. .. s ”a 6 1RD 4 . .n s I .1. ”I n «L vi 6 A: o _ v a f y .. . .lu .: 0 . ‘ a gay n" nu A 1 :a . n r». nun . ‘ A . .P s .5. n h ed .‘rq' WE e1. 1 L." :~~tra In 6‘. "15 t “’9’! 'n a I‘ a Stephen Lee Snover From the uniqueness of the XNR—design, it is also possible to conclude the uniqueness of the S(4,7,23) Steiner system. Both the generalized block intersection numbers and the fact that a subgroup isomorphic to A7 of PSL(4,2) is l-transitive on lines of PG(3,2) aid in showing that the XNR—design builds the S(4,7,23) design uniquely, up to an arbitrary permutation of the 7 added coordinates. Witt [40] proved the uniqueness of S(4,7,23) based on the geometry of PG(2,S), while the same result is proved here based on PG(3,2) and the fact that the XNR— design is unique within this geometry.) Finally, from the uniqueness of S(4,7,23), the uniqueness of S(5,8,24) and of the Golay code and its extension, up to equivalence, follow. Because these proofs proceed from the XNR-design, it is actually shown that the extended Nordstrom-Robinson code extends to the Golay binary code uniquely, up to an arbitrary permutation of the added coordinates. In order to tackle the coding theory problem basic to this thesis, concepts from t-designs, the finite geometries of V(n,2) and PG(n—l,2), and permutation and automorphism groups are used. In particular, it is shown that A -+T(4), 7 i.e. A7 extended by the elementary abelian group of order 16, is the automorphism group of both the XNR-design and the extended Nordstrom-Rdbinson code. Some graph theory is also used in establishing what appears to be a new proof of the classical isomorphism, A8 a PSL(4,2) . While this thesis [5 39" r.“ .‘L Cu F; . “Iv-n .8. t5 .sslic Post he rm 3 no. v- \ on Stephen Lee Snover offers new definitions, proofs, or results for each of these topics in finite mathematics, the major contribution lies in the application of t—designs to the study of non-linear codes. In fact, it is the concept of the generalized block intersection numbers for t-designs, yielding necessary conditions for the building and extension of t-designs, Which is most helpful in the analysis of non-linear codes and their designs. THE UNIQUENESS OF THE NORDSTROM-ROBINSON AND THE GOLAY BINARY CODES BY Stephen Lee Snover A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1973 DEDICATION To my parents, without whose stimulus I might not have gone so far, and To my loving wife, Ans, for her support. ii ACKNOWLEDGMENT S Many thanks go to Professor J. J. Seidel for his fine teaching, good example, and patient guidance; Professor J. M. Goethals for his stimulating discussions and above all for suggesting the topic of this thesis; Professor L. M. Kelly for his thorough reading, suggested changes, and administrative assistance; Professor W. Jonsson for suggestions on the structure of Chapters 9 and 11; The Michigan State University Mathematics Department and the Technical University of Eindhoven Mathematics Department for their financial support; Annerie 't Hart-Wustefeld and Sue Stewart for their fine typing. iii ».l ‘fiL- ».. TABLE OF CONTENTS Page PART A: INTRODUCTION . . . . . . . . . . . . . . . . 1.1 Chapter 1. Introduction . . . . . . . . . . . . . 1.1 Section 1.1 Heuristic Introduction . . . . . 1.1 Section 1.2 History of the Fundamental Questions in this Thesis . . . . 1.5 Section 1.3 Scope of this Thesis . 1.8 Section 1.4 Organization Scheme of the Chapters . . . . . . . . . . . . 1.10 PART B: PRELIMINARIES . . . . . . . . . . . . . 2.1 Chapter 2. Binary Codes: Basic Definitions and Properties . . . . . . . . . . . . . . . . . . 2.1 Section 2.1 Introduction . . . . . . . . . 2.1 Section 2.2 Binary Vector Spaces . . . . . . 2.2 Section 2.3 Binary Codes . . . . . . . . . . 2.4 Section 2.4 Incidence Matrices . . . . . 2.5 Section 2.5 Modifications of Codes . . . . 2.5 Section 2.6 Geometric Codes . . . . . . . . 2.8 Chapter 3. Definitions and Existence of the Golay and the Nordstrom-Robinson Binary Codes 3.1 Section 3.1 Introduction . , 3.1 Section 3.2 Perfect Codes . . . 3.3 Section 3.3 Definition of the Golay Code . 3.4 Section 3.4 Nearly Perfect Codes . . . . . 3.7 Section 3.5 Definition of the Nordstrom- Robinson Code . . . . . . . . . 3.10 Chapter 4. t-Designs and Generalized Block Intersection Numbers . . . . . . . . . . . 4.1 Section 4.1 Main Definitions . . . . . . . . 4.1 Section 4.2 Examples . . . . . 4.3 Section 4.3 An Application of t- -Designs to Binary Codes . . . . . . . 4.6 iv f7 PART C: Section Section Section Section Chapter 5. 4. 4. 7 Block Intersection Numbers bi j 1’ Motivation for the Generalized Block Intersection Numbers Using the Design of the Thirty 3-Cubes in the 4—Cube . . . . . . . . Generalized Block Intersection Numbers . . t-Designs with dzdc.) Automorphism Groups and an Explicit Construction of the XNR-Design Section 5.1 Section 5.2 Section 5.3 Chapter 6. Section Section Section Section Section Section Chapter 7. Code by Section Section Section Section Section \l\l\l 6. 6. 6 Permutation Groups . . . . . . . Automorphism Groups . . Application and Examples THE NORDSTROM-ROBINSON CODE . . . . . . Equivalence of the Uniqueness of the XNR Code and the Uniqueness of the XNR-Design . 1 2 3 .4 .5 .6 Introduction . . . . . Organization of Chapter . . . Fundamental XNR-Design of Weight 6 Code WOrds in any (16, 256, 6) Code C with 06C . . . . . Weight Distribution of Any (16, 256,6) Code C with QGC . Each XNR-Design Builds a (16,256,6) Code in Just One Way Conclusion . . . . . . . . . . . Coordination of the XNR (16, 256,6) V(4’ 2) o o o o o o o o o o c .1 .2 .3 Introduction . . . Coherent 4- -Tup1e Vectors . . 3— (3, 8, 16) Design with d28 the Weight 8 Vectors of XNR (l6,256,6) and the Reed-Muller Code 3- with Parameters (16,32,8) Linearity and Uniqueness of the Reed-Muller (16,32,8) Code fl Contained in SNR (l6,256,6) . Coordinatization of XNR by Points of V(4,2) . . . . . '03: Page 4. U1U'1U'1 (DOW CDO‘O‘O‘ 8 .11 .18 .22 WNW Page Chapter 8. Coordinates for Lines of PG(3,2) . . . 8.1 Section 8.1 Introduction . . . . . . . . . . 8.1 Section 8.2 Finding PG(5,2) Within V(8,2) 8.2 Section 8.3 The Klein Quadric . . . . . . . . 8.3 Section 8.4 Graph Theory Definitions . . . . . 8.4 Section 8.5 Graphs G and H and Their Maximal Cliques . . . . . . . 8.5 Section 8.6 58 =- Aut (G) =>- 56(+,2) .1 Aut(H) 8.8 Section 8.7 S8 is 1—Transitive and A8 is %-—Transitive On the 30 Maximal Cliques of Graph G . . 8.11 Section 8.8 Finding PG(3, 2) Within the Klein Quadric K . . . . . . . . . . 8.17 Section 8.9 Eight Objects in PG(5,2) Permuted by PSL(4,2) 3 A8 . . . . 8.23 Section 8.10 Line Coordinates for PG(3,2) and 8 Objects in PG(3,2) Permuted by PSL(4,2) . . . . . . . . . . . . . 8.24 Chapter 9. The Uniqueness of the XNR—Design Within the Geometry of V(4,2) . . . . . . . . . . . . 9.1 Section 9.1 Introduction . . . . . . . . . . 9.1 Section 9.2 Necessary Conditions for the Existence of an XNR-Design: Designs S and L and Correspondence 5 . 9.2 Section 9.3 The Uniqueness Under A8 of Correspondence 3 and Design L 9.6 Section 9.4 The Uniqueness of the Design Pair S, L . . . . . . . . . . . . . 9.10 Section 9.5 The Uniqueness of the XNR-Design D . . . . . . . . . . . . . . . . 9.14 Chapter 10. The Uniqueness of the Nordstrom-Robinson and the Extended Nordstrom-Robinson Binary Codes 10.1 Section 10.1 Introduction . . . . . . . . . . 10.1 Section 10.2 The Uniqueness of the XNR (16, 256, 6) Code . . . . . . . . . 10.1 Section 10.3 The Uniqueness of the NR (15,256,5) Code . . . . . . . . . 10.2 Section 10.4 Non-Linearity of the NR and XNR Codes . . . . . . . . . . . . . . 10.3 vi ”.5- v- ,— .....~ I! 0‘ "- -.a.n PART D: THE GOLAY BINARY CODE Chapter 11. The Uniqueness of the Large Steiner Systems S(4,7,23) and 8 Section 11. Section 11. Section 11. 1 2 3 Introduction . The Uniquene Page Based On the Uniqueness of the XNR-Design The Uniquene Chapter 12. The Uniqueness of the GOLAY (23,2 12 and XGOLAY (24,2 ,8) Co Section 12. Section 12. Section 12. Section 12. Bibliography . . 1 2 Introduction Weight Distr (24,212,8) Designs S(4, Build (23,212, Codes, Respe The Uniquene (23,212,7) Binary Codes vii 11.1 (5,8,24) 11.1 o 11.]. ss of. S(4, 7 ,23) o o o o 11.2 $3 of S(S, 8, 24) . . . 11.12 12,7) des . . 12.1 . . 12.1 ibution. of Any Code . . . . . . . . . 12.1 7,23) and S(5,8,24) 7) and (24,212,8) ctively, in One Way . 12.7 ss of the GOLAY and XGOLAY (24,212,8) . . . . . . . . 12.14 B.l,B.2,B.3 All equation out this in Secti the chap position is disca necessar in the s r‘éferreé originat Numbering and Notation All the theorems, corollaries, lemmas, and important equations and remarks are numbered consecutively through- out this thesis with a three position label. For example, theorem (6.5.9) is the ninth item worth labelling in Section 5 of Chapter 6. If an item is referred to in the chapter in which the item originally appears, a two position reference number is given; the chapter number is discarded in this case because it is not really necessary and because then the fact that this item occurs in the same chapter will be emphasized. If an item is referred to in a different chapter from where it originates, the entire three position reference number is used. For example, within Chapter 6, Theorem (6.5.9) is referred to as Theorem (5.9), and in other chapters, the same theorem is referred to as Theorem (6.5.9). In various places throughout this thesis the following notation shall be used: := means "is defined to be" . |X| means the cardinality of set X . X‘\Y means the set difference of X and Y, i.e. X\\Y := the set of elements in X but not Y . XZSY means the symmetric difference of sets X and Y , i.e. XAY := (X\Y)L_)(Y\X) . PSL(n,2) 06(+,2) is the map m with its domain restricted to the set 5 mean the symmetric and alternating groups on n letters. are notations used for certain classical simple groups by E. Artin in [1]. PART A: INTRODUCTION CHAPTER 1 §1.l Heuristic Introduction In all forms of human communication messages are sent by means of codes. We naturally code our ideas into English phrases and sentences. English is a prototype for the kind of code we wish to discuss, as it is a code involving an agreed upon alphabet, a dictionary of code words which are meaningful sequences of letters from this alphabet, and messages being sentences or special sequences of words. we should note that not all sequences of letters form words, nor all sequences of words, messages. Some codes, those commonly used during war times, are designed to disguise messages so that no one but the intended receiver can understand the message properly. Such codes arecalled minimum decodable. We will be concerned, however, with more common and very different types of codes -- maximum decodable or error correcting codes. These codes are designed to send messages in a way that even errors in transmission do not change or destroy the intended meaning of the message. Errors in speaking or writing English, i.e. mispro- nunciations or misspellings, are most often detected 1.1 because Le send all ch risunc‘er Err followin 50 that j 35 messac Ember 01 5°59 wort praCiice the end ( than a ti (as in Aw 50‘“ 1 led Tech some“. in the alpha: f A be because the resulting "words" are meaningless sequences of letters (words that are not in the code). Such errors can then be corrected either from context or by asking the sender to repeat the message. Sometimes, however, small changes in Spellings or pronunciations cause misunderstandings. Error correcting codes are designed with the following desirable features: (1) The alphabet is simple; there are few symbols. (2) There are enough words to convey any message, so that it is not necessary to rely upon context or repeats of messages in order to correct transmissional errors: (3) words are not too "close" together, i.e. the number of letters that need to be changed to convert a code word into another is relatively large. Finally, in practice it is important to be able to distinguish between the end of one word and the beginning of the next by other than a time lapse (as in English) or a punctuation mark (as in Amharic, the Ethiopian language). Therefore, the so-called fixed block length codes require that (4) words all are of a fixed length of n letters. Technically we may describe a fixed block length error correcting code as follows: Let A := [0,1,2,...,k-—l} be the alphabet and S := the cartesian product of n copies of A be the code space. A code C in the code space S is a subset of S . Each element x in C is called a 1.3 "word" of C and ‘x := (xl,x2,...,xn), where xi is the i-th letter of the code word x,. A reasonable measure of distance between two words is the number of places in which their corresponding i-th letters differ. This is the historical definition of the "Hamming distance" between words. A code C is often specified by the four parameters (k,n,M,d) where k is the cardinality of the alphabet, n is the length of each word, M is the number of code words in code C , and d is the minimum distance between any pair of code words from C . These parameters corre- spond directly to the four features of an error correcting code. In this thesis, only the case of alphabets of two letters is considered. we therefore shorten the parameters for a code the (n,M,d) with k = 2 being understood. Parameter 6 needs more explanation to make clear the correspondence between 6 and the ability to correct transmission errors in received words without relying upon context or repeats. In the example of English, the minimum distance is 1 since the words "step" and "stop" differ only in one place. If "step" is sent and "stop" received, you might not be able to even detect the error, let alone be able to correct it. If English were refined so that no two words in the dictionary differed by only one letter, then the minimum distance would still be small, namely 2, as exhibited by the pair of words "sign" and "sing". In general we would like a code to have a relatively high minimum distance d so that such minor changes would not go unnoticed. Although any subset of a code space S is a code, not every one is "good". Most codes with many words are like English in that the minimum distance between some pairs of words equals 1 . "Good" codes have a maximum number of code words relative to their parameter values of n and d Thus, a fundamental problem in coding theory is the deter- mination of the largest possible code and its "structure" that can be selected in a given code space if the minimum distance between code words is Specified. In a way, the search for "good" codes amounts to a search for sphere packings in given code spaces. Because the Hamming distance is a legitimate distance function which satisfies the triangle inequality, the spheres of radius e about each code word in a (n,M,d) code are disjoint spheres, When e = [(d-d)/Q]. Codes having the property that the spheres of radius e pack the code space are so "good" that they are called perfect. All perfect codes are known (for k being any prime power) and nearly-perfect and quasi—perfect codes are the topic of much current study. cover of alphabet vector 5; issediate ifipcsed r about the St‘ldy of Code EVen h u! the N0 8. Aubry C .: in C and s. If k (the number of letters in the alphabet) is a power of a prime,field properties may be imposed upon the alphabet so that the code space S has the structure of a vector space Where, if .5 = (x1,x2,...,xn) and X_= (Y1,Y2,...,yn) are any two vectors in S , then 95.41 = (x1 ”rs/1.x2 +y2,.. .,xn +yn) and xx = (xly1,x2y2,...,xnyn), the component-wise operations being performed in GF(k). These Operations have no immediate intuitive interpretations, however, and are imposed merely in order to apply What is already known about the algebra and geometry of vector spaces to the study of codes. Codes having the property that they are subspaces of their code vector space are called linear; more is known about this kind of code than any other. Unfortunately, linear codes are not in general as "good" as other non-linear codes. One of the major accomplishments of this thesis is the presentation of a new method of handling some non-linear, "good" codes. §l.2 The History 2: the Fundamental Questions ig_this Thesis Even before the discovery of either the Golay (23,212 or the Nordstrom-Robinson (15,28,S) binary codes, the ,7) history of their uniqueness began. In 1927 Witt [39] and [40], in an effort to establish the uniqueness of the 4- and M and S- trans1t1ve Math1eu groups M23 24 demonstrated the uniqueness of the Steiner systems, S(4,7,23) and S(5,8,24), on Which these groups operate as automorphism groups. Then shortly after Golay discovered his (23,212,7) code Paige [29] showed that 12,7) code possesses a S(4,7,23) as its set of any (23,2 weight 7 code vectors. Since Golay defined his code to be linear, Paige could then display 12 linearly independent weight 7 vectors in the S(4,7,23), which was already shown to be unique by Witt, and claim that M23 is also the automorphism group of Golay's code. Pless [31] reproduced Paige's arguments and extended 12,7) or (24,212,8) them to showing that any linear (23,2 binary code contains S(4,7,23) or S(5,8,24) Steiner system as its set of non-zero minimal weight code vectors and possesses the automorphism group M23 or M24 , respectively. prever, both Paige and Pless relied on Golay's original definition of the linearity of his code in order to establish the facts about the automorphism groups and uniqueness, in spite of the fact that they showed that an arbitrary code with the right parameters would contain the appropriate Steiner system. This brings up the following question: Qgestion #1: Is the uniqueness of the S(4,7,23) and the S(5,8,24) systems sufficient to imply the 12 l uniqueness of the (23,2 ,7) and (24,2 2,8) binary codes without the restriction of linearity? CnA grOUp L Lhe G1 in th- 1.7 If the answer be affirmative, then clearly by quoting Pless, Paige, and‘Witt, the unique codes of those parameters would also possess the automorphism groups, M23 and M24 Golay's codes have the maximum number of possible code vectors relative to their lengths and distances, a property also shared by Nordstrom and Robinson's (15,28,S) and (16,28,6) non-linear codes. When analyzing Golay's (24,21 2,8) code, J. M. Goethals [15] noticed that this code contained a (16,28,6) non-linear code in a special way, and from this construction, he was able to find the automorphism group of this code. Although he never established a correspondence between Nordstrom-Robinson's (16,28,6) code and his, Goethals was privately convinced that they were the same and that perhaps the code in question was unique. 80 it was Goethals Who inspired the following: Qpestion #2: Are the (15,28,5) and (16,28,6) Nordstrom-Robinson codes unique? Question #3: Are the automorphism groups of these codes A7 and A7 extended by the elementary abelian group of order 16, respectively? Question #4: Does the (16,28,6) code extend to l the Golay (24,2 2,8) code in essentially one way? These four questions are all answered affirmatively in this thesis. All the definitions, developments, and proofs to these questions are completely self—contained . J 1‘ . . -4 .1. .2 .1 Nu. flu. .fi 74 v u .. h» S e u e -l s be a... 2 A c . . . .J a: mu 3. an” n. a :1 Ru 1 . : t n . D... .C q 8. t uh ..w my .9. Arie .- , ?.... h s 1.8 herein, and the results of all but Question #3 are new. §1.3 The Scope 2£_this Thesis Although the basic and most difficult theorems in this thesis show the uniqueness of the Nordstrom-Robinson (15,28,5) and (16,28,6) and the Golay (23,21 1 2,7) and (24,2 2,8) binary codes, this is certainly not the only new nor important concept. In a manner similar to Paige's analysis of the Golay 12,7) code [29], we proceed toward answering the (23,2 four basic questions of the thesis by showing that the minimal weight non—zero code words in the Nordstrom- Robinson (16,28,6) code form a t-design, a 4-(3,6,l6) design with d216, which we call an XNR-design. Then the question of the uniqueness of this code is found to be equivalent to the uniqueness of the XNR-design. While the uniqueness of the S(4,7,23) design of minimal weight non-zero code vectors in the Golay (23,212 ,7) code was proved to be unique by Witt even before the discovery of the code, neither the existence nor the uniqueness of the XNR-design seem to have previously been known. Thus it is, that t—designs become basic in the analysis leading to the uniqueness proofs of this thesis. To the theory of t-designs, we unveil a new definition, t-designs with dZLdO: and a new tool, generalized block intersection numbers for any t-design. Us“ 51-01 n... .i... a e "W The extra condition, d;:do, for any t-design enables one to distinguish among those t-designs which might be useful for binary coding theory purposes and the rest. The generalized block intersection numbers, a link between Mendelsohn's intersection numbers [25] and J. M. Goethal's block intersection numbers [16], become fundamental to the analysis, being essential in Chapters 5, 6, 7, 11, and 12. First of all, they are helpful in proving that the uniqueness of the codes is equivalent to the uniqueness of the t-designs of the minimal non-zero weight vectors of those codes. These numbers prove that the S(5,8,24) design can be built in essentially one way from the XNR-design. 12,8) With these numbers, we can deduce that any (24,2 code is necessarily the linear span of the S(5,8,24) design formed by its minimal weight non-zero code vectors. In fact, these new generalized intersection numbers are just the tool necessary to tackle these codes without assuming any linearity. Permutation groups come into play in order to establish a new construction of the important XNR-design, perhaps the first direct explicit construction. Constructing this design to contain the group A7 extended by the elementary abelian group of order 16, it is then possible to conclude at a later time that this group is the automorphism group 8 of the unique Nordstrom-Robinson code (16,2 ,6) and its essential design. in L) (D 51.4 In order to establish the uniqueness of the XNR-design, we need to appeal to the action of A7 on the geometry of PG(3,2).- Instead of quoting the literature, however, we establish What appears to be a new proof of the classical isomorphism A 8e=PSL(4,2), and then restrict our attention to the action of A7 This thesis attempts to present new results, new approaches, or at least new proofs in each of the following studies: (1) coding theory (2) t-designs (3) automorphism groups (4) finite vector spaces over GF(2), especially PG(3,2). §l.4 The Organization Scheme 2§_the Chapters As explained in §1.2, this thesis answers the four questions: Question #1: Is the uniqueness of the S(4,7,23) and S(5,8,24) Steiner systems sufficient to imply the 12:7) and (24,212,8) binary uniqueness of the (23,2 codes without the restriction of linearity? Questionp: Are the (15,28,5) and (16,28,6) Nordstrom-Robinson codes unique up to a permutation of their 15 and 16 coordinates, respectively? Question #3: Are the automorphism groups of these codes A7 and A7 extended by the elementary abelian ’0.“ -.-\. SIG group of order 16, respectively? Question t4: Does the (16,28,6) code extend to the Golay (24,212,8) code in essentially one way? We shall now explain how the chapters of this thesis are organized in order to answer these questions. First of all, the second through fifth chapters are introductory in nature, developing definitions, examples, and constructions of the codes under consideration. Definitions used in more than one of the following chapters are defined in these initial chapters. Other definitions, for example those concerning graph theory, occur within the only chapter where they are used. As often as possible, the examples used to explain the definitions are examples that will be referred to in a later part of this work. Also within these introductory chapters are constructions of the Golay codes, the S(4,7,23) and S(5,8,24) Steiner systems, the Nordstrom—Robinson codes and the XNR—design. Chapters 2 and 3 are devoted to coding theory definitions and the existence of the codes under study, Chapter 4 to t-designs and the development of the generalized block intersection numbers, and Chapter 5 to permutation groups and an explicit construction of the XNR-design. Commencing with Chapter 6, we embark on an analysis of the Nordstrom—Robinson codes culminating, in Chapter 10, with the affirmative answers to Questions #2 and #3. are a ha won-Z SCH "I ~ Aerc 5e This analysis begins in the first half of Chapter 6 by trying to parallel Paige's analysis of Golay's (23,212,?) code. Although Golay's code is perfect, the property Paige made use of in his proofs, the Nordstrom- Robinson codes are not. However, both types of codes have a maximal number of code vectors relative to their length and minimum distance parameters. Using this property, we are able in Theorem (6.3.1) to show that the minimum weight 8 non-zero code vectors of any (16,2 ,6) code, C , with 0 CC , form a XNR-design. We find ourselves well on the way to answering Question 2 in the second half of Chapter 6 after proving that any XNR-design builds a (16,28,6) code in a unique way (Theorem (6.5.9)). The key to this important theorem lies in calculating and analyzing the generalized block intersection numbers for the XNR-design determined by the weight 6 vectors of the code. These numbers indicate necessary requirements for augmenting this set of 112 weight 6 code vectors to a (16,28,6) code. So thanks to these intersection numbers and the theorems of Chapter 6, we reduce the question of uniqueness to the study of the XNR-design. In Chapters 7, 8, and 9 the question of the uniqueness of this XNR-design is answered. Chapter 7 employs the generalized intersection numbers to prove that any XNR- design is embeddable in a copy of V(4,2), the finite four .9. r. a dimensional vector space over GF(2), Theorem (7.5.1). In other words, the blocks of the XNR-design can be viewed as special subsets of points in PG(3,2), the projective space of 3 dimensions over GF(2). Chapter 8 occurs as an intermezzo, developing line coordinates (Theorem (8.10.1) for the lines of PG(3,2), Which line coordinates are then used in Chapter 9 to prove the uniqueness of the design within the framework of the geometry of PG(3,2), Theorem (9.5.1). Finally, Chapter 10 assembles the results of Chapters 6, 7, 8, and 9 to answer the fundamental Questions 2 and 3. Questions 1 and 4 relating to the Golay codes are considered in Chapters 11 and 12 after all the work relative to the XNR-design has been completed. Since it was shown in Chapter 6 that the (16,28,6) code is unique if and only if the XNR-design is also unique and since a similar theorem will be shown in Chapter 12 relative to the Golay (24,212 ,8) code and the S(5,8,24) design, Chapter 11 tackles Question 4 by considering only the designs in question. Chapter 11 shows that, up to an arbitrary permutation of the 7 additional coordinates, the XNR-design builds a S(4,7,23) in a unique way, Theorem (11.2.8). They by appling the fact that the S(5,28,24) design can be built from the S(4,7,23) design only by adding a new 2452- coordinate which acts as a parity check on the other 23 coordinates, Theorem (11.3.9), S. .a r 1. .wd 2. Int 4 «\b w“ q a... «d 3- we have the theorem that the XNR—design builds S(5,8,24) in essentially one way. Use of the generalized block intersection numbers relative to each of the large Steiner systems is requisite in the proofs of this theorem. Inspired by the approach of Chapter 8, which was the real reason for including that chapter as it appears, we can establish the uniqueness of both the S(4,7,23) and the S(5,8,24) designs relative to the already proven uniqueness of the XNR—design. Furthermore, as a corollary to these uniqueness theorems, we can establish the facts that the automorphism groups of these Steiner systems are 4— and 5- transitive on the points of the designs, respectively, as well as block transitive on them, Theorems (11.2.18), (11.3.14), (11.2.16), and (11.3.13). By almost literally duplicating the proof of theorem 1 (6.5.9), but relative to the Golay (24,2 2,8) code and S(5,8,24), we can show in Theorem (12.3.5) that the (24, 21 2,8) code is unique since the S(5,8,24) is unique. This proof uses the generalized block intersection numbers to full advantage and establishes the equivalence with no assumption of linearity. In fact, linearity of the unique 12,8) 'code ispa lucky, non-essential outcome. Since (24,2 we can answer Questions 4 and l affirmatively after proving Theorem (12.4.1), we now have reached the goal of these chapters. PART B: PRELIMINARIES CHAPTER 2 Binary Codes: Basic Definitions and Properties §2.l Introduction A binary code will be viewed in this thesis as a carefully chosen subset of the set of all vectors of an n—dimensional vector space over GF(2), the field of two elements. We shall customarily write the code vectors as column vectors and represent the entire code by an incidence matrix whose columns are precisely all the code vectors. As in the case with the Nordstrom-Robinson and Golay binary codes, this incidence matrix can be considered as a collecticni of t—designs; and as such, the concepts of binary vector spaces, binary codes, t-designs, and automorphism groups assist one another. This Chapmatincludes most of the needed definitions relating to binary codes. The concepts of perfect and nearly perfect codes are defined in the next chapter along with definitions of the Golay and Nordstrom-RObinson codes. The tools relating to t-designs and automorphism groups will also come later. (References about binary coding related to this chapter are [3], [21], and [30].) 2.1 §2.2 Binary Vector Spaces (2.1) Let V(n,2) denote the vector space of n dimensions over GF(2), the Galois Field of the two elements, 0 and l . Let ‘5 denote any vector in V(n,2). Some- times elements of V(n,2) shall be called pgints. Let B := [e1,e2,...,en} , be a basis of V(n,2). Then relative to B , each ‘x£EV(n,2) is uniquely represented T as a column vector, §_= (x1,x2,...,x ) , where each n xi €GF(2) for i = 1,2,...,n , and where T denotes the transpose of the indicated row vector. Unless other- wise stated, V(n,2) will always be considered as posses- sing a given fixed basis. Let .9 and 1_ be the vectors of V(n,2) all of whose entries are either 0 or 1 , respectively. (2.2) Let PG(n-1,2) denote the set of one-dimensional subspaces of V(n,2) . Since the equation (2.3) §+y=g for _x_,y€V(n,2) is equivalent over GF(2) to (2.4) as = y , it follows that PG(n-l,2) = V(n,2)‘\[g} . Call a non-zero vector of V(n,2) a point, when considered as an element of PG(n-l,2). The mapping (2.5) ( , ) : V(n,2) xV(n,2) 4GF(2) given by y. (modulo 2) 1 n (251) = 2 xi i=1 TEV(n,2), for the vectors x.= (x1,x2,...,xn) X = (Y1,Y2,...,yn)T'€V%n,2) defines a symmetric bilinear form, which is an inner product. For a given .x(5V(n,2) any y€V(n,2) such that (35,1) = 0 is said to be orthogonal to x. in V(n,2) . The set {XI (25,1) = 0, ye V(n,2)] for a given _}£€V(n,2) is the (n-l)-dimensional subspace of V(n,2) orthogonal to x . For a point _x_ePG(n-l,2), the set [1 | (35,1) = O,y€PG(n-l,2)} is a hyperplane of PG(n-1,2) and is called the polar of x in PG(n-l,2). (Linear) subspaces of PG(n-l,2) are (perhaps empty) sets of points of PG(n-l,2) which are closed under vector addition defined in V(n,2) . It is well known that the set of all subspaces of PG(n-l,2) forms a lattice under A and v , which are given respectively by set intersection and linear span. Collineations of PG(n-l,2) are lattice preserving permutations of the points of PG(n-l,2) . Correlations are lattice inverting permutations, which send the i-dimensional subspaces of PG(n-l,2) to ((n-l)-i) dimensional supspaces, for -lgign-l where points are 0-dimensional supspaces and 0' the (-1)-dimensional subspace: of PG(n—l,2). In particular, correlations exchange the sets of points and hyperplanes of PG(n-l,2) §2.3 Binapy Codes Given any two vectors §_= (x1,x2,...,xn)£EV(n,2) and ‘y = (y1,y2,...,yn)£5V(n,2), with coordinates relative to a given fixed basis of V(n,2), then define the following: The weight, |x|, of a vector .§(EV(n,2) is a mapping | ‘: V(n,2)-4 the set of integers,, 2 given by n (3.1) |x| := 2 xi , where addition is now computed in Z . i=1 The (Hamming) distance‘*, d(x,y) , between two vectors, x and yEV(n,2) is (3.2) d(x,y) := [x-ty] . The coordinate-wise product of two vectors is (3.3) fl 3: (xlyl’x2Y2""’ann) A vector .x is contained in a vector y , (3.4) £31 iff 35:31. One can easily check the following list of properties that pertain to the above definitions: (3.5) the Hamming distance is a distance function. (3.6) Isl + I2) = la +x| + lexl - (3.7) xx =,§ . (3.8) g_is a partial ordering on vectors of V(n,2) (3.9) 3531 iff IE +xl = IX) - III * The Hamming distance is the square of the customary Euclidean distance in the binary case. (I; 1.x) A (binary) code, C , is any set of vectors from V(n,2) . (3.10) A code word is a vector ve:V(n,2) that is also in C . A (n,M,dO) code C is a code C of [Cl = M vectors from V(n,2) so that (3.11) min [5+112d0 . x,y€C. xa‘y (3.12) we sometimes write "C is a code with dgldo" or "C has minimum distance do" if C is an (n,M,do) code and if the value of n is understood. (3.13) A linear code C is a code satisfying 5X60 imply 35 +y€C . (3.14) A linear code is a subspace V(m,2) of V(n,2) for OSmgn , and is said to have dimension _n_1_ . Any linear code C with at least one code word contains .9 , and as such is an (n,2n,d0) code for (3.15) d0 = min Ix] . xeC x#0 We shall, for the most part, consider non-linear codes, although occasionally the concept of linear codes is a useful tool in this thesis. 52.4 Incidence Matrices (4.1) An incidence matrix for an (n,M,dO) code C is an nth zero-one matrix whose columns are the code words (per def. (3.10)) (4.2) If C is a linear code, then one may choosezabasiscaf code words and form an n.xm matrix ‘Q called a generator matrix for C , having as columns those m basis vectors which span the code (a V(m,2) subspace, cf. (3.14)). Let C be a code, and define (4.3) C1 := [y€V(n,2) | (35y) = O for all _)_(_€C} Cl is called the code orthogonal to C . By the definition (4.3) of Cl it is clear that the following properties hold: (4.4) C‘L is always a linear code. (4.5) (Cl)1 is the linear span of C . (4.6) (C1)1 = C iff C is linear. (4,7) Let any generator matrix of Cl be denoted by H and be called a parity check matrix of C . We now proceed to define the Hamming codes in terms of the generator matrix of their orthogonal codes. Let Hn be the (Zn—l) xn. matrix Whose rows are all the (Zn-l) distinct non-zero vectors of V(n,2), and so placed in Hn , that the iEh-row of Hn represents (relative to a fixed basis of V(n,2)) the binary expansion of the integer i , for lgian-l . Let (4.8) on := [_x_€V(2n-1,2) | gen = 9T } The code Cn is called the Hamming code of length Zn-l (4.9) m: cn isa linear (2“-1,2(2n‘1'“),3) code. Proof: Property (4.5) shows that CD is linear. Then it is 5,8 ‘ P)- u‘e A: t n i. 4.. . nJ .9 5 .LJ AU fl Nate IONS €5.31 z 2((2“-1)—n) clear that |Cn| It now suffices to check d023 in (3.15). If |x| = l for xeCn, then xifln = 9? implies that one of the rows of Hn is the Q€V(n,2), contradiction. If [3“ = 2, for xecn , then xyfln =.QT implies that two distinct non-zero vectors of V(n,2) are linearly dependent, contradicting equations (2.3) and (2.4). Hence, d0213 . // §2.5 Modifications pf codes Given an (n,M,dO) code C , one can obtain related codes by a number of different standard modifications. Some of these are given in the following list of definitions. (5.1) A coset, C +‘x , of a code C is C +_}_{_ := [y +x | xEV(n,2), yec} Note that if C is linear then y,§€C + 35 imply y + 2 EC , but not so if C is not linear. (5.2) A punctured code of C is a code with an incidence matrix identical with that for C except that one of the rows is eliminated. (5.3) A parity check code of C is a code with an incidence matrix identical with that for C and with one extra row; the zero or one entries in the extra row are chosen so that the weights of the resulting column vectors are always even. The added row is called the parity check coordinate row. (5.4) An equivalent code to code C is a code Whose A s'ct ‘r I . -A‘ -541 u . — I F... a . ‘ . o. L e :4 71 CJ .7. :4 I e .I... .7 :l . . - . A. a 1 Fug incidence matrix N can be transformed into that for C after a suitable permutation of the rows and columns of N . One can easily see that the following properties hold for a given (n,M,dO) code C (5.5) A punctured code of C is a (n-l,M,dO-l) code. (5.6) If dO is odd, then a parity check code of C is a (n + l,M,dO-+l) code. (5.7) The relation of "being an equivalent code" is an equivalence relation. (5.8) A punctured code of a linear code C is again a linear code. (5.9) A parity check code of a linear code C is again a linear code. (5.10) As examples of parity check codes, we define the Extended Hamming code, E;', of length 2n as the parity check code of C whose parity check coordinate row is the first row of the corresponding incidence matrix. Then by (5.6) and (5.9) we have proved: (5.11) Lemma: The Extended Hamming code, 53', of length n 2n is a (2’222 ‘1‘“,4) linear code. §2.6 Geometric Codes Let m be any fixed one to one correspondence: (6.1) m : V(2“,2)..2V(“’2) so that the standard basis vectors from a fixed basis B of V(2n,2) are mapped to points of V(n,2). Then the vectors of V(2n,2) are called characteristic functions v?“' I A an . .4...“ '9;- d . _.A fr.» .1 O y In...» II\ #0 no of subsets of the points of V(n,2) relative to w and B . (6.2) Let cp : ei€B4x€V(n,2) so that, relative—:0 a fixed basis A of V(n,2), the binary expansion of i is x . From (6.2) it follows directly that: (6.3) Lemma: For m defined in (6.2) and for fixed bases A and B of V(n,2) and V(2n,2) respectively, the code words in the Hamming code C are precisely the n ) characteristic functions of binary dependent sets from PG(n—l,2) A geometric code is a binary code, whose code words can be interpreted in terms of the geometries of V(n,2) or PG(n-l,2) by an appropriate one to one correspondence T . ' From Lemma (6.3) one can see that the Hamming codes are geometric codes. The Nordstrom-Robinson code, which will be defined in the following chapter, is also a geometric code, Theorem (7.5.1). This observation is a key step in the uniqueness proofs, Theorems (10.3.2) and (10.2.1), of the Nordstrom-Robinson code and its extension. CHAPTER 3 Definitions and Existence of the Golay and Nordstrom-Robinson Binary Codes §3.1 Introduction The definitions and existence of the Golay and Nordstrom-Robinson codes will be presented in Sections 3.3 and 3.5. To this end it will be useful to establish the sphere packing bound, in Section 3.2, which gives an upper bound for the number, M , of code words in an (n,M,(2e+l)) code. Those codes satisfying equality in this bound are called perfect codes. Thus if C is a perfect code in V(n,2) all the points of V(n,2) can be "perfectly" covered by the disjoint spheres of (Hamming) radius e centered about the points of C . The Golay code is an example of a perfect code. The Nordstrom-Robinson code is not perfect, but does satisfy equality for a refinement of the sphere packing bound, called the specialized JOhnson bound. This is introduced in Section 3.4. Codes satisfying equality in this bound are called nearly perfect codes, a name coined by Goethals and Snover [17]. The class of nearly perfect codes contains the class of perfect codes. In terms of V(n,2), if C is a nearly perfect code, then the spheres of radius e-tl centered about points of C cover all points of V(n,2) . (The Spheres are not disjoint in this tl‘ E case, though.) All perfect codes are known. VanLint [21] and Tietgvginen and Perko [34] have shown that they must be of the following types: (1) the Hamming (linear) codes and the Vasil'ev (non-linear) 2k—k-l codes, both with parameters (ZR-1,2 ,3) for any k , 12,7), and (2) the Golay binary code with parameters (23,2 (3) the trivial one word and two word codes of lengths n = e and n = e-tl respectively for any e It is known that the Hamming codes are unique up to isomorphism. While no proof of this can readily be found in the literature, a proof similar to that of Theorem (7.4.4) of this thesis can be constructed. However, without the restriction of linearity, codes with the same parameters as k 2k-k—l the Hamming codes, (2 -l, 2 ,3), are not unique for k214 as was shown by Vasil'ev [36]. In 1968 V. Pless showed [31] that any linear (23,212,?) code must be isomorphic to the Golay code. One major purpose of this thesis is to establish the fact that the Golay binary code is unique even without the linearity assumption. This will be accomplished in Chapter 12. Furthermore, the Nordstrom-Robinson code will be shown to be unique up to isomorphism in Chapter 10. This code is the first code in each of the infinite families of k Preparata codes of parameters (4k-l, 24 -1-4k,5) for anifif‘e l '5’“- a» ,0» ‘. 5 ~ HM.- Jen (2.2T: k;12 [32], and Kerdok codes of parameters (4k-1, 24k,((4k—2k)/2—1)) for k22 [20]. Our present purpose in this chapter is to develop the concepts of perfect and nearly perfect codes, to establish the existence of the Golay and Nordstrom-Robinson codes, and to show that these codes are both nearly perfect While the Golay code is perfect. §3.2 Perfect Codes For a given (n,M,dO) code C let (2.1) e := Then e is called the error correctingpcapabilipy of code C . C is said to be an e—error correcting code. Let the sphere, B(w,r), of radius r about w€V(n,2) be defined as follows: (2.2) B(y_,r) := {y€V(n,2) |d(_w_,y)gr} . Since the Hamming distance is a distance function by (2.3.5), it satisfies the triangle inequality. Therefore, the spheres of radius e about code words in the given (n,M,dO) code C must be disjoint. This observation proves the following inequality: | u B(§,e)| g (V(n,2)| = 2“, xQEC o and gives the sphere packing bound: (13) (q.(1+(§)+(§)+...+(2))g2“. r :2 J m ¢ 1 is '11 lficlc i.» - dddlc :fi “‘1‘”; 3.4 (2.4) A code C satisfying equality in the sphere packing bound (2.3) is called a perfect code. Notice that e = n yields the trivial solution of equality in (2.3) for [C] = 1.; the corresponding code C is the trivial code, consisting of (any) one vector of V(n,2) . For |C| > 1, necessarily e < n/2, in which case e is defined as in (2.1). (2.5) Lgmma: The Hamming code Cn of length 2n—l is perfect. 2n-1 n 2 "1"“).(1+ (2“-1)) = 2 . // Proof: 2( §3.3 Definition pf the Golay Code With a construction method due to E. F. Assmus and H. F. Mattson, cf. VanLint [21], we shall construct from 1 E; , the extended Hamming code of length 8 , a (24,2 2,8) code. Then by puncturing this code we shall show that the 1 (23,2 2,7) code called the Golay binary code obtained in this way is linear and perfect with e = 3 Let '5; be the extended Hamming code of length 8 with incidence matrix N given in Figure (3.1). Notice that the indicated 7 x7 submatrix M is the familiar symmetric form of the incidence matrix of PG(2,2) . The rows of N are numbered by m (of. (2.6.1) with the integers 0,1,2,...,7. Figure (3.1) N o 000 0111111110000000 1 O O 1 O O 1 1 O l O O 1 l O O 1 O l 1 2 O 1 O O O O l 1 O 1 O l 1 l O O l O 1 4 l O O O O O O 1 l O l 1 l l 1 O O l O 5 1 O 1 O 1 O O O l 1 O l O l l l O O l 7 l 1 1 O O 1 O O O 1 1 1 l O 1 1 l O O 3 O 1 1 O 1 O 1 O O O l 1 O l O 1 1 1 O 6 110 0110100010010111 M . Figpre (3.2) O O O O O 1 1 1 l 1 1 1 1 O O O O O O O 6 110 0110100010010111 3 O 1 1 O 1 O 1 O O O 1 1 O 1 O l l l O 7 1 1 1 O O 1 O O O l l 1 1 O l l 1 O O 5 1 O 1 O l O O O 1 l O 1 O 1 l 1 O O 1 4 1 O O O O O O 1 1 O 1 1 1 1 1 O O 1 O 2 O 1 O O O O 1 1 O 1 O 1 1 1 O O l O 1 1 O O 1 O O 1 1 O 1 O O 1 1 O O 1 O l 1 Perform the row permutation (16)(23)(47) on N , inverting the order of the last seven rows, and obtain the equivalent code '5; , (cf. figure (3.2)) and N' (3.3) £131.19: (1.) 6306; = {9,1} . (2.) All code words of '5; and '5; ‘have weights 0, 4, and 8 (3.) All vectors of the form mgty , where age-C; and y 6C: have even weight. Proofs: Claims (1.) and (2.) are immediate from inspecting in F” . s 1") ) ‘3‘ Saw ( least {3.3) \ = $1an the incidence matrices N and N' of 53' and '5; given in Figures 1 and 2 respectively. Claim (3.) follows from (2.) and Formula (2.3.6) Which reads: (3-4) M + (Y) = 122 +x| + 2W)- Now define (3.5) XGOLAY := [(3 +15 :13 +_)_(, _a_ +1; +35)T |_a_,:_b_eE—3- and to be the extended Golay code, or XGOLAY. l 5.1, ) Theorem: XGOLAY is a (24,2 2,8) linear code. Proof: That XGOLAY is linear is immediate from Definition 3.55). That XGOLAY has dimension 12 is an immediate consequence of the fact that Q? has no nontrivial representation of the form (§.+ m, p_+ m, a_+'p_+.§)T . It now suffices to show that d028 . If y_ =(a_+x_,_b_+_x_,§_+b_+_)£)T#9_T andifat least one of g, 2, 3+2, or 35 is either 9 or _]_._, then (3.3) implies that [g] 2_8 . Three applications of (3.4) yield the following equality; (3.7) Ia+§l +Lle+25|+la+12+r|= = (2+2! +2Il + |e+2+2£| = [5| + 2{|(e +§)(s+§)|+(e+s)(l+r)|l = [5] + 2‘2 +»p + gp,+ m] . If none of g, p, a +-p, m are either 9_ or p; , then [5| = 4, and it is necessary to show |§'+-p,+'§p +.§|§2 2 . Since IQ] = [b] = 4 and (3.4) implies that [am] is even, |E+2+22+2£1 mustalsobeeven. If |g+p+§p+§|=o 3 then _a_+p+§la_=x. Then (3+_]:)(_b_+l)= (35+_l_),and 3.7 hence §_= 2,: §_. Therefore .§(§E;(W é , contradicting Isl =4.// (3.8) Any punctured code of XGOLAY is called the‘*Golay code or GOLAY. (3.9) Lemma: The Golay code is a linear (23,212,7) code» Proof: Use (2.5.5), (2.5.8), and Theorem (3.6). // (3.10) Theorem: The Golay code is a perfect linear (23,212,7) code. 2352:: 212(1 + (213) + (223) + (233)) = 223 . // §3.4 Nearly Perfect Codes Let C be any (n,M,dO) code where d0 = 2e+l, i.e. dO is odd. Let B(m,r) be as in (2.2) and 356C . Let (4.1) T(x) := [er(n,2) |d(_x,y_) = e+l] . Now partition T(m) into two classes, Ta(§) and TB(X)’ according as the elements of T(m) belong to some B(y,e) for some yEC, or not, that is, (42) any F{£€TBHBXEC,X£BQfiU}o (4.3) Tags) := (xeerrxec, “amen. (4.4) Lflnmg: For each _x_€C, |Ta(3§) |g[(n-e)/(e+l)](2) , 392:: Let yeTan) = e+1, d(_\_r_,y)ge , d(§,y)>_2e+l = do . By the triangle inequality, necessarily it follows that d(y,y) + d(y_,3<_) = d(y,_x_) = 2e+l = do . * Later we shall prove that this code is unique up to equ1valence, and so the article "the" is not a mistake. In ti) 3.8 In this case |TG(§) fl B(z,e)\ = [29”), e+l from Which, (4.5) [Ta(3_<_)l = (26:1 e l) IN2e+l(§)l ’ where N2e+l(§) is the set of code words y, at distance 2e+l from .5 . Since any two vectors in N2e+l(§) are at least a distance 2e+l apart, the (2e+l)-sets of coordinate places in Which they both differ from y_ share at most t coordinate places. Furthermore since there are at most [(n—e)/(e+l)] subsets of cardinality (2e+l) of a set of n elements which share precisely a given sdbset of cardinality e , we deduce 4. _ 1 n 2e+l . < 6) |N29.1(r)|_<_[(n e)/(e+ )] Now we are able to state and prove a refinement of the Sphere packing bound, which is a specialized version of the S. JOhnson bound [18] . The Johnson bound itself uses the numbers max [Nd(§)| rather than the particular value in .§€C terms of n and e given by inequality (4.6). (4.8) Theorem: (the specialized Johnson bound) Fer pm For any code of length n , and minimum distance 2e+l, n n 1 11 n-e n—e r1 c.1+( )+( )+...+ ()---‘--— $2~ Before proving this theorem we note the following equivalent form of the specialized Johnson bound: n n n 1 n+1 tr (4.9) ICI- \1 H1) + (2) + +Ke-1)+[ (n+1)/(e+1)]\e+1/‘}$2 Which is equivalent to that in the statement of Theorem (4.8) because n-e ,n-e _ _ _ _£L_n .2114 \EII’LET-IJ) .. o e n = l (mode+l)eLe+lJ#Le+1J . Proof of Theorem (4.8): There are at least |(J TB(§)| vectors of the space, V(n,2), not contained in afifrc B(§,e), mEC . A given vector of the space can belong to at most [n/(e+l)] distinct sets TB(_x_) , for 35 6C , since vectors of the code are at least a distance 2e+l apart. Hence, using Corollary (4.7), we obtain (4.10) UT (g) M n -' 319' n , Ixec f5 |2[n7(e+1)] \Kefl) Le+l JKeN from which the result follows by noting that the number of vectors in L)(B(§,e)lJ TB(§)) is less than or equal to xec n — 2 -// (4.11) Codes meeting the bound of Theorem (4.8) are called nearly perfect. The next lemma shows the important fact that the class of nearly perfect codes contains the class of perfect codes. (4.12) Lemma: Every perfect code is also a nearly perfect code. t) -i V I 44. C051 eve. . n V“ E Proof: The specialized Johnson bound reduces to the sphere packing bound exactly when n+1 -:—' 0 (mod (e+l)) . // We can describe nearly perfect codes in more detail with: (4.13) .EETEE! For any nearly perfect e~error correcting code of length n (i) any vector at a distance greater than e from every code word is at a distance e+l from exactly [n/(e+1)] code words, (ii) any vector at a distance e from a given code word is at a distance e+l from exactly [(n—e)/(e+l)] other code words. .gmgpj: Equality in (4.9) implies equality also in (4.10) and (4.7). Equality in both (4.7) and (4.10) implies that each vector at a distance greater than e from each code word is at a distance e+l from exactly [n/(e+l)] code words, i.e. part (i). Equality in (4.7) together with (4.5) proves (ii).// §3.5 Definition 9; the Nordstrom-RObinson Code Various people involved in binary coding theory were aware in the early 60's that there might exist a (l6,256,6) code. The specialized Johnson bound (Theorem (4.8)), which was known then, inspired the search, since this showed that no (l6,M,6) code could have an M:>256. Moreover, since 256 is a power of 2 , it was natural to ask if there was a linear code with parameters (l6,256,6) . Calabi et al., 525149 answered this question [7] in the negative. However, Nadler [27] had discovered in 1962 a (l3,32,6) non-linear code, that, even up to today, is the (13,M,6) code with the largest known M value. Nordstrom and a high school student named Robinson were able to construct a (15,256,5) and hence a (l6,256,6) non-linear code from Nadler's code [28]. In this section we construct the extended Nordstrom— Rdbinson code from IE; , the extended Hamming code of length 8, in a way resembling the construction of XGOLAY given in Section 3.3. In this construction, due to C. L. Lin, B. G. Ong, and G. R. Ruth [22], we create a code of length Zn from two codes of length n , the first of which must be linear. In order to better understand this scheme, we first prove a few remarks and lemmas regarding linear codes. Since a linear code C is a subgroup of the additive abelian group [V(n,2), +], Where + is vector addition in V(n,2), it is necessary (by the Lagrange theorem for group theory) that |C| = M = 2k for some 03kgn . Furthermore, the set V(n,2) may be partitioned into 2n/2k = 2'“-k cosets (cf. Definition (2.5.1)) by c Therefore, (5.1) Lgmmg: Let C be a linear (n,2k,d) code and let L = {il’l2""’i2n-k} be a set of distinct coset . n- . . representat1ves, one chosen from each of the 2 k d1st1nct cosets of C in V(n,2) . Then each er(n,2) can be expressed uniquely as y = .11 + m, where 16L and mEC . we omit the standard proof. Note that it is always possible to choose coset representatives 1, of minimum weight, since each coset C +4; of C in V(n,2) is a finite set. Let E; be the extended Hamming code of length 8 . By Lemma (2.5.11), '5; is a linear (8,16,4) code and is given by the 8;(l6 incidence matrix of Figure (3.1). Let I. be the set of 16 minimum weight coset leaders of E; to cosets of 63' in V(8,2) given in Figure (5.3). Figure (5.3) Cosets of ‘5; Assignment by f of words (identified by their leaders) in C; to the cosets 1151‘ 15(1):) 6C3 0 0 0 0 O 0 O 0 O 0 O 0 0 0 0 0 0 1 0 0 0 0 0 0 l 0 0 O l 0 l l 0 0 l O 0 O O 0 l l 0 0 0 l O l 0 O 0 l 0 O O 0 l l l 0 O 0 l 0 O O O 0 l 0 0 0 l 0 l l 0 O O l O 0 0 O 0 l 0 0 1 l O 1 l O 0 0 O 0 0 0 0 0 l 0 l 0 l 0 1 1 O O 0 O 0 0 0 O 0 l l O 0 1 0 l l 0 l 0 O 0 0 O 0 0 l l l 1 l l 1 l l l O 0 O O O 0 0 l l l 0 l 0 0 l 0 l O 0 O O 0 0 0 l 1 l 0 l O 1 0 0 l O O 0 0 O 0 0 l l l O l l O 0 O 1 0 O 0 0 1 0 0 l 1 l 0 1 0 0 0 O l O 0 O 0 l 0 O 1 1 l 1 0 0 0 0 0 l 0 O 1 0 1 0 0 1 l l O O O 0 0 0 1 O l l 0 l O O 1 NT where N is from Figure (3.1) Now define (5.4) XNR := {(2, y_+f(y))T| “V(8,2) and f(y) = f(1i-+m) = f(Ji) for f given in Figure (5.3)] to be the extended Nordstrom-Robinson code or XNR. (5.5) Theorem: XNR is a (16,28,6) code. Proof: From (3.4) we may derive wt) m+xl+u+x+sl EI+MB+xH§+x+y| Le) + 2l(.>_<.+1) + (e+x)e| =LM+2BE+E)+mx+y|. Furthermore, if 11 and 12 denote coset leaders of C3 from L and if f(&i) and f(12) denote the code words of 5? verify that (5.7) “11 +1.2)(11 +1.2 + f(1.1)+ f(1,2))| = 1 Whenever |f(&l) + f(&2) | = 4 . assigned to them in Figure (5.3), then one can easily Now choose any two distinct code words (21,31 + f(yl)) and (32,32 + f(yz)) from XNR. The distance between these two words is |(.Y.]_ +312: .21 +12 + f(V1) + f(22))| . S1nce Lemma (5.1) implies that .31 = ‘1 +-ml, 22 = 12 + m2 for suitable 11 and AZEL and ml and mzec3 , this distance may be written as |(-lt]_ +1111 +112 +322: 111 +31 +12 +312 4' f(fil)+f(_&2))| = 1f(.&1)+ “1.2” + Zlui +12H11 +12 + t"41”“ 1‘"42” +031 *rmsz1 +912 + f(1.1)+f(1.2))| by (5.6). we examine three cases: Case 1: |f(Al) + f(12)| = 8 . Clearly, the distance between the two words is greater than or equal to 8 . Case 2: lf(&l) + f(&2)| = O . This implies that «£1 =‘12 and f(11) = f(&2) . The distance between the two words is then ZIQEI +s2Hs1 +512)! = 2|(ml +192” ;._8 because ml a! m2 Case 3: |f(&1) + f(12)| = 4 . By (5.7) we now have ((11 +12H11 +12 + f(11)+ f(1.2))|= 1. Since ml, m2, f(11), and f(12) are in C3 , [(El +'92)(fll + 92 + f(&1) + f(&2))| is an even number. It follows that lul +1.2) (1.1 +1.2 + “11) + f(1.2)) + (1111 +112) (1111 +_er + f(_§1)+f(3._2))|,\0 and the distance is at least 6 . XNR has [C] = M = 28 since 3. may be chosen arbitrarily from V(8,2). XNR has distance 2_6 since in all three cases above, the distance between any two distinct words of XNR is greater than or equal to 6 . // (5.8) Any punctured code NR of XNR is called the Nordstrom-Robinson code or N3 . (5.9) Lgmmg: The NR code is a (15,256,5) code. uggppfi: Use (2.5.5), (2.5.8), and Theorem (5.5). //' (5.10) Theorem: The NR code is a nearly perfect (15,256,5) code. 8 15 Proof: 2 - (l + ( 1 ) 15 + (136))=2 .// 1 T6" LTT' J there (1.2; CHAPTER 4 t-Design and Generalized Block Intersection Numbers §4.l Main Definitions Let an x-(sup)set denote a (sub)set of cardinality x. A block design is a collection B of k-subsets of a given v—set X . Elements of X and B are pgints and blocks, respectively. (1.1) A t-desigp with parameters A-(t,k,v) is a block design with the property that each t-subset of X is contained in precisely 1 blocks of B . The parameters of? a t-design are all non-negative integers so that ogtgkgv mm 1>0. Whenever a t-design with parameters x-—(t,k,v) exists, there exist positive integers bi’ i = O,l,...,t, so that (1.2) bt = ). and (v-i)b1+1 = (k-i)bi for Ogit are never constants originally. We conclude this section by revisiting the example of pOir COR: bloc the 14 planar 4-tuples in V(3,2) . The counts bO = 14, b1 = 7, b2 = 3, and b3 = 1 can be found from the three equations of (1.2) and the parameters l-(3,4,8) of the design. Then noting that b1 0 = bi for ogigt = 3, , and employing the Pascal property for block intersection numbers we find the bi j for this design to be: 3 (4.6) 14 To help clarify these counts, the number 4 is the count b and represents the number of dependent 4-tuples of 1,1 V(3,2) containing a given point (vector) v1 of V(3,2) and missing another given point v2 . Choosing any third point of V(3,2), say v3 , then there are two blocks containing v1, missing v2 and containing v3 and two blocks containing v1 , missing v and also missing v3 . These counts are b2 1 = 2 and b = 2, respectively. 9 1,2 1-+b = b holds. ’ Note that the Pascal property b l 2 3 2 1,1 §4.5 Motivation for the Generalized Block Intersection Numbers Using the Design g£_the Thirty 3-Cubes $2 the 4-Cube Although in a t-design the counts bi,j are not constant for i-+j:>t (unless the t-design were originally at least a (i-+j)-design), these counts may depend only on a certain character of the (i-tj)-set in question. For example, in V(3,2) the count of the number of dependent 4-sets passing through a given 4-set is either 1 or 0 depending upon whether that 4-set be a dependent 4-set or an independent one. In the next section we shall define generalized block intersection numbers which are constants, like the block intersection numbers, as long as we specify the particular (k-+j)-set in question. However, we now preempt that discussion by exploring in depth one important example. Consider the thirty 3-cubes contained in the 4-cube. That is, consider the thirty copies of V(3,2) contained in V(4,2) . That there are thirty is established in the following lemma. (5.1) .EEEE33 There are 30 copies of V(3,2) in V(4,2) . Egggfi: First notice that each V(3,2) contains 14 dependent 4-tuples and hence (2) - 14 = 56 independent 4-tup1es. Now count the ways to choose an independent 4-tuple from V(4,2). The first three vectors of V(4,2) may be chosen arbitrarily. But then the fourth, in order to form an independent 4-set must not be the unique vector sum of the first three. Since these four vectors from V(4,2) may be chosen in any order, we obtain 16.15.14.12 4.3.2.1 = 1680 independent 4—tup1es in V(4,2) Finally, because each V(3,2) contains 56 of these independent 4—tup1es, there are in total 1680/56 = 30 copies of V(3,2) in V(4,2). // Consider now the t-design whose points are the 16 vectors of V(4,2) and whose blocks are the 30 copies of V(3,2) in V(4,2). (5.2) Claim: This design of the thirty 3—cubes in the 4-cube as blocks and the sixteen vectors of the 4—cube as points is a 3-(3,8,l6) design. .ggggfi: The key to this proof rests on an inspection of the planar 4-tup1es, which are copies of V(2,2). To this end we note the following: (5.3) Remark: Each pair of V(3,2) can intersect in either a V(—1,2) = a, a V(O,2), a V(l,2), or a V(2,2) and hence the intersection set has cardinality 0,1,2, or 4 . Now proceeding with the proof of (5.2) we note that any planar 4-tup1e is contained in at most three copies of V(3,2), since the sets of the four points other than the planar 4-tuples from each of the V(3,2) must be disjoint. So each triple is contained in a unique planar 4-tup1e. Next considering formula (1.8) for t-designs we have: k v A average b = b = b ( )/( ) = 30.8.7.6/16.15.14==3 3 3 0 I3 3 Finally, since no triple can be contained in more than three blocks, we see that each triple is contained in exactly three blocks, making the design a 3-(3,8,16) design. Now the formulas (1.2) and v = 16, k = 8, and b3 = 3 3 imply that bO = 30, b = 15, and b = 7 . From the 1 2 Pascal property the block intersection numbers for any 3-(3,8,16) design follow: (5.4) 30 This design of the 30 c0pies of V(3,2) in V(4,2) is not a 4-design. Indeed, although each planar 4—tup1e is contained in three blocks (3-cubes), each non-planar (independent) 4-tup1e spans a unique 3-cube. Hence b4 is A non-constant. Note that b4 is not even an integer: /\ _ 14.3 +56.1 __ _7_ (5'5) ’04- 7o “’5’ since each of the 14 planar 4—sets is contained in three blocks and each of the 70—14 = 56 non-planar 4—sets is contained in just one block. So there are two types of 4-tuples in V(4,2): planar and non-planar 4-tuples. However, the number of blocks through any type of 4-set is a constant. Therefore, it makes sense to define b: = 3, and bi = l, for the planar, and non-planar 4-sets respectively. This leads to a generalizatirnm of the bi j w.r.t. the planar set P by defining ) bi,j=bi,j for 1+Jg3, P _ P _ b4,0 —‘b4 - 3 and P P _ P _ . . . bi,j+l+bi+l,j -bi,j for 1+3 - 3,031,333 . This last statement defined all bi j ’ for 4;:j;:l . These b: j then are: ’ (5.6) 30 15 15 7 8 7 3 4 4 3 3 O 4 O 3 Similarly we can extend the b. . to by . : 1,] 1:3 (5.7) 30 15 15 7 8 7 3 4 4 3 1 2 2 2 1 Suppose we try extending the bi,j to other sets L . For example, let L be a dependent 6-tuple in V(4,2) . (In the following chapter we establish the existence of 448 of these.) A dependent 6-tup1e has certainly no subset of 4 points which are also dependent (since then the remaining pair of points could not be distinct by (2.2.3) and (2.2.4)). Hence, a dependent 6-tuple contains no planar 4-sets. Then each 4-set contained in the 6-tuple, being an independent set of 4 vectors of V(4,2), spans a unique V(3,2) . Furthermore, if a S-set contained in this dependent 6-set were contained in a V(3,2), the S-set would then contain a dependent 4-set; so each S—set contained in the dependent 6-set must span all of V(4,2) Actually, we have proved the following lemma which will be useful in Chapter 5: (5.8) Lemma: Dependent 6—tuples contained in V(4,2) are composed of 6 vectors of V(4,2) no 4 of which are dependent (form a V(2,2)) and no 5 of which are contained in a 3-cube (span a V(3,2)) We may now define bi = l, 'b? = 0, 'b2 = 0 (well- defined so long as the set L is a dependent 6—set in V(4,2)). Then we may generalize the bi j to b]; j for Ogi +j36 1 .9 by defining L _ . . bi,j _bi,j for O_<_1+3_§_3 , L L . bi,0=bi for 03136 , and bL +bL -b f o '+° 5 1+1 i,j+1 " i,j or $1 33 ' The numbers b? . 1:] 3-(3,8,16) design passing through a given i-set and avoidixn; now count the number of blocks of the j-set where the (i-+j)—set is a subset of the special set L, namely a dependent 6-tup1e from V(4,2) . These by 1,3 are: (5.9) 30 15 15 7 s 7 3 4 4 3 1 2 2 2 1 o 1 1 1 1 o o o 1 o 1 o 0 Our use of these generalized block intersection numbers lies in the interpretation of the bottom line, the b? j ’ for i+j=6: (5.10) ggmmg; A given dependent 6—tuple of V(4,2) meets; any copy of V(3,2) in V(4,2) in exactly two or four places. Proof: Each bi j for i-+j = |L| counts the number of ) blocks of the design in question passing through exactly i ( and not the other j ) of the points of L . Since in (5.4) only bi 2 and b; 4 are non-zero, the lemma follows.// 1 3 Finally we shall extend the bi j to the counts bf 3 ’ where B is a block of the design. We already calculated, in (5.5), that each 4-tuple contained in an block of this 3-(3,8,16) design was contained in 7/5 blocks, on the average. Each S-set, which is contained in a block, a V(3,2), certainly contains an independent 4-set, so this 5-set is contained in only that block, and no other. Therefore, we may set A B _ _ B _ _ B _ B _ B Then again by the definitions: b1? . =b. . for ogi+jg3 1’] 1’] B _ B . bi,0 — bi for 03138 b3 +1:B =b for o i+° 8 i+l,j i,j+1 i,j S 33 ’ we obtain generalized block intersection numbers for this design relative to a block of the design: (5.11) 30 15 15 3 4 4 3 7/5 8/5 12/5 8/5 7/5 1 2/5 6/5 6/5 2/5 1 1 0 2/5 4/5 2/5 0 1 1 o 0 2/5 2/5 0 o 1 1 o o 0 2/5 0 o o 1 Now interpreting these generalized intersection numbers we have: (5.12) Lemma: Blocks of the 3-(3,8,16) design of the thirty 3-cubes in the 4-cube meet one another in 0 or 4 places. Proof: Only the b? j 7’ o with i+j = 8 = |B| for ) i = 0,4, or 8 . That bB = 1 means that the block B 8,0 of the design meets only itself in all of its 8 places. /7’ This lemma was not evident a priori. Compare (5.3) to the statement of Lemma (5.12). (5.13) Note also that we do not wish to consider the B generalized numbers bi to be integers, but rather average: ’ over all i—sets of the number of blocks through each i-set contained in the given set B . §4.6 Generalized Block Intersection Numbers J. M. Goethals in [16] defined the block intersection numbers bi j for a t-design and for ogi+jgt . The ’ generalized block intersection numbers bi j for L being a J block of the design were considered by N. S. Mendelsohn in [25]. These numbers b? j’ to be formally defined in this 3 section, provide a link between the two concepts as well as a legitimate generalization of both. Remembering the comment (5.13) at the end of the last section we shall define, relative to a given L set L (contained in the point set X of a t-design), bi as the: .7 average over all the possible (i +j)-sets contained within L of the number of blocks of the t-design passing through the i-set and avoiding the j-set. Formally: L B,A\B a given t-design containing all points of A and no points (6.1) Let b denote the integer number of blocks of’ of B, for given sets so that BcA CL . (6.2) Then b?” . := (‘9') z: (( '2‘)‘1 2: bg’MB) . 1,3 1+j ACL |AT=i+j 15:1 So the numbers b: A\B are integer counts whereas the i L L i,j are averages over all the possible bB,A\B w1th BgAEL . (Relative to the very last example in the last b section with the set L being a block of the thirty 3-cubes . _ . L _ L _ L in the 4 cube de31gn, bP,P - 3, bN,N _ 1, and b4,0 = 7/5 where the sets P and N were the planar and non—planar 4-sets contained in the block L, respectively.) (6.3) Lemma: The generalized block intersection numbers L . bi,j satisfy: L 6.4 b. . = b. . f r L t () 1,3 1,3 O ‘K (6.5) b? j are constants depending only on the particular 3 set L and the cardinalities i and j, and L L _L (6.6) (Pascal Property) bi+1,j'+bi,j+l — bi,j for i+jg|L|-1 Proof: Since the b: A\B ans constants independent of the ) set L and the cardinality of B, as long as |B|5;t, property (6.4) is clear. Again, since the b? are 1,5 averages over all the possible subdivisions of the given set: L, into subsets of cardinality i,j, and (|Ll-i-j), these numbers are constants dependent only on the set L and the: cardinalities i and j . Property (6.6) is established directly. L := Ll -1 i+j -1 .. L ‘by bi,j (i+j ) 132 ( i ) CZ“ bc,13\c lsfii+j |df£i definition. Since for each P EL\B the following holds: L _ L L bc,s\c “ bcup + be, (BUP)\C(BUP) \ (CUP) we can write L ._ L —1 ~ 1+3 L-('+') —1 bi,j‘(l+3‘) L ( 1’23” )113) BCL CcB |sT=i+j |CTéi 23 (bL L where CLJP means CLJ[P} . . L i+j+1 __ L L _(i+j) Since (iljll)(l ) —. (1+;)(\ | ) and Since 2:] 2" = 1" Z for A : BL'P , ‘B)=i+j |ATsi+j+1 L _ L i+j+1 -1 . i+j -l bi:j — (iljll)-l ( ) A: P%A( i ) |ATsi+j+1 z (bL(CUP), A\(CUP) +bL ) 'ng\P c ,A\C =1 Then by separation; bf j =(1le-‘4l-l)-l Z (1+i+1)-1 §A(ii+j)_1 ’ AcL P |ATéi+j+1 bL . . CC§\Pb (CL/P), A\ (CUP) 4» (iljll)-1AZJ (1+1).+1)_1 ' L ICTfl |A =i+j+l 2 (14-3)”1 2: bL PEA 1 CCA P C,A\C . NOW: Since (i+i+l”i;j’ = (1315“?) = (“9+1Hi) and since \ =‘CZI 2k , Pacffipé iPEAC — L ‘ i“"341 -l i+l —1 bi,j — (iljil); 4:1 ( 1+1 ) ( l ) IATsi+j+l 4.22 .‘ L 2, 23 b |L| -1 ICT=i . . .-l .. + .. L (1 {+1) 1(1) 2: 2: bf; A\c AcL CcA PeA\C ’ |AT=i+j+1 |CT=i Furthermore, 23 Z; Z) L, for D = CLJP yield ccA PeA\C D PED |CT=1 |DT21+1 . . . -1 L __ |L| -l 1+j+l -1 1+1 bi,j " (i+j+1) AZL ( 1+1 ) 2’ ( l ) |Af;i+j+1 |DT=i+l L |L| -l i+j+1 -1 Lb +(. . ) Z ( . ) PED D,A\D i+j-+1 Ad 1 |AIEi+j+l . ' —1 L L (3) 2: b . 1 P€A\C C,A\C c [Cfii L Then since b is constant for each P 6D and since D,A\D bg,A\C is constant for each P EA c, bij = b§+l,j+bi,j+l' // 'Eggg: If all the b§,0 can be calculated for a given set L relative to a given t-design, then by the Pascal property (6.6) all bi,j can be calculated. Then one may conclude facts from the other b£,j for j #’0, especially those for- i+j = |L| . This process can work in other ways as well, (3.9, if the bi,j can be found for i+j = |L| then the bi,0 may be calculated. §4.7 t—Designs with dzdO Throughout this thesis we shall deal with various t-designs having the property that bE+1 0 = 1 for every J block L of a design. This property means that each (t+1)- set is contained in at most one block, or equivalently that columns of the incidence matrix for the t-design are a distance at least 2(k-t) apart when considered as vectors“ Hence we have now proved: (7.1) Lemma: Vector columns of the 0,1 incidence matrix for a t-design have distance 2_2(k-t) from one another iff bL = 1 for the generalized block intersection t+1,0 numbers of the t-design relative to a given block L of the design. Remarks: If b: 0 = l for a given t-design and block L , J the design is a Steiner System. A t—design with bt+1 0 = l. ’ for blocks L is a generalized Steiner system that by Lemma (7.1) has use in coding theory. Lemma (7.1) now serves as a motivation for the following definition. (7.2) Define a t-design with d;;do to be a t-design so that the column vectors of the incidence matrix for the design have mutual distance at least dO . (7.4) L_e_m__r_n_;a_: The 3-(3,8, 16) design of the thirty 3-cubes in the 4-cube is a 3-(3,8,16) design with d218 . L Proof: By the b? . in (5.11) we see that b = 1 so ———-— 1 3 5,0 that d22(8-4) = 8 - // As applications and examples of the concept of a t-design with dlido we establish the following lemmas. (7.5) Lemma: A vector set of vectors of length v and 4.24 all of weight k and of mutual distance dzdO has bO vectors with v—t \7 k (7.6) bOg[ f: ](t)/(t) db do+l for t = (k-T) and d0 = 2[ —-2—] . (d0 = smallest even integer greater than or equal to do) m: For t and d6 defined above (d6 is the even integer 260) , through each t-set can pass at most [if—E] vectors. Given bO vectors, then the average bt for this system of b vectors is O k b ( ) A 0 t __ .123. from (1.8) (v) - th[k-t] t since for each particular t-set btg[]‘-:-}E] . Solving for b0 proves the lemma. // (7.7) Lemma: A vector set of vectors of length v , weight k and mutual distance dzdO and the maximum possible b0 = [13%](Z)/(]:) (according to (7.6) is a t-design. If k -t - . . . also [h] = iii , then the t—des1gn is a (t+1)-—Ste1ner system. Proof: The first part arises from the fact that btg[_—k::] A _ for any given t-set bt = [fig] from the fact that bo is maximal. Hence bt = [E]. dzdO ensures that each (t+1).. t set is contained in a unique block. If also [g] = 3‘5? , then each (t+1)—set is contained. in at least one block. // One could at this point apply Lemma (7.7) to the GOLAY and NR codes and obtain the same result as stated in (3.3) and (3.4). However, the proof given in Section 4.3 is more 4.25 efficient as well as sufficient for our purpose. We shall instead give an example of (7.7) that shall be used later in Chapter 8 . (7.8) Lemma: If T is maximal set of vectors of V(8,2) of weight 4 and having mutual Hamming distance 2’4, then T is a S(3,4,8) design. 8-2 Proof: From (7.6), t = 4-4/2 = 2 . Then bO = [2:3] . 8.7 4.3 the design is a S(3,4,8) . // = 14. Equality holds in the inequality (7.6) so by (7.7), Furthermore, one obtains from the generalized block intersection numbers for this S(3,4,8) design T relative to a block of the design: (7.9) ‘Lgmmg: T as given in Lemma (7.8) is composed of 7 complementary pairs of vectors, with representatives from: distinct complementary pairs having Hamming distance exactlgr equal to 4 . 2529;: Let L be any block of T , then the generalized block intersection numbers for T relative to L are necessarily: (7.10) 14 7 7 3 14 3 l 2 2 l 1 (D 2 O l where bL = 1 = bL since d214 in this design. In 3,0 4,0 (7.10), b3 4 = 1, so the complement of each block is 3 necessarily a block, all other blocks meet L then at distance exactly equal to 4 . // It is important to note that this added condition, with dzid is not necessarily satisfied by a general 0 : t-design. Consider for the moment the 4-(3,6,l6) design of minimum non-zero weight vectors in an XNR code containing Q_(see Remark (3.4)). Since this design has an incidence matrix whose columns are code words in XNR, and since XNR has minimum distance 6 between code words, the design has the "with d216" property. We have constructed numerous non-isomorphic 4-(3,6,16) designs, but we show (after Chapter 9) that there is only one 4-(3,6,l6) desigr: with d>_6 ; that is, there is only one such design which can be embedded in a code. (7.3) So that it will be easier to state later theorems we shall call any 4-(3,6,16) design with d216 an gag: design. One such exists by Theorem (3.9), is explicitly constructed in Chapter 5 and is shown to be unique up to isomorphism in Chapter 9. CHAPTER 5 Automorphism Groups and an EXplicit Construction of the XNR—Design §5.1 Permutation Groups Given a finite set X whose elements are called points, a permutation on X is a bijection x::Xh+X . Under the operation of composition, the set of all permutations on X, S is the symmetric group on X . If X is fixed in a x3 particular discussion and |X| = n, ‘we sometimes write 3n for Sx. A tranSposition is a permutation which fixes all but: two of the points of X and exchanges those two points. .A permutation can be written as a product of transpositions in. numerous ways, but the number modulo 2 of transpositions used is always a constant; hence, a permutation is considered pgg_or 2323 as the number of transpositions needed is odd or even, respectively. The group of all even permutations of Sx is a normal subgroup of index 2 denoted by Ax or A n A permutation grogp is a triple (X,G,i), where X is a finite set, G is an abstract finite group, and i is a lkamomorphic injection i :G-oS We say that G acts on 1X x O (n: G has a (permutation) representation on X . If the luarnel of the injection is trivial, the representation of G 5.1 is faithful and ‘X‘ is the degree of the representation. In practice, for faithful representations, we shall identify G with its image in 8X . An orbit of a point P’eXZ under the action of G on X is the set xG: {xg | 966} . G is transitive on X if all points of X are in one orbit of the action of G on X . Clearly, G is transitive on any given orbit; and a representative of an orbit is simply any member of the orbit. G is k-transitive on X if for each pair of k-subsets of X , [x1,x2,...,xk} and {yl,y2,...,yk} c 2x , there exists an element 9 EG so that xig = yi for i = l,2,...,k . Then by definition it is clear that the concepts of "l-transitive" and "transitive" are identical. A group G is half-transitive on X if there are t orbits for 1Jlumns. Clearly, the set of all permutation matrices is Sn' (2.1) The group of automorphisms, the automorphism group, Aut(N), of a v)(b incidence matrix N is the set of all permutation matrices Pv for which there exists a corre- sponding permutation matrix Qb so that The set {Pv} is a group under matrix multiplication since for given pi, i = 1,2, there exist 0;, i = 1,2, so that 1 2 2 1 _ 1 1 _ (pvpvmmbob) — PVNQb — N . Let D = (X,B) be a t—design. (2.2) An automorphism group of a t-design D is the group of permutations w of the point set X so that for each b EB, b1r EB . As a special case of this definition, we state in particular that the automorphism group of a graph is the group of permutations v of the points (vertices) of the graph so that for each edge {vl,v2}, {v1n,v2w} is also an edge. One can easily establish the following properties: (2.3) The automorphism group Aut(N) of an incidence matrix N for a t-design is isomorphic to the automorphism group of the t-design. are two incidence matrices for a (2.4) If N and N l 2 t-design, then Aut(N1)=*Aut(N2) . $2.5) The automorphism group of a code C is the group of Inermutations w of the standard basis elements, i.e. the coordinate positions, so that for each _v EC, y_1r EC . Since ‘Uie incidence matrix of vectors of C can be arranged as a disjoint union of incidence matrices of vectors of C of each distinct weight class, which matrices are O—designs, we have (2.6) Lemma: The automorphism group of a binary code C is the intersection of the groups Aut(Ck), Vk Proof: Each class Ck of all of the vectors of weight k in C has, as a O-design a group Aut(Ck) of automorphisms. Each of these groups acts on X , the set of n coordinate positions. For each V in the automorphism group of C , n Aut(C) holds necessarily 51k” = wk 6C , so 7r EC fl Aut (Ck) k=O n Clearly for each 7r 6 fl Aut(Ck) , _y_1r EC for each 16C , so k=0 n Aut(C) = flAut(Ck) . // k=O §5.3 Applications and Examples In this section we shall apply some of the definitions given in Section 5.2 to specific examples. Our goal is to construct from the action of the group of translations of V(4,2) acting on the set of 448 dependent 6-tuples of V(4,2) an XNR-design, [Theorem(3.10)], thus establishing the fact that the group of translations of V(4,2) acts on this design. The XNR-design is a 4-(3,6,l6) design with d;16 18ccording to Definition (4.7.3). The points of V(n,2) form an additive abelian group luader vector addition. (3.1) Definition: T(n) is the group of translations on V(n,2), i.e. T§6T(n) is a translation given by (X)T§=X+?$ for each y€V(n,2) (3.2) Lemma: T(n) acts as a regular group on the points of V(n,2) Proof: For two points y,3<_€V(n,2) then gTy = ET); for is equivalent to _x = exa ctly |V(n,2)| y . Hence, there are elements in T(n) . But also, for each pa 1 r y,_x£V(n,2) there is a vector (5+1) , and hence a t ra nslation T(x +1) , so that yT(_x+y) = y+§+y = is . Hence, T(n) is transitive on the points of V(n,2) .// there exist 448 dependent 6-tup1es. These as blocks and the 16 vectors of V(4,2) E: 3L.6—(3,6,16) (3 - 3) Lemma: In V(4,2) as points form design with d24 . Eroof: By the Lemma (4.5.8) we can see that in choosing 6 Vectors to form a dependent set from V(4,2) the first tllree may be chosen arbitrarily, so there are 16, 15, and 14 choices for each of these. The fourth must not be the Sum of the first three, so this may be chosen in 12 ways. The fifth cannot be in the V(3,2) spanned by the first 150 ur, so this may be chosen in 8 ways. The final vector is th en the (unique) sum of the first five. So in total there are 16.15.14.12.8.l/6: = 448 S“ (:11 sets. NeXt we notice that an arbitrary triple of vectors from V (4., 2) may be completed to a dependent 6-set in 12.8.1/3! ways, i.e. b3 = 16 3 since the first three of a dependent 6-set may be completely arbitrarily chosen. So the design is a l6—(3,6,16) design. Let B1 and B2 be any two distinct dependent 6-sets from V (4,2) . Their symmetric difference: (3-4) BlAB2 := (Bl\BZ) b (B2\Bl) i s also dependent and has even cardinality :» 0 . Since no pa ir of distinct vectors over GF(2) are dependent, I B (1le24 . Hence, the design has dz4 . // IL ( 3 - 5) Theorem: T(4) acts on the 448 dependent 6-tuples 0 f points of V(4,2) yielding 28 orbits of 16 dependent 6— tuples per orbit. Each orbit is a 2-(2,6,16) design wi th 628 . Furthermore, T(4) acts half-transitively on th ese 448 dependent 6-tuples. _Prcof: Let ( 3 -6) Q := {§1.§2.§_3..§4,§5:§6 liaise]; = .9} be any one of the dependent 6-tuples. Let also _1’—2: - - ”—6’51 +£2 +3341 +252 +41, . "’931 +255 Qt} _23__1 _33°"32(_5 +5639} —2’°'°’-’56’-’57’l‘s’°°°’§15’9} By simply checking, one sees that |B| = 16 = |A| = [XI , whence, X =A = B . (3-7) Let yeX,y#O. Thenwe claim that |W+x)flo|=2. r y 7! 9, there exists a unique non—zero element of B(=X) so that y = 351 +x2 , say. 111611 | _ x x 1: +x +x x +x +x x +x +x x+ + (Q X) { 2’ l’ l 2 3’ 1 2 4’ l 2 5’ 1 x2 x6} and (0+X) 0 Q = {xl’xz} Hence (3.7) holds. since Q +ycA . But each non-zero element y of X yi e lds (by considering B) a distinct dependent 6—tuple (Q +y), so orbits under the action of T(4) on the 448 :3 ependent 6-tuples have cardinality 1+15 = 16. Each pair of points from Q is contained in Q and precisely one other dependent 6-tuple in the orbit of Q under T(4). Since this property holds for each member of the orbit, each pair of points of V(4,2) is contained in Precisely two members of the orbit. 6~ Hence the 16 dependent tuples in any orbit form a 2-(2,6, 16) design. Finally d 2 8 since, in a given orbit, any pair of dependent 6—tuples 8113 re precisely two points of V(4,2). // (3 - 8) m: For Q being one of the dependent 6-tuples of points of V(4,2) as defined in (3.6) and for any n°n~zero point z €V(4,2) then (Q +_z_) A0 in a 3-cube. Pr 6, 00f: Let Q 3: {£l:_§2:§3:§.4’£5’§6 I '2’ £1 = 9} i=1 men by Theorem (3.5), 2 - 351 +52 say and (Q +5) AQ = {£3’é4’3—5’56’35-1 +§2 +§3v§1 +3.2 +£42§1 +952 +355:251 +52 +36} x3,x4,§5, and £6 are a basis one can easily see that Of 6 2<_-=9.) i=1 1 (Q+g)AQ (using As such, (Q-+§)ZSQ is a copy of V(3,2) within V(4,2) and is therefore by definition a 3-cube. // (3.9) Theorem: An XNeresign exists with T(4) acting transitively on the 16 points of the design. ggggfi: It suffices to construct the 4-(3,6,l6) design as; a set of 7 disjoint orbits. Consider the following 7 dependent 6—tuples: Q1 ‘= {X1’§2:2‘.3:E4’9—‘5—5 ‘ 2 X1 = 9} i=1 Q2 ‘= {—1’—2’-X-3’X—1 —2 —4’ -1+X3 +355’X-1 +54 +195} Q3 :-_- {£12§2:X3’x1+x3+—6’—1+£5+§6’§l+352 +355} Q4 3: {£13.’_{2:§32§1 +354 +§6’-}21+—2+—6’—1 +X3 +£4} Q5 ={X4’X —5’—6’ —1 +X2 +54’351 +933 ”‘Xe’Xl +254 +356} Q6 := (£4, 335,56,x1+x3+x5,x1+x5 +_6,x1+x2 +_6} Q7 ‘= {X4’Xs’i‘6’351 +X4 3—‘5’X1 +X2 +Xs’Xl +X3 +394} ° (3.11) It is straightforward to check that each of these Qi is a dependent 6-set and that any pair of distinct Qi meet one another in either 1 or 3 places. Define D to be the 7.16 = 112 dependent 6-sets, called blocks of D , obtained from the 7 orbits (of dependent 6-tup1es under the action of T(4)) whose representatives are Qi’ i = l,2,...,7 . Since no 2 of the Qi meet on exactly 2 places, no 2 of the orbits coincide Let,for the moment, Q and R be any 2 distinct dependent 6—tuples from among the 448 in V(4,2) . Let .5 be any non—zero point of V(4,2), then Lemmas (3.8) and (4.5.9) imply II M IQfl((R+§)AR)| or 4. Therefore 0 mod 2 mm ((R+g)AR)l But |QF]((R+_§)AR)I= |(Qfl(R+z._))A(QnR)| = (00 (R+§)|+|Qfl (n+5) fl Rl . so that (3.12) (on R| = |Q n (R+£)| modulo 2 Now letting Q and R be blocks of D, (3.11) and (3.12) imply that by considering the representatives for Q and R among {Qi}, i = l,2,...,7, (3.13) |Q n R| e 1 modulo 2 iff Q and R are in distinct orbits. If Q and R are in the same orbit then, by Theorem (3.5), [015R] = 8 . If Q and R are in different orbits then, by (3.4) and (3.13), |QAR| = 10 or 6 . Therefore (3.14) d216 in this design. Finally (3.14) together with Lemma (4.7.7) imply that D is a 4-(3,6,16) design with d216, i.e. by Definition (4(7.3), D is an XNR—design. Now Theorem (3.9) is proved. // PART C: THE NORDSTROM-ROBINSON CODE CHAPTER 6 Equivalence of the Uniqueness of the XNR Code and the Uniqueness of the XNR-Design §6.l Introduction The method of constructing the extended Nordstrom- Robinson cede, XNR, given in Theorem (3.5.4) is not the only' one. J. M. Goethals demonstrated [15] that such a code could be derived from the XGOLAY code. From his work with these codes, Goethals suggested in a private communication that the Nordstrom-Robinson code might be unique. Thanks to his suggestion, we now show that this conjecture is true. Our long proof of the uniqueness of XNR (and NR) is subdivided for convenience into chapters. In this chapter we reduce the question of uniqueness of these codes to that of the uniqueness of the XNR-design, which was defined in (4.7.3). It is then shown that every XNR-design can be described in terms of the geometry of V(4,2) . In Chapters 8 and 9 we show that within ‘I(4,2) the XNR-design is unique up to an automorphism of Aut(V(4,2)) . Finally Chapter 10 is a summary of the various parts of the uniqueness proof. §6.2 Organization 9.5. Chapter 6 This chapter is organized as follows. In Section 6.3 it is shown [Theorem (3.1)] that the set of minimum non- zero- weight vectors in any (16,256,6) code, C , with 9 EC form an XNR-design. Section 6.4 establishes the necessary weight distribution of any (16,256,6) code, C , with 9 EC , and shows that the vectors of weights 10 and 16 in C are the complementary vectors to those of weights 6 and O . In Section 6.5 it is shown that the vectors of weight 8 in C must necessarily be obtained from the XNR-design in a special way. The equivalence of the questions of uniqueness of the (16,256,6) code and the XNR-design is then stated in Section 6.6. §6.3 The Fundamental XNR-Design _o_f Weight 9 Code Words in any (16,256,6) Code C , with QEC . Note that there is no loss of generality in assuming that any (16,256,6) code contains 9, since if C* is a (16,256,6) code with 33* EC* , then C := C* +19” is an equivalent code with Q = 3g" +§* EC . (3.1) Theorem: In any (16,256,6) code C , with 96C, the set of 112 weight 6 code words forms an XNR-design. Pro____g__f: Since 256(1+(1611)+__16(136))_ 2(16- -1) {—3—} any punctured code of C is nearly perfect, by (3.4.11). Then by Lemma (4.3.2), the set of weight 6 code words form a 4-(3,6,16) design with d26, which is, by Definition (4.7.3) an XNR-design. Finally this design has 100 = 4(136)/(§) = 112 blocks by (4.1.3). // §6.4 The Weight Distribution of any (16,256é) code, Q , with _9 EC (4.1) Theorem: Any (16,256,6) code, C , with QEC has 112 code words of weights 6 and lo, 30 words of weight 8, and one code word of weight 16. Such a code has the additional property that the complementary vector to any code word is also a code word. M: Let C be any (16, 256,6) code with 9 EC . Since vector addition is done modulo 2, 9 EC +5 for any coset code C+_z_ . For this reason, for each _z_EC, C+g._ is a (16,256,6) code with _QEC-i-g . Theorem (3.1) then applies also to C-+g. showing (4.2) lemma. The 112 weight 6 code words in any C +5, for _z_EC , are the elements of an XNR-design. This is the key point in the proof of Theorem (4.1). Indeed, many of the proofs of the following lemmas, which eventually prove Theorem (4.1), consider the generalized block intersection numbers for the XNR-design indicated by the weight 6 code words of a C-+§_ coset code for a particular 56C . Useful in establishing the various generalized block intersection numbers needed are the block intersection numbers for any 4-(3,6,16) design: (4.3) 112 70 42 42 28 14 24 18 10 4 We shall now proceed with the series of lemmas which culminate in Theorem (4.16), a restatement of Theorem (4.1). The following two lemmas will be proved simultaneously. (4.4) m: Any (16,256,6) code, C , with QEC contains 15 weight 8 code words, no two of which are complementary. (4.5) BEBE: Any (16,256,6) code, C , with QEC contains at least 36 weight 10 code words. Proofs of Lemmas (4.4) and (4.5): Let EEC be a code word of weight 6 . By Theorem (3.1), the 112 weight 6 code words in C-+z. indicate an XNR-design. Also in the coset code C-rg. is the code word .5 . Let L be the 6-tuple indicated by the vector 5.. Consider now the generalized block intersection numbers for the XNRvdesign relative to 1.. Since the design has d;;6, (cf. Definition (4.7.3)), bio = 1 for each block L . Therefore these numbers, bi,j’ are the same relative to any block of any XNR-design, and are: (4.6) 112 70 42 42 28 14 24 18 10 4 13 ll 7 3 l 6 7 4 3 O 1 From these numbers, the b? j with i-+j = 6 imply that ’ 6;x(i) = 36 blocks of the design meet L in one place, 1.x(g) = 15 blocks meet L in two places, and 3)((§) = 60 blocks meet L in three places. Therefore, of the 112 weight 6 code words in C-+z_, one is z_ and the 36,15, and 60 others are at distances 10, 8, and 6 from 5’, respectively. Adding the vector 5_ to each of these 112 weight 6 code words of C-+§ , we obtain code words in C = C-+§g+§ . Therefore C contains .9 , at least 36 code words of weight 10, and at least 15 code words of weight 8 . The 15 weight 8 code words could not have any pair being complemented, for then the corresponding pair upon addition of z_, would be a pair of weight 6 vectors in C-+§_ at a distance 16 from each other. This is a contradiction, since the distance between two weight 6 vectors is at most 12 Lemmas (4.4) and (4.5) are thus proved. (4.7) .Qggmg: C contains no code word of weight 12 . EEQQE: Consider the XNR-design relative to the 112 weight 6 code words in C . Let ‘3 ‘be any weight 12 vector. Then ‘i-sw is a vector of weight 4, for j_ the all one vector of length 16. Now {jgsg indicates the 4-tuple, M , which gives these generalized block intersection numbers, b. i,j , for this design: (4.8) 112 70 42 42 28 14 24 18 10 4 12+x 12+x 6+x 4-x x where b: O = x = O or 1 . This means that any such .0 4-tup1e, M , is disjoint from at least 12 blocks of the design. Hence, 3 contains at least 12 weight 6 code words of C . Let E_ be one of these 12 weight code words of C . Then in C +35, w+_;_, and _z are code words located at L 0,6 contradiction follows the fact that .3 cannot be a code word distance 12 , contradicting b = O in (4.6). From this of C . Since 3 is an arbitrary weight 12 vector, Lemma (4.7) is proved. (4.9) £3993: Any weight 10 code word in any (16,256,6) code, C , with _Q EC , is the complement of a weight 6 code word in C . grogg: Consider any weight 10 vector 3,. Viewing the complementary weight 6 vector, 13+! , as a 6-tuple, N , in the XNR-design of the 112 weight 6 code words of C , we obtain these b? : ,3 (4.10) 112 70 42 42 28 14 24 18 10 4 12+x 12-x 6+x 4-x x 2+5x-y lO-4x+y 2+3x-y 4-2x+y x-y y -10+15x-6y+z 12-10x+5y-z -2+6x-4y+z 4-3x+3y-z x-2y+z y-z z wa, a weight 10 code vector !_ cannot meet any weight 6 code word at distance 12, since then C-fiy would be a (16,256,6) code with 9 EC and containing a code word of weight 12, contradicting Lemma (4.7) . Hence, (4.11) O=bg6-lo+15x—6y+z and 9 _ N _ (4.12) O - b4,2 x 2y+z . Notice that z is an integer, because b2 0 is simply 1 the number of blocks meeting the set N in all of its points. Moreover, z = l or O , because the 6—set N is either a block or not. These equations (4.11) and (4.12) together with z = 1 or 0 yield the following two possible sets of solutions: Case 1: x = y = z = 1 . Hence, the 6-tup1e N represents a block, i.e. the vector “y is the complement of a weight 6 code vector. Case 2: z 0, y = 5/12, x = 5/6 . This implies that the 6-tup1e meets: (y-z). (g) = (5/12).6 = 5/2 blocks of the design in five places. But since 5/2 is not an integral number of blocks, no such 6-tuple can exist. This proves Lemma (4.9) along with the following corollary: (4.13) Corollary: Any (16,256,6) code, C , with QEC contains a weight 6 code word, whose complementary vector is also a code word. (4.14) _L_eLn_1_n_a_: Any (16,256,6) code, C , with QEC contains 1’, the all one vector of length 16 .Egggfi: Let z_ be a weight 6 code word of C , whose complement j +5_ is also a code word, as guaranteed by Corollary (4.13). Consider C+z_ . Not only are 9 and 112 weight 6 code words in C +_z_, but i = (i+§)+§ (C41 . By Lemma (4.9) all the 112 weight 10 code words are complementary to the 112 weight 6 code words. Since _z_ = 9+; is one of the weight 6 code words in C43, both _z_ and i+_z_ are code words of C+§ . Therefore (i+_z_)+g_ = j_ is a code word of C . (4.15) Corollary: If C is any (16,256,6) code with 9 EC , then the complement of any code word is also a code word of C . £33393: Let g be any code word of C , then c+_w contains 9 and is a (16,256,6) code. Then, by Lemma (4.4), jEC+g . Therefore g+iEC . (4.16) Theorem: (A restatement of Theorem (4.1)): If C is a (16,256,6) code with QEC , then C contains also 112 weight 6 code words, 15 weight 8 code words, no two of which are complementary, together with the vectors comple- mentary to those 1 +112 +15 = 128 code words. 2319;: This is a result of Lemmas (4.2), (4.4) and Corollary (4.15). (4.17) Corollary: Any (16,256,6) code, C , with 96C, has the same weight distribution as any of the coset codes C+_z, for any EEC. Proof: Because C +5 is also a (16,256,6) code with O = _z_+_z_ EC +5 , for any 56C, Theorem (4.16) applies. 56.5 Each XNR—Desigg_Builds a (16,25646) Code in jpst One Wa X To build a (16,256,6) code from an XNR-design, Theorem (4.1) requires that the code be complemented, so the 112 needed weight 10 vectors must form the design comple- mentary to the given design. Then to complete this set of l-+112-+112-+l vectors to a (16,256,6) code, 30 weight 8 vectors must be carefully selected. In trying to establish Theorem (5.2), which says that these can be chosen in only one way relative to a given XNR-design, we shall explore a necessary condition for these "admissible“ weight 8 vectors. (5.1) Define an admissible weight 8 vector to be a weight 8 vector which together with the set of 1-+112-+112-+l vectors given by Q_, the 112 weight 6 vectors in the given XNR-design and their complements preserve the distance condition 626 . (5.2) Theorem: Given XNR-design, then admissible weight 8 vectors (by Definition (5.1)) are symmetric differences in 28 ways of two weight 6 vectors from D which share two coordinate places. uggggfi: Let L be the 8—tuple indicated by an admissible weight 8 vector. By the condition d;;6 , L meets blocks of the XNR-design D in at most 4 places; so b: O = b: 0 = L L L L ’ ’ b7,0 = b8,0 = O . Let b4,0 = x , then the bi,j become: (5.3) 112 7O 14 42 28 14 24 18 10 4 12+x lZ-x 6+x 4-x x 2+5x lO-4x 2+3x 4-2x x 0 -10+le 12—10x —2+6x 4-3x x O 0 -28+35x 18-20x -6+10x 4-4x x 0 O O -56+70x 28-35x -lO+15x 4-5x x O O O O . L From —56+70x = b and 4-5x = b? 5310, 'we learn that 9 0,8?—0 x = 4/5, showing that the b? j really are: ’ (5.4) 112 70 42 42 28 14 24 1s 10 4 64/5 56/5 34/5 16/5 4 /5 6 34/5 22/5 12/5 4/5 0 2 4 14/5 8/5 4/5 0 o o 2 2 4/5 4/5 0 o o o o 2 0 4/5 0 o o 0 From the b? values with i-kj = |L| = 8 we can now see : that an admissible weight 8 vector meets a weight 6 vector in either 2 or 4 places. But these bi,j tell us even more. Let us view the incidence matrix N of the design D as sectioned into two halves, upper and lower, according to the 8—tuple L . Then we have Figure (5.5) Fr— 3’ _ L" Here the x)(112 matrix A represents those parts of the blocks of D meeting L, and B represents those parts missing L . Matrix A can further be divided into two parts according to its parts of blocks of weight 2 and its parts of weight 4. After permuting the blocks so that all the weight 4 parts occur to the left we obtain: A4 A2 1L . B B Figure (5.6) 2 4 Here A = [A4,A2] and A represents a design of weight 4 4 blocks on the 8 points of L while 82 represents a design of weight 2 blocks on the other 8 points (which comprise the rest of the blocks of D through A4 .) Since D is a 4—(3,6,16) design, each 3 points of L must be located in precisely 4 blocks of A . These blocks must be all in A4, so A4 is necessarily a 4-(3,4,8) design. Since a 4-(3,4,8) design has b2 = 12 while design D has b2 = |L|, each pair of points from L must occur twice as a block in design A2 . Thus, A2 actually consists of two copies of the complete pair design from 8 points. Denote A2 by [(3),(g)] to indicate that each pair of points from L is a block of A2 occurring twice. By exactly the same reasoning relative to the other 8 points, not contained in L, B 2 is two copies of the complete (3)- design, and B4 is a 4-(3,4,8) design. Now we wish to show that the two blocks of 82 representing any fixed pair of points from the complement L' of L, are attached to complementary, disjoint weight 4 blocks of A Once this is shown, we have the fact that 4 . L is necessarily the modulo 2 sum or equivalently the symmetric difference of two weight 6 blocks of D , which meet each other on two places - the fixed pair from L' . In fact, since this must be true relative to any fixed pair of points chosen from L' , L is the symmetric difference in 28 ways of two blocks of D , which share two places since 28 = (g) is the number of pairs from L' It suffices now to fix our attention on a pair of points, say points 1 and 2 from L' , the complement of set L . Choose also an arbitrary point, say a , from set L itself. (5.7) Claim: The sub-design of B4 corresponding to exactly those blocks of D passing through B4 and containing point a is a l-(3,4,8) design. Proof: Consider the design A2 . This design has b = 14 3 1 so a is contained in 14 blocks of D which pass through B4 . Now consider the design E of the 14 blocks of B4 on the 8 points of L' . Since blocks of weight 2 in A2 and all containing a differ in at most one place, such blocks have Hamming distance 32 , when considered as vectors. Yet blocks of D have Hamming distance :16 . So the 14 blocks of E have Hamming distance 234 . Now lemma (4.7.7), applies with [%E%] = %E%' so that E is a l-(3,4,8) Steiner system. This proves the Claim (5.7). // Since by (5.7) E has b2 = 3, the triple of points {a,l,2} are contained in precisely three blocks of D passing through A2 . As such, that triple {a,l,2} is necessarily contained in a unique (1 = 4—3) block of D passing through A4 . (5.8) This can be interpreted as: Given the pair {1,2} from L', then each point a of L , the triple {o,l,2} is contained in a unique block of D and meeting L in four places. Finally, we notice that there are two blocks of D meeting L' in precisely {1,2} and meeting L in four places. By (5.8) the 4-tuple parts of the two blocks of D in question must be disjoint and complementary, relative to L . This proves the theorem. // (5.9) Theorem: Each XNR-design builds a (16,256,6) code C uniquely. .ggggg: According to Theorem (4.1) to form an XNeresign D one must choose the vectors .Q,, i, and the 112 complements of the weight 6 vectors indicated by D . Furthermore, by Theorem (5.2) one may choose as admissible weight 8 vectors only those vectors of weight 8 which are symmetric differences of weight 6 vectors meeting one another on precisely two places. By the bi,j for a block L of design D , as listed in (4.6), each weight 6 vector meets exactly one other block in each of its (3) = 15 pairs; so each weight 6 vector- meets 15 other weight 6 vectors in precisely two places. Choosing the weight 6 vectors in turn gives 112.15/2: = 840 admissible weight 8 vectors. But again by Theorem (5.2) eadh of these must be formed as a symmetric difference in 28 ways, so there are but 840/28 = 30 admissible weight 8 vectors possible. By Theorem (4.1), all of these must be used to complete design D to a (16,256,6) code. // §6.6 Conclusion Restating the previous Theorem (5.9) in a form more suitable for later use we have: (6.1) Theorem: The (16,256,6) code is unique ( up to a permutation of the 16 points of the design) if the MIR- design i 3 unique . CHAPTER 7 Coordinatization of the XNR (16,256,6) Code by V(4,2) §7.l Introduction By Theorem (6.6.1), we need only show that the XNR- design is unique in order to conclude the uniqueness of the XNR (16,256,6) code. Proceeding towards this goal we show in this chapter that the vectors of the XNR (16,256,6) code can always be viewed as characteristic functions of dependent sets in V(4,2), Theorem (5.1). Then combining Theorems (6.6.1) and (5.1), it can be seen that any XNR- design is embeddable in V(4,2). This reduces the problem to studying PG(3,2) and V(4,2) in order to see that the design is unique. Chapters 8 and 9 accomplish this latter part of the uniqueness proof. §7.2 Coherent 4-Tup1e Vectors The concept of coherent 4-tuples is important in the analysis of the design of the weight 8 vectors from the XNR code as well as essential in building the S(4,7,23) design from the XNR—design. Briefly described, the coherent 4-tuples are precisely all those 4-sets not contained in any block of the XNR-design. we shall now define these care- fully and show that there are 140 such coherent 4-sets weight 10 vectors of XNR are precisely the complementary vectors of the weight 6 vectors of XNR (Lemma (6.4.9)), any weight 8 vector meets 56 weight 10 vectors of XNR at distance 6 and the other 56 weight 10 vectors of XNR at distance 10, respectively. Then by the Theorem (6.4.1), any weight 8 vector of XNR must meet other vectors of the set B of weight 0,8, and 16 vectors of XNR at distance 8 or 16. One now sees that the code fi- has minimum distance 8 and contains, for each 3563 a vector also of 3 and at distance 16 from ‘m . This means that the complementary vector thi is necessarily in 3 , and that B is therefore complemented. // (3.4) Lemma: The 30 weight 8 vectors of XNR (16,256,6) fbrm the columns of a 3-(3,8,16) complemented design with 62:8 . gmggj: Since the complement of a weight 8 vector is again of weight 8 and since code 3 is complemented, the design C corresponding to the weight 8 vectors of XNR is a complemented design. Considering weight 8 code vectors as 0,1 incidence matrix columns, choose any three of the rows of this 16 x30 matrix. Assume that these three rows are contained in at least four blocks, B B 83, and B4 , where blocks 1’ 2’ are the sets of cardinality 8 given by the ones from the columns of the matrix. Then §7.3 The 3—(3,8416) Design with d28 afthe Weight_8_ Vectors 9f XNR (16,256,6) and the Reed-Muller Code Q_ with Parameters (16,32,8) (3.1) Given the XNR (16,256,6) code, let ,Q_ be the sub—code of weight 0,£3, and 16 vectors. Then 3, is a (16,1+30+l,d) code for d to be yet determined. we shall now show, Lemma (3.3), that d = 8 . (3.2) 3’ is referred to in the literature as the §i£a£_ order Reed-Muller code of length 16 (cf. Petersen [30], Berlekamp [3]). (3.3) gamma: y as defined in (3.1) has minimum distance 8, and is a (16,32,8) complemented code (i.e. the complementary vector to each vector of the code is again in the code). ggaaj: By Theorem (6.4.1), the XNR code contains 30 vectors of weight 8 and 112 vectors of weight 6 and 10, respectively. Considering the 6-sets and 8-sets for which the weight 6 and 8 code vectors are characteristic functions, we see from the generalized block intersection numbers for the XNeresign B of those 6-sets relative to a given 8-set L (cf. (6.5.4)) that L meets 6-sets either in two or four places. More- over, L meets precisely 2. ( g) = 56 of the 6-sets in two places and g. ( 3) = 56 of them in four places. Translated into terms of vectors, any weight 8 vector of XNR meets 56 weight 6 vectors of XNR at distance 10 and the other 56 weight 6 vectors of XNR at distance 6. Since the which together form a S(3,4,16) design. (2.1) Let D be the XNR-design. Since d;16, b2,0 is equal to 1 for any block L of the design (cf. (6.4.6)). In other words, each 4-set from the set of 16 points is contained either in one unique block of D or not at all. (2) Define a 4-set to be a coherent 4-tup1e relative to D if the 4-set is contained in no block of D . A coherent 4-tup1e vector is then the characteristic function vector of a coherent 4-tup1e. (2.3) ££Efl2= The coherent 4-tuples relative to the given XNR-design D form a l-(3,4,16) or S(3,4,16) Steiner system. There are 140 such coherent 4-tuples. .2522£= Since each 4-tup1e of D , cf. (2.1), is contained in at most one block of D , there are (146)-112( 2) = 140 coherent tuples. Any 3-tuple is contained in four blocks of D , say Ai,i = l,2,3,4 . Since |.C) Ail = 15, the 3-tuple plus the remaining 16gb point f::m a 4-tup1e, which is contained in no block of D (since the four blocks, .Ai, are the only blocks containing the 3-tuple). Thus each 3-tuple is in at least one coherent 4—tuple. But an average indicates 14o.(§) A 1’3“ l6 ‘1' (3) Thus, the 4-tuples form a l-(3,4,l6) design. // 4 4 lJ B- = 23 B. - Z, B.{WB. ~+ 11:1 1| 1:11 .1 igjl 1 ,I I I4 I z: |B. (78.0 - B. 1757474 1 3 Bk 4:1 1 e 4.8-6.4+Z}|BiflBjflBk| - I121 Bi| Since |BiflBjflBk| = 3 or 4, |UBi|zl7 , a contradiction. Therefore no 3-tuple of rows is contained in more than 3 blocks. However, A 30.(f;) 133 = ——(T6—;- = 3 , from (4.1.8) 3 Thus b = 3 and the design C is a 3—(3,8,16) design. Finally, since these weight 8 vectors are all contained in code 3' with minimum distance 8, C is a 3-(3,8,l6) design with d28 . // §7.4 The Linearity and Uniqueness a§_the Reed-Muller (16,32,8) Code A; Contained i2 XNR (16,256,6) As a consolidation of the Lemmas (4.3) and (4.4) in this section we prove: (4.1) Theorem: The (16,32,8) code 3' formed by the weight 0, 8, and 16 vectors of a (16,256,6) XNR code is linear and unique up to a permutation of the 16 coordinates. (4.2) .Efiflfléfi For C being the 3—(3,8,16) design with d218 corresponding to the weight 8 vectors in XNR, any three points of the design are contained in a unique coherent 4-tuple which is in turn contained in precisely three blocks of C . Proof: Choose any weight 8 block B . Choose any three rows incident with B . There are four weight 6 blocks, A A A and A incident with these three rows. Each 1’ 2) 3’ 4 ) of these Ai meets B in exactly 4 places, because the correSponding weight 6 code vectors meet the weight 8 code vector in either 2 or 4 places. This gives 4 |(U Ai)nB|=7. i=1 Therefore, the BEE-row incident with B together with those 3 rows form a coherent 4—tuple of rows. Furthermore, all of these four rows are incident with B .// (4.3) LEEEE‘ 3’ is a linear code. Proof: Consider any two vectors and 52 in B . If 51 either of these is ‘Q or “i, or if these vectors are complementary, then their sum is also in §_, since 3 is a complemented code. Let ~51 and 52 correspond to two non-complementary weight 8 blocks, B1 and B2 . Since 51 and 52 are at distance 8, |B1r1B2| = 4 . Now considering any triple of rows incident with BlrWBz, one can see that BlflB2 is a coherent 4-tup1e by Lemma (4.2). But furthermore, the three rows are incident with also a third block B of the 3 3-(3,8,16) design with d;18 . Therefore 131013an3 = 31032 = B10133 = 1320133 Let a3 be the weight 8 code vector corresponding to B3 Then al-+zz = ig+£3 which is in 3 . Hence, 3 is linear. // (4.4) Lemma: Up to a permutation of the 16 basis coordinate positions of V(16,2), the code fl is unique. ggaaf: Since 3 is linear, fi can be linearly generated by a 5)fi . _P_r_g_<_>_f_: That XNR 3.0 is by definition. 6 depends only on fi-, not on all of XNR, and, in fact, 6 is the orthogonal space to 3 in V(16,2) . Since each weight 8 vector of XNR meets weight 6 and 10 code words of XNR in an even number of places, and meets other weight 8 code words in an even number of places, 3 is orthogonal to XNR . Hence 5 3 XNR. // We now define the mapping a needed for Theorem (5.1). Let G* be the matrix G less the row 1.. Then as in (4.8), up to a permutation q, E816, the symmetric group of all permutations of the 16 standard basis vectors of V(l6,2), G*, can be given as: (5.5) roooooooo1111111f 0000111100001111 O O l 1 O 0 1 1 O O 1 1 O O 1 1 LO 1 O l O 1 O 1 O 1 O 1 O 1 O {J For the matrices G and G* as given above, define the one to one correspondence: (5.6) a :21 4 (Mai) = {Bi} c V(4,2) where 9i = (0,0,...,l,0,...,0), theebasis vector of V(16,2) with a single one in the iEh’ place, and where Bi is the iEE' column of G* . Now extend this definition linearly to all vectors of V(16,2) by 16 (5.7) Mir; xiai) = Umi | xi 1}. For example, a(al-+az) = {21,22} . Thus, a is a well- defined linear map of V(16,2) onto 2V(4:2) (5.8) Lemma: 5 is the Extended Hamming code '54 of length 16. V(4,2) Proof: Define the subsequent map: B :2 » V(4,2) by B=221 =23 eV(4,2). i,j = 0.1.2....,15. Then Boa, the composition of first a and then B , is a linear homomorphism of V(16,2) onto V(4,2) so that (5.10) (600035 = G*g<_ . It follows from the fact that G* is the matrix G less the row containing 1. and the definition of 6, (5.3), 1 that 6 c (50a)- (9) . Therefore all vectors of 6 are characteristic functions of dependent sets in V(4,2) . But moreover since vectors of a are also orthogonal to j. as well as merely G* , the entry in the 20 coordinate place is either 1 or 0 so as to make the weight of the entire vector even. So combining Lemma (2.6.3) with this last statement, 6 is necessarily the parity check code C; of the Hamming C4 of length 15. // For the rest of this section assume that the map a is defined as in (5.6) and (5.7) and is that described in Theorem (5.1). (5.11) LEEEE‘ The weight 6 vectors of XNR are the characteristic functions of 112 of the 448 possible dependent 6-sets in V(4,2). These dependent 6-sets are symmetric sums of pairs of planar 4-sets in V(4,2) which span all of V(4,2) and which intersect in one point. 3599;: We have seen in Lemma (5.3.3) that there are 448 dependent 6-sets in V(4,2). Since by Lemma (5.4) and Theorem (5.1), XNR CHE all the weight 6 vectors of 4 .9 XNR correspond to some (in fact 112) of the possible dependent 6-sets in V(4,2). Let a typical dependent 6-set be {351,352,353,§4,§5,§6},L . Choose any three of these, say {filLEZLEB} = M . Then there is a unique fourth point m7 from V(4,2) so that MLJ[§7} is a dependent 4-set in V(4,2). Note that a? is not already in L since a dependent 6—set by Lemma (4.5.8) was shown to have no four of its points in a plane. If 58 is the unique point completing L\\M to a plane then de CC nt 4. Wh th 131: set union ((L\\M)LJ{§8])LJ(MLJ{§7}) = {5i |i = 1,...,8} is also dependent. Then the symmetric difference LA{xi [i = 1,...8} = {x7,x8} is also dependent. Then the symmetric difference Lllfmi | i = 2,...,8} = {57*E8} is again dependent showing that [as = 57 . In this way, L is the symmetric difference of two planar 4-sets sharing one point. Finally these two planar 4-sets span V(4,2) because their union contains L which spans V(4,2) by Lemma (4.5.8). // (5.12) gamma: Under a , coherent 4—tuple vectors defined from the weight 6 vectors of XNR (cf. Definition (2.2)) are the characteristic vectors of all the 140 planar 4-sets in V(4,2) . .ggaag: Let L be any 8—set of V(16,2) corresponding to a weight 8 vector of XNR , and let C be the 3-(3,8,l6) design with d;;8 of all such 8-sets. Let B be any coherent 4-tup1e. Viewing the generalized block intersection B numbers bi for the design C relative to the coherent ) 4-tuple B we have: (5.13) 30 x 3—x 4+x 3-x x where b2 0 = x . By Lemma (4.2), if any three points of .9 B are contained in L , B c L , we have b? 1 = 0 = 3-x so .9 that x = 3 . Consequently b? 3 = 0 and B meets every 2 block of C in an even number of places. Therefore for every coherent 4-tuple vector y EV(16,2), y is orthogonal to the code fi of all weight 0,8, and 16 vectors of XNR. Hence, _yega =IE4 by Lemma (5.8) and y_ is a characteristic vector of a dependent 4-set or planar 4-tup1e in V(4,2) by Theorem (5.1). Since there are 140 coherent 4-tuples and the same number of planar 4-sets in V(4,2), a identifies these sets. // (5.14) gamma: Under a , weight 8 vectors of XNR are characteristic functions of the 30 copies of V(3,2) in V(4,2). Egaag: Again using Lemma (4.2) we shall see that if three points of V(4,2) of a planar 4+set are contained in the image 8-set under a of a weight 8 code word in XNR, then all four points of that planar 4-set are contained in that 8-set. This implies that each 8-set arising in this way is the linear span of its points. Since any 8-set in V(4,2) contains four independent points, the span of these is a V(3,2) which must coincide with the 8-set. There are 30 copies of V(3,2) in V(4,2), so a identifies these sets. // (5.15) Theorem: The stabilizer group of fi in 816 (the symmetric group of all permutations of the 16 coordinates of V(16,2)) is a degree 16 representation of Aut(V(4,2)) . 2592;: Let y = BOG:V(16,2) a V(4,2) for a as in (5.6) and (5.7) and for B as in (5.9) be the linear homomorphism given by H35) = (600:) (as) = G*35 with 0,6, and G* as in (5.5) . Aut(V(4,2)) is the set of motions w of V(4,2) preserving linear dependency. Thus, for each W EAut(V(4,2)), {1) E816 and y-1 stabilizes 6 . Since y-1¢(G*) = 6* only if W = l, the group fi'c $16 which stabilizes 6 has no more elements then the number of distinct generator matrices i G = for 6 . 6* This number is 30.28.24.16, since that is the number of ways of choosing 4 linearly independent vectors of 6 that together with .1 form a basis of 'fi-. Consequently, |3| g 30.28. 24. 16 . But 3' contains a subgroup isomorphic to Aut(V(4,2)) which has the same order. Hence J's Aut(V(4,2)). // CHAPTER 8 Coordinates for Lines of PG(3,2) §8.l Introduction In order to show the uniqueness in Theorem (9.5.1) of the XNeresign within the context of V(4,2) and PG(3,2), we need to use the fact that the alternating group A7 operates transitively on the 35 lines of PG(3,2). Therefore we shall establish in this chapter the classical isomorphism PLS(4,2) 8 A8 and determine eight coordinates for lines of PG(3,2) . The classical isomorphism making possible the needed coordinatization was early known to group theorists, (cf. Dickson [l3], and as early as 1910 was interpreted in a geometrical context by Conwell [10]. Perhaps this geometrical representation was forgotten, for the same sort of work was duplicated by Edge [14] in 1954 and just recently duplicated independently (for different goals) by Jonsson in [19] and Seidel in [S] and [6]. A seven coordinate system for lines of PG(3,2) was introduced by Gleason in a very efficient manner in 1952 (cf. Wagner [38]). This development would suffice for our purposes, but we shall instead develop these coordinates in 8.1 a new manner which will lend a bit more insight into the geometric counterparts of these seven and eight coordinates for lines of PG(3,2). §8.2 Eingigg P§(5,2) within V(8,2) (2.1) Given V(8,2), consider the set of all even weight vectors. These form a V(7,2) within V(8,2), in 8 fact, the hyperplane 2335. = 0 . i=1 (2.2) Define a relation "~" by _x_~y if y_=_x_ or y=3c_+j_, where j is the all—one column vector of length 8. (2.3) This relation is easily seen to be an equivalence relation. NOw define "+" and "." for these equivalence classes: (2.4) <5> + <1> == <35 + 1> 35,1EV(7,2) (2.5) 1(5) := < u> §€V(7,2), 1 eGF(2) . Now it is clear that the set of equivalence classes under ~ of V(7,2) with the "+" and ".“ operations defined in (2.4) and (2.5) form a V(6,2) . (2.6) Finally by restricting our attention to the vector equivalence classes other than <9) we have a copy of PG(5,2) contained in V(8,2) . Remark: This relatively strange way of locating PG(5,2) within V(8,2) is contrived so that we can within this setting show PSL(4,2) = A8 . §8.3 The Klein Quadric The 128 vectors in V(7,2) considered in (2.1) have length 8. There are (2) = 70 weight 4 vectors, (3) = 28 weight 2 and weight 6 vectors, plus the Q and i vectors. It is convenient to subdivide these by 8 (3.1) 0(fi) = _Z) xixj = 0 where [a = (xl,x2,...,x8) 1) = 1 iff 35 has weight 2 , 0 iff x has weight 4 . o(<_=5>) we can relate the quadratic form a given in (3.1) to the Klein quadric (cf. [1] or [35]) in PG(5,2) as follows. Under the transformation: (3.4) y1 = x3-+x5-+x8 , y5 = x2-+x3-+x y2 = x4-+x6-+x8 , y6 = x1-+x4-+x7 y3 = x2-+x6-+x7 , y7 = xz-rx4-kx5 x1+xS +x8 , y8 = x1 +x3 +x6 8 (305) i§jxixj = Y1Y2+Y3Y4+Y5y6+y7Y8 showing that n is a hyperbolic quadric (cf. [1] or [35]) in V(8,2). This transformation maps even weight vectors onto even weight vectors and the all one vector onto itself. Then by considering the equivalence classes under ~ (in (2.2)), one may set (3.6) y8 = 0 and see that Q = 0 corresponds to (3.7) y1y2+y3y4+y5y6 =0 in PG(5,2) This statement (3.7) is equivalent to E. Artin's definition of the Klein quadric in PG(5,q) for q = 2, cf. [1] . Therefore we may define: (3.8) K = the Klein quadric = { EPG(5,2) | n(<_x,\) = 0] or equivalently, due to (3.3). (3.9) K = the Klein quadric = [(35) EPG(5,2) [ |35| = 4] . §8.4 Graph Theory Definitions (4.1) A agapm is a pair (X,B), where X is a set of elements called vertices, and E is a set of pairs of elements from X called aggaa. (4.2) The edges determine an adjacency relation, so that two vertices, v1, v2, of (X,B) are adjacent iff the pair {v1,v2} is an edge. (4.3) A graph is connected if there exists a finite sequence of edges of the form {[v1,v2],[v2,v3],...,{vn_l,vn}} for each pair of vertices v1 and vn in (X,B) (4.4) A complete graph is a graph whose edge set contains all pairs of vertices. (4.5) A cligue in a graph (X,B) is a complete sub-graph. (4.6) A maximal clique in a graph (X,B) is a clique which cannot be augmented by another vertex and remain a clique. §8.5 The Graphs .g and ‘H and their Maximal Cliques In our representation of PG(5,2) within V(8,2) given by (2.6), we have the Klein quadric, K, given in (3.8). On K and off K we may define two graphs G and H as follows: (5.1) Let G = (XG’EG) be the graph whose vertices are the 35 points of’ K and whose edges are given by the adjacency relation: <35) is adjacent to iff Q(<§_+y>) = 0 for all (95> and (1) on K . (i.e. for all (a) and (y) so that (“(5,3) = 0()=0 .) (5.2) Let H be the graph H = (XH’EH) whose vertices are the 28 points of PG(5,2) of K , i.e. those <35) of PG(5,2) so that Q() = l , and whose edges are given by the adjacency relation: <_x_> is adjacent to iff Q() = 1 for all (a) and (1) so that n(<§>) = n() = 1 . Then choosing representatives of the equivalence classes, (ggy, to be weight 2 or 4 vectors of V(8,2), as in (3.3) we see that equivalent definitions of the adjacencies for G ~and H can be given as: (5.3) (a) is adjacent to (y) in G iff is also of weight 4 (as both <95) and (y) are), (5.4) (33> is adjacent to (y) in H iff <§+y> is also of weight 2 (as both (35> and <1> are). Consider now cliques in G . These by Definitions (3.9), (5.1), and (5.3) are sets T of equivalence classes of complementary weight 4 vectors in V(8,2) with mutual Hamming distance exactly equal to 4. By Lemmas (4.7.7) and (4.7.8) such a set T is a S(3,4,8) whose 7 sets of complementary weight 4 vectors form a clique in G which is maximal, by Lemma (4.7.6). 'Thus, we have: (5.5) gamma: Maximal cliques in G are precisely all the sets of 7 points of the Klein quadric K (cf. (3.8))in PG(5,2) so that their 14 vector representatives from V(8,2) form all the distinct S(3,4,8) designs T in V(8,2) Maximal cliques in H are easier to handle.. Vertices of H are equivalence classes of complementary pairs of vectors of weight 2 and 6 in V(8,2), by (3.3). Furthermore, two such classes are adjacent iff their weight 2 representa- tive vectors share preciesly one coordinate with entry 1 from GF(2), by (5.2) and (5.4). Then considering simply the combinatorics of choosing representative vectors in a maximal clique one Obtains: (5.6) gamma: Maximal cliques in H are of two types: Type 1: three vectors whose vector sum is (Q) Type 2: seven vectors no three of which sum up to <9.> .ggaag: If a third vector in the clique is the vector sum in V(6,2) of two others in the clique, then the maximal clique of Type 1, containing these three vectors, is simply this set of three. If no vector of the clique is the vector sum of any two of the others in the clique, then all vectors of the clique of Type 2 must, in the V(8,2) representation, share a fixed coordinate with value 1. Since there are 7 other coordinates possible for the second coordinate with value 1 for the weight 2 representative, such maximal cliques have 7 vectors. // (5.7) From the vector sum definition of linearity in V(6,2), (a), (y), and (a) are collinear iff + + <.z_-> = <9> and iff = <2s>+ = (by (2.4)). This leads to geometric interpretations of maximal cliques in G and H: (5.8) gamma: Maximal cliques in G correspond to coplanar sets of seven points all contained in the Klein quadric K . Maximal cliques of H of types 1 and 2 correspond respectively to lines completely disjoint from K and to sets of seven points not on K which form a simplex in V(6,2) Proof: By (5.7) and (5.1), maximal cliques in G are the linear Spans in PG(5,2) of the 7 points; hence, the points must form a Fano plane completely contained on the Klein quadric K . By (5.6) and (5.7) each Type 1 maximal clique in H is a line of PG(5,2) disjoint from K while Type 2 maximal clique is a set of seven points off K , no three of which are collinear, no four coplanar, no five in a V(3,2), no six in a V(4,2); i.e. a simplex. // §3,6 38 ==- Aut(G) =- 66(+,2) =- Aut(H) In the setting of PG(5,2 c V(8,2) given in Section 8.2, it is particularly easy to establish the isomorphic action of S8 , the symmetric group of all permutations of the 8 coordinate places of V(8,2), with —E(+:2): the group of all motions of PSL(6,2) stabilizing the Klein quadric. The following series of lemmas will complse Theorem (6.4) which says that S8 3 Aut(G) 3 56(+,2) a Aut(H) for graphs G and H as defined in (5.1) and (5.2), and for the Klein quadric defined in (3.8). (6.1) gamma: If chSB fixes each vector of V(8,2) of a given weight class k #'0, 8, then m is the identity permutation of 88 . .gaaag: Let R be the set of all weight k vectors of V(8,2). Since all weight k vectors are present, it is possible to find a pair of weight k vectors agreeing on all but two coordinate places, and this coordinate pair may be arbitrarily chosen. Since m fixes all weight k vectors, m fixes all weight 2 vectors, and the problem reduces to the _case where k = 2. Let S be the set of all weight 2 vectors in V(8,2) . Because in S one can find a pair of weight 2 vectors sharing precisely one coordinate with value 1 and disagreeing on any given pair of other coordinate places and because m stabilizes each pair of coordinate places,¢p must, fix each of the coordinates of that pair. Hence cp = 1 e58 . // (6.2) .gamma: 58 is isomorphic to a subgroup of PSL(6,2) which fixes the Klein quadric (defined in (3.8)), hence S C66(+)2)o 8 3522:: For any cpES8 , cp fixes Q and i . Since 1 is fixed, m operates in a well-defined fashion on complementary' pairs of vectors of V(8,2). Since 9 is fixed, Qp operates on PG(5,2) and so 88 : PSL(6,2) . Furthermore, m stabilizes the sets of weight 2 and weight 4 vectors which are representatives of the equivalence classes which are points of’ PG(5,2) and that set of weight 4 classes is precisely the’ Klein quadric K as defined in (3.7). So ¢€65(+:2): the stabilizer group within PSL(6,2) of K . Finally, this representation of S8 within 56(+,2) is faithful if w fixes all points of PG(5,2), m fixes all the points not on K , i.e. fixes the weight 2 vectors of V(8,2) . Then by Lemma (6.1), cp = 1638 - // (6.3) gamma: S8 operates faithfully as a subgroup of each of the groups Aut(G) and .Aut(H) , where the graphs G and H are defined in (5.1) and (5.2). _P_rc_>_9_f_: Any cpESa preserves linearity of V(8,2) and fixes Q_ and j_. Therefore, by Lemma (6.2), w preserves linearity in PG(5,2). Since m also stabilizes each weight class of vectors in V(8,2), w then preserves the adjacencies in graphs G and H according to (5.3) and (5.4). The proof follows by applying Lemma (6.1) and the fact that vertices of G and H correspond respectivelgr to weight 4 and weight 2 vectors. (For the graph G it is important, in order to use Lemma (6.1), that all 70 weight 4 vectors must be fixed. But if 35 representative weight 4 vectors are fixed, the fact that j. is fixed assures us that the complementary 35 weight 4 vectors are also fixed. ,0/ (6.4) Theorem: S a Aut(G) a 56(+,2) a Aut(H) . 8 Proof: By Lemmas (6.2) and (6.3) we have the faithful injection of S into each of these groups. Each non- 8 adjacent pair of vertices in G determines by linearity in PG(5,2) a unique point not on K with a representative weight 2 vector from V(8,2). So each motion cpEAut (G) induces a unique motion of 56(+,2) c PSL(6,2), which agrees with w on G and preserves linearity. Similarly, since any two non-adjacent vertices in H determine by linearity a unique vector of weight 4 in V(8,2) and hence a unique point of PG(5,2), each mEAut H induces a unique motion —g(+,2) c PSL(6,2) agreeing with m on H and preserving linearity. If p is any motion of '56(+,2), then p in turn induces a unique motion of V(8,2) preserving linearity, stabilizing complementary pairs of vectors of V(8,2) and fixing a, and j_. Hence we can inject each of the groups Aut(G), Aut(H), and ‘56(+,2) into 58 . Finally, these injections are faithful, completing the proof. // Used in the proof is the following fact that will later be referred to: (6.5) Corollary: Each. ¢.EAut(G) extends to a unique motion m* of A8 which stabilizes ‘Q, 1,, equivalence classes of complementary pairs of vectors in V(8,2) and preserves linearity. §8.7 S8 is l-Transitive and A8 is %w-Transitive on the 29_Maximal Cliques 2; Graph g It is well known that the Fano plane, PG(2,2) of 7 points and 7 lines, is combinatorially unique and has an automorphism group of order 168 (cf. [8]). This means that regardless of the numbering of the points of the plane, any two such planes are isomorphic.. Allowing S7 to operate on these 7 points produce 7!/168 = 30 distinct but isomorphic numbering schemes. The fact that these are isomorphic can be restated as the fact that S7 operates on the set of 30 distinct numberings of Fano planes giving one orbit. The most succinct development of this fact is given by wagner [38]. Rather than quoting the literature, we shall prove the needed result in the context of coding theory. (7.1) gamma: Given any S(3,4,8) design T , then its 14 vectors from V(8,2) together with Q. and j. form a linear (8,16,4) code. 3592;: Since for any S(3,4,8) design each triple occurs in exactly one block, two blocks share at most two places and have Hamming distance 2fi4 . Augmenting the 14 vectors of T by Q_ and j_ does not destroy the distance d;14 property, so the set of 16 vectors forms an (8,16,4) code, 5’. According to the generalized block intersection numbers for this design relative to a block L of the design (cf. (4.7.9)), each block is complemented, so, for each 5E5, 35-1-1 is also in “E . Furthermore, since blocks of T meet one another in exactly 2 or 0 places by (4.7.9) and since each of 19 and j_ meet all other vectors in IE at distances 4, or 8, we see that two distinct code vectors of IE are either at distance 4 from one another or are complementary. If two vectors are complementary, their sum is :1 EC . If two vectors a, and ‘y are not complementary, they meet on two places. Since b2 = 3 for a S(3,4,8) design, there is a third vector a_ sharing with a. and ‘y those two places. But since d>_4 , the remaining places of a, y, and a take care of the 6 other coordinate places of V(8,2). As such _:_c+y_ = _z_+j_ which, in turn, is in E . Therefore, E is linear. // (7.2) Lemma: A linear (8,16,4) code C' is unique up to a permutation of the 8 coordinate places of V(8,2). .gaaag: Choose a basis 3 for the linear subspace IE of V(8,2) so that the all-one vector is among those basis vectors, 8 = {1’51*§2*§3} . Let G be an 81x4 zero-one matrix whose columns are the vectors of 5, i.e. G is a generator matrix of IE . The linear independence condition on basis vectors forces '51’-§2’ and_x3 to be of weight 4 and to meet one another on precisely two places, i.e. ai.§j| = 2 for i,j = 1,2,3 . But l51‘-’-‘-2'-3| = l , because if 351’ 352, and a3 (i.e. [351 .352 .353| = 2) meet on two places, §B-+j_= 51'”§2 and if they meet mutually on no places then 53 = ml-tge contradicting linear independence. Now three permutations can be found in S8 , $1: $2: 03 so that ¢1 permutes ml to (§l¢1)T = (0 0 0 0 1 l l l )T, so that $2 stabilizes -§l¢l and permutes §2¢1 to xzmlwz so that (xzolcpzfl = (0 0 1 1 0 0 1 1)T, and so that $3 stabilizes both Elml and I§2¢1¢2 and moves .§3¢1¢2 to .E30102m3 With (£3o1m2o3)T = (0 1 O l 0 l O 1)T . Thus GT always can be put in the form (7.3) F11111111" 'r 00001111 00110011 _010101014 . This shows that IE is unique up to a motion of S8 . // (7.4) gamma: S(3,4,8) is the design of the dependent 4-set in V(3,2). Remark: This lemma is quickly proved in either of two ways: Proof 1: Given V(3,2), each triple of vectors completes uniquely to a dependent 4-set, so the dependent 4—sets form an S(3,4,8), which by Lemmas (7.1) and (7.2) must be unique. Proof 2: Given a design S(3,4,8) and its spanning code C, one can see via the b? . for a block L of the design S(3,4,8) (cf. (4.7.9))’that all blocks meet in an even number of places. Therefore in IE, all vectors are orthogonal to all other vectors from 5'. In this way code vectors of IE are the characteristic vectors of dependent sets in the V(3,2) which vectors are mama of G (columns of GT) as in (7.3). // (7.5) Theorem: 88 operates transitively on the set of 30 copies of S(3,4,8) in V(8,2). 2399;; We see via Lemma (7.2) that a design S(3,4,8) is given by the set of weight 4 vectors in the linear span of the matrix G of (7.3). we shall count the number of distinct but isomorphic copies of S(3,4,8) in V(8,2) under the action of S8 by counting the number of ways of obtaining the generator matrix G . From the complete design of all 4-tuples from the set of 8 coordinates of V(8,2) we must choose vectors 51"52’ andm3 which will together with j_ form a generator matrix isomorphic to G . There are 70 ways that .51 can be chosen. The number of vectors a2 is then the number of 4-tuples from 8 that meet the 4-tuple correSponding to .51 in exactly two places. This number is (‘2’) . (2:3) = 36. Then the number of vectors 53 that can be chosen to meet _xl._x2_,_xl.(j+§2),_2_c_2. (mi-£1), and jgbml-t52-+§l§Z,(1.e. the four d13301nt pairs determined by ‘51 and ‘52) in one place each is 24 = 16 . Hence there are 70.36.16 matrices G . Next we count the number of matrices G that correspond to a particular S(3,4,8) design, T. From T, the 51 may be chosen in 'bO = 14 ways, for the second, since .j,.§1 and .mz must be linearly independent,_x2 may not be the vector jgbml of T . Therefore,gc_2 may be chosen in 12 ways. Similarly due to the linear independence of B = fix§1x§2x§3}:.£3 may be chosen from T in 14-6 = 8 ways as the vectors m1,m2,§1-b§2, and their complements may not be chosen. Therefore, there are 70.36.16/14.12.8 = 30 distinct copies of S(3,4,8) under the transitive action of S8 on these 30 copies. // (7.6) Corollagy: The design S(3,4,8) has an automorphism group of order 8.7.6.4. ggaag: There are l4.12.8 = 8.7.6.4 motions under 58 which stabilize a given S(3,4,8). // (7.7) Theorem: A8 acts éu—transitively on the 30 copies of S(3,4,8) in V(8,2), yielding two orbits of 15 copies each. Egaag: Consider (as in the last Theorem (7.5)) the generator matrix G (7.3) of a S(3,4,8) design T . Given the two vectors 'El and '52 of G , there are 16 ways of choosing the vector .a3 as we saw in the proof of Theorem (7.5). But considering the design T , the 4 vectors 53,351 {153,352 +353,_§1 +352 +353 , and their complements all meet the two vectors ‘51 and ‘52 in such a way that each of these 8 vectors shares just one 1 with each of the pairs 351 . 52’51 . (.1412): 52 . (1 +351) , and j+351 +52 +£12.22 . Therefore, the set Chip-’52} can be complemented in 16 ways to generate 16/8 = 2 distinct copies of S(3,4,8) . Consider now the set of automorphisms q, EA8 which stabilizes 51 and 52 . There are 24 = 16 motions in S8 stabilizing {filtéz} and therefore the 8 motions of A8 which stabilize [51L§2} must yield 8 ways to complete {1951*52} to generate 8/8 = 1 unique S(3,4,8). In other words, under A8*§1 and a2 determine a unique copy of S(3,4,8). Considering just 51’ this vector set {1951} completes to {j,§_1,§2,§_3} in 36.16 ways giving 36/12.16/8 = 6 copies of S(3,4,8) all sharing m1 . But [1,351] completes then to only 36/12.8/8 = 3 copies of S(3,4,8) under the action A8 . Similarly under ‘A8’ [1] may be completed to G in 70.36.8 ways giving 70.36.8/14.12.8. = 15 copies of S(3.4.8) in an orbit under the action of A8 . // (7.8) Corollary: Under the action of A8 on the 30 copies of S(3,4,8), all distinct cepies T and S of S(3,4,8) within one orbit share exactly one pair of complementary vectors {£121N*§11 . 2529;: We see within the proof of Theorem (7.7) that the set [1,51],, completes to 3 copies of S(3,4,8) under the action of A8 all of which copies share only £1 and the complementary vector jgtml . (Since if S and T were to share a1 and £2 7! j+x_1 , then S = T due to the fact that {1’51’52} completes uniquely to a copy of S(3,4,8) under the action of A8.) // (7.9) Corollary: Each pair of equivalence classes of 4—tuples from V(8,2) and adjacent in G is contained in two copies of S(3,4,8), one from each of the two orbits under action of A8 . Proof: Within the proof of Theorem (7.7) we saw that each pair of complementary 4-tuples was contained in two copies of S(3,4,8). // 68.8 Finding PG(3,2) within the Klein Quadric .5 Thanks to the construction given in Section 8.7 we may now locate the points and lines of PG(3,2) to be the 15 maximal cliques in G under the action of A8 and the 35 points of K , Theorem (8.8). As an immediate byproduct of this approach we obtain a proof of the classical group isomorphism A8 a PSL(4,2), Theorem (8.10). Let K be the Klein quadric as defined in (3.8) and G be the graph as given in (5.1). (8.1) Remark: A acts %-transitively on the 30 maximal 8 cliques in G giving two orbits of 15 maximal cliques each, since the statement is merely a translation into terms relative to G of Theorem (6.4), Lemma (5.5), and Theorem (7.7). (8.2) Let M be a fixed one of the orbits of 15 maximal cliques in G under the action of A8 . (8.3) (gamma: In M each point P of K (each vertex of G) is contained in precisely three maximal cliques of G . The 3.(7-l) = 18 points other than P on these three maximal cliques are precisely all the vertices of G adjacent to P . 2329;: Interpreting Definition (3.9) and Corollary (7.8) into terms relative to G , one learns that each vertex of G (each complementary pair of weight 4 vectors in V(8,2)) is contained in precisely three maximal cliques of G (copies of S(3,4,8) in V(8,2)) under the action of A8 . Furthermore, given a weight 4 vector .5 of V(8,2) corresponding to a vertex P of G , the number of vertices Q of G , which are adjacent to P is the number of ways of choosing representatives [y of distinct equivalence classes of complementary vectors of V(8,2) with weight 4 which representatives meet .5 on two places, i.e. [§.,y| = 2 . (This is seen from (3.9).) The number of vectors y_ meeting as on two places is (g) . (g) = 36 , but these fall into 18 classes of complementary pairs of weight 4 vectors, each representative of which meets .5 on two places. So P is adjacent in G to 18 vertices Q . Since the three maximal 8.19 cliques through P under A8 are in one orbit, these maximal cliques share only P with one another due to Corollary (7.8). Hence contained in these cliques are 3.(7-l) = 18 other distinct vertices of G , each being adjacent to P . So all the vertices Q of G adjacent to P lie on these three maximal cliques. // By Lemma (8.3) we may now define a design 9 as follows: (8.4) Let points of 9 be the maximal cliques of M (defined in (8.2)). Let blocks of 0 be the sets of three maximal cliques of M which share mutually a single point. So a point of 0 is incident with a block of 9 if that maximal clique is contained in the set of three maximal cliques forming a block. (8.5) Call blocks of o Iggaaa. Two lines of ‘9 intersect if they share a point of 9 . we have the correspondence of points of K (vertices of G) with lines of 9 . we shall now proceed towards showing that points and lines of 9 are the points and lines of PG(3.2). (8.6) gamma: Vertices of G are adjacent iff the corresponding lines in 0 intersect. Iggaag: Let P and Q be two adjacent vertices of G . By Lemma (8.3) there is just one maximal clique, w , of G through P and containing 0 . So w is the maximal clique of M containing both P and Q . Hence, the lines corresponding to P and Q in 9 intersect. Conversely if two lines of 9 intersect, the corresponding vertices P and Q of G lie on a maximal clique of M and are, by the definition of a clique, adjacent in G . // (8.7) Theorem: The points and lines of 9 form the points and lines of PG(3,2). 2399;: It is well known (c.f. Veblen and Y0ung [37] and Dembowski [11]) that PG(3,2) is characterized by the following axiom system: (i) Each two points determine a line. (ii) Each two lines intersect in at most one point. (iii) There are three points on each line. (iv) (Pasch Axiom) Given any three non-collinear points and the three lines determined by these points, if another line meets any two of these lines then it meets also the third. (v) There are 15 points. From Lemma (8.3) follows (iii). Axiom (v) is by definition. Axiom (ii) follows from the fact that each adjacent pair P,Q of G is contained in precisely one maximal clique of G , due to Lemma (8.3). In order to verify Axiom (i) we proceed as follows. A maximal clique n containes 7 points (Lemma (5.8)) and each of these points is contained in three maximal cliques of M , an orbit under A8 , by Lemma (8.3). So counting, there are 2.(7) = 14 other maximal cliques in M meeting w on a single point. Since A8 is transitive on M , (1) follows. Axiom (iv) follows from the existence of maximal cliques in G other than those from M . Let w1,'n2, and W3 be three non-collinear points of 9 (i.e. three maximal cliques in M). Let 112,113, and 123 be the three lines of 9 determined by those points and let P12, P13, and P23 be the corresponding vertices of G (these are distinct since the points wl,‘n2, and #3 are not collinear). If g is any other line of 0 meeting two, say 112 and 113, lines from [112,113,123], then the corresponding point P of G is by Lemma (8.7) adjacent to both P12 and P13 . But vertices P12 and P13 are in a unique clique of M due to Lemma (8.3), so that P,P12P13 and P23 are all adjacent. Then again by Lemma (8.7), lines 1 and 123 meet. // (8.8) Corollary: The 15 maximal cliques of G other than those of M correspond to the 15 planes of 9 = PG(3,2). gmaag: By axioms (iv) and (v) 15 planes of 0 exist. Each of these is then a set of 7 lines of 9 mutually intersecting. By Lemma (8.7) these 7 lines correspond to a clique of G , but mag_to a clique of M. // (8.9) Corollagy: Three vertices of G which are mutually adjacent are collinear in PG(5,2) iff they correspond to planar fans of lines in PG(3,2), i.e. three lines that are concurrent and coplanar. .ggaag: By Lemma (7.9) two adjacent vertices of G are contained in two maximal cliques, one from each orbit under A8 . Three adjacent vertices which are also collinear are therefore contained in two maximal cliques one corresponding to a point and the other to a plane of PG(3,2) . // (8.10) Theorem: A8 a Aut(G) a PSL(4,2) . 'ggaagz PSL(4,2) is by definition the group of collineations of PG(3,2) A8 <; PSL(4,2): Let (p EA8 , then q; induces an automorphism of G moving vertices while stabilizing each of the sets of points, of lines and of planes. Because of Corollary (8.9) and the fact that w preserves linearity in PG(5,2) and adjacency in G, I; preserves linearity in PG(3,2) Conversely: PSL(4,2) ; A Let EEPSL(4,2), then cp induces a 8' motion m* of G stabilizing each of the orbits of maximal cliques in G under A8 . cp* EAut (G) by virtue of Lemma (8.7). But ¢* extends uniquely to a motion m of PG(5,2) and V(8,2) via Corollary (6.5). Finally q,€ 6(+,2) a A8 due to Corollary (8.9). // (8.11) Corollary: 88 e the group of all collineations and correlations of PG(3,2) = PrL(4,2). Proof: The design 0 of Definition (8.4) is isomorphic to PG(3,2) no matter which orbit of 15 maximal cliques of G under A8 is used. With one of these orbits chosen to represent points, a motion of 88\A8 induces a motion of PG(3,2) preserving linearity but exchanging the roles of points and planes. This motion is a collineation of the PG(3,2) defined relative to the former orbit. Hence, S8 c PrL(4,2). The converse inclusion is similarly shown. /7’ §8.9 Eight Objects in PG(5,2) Permuted by PSL(4,2) 3 A 8 Now that we have PSL(4,2) e A (Theorem 8.10), we 8 can recall the definition of the graph H (5.2) and the Lemma (5.8) stating that there are eight simplices of PG(5,2) disjoint from the Klein quadric K (3.8), which eight simplices not only have their 7 vertices located off K , but also (by Definition (5.4)) their (3) = 21 third points on the (g ) = 21 lines joining pairs of vertices of such a simplex located off K . There are only 8 simplices of PG(5,2) of this nature, since any such simplex must be a maximal clique of H of 7 vertices. These are 8 geometrical objects in PG(5,2) permuted by PSL(4,2): (9.1) Theorem: PSL(4,2) faithfully permutes the 8 simplices whose 7 vertices and whose (Z) = 21 third points on the l-skeleuxy the set of lines joining these 7 vertices, are totally off K . Egaag: Since by Lemma (5.6) the 8 maximal cliques of graph H from (5.2)) are coordinatized under V(8,2) by 7 pairs of coordinates from V(8,2) which all share one coordinate, these 8 maximal cliques correspond one to one to the coordinates of V(8,2) . Furthermore, these correspond 8.24 to 8 simplices of PG(5,2) whose 8 vertices and 21 third points on the l-skeleton of such a simplex are off K (Lemma (5.8)). Then Theorem (8.10) shows that PSL(4,2) permutes these. The action is faithful because if all 8 simplices are fixed, all the 8 coordinates of V(8,2) must be fixed and the motion must be the identity. // §8.10 Line Coordinates for PG(3,2) and 8 Objects g2. PG(3,2 Permuted gy_ PSL(4,2) It has finally been established that lines of PG(3,2) are permuted by PSL(4,2) exactly as the complementary pairs of weight 4 vectors of V(8,2) are permuted by A8 , and so that lines of PG(3,2) intersect iff representative weight 4 vectors share ones in exactly two coordinate places. (10.1) Theorem: There is a one to one correspondence m from the 35 lines to the 35 sets of complementary 4—tuples from a given set of 8 letters so that PSL(4,2), operating on the 35 lines, is mapped isomorphically to A8 , operating on the 8 letters. Egaag: Let the set X of 8 letters correSpond to 8 standard basis coordinate vectors of a V(8,2) . Then Theorem (6.4) shows that corresponding to Definitions (2.6) of PG(5,2) c V(8,2), (3.8) of the Klein quadric K in PG(5,2), and (5.1) of the graph G in K , A a Aut(G) . Further- 8 more, defining 9 as in (8.4), we have by Theorem (8.7) that 9 is isomorphic as a geometry to PG(5,2) and that PSL(4,2) e Aut(G) a A by Theorem (8.10). This gives a 8 correspondence m between lines of PG(3,2) and complementary' pairs of 4-tuples from the set X of 8 letters via Theorem (8.7), Lemma (8.6), and Definitions (5.2), (3.9), and (2.6), so that lines of PG(3,2) intersect iff representative 4-tuples from X share precisely two letters. It follows that PSL(4,2) =~ A8 under cp . // (10.2) Throughout this section let IX be the set of 8 letters X:= [a,b,c,d,e,f,g,h] on which A8 acts isomorphically to PSL(4,2) according to Theorem (10.1). Since Theorem (10.1) gives 8 letter coordinates for lines of PG(3,2), sets of lines can also be coordinatized by these 8 letters. Since points and planes of PG(3,2) are each characterized by special sets of lines, we have: (10.3) gamma; The 15 points and the 15 planes of PG(3,2) are each coordinatized by the 30 copies of S(3,4,8) in the V(8,2) whose 8 standard basis vectors are the 8 elements of X . .gaaag: Points of PG(3,2) are characterized by the 7 lines of PG(3,2) through the point. Planes are characterized by the 7 lines on that plane. Each set of 7 lines forms a maximal clique of 7 mutually intersecting lines in PG(3,2) and then the pairs of complementary 4-tuples coordinatizing those 7 lines form a copy of S(3,4,8). Then by Lemma (5.5), Definition (8.4), Theorem (8.7), and Corollary (8.8) the result follows. // Now we shall proceed to establish just what sets of lines of PG(3,2) correspond in a one to one fashion to the 8 letters on which A acts. 8 (10.4) Define a spread in PG(3,2) to be a set of lines which are mutually disjoint and so that every point of PG(3,2) is contained in exactly one of these lines. It is clear that there are 15/3 = 5 lines in each spread of PG(3,2) . This definition corresponds to D. M. Mesner's use of the word in [26]. (10.5) gamma: Triples from the set X of 8 letters on which A8 actsisomorphically to PSL(4,2) correSpond under this isomorphism to the (g) = 56 spreads of PG(3,2) . The five lines in a spread all have representative 4-tuples which contains the triple corresponding to that spread. ggaag: Given any triple, say {a,b,c] c X , there are precisely 5 lines of PG(3,2) whose corresponding equivalence classes of complementary 4-tuples from X have a repre- sentative containing [a,b,c} . Since by Theorem (10.1) lines in PG(3,2) intersect iff their representative 4-tuples share precisely two letters, the 5 lines corresponding to [a,b,c] are mutually disjoint. Together the 5 lines contain all 3.5 = 15 points of PG(3,2) , so they form a spread of PG(3,2) by Definition (10.4). To show that the (3) = 56 spreads obtained in this way are all the spreads of PG(3,2) we note that representative 4-tuples for three mutually disjoint lines having their representatives share three letters can be chosen in the following two ways: 8.26 of lines of PG(3,2) correspond in a one to one fashion to the 8 letters on which A acts. 8 (10.4) Define a spread in PG(3,2) to be a set of lines which are mutually disjoint and so that every point of PG(3,2) is contained in exactly one of these lines. It is clear that there are 15/3 = 5 lines in each spread of PG(3,2) . This definition corresponds to D. M. Mesner's use of the word in [26]. (10.5) gamma; Triples from the set X of 8 letters on which A8 actsisomorphically to PSL(4,2) correspond under this isomorphism to the (g) = 56 spreads of pe(3,2) . The five lines in a spread all have representative 4-tup1es which contains the triple corresponding to that spread. gamma: Given any triple, say [a,b,c] C'X , there are precisely 5 lines of PG(3,2) whose corresponding equivalence classes of complementary 4-tuples from X have a repre- sentative containing {a,b,c] . Since by Theorem (10.1) lines in PG(3,2) intersect iff their representative 4-tuples share precisely two letters, the 5 lines corresponding to {a,b,c] are mutually disjoint. Together the 5 lines contain all 3.5 = 15 points of PG(3,2) , so they form a spread of PG(3,2) by Definition (10.4). To show that the (3) = 56 spreads obtained in this way are all the spreads of PG(3,2) we note that representative 4—tuples for three mutually disjoint lines having their representatives share three letters can be chosen in the following two ways: {8.b,C.d } {3,b,c, e ) [a,b,c f} or {a.b.C.d } {a.b.C. e } {a,b, d,e ] . Each of these completes uniquely to a set of 5 representative: 4-tuples for a spread, the first of which has all repre- sentatives containing {a,b,c] and the second of which has the complements of all representatives containing [f,g,h] . Therefore each spread corresponds to one unique triple from X . // (10.6) .EEEEE‘ Two spreads of PG(3,2) share 0, l, or 2 lines of PG(3,2) according as the triples from X corresponding to those two spreads share 1, 2, or 0 letters respectively. ugaaag: The two spreads [a,b,c}, [a,b,d} share only the line [[a,b,c,d] , [e,f,g,h]} . The two spreads [a,b,c] , [d,e,f] both share only the two lines given by {[a,b,c,g] , [d,e,f,h]] and [[a,b,c,h], [d,e,f,g]] . None of the 5 lines of {a,b,c] are among those of the spread {a,d,e] , so two Spreads sharing one letter are disjoint spreads. // (10.7) Definition: The lines in a set of 6 spreads of PG(3,2) which pairwise share one line of PG(3,2) is called a linear complex of lines of PG(3,2) . This definition is equivalent in the setting of PG(3,2) to the definition of linear complex given by Todd in [35], but this equivalence shall not be established as we shall only use the definition as a convenient name. (10.8) gamma: The (3) = 28 pairs of letters of X correspond to the 28 linear complexes in PG(3,2) . .gaaag: There are two types of sets of four spreads of PG(3,2) which pairwise share one line of PG(3,2) . Using Lemma (10.6) these are: {a,b,c } [a,b,c } [a,b, d } [a,b, d} and [a,b, e ] [3, c,d] [a,b, f] [ b,c,d] The second of these cannot be completed to a set of even 5 spreads which pairwise share one line, whereas the first can be completed to the linear complex: {a,b,c [a,b, d [a,b, e [a,b, f [a,b, g [a,b, h Therefore, linear complexes correspond one to one to pairs of the 8 letters of X . // (10.9) 1 spre lettex Eggggz pair (10.1< is a : Spree: 1101, (10.1 PG(3,. £399: Pairs a fix t0 on lette (10.1 of 11 80 th (10.9) gamma: Two linear complexes of PG(3,2) share 0 or I spread of PG(3,2) iff their corresponding pairs of letters from X share 0 or 1 letters reSpectively. Egaag: [a,b] and [a,c] share the spread [a,b,c] . The pair [a,b] and [c,d] share no spread. // (10.10) Definition: A heptad of linear complexes in PG(3,2) is a set of 7 linear complexes which pairwise share one Spread. This name is used by Conwell, Edge, and Jonsson in [10], [14], and [19], respectively. (10.11) gamma: The eight heptads of linear complexes in PG(3,2) correspond to the eight letters of X themselves. .gaaag: Using (10.9) and (10.10), a set of more than three pairs of X which mutually share one letter must all contain a fixed one of the letters of X . So each heptad corresponds to one of the letters of X . // Lemma (10.11) plus the fact that A permutes the 8 8 letters of X faithfully proves: (10.12) Theorem: There are 8 heptads of linear complexes of lines in PG(3,2) which A8 permutes faithfully in a way so that A8 a PSL(4,2). CHAPTER 9 The Uniqueness of the XNR-Design Within the Geometry of V(4,2) §9.l Introduction It is the purpose of this chapter to complete the proof of the uniqueness of the XNR-design, Theorem (9.5.1), by showing that the design can be constructed within the context of V(4,2) in only one way (up to an automorphism of' V(4,2)). Chapter 7 has shown that the weight 6 code words in any XNR code (containing 9) are embeddable in V(4,2), Theorem (7.5.1) and Lemma (7.5.11). From the fact that the weight 6 code words form an XNR-design, Definition (4.7.3) and Remark (4.3.4), it follows that any XNR-design can be embedded in V(4,2). Therefore, in order to prove that the XNR-design is unique, it suffices to show that it can be constructed within V(4,2) in only one way (up to auto- morphism). Within the context of V(4,2), the uniqueness proof proceeds as follows. (First, in Section 9.2, necessary conditions for the existence of the XNR-design, D , are noted. The 112 blocks of D sub-divide into sets of 42 and 70 blocks according as therblocks contain the point corresponding to a EV(4,2) or not. These 42 and 70 blocks form designs 8 and L respectively on the point set PG(3,2) = V(3,2)-[Q] . Moreover these blocks indicate simplices and skew line pairs, respectively, in PG(3,2) Design L gives rise to a one to one correspondence, 5 , between all the lines of PG(3,2) and some of the spreads of PG(3,2) . Then, in Sections 9.3 and 9.4, it is shown that, up to an automorphism of PG(3,2), correspondence 8 and designs L and S are unique. Finally, in Section 9.5, it is shown that the XNR-design D is unique up to an automorphism of V(4,2) . Designs S and L and correspondence 3 , which are referred to throughout this chapter, are defhaed in Section 9.2. As a corollary of the uniqueness of the XNR-design, D , we obtain the fact that D is coincident with the design constructed in Chapter 5, Theorem (5.3.9). This leads to the fact that the automorphism group of the XNR-design is A7-+T(4), i.e. A7 extended by the groups of translations of V(4,2) , Theorem (5.2) §9.2 Necessary Conditions for the Existence a; am XNRsDesigna Designs §. and [g and Correspondence .a Given an XNR-design D , from Theorem (7.5.11) all of the 112 blocks, when viewed as weight 6 vectors in V(16,2) are characteristic functions of dependent 6-sets of vectors of V(4,2) . Since dependent sets in V(4,2) are given relative to QEV(4,2) and since bl = 42 for design D (c.f. (6.4.b)), there are 42 weight 6 vectors of D containing the coordinate corresponding to Q_ and 70 not containing 9 . Interpreted in terms of characteristic functions relative to PG(3,2) = V(4,2)‘\{9] , we have: (2.1) gamma: When the point set is restricted to PG(3,2) = V(4,2)\\[Q], the 112 blocks of the design D subdivide into a set of 42 weight 5 blocks and a set of 70 weight 6 blocks. Their respective weight 5 and 6 vectors are characteristic functions of simplices and pairs of skew lines in PG(3,2) . _P_r_9_a§_: Let a1 be the basis vector of V(16,2) corresponding to _0_EV(4,2). By b = 42 for D , the 42 weight 6 vectors 1 containing a 1 in the coordinate a1 place locate a dependent set of 5 points in PG(3,2). Since no two points in any PG(n,2) are dependent, this set must have no three points dependent (collinear) and no four dependent (coplanar). As such each dependent set of five points is a simplex in PG(3,2). For the 70 weight 6 vectors containing a 0 in the coordinate corresponding to £1 , each yields a set of 6 dependent points of PG(3,2). Simplices have in PG(3,2) at most 5 points so at least 3 of the 6 points must be dependent (collinear), but then the complementary set must be also dependent of cardinality at least 3. So such a dependent 6—set is necessarily a pair of skew lines in PG(3,2) . // (2.2) Corollary: The 42 simplices and 70 pairs of skew lines from PG(3,2) form, respectively, a 44- (2,5,15) design S and a 10-(2,6,15) design L , each with d216 Proof: According to (4.15), the 42 blocks of D having a 1 in the place, al , form the derived design of D which is a 4-(3-l,6-l,l6—l) design, S . The other 70 blocks then form a (l4-4)-(3-l,6-0,l6-l) design L , because D is by (4.1.4) also a 14-(2,6,l6) design. These designs clearly inherit d216 being no more than a subset of vectors already with the d216 property. Hence these sets of 42 simplices and 70 pairs of skew lines must be 4-(2,5,15) and lO-(2.6.15) designs with d26 . // (2.3) So if D is any XNR-design embedded in V(4,2) , its 112 blocks define on the point set PG(3,2) a design _§ of 42 simplices of PG(3,2) and a design ‘g of 70 skew line pairs of PG(3,2) . Designs S and L are 4-(2,5,15) and lO-(2,6,15) designs with d216 , respectively, by Corollary (2.2). Since D is a 3-design, each triple of points from PG(3,2) occurs a total of b3 = 4 times among the blocks of the designs S and L . Since triples of points of PG(3,2) are of two types, collinear or non-collinear, (2.4) we shall call these sets ggpaa and triangles of PG(3,2) , respectively. (2.5) .LEEEE‘ Each triangle of PG(3,2) is contained in exactly one of the blocks of S . gamma: Since Corollary (2.2) shows that S has d;;6 , two simplices of the design cannot share a triangle. Hence, each triangle must be contained in a unique simplex. There are (135) triples in pc(3,2) and of these, 15.14.1/3: = 35 triples are lines, so there are (135) -35 = 420 triangles of PG(3,2) . But there are then 42. ( g) = 420 triangles each contained uniquely in the 42 blocks of the simplex design, S . Therefore, each triangle of PG(3,2) is in exactly one block. // (2.6) Corollary: Each triangle of PG(3,2) is contained in exactly three blocks of L . (3529;: Each triple of D is in precisely 4 blocks, and each triangle is in a unique simplex, by (2.5). // (2.7) .222223 Each line of PG(3,2) is contained in exactly four blocks of L . Each such line and the four others skew to it from each of the four blocks form a spread in PG(3,2) . Izaaag: Since no triple in a simplex can be dependent (collinear), each line of PG(3,2) must be in 4 blocks of L . Consider the 4 blocks from L containing a fixed line 11 0f PG(3,2) . Let ‘2, ‘3, L4, and ‘5 be the other lines skew to ‘1 so that [11,11] i = 2,3,4,5 are those four blocks of L . Because d216 in L (Corollary (2.2)), the pairs {‘i"j}’ i,j = 2,3,4,5, j #’i , must also be skew. Therefore {Li | i = l,2,3,4,5] is a spread of PG(3,2) (cf. Definition (8.10.5)). // (2.8) Theorem: Corresponding to each design L in PG(3,2) there is an injection, 8 , of the lines of PG(3,2) into the spreads of PG(3,2) such that each of the four blocks of L containing a line 1 contains also a second line from the spread 5(1) [Egaag: By Lemma (2.7) the four blocks of L containing a given line 11 of PG(3,2) determine a well—defined spread, S(Ll) = {11,12,13,z4,25} in PG(3,2), so that {11,51} for i = 2,3,4,5, are blocks of L . Should any two lines, say ‘1 and L , from PG(3,2) determine the same spread, then s(1,1) =s(1,) so that LEs(1,1) . Let 1, be 1.2 w.1.o.g. Now Lemma (2.7) applied to 8(12) implies that {12,11} for i = 3,4,5 are also blocks of L . Hence these are blocks of D . Then {11,54} and {12,53} are two disjoint blocks of D . But since bB = 0 for 0,6 the generalized block intersection numbers for D relative to a block B of this design D (cf. (6.4.6)), D has no block disjoint from any given block B of D . This contradiction forces the spreads 3(11) and 3(12) to be distinct. Thus the correspondence s is one to one. // (2.9) Define ‘a, to be any of the one to one correspondences determined by a design L in PG(3,2) §9.3 The Uniqueness Under 8 of the Correspondence s and Design L (3.1) .EEEEE! The stabilizer of a line in PG(3,2) is transitive on the set of 8 spreads of PG(3,2) which contains that line. .gaaag: Since there is always an even permutation of X mapping any 4-tuple from X to any other, A8 is transitive on lines of PG(3,2). So w.l.o.g. we may consider a line L of PG(3,2) to be coordinatized by [[a,b,c,d},[e,f,g,h]]. By Lemma (8.10.6) this line is contained in the 8 spreads: [a,b,c], {a,b,d], [a,c,d], {b,c,d}, [e,f,g], [e,f,h], [e,g,h}, and [f,g,h] . Since these 8 triples are completely contained in either of the 4-tuples corresponding to the line L , there is a motion. ¢;EAB which stabilizes g and moves any of these triples to any other of these triples. // (3.2) Theorem: Any one to one correspondence s of lines of PG(3,2) to 35 of the spreads of PG(3,2) such that each line L' of PG(3,2) together with the four other lines of the spread S(g') form a block of L , is uniquely determined by any one line and its corresponding spread. 3:29;: First consider any two skew lines. They must have 8 letter coordinates which by Theorem (8.10.1) have representatives sharing 1 or 3 letters. There is a motion 6 of A8 sending the coordinates of a line 11 to [{a,b,c,d], [e,f,g,h}} . Then a further motion $2 of A8 may be chosen to send the coordinates of a line 12 which is skew to ‘1 to [{a,e,f,g], [b,c,d,h]] . (A8 is shown to be transitive on pairs of skew lines in this way.) Now it is clear that 11 and 12 are both in the two spreads {b,c,d} and [e,f,g), (cf. (8.10.6)). Now let S(Ll) = [b,c,d] . If s is to generate the blocks of a lO-(2,6,15) design L , with d;i6 , as indicated in the hypotheses of this lemma, then {11,12} must be a block of L . Now 12 must correspond to one of the two spreads containing {11,12} since this set is 9.8 already a block of L . But does not correspond to ‘2 [b,c,d] = 3(11) by Theorem (2.8), and hence, necessarily 5(11) in the spread {b,c,d] must correspond by s to the spread {y,z,w] for {y,z,w] c {e,f,g,h] . Note that each of the five lines with correspondence 5 defined already, correspond to the spread given by that triple which together with the letter a form a 4-tuple representative for the line. Now by considering the 4.(5-2) = 12 other lines in the four spreads [y,z,w} c [e,f,g,h] corresponding under s to the other four lines in the initial spread {b,c,d} , one sees that each of these lines must correspond under s to that triple which together with the letter a forms a 4-tuple representative of the line. For example, consider the spread {e,f,g] and its five lines: [{a,b,c,d}, [e,f,g,h]] = ‘1 {maxim}. {6,139,611} = 12 [[a,c,d,h], {e,f,g,b]] = 13 [{a,b,d,h], {e,f,g,c]] [[a,b,c,h], {e,f,g,d]] . Since {12,13} is already necessarily a block of L , su3) = {c,d,h} . Finally, by considering each of the 18 other lines from PG(3,2), one finds that there is exactly one spread that can correspond to each of these lines. This spread is the one whose triple together with the letter a forms a 4-tuple representative of that line. // (3.3) Corollaay: If 5(1) = [b,c,d] for the line L given by {{a,b,c,d], [e,f,g,h}], then 5(1') = [x,y,z] where [[a,x,y,z}, {w,m,n,p]] is the 8 coordinate name for L' , and {x,y,z,w,m,n,p] = X\([a] . (3.4) Theorem: Up to a motion of PG(3,2), the design L is unique. .gaaag: By Theorem (2.8), there must be a correspondence 8 mapping the lines of PG(3,2) to 35 of the spreads of PG(3,2) so that the correspondence locates the blocks of the design L . Up to a permutation A8 the initial choice of the spread S(L) corresponding to z is unique for any fixed line L of PG(3,2), by Lemma (3.1). Then Theorem (3.2) shows that s is completely determined by these initial conditions. // (3.5) Theorem: The automorphism group of the design L is A7 £5925: By Lemma (2.7) each line of PG(3,2) is contained in four blocks of L . Any motion m of the points of L , i.e. the points of PG(3,2), which sends also blocks to blocks must send the four blocks through one line to the four blocks through another line. Hence m induces a collineation ¢p* of PG(3,2) so ¢p*EPSL(4,2) e-A But 8 0 w*, as a collineation of PG(3,2), permutes the set of 56 spreads of PG(3,2) . By Corollary (3.3), ¢* must move these 56 spreads in two sets - the set of 35 spreads corresponding under s to lines of PG(3,2) whose triples are from X\({a], and the set of 28 other spreads whose triples contain the letter a. Since the subgroup of A8 which fixes the letter a is A7 ,Aut(L) : A7 . If cpEA7 where A7 operates on X\{a}, then m induces a unique mapping 3 agreeing with the hypotheses of Theorem (2.8) and the correspondence given in Corollary (3.3). Therefore, the equivalent lO-(2,6,15) design (LT) with d;z6 induced by m has exactly the same correspondence 8 and hence the same blocks. Therefore A7 c Aut(L) . // (3.6) Corollary: A7 is l-transitive on blocks of L . ‘3g29g: Consider for each line of PG(3,2) only the representative 4—tuple which contains the letter a. Then on X‘\{a], lines corre5pond to triples. Exactly these triples are also the spreads under the correspondence 8 , as in Corollary (3.3). This means that the two lines of a typical block of L have corresponding triples which are disjoint triples chosen from X\\{a] . Since A7 is transitive on pairs of disjoint triples chosen from X)\[a}, A7 is transitive on blocks L . // §9.4 The Uniqpeness 2; the Design Pair S,L we know from Section 9.3 that design L and its related correspondence 5 are unique up to a motion of PSL(4,2). Aiming towards the uniqueness of D we show in this section that there is a unique design 8 that can extend a fixed design L to D . We do not prove that design S is unique, but rather the uniqueness of the pair S,L which can be extended to D . (4.1) Theorem: Given PG(3,2) and the (unique) design 1., there is a unique design S which together with L can be extended to an XNR-design D . lgaaag: Assume that S and L are respectively 4-(2,5,15) and lO-(2,6,15) designs which build an XNdeesign D by attaching a sixteenth point to the point set of these two designs. Considering the 15 point set to be the set of points of PG(3,2), 0 may be then augmented to each simplex and to none of the pairs of skew lines so that the resulting design D has V(4,2) as its point set. Then by Lemma (2.5), it is necessary that each triangle from PG(3,2) be located in one and only one simplex of S . (4.2) Furthermore, since d;;6 in D , two blocks of D , one from S and one from L must overlap on at most three points of PG(3,2) Consider any one triangle of PG(3,2). Label its three lines as 11,12,13 . In PG(3,2) this triangle completes to a Fano plane. Let the seventh point of this plane, which is not on any of the three lines 51,12, or ‘3, be called P . Through P pass seven lines of PG(3,2), three of which occur on this plane. Let the four lines through P and not contained in this plane be labeled m1,m2,m3 and m4 . By the necessary correspondence 8 , as given in Theorem 2.8) and Definition (2.9) spreads 3(11),s(12), and 3(13) must correspond to lines 51,12,13 of the fixed triangle so that 1i together with each of the other four lines in the spread S(Li) must form a block of L , for i = 1,2,3 . Since one line of any spread, by Definition (8.10.5), passes through each point of PG(3,2), one of the four lines mj, j = l,2,3,4, together with each Li’ 1 = 1,2,3, must form a block of L . But furthermore, since d;z6 in design L , and since any two of the lines ‘i for i = 1,2,3 meet on a point, each ‘i’ i = 1,2,3 must form a block with a distinct one of the lines mj, j = l,2,3,4. So w.l.o.g. let [11,mi], i = 1,2,3 be blocks of L , i.e. let mi be contained in the spread S(ji) for i = 1,2,3. Now, any triangle of PG(3,2) is contained in four simplices of PG(3,2), namely the three points of the triangle P12,P13,P23 (for Pij = ‘i Flzj , i, j = 1,2,3, i i j), together with the two points of each of the four lines mj, j = l,2,3,4 other than P . If the simplex to be chosen through [P12,P13, P23} contains the two points of mj for j = 1,2,3 other than P , say the two points 01 and R1 of m1, then the simplex [P12,P13,P23,Q1,R1} of 8 would meet the block {‘l’ml} of L in the four points of {P12,P13,01.R1] , contradicting the fact stated in (4.2) that a block of L and a block of M must share at most three points. Therefore, through [P12,P13,P23] can be chosen only the simplex {P12,P13,P23,Q4,R4] where Q4 and R4 are the two points of m4 other than P . Hence, the triangle can be contained in at most one simplex that can be used for the design S . Now the existence of the XNR-design D as guaranteed by Remark (4.3.4) (and by Theorem (5.3.9)) shows together with Lemma (2.5) that each triangle is contained in exactly one simplex of S . // (4.3) Corollary: The design 8 of 42 simplices as referred to in Theorem (4.1) has d;z6 gaaag: The uniqueness of the system as guaranteed by Theorems (3.4) and (4.1) together with the existence of the systems shown in Theorem (5.3.9) yields the distance condition d;;6 for S as well for L and D . // (4.4) Theorem: The automorphism group of S is A7 . 'gaaag: By Theorem (3.5) the automorphism group of design L is A7 . Each motion of A7 then permutes the 15 points of PG(3,2) and stabilizes the set of 70 pairs of skew lines of PG(3,2) forming blocks of L . As such, since the 70 block design L implies the existence of 42 simplices uniquely chosen relative to L , each motion T of Aut(L) 3 A7 moves points of PG(3,2) and stabilizes the set of 42 simplices in S . Hence A7 : Aut(S) Conversely, given any cp EAut(S), consider the four blocks of S containing a given pair of points. As m moves points of PG(3,2) to points and simplices of S to simplices of S , m must move a pair of points together with the four blocks of S containing that pair to another pair of points together with its four blocks. Counting all the points in these four blocks with use of d;;6 , four blocks containing that pair involve 14 of the 15 points of PG(3,2). By Lemma (2.7) this fifteenth point must be collinear with that pair. Hence, m moves lines of PG(3,2) to lines and therefore is a collineation of PG(3,2). But as a collineation of PG(3,2), m permutes spreads of PG(3,2). Were the 35 spreads corresponding to the design L , which according to the hypotheses of Theorem (4.1) exists simultaneously with ,S , not stabilized by w , then T would not stabilize the 70 blocks of L . Then the correspondence 5 would not stabilize the 42 blocks of S , and cpEAut(S) , a contradiction. Therefore m induces an automorphism of L showing that Aut(S) c A7 . As a result, Aut(S) = A7 a Aut(L) . // §9.5 The Uniqueness pg the XNR-Design IQ (5.1) Theorem: Up to a permutation of the 16 coordinates of V(16,2) , the XNR-design D is unique. 35293: As seen in Theorem (6.5.9), each XNR-design D generates a (16,256,6) code C , where standard basis vectors of V(16,2) are the points of D . Then by Theorem 7.5.11) the weight 6 vectors in C , i.e. those corresponding to blocks of D must be characteristic functions of dependent 6-sets in V(4,2) . Then by letting an arbitrary coordinate place of V(16,2) correspond to QEV(4,2) , these dependent 6-sets in V(4,2) yield a design L according to Lemma (2.1) and Corollary (2.2). Design L is unique, Theorem (3.4), up to a collineation of PG(3,2) which is a permutation of the 15 coordinates of V(16,2) other than the one corresponding to Q EV(4,2) . Furthermore, design L induces a unique design S which together with L builds design D whose points are the 16 vectors of V(4,2), by Theorem (4.1). Hence, even after arbitrarily fixing the coordinate place of V(16,2) corresponding to 0 EV(4,2) , there is a permutation of the other 15 coordinates which puts D into a given standard form for D . // Actually the proof of Theorem (5.1) proves the stronger statement: (5.2) Corollamy: Given any two distinct c0pies D and 1 D2 of a XNdeesign, then there is a motion m of the 16 coordinate places of V(16,2) which fixes one coordinate and moves the other 15 coordinate places so that Dlm = D2 . (5.3) Theorem: The automorphism group of the unique XNR-design D is A7-+T(4), i.e. A7 extended by T(4), the group of the 16 translations of V(4,2) . Egaag: By Theorem (5.1), the design D is unique. As constructed in Theorem (5.3.9), this design D is composed of 7 orbits of dependent 6—sets under the action of T(4), the translation group of V(4,2) . Hence, T(4) stabilizes D Since T(4) is regular on V(4,2) , Lemma (3.2), any motion of T(4) fixing _QEV(4,2) is the identity vector. Then with .9 fixed, Lemma (2.1), Corollary (2.2), and Theorems (3.5) and (4.4) show that A7 acts on D with El fixed. Hence, the total group of automorphisms D is A7 7 WM) . // (5.4) Theorem: The automorphism group A7-+T(4) of the extended by T(4), A XNR-design D is 1-transitive on the 112 blocks of the design. 3:29;: By the construction method of D as shown in Theorem (5.3.9), T(4) acting on D is %-transitive on blocks of D «giving 7 orbits of 16 blocks each. Since T(4) is regular on the 16 coordinate places of V(16,2), by Lemma (3.2), there is always at least one block of each of these orbits which contains a 0 in the coordinate place of V(16,2) corresponding to the QEV(4,2) . In other words at least one block of each of these orbits is contained in L . By Theorem (3.5) and Corollary (3.6), Aut(L) 8 A7 is 1-transitive on these 70 blocks. Therefore A7-+T(4) is l—transitive on all the 112 blocks of D . // (5.5) Theorem: A7-+T(4) is 3-transitive on the 16 points of X for the XNR-design D = (X,B) Egaag: By Theorem (5.4), A7-+T(4) acts as a l-transitive degree 112 group of permutations of the 112 blocks of D . Since each of the motions of A7-+T(4) is an automorphism of D , there is an isomorphic injection i mapping the group which acts on the 112 blocks of B into the group which acts on the 16 elements of X . Let G be the subgroup of the action of A7-+T(4) on /3 which stabilizes a block B EB . Via the injection i , Gi is a homomorphic image of G on X stabilizing the two sets B and X\\B . m: The homomorphic image Gi of G acting on the 6 elements of the stabilized block B gives a faithful representation of G on B . 4 2V(4,2) for X 3529:: Consider the mapping 0.:V(l6,2) being a basis of V(16,2) which exists according to Theorem (7.5.1) in such a way that blocks of D are characteristic functions of dependent 6—sets in V(4,2) Theorem (7.5.15) shows that each automorphism cp EAut (D) induces a motion, a0¢,¢ followed by a , of V(4,2) preserving linearity in V(4,2) . Then due to the fact that eadh dependent 6—set in V(4,2) spans all of V(4,2) by Lemma (4.5.8), it follows that if 00¢ fixes pointwise a dependent 6-set of V(4,2) , then 00¢ must fix pointwise all the 16 points of V(4,2) . Hence any motion of Gi fixing B pointwise induces the identity motion in the action Gi on X and hence is the identity automorphism of G . This proves the claim. // Proceeding with the proof of Theorem (5.5) we notice that since G stabilizes one of the 112 blocks of B , |Gi| = 360 . Then the only subgroup of the set of all 6! permutations of the elements of B of this order is A6 Hence Gi 3 A6 , which is 4-transitive on the 6 points of B . As such, any triple of the 16 points of X may be 9.18 moved to any other triple of X by first moving one of the blocks through the first triple to one of the blocks through the other triple and then by using a motion of G on the image block. // Note that the proof of Theorem (5.5) actually proves the following: (5.6) Corollary: A7-+T(4) is 4-transitive on the set of (2).112 4-tuples contained in blocks of the XNR—design D . CHAPTER 10 The Uniqueness of the Nordstrom—Robinson and The Extended Nordstrom—Robinson Binary Codes §10.l Introduction This chapter will collect information from Chapters 5, 6, and 9 to show the uniqueness of the (15,256,5) code first discovered by Nordstrom and Robinson, together with the uniqueness of the extended (16,256,6) code. We shall use the notation NR and XNR for the (15,256,5) and (16,256,6) codes, respectively, according to Definition (3.5.8) and (3.5.4). 610.2 The Uniqueness pg the XNR(l6,256,6) Code (2.1) Theorem: Up to a permutation of the 16 standard basis vectors of V(16,2), the XNR(l6,256,6) code is unique. ggapg: From Theorems (9.5.1) and (6.6.1) the code is unique up to a permutation of the 16 coordinate places. // (2.2) Theorem: The automorphism group of the XNR(l6,256,(5) code is a degree 16 representation of the group A7-tT(4) , i.e. A7 extended by the group of translations of V(4,2) ’ as long as _QEXNR . Proof: Given a particular copy of the unique XNR code, C , with 0 EC , then by Theorem (6.3.1), the set of 112 weight 10.1 10.2 6 vectors of C form an XNR-design D . By Theorem (9.5.2) this design D possesses the group A7 -+T(4) as its group of automorphisms acting as a degree 16 group on the 16 standard basis vectors of V(16,2) . By the Definitions (5.2.5) and (5.2.6), the group of automorphisms of C must be a subgroup of A -+T(4) . But since Theorem (6.5.9) 7 shows that the design D determines uniquely all the 256 vectors of C , each automorphism of D which by definition stabilizes the set D of weight 6 vectors of C must also stabilize the sets of weight 8, 10, 16, and 0 vectors of C ./9/ (2.3) Corollary: The group A7-+T(4) of automorphisms of the XNR(l6,256,6) code is 3-transitive on the set of 16 standard basis vectors of V(16,2) Proof: Use Theorem (9.5.5). // §10.3 The Uniqueness 2; the NR(15,256,5) Code (3.1) Lemma: Given any two copies Ci and C5 of the XNR(l6,256,6) code, then there is a motion T which fixes one of the 16 coordinate places of V(16,2) , and permutes the other 15 so that Cim = C5 . a Proof: By Corollary (9.4.2) there is m fixing one coordinate place of V(16,2) and permuting the other 15 places so that the weight 6 vectors of Ci , which form an XNR—design, D1 , are mapped onto the weight 6 vectors of Ci , Then since each SNR-design D builds a (16,256,6) code in only one way by Theorem (6.5.9), the same m maps 'Ci c2.// t0 I‘- 10.3 (3.2) Theorem: The NR(15,256,5) binary code is unique up to a permutation of the 15 standard coordinate basis vectors of V(15,2). ggaag: Given any two (15,256,5) codes, Cl and 02 , each extends by a parity check coordinate augmentation to a (16,256,6) code Ci and C5 respectively according to Definition (2.5.3) and Lemma (2.5.6). Now by Lemma (3.1) there is a permutation of the 15 coordinates of V(15,2) mapping Ci and C5 simultaneously C1 to Ci . // §10.4 The Non-Linearity 93 the EB and XNR Codes Using a simple idea due to J. M. Goethals [15] we can now show the non-linearity of both the unique NR(15,256,5) code and the XNR(16,256,6) code. As a by-product we have a distinct proof of the Calabi, et al.[7] result that there exists no linear (16,256,6) code. (4.1) Theorem: The unique XNR(16,256,6) code is non-linear. M: (J. M. Goethals) Let w.l.o.g. QEC , where C is a (16,256,6) code. By (6.3.1) the set of weight 6 vectors fonmsan XNR-design D . Choose any three coordinate places, .a1,a2, and a3, from V(16,2) . Since b3 = 4 for the desigrl D , there are exactly four vectors of weight 6 in C which contain ones in these three coordinate places. Call these four vectors .alhazpa3, and ‘a4 . Then using the facts that d216 for all pairs of code vectors from C and since 5i . a]. | 23 for each pair of these four vectors, 10.4 i y’ j, i, j= l,2,3,4, then Lx +§_ +35 +354] = 12 . But 1 2 3 according to Lemma (6.4.7), any (16,256,6) code C with ‘QGEC contains no vector of weight 12. This implies that _J_{_ +35 +§3 +§4£C and that C is non-linear. // l 2 (4.2) Corollary: The NR(15,256,5) code is non-linear. .gaaag: By Definition (2.5.3) and Lemma (2.5.6) and by the uniqueness of the NR and XNR codes, the XNR code is necessarily the parity check code of the NR code. Similarly, by Definition (2.5.2) and Lemma (2.5.5) the NR. code is necessarily the punctured code of XNR . Then by Lemmas (5.8) and (5.9) one code is linear iff the other is also linear. Hence, by Theorem (4.1), the NR code is non-linear. // (4.3) Corollary: There exists no linear (16,256,6) code. Proof: The (16,256,6) code is unique. // PART D: THE GOLAY BINARY CODE CHAPTER 11 The Uniqueness of the Large Steiner Systems S(4,7,23) and S(5,8,24) §ll.l Introduction As a by-product of our work with the uniqueness of the Nordstrom-Robinson code, we can show the uniqueness of the Steiner systems S(4,7,23) and S(5,8, 24) . Furthermore, we can show that the automorphism groups of these designs are of order [M23| and |M24|, are block transitive on the designs, and are 4- and S-transitive on the 23 and 24 point sets of those designs, respectively. In an effort to locate a good setting for the action of the 4- and 5- transitive groups M23 and M24 discovered earlier by Mathieu [39], Witt (1938) showed in [40] the uniqueness of these Steiner systems building them up from the unique projective plane over GF(S) . Witt's concern was to establish the uniqueness of the 4- and 5- transitive groups M23 and M24 . Actually, H. Luneborg [23] discovered and corrected a flaw in Witt's construction. Much more recently, Jonsson built up the Steiner system S(3,6,22) from facts concerning the geometry of PG(3,2), cf. [19]. From the uniqueness of S(3,6,22) thus established, 11.1 11.2 Jonsson concluded similar results about the uniqueness of the three large Steiner systems S(3,6,22), S(4,7,23), and S(5,8,24) and their related automorphism groups M22, M23, and M Our construction of these designs corresponds to 24 ' constructing M23 from its maximal subgroup isomorphic to A -+T(4) whereas that from Jonsson constructs M 7 from S6 . 22 §ll.2 The Uniqueness pg S(4,7,23) Based pm the Uniqueness a; the XNR-Design Throughout this section let X be a set of 23 points. Also let S be an S(4,7,23) design. (2.1) .gamma: S = (X,B) is a l-(4,7,23) design with d218 and each block B of B shares with 140 blocks of 8 three elements of B and with 112 blocks of B one element of B . .ggaag: By definition, S is a S(4,7,23) or a l-(4-7-23) design so that each 4-tuple from X is contained in precisely' one block of the design. Therefore, two distinct blocks share at most three elements of X and have Hamming distance d28 from one another. By formulas (4.1.2) one sees that bO = 253, b1 = 77, = 21, b3 = 5, and b4 = l . Furthermore, b4 = 1 B_B_B_ . 5’0 - b6,0 — b7,o — 1 for a given block B of design S . Hence, the generalized block intersection b2 implies b numbers for 8 relative to a block B of the design are: 11.3 (2.2) 253 176 77 120 56 21 80 40 16 5 52 28 12 4 l 32 20 8 4 0 1 l6 l6 4 4 0 0 l 0 16 0 4 O 0 0 1 From the b§,j for i-+j = 7 we conclude that each block B meets 4 blocks on each triple from B and 16 blocks on each element of B . Hence, B meets (g) . 4 = 140 blocks on three elements of B and (3:). 16 = 112 blocks on one element. // Let Y = X)\B be the set of the 16 points of S other than those of a fixed block. (2.3) ,gamma: The 140 blocks of S meeting B on 3 places form an S(3,4,16) design P on the 16 elements of Y . The 112 blocks of S meeting B on one place form an XNR-design D . 2399;: From the bE,j for S with respect to a block of S as given in (2.2), the 112 blocks of S meeting B in one place form, on the set B , 16 copies of the complete (3 )-design. Similarly those 140 blocks meeting B on three places form on B four copies of the complete ( ;)-design. Let the corresponding parts of these 112 and 140 blocks with point set y = X‘\B be called designs D and P , respectively. Figure (2.4) 112 140 l D P Y fi 7 7 7 16“,) 4M3) (7) B U} Blocks of D have cardinality k = 6 since the corresponding weight 7 blocks of S meet B in one place. Each 4-set from X occurs in a unique block of S , so that in D blocks have Hamming distance d326 from one another. Then for t = 6-6/2 = 3, equality in (4.7.5) holds showing by Lemma (4.7.7) and Definition (4.7.3) that D is an XNR-design. Design P is then a S(3,4,16) by the fact that each 4-tuple from Y occurs uniquely either in D or in P and by Definition (7.2.2) and Lemma (7.2.3). // (2.5) Corollary: The 140 blocks of P as given in Figure (2.4) form the 140 planar 4-tuples of V(4,2) where the 16 vectors of V(4,2) are the 16 elements of Y . _Eaaag: This follows by Lemma (2.3) and Lemma (7.5.12). // (2.6) ,gamma: The 16 blocks of S through D meeting a fixed block B of S on a given single element of B form a 2-(2,6, 16) design T with d28 . .ggaag: Consider the 16 blocks of S which meet B in precisely the element x EB . Let T be the design whose point set is Y and whose blocks are those 16 blocks restricted to Y . Blocks of T have cardinality 6 and meet one another on 0 or 2 places since blocks of S meet one another on 1 and 3 places. Consider the average number of 11.5 blocks of T through any pair of points from Y . Formula (4.1.8) yields b2 = 16.6.5/16.15 = 2 Since blocks of T meet on no more than 2 places, b2 = 2 is a constant, so that T is a 2-(2,6,l6) design with 628 . // (2.7) gamma: Each block of the XNR-design, D , is contained in precisely one 2-(2,6,16) design, T , with d218 composed of 16 of the blocks from D . Thus the design D decomposes into a collection of 7 disjoint 2-(2,6,16) designs with d28 . gmaag: That each block of D is in a 2-(2,6,16) design with d;;8 of 16 blocks of D is a result of Theorems 5.3.5) and (5.3.9). From the generalized block intersection numbers for D relative to a block, L , of D given in (6.4.6), bg’4 = 1 implies that there are precisely 21x (3) ==15 other blocks of D that meet L in precisely two places, which blocks together with L could form a 2—(2,6,l6) design, T , with d;28 . // Now with these lemmas we can proceed to prove: (2.8) Theorem: Up to a permutation of the 23 elements of X , the S(4,7,23) design S is unique. Proof: Let S and 82 be any two S(4,7,23) designs 1 defined on, for simplicity, the same point set X of cardinality 23. Choose any two blocks BiESi for i = 1,2, 11.6 one from each design, and consider the corresponding subdesigns Di and P1 of Si , i = 1,2 as shown in Figure (2.4). Let Di = (X,Bi) for i = 1,2 . Because of Theorem (9.5.1) and Definition (5.2.1) there exists a pair of one to one correspondences (m,¢) for (2.9) cp:X4X and ¢:Bl452 so that ($21) map points and the blocks of D1 to the points and blocks of D2 . we shall now proceed to show that each of the maps in the pair (¢,¢) extend to the maps m* and w* respectively in a unique way so that (¢*,¢*) carry the points and blocks of S1 to those of S and so that 2 9*‘X\Bl=¢ and wit1131:w By Lemma (2.7), W maps each of the 2-(2,6,l6) designs with d218 in D1 to one of D2 . Since each block of D. 1, i = 1,2, in a given 2-(2,6,16) design with d218 corresponds (Lemma (2.6)) to a single element of Bi,i = 1,2, there is a unique map (2.10) G:B 4B 1 2 so that the combined map (2.11) cp*6823,cp:X 4 X where w* 1 X\\Bl = w and m* 1 B1 = 9 carries points of S1 to those 8 at the same time that 2 w carries the 112 blocks of S1 meeting D1 to the 112 blocks of S2 meeting D2 . 11.7 Now that m* is defined it is sufficient in proving Theorem (2.8) to show that if the 23 x(112-+l) matrix part of S is given Figure (2.12) 112 l D X\B 7 7 16ml) (7) B then the corresponding 140 blocks completing the design to an S(3,7,23) are uniquely determined. (That the other 140 blocks are uniquely determined forces the extension ¢* of w to be unique.) (2.13) Egagm: Given the 113 blocks of S as in Figure (2.12), then there is a unique way to complete these blocks to a S(4,7,23) design. £59532: Choose any three elements a,b,c, EX\B . These three elements are contained in blocks Bj’ j = l,2,3,4 of 8 meeting D and must be contained in one other block B5 of S . Since d326 in D , HJBi| = 15 and there is a unique 4—tuple from X)\B containing [a,b,c] c X\\B . Since blocks Bj intersect one another in three elements, they are, by Lemma (2.7), members of distinct 2-(2,6,16) designs with d218 . Then by Lemma (2.6) the corresponding single elements from 8 contained in the blocks l,2,3,4, of S, must be distinct elements u. II j) xj, design S each 4-tuple must be contained in a unique block, j = l,2,3,4, of B . Then because in the S(4,7,23) the set of three elements of B contained in block BS must be B\[xj [j = l,2,3,4} . So for each triple from X\\B there is a unique block B5 that necessarily must be chosen to complete the set of 113 blocks of Figure (2.12) to the design S . This finishes the proof of Theorem (2.8)./Q’ (2.14) Corollary: In a S(4,7,23) design S , the group of automorphisms stabilizing a block B of the design is A7-+T(4) . Proof: This follows from Lemma (2.3), Theorem (9.5.3), and the Claim (2.13). // (2.15) Corollary: The S(4,7,23) design exists and is unique. .gaaag: Existence follows from Theorem (3.3.10) and Lemma (4.3.3). Uniqueness follows from Theorem (2.8).// (2.16) Theorem: The automorphism group of S(4,7,23) design S is block transitive. ugaaag: Consider the set of 112 blocks of S meeting a fixed block B in one place. The stabilizer group of B is by Corollary (2.14) transitive on these 112 blocks. This means that given any two blocks B1 and B of S , if 2 there is a third block 83 meeting each of the first two blocks on one place each, then there is an automorphism of S moving B to B . l 2 By the fact that any two blocks of S meet in either 1 or 3 places (Lemma (2.1)) we need only consider two cases. Let B1 and B2 be blocks of S . Case 1: If [Bl F.B2| = l , then 82 is one of 11.9 the 112 blocks meeting B1 on one place. By the generalized block intersection numbers for the design D corresponding to these blocks, (cf. (6.4.6)) there are 36 blocks of D meeting B on one place of the 16 point set X\Bl of D . 2 Choose one of these 36 blocks and call the corresponding block of S , B3 . Since blocks of S meet one another on 1 or 3 places and Since [83 FIBZ| = l , the single element of "1 B2 FIB1 must not be contained also in B3 . Hence, B3 a. meets each of B1 and B2 on one place. Therefore there r; exists an automorphism of S stabilizing B3 and moving B1 to B2 Case 2: If '31 fl B2| = 3 , then choose a EB].\B2 . There are 16 blocks of S meeting B1 on only a and forming, with respect to X\(Bl, a 2-(2,6,l6) design with d;18 . At most 4 of these 16 blocks share point a and three points of BZ‘\B since each 4-tuple of X occurs in 1 3 a unique block of S . So there are blocks of S meeting B1 on a and 82 on one place. Choose one of these, 83 . Then |B3 F1B2| = |B3 F1B1| = 1 . Therefore again there is an automorphism of S fixing 83 and moving B1 to 82 . //' The group of automorphisms of S(4,7,23) is known to be M23 (cf. Witt [39]). we may conclude at this point the following: (2.17) Corollary: The automorphism group of S(4,7,23) design 8 is of order 253.112.360 = 23.22.21.20.4s = [M23| . .gaaag: Since Aut(S) is block transitive on 253 blocks of S by Theorem (2.16) and since the stabilizer group of a 11.10 block of S has order 112.360 by Theorem (9.5.3), Aut(S) has order 253.112.360. // (2.18) Theorem: Aut(S) acts 4-transitively on the 23 points of S , where S = (X,B) is the S(4,7,23) design. £5993: Since Aut(S) is block transitive on B by Theorem (2.16), it suffices to show that the stabilizer of a i block of S acts 4-transitively on the 7 points of that .— block. Choose a block B EB . Then by Corollary (2.14), the subgroup G of the action of Aut(S) on the 23 points of at: X stabilizing the sets B and X‘\B is isomorphic to A7-+T(4) . G acts necessarily as an automorphism of the design P of Figure (2.4), since G must stabilize those blocks of S meeting block B in precisely 3 places. Furthermore, by Corollary (2.5), design P represents the set of 140 planar 4—tuples of a V(4,2) whose 16 vectors are the 16 elements of X\(B . Choose a point a EXN\B . Call the subgroup of G which fixes a EX\B as well as stabilizes sets X\B and B , the group H . Then H must stabilize the 35 blocks of P which contain a EX\B . But the design of 35 blocks of P containing' a EXN\B when restricted to the point set X‘\(B u [a}) is the design of the 15 points and 35 lines of PG(3,2) , the derived design of the points and planar 4-tuples of V(4,2) . Therefore, H is a subgroup of the collineation group of PG(3,2) . By Theorem (9.5.3), Lemma (9.2.1), Theorem (9.3.5), and Theorem (9.4.4), in that order, H 3 A7 Therefore H m PSL(4,2) by Theorem (8.8.10) and acts on the 11.11 points and blocks of the derived design of P Choose any m-:2L- contradicting yg% . We may now only conclude that z = l . This means that L' must be a code vector and that L must be a code vector and that L is the complement of a code word. // (2.12) _L_e_m_ma: Any (24,212,8) code, 0 , with age is complemented, i.e. the complement of any code word of C is again a code word. 3392;: Lemmas (2.5) and (2.10) ensure the existence in C of a code word, _z_EC , of weight 16, whose weight 8 complementary vector is also a code word. Considering the codes C+a and C+ (1+5), one sees that, due to Lemma (2.3), there are 759 weight 8 code words in each of these coset codes. Therefore, 6 +_z_ contains 9 = 5+5, 1 = (1+5) +2 , and 759 code words of each of the weights 8 and 16. By Lemma (2.10), those weight 16 code words in C +5 must be the complementary vectors to the 759 weight 8 code words in C+a . But a = Q+£€C+£ , so that both _z_ and j+_z_ are code words of C+_z_ as well as of C . Then, since C = C+_z_-ta , j = (j +5) +_z_EC . So any 1 (24,2 2,8) code C with QEC , contains also 1 asa 12.7 code word. Next, let 2. be any code word of C . The coset code C+_w_ is a (24,212,8) code with p = m+_w_EC+y_ , so _‘iEC-i-yg . Therefore, i+E€C = C+_v_v+ Hence, the It complementary vector to any code word of C is also a code word of C . // (2.13) Theorem: Any (24,212, 8) code C , with QEC , has one code word of weights 0 and 24 each, 759 code words of weights 8 and 16, and 2576 code words of weight 12. ggpagg Since by Lemma (2.12) the complement of each code word is also a code word, and since C has 759 weight 8 vectors by Lemma (2.3), C has 759 weight 16 vectors complementary to those weight 8 vectors. Furthermore, C has j,EC:. The code words of weights l,2,...,7 are impossible since d28 in C and QEC . Then by Lemmas (2.7) and (2.12), all other code words of C must be of weight 12. There are then 212-(1-+75912 = 2576 weight 12 vectors in c . // §12.3 The Designs S(4,7,23) and S(518,24) Build 423,212,7) and (24,21 2,8) Codes, Respectively, gm One Way By Chapter 11 we know that the designs S(4,7,23) and S(5,8,24) are unique up to a permutation of the point sets in question. Furthermore, by Lemma (2.3) and Corollary (2.4), l 1 each (23,2 2,7) and (24,2 2,8) code with QEC contains weight 7 and 8 vectors which determine S(4,7,23) and 12.8 S(5,8,24) designs, reSpectively. If we can show that each of these designs build the corresponding code in exactly one way, it will be shown that the corresponding codes are also unique. This is the goal of this section. Let S = (X,B) be a S(5,8,24) design, with X containing the 24 standard basis vectors of a V(24,2) as elements. Consider the set C of l-+759 vectors of V(24,2) which are ‘9, and the 759 vectors of weight 8 whose 8 coordinate places containing ones from the 8—sets of the S(5,8,24) design. Define (3.1) An admissible weight 12 vector to be a vector '5 of weight 12 from V(24,2) which has distance d218 from each of the 759 weight 8 vectors already in C . Let the lZ-set given by the 12 coordinate places of an admissible weight 12 vector 5, containing ones be called an admissible 12—tuple of S . (3.2) gamma: An admissible 12-tuple L of S meets 132 blocks of S in 5 places, 495 blocks in 4 places, and 132 blocks in 2 places. These sets of blocks when restricted to the complementary 12-tuple L' = X‘\L form two copies of? the complete ( 122) -design, the complete (1:) -design, and an S(5,6,12) design, respectively. [gaaag: Consider the generalized block intersection numbers for the design S relative to an admissible lZ-tuple, L , of S . Such a 12-tuple meets blocks of 8 in at most 6 places, for otherwise the Hamming distance between the corresponding vectors would be less than 8 . Hence, 12.9 L . _ . K j,0 — 0 for j — 7,8,...,12. Letting b6,0 see that the generalized block intersection numbers for 8 b = x, we relative to the admissible lZ-tuples L are: 759 506 253 330 176 77 210 120 56 21 130 80 40 16 5 28 52 28 12 4 l 45+x 33-x l9+x 9-x 3+x l-x x 24 21 12 7 2 1 x 0 +7x -6x +5x -4x +3x -2x y 9 15 6 6 l l x 0 +28x —21x +15x -10x +6x -3x * 84x 15 35x 6 10x 1 x 0 —6 —56x ~20x —4x , 210x 22 70x 7 15x 1 x 0 -28 -126x -7 -35x —1 -5x 462x 38 126x 9 21x l-6x x 0 0 -66 -252x -l6 -56x -2 924x 66 210x 12 28x l—7x x 0 C) 0 -l32 -462x -28 —84x -3 . L L Since each b and b must be 2_0, 924x‘»132 and 0,8 1,7 *- 6621462x showing that x = 1/7 . Therefore the generalized block intersection numbers b? j of S relative to L .9 with i-+j = 12 are b9 . = 0 except for bL = 2 , 1:3 2’6 L = l, and bL = 1/7 . These numbers imply that L 4,4 6,2 meets l/7x(162) = 132 blocks in 6 places, lx( 142) = 495 b blocks in 4 places and 2x( 122) = 132 blocks in 2 places. Since in S(5,8,24) each S-tuple from X occurs in a unique block, the 132 blocks of S meeting L on 6 places must have the property, when restricted to the point set of L , that each S—tuple is contained in a unique block. These 132 12.10 blocks then form a S(5,6,12) design. A S(5,6,12) design has by the formulas (4.1.2), b4 = 4; the S(5,8,24) has b4 = 5 . Therefore the set of 495 blocks of S meeting L on 4 places must form one copy of the complete ( :2) —design on L . Similarly b2 = 77 in S(5,8,24), b2 = 30 in S(5,6,12), and b2 = 45 in the complete ( :é)—design. This implies that each pair from L must occur twice among the 132 blocks of S meeting L on two places, and that these pairs form two copies of the complete ('52)—design when restricted to L . According to Lemma (2.12), the set of 759+l vectors of C 12,8) code only if the comple— may be completed to a (24,2 mentary vector to each code word is also a code word. There— fore the complementary 12-tuple to L , i.e. L' = X\\L must also be an admissible lZ-tuple. This means that L' meets blocks of S in the same manner as L does. // (3.4) Theorem: Each admissible lZ-tuple of S is the symmetric difference of two blocks of S which meet on two places in 66 ways. Egaag: Consider the dissection of S = (X,F) into subdesigns according to an admissible lZ-tuple L c X , as given in Lemma (3.2). Let sets A,B, and C be the sets of 132, 495, and 132 blocks of S which reSpectively meet L on 6, 4, and 2 places. Let L’ = X\\L . 12 Consider the complete ( 4 )-design of B restricted to L' . Let 1, 2, and 3 be three arbitrary points of L' Since b3 = 9 for a complete (142) -design (cf. 4.1.2), -ma... _ ' I H cai . a 12.11 [1,2,3] is contained in 9 blocks of B Consider these 9 blocks of 8 containing [1,2,3] and restrict attention to the set L . These 9 blocks form on L a design D of 12 points and 9 blocks. Design D has dgi6 since in S(5,8,24) blocks have d;;8 and the parts of these 9 blocks of B restricted to L' differ pairwise in two places (i.e. have d = 2 when restricted to L'). Then D has k = 4 and t 4-6/2 = l yielding equality in the formula (4.7.5) 12—1 12 _ b65173] ~71” 9 Therefore by Lemma (4.7.6), D is a 3-(l,4,12) design. (Actually one can prove that D is the transpose of the affine geometry AG(2,3) of two dimensions over GF(3), but this is not necessary for our purposes.) Let 0 be an arbitrary point of L . Since D has bl = 3 , the set [0,1,2,3] is contained in precisely 3 blocks of B . Considering S , b4 = 5 , so {a,l,2,3] must also be contained in precisely two blocks of CLJA . But blocks of A restricted to L' are pairs of points of L' , so [al,2,3] is contained in two blocks of C . Considering the complete (142) -design, E , and the two copies of the complete (122) -design, F , corresponding to blocks of B and C restricted to L' , one calculates bl = 165 in E and b1 is contained in 165 blocks of B and 22 blocks of C = 2 x11 in F . Therefore [a] 12.12 Now considering b2 for the designs G and H , b2 = 5 in H . This implies that for an arbitrary pair {1,2,3} c L' , [a,l,2] is contained in 15+5 " 20 blocks of BLJC . But b3 = 21 in the S(5,8,24) design S , so that [a,1,2] must be contained precisely one block of A . Restated, this last fact says that the pair [1,2] C L' , which is contained in precisely two blocks of A , is contained together with each OLEI. in.a unique block of A . This means that the two blocks of A containing an arbitrary! pair [1,2] c L' , when restricted to the set L form complementary 6—tuples. So we have finally shown that the admissible 12-tuple I. is the symmetric difference (a modulo 2 sum) of two blocks of S which share a given pair from L' = X\\L . Further- more, since there are 2 x66 blocks of S in A and since there are 66 pairs in the complete (122) -design, any admissible 12-tuple L is the symmetric difference of two blocks of S in 66 ways. // (3.5) Theorem: Given any S(5,8,24) design whose 24 point set X contains, as points, the 24 standard basis vectors of V(24,2), then S(5,8,24) always determines precisely one (24,212,8) code whose weight 8 vectors determine that S(5,8,24) design. .ggaag: Let C be the set of 759 vectors of V(24,2) which have ones in the coordinate places corresponding to the elements of X in the 759 blocks of the S(5,8,24) design. 12.13 12 For C to be augmented to a (24,2 ,8) code, Theorem (2.13) requires there to be one vector of weights 0 and 24, 759 vectors of weights 8 and 16 and 2576 vectors of weight 12. By Lemma (2.12) the complement of each code word must also be a code word. Therefore we must augment C by Q, j, and the 759 weight 16 vectors complementary to those already contained in C . Now by Theorem (3.4), the only admissible weight 12 vectors are modulo 2 sums of two weight 8 vectors of C , each in 66 ways. By counting the maximum number of possible admissible weight 12 vectors we see that there are 759.448/2 = 170,016 ways to choose pairs of blocks of S which share two elements of X . This yields 170.016/66 = 2576 possible distinct admissible weight 12 vectors. All of 12 these must be present in order to augment C to a (24,2 ,8) code. Therefore, the S(5,8,24) design builds a (24,212,8) code in a unique way. // (3.6) Theorem: The S(4,7,23) design builds a (23,212,7) code in a unique way. .graag: Let Y be a 23 point set and S = (Y,B) be a S(4,7,23) design. Let m be an additional point not from Y and let X = YLJ{m} . By Theorem (11.3.9) the design S builds a unique S(5,8,24) design on X . Let the 23 points of Y be the basis vectors of a V(23,2) and m be an additional vector so that points of X form a basis of — -.__ 1.. 12.14 V(24,2) . Then by Theorem (3.5), the S(5,8,24) design 1 builds uniquely a (24,2 2,8) code C' on V(24,2) whose weight 8 vectors determine that S(5,8,24) design. Then a 12 punctured code of this (24,2 ,8) code C' formed by removing the coordinate place corresponding to w is a (23,212,7) code C , (cf. (2.5.5)), whose weight 7 vectors determine the S(4,7,23) design S that was given. Were S to be contained in any other copy of C1 of 3 12,7) code, then the parity check code, Ci 2 12 formed from C1 would have its weight 8 vectors determinixx; (23,2 (24.2 ,8) a distinct copy of the S(5,8,24) (by Theorem (3.5)) and this would have (by Theorem (11.3.9)) a distinct S(4,7,23) design as a derived design. This contradicts the fact that the punctured code of Ci , namely Cl itself, has its weight 7 vectors determining the same design S as the code 1 C . Hence, S builds a unique (23,2 2,7) code C . // §12.4 The Uniqueness pg_the GOLAY 123,212,?) and XGOLAY (24,212,81 Binary Codes Since each (23,212,?) code and (24,212,8) code containing .9 has its minimum non-zero weight vectors determining respectively the unique S(4,7,23) and S(5,8,24) designs we have from Section 12.3 and Chapter 11 that: (4.1) Theorem: Up to a permutation of the 23 basis 1 vectors of V(23,2), the GOLAY (23,2 2,7) code is unique. Up to a permutation of the 24 basis vectors of V(24,2) the 12.15 XGOLAY (24,212,8) code is unique. ‘ggaag: By Theorem (11.2.8) and Corollary (11.3.10) the S(4,7,23) and S(5,8,24) designs are unique up to a permutation of their 23 and 24 point sets respectively. Then by Theorems (3.6) and (3.5) these designs build unique (23,212,7) and (24,212,8) codes respectively. // i "'74 Furthermore, due to the fact that these Steiner systems build the respective codes in unique ways, we have: 1": (4.2) Theorem: The automorphism groups of the (23,212,?) ' and (24,212,8) codes containing 9_ are isomorphic to the automorphism groups of the respective Steiner systems S(4,7,23) and S(5,8,24) determined by the minimum non-zert> weight vectors of the codes. These automorphism groups are respectively 4- and 5-transitive on the 23 and 24 basis vectors of V(23,2) and V(24,2), while stabilizing these codes. Proof: Use Theorems (3.6) and (3.5), and Theorems (11.2.18) and (11.3.14). // BIBLIOGRAPHY 10. 11. 12. 13. 14. BIBLIOGRAPHY Artin, The orders pg the classical simple groups, Comm. Pure Appl. Math. §(l955), 455—72. F. Assmus and H. F. Mattson, gm tactical configpr rations and error-correcting codes, Journal of Comb. Theory 3(1967), 243-257. R. Berlekamp, Algebraic coding theory, McGraw Hill, New York, 1968. R. Berlekamp, Coding theory and the Mathieu groups, Information and Control, g§(l97l), 40—64. C. Bussemaker and J. J. Seidel, Symmetric Hadamard matrices pg order 29, Proc. Inter. Conf. Combin. Math., N. Y. Acad. Sci. (1970), 66—79. C. Bussemaker and J. J. Seidel, Symmetric Hadamard matrices pg order 36, Technological University Eindhoven, The Netherlands, T. H. Report 70-WSK-02, (1970). Calabi and E. Myrvaagnes, gm the minimal weight 2; binary groap codes, Correspondence IEEE Trans. on Inform. Theory IT-lO-4 (1964). D. Carmichael, Introduction mg the theory pg groups pg finite order, Dover Publ., New York, (1956). H. Conway, a_group pg order 8,315,553,613,082,720y000, Bull. Lond. Math. Soc. g(l969), 79-88. M. Conwell, The three space PGj3,2) and its group, Ann. of Math., (2), gg(1910), 60-76. Dembowski, Finite geometries, Berlin, Springer (1968). Dembowski, Some characterizations pg finite projective spaces, Arch. Math. gg(l960), 465-469. E. Dickson, Linear groups, Dover Pub., New York, (1958), p. 309. L. Edge, The geometry pg linear fractional group LF(4,2 , Proc. London Math. Soc. (2) 3(1954), 317-342. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 8.2 J. M. Goethals, gm the Golay perfect binary code, Journal of Comb. Theory, 11(1971), 178—186. J. M. Goethals, 9p t-designs and threshold decoding, Univ. of North Carolina, Institute of Statistics Mimeo Series No. 600.29, June, 1970. J. M. Goethals and S. L. Snover, Neargngerfect Binary Codes, Discrete Mathematics, 2(1972), 65-88. S. M. Johnson, a new upper bound for error-correcting codes, IRE Trans. Inform. Theory IT—8, (1962), 203-207. W. Jonsson, am the Mathieu groups M22, M23, M24, and the uniqueness pg the associated Steiner systems, Math. Z., 125(1972), 193-214. A. M. Kerdock, a_class pg low-rate nonlinear binary codes, Information and Control 2Q_no. 2 (1972), 182-187. J. H. Van Lint, Coding theory, Lecture notes gm mathematics, no. 201, Springer-Verlag, New York (1971). C. L. Liu, B. G. Ong, and G. R. Ruth, a construction scheme for linear and non-linear codes, Discrete Mathematics, 3(1973), 171—184. H. Luneburg, Transitive Erweiterungen eindlicher Permutationsgruppen, Lecture notes in mathematics, no. 84, Springer-Verlag, New York (1969). Mathieu, Journal de Mathematiques (1861), p. 270. N. S. Mendelsohn, Intersection numbers of t-designs, Studie in pure mathematics, ed. L._Mirsky, New York, Academic Press (1971), 145—150. D. M. Mesner, Sets pg disjoint lines gp_ PG(3,2), Canad. J. Math., mg (1967), 273-280. M. Nadler, a 325point, n = 12, d = 5 code, IRE Trans. Inform. Theory IT-8 (1962), 58. A. W. Nordstrom and J. P. Robinson, am optimum nonlinear code, Information and Control, ggjl967), 613-616. L. J. Paige, A note on the Mathieu groups, Canad. J. Math., 2(1956),_TS—18. W. W. Peterson, Error-correcting codes, MIT Press, Cambridge (1961). Ll 31. 32. 33. 34, 35. 36. 37. 38. 39. 40. Pless, 0n the uniqueness of the Golay codes, Journal of Comb. Theory, —g1(l968), 215- 228. .P. Preparata, A class of optimum nonlinear double— error- correcting codes, Information and Control, g§(l968), 378— 400. Schonheim, 9p linear and nonlinear single-error- correctipg qanary perfect codes, Information and Control gg_(l968), 23-26. Tietavainen and A. Perko, There are mp unknown perfect binary codes, Ann. Univ. Turku, Ser. AI 148(1971). A. Todd, Projective and analytical geometry, ; . Sir Issac Pitman and Sons, Ltd., London (1958). 5'“ L. Vasil'ev and B. Lindstrom, 0n group and nonjgrour> perfect codes, Math. Scand. 25(1969), 149- 158. Veblen and J. W. Young, Projective geometry, Ginn and Co., New York (1918). Wagner, 0n collineation groups of projective spaces I, Math. Z. 76(1961), 411- 426. Witt, Die S-fach transitiven Gruppen von Mathieu, Abh. Math. Sem. Hamb. $211938), 256-264. Witt, Uber Steinersche Systeme, Abh. Math. Sem. Hambn, .g2(l938), 265-275.