Sphere Packings, Lattices and Groups (Grundlehren der mathematischen Wissenschaften (290))

analog of Wells ' "Structural Inorganic Chemistry" [Wel4]. Recent work on quasi-crystals has made use of six-and eight-dimensional lattices.Higher-dimensional lattices are of current interest in physics. Recent developments in dual theory and superstring theory have involved the E8 and Leech lattices, and there are also connections with the Monster group.Other applications and references for these topics will be found in Chap. 1.Who should buy this book. Anyone interested in sphere packings, in lattices in n-dimensional space, or in the Leech lattice. Mathematicians interested in finite groups, quadratic forms, the geometry of numbers, or combinatorics. Engineers who wish to construct n-dimensional codes for a band-limited channel, or to design n-dimensional vector quantizers. Chemists and physicists interested in n-dimensional crystallography.Preface ix brief discussion of reflection groups and of the technique of gluing lattices together.Chapters 5-8 are devoted to techniques for constructing sphere packings. Many of the constructions in Chaps. 5 and 7 are based on error-correcting codes; other constructions in Chapter 5 build up packings by layers. Layered packings are studied in greater detail in Chap. 6, where the formal concept of a laminated lattice An is introduced. Chapter 8 uses a number of more sophisticated algebraic techniques to construct lattices.Chapter 9 introduces analytical methods for finding bounds on the best codes, sphere packings and related problems. The methods use techniques from harmonic analysis and linear programming. We give a simplified account of Kabatiansky and Levenshtein's recent sphere packing bounds.Chapters 10 and 11 study the Golay codes of length 12 and 24, the associated Steiner systems S (5,6,12) and S (5, 8, 24), and their automorphism groups MI2 and M 24• The MINIMOG and MOG (or Miracle Octad Generator> and the Tetracode and Hexacode are computational tools that make it easy to perform calculations with these objects. These two chapters also study a number of related groups, in particular the automorphism group Coo (or' 0) of the Leech lattice. The Appendix to Chapter 10 describes all the sporadic simple groups.Chapter 12 gives a short proof that the Leech lattice is the unique even unimodular lattice with no vectors of norm 2. Chapter 13 solves the kissing number problem in 8 and 24 dimensions -the E 8 and Leech lattices have the highest possible kissing numbers in these dimensions. Chapter 14 shows that these arrangements of spheres are essentially unique.Chapters 15-19 deal with the classification of integral quadratic forms. Chapters 16 and 18 together give three proofs that Niemeier's enumeration of the 24-dimensional even unimodular lattices is correct. In Chap. 19 we find all the extremal odd unimodular lattices in any dimension.Chapters 20 and 21 are concerned with geometric properties of lattices. In Chap. 20 we di~cuss algorithms which, given an arbitrary point of the space, find the closest lattice point. These algorithms can be used for vector quantizing or for encoding and decoding lattice codes for a band limited channel. Chapter 21 studies the Voronoi cells of lattices and their second moments.Soon after discovering his lattice, John Leech conjectured that its covering radius was equal to ..fi times its packing radius, but was unable to find a proof. In 1980 Simon Norton found an ingenious argument which shows that the covering radius is no more than 1.452... times the packing radius (Chap. 22), and shortly afterwards Richard Parker and the authors managed to prove Leech's conjecture (Chap. 23).Our method of proof involves finding all the "deep holes" in the Leech lattice, i.e. all points of 24-dimensional space that are maximally distant x Preface from the lattice. We were astonished to discover that there are precisely 23 distinct types of deep hole, and that they are in one-to-one correspondence with the Niemeier lattices (the 24-dimensional even unimodular lattices of minimal norm 2) -see Theorem 2 of Chap. 23. Chapter 23, or the Deep Holes paper, as it is usually called, has turned out to be extremely fruitful, having stimulated the remaining chapters in the book, also Chap. 6, and several journal articles.In Chap. 24 we give 23 constructions for the Leech lattice, one for each of the deep holes or Niemeier lattices. Two of these are the familiar constructions based on the Golay codes. In the second half of Chap. 24 we introduce the hole diagram of a deep hole, which describes the environs of the hole. Chapter 25 (the Shallow Holes paper) uses the results of Chap. 23 and 24 to classify all the holes in the Leech lattice.Considerable light is thrown on these mysteries by the realization that the Leech lattice and the Niemeier lattices can all be obtained very easily from a single lattice, namely 1125,1> the unique even unimodular lattice in Lorentzian space R 25 ,). For any vector w E R 25 ,), let wl-= Ix EII 25 ,):X•w=0}.Then if w is the special vector W25 = (0,1,2,3, .... 23,24170), wl-/w is the Leech lattice, and other choices for w lead to the 23 Niemeier lattices.The properties of the Leech lattice are closely related to the geometry of the lattice 1125,). The automorphism groups of the Lorentzian lattice In,) for n ~ 19 and lIn,) for n = 1, 9 and 17 were found by Vinberg, Kaplinskaja and Meyer. Chapter 27 finds the automorphism group of 1125,). This remarkable group has a reflection subgroup with a Coxeter diagram that is, speaking loosely, isomorphic to the Leech lattice. More precisely, a set of fundamental roots for 1125,) consists of the vectors r E 1125,) satisfying r . r = 2, r . W25 = -I , and we call these the Leech roots. Chapter 26 shows that there is an isometry between the set of Leech roots and the points of the Leech lattice. Then the Coxeter part of the automorphism group of Il25,) is just the Coxeter group generated by the Leech roots (Theorem I of Chap. 27).Since 1125,) is a natural quadratic form to study, whose definition certainly does not mention the Leech lattice, it is surprising that the Leech lattice essentially determines the automorphism group of the form.The Leech roots also provide a better understanding of the automorphism groups of the other lattices In,) and lIn,), as we see in Chap. 28. This chapter also contains an extensive table of Leech roots. Chapter 29 describes a construction for the Monster simple group, and the Preface XI final chapter describes an infinite-dimensional Lie algebra that is obtained from the Leech roots, and conjectures that it may be related to the Monster.The book concludes with a bibliography of about 1550 items.The structure of this book. Our original plan was simply for a collection of reprints. But over the past two years the book has been completely transformed: many new chapters have been added, and the original chapters have been extensively rewritten to bring them up to date, to reduce duplicated material, to adopt a uniform notation and terminology, and to eliminate errors.We have however allowed a certain amount of duplication to remain, to make for easier reading. Because some chapters were written at different times and by different authors, the reader will occasionally notice differences in style from chapter to chapter.The arrangement of the chapters presented us with a difficult problem. We feel that readers are best served by grouping them in the present arrangement, even though it means that one or two chapters are not in strict logical order. The worst flaw is that the higher-dimensional part of the laminated lattices chapter (Chap. 6) depends on knowledge of the deep holes in the Leech lattice given in Chap. 23. But the preceding part of Chapter 6, which includes all the best lattice packings known in small dimensions, had to appear as early as possible. The Third Edition Of This Book Continues To Pursue The Question, What Is The Most Efficient Way To Pack A Large Number Of Equal Spheres In N-dimensional Euclidean Space? The Authors Also Continue To Examine Related Problems Such As The Kissing Number Problem, The Covering Problem, The Quantizing Problem, And The Classification Of Lattices And Quadratic Forms. Like The Previous Edition, The Third Edition Describes The Connections Of These Questions With Other Areas Of Mathematics And Science Such As Coding Theory, Digital Communication, Number Theory, Group Theory, Analog-to-digital Conversion And Data Compression, And N-dimensional Crystallography. Of Special Interest In The Third Edition Is A Report On Some Recent Developments In The Field And A Supplementary Bibliography For 1988-1998 Containing Over 800 Items.--book Jacket. Sphere Packings And Kissing Numbers / J.h. Conway And N.j.a. Sloane -- Coverings, Lattices And Quantizers / J.h. Conway And N.j.a. Sloane -- Codes, Designs And Groups / J.h. Conway And N.j.a. Sloane -- Certain Important Lattices And Their Properties / J.h. Conway And N.j.a. Sloane -- Sphere Packing And Error-correcting Codes / J. Leech And N.j.a. Sloane -- Laminated Lattices / J.h. Conway And N.j.a. Sloane -- Futher Connections Between Codes And Lattices / N.j.a. Sloane -- Algebraic Constructions For Lattices / J.h. Conway And N.j.a. Sloane -- Bounds For Codes And Sphere Packings / N.j.a. Sloane -- Three Lectures On Exceptional Groups / J.h. Conway -- Golay Codes And The Mathieu Groups / J.h. Conway -- Characterization Of The Leech Lattice / J.h. Conway -- Bounds On Kissing Numbers / A.m. Odlyzko And N.j.a. Sloane -- Uniqueness Of Certain Spherical Codes / E. Bannai And N.j.a. Sloane -- On The Classification Of Integral Quadratic Forms / J.h. Conway And N.j.a. Sloane -- Enumeration Of Unimodular Lattices / J.h. Conway And N.j.a. Sloane -- 24-dimensional Odd Unimodular Lattices / R.e. Borcherds -- Even Unimodular 24-dimensional Lattices / B.b. Venkov -- Enumeration Of Extremal Self-dual Lattices / J.h. Conway, A.m. Odlyzko And N.j.a. Sloane -- Finding The Closet Lattice Point / J.h. Conway And N.j.a. Sloane -- Voronoi Cells Of Lattices And Quantization Errors / J.h. Conway And N.j.a. Sloane -- Bound For The Covering Radius Of The Leech Lattice / S.p. Norton -- Covering Radius Of The Leech Lattice / J.h. Conway, R.a. Parker And N.j.a. Sloane -- Twenty-three Constructions For The Leech Lattice / J.h. Conway And N.j.a Sloane -- Cellular Structure Of The Leech Lattice / R.e. Borcherds, J.h. Conway And L. Queen -- Lorentzian Forms For The Leech Lattice / J.h. Conway And N.j.a. Sloane -- Automorphism Group Of The 26-diemnsional Even Unimodular Lorentzian Lattice / J.h. Conway -- Leech Roots And Vinberg Groups / J.h. Conway And N.j.a. Sloane -- Monster Group And Its 196884-dimensional Space / J.h. Conway. J.h. Conway, N.j.a. Sloane ; With Additional Contributions By E. Bannai ... [et Al.]. Includes Bibliographical References (p. [574]-679) And Index. Front Matter....Pages i-xxvii Sphere Packings and Kissing Numbers....Pages 1-30 Coverings, Lattices and Quantizers....Pages 31-62 Codes, Designs and Groups....Pages 63-93 Certain Important Lattices and Their Properties....Pages 94-135 Sphere Packing and Error-Correcting Codes....Pages 136-156 Laminated Lattices....Pages 157-180 Further Connections Between Codes and Lattices....Pages 181-205 Algebraic Constructions for Lattices....Pages 206-244 Bounds for Codes and Sphere Packings....Pages 245-266 Three Lectures on Exceptional Groups....Pages 267-298 The Golay Codes and The Mathieu Groups....Pages 299-330 A Characterization of the Leech Lattice....Pages 331-336 Bounds on Kissing Numbers....Pages 337-339 Uniqueness of Certain Spherical Codes....Pages 340-351 On the Classification of Integral Quadratic Forms....Pages 352-405 Enumeration of Unimodular Lattices....Pages 406-420 The 24-Dimensional Odd Unimodular Lattices....Pages 421-426 Even Unimodular 24-Dimensional Lattices....Pages 427-438 Enumeration of Extremal Self-Dual Lattices....Pages 439-442 Finding the Closest Lattice Point....Pages 443-448 Voronoi Cells of Lattices and Quantization Errors....Pages 449-475 A Bound for the Covering Radius of the Leech Lattice....Pages 476-477 The Covering Radius of the Leech Lattice....Pages 478-505 Twenty-Three Constructions for the Leech Lattice....Pages 506-512 The Cellular Structure of the Leech Lattice....Pages 513-521 Lorentzian Forms for the Leech Lattice....Pages 522-526 The Automorphism Group of the 26-Dimensional Lorentzian Lattice....Pages 527-531 Leech Roots and Vinberg Groups....Pages 532-553 The Monster Group and its 196884-Dimensional Space....Pages 554-567 A Monster Lie Algebra?....Pages 568-571 Back Matter....Pages 572-665 The main themes. This book is mainly concerned with the problem of packing spheres in Euclidean space of dimensions 1,2,3,4,5,.... Given a large number of equal spheres, what is the most efficient (or densest) way to pack them together? We also study several closely related problems: the kissing number problem, which asks how many spheres can be arranged so that they all touch one central sphere of the same size; the covering problem, which asks for the least dense way to cover n-dimensional space with equal overlapping spheres; and the quantizing problem, important for applications to analog-to-digital conversion (or data compression), which asks how to place points in space so that the average second moment of their Voronoi cells is as small as possible. Attacks on these problems usually arrange the spheres so their centers form a lattice. Lattices are described by quadratic forms, and we study the classification of quadratic forms. Most of the book is devoted to these five problems. The miraculous enters: the E 8 and Leech lattices. When we investigate those problems, some fantastic things happen! There are two sphere packings, one in eight dimensions, the E 8 lattice, and one in twenty-four dimensions, the Leech lattice A, which are unexpectedly good and very 24 symmetrical packings, and have a number of remarkable and mysterious properties, not all of which are completely understood even today. We now apply the algorithm above to find the 121 orbits of norm -2 vectors from the (known) nann 0 vectors, and then apply it again to find the 665 orbits of nann -4 vectors from the vectors of nann 0 and -2. The neighbors of a strictly 24 dimensional odd unimodular lattice can be found as follows. If a norm -4 vector v E II. corresponds to the sum 25 1 of a strictly 24 dimensional odd unimodular lattice A and a!-dimensional lattice, then there are exactly two nonn-0 vectors of ll25,1 having inner product -2 with v, and these nann 0 vectors correspond to the two even neighbors of A. The enumeration of the odd 24-dimensional lattices. Figure 17.1 shows the neighborhood graph for the Niemeier lattices, which has a node for each Niemeier lattice. If A and B are neighboring Niemeier lattices, there are three integral lattices containing A n B, namely A, B, and an odd unimodular lattice C (cf. [Kne4]). An edge is drawn between nodes A and B in Fig. 17.1 for each strictly 24-dimensional unimodular lattice arising in this way. Thus there is a one-to-one correspondence between the strictly 24-dimensional odd unimodular lattices and the edges of our neighborhood graph. The 156 lattices are shown in Table 17.I. Figure I 7. I also shows the corresponding graphs for dimensions 8 and 16. Contents: Sphere Packings and Kissing Numbers Coverings, Lattices and Quantizers Codes, Designs and Groups Certain Important Lattices and Their Properties Sphere Packing and Error-Correcting Codes Laminated Lattices Further Connections Between Codes and Lattices Algebraic Constructions for Lattices Bounds for Codes and Sphere Packings Three Lectures on Exceptional Groups The Golay Codes and the Mathieu Groups A Characterization of the Leech Lattice Bounds on Kissing Numbers Uniqueness of Certain Spherical Codes On the Classification of Integral Quadratic Forms Enumeration of Unimodular Lattices The 24-Dimensional Odd Unimodular Lattices Even Unimodular 24-Dimensional Lattices Enumeration of Extremal Self-Dual Lattices Finding the Closest Lattice Point Voronoi Cells of Lattices and Quantization Errors A Bound for the Covering Radius of the Leech Lattice The Covering Radius of the Leech Lattice Twenty-Three Constructions for the Leech Lattice The Cellular Structure of the Leech Lattice Lorentzian Forms for the Leech Lattice The Automorphism Group of the 26-Dimensional Even Unimodular Lorentzian Lattice Leech Roots and Vinberg Groups The Monster Group and its 196884-Dimensional Space A Monster Lie Algebra?- Bibliography Index. The third edition of this definitive and popular book continues to pursue the question: what is the most efficient way to pack a large number of equal spheres in n-dimensional Euclidean space? The authors also examine such related issues as the kissing number problem, the covering problem, the quantizing problem, and the classification of lattices and quadratic forms. There is also a description of the applications of these questions to other areas of mathematics and science such as number theory, coding theory, group theory, analogue-to-digital conversion and data compression, n-dimensional crystallography, dual theory and superstring theory in physics. New and of special interest is a report on some recent developments in the field, and an updated and enlarged supplementary bibliography with over 800 items. This book is an exposition of the mathematics arising from the theory of sphere packings. Considerable progress has been made on the basic problems in the field, and the most recent research is presented here. Connections with many areas of pure and applied mathematics, for example signal processing, coding theory, are thoroughly discussed.