What is the max number of points I can put in an n-dimensional ball with radius 1, so that the distance between any two points is $\ge 1$?

Question

I want calculate max number of points that I can put in an n-dimensional ball with radius 1, so that the distance between any two points is $\ge 1$. I want get the exact formula or lower bound for number of points that depends on dimensionality. I write a program that try placed maximum points to the ball with radius 1 and I get so far: \begin{array} {|r|r|}\hline \text{dim} & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline \text{num points} & 3 & 7 & \ge13 & \ge23 & \ge 37 & \ge 59 & \ge 87\\ \hline \end{array}

Answer 1

If I understand your problem correctly, this is essentially the kissing number problem, with an extra point at the center of the ball. (In your problem, you don't have to put a point at the center of the ball, but if you put a point in the ball's interior that is located away from the center, then you've eliminated a large region of the ball's surface that isn't counterbalanced by opening a bunch of space in its interior. I strongly suspect that makes that tactic sub-optimal, but it would be worth verifying.)

If you put a point at the ball's center, then the remaining points will be on the ball's surface, and they must be separated by distance $1$, which are exactly the tangent points of balls in the kissing number problem. Therefore, the answer to your question will be one plus the answer to the kissing number problem: that is,

$$ n_1 = \kappa(1)+1 = 2+1 = 3 $$ $$ n_2 = \kappa(2)+1 = 6+1 = 7 $$ $$ n_3 = \kappa(3)+1 = 12+1 = 13 $$ $$ n_4 = \kappa(4)+1 = 24+1 = 25 $$

Values are also known for dimensions $8$ and $24$, due to the symmetries of the $E_8$ and Leech lattices:

$$ n_8 = \kappa(8)+1 = 240+1 = 241 $$ $$ n_{24} = \kappa(24)+1 = 196\,560+1 = 196\,561 $$

Even where values are not precisely known, we may draw from the lower and upper bounds established for the kissing number problem—for example:

$$ n_5 = \kappa(5)+1 \in \{41, 42, \ldots, 45\} $$ $$ n_6 = \kappa(6)+1 \in \{73, 74, \ldots, 79\} $$ $$ n_7 = \kappa(7)+1 \in \{127, 128, \ldots, 135\} $$

and so forth. Incidentally, each of these is consistent with your lower bounds.

This is a problem with deep connections to coding theory, and indeed part of the proof of the four-dimensional case draws upon a clever modification by Oleg Musin to a coding theory approach sometimes called the Delsarte method. See Pfender and Ziegler, "Kissing Numbers, Sphere Packings, and Some Unexpected Proofs," in Notices of the AMS, Vol. $51$, pp. $873$–$883$. If I get the motivation at some point, I may come back and sketch out the Delsarte method for two dimensions. This case is of course easy to establish ad hoc, but showing the Delsarte method for two dimensions makes the approach easier to understand.

Casselman, "The Difficulties of Kissing in Three Dimensions," also gives some interesting history behind this problem, including the somewhat surprising fact that the story of Newton and Gregory's discussion of the three-dimensional case is often distorted! I had always heard (initially from Martin Gardner's retelling in his Mathematical Games column) that Newton thought $\kappa(3) = 12$ while Gregory thought $\kappa(3) = 13$, but that is an oversimplification. See the article for more details.