Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
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? –  S. Carnahan Feb 19 '13 at 15:33
    
This is related to this question: mathoverflow.net/questions/98007/… –  Igor Rivin Feb 19 '13 at 16:42
2  
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). –  Noam D. Elkies Feb 19 '13 at 20:38
2  
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. –  Aaron Meyerowitz Feb 20 '13 at 3:00
1  
@Aaron Meyerowitz: If it would converge/decrease to something positive, I'd find this somehow more intuitive. –  quid Feb 20 '13 at 11:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.