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

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.


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