New upper bounds on sphere packings. I. (English) Zbl 1041.52011

Cohn, Henry; Elkies, Noam

Ann. Math. (2) 157, No. 2, 689-714 (2003).

The authors develop an analogue for sphere packing (the densest packing of Euclidean spheres into Euclidean space) of the linear programming bounds for error-correcting codes, and use it to prove upper bounds for the density of sphere packings, which are the best bounds known at least for dimensions 4 through 36. The methods used here are not limited to studying Euclidean sphere packings, but can be applied to translations of arbitatry symmetrical convex bodies \(C\). The main result: Suppose \(f:{\mathbb R}^n \to {\mathbb R}\) is an admissible function, \(f\neq 0\), and \(f(x) \geq 0\) for \(x\notin C\) and \(\widehat f(t)\geq 0\) for all \(t\). Then all packings with translates of \(C\) have density bounded above by \((\text{vol} (C) f(0))/(2^n \widehat f(0))\). The authors conjecture that their approach can be used to solve the sphere packing problem in dimensions 8 and 24.

Reviewer: Alexey Alimov (Moskva)

MSC:

52C17	Packing and covering in \(n\) dimensions (aspects of discrete geometry)
90C05	Linear programming
94B70	Error probability in coding theory

Keywords:

sphere packing; error-correcting code; linear programming bound