Kissing number

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.

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.

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.[14]

There are several approximation algorithms on intersection graphs where the approximation ratio depends on the kissing number.[15] 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. Let ${\displaystyle x_{n}}$ be a set of N D-dimensional position vectors of the centres of the spheres. The condition that this set of spheres can lie round the centre sphere without overlapping is:[16]

$${\displaystyle \exists 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 which is why this problem has only been solved up to four dimensions. By adding additional variables, ${\displaystyle y_{nm}}$ this can be converted to a single quartic equation in N(N − 1)/2 + DN variables:[17]

$${\displaystyle \exists xy\ \left\{\sum _{n}\left(x_{n}^{\textsf {T}}x_{n}-1\right)^{2}+\sum _{m,n:m<n}{\Big (}(x_{n}-x_{m})^{\textsf {T}}(x_{n}-x_{m})-1-(y_{nm})^{2}{\Big )}^{2}=0\right\}}$$

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. For the D = 24 dimensions and N = 196560 + 1, the quartic would have 19,322,732,544 variables. An alternative statement in terms of distance geometry is given by the distances squared ${\displaystyle R_{mn}}$ between the m^th and n^th sphere:

$${\displaystyle \exists R\ \{\forall _{n}\{R_{0n}=1\}\land \forall _{m,n:m<n}\{R_{mn}\geq 1\}\}}$$

This must be supplemented with the condition that the Cayley–Menger determinant is zero for any set of points which forms an (D + 1) simplex in D dimensions, since that volume must be zero. Setting ${\displaystyle 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.

• Equilateral dimension
• Spherical code
• Soddy's hexlet
• Cylinder sphere packing

• T. Aste and D. Weaire The Pursuit of Perfect Packing (Institute Of Physics Publishing London 2000) ISBN 0-7503-0648-3
• Table of the Highest Kissing Numbers Presently Known maintained by Gabriele Nebe and Neil Sloane (lower bounds)
• Bachoc, Christine; Vallentin, Frank (2008). "New upper bounds for kissing numbers from semidefinite programming". Journal of the American Mathematical Society. 21 (3): 909–924. arXiv:math.MG/0608426. Bibcode:2008JAMS...21..909B. doi:10.1090/S0894-0347-07-00589-9. MR 2393433. S2CID 204096.

• Grime, James. "Kissing Numbers" (video). youtube. Brady Haran. Archived from the original on 2021-12-12. Retrieved 11 October 2018.