New Lattice Packings of Spheres

Barnes, E. S. ; Sloane, N. J. A.

Canadian journal of mathematics, Tome 35 (1983) no. 1, pp. 117-130

Résumé

1. Introduction. In this paper we give several general constructions for lattice packings of spheres in real n-dimensional space R n and complex space Cn . These lead to denser lattice packings than any previously known in R 36, R 64, R 80, ..., R 128, .... A sequence of lattices is constructed in R n for n = 24m ≦ 98328 (where m is an integer) for which the density Δ satisfies log2 Δ ≈ – (1.25 ...)n, and another sequence in R n for n = 2m (m any integer) with The latter appear to be the densest lattices known in very high dimensional space. (See, however, the Remark at the end of this paper.) In dimensions around 216 the best lattices found are about 2131000 times as dense as any previously known.Minkowski proved in 1905 (see [20] and Eq. (23) below) that lattices exist with log2 Δ > –n as n → ∞, but no infinite family of lattices with this density has yet been constructed.

Détail

DOI : 10.4153/CJM-1983-008-1

Bibliographie

[1] 1. Barnes, E. S., The construction of perfect and extreme forms, Acta Arithmetica 5 (1959), 57–79 and 205-222. Google Scholar

[2] 2. Barnes, E. S. and Wall, G. E., Some extreme forms defined in terms of Abelian groups, J. Australian Math. Soc. 1 (1959), 47–63. Google Scholar

[3] 3. Bos, A., Sphere packings in high-dimensional space, preprint. Google Scholar

[4] 4. Bos, A., Upper bounds for sphere-packings in Euclidean space, IEEE Trans. Information Theory, to appear. Google Scholar

[5] 5. Bourbaki, N., Groupes et algèbres de Lie, Chapitres IV, V, VI (Hermann, Paris, 1968). Google Scholar

[6] 6. Conway, J. H., A characterisation of Leech's lattice, Inventiones Math. 7 (1969), 137–142. Google Scholar

[7] 7. Conway, J. H., Parker, R. A. and Sloane, N. J. A., The covering radius of the Leech lattice, Proc. Royal Soc. London, A380 (1982), 261–290. Google Scholar

[8] 8. Conway, J. H. and Sloane, N. J. A., Voronoi regions of lattices, second moments of polytopes, and quantization, IEEE Trans. Information Theory, IT-28 (1982), 211–226. Google Scholar

[9] 9. Conway, J. H. and Sloane, N. J. A., Twenty-three constructions for the Leech lattice, Proc. Royal Soc. London (A)381 (1982), 275–283. Google Scholar

[10] 10. Conway, J. H. and Sloane, N. J. A., Laminated lattices, Annals of Math. 116 (1982), in press. Google Scholar

[11] 11. Coxeter, H. S. M. and Todd, J. A., An extreme duodenary form, Can. J. Math. 5 (1953), 384–392. Google Scholar

[12] 12. Kabatiansky, G. A. and Levenshtein, V. I., Bounds for packings on a sphere and in space (in Russian), Problemy Peredachi Informatsii 14, No. 1 (1978), 3–25. English translation in Problems of Information Transmission 14, No. 1 (1978), 1-17. Google Scholar

[13] 13. Leech, J., Notes on sphere packings, Can. J. Math. 19 (1967), 251–267. Google Scholar

[14] 14. Leech, J. and Sloane, N. J. A., New sphere packings in more than 32 dimensions, Proc. Second Chapel Hill Conference on Combinatorial Mathematics and its Applications, Univ. of North Carolina at Chapel Hill (1970), 345–355. Google Scholar

[15] 15. Leech, J. and Sloane, N. J. A. Sphere packings and error-correcting codes, Can. J. Math. 23 (1971), 718–745. Google Scholar

[16] 16. Levenshtein, V. I., On bounds for packings in n-dimensional Euclidean space (in Russian), Dokl. Akad. Nauk SSSR 245, No. 6 (1979), 1299–1303. English translation in Soviet Math. Doklady 20, No. 1 (1979), 417-421. Google Scholar

[17] 17. MacWilliams, F. J. and Sloane, N. J. A., The theory of error-correcting codes (North- Holland, Amsterdam, 1977). Google Scholar

[18] 18. Peterson, W. W. and Weldon, E. J., Jr., Error-correcting codes (MIT Press, Cambridge, MA, 2nd edition, 1972). Google Scholar

[19] 19. Rao, V. V. and Reddy, S. M., A (48,31,8) linear code, IEEE Trans. Information Theory, IT-19 (1973), 709–711. Google Scholar

[20] 20. Rogers, C. A., Packing and covering (Cambridge University Press, Cambridge, 1964). Google Scholar

[21] 21. Sloane, N. J. A., Sphere packings constructed from BCH and Justesen codes, Mathematika 19 (1972), 183–190. Google Scholar

[22] 22. Sloane, N. J. A., Binary codes, lattices and sphere packings, in Combinatorial Surveys (Proc. 6th British Combinatorial Conference), (Academic Press, London, 1977), 117–164. Google Scholar

[23] 23. Sloane, N. J. A., Codes overGF﹛4) and complex lattices, J. Algebra 52 (1978), 168–181. Google Scholar

[24] 24. Sloane, N. J. A., Self-dual codes and lattices, in Relations between combinatorics and other parts of mathematics, Proc. Sympos. Pure Math. 34 (Amer. Math. Soc, Providence, RI, 1979), 273–308. Google Scholar

[25] 25. Sloane, N. J. A., Recent bounds for codes, sphere packings and related problems obtained by linear programming and other methods, in Papers in analysis, algebra and statistics (Contemporary Math. 9), (Amer. Math. Soc., Providence, R.I. 1982), 153-185. Google Scholar