Kissing number

One dimension In one dimension, the kissing number is : Two dimensions In two dimensions, the kissing number is : 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 six 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. Three dimensions . This leaves slightly more than of the radius between two nearby spheres. In three dimensions, the kissing number is , 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, with 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 ; Gregory thought that a 13th could fit. Some incomplete proofs that Newton was correct were offered in the 19th century, most notably one by Reinhold Hoppe, but the first correct proof (according to Brass, Moser, and Pach) did not appear until 1953. 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 is found in a cubic close-packed or a hexagonal close-packed structure. Larger dimensions In four dimensions, the kissing number is . This was proven in 2003 by Oleg Musin. Previously, the answer was thought to be either or : it is straightforward to produce a packing of 24 spheres around a central sphere (one can place the spheres at the vertices of a suitably scaled -cell centered at the origin), but, as in the three-dimensional case, there is a lot of space left over — even more, in fact, than for — so the situation was even less clear. The existence of the highly symmetrical lattice and Leech lattice has allowed to determine the kissing number for (namely, ) and for (namely, ). For and dimensions, the arrangement with the highest known kissing number found so far 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==

The following table lists some known bounds on the kissing number in various dimensions. The dimensions in which the kissing number is known are listed in boldface. in . The base of exponential growth is not known. The gray area in the above plot represents the possible values between known upper and lower bounds. Circles represent values that are known exactly. ==Generalization==

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 example, for the regular tetrahedron, it is known that both the lattice kissing number and the translative kissing number are equal to , whereas the congruent kissing number is at least . ==Algorithms==

There are several approximation algorithms on intersection graphs where the approximation ratio depends on the kissing number. For example, there is a polynomial-time -approximation algorithm to find a maximum non-intersecting subset of a set of rotated unit squares. ==Mathematical statement==

The kissing number problem can be stated as the existence of a solution to a set of inequalities. Let x_n be a set of N D-dimensional position vectors of sphere centres. The condition that this set of spheres can lie round the central sphere without overlapping is: \exist x\ \left\{ \forall_n \{x_n^\textsf{T} x_n = 1\} \land \forall_{m,n: m \neq n} \{ (x_n - x_m)^\textsf{T}(x_n - x_m) \geq 1\} \right\}. Thus the problem for each dimension can be expressed in the existential theory of the reals. However, general methods of solving problems in this form take at least exponential time; that is why this problem has only been solved up to four dimensions. By using additional variables y_{nm}, this can be converted to a single quartic equation in N(N-1)/2 + DN variables: \exist xy\ \left\{ \sum_n \left(x_n^\textsf{T} x_n - 1\right)^2 + \sum_{m,n: m Therefore, to solve the case in D = 5 dimensions and N = D5 lattice| vectors would be equivalent to determining the existence of real solutions to a quartic polynomial in 1025 variables. For the D = 24 dimensions and N = Leech lattice| , the quartic would have 19,322,732,544 variables. An alternative statement in terms of distance geometry is given by the squared distances R_{mn} between the m-th and n-th sphere centers: \exist R\ \{ \forall_n \{R_{0n} = 1 \} \land \forall_{m,n: m This must be supplemented with the condition that the Cayley–Menger determinant is zero for any set of points which forms a (D+1)-simplex in D dimensions, since that volume must be zero. Setting R_{mn} = 1 + {y_{mn}}^2 gives a set of simultaneous polynomial equations in just y which must be solved for real values only. The two methods, being entirely equivalent, have various different uses. For example, in the second case, one can randomly alter the values of the y by small amounts to try to minimise the polynomial in terms of the y. ==See also==