Sphere Packings and Error-Correcting Codes

Leech, John ; Sloane, N. J. A.

Canadian journal of mathematics, Tome 23 (1971) no. 4, pp. 718-745

Résumé

Error-correcting codes are used in several constructions for packings of equal spheres in n-dimensional Euclidean spaces En. These include a systematic derivation of many of the best sphere packings known, and construction of new packings in dimensions 9-15, 36, 40, 48, 60, and 2m for m ≧ 6. Most of the new packings are nonlattice packings. These new packings increase the previously greatest known numbers of spheres which one sphere may touch, and, except in dimensions 9, 12, 14, 15, they include denser packings than any previously known. The density Δ of the packings in En for n = 2m satisfies In this paper we make systematic use of error-correcting codes to obtain sphere packings in En, including several of the densest packings known and several new packings.

Détail

DOI : 10.4153/CJM-1971-081-3

Bibliographie

[1] 1. Assmus, E. F., Jr. and Mattson, H. F., Jr., New 5-designs, J. Combinatorial Theory 6 (1969), 122–151. Google Scholar

[2] 2. Assmus, E. F., Jr. and Mattson, H. F., Jr., Algebraic theory of codes. II, Applied Research Laboratory, Sylvania Electronic Systems, Waltham, Mass., Report AFCRL-69-0461, 15 October, 1969. Google Scholar

[3] 3. 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

[4] 4. Berlekamp, E. R., Algebraic Coding Theory (McGraw-Hill, New York, 1968). Google Scholar

[5] 5. Berlekamp, E. R., Coding theory and the Mathieu groups, Information and Control 18 (1971), 40–64. Google Scholar

[6] 6. Chen, C. L., Computer results on the minimum distance of some binary cyclic codes, IEEE Trans. Information Theory 16 (1970), 359–360. Google Scholar

[7] 7. Conway, J. H., A characterization of Leech's lattice, Invent, math. 7 (1969), 137–142. Google Scholar

[8] 8. Conway, J. H., A group of order 8,315,553,613,086,720,000, Bull. London Math. Soc. 1 (1969), 79–88. Google Scholar

[9] 9. Conway, J. H., (private communication). Google Scholar

[10] 10. Coxeter, H. S. M., Extreme forms, Can. J. Math. 8 (1951), 391–441. Google Scholar

[11] 11. Coxeter, H. S. M., An upper bound for the number of equal nonoverlapping spheres that can touch another of the same size, Proc. Symp. Pure Math, Vol VII (Providence, 1963), 53–71. Google Scholar

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

[13] 13. Golay, M. J. E., Notes on digital coding, Proc. I.R.E. 37 (1949), 637. Google Scholar

[14] 14. Golay, M. J. E., Binary coding, IRE Trans. Information Theory 4 (1954), 23–28. Google Scholar

[15] 15. Hanani, H., On quadruple systems, Can. J. Math. 12 (1960), 145–157. Google Scholar

[16] 16. Julin, D., Two improved block codes, IEEE Trans. Information Theory 11 (1965), 459. Google Scholar

[17] 17. Kasami, T. and Tokura, N., Some remarks on BCH bounds and minimum weights of binary primitive BCH codes, IEEE Trans. Information Theory 15 (1969), 408–413. Google Scholar

[18] 18. Leech, J., Some sphere packings in higher space, Can. J. Math. 16 (1964), 657–682. Google Scholar

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

[20] 20. Leech, J., Five-dimensional nonlattice sphere packings, Can. Math. Bull. 10 (1967), 387–393. Google Scholar

[21] 21. Leech, J., Six and seven dimensional nonlattice sphere packings, Can. Math. Bull. 12 (1969), 151–155. Google Scholar

[22] 22. Leech, J. and Sloane, N. J. A., New sphere packings in dimensions 9-15, Bull. Amer. Math. Soc. 76 (1970), 1006–1010. Google Scholar

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

[24] 24. Mann, H. B., On the number of information symbols in Bose-Chaudhuri codes, Information and Control 5 (1962), 153–162. Google Scholar

[25] 25. Peterson, W. W., Err or-correcting Codes (The M.I.T. Press, Cambridge, Mass., 1961). Google Scholar

[26] 26. Pierce, J. N. (private communication). Google Scholar

[27] 27. Pless, V., On a new family of symmetry codes and related new five-designs, Bull. Amer. Math. Soc. 75 (1969), 1339–1342. Google Scholar

[28] 28. Pless, V., Symmetry codes over GF﹛3) and new five-designs (to appear in J. Combinatorial Theory). Google Scholar

[29] 29. Pless, V., (private communication). Google Scholar

[30] 30. Rogers, C. A., The packing of equal spheres, Proc. London Math. Soc. 8 (1958), 609–620. Google Scholar

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

[32] 32. Sloane, N. J. A. and Seidel, J. J., A new family of nonlinear codes obtained from conference matrices, Ann. New York Acad. Sci. 175 (1970), 363–365. Google Scholar

[33] 33. Sloane, N. J. A. and Whitehead, D. S., A new family of single-error correcting codes, IEEE Trans. Information Theory 16 (1970), 717–719. Google Scholar

[34] 34. Thompson, J. G. (private communication). Google Scholar

[35] 35. Todd, J. A., A representation of the Mathieu group Mu as a collineation group, Ann. Mat. Pura Appl. 71 (1966), 199–238. Google Scholar

[36] 36. Watson, G. L., The number of minimum points of a positive quadratic form (to appear). Google Scholar

[37] 37. Witt, E., Über Steinersche Système, Abh. Math. Sem. Hansischen Univ. 12 (1938), 256–264 Google Scholar