7
$\begingroup$

Simply put, my question is this: what is the smallest dimension, if any, where we can know for sure that a convex body exists whose translative packing constant is strictly larger than its lattice packing constant?

Some relevant facts I know:

  • In two dimensions, the translative packing constant is always equal to the lattice packing constant for convex bodies. For non-convex bodies, already in two dimensions there are counterexamples. Bezdek and Kuperberg give a good exposition of this.

  • In ten dimensions, the best packing of spheres seems to be non-lattice. In lower dimensions, the best lattice packing seems to be also the best packing. The best known lattice packing in dimensions above 8 is not actually known to be best (except in 24 dimensions). Therefore, even for spheres, there is no dimension where lattices are proved to be suboptimal. See this MO question for more on that.

  • Convex bodies that tile by translation can also tile by lattice translations. So the example cannot be a tiling body. This is famous result due to Venkov, Alexandrov, and McMullen, and Gruber's book on Convex and Discrete Geometry gives a nice treatment.

  • Except for tiling bodies, which are ruled out be the previous point, very few bodies have known translative packing constants. However, all we need to have an example is a lower bound for the translative packing constant and an upper bound for the lattice packing constant. There are known methods to compute the lattice packing constant for polytopes, and in 3D one such method has been implemented by Betke and Henk.

So, it seems that in dimension 10, there are convex bodies, namely spheres, that pack better by translation than by lattice translation. However, this is not rigorously known. If true, this example can probably be extended to higher dimensions by forming cylinders. However, it seems to me that if we allow nonspherical bodies, the dimension where translative packing starts to beat out lattice packing should be siginificantly lower. Is there an example? In dimensions low enough (e.g. 3D), candidates can be checked computationally and rigorously established if they check out.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ I don't know of an example, and I wouldn't be surprised if nobody knows one (but I'll be very pleased if I'm wrong about this). $\endgroup$ – Henry Cohn Oct 3 '14 at 18:43
  • $\begingroup$ Thanks @HenryCohn. This is indeed as I feared, but I wanted to check that I wasn't missing something known. The fact that we have a good candidate in 10D and we have a good method for checking candidates in 3D makes me feel that it should not be impossibly hard to produce an example in some intermediate dimension. $\endgroup$ – Yoav Kallus Oct 3 '14 at 19:02
  • $\begingroup$ Yeah, I think it's very plausible that one could construct an example in a much lower dimension, and conceivable that one could prove it rigorously. I haven't thought much about how hard the difficulty of proving that a lattice packing is optimal varies with dimension (for convex bodies). The Betke-Henk paper deals beautifully with polyhedra in three dimensions, but I have no idea how hard four, five, or six dimensions would be. $\endgroup$ – Henry Cohn Oct 3 '14 at 19:58
4
$\begingroup$

This is not an answer, but rather a documentation of a failed attempt to obtain an answer.

One problem for which we know there is a significant difference between unrestricted sets of translations and lattices is in tilings with equal-size cubes. Every lattice tiling with n-cubes has a pair of cubes sharing an entire (n-1)-dimensional face (Hajós). On the other hand, in dimensions $n\ge8$, there are translational tilings with n-cubes in which no two cubes share an entire (n-1)-dimensional face ($n\ge10$ due to Lagarias and Shor, improve to 8 by Mackey, n=7 case open, see Keller's conjecture). Moreover, a stronger property holds in these tilings: the center of each (n-1)-face does not lie in the relative interior of any other (n-1)-face. I call such a tiling a center-to-boundary tiling.

Now consider a slightly stellated n-cube: the convex hull of a unit n-cube and a point for each face lying a height $\epsilon$ above the center of the face. It is easy to perturb a center-to-boundary tiling of n-cubes to a packing with mean volume $(1+\epsilon)^n$. I wanted to show that since lattice tilings have shared faces along at least one direction, and a lattice packing of slightly stellated cubes will be near a lattice tiling, that the mean volume (i.e. lattice determinant) of the packing will have to be $\ge 1+(n+1)\epsilon + o(\epsilon)$, but this turns out to be false. Here is an example of a family of lattices that pack $\epsilon$-stellated 5-cubes, but have determinant $1+(47/8)\epsilon+O(\epsilon^2)$: $L=A\mathbb{Z}^5$, where

$$A=\left(\begin{array}{ccccc} 1+2\epsilon&-\tfrac12&0&0&0\\ 0&1+\epsilon&-\tfrac12&\tfrac12&0\\ 0&0&1+\epsilon&0&-\tfrac14\\ 0&0&0&1+\epsilon&\tfrac12\\ 0&0&-\tfrac12\epsilon&0&1+\epsilon \end{array}\right)\text.$$

Now, still $47/8>5$, but this example does not bode well for the program. For large $n$, I believe similar constructions are possible that achieve determinants $\le 1+n\epsilon+o(\epsilon)$. It might still be that this is impossible for $n=8$, but if so, it could be delicate to show.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.