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?
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_n$ is "a" $n$-dim lattice satisfies
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 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
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.