2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I don't know about a specific dimension, but for large $n$, packing spheres into a sphere is approximately equal to designing a code for communicating over a Gaussian channel, and information theory has a lot to say about that. Maybe some coding theory lit would be relevant? $\endgroup$ – stochasticboy321 May 18 '16 at 17:36
  • 1
    $\begingroup$ See Wikipedia and Sphere Packings, Lattices and Groups. $\endgroup$ – joriki May 18 '16 at 17:38
  • $\begingroup$ I had already seen the wikipedia page, but all it says is "In dimensions higher than three, the densest regular packings of hyperspheres are known up to 8 dimensions". I was wondering what these regular packings were, and things like its density. $\endgroup$ – Cheese May 18 '16 at 18:59
4
$\begingroup$

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)
$\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.