Kissing number problem
|
|
In geometry, the kissing number problem is to find the maximum number of spheres of radius 1 that can simultaneously touch the unit sphere in n-dimensional Euclidean space (or, with the restriction for their centres to be in a particular lattice).
In one dimension, the answer is obviously 2:
It is easy to see (and to prove) that in two dimensions the answer is 6.
In three dimensions the answer is not so clear. It is easy to arrange 12 spheres so that each touches a central sphere, but there is a lot of space left over, and it is not obvious that there is no way to pack in a 13th sphere. (In fact, there is so much extra space that any two of the 12 outer spheres can exchange places without any of the outer spheres losing contact with the center one.) This was the subject of a famous disagreement between mathematicians Isaac Newton and David Gregory. Newton thought that the limit was 12, and Gregory that a 13th could fit. The question was not resolved until 1874; Newton was correct.
The kissing number in n dimensions is unknown for n>3, except for n=8 (240), and n=24 (196,560). For n=4, it has been known for some time that the answer is either 24 or 25. It is easy to produce a packing of 24 spheres around a central sphere, but as in the three-dimensional case, there is a lot of space left over---even more, in fact---so the situation is even less clear. In 24 dimensions, the kissing packing places the spheres at the points of the Leech lattice and there is no space at all left over.
Rough volume estimates show that kissing number in n dimensions grows exponetially. The base of exponential growth is not known.
Some known bounds
In the following table, * denotes dimensions for which the kissing number is known.
| Dimension | Lower bound | Upper bound |
|---|---|---|
| 1* | 2 | 2 |
| 2* | 6 | 6 |
| 3* | 12 | 12 |
| 4 | 24 | 25 |
| 5 | 40 | 46 |
| 6 | 72 | 82 |
| 7 | 126 | 140 |
| 8* | 240 | 240 |
| 9 | 306 | 380 |
| 10 | 500 | 595 |
| 11 | 582 | 915 |
| 12 | 840 | 1,416 |
| 13 | 1,130 | 2,233 |
| 14 | 1,582 | 3,492 |
| 15 | 2,564 | 5,431 |
| 16 | 4,320 | 8,313 |
| 17 | 5,346 | 12,215 |
| 18 | 7,398 | 17,877 |
| 19 | 10,688 | 25,901 |
| 20 | 17,400 | 37,974 |
| 21 | 27,720 | 56,852 |
| 22 | 49,896 | 86,537 |
| 23 | 93,150 | 128,096 |
| 24* | 196,560 | 196,560 |
See also
Sphere packing, Lattice packing
References
- The exact values of kissing number in dimensions 8 and 24 were obtained independently by Levenshtein and Odlyzko/Sloane:
- Levenshtein, V. I. Boundaries for packings in n-dimensional Euclidean space. (Russian) Dokl. Akad. Nauk SSSR 245 (1979), no. 6, 1299—1303.
- Odlyzko, A. M., Sloane, N. J. A. New bounds on the number of unit spheres that can touch a unit sphere in n dimensions. J. Combin. Theory Ser. A 26 (1979), no. 2, 210—214.