Kissing number

In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere.

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] In one dimension,[4] the kissing number is 2: In two dimensions, the kissing number is 6: Proof: Consider a circle with center C that is touched by circles with centers C1, C2, ....

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

Some incomplete proofs that Newton was correct were offered in the nineteenth century, most notably one by Reinhold Hoppe, but the first correct proof (according to Brass, Moser, and Pach) did not appear until 1953.

[1][2][6] 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).

[7][8] Previously, the answer was thought to be either 24 or 25: 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 24-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 n = 3 — so the situation was even less clear.

The existence of the highly symmetrical E8 lattice and Leech lattice has allowed known results for n = 8 (where the kissing number is 240), and n = 24 (where it is 196,560).

If arrangements are restricted to lattice 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.

[11] For 5, 6, and 7 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.

The following table lists some known bounds on the kissing number in various dimensions.

[12] The dimensions in which the kissing number is known are listed in boldface.

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.

[14] For example, there is a polynomial-time 10-approximation algorithm to find a maximum non-intersecting subset of a set of rotated unit squares.

The kissing number problem can be stated as the existence of a solution to a set of inequalities.

be a set of N D-dimensional position vectors of the centres of the spheres.

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 which is why this problem has only been solved up to four dimensions.

this can be converted to a single quartic equation in N(N − 1)/2 + DN variables:[16]

Therefore, to solve the case in D = 5 dimensions and N = 40 + 1 vectors would be equivalent to determining the existence of real solutions to a quartic polynomial in 1025 variables.

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.

gives a set of simultaneous polynomial equations in just y which must be solved for real values only.

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.