Packing of n-balls

Question

Much has been written about the packing of circles and spheres, but I was wondering what the most efficient way there was to pack n-balls in an n-dimensional box.

I saw that the most dense packing of circles is approximately .91 and the packing of spheres is about .74, but how about 4-balls? What if the balls are of different sizes?

Also, what would that packing look like?

Answer 1

As of March 2016, the optimal density for lattice packing of unit $n$-spheres are known for $n \le 8$ and $n = 24$. All the associated lattices are laminated lattices.

Laminated lattices $\Lambda_n$ can be defined/constructed recursively.

• For $n = 1$, $\Lambda_1$ is "the" lattice of even integers.

• For $n > 1$, $\Lambda_n$ is "a" $n$-dim lattice satisfies

  1. the minimal spacing among lattice points is $2$.
  2. contains "a" $\Lambda_{n-1}$ as sub-lattice.
  3. subject to 1) and 2), the volume of its fundamental cell is minimal.

Geometrically, one can think of $\Lambda_n$ as stacking copies of a lower dimensional laminated lattice $\Lambda_{n-1}$ as tightly as possible without reducing the minimum lattice spacing.

With this definition, there is no guarantee $\Lambda_n$ is unique for a given $n$. Indeed, it isn't unique in general. However, $\Lambda_n$ is unique for $n \le 10$ and $14 \le n \le 24$.

Let $V_n$ be the volume of unit $n$-sphere. For any $n$-dim lattice $\Lambda$,

• the determinant of $\Lambda$, $\det\Lambda$, is the square of the volume of its fundamental cell.
• the packing density of $\Lambda$, $\Delta$, is the ratio $\frac{V_n}{\sqrt{\det\Lambda}}$
• the center density $\delta$ is the ratio $\frac{\Delta}{V_n} = \frac{1}{\sqrt{\det\Lambda}}$.
• the kissing number $k$ is the number of nearest neighbors.

The expression of $V_n$ is complicated, $$V_n = \frac{\pi^{n/2}}{\Gamma(\frac{n}{2}+1)} = \begin{cases} \frac{\pi^k}{k!}, & n = 2k\\ \frac{2(2\pi)^k}{(2k+1)!!} = \frac{2k!(4\pi)^k}{(2k+1)!}, & n = 2k+1 \end{cases} $$ it is simpler to describe a packing using the center density $\delta$. Following table is a summary for known optimal lattice packing. For those $n$ with a $*$, the packing is actually optimal among all lattice and non-lattice packing.

$$\begin{array}{l:rrr:c} \hline n &\hfill \Delta\hfill&\hfill\delta\hfill & k & \text{ Lattice }\\ \hline 1* & 1 & \frac12 = 0.50000 & 2 & \Lambda_1 \simeq A_1 \simeq \mathbb{Z}\\ 2* & 0.90690 & \frac{1}{2\sqrt{3}} \approx 0.28868 & 6 & \Lambda_2 \simeq A_2\\ 3* & 0.74048 & \frac{1}{4\sqrt{2}} \approx 0.17678 & 12 & \Lambda_3 \simeq A_3 \simeq D_3\\ 4 & 0.61685 & \frac18 = 0.12500 & 24 & \Lambda_4 \simeq D_4\\ 5 & 0.46526 & \frac{1}{8\sqrt{2}} \approx 0.08839 & 40 & \Lambda_5 \simeq D_5\\ 6 & 0.37295 & \frac{1}{8\sqrt{3}} \approx 0.07217 & 72 & \Lambda_6 \simeq E_6\\ 7 & 0.29530 & \frac{1}{16} = 0.06250 & 126 & \Lambda_7 \simeq E_7\\ 8*& 0.25367 & \frac{1}{16} = 0.06250 & 240 & \Lambda_8 \simeq E_8 = D_8^{+}\\ 24& 0.001930 & \hfill 1 \hfill & 196560 & \Lambda_{24} \\ \hline \end{array}$$

In above table, the rightmost column is a list of lattices equivalent to $\Lambda_n$.

• The lattice $A_n$. For $n \ge 1$, $$A_n = \{ (x_0,x_1,\ldots,x_n) \in \mathbb{Z}^{n+1} : x_0 + \ldots + x_n = 0 \}$$ i.e. a sub-lattice of the $(n+1)$-dim cubic lattice $\mathbb{Z}^n$ on the hyperplane $\sum_{k=0}^n x_k = 0$.

  $A_2$ is the familiar hexagonal lattice (for mathematician, triangular lattice for physicists).

  $A_3$ is equivalent to the face centered cubic lattice (in chemistry)

• The lattice $D_n$ and $D_n^{+}$. For $n \ge 3$, $$D_n = \{ (x_1,\ldots,x_n) \in \mathbb{Z}^n : x_1 + \ldots + x_n \text{ even } \}$$ i.e. sublattice of the cubic lattice whose coordinates sum to an even number.

  Given any lattice $\Lambda$, the covering radius of $\Lambda$ is the smallest radius of spheres centered at $\Lambda$ that cover all $\mathbb{R}^n$. $$\text{covering radius} = \min\left\{ r : \mathbb{R}^n = \bigcup\limits_{p\in\Lambda} B(p,r) \right\}$$ The covering radius of $D_n$ increases with $n$. When $n = 8$, it is equal to the minimal distances among lattice points. This means for $n \ge 8$, we can slide another copy of $D_n$ between the points of $D_n$, doubling the density without reducing the lattice spacing. This lattice is called $D_n^{+}$.

• The lattice $E_6$, $E_7$ and $E_8 = D_8^{+}$.

  The $E_8$ lattice is equivalent to $D_8^{+}$ mentioned above. It can be constructed by taking union of the cubic lattice $\mathbb{Z}^8$ with a copy of it shifted along the diagonal and then collected those points whose coordinates sum to an even number: $$E_8 = \left\{ (x_1, \ldots, x_8) : \text{ all } x_i \in \mathbb{Z} \text{ or all } x_i \in \mathbb{Z}+\frac12;\;\; \sum_{i=1}^8 x_i \equiv 0 \pmod 2 \right\}$$

  Once we have $E_8$, pick any minimal vector $\nu$ from it, the vectors in $E_8$ perpendicular to $\nu$ will be equivalent to $E_7$. i.e. $$E_7 = \left\{ x \in E_8 : x \cdot \nu = 0\right\}$$

  If we pick a $A_2$ sub-lattice $V$ of $E_8$ instead, the vectors in $E_8$ perpendicular to $V$ will be equivalent to $E_6$. i.e. $$E_6 = \left\{ x \in E_8 : x \cdot \nu = 0, \forall \nu \in V \right\}$$

• The lattice $\Lambda_{24}$.

  $\Lambda_{24}$ is the famous Leech lattice discovered by John Leech (1967). It has a lot of interesting properties. please refer to wiki for what it is.

I don't really know this stuff. Most of the material above is extracted from the book Sphere Packings, Lattices and Groups by Conway and Sloan. Look at

• $\S1.4$ - $\S1.5$ for a summary of the known densities.
• Chapter 4 for the lattices mentioned above.
• Chapter 5 for more details about laminated lattices.

Please note that this book is not most uptodate. The optimality of $\Lambda_8$ for all packing and $\Lambda_{24}$ for all lattice packing is only proved two months ago. Look at following two papers and the references there for most uptodate information.

• Maryna Viazovska, The sphere packing problem in dimension 8 (arXiv:1603.04246)
• Henry Cohn, el al. The sphere packing problem in dimension 24 (arXiv:1603.06518)