4
$\begingroup$

I know how to find the closest packing of equal spheres in $\Bbb{R}^3$. I'd like to know how to find the closest packing of equal balls in $\Bbb{R}^4$ with the standard Euclidian metric. I suspect it's going to be something like the $\Bbb{R}^3$ FCC or HCP packing layered in hyperplane 'slices', but I'm having a hard time formulating an equation that I can use to compute the central points for the balls.

$\endgroup$
1
  • 2
    $\begingroup$ The densest 4-d lattice packing is achieved by the lattice $D_4$ which can be constructed by taking the integer lattice and include only those points whose coordinates sum to an even number: $$D_4 = \big\{ (x,y,z,w) \in \mathbb{Z}^4 : x+y+z+w \equiv 0 \pmod 2 \big\}$$ Its optimality is established by Korkine and Zolotarev 1872?. It is not known whether this is the densest 4-d packing. $\endgroup$ Commented Jun 5, 2015 at 14:28

3 Answers 3

4
$\begingroup$

According to MathWorld, it is not known what the densest hypersphere packing in more than 3 dimensions is. The densest lattice packing is known up to dimension 8 (in four dimension the 4D analog of face-centered cubic is the densest), but it has not been proved that there is no denser non-periodic packing.

$\endgroup$
1
  • $\begingroup$ I think the lattice packing is what I'm looking for (was not familiar with that term.) My goal is to create a set of points that I can use to efficiently 'sample' over a known volume. My first approach was to use a simple hypercube spacing, but I'm thinking I can reduce the number of points I need to use (and reduce the number of neighbors, which benefits some other calculations) if I pack more efficiently. $\endgroup$
    – Dan Bryant
    Commented Jun 5, 2015 at 14:14
1
$\begingroup$

To get the 4D analog of HCP, you can think about how HCP is built up through the dimensions. In 1D it is just a series of line segments placed end to end along the $x$ axis. To make the 2D version, change the segments into 2-balls (disks). Your line becomes one line of the 2D packing and you put another line offset in the new $(y)$ direction. The new 2-balls make an equilateral triangle with the old ones and you repeat the pattern. To go to 3D, change the 2-balls into 3-balls and use that as one layer. Make a new copy that you put displaced as little in $z$ as possible. That makes each new ball make a regular tetrahedron with three of the old ones. The new ball is located in $x,y$ over the centroid of the 2D triangle. To go to 4D, you do the same. Make your existing 3-balls into 4-balls and that is one layer. Find the $(x,y,z)$ coordinate of the centroid of a tetrahedron. One of the balls goes at $(x,y,z,w)$ so that it makes a regular 4-simplex. That will give you the layer spacing in the fourth dimension. So in 3D the centers are $(0,0,0), (2,0,0), (1,\sqrt 3,0),(1,\frac 13\sqrt 3,\frac 13\sqrt 6)$ and the new point becomes $(1,\frac 13\sqrt 3,\frac 1{12}\sqrt 6,\frac 14\sqrt{10})$ You can add that vector to all the points of the 3D lattice to get the next layer in 4D and keep on to build up the whole 4D lattice. You can then repeat the construction to get 5D and so on.

$\endgroup$
1
$\begingroup$

As your profile says you are in the business, recommend three books I have, the first can probably be read from cover to cover:

THOMPSON

EBELING

CONWAY + SLOANE

W. Ebeling was nice to me; I should write to him, tell him the article that included material from his book appeared. I do know that he was not able to include my, well, application of his notes, into his third edition, there was not enough time. Conway and Sloane is usually referred to as SPLAG. It is up to a third edition, at least.

Mild detail: Ebeling's first chapter has a nice bit on going from codes to lattices. Also more than I had realized on root lattices, which are your current concern. The big discussion of root lattices is HUMPHREYS. In the first edition of SPLAG Table 1.2 on page 15 seems to be the densest packings. The introduction is a bit roundabout, I guess it is dimensions 1-8 and then 24 where the best lattice packing is known and proved best...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .