Sphere Packings, Lattices and Groups

by Conway, John Horton; Sloane, N. J. A.

• ISBN13: 9780387985855
• ISBN10: 0387985859
• Edition: 3rd
• Format: Hardcover
• Copyright: 1998-12-01
• Publisher: Springer Verlag

Summary

The third edition of this timely, 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 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 applications of these questions to other areas of mathematics and science such as number theory, coding theory, group theory, analog-to-digital conversion and data compression, n-dimensional crystallography, dual theory and superstring theory in physics. Of special interest to the third edtion is a brief report on some recent developments in the field and an updated and enlarged Supplementary Bibliography with over 800 items.

Table of Contents

Preface to First Edition	v	(10)
Preface to Third Edition	xv	(46)
List of Symbols	lxi
Chapter 1 Sphere Packings and Kissing Numbers	1	(30)
J.H. Conway
N.J.A. Sloane
1. The Sphere Packing Problem	1	(20)
1.1 Packing Ball Bearings	1	(2)
1.2 Lattice Packings	3	(4)
1.3 Nonlattice Packings	7	(1)
1.4 n-Dimensional Packings	8	(4)
1.5 Sphere Packing Problem--Summary of Results	12	(9)
2. The Kissing Number Problem	21	(10)
2.1 The Problem of the Thirteen Spheres	21	(1)
2.2 Kissing Numbers in Other Dimensions	21	(3)
2.3 Spherical Codes	24	(2)
2.4 The Construction of Spherical Codes from Sphere Packings	26	(1)
2.5 The Construction of Spherical Codes from Binary Codes	26	(1)
2.6 Bounds on A(n, Tita)	27	(2)
Appendix: Planetary Perturbations	29	(2)
Chapter 2 Coverings, Lattices and Quantizers	31	(32)
J.H. Conway
N.J.A. Sloane
1. The Covering Problem	31	(10)
1.1 Covering Space with Overlapping Spheres	31	(2)
1.2 The Covering Radius and the Voronoi Cells	33	(3)
1.3 Covering Problem--Summary of Results	36	(4)
1.4 Computational Difficulties in Packings and Coverings	40	(1)
2. Lattices, Quadratic Forms and Number Theory	41	(15)
2.1 The Norm of a Vector	41	(1)
2.2 Quadratic Forms Associated with a Lattice	42	(2)
2.3 Theta Series and Connections with Number Theory	44	(3)
2.4 Integral Lattices and Quadratic Forms	47	(3)
2.5 Modular Forms	50	(2)
2.6 Complex and Quaternionic Lattices	52	(4)
3. Quantizers	56	(7)
3.1 Quantization, Analog-to-Digital Conversion and Data Compression	56	(3)
3.2 The Quantizer Problem	59	(1)
3.3 Quantizer Problem--Summary of Results	59	(4)
Chapter 3 Codes, Designs and Groups	63	(31)
J.H. Conway
N.J.A. Sloane
1. The Channel Coding Problem	63	(12)
1.1 The Sampling Theorem	63	(3)
1.2 Shannon's Theorem	66	(3)
1.3 Error Probability	69	(2)
1.4 Lattice Codes for the Gaussian Channel	71	(4)
2. Error-Correcting Codes	75	(13)
2.1 The Error-Correcting Code Problem	75	(2)
2.2 Further Definitions from Coding Theory	77	(2)
2.3 Repetition, Even Weight and Other Simple Codes	79	(1)
2.4 Cyclic Codes	79	(2)
2.5 BCH and Reed-Solomon Codes	81	(1)
2.6 Justesen Codes	82	(1)
2.7 Reed-Muller Codes	83	(1)
2.8 Quadratic Residue Codes	84	(1)
2.9 Perfect Codes	85	(1)
2.10 The Pless Double Circulant Codes	86	(1)
2.11 Goppa Codes and Codes from Algebraic Curves	87	(1)
2.12 Nonlinear Codes	87	(1)
2.13 Hadamard Matrices	87	(1)
3. t-Designs, Steiner Systems and Spherical t-Designs	88	(2)
3.1 t-Designs and Steiner Systems	88	(1)
3.2 Spherical t-Designs	89	(1)
4. The Connections with Group Theory	90	(4)
4.1 The Automorphism Group of a Lattice	90	(2)
4.2 Constructing Lattices and Codes from Groups	92	(2)
Chapter 4 Certain Important Lattices and Their Properties	94	(42)
J.H. Conway
N.J.A. Sloane
1. Introduction	94	(1)
2. Reflection Groups and Root Lattices	95	(4)
3. Gluing Theory	99	(2)
4. Notation; Theta Functions	101	(5)
4.1 Jacobi Theta Functions	102	(4)
5. The n-Dimensional Cubic Lattice Z(n)	106	(2)
6. The n-Dimensional Lattices A(n) and A(*)(n)	108	(9)
6.1 The Lattice A(n)	108	(2)
6.2 The Hexagonal Lattice	110	(2)
6.3 The Face-Centered Cubic Lattice	112	(1)
6.4 The Tetrahedral or Diamond Packing	113	(1)
6.5 The Hexagonal Close-Packing	113	(2)
6.6 The Dual Lattice A(*)(n)	115	(1)
6.7 The Body-Centered Cubic Lattice	116	(1)
7. The n-Dimensional Lattices D(n) and D(*)(n)	117	(3)
7.1 The Lattice D(n)	117	(1)
7.2 The Four-Dimensional Lattice D(4)	118	(1)
7.3 The Packing D(n)	119	(1)
7.4 The Dual Lattice D(*)(n)	120	(1)
8. The Lattices E(6), E(7) and E(8)	120	(7)
8.1 The 8-Dimensional Lattice E(8)	120	(4)
8.2 The 7-Dimensional Lattice E(7) and E(*)(7)	124	(1)
8.3 The 6-Dimensional Lattice E(6) and E(*)(6)	125	(2)
9. The 12-Dimensional Coxeter-Todd Lattice K(12)	127	(2)
10. The 16-Dimensional Barnes-Wall Lattice A(16)	129	(2)
11. The 24-Dimensional Leech Lattice A(24)	131	(5)
Chapter 5 Sphere Packing and Error-Correcting Codes	136	(21)
J. Leech
N.J.A. Sloane
1. Introduction	136	(1)
1.1 The Coordinate Array of a Point	137	(1)
2. Construction A	137	(4)
2.1 The Construction	137	(1)
2.2 Center Density	137	(1)
2.3 Kissing Numbers	138	(1)
2.4 Dimensions 3 to 6	138	(1)
2.5 Dimensions 7 and 8	138	(1)
2.6 Dimensions 9 to 12	139	(1)
2.7 Comparison of Lattice and Nonlattice Packings	140	(1)
3. Construction B	141	(1)
3.1 The Construction	141	(1)
3.2 Center Density and Kissing Numbers	141	(1)
3.3 Dimensions 8,9 and 12	142	(1)
3.4 Dimensions 15 to 24	142	(1)
4. Packings Built Up by Layers	142	(4)
4.1 Packing by Layers	142	(2)
4.2 Dimensions 4 to 7	144	(1)
4.3 Dimensions 11 and 13 to 15	144	(1)
4.4 Density Doubling and the Leech Lattice A(24)	145	(1)
4.5 Cross Sections of A(24)	145	(1)
5. Other Constructions from Codes	146	(4)
5.1 A Code of Length 40	146	(1)
5.2 A Lattice Packing in R(40)	147	(1)
5.3 Cross Sections of A(40)	148	(1)
5.4 Packings Based on Ternary Codes	148	(1)
5.5 Packings Obtained from the Pless Codes	148	(1)
5.6 Packings Obtained from Quadratic Residue Codes	149	(1)
5.7 Density Doubling in R(24) and R(48)	149	(1)
6. Construction C	150	(7)
6.1 The Construction	150	(1)
6.2 Distance Between Centers	150	(1)
6.3 Center Density	150	(1)
6.4 Kissing Numbers	151	(1)
6.5 Packings Obtained from Reed-Muller Codes	151	(1)
6.6 Packings Obtained from BCH and Other Codes	152	(1)
6.7 Density of BCH Packings	153	(2)
6.8 Packings Obtained from Justesen Codes	155	(2)
Chapter 6 Laminated Lattices	157	(24)
J.H. Conway
N.J.A. Sloane
1. Introduction	157	(6)
2. The Main Results	163	(5)
3. Properties of A(0) to A(8)	168	(2)
4. Dimensions 9 to 16	170	(4)
5. The Deep Holes in A(16)	174	(2)
6. Dimensions 17 to 24	176	(1)
7. Dimensions 25 to 48	177	(2)
Appendix: The Best Integral Lattices Known	179	(2)
Chapter 7 Further Connections Between Codes and Lattices	181	(25)
N.J.A. Sloane
1. Introduction	181	(1)
2. Construction A	182	(3)
3. Self-Dual (or Type I) Codes and Lattices	185	(4)
4. Extremal Type I Codes and Lattices	189	(2)
5. Construction B	191	(1)
6. Type II Codes and Lattices	191	(2)
7. Extremal Type II Codes and Lattices	193	(4)
8. Constructions A and B for Complex Lattices	197	(5)
9. Self-Dual Nonbinary Codes and Complex Lattices	202	(3)
10. Extremal Nonbinary Codes and Complex Lattices	205	(1)
Chapter 8 Algebraic Constructions for Lattices	206	(39)
J.H. Conway
N.J.A. Sloane
1. Introduction	206	(1)
2. The Icosians and the Leech Lattice	207	(4)
2.1 The Icosian Group	207	(3)
2.2 The Icosian and Turyn-Type Constructions for the Leech Lattice	210	(1)
3. A General Setting for Construction A, and Quebbemann's 64-Dimensional Lattice	211	(4)
4. Lattices Over Z[e(Piet/4)], and Quebbemann's 32-Dimensional Lattice	215	(6)
5. McKay's 40-Dimensional Extremal Lattice	221	(1)
6. Repeated Differences and Craig's Lattices	222	(2)
7. Lattices from Algebraic Number Theory	224	(8)
7.1 Introduction	224	(1)
7.2 Lattices from the Trace Norm	224	(3)
7.3 Examples from Cyclotomic Fields	227	(1)
7.4 Lattices from Class Field Towers	227	(2)
7.5 Unimodular Lattices with an Automorphism of Prime Order	229	(3)
8. Constructions D and D'	232	(4)
8.1 Construction D	232	(1)
8.2 Examples	233	(2)
8.3 Construction D'	235	(1)
9. Construction E	236	(2)
10. Examples of Construction E	238	(7)
Chapter 9 Bounds for Codes and Sphere Packings	245	(22)
N.J.A. Sloane
1. Introduction	245	(4)
2. Zonal Spherical Functions	249	(8)
2.1 The 2-Point-Homogeneous Spaces	250	(2)
2.2 Representations of G	252	(1)
2.3 Zonal Spherical Functions	253	(3)
2.4 Positive-Definite Degenerate Kernels	256	(1)
3. The Linear Programming Bounds	257	(8)
3.1 Codes and Their Distance Distributions	257	(1)
3.2 The Linear Programming Bounds	258	(2)
3.3 Bounds for Error-Correcting Codes	260	(3)
3.4 Bounds for Constant-Weight Codes	263	(1)
3.5 Bounds for Spherical Codes and Sphere Packings	263	(2)
4. Other Bounds	265	(2)
Chapter 10 Three Lectures on Exceptional Groups	267	(32)
J.H. Conway
1. First Lecture	267	(7)
1.1 Some Exceptional Behavior of the Groups L(n)(q)	267	(2)
1.2 The Case p = 3	269	(1)
1.3 The Case p = 5	269	(1)
1.4 The Case p = 7	269	(2)
1.5 The Case p = 11	271	(2)
1.6 A Presentation for M(12)	273	(1)
1.7 Janko's Group of Order 175560	273	(1)
2. Second Lecture	274	(12)
2.1 The Mathieu Group M(24)	274	(2)
2.2 The Stabilizer of an Octad	276	(2)
2.3 The Structure of the Golay Code XXX(24)	278	(1)
2.4 The Structure of P (Omega)/XXX(24)	278	(1)
2.5 The Maximal Subgroups of M(24)	279	(4)
2.6 The Structure of P(Omega)	283	(3)
3. Third Lecture	286	(13)
3.1 The Group Co(0) = 0 and Some of its Subgroups	286	(1)
3.2 The Geometry of the Leech Lattice	286	(1)
3.3 The Group 0 and its Subgroup N	287	(3)
3.4 Subgroups of 0	290	(2)
3.5 The Higman-Sims and McLaughlin Groups	292	(1)
3.6 The Group Co(3) = 3	293	(1)
3.7 Involutions in 0	294	(1)
3.8 Congruences for Theta Series	294	(1)
3.9 A Connection Between 0 and Fischer's Group Fi(24)	295	(1)
Appendix: On the Exceptional Simple Groups	296	(3)
Chapter 11 The Golay Codes and the Mathieu Groups	299	(32)
J.H. Conway
1. Introduction	299	(1)
2. Definitions of the Hexacode	300	(2)
3. Justification of a Hexacodeword	302	(1)
4. Completing a Hexacodeword	302	(1)
5. The Golay Code XXX(24) and the MOG	303	(2)
6. Completing Octads from 5 of their Points	305	(2)
7. The Maximal Subgroups of M(24)	307	(1)
8. The Projective Subgroup L(2)(23)	308	(1)
9. The Sextet Group 2(6):3 S(6)	309	(2)
10. The Octad Group 2(4):A(8)	311	(3)
11. The Triad Group and the Projective Plane of Order 4	314	(2)
12. The Trio Group 2(6):(S(3) X L(2)(7))	316	(2)
13. The Octern Group	318	(1)
14. The Mathieu Group M(23)	319	(1)
15. The Group M(22):2	319	(1)
16. The Group M(12), the Tetracode and the MINIMOG	320	(3)
17. Playing Cards and Other Games	323	(4)
18. Further Constructions for M(12)	327	(4)
Chapter 12 A Characterization of the Leech Lattice	331	(6)
J.H. Conway
Chapter 13 Bounds on Kissing Numbers	337	(3)
A.M. Odlyzko
N.J.A. Sloane
1. A General Upper Bound	337	(1)
2. Numerical Results	338	(2)
Chapter 14 Uniqueness of Certain Spherical Codes	340	(12)
E. Bannai
N.J.A. Sloane
1. Introduction	340	(2)
2. Uniqueness of the Code of Size 240 in Omega(8)	342	(2)
3. Uniqueness of the Code of Size 56 in Omega(7)	344	(1)
4. Uniqueness of the Code of Size 196560 in Omega(24)	345	(4)
5. Uniqueness of the Code of Size 4600 in Omega(23)	349	(3)
Chapter 15 On the Classification of Integral Quadratic Forms	352	(54)
J.H. Conway
N.J.A. Sloane
1. Introduction	352	(2)
2. Definitions	354	(2)
2.1 Quadratic Forms	354	(1)
2.2 Forms and Lattices; Integral Equivalence	355	(1)
3. The Classification of Binary Quadratic Forms	356	(10)
3.1 Cycles of Reduced Forms	356	(1)
3.2 Definite Binary Forms	357	(2)
3.3 Indefinite Binary Forms	359	(5)
3.4 Composition of Binary Forms	364	(2)
3.5 Genera and Spinor Genera for Binary Forms	366	(1)
4. The p-Adic Numbers	366	(4)
4.1 The p-Adic Numbers	367	(1)
4.2 p-Adic Square Classes	367	(1)
4.3 An Extended Jacobi-Legendre Symbol	368	(1)
4.4 Diagonalization of Quadratic Forms	369	(1)
5. Rational Invariants of Quadratic Forms	370	(3)
5.1 Invariants and the Oddity Formula	370	(2)
5.2 Existence of Rational Forms with Prescribed Invariants	372	(1)
5.3 The Conventional Form of the Hasse-Minkowski Invariant	373	(1)
6. The Invariance and Completeness of the Rational Invariants	373	(5)
6.1 The p-Adic Invariants for Binary Forms	373	(2)
6.2 The p-Adic Invariants for n-Ary Forms	375	(2)
6.3 The Proof of Theorem 7	377	(1)
7. The Genus and its Invariants	378	(7)
7.1 p-Adic Invariants	378	(1)
7.2 The p-Adic Symbol for a Form	379	(1)
7.3 2-Adic Invariants	380	(1)
7.4 The 2-Adic Symbol	380	(1)
7.5 Equivalences Between Jordan Decompositions	381	(1)
7.6 A Canonical 2-Adic Symbol	382	(1)
7.7 Existence of Forms with Prescribed Invariants	382	(2)
7.8 A Symbol for the Genus	384	(1)
8. Classification of Forms of Small Determinant and of p-Elementary Forms	385	(3)
8.1 Forms of Small Determinant	385	(1)
8.2 p-Elementary Forms	386	(2)
9. The Spinor Genus	388	(8)
9.1 Introduction	388	(1)
9.2 The Spinor Genus	389	(1)
9.3 Identifying the Spinor Kernel	390	(1)
9.4 Naming the Spinor Operators for the Genus of f	390	(1)
9.5 Computing the Spinor Kernel from the p-Adic Symbols	391	(1)
9.6 Tractable and Irrelevant Primes	392	(1)
9.7 When is There Only One Class in the Genus?	393	(3)
10. The Classification of Positive Definite Forms	396	(6)
10.1 Minkowski Reduction	396	(3)
10.2 The Kneser Gluing Method	399	(1)
10.3 Positive Definite Forms of Determinant 2 and 3	399	(3)
11. Computational Complexity	402	(4)
Chapter 16 Enumeration of Unimodular Lattices	406	(15)
J.H. Conway
N.J.A. Sloane
1. The Niemeier Lattices and the Leech Lattice	406	(2)
2. The Mass Formulae for Lattices	408	(2)
3. Verifications of Niemeier's List	410	(3)
4. The Enumeration of Unimodular Lattices in Dimensions n is less than equal to 23	413	(8)
Chapter 17 The 24-Dimensional Odd Unimodular Lattices	421	(8)
R.E. Borcherds
Chapter 18 Even Unimodular 24-Dimensional Lattices	429	(12)
B.B. Venkov
1. Introduction	429	(1)
2. Possible Configurations of Minimal Vectors	430	(3)
3. On Lattices with Root Systems of Maximal Rank	433	(3)
4. Construction of the Niemeier Lattices	436	(3)
5. A Characterization of the Leech Lattice	439	(2)
Chapter 19 Enumeration of Extremal Self-Dual Lattices	441	(4)
J.H. Conway
A.M. Odlyzko
N.J.A. Sloane
1. Dimensions 1-16	441	(1)
2. Dimensions 17-47	441	(2)
3. Dimensions n is greater than or equal to 48	443	(2)
Chapter 20 Finding the Closest Lattice Point	445	(6)
J.H. Conway
N.J.A. Sloane
1. Introduction	445	(1)
2. The Lattices Z", D(n) and A(n)	446	(2)
3. Decoding Unions of Cosets	448	(1)
4. "Soft Decision" Decoding for Binary Codes	449	(1)
5. Decoding Lattices Obtained from Construction A	450	(1)
6. Decoding E(8)	450	(1)
Chapter 21 Voronoi Cells of Lattices and Quantization Errors	451	(27)
J.H. Conway
N.J.A. Sloane
1. Introduction	451	(2)
2. Second Moments of Polytopes	453	(5)
2.A Dirichlet's Integral	453	(1)
2.B Generalized Octahedron or Crosspolytope	454	(1)
2.C The n-Sphere	454	(1)
2.D n-Dimensional Simplices	454	(1)
2.E Regular Simplex	455	(1)
2.F Volume and Second Moment of a Polytope in Terms of its Faces	455	(1)
2.G Truncated Octahedron	456	(1)
2.H Second Moment of Regular Polytopes	456	(1)
2.I Regular Polygons	457	(1)
2.J Icosahedron and Dodecahedron	457	(1)
2.K The Exceptional 4-Dimensional Polytopes	457	(1)
3. Voronoi Cells and the Mean Squared Error of Lattice Quantizers	458	(20)
3.A The Voronoi Cell of a Root Lattice	458	(3)
3.B Voronoi Cell for A(n)	461	(3)
3.C Voronoi Cell for D(n) n is greater than or equal to 4	464	(1)
3.D Voronoi Cells for E(6), E(7), E(8)	464	(1)
3.E Voronoi Cell for D(*)(n)	465	(9)
3.F Voronoi Cell for A(*)(n)	474	(2)
3.G The Walls of the Voronoi Cell	476	(2)
Chapter 22 A Bound for the Covering Radius of the Leech Lattice	478	(2)
S.P. Norton
Chapter 23 The Covering Radius of the Leech Lattice	480	(28)
J.H. Conway
R.A. Parker
N.J.A. Sloane
1. Introduction	480	(2)
2. The Coxeter-Dynkin Diagram of a Hole	482	(4)
3. Holes Whose Diagram Contains an A(n) Subgraph	486	(11)
4. Holes Whose Diagram Contains a D(n) Subgraph	497	(7)
5. Holes Whose Diagram Contains an E(n) Subgraph	504	(4)
Chapter 24 Twenty-Three Constructions for the Leech Lattice	508	(7)
J.H. Conway
N.J.A. Sloane
1. The "Holy Constructions"	508	(4)
2. The Environs of a Deep Hole	512	(3)
Chapter 25 The Cellular Structure of the Leech Lattice	515	(9)
R.E. Borcherds
J.H. Conway
L. Queen
1. Introduction	515	(1)
2. Names for the Holes	515	(1)
3. The Volume Formula	516	(5)
4. The Enumeration of the Small Holes	521	(3)
Chapter 26 Lorentzian Forms for the Leech Lattice	524	(5)
J.H. Conway
N.J.A. Sloane
1. The Unimodular Lorentzian Lattices	524	(1)
2. Lorentzian Constructions for the Leech Lattice	525	(4)
Chapter 27 The Automorphism Group of the 26-Dimensional Even Unimodular Lorentzian Lattice	529	(5)
J.H. Conway
1. Introduction	529	(1)
2. The Main Theorem	530	(4)
Chapter 28 Leech Roots and Vinberg Groups	534	(22)
J.H. Conway
N.J.A. Sloane
1. The Leech Roots	534	(9)
2. Enumeration of the Leech Roots	543	(6)
3. The Lattices I(n.1) for n is less than equal to 19	549	(1)
4. Vinberg's Algorithm and the Initial Batches of Fundamental Roots	549	(3)
5. The Later Batches of Fundamental Roots	552	(4)
Chapter 29 The Monster Group and its 196884-Dimensional Space	556	(14)
J.H. Conway
1. Introduction	556	(2)
2. The Golay Code xxx and the Parker Loop XXX	558	(1)
3. The Mathieu Group M(24): the Standard Automorphisms of XXX	558	(1)
4. The Golay Cocode XXX(*) and the Diagonal Automorphisms	558	(1)
5. The Group N of Triple Maps	559	(1)
6. The Kernel K and the Homomorphism g - g	559	(1)
7. The Structures of Various Subgroups of N	559	(1)
8. The Leech Lattice A(24) and the Group Q	560	(1)
9. Short Elements	561	(1)
10. The Basic Representations of N	561	(1)
11. The Dictionary	562	(1)
12. The Algebra	563	(1)
13. The Definition of the Monster Group XXX, and its Finiteness	563	(1)
14. Identifying the Monster	564	(1)
Appendix 1. Computing in XXX	565	(1)
Appendix 2. A Construction for XXX	565	(1)
Appendix 3. Some Relations in Q	566	(2)
Appendix 4. Constructing Representations for N	568	(1)
Appendix 5. Building the Group G	569	(1)
Chapter 30 A Monster Lie Algebra?	570	(4)
R.E. Borcherds
J.H. Conway
L. Queen
N.J.A. Sloane
Bibliography	574	(68)
Supplementary Bibliography	642	(39)
Index	681