Kissing number problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In geometry, a kissing number is defined as the number of non-overlapping unit spheres that can be arranged such that they each touch another given unit sphere. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another. Other names for kissing number that have been used are Newton number (after the originator of the problem), and contact number.

In general, the kissing number problem seeks the maximum possible kissing number for n-dimensional spheres in (n + 1)-dimensional Euclidean space. Ordinary spheres correspond to two-dimensional closed surfaces in three-dimensional space.

Finding the kissing number when centers of spheres are confined to a line (the one-dimensional case) or a plane (two-dimensional case) is trivial. Proving a solution to the three-dimensional case, despite being easy to conceptualise and model in the physical world, eluded mathematicians until the mid-20th century.[1][2] Solutions in higher dimensions are considerably more challenging, and only a handful of cases have been solved exactly. For others investigations have determined upper and lower bounds, but not exact solutions.[3]

Known greatest kissing numbers[edit]

In one dimension, the kissing number is 2:

Kissing-1d.svg

In two dimensions, the kissing number is 6:

Kissing-2d.svg

Proof: Consider a circle with center C that is touched by circles with centers C1, C2, .... Consider the rays C Ci. These rays all emanate from the same center C, so the sum of angles between adjacent rays is 360°.

Assume by contradiction that there are more than 6 touching circles. Then at least two adjacent rays, say C C1 and C C2, are separated by an angle of less than 60°. The segments C Ci have the same length - 2r - for all i. Therefore the triangle C C1 C2 is isosceles, and its third side - C1 C2 - has a side length of less than 2r. Therefore the circles 1 and 2 intersect - a contradiction.[4]

A nice way to obtain this arrangement is by aligning the centers of outer spheres with vertices of an icosahedron. This would leave just a bit more than 0.1 of the radius between two nearby spheres.

In three dimensions, the kissing number is 12, but the correct value was much more difficult to establish than in dimensions one and two. 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 through a continuous movement 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 correctly thought that the limit was 12; Gregory thought that a 13th could fit. Some incomplete proofs that Newton was correct were offered in the nineteenth century, but the first correct proof did not appear until 1953.[1][2]

The twelve neighbors of the central sphere correspond to the maximum bulk coordination number of an atom in a crystal lattice in which all atoms have the same size (as in a chemical element). A coordination number of 12 is found in a cubic close-packed or a hexagonal close-packed structure.

In four dimensions, it was 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 (one can place the spheres at the vertices of a suitably scaled 24-cell centered at the origin). As in the three-dimensional case, there is a lot of space left over—even more, in fact, than for n = 3—so the situation was even less clear. In 2003, Oleg Musin proved the kissing number for n = 4 to be 24, using a subtle trick.[5][6]

The kissing number in n dimensions is unknown for n > 4, except for n = 8 (240), and n = 24 (196,560).[7][8] The results in these dimensions stem from the existence of highly symmetrical lattices: the E8 lattice and the Leech lattice.

If arrangements are restricted to regular arrangements, in which the centres of the spheres all lie on points in a lattice, then this restricted kissing number is known for n = 1 to 9 and n = 24 dimensions.[9] For 5, 6 and 7 dimensions the arrangement with the highest known kissing number is the optimal lattice arrangement, but the existence of a non-lattice arrangement with a higher kissing number has not been excluded.

Some known bounds[edit]

The following table lists some known bounds on the kissing number in various dimensions.[3] The dimensions in which the kissing number is known are listed in boldface.

Rough volume estimates show that kissing number in n dimensions grows exponentially in n. The base of exponential growth is not known. The grey area in the above plot represents the possible values between known upper and lower bounds. Circles represent values that are known exactly.
Dimension Lower
bound
Upper
bound
1 2
2 6
3 12
4 24[5]
5 40 44
6 72 78
7 126 134
8 240
9 306 364
10 500 554
11 582 870
12 840 1,357
13 1,154[10] 2,069
14 1,606[10] 3,183
15 2,564 4,866
16 4,320 7,355
17 5,346 11,072
18 7,398 16,572
19 10,688 24,812
20 17,400 36,764
21 27,720 54,584
22 49,896 82,340
23 93,150 124,416
24 196,560

Generalization[edit]

The kissing number problem can be generalized to the problem of finding the maximum number of non-overlapping congruent copies of any convex body that touch a given copy of the body. There are different versions of the problem depending on whether the copies are only required to be congruent to the original body, translates of the original body, or translated by a lattice. For the regular tetrahedron, for example, it is known that both the lattice kissing number and the translative kissing number are equal to 18, whereas the congruent kissing number is at least 56.[11]

See also[edit]

Notes[edit]

  1. ^ a b Conway, John H.; Neil J.A. Sloane (1999). Sphere Packings, Lattices and Groups (3rd ed.). New York: Springer-Verlag. p. 21. ISBN 0-387-98585-9. 
  2. ^ a b Brass, Peter; Moser, W. O. J.; Pach, János (2005). Research problems in discrete geometry. Springer. p. 93. ISBN 978-0-387-23815-9. 
  3. ^ a b Mittelmann, Hans D.; Vallentin, Frank (2009). "High accuracy semidefinite programming bounds for kissing numbers". Experimental Mathematics 19: 174–178. arXiv:0902.1105. 
  4. ^ See also Lemma 3.1 in Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). "Simple heuristics for unit disk graphs". Networks 25 (2): 59. doi:10.1002/net.3230250205.  edit
  5. ^ a b O. R. Musin (2003). "The problem of the twenty-five spheres". Russ. Math. Surv. 58 (4): 794–795. doi:10.1070/RM2003v058n04ABEH000651. 
  6. ^ Pfender, Florian; Ziegler, Günter M. (September 2004). "Kissing numbers, sphere packings, and some unexpected proofs". Notices of the American Mathematical Society: 873–883. .
  7. ^ Levenshtein, Vladimir I. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [On bounds for packings in n-dimensional Euclidean space]. Doklady Akademii Nauk SSSR (in Russian) 245 (6): 1299–1303. 
  8. ^ 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
  9. ^ Weisstein, Eric W., "Kissing Number", MathWorld.
  10. ^ a b В. А. Зиновьев, Т. Эриксон (1999). "Новые нижние оценки на контактное число для небольших размерностей". Пробл. Передачи Информ. (in Russian) 35 (4): 3–11.  English translation: V. A. Zinov'ev, T. Ericson (1999). "New Lower Bounds for Contact Numbers in Small Dimensions". Problems of Information Transmission 35 (4): 287–294. MR 1737742. 
  11. ^ Lagarias, Jeffrey C.; Zong, Chuanming (December 2012). "Mysteries in packing regular tetrahedra". Notices of the American Mathematical Society: 1540–1549. 

References[edit]