Skip to main content
10 of 11
added 55 characters in body; added 2 characters in body
Hao Chen
  • 2.6k
  • 19
  • 29

How many unit balls can be put into a unit cube?

Here a unit ball is a ball of diameter 1, and a unit cube is a cube of edge length 1.

A famous counterintuitive fact is that, as the dimension increases, the volume of the unit ball tends to zero while that of the unit cube remains 1. Imagine that there is a unit ball centered at each corner of the unit cube, the space in the middle is enough for another unit ball only when the dimension is 4 or higher. In even higher dimensions, it will be possible to introduce more unit balls.

The question is:

In dimension $d$, what is the maximum number $N(d)$ of unit $d$-balls with disjoint interiors, that is possible to be centered in a $d$-dimensional hypercube (with periodic boundary condition).

It is equivalent to ask:

What is the maximum size $N(d)$ for a set of points $S\subset\mathbb{R}^d/\mathbb{Z}^d$ such that for any two points $[x],[y]\in S$, the distance between $[x]$ and $[y]$ is at least 1.

Here, the distance between $[x]$ and $[y]$ is defined as the minimum distance between $\mathbb{Z}^d+\{x\}$ and $\mathbb{Z}^d+\{y\}$.

For lower dimensions, we know that $N(d)=1$ for $d<4$, $N(d)=2$ for $d=4$. An obvious upperbound is $\lfloor 1/V_d\rfloor$ where $V_d$ is the volume of the $d$-dimensional unit ball. Another upperbound is $\lfloor 2^d\delta(d)\rfloor$ where $\delta(d)$ is the center density of a sphere packing in dimension $d$ (the sphere packing is defined by spheres of unit radius).

Actually, it's a problem very similar to the very hard densest packing problem. I don't expect any complete answer. A more specifique question is:

How different is $N(d)$ from $\lfloor 2^d\delta(d)\rfloor$?

For reference, for $d=1,2,...,9$, the value of $\lfloor 2^d\delta(d)\rfloor$ are respectively $1,1,1,2,2,4,8,16,22$ (using the best know results in Conway and Sloane's book). Also, as @Noam pointed out, we know that $N(24)=2^{24}$.

Hao Chen
  • 2.6k
  • 19
  • 29