14
$\begingroup$

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(d)=\lfloor 2^d\delta(d)\rfloor$ for $d=1,2,3,4,8,24$.

$\endgroup$
8
  • 3
    $\begingroup$ Just a remark: MathOverflow tends to work well when you ask questions for which you can reasonably expect someone to know the answer, or know how to figure it out. Since your question seems to be "too hard" in the case of large $d$, I'm wondering if you would like to ask for partial results to date, instead? $\endgroup$
    – S. Carnahan
    Commented Feb 19, 2013 at 15:33
  • $\begingroup$ This is related to this question: mathoverflow.net/questions/98007/… $\endgroup$
    – Igor Rivin
    Commented Feb 19, 2013 at 16:42
  • 2
    $\begingroup$ Is $\lfloor2^9\delta(9)\rfloor$ really known? $$ $$ For $d=8$, the $E_8$ lattice can be constructed from the $[8,4,4]$ (extended Hamming) binary code, so $N(8)=16$ (the Rogers bound suffices to show one cannot accommodate a 17th sphere). Likewise for $d=24$ the Leech lattice has an orthogonal frame of minimal vectors so $N(24) = 2^{24}$ (using the Cohn-Kumar computation to show that this is optimal). $\endgroup$ Commented Feb 19, 2013 at 20:38
  • 2
    $\begingroup$ Is it really so counter-intuitive that the volume of the ball tends to zero? To maintain the volume when the dimension goes go up by one (as much as we can imagine) would require a cylinder which gets whittled down to make a ball. $\endgroup$ Commented Feb 20, 2013 at 3:00
  • 1
    $\begingroup$ @Aaron Meyerowitz: If it would converge/decrease to something positive, I'd find this somehow more intuitive. $\endgroup$
    – user9072
    Commented Feb 20, 2013 at 11:15

0

You must log in to answer this question.

Browse other questions tagged .