Dense sphere packings which are not lattice packings - MathOverflow

Dense sphere packings which are not lattice packings

2011-04-07T10:18:48Z

This question is about dense sphere packings in euclidean space $\mathbb R^n$. By a sphere packing I understand any arrangement of mutually disjoint solid open spheres in $\mathbb R^n$, all of the same radius. The density of a packing is $$\mathrm{lim}_{R \to \infty}\frac{\mathrm{vol }(B(0,R) \cap \mathrm{spheres})}{\mathrm{vol } B(0,R)} $$ if it exists. Here, $B(0,R)$ is the open ball of radius $R$ centered at $0 \in \mathbb R^n$.

In low dimensions, the highest possible densities of sphere packings are known to be attained by lattice packings, that is, packings such that the centers of the spheres form a discrete subgroup of $\mathbb R^n$ of rank $n$. One could speculate that this is so in all dimensions, but I doubt it very much...

Is it true that for some (possibly very lagre) integer $n$, there is a sphere packing in $\mathbb R^n$ which has a higher density than any lattice packing?

Edit -- Note: I didn't mean to ask about an explicit $n$, let alone about explicit packings. So i'm completely satisfied if somebody tells me that there is asymptotically such and such upper bound for lattice packing densities and this and that lower bound for general densest sphere packing densities.

Answer by Gerry Myerson for Dense sphere packings which are not lattice packings

2011-04-07T12:16:37Z

Wikipedia (http://en.wikipedia.org/wiki/Sphere_packing), that fount of all knowledge, says "in certain dimensions (e.g. 10) the densest known irregular packing is denser than the densest known regular packing." But as Roland implies in his comment, "densest known" isn't necessarily densest, certainly not by the time you get to dimension 10.

Answer by Henry Cohn for Dense sphere packings which are not lattice packings

2011-04-07T12:22:13Z

In ten dimensions the best packing known is the Best packing, which is not a lattice packing. Marc Best found a nonlinear $40$-element binary code of block length $10$ and minimal Hamming distance $4$, and one can turn it into a sphere packing in $\mathbb{R}^{10}$ by centering spheres at all the points in $\mathbb{Z}^{10}$ that reduce to it modulo $2$. This packing seems to be better than any lattice packing, but no proof is known. The best lattice packings up through $\mathbb{R}^8$ were determined by the 1930's, but even $\mathbb{R}^9$ isn't known, let alone $\mathbb{R}^{10}$, and there aren't even good enough bounds to prove that nothing is as good as the Best packing.

For some reason, good non-lattice packings are more likely to be known in even dimensions than odd dimensions, at least for dimensions a little less than $24$. For example, (hypothetical) answers are known in $\mathbb{R}^{18}$, $\mathbb{R}^{20}$, and $\mathbb{R}^{22}$, but not in between. I imagine this is an artifact of coding-theory-based constructions.

Probably lattices are suboptimal in all sufficiently high dimensions, but nobody really understands how to think about this problem asymptotically. The best existence results in high dimensions all produce lattices, but that's presumably just because lattices are more tractable than non-lattice packings.