Kissing number

Last updated
Unsolved problem in mathematics:
What is the maximum possible kissing number for n-dimensional spheres in (n + 1)-dimensional Euclidean space?

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. For a given sphere packing (arrangement of spheres) in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. 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.

Contents

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

One dimension

In one dimension, [4] the kissing number is 2:

Kissing-1d.svg

Two dimensions

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 CCi. 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 CC1 and CC2, are separated by an angle of less than 60°. The segments C Ci have the same length – 2r – for all i. Therefore, the triangle CC1C2 is isosceles, and its third side – C1C2 – has a side length of less than 2r. Therefore, the circles 1 and 2 intersect – a contradiction. [5]

A highly symmetrical realization of the kissing number 12 in three dimensions is by aligning the centers of outer spheres with vertices of a regular icosahedron. This leaves slightly more than 0.1 of the radius between two nearby spheres. Kissing-3d.png
A highly symmetrical realization of the kissing number 12 in three dimensions is by aligning the centers of outer spheres with vertices of a regular icosahedron. This leaves slightly more than 0.1 of the radius between two nearby spheres.

Three dimensions

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, 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 12; Gregory thought that a 13th could fit. 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). A coordination number of 12 is found in a cubic close-packed or a hexagonal close-packed structure.

Larger dimensions

In four dimensions, the kissing number is 24. This was proven in 2003 by Oleg Musin. [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). [9] [10] The kissing number in n dimensions is unknown for other dimensions.

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.

Some known bounds

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. Kissing growth.svg
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.
DimensionLower
bound
Upper
bound
12
2 6
3 12
4 24 [7]
5 40 44
6 72 77
7 126 134
8 240
9306363
10510553
11592868
128401,355
131,1542,064
141,9323,174
152,5644,853
164,3207,320
175,73010,978
187,65416,406
1911,69224,417
2019,44836,195
2129,76853,524
2249,89680,810
2393,150122,351
24 196,560

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

Algorithms

There are several approximation algorithms on intersection graphs where the approximation ratio depends on the kissing number. [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.

Mathematical statement

The kissing number problem can be stated as the existence of a solution to a set of inequalities. Let be a set of ND-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: [15]

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, 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. 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 between the mth and nth sphere:

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

Notes

  1. 1 2 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. 1 2 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. Mittelmann, Hans D.; Vallentin, Frank (2010). "High accuracy semidefinite programming bounds for kissing numbers". Experimental Mathematics . 19 (2): 174–178. arXiv: 0902.1105 . Bibcode:2009arXiv0902.1105M. doi:10.1080/10586458.2010.10129070. S2CID   218279.
  4. Note that in one dimension, "spheres" are just pairs of points separated by the unit distance. (The vertical dimension of one-dimensional illustration is merely evocative.) Unlike in higher dimensions, it is necessary to specify that the interior of the spheres (the unit-length open intervals) do not overlap in order for there to be a finite packing density.
  5. 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. arXiv: math/9409226 . doi:10.1002/net.3230250205.
  6. Zong, Chuanming (2008). "The kissing number, blocking number and covering number of a convex body". In Goodman, Jacob E.; Pach, J├ínos; Pollack, Richard (eds.). Surveys on Discrete and Computational Geometry: Twenty Years Later (AMS-IMS-SIAM Joint Summer Research Conference, June 18ÔÇô22, 2006, Snowbird, Utah). Contemporary Mathematics. Vol. 453. Providence, RI: American Mathematical Society. pp. 529–548. doi:10.1090/conm/453/08812. ISBN   9780821842393. MR   2405694..
  7. 1 2 O. R. Musin (2003). "The problem of the twenty-five spheres". Russ. Math. Surv. 58 (4): 794–795. Bibcode:2003RuMaS..58..794M. doi:10.1070/RM2003v058n04ABEH000651. S2CID   250839515.
  8. Pfender, Florian; Ziegler, Günter M. (September 2004). "Kissing numbers, sphere packings, and some unexpected proofs" (PDF). Notices of the American Mathematical Society: 873–883..
  9. Levenshtein, Vladimir I. (1979). "О границах для упаковок в n-мерном евклидовом пространстве" [On bounds for packings in n-dimensional Euclidean space]. Doklady Akademii Nauk SSSR (in Russian). 245 (6): 1299–1303.
  10. Odlyzko, A. M.; Sloane, N. J. A. (1979). "New bounds on the number of unit spheres that can touch a unit sphere in n dimensions". Journal of Combinatorial Theory . Series A. 26 (2): 210–214. doi: 10.1016/0097-3165(79)90074-8 .
  11. Weisstein, Eric W. "Kissing Number". MathWorld .
  12. Machado, Fabrício C.; Oliveira, Fernando M. (2018). "Improving the Semidefinite Programming Bound for the Kissing Number by Exploiting Polynomial Symmetry". Experimental Mathematics . 27 (3): 362–369. arXiv: 1609.05167 . doi:10.1080/10586458.2017.1286273. S2CID   52903026.
  13. Lagarias, Jeffrey C.; Zong, Chuanming (December 2012). "Mysteries in packing regular tetrahedra" (PDF). Notices of the American Mathematical Society: 1540–1549.
  14. Kammer, Frank; Tholey, Torsten (July 2012). "Approximation Algorithms for Intersection Graphs". Algorithmica. 68 (2): 312–336. doi:10.1007/s00453-012-9671-1. S2CID   3065780.
  15. Numbers m and n run from 1 to N. is the sequence of the N positional vectors. As the condition behind the second universal quantifier () does not change if m and n are exchanged, it is sufficient to let this quantor extend just over . For simplification the sphere radiuses are assumed to be 1/2.
  16. Concerning the matrix only the entries having m < n are needed. Or, equivalent, the matrix can be assumed to be antisymmetric. Anyway the matrix has justN(N  1)/2 free scalar variables. In addition, there are ND-dimensional vectors xn, which correspondent to a matrix of N column vectors.

Related Research Articles

<span class="mw-page-title-main">Hausdorff dimension</span> Invariant measure of fractal dimension

In mathematics, Hausdorff dimension is a measure of roughness, or more specifically, fractal dimension, that was introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a line segment is 1, of a square is 2, and of a cube is 3. That is, for sets of points that define a smooth shape or a shape that has a small number of corners—the shapes of traditional geometry and science—the Hausdorff dimension is an integer agreeing with the usual sense of dimension, also known as the topological dimension. However, formulas have also been developed that allow calculation of the dimension of other less simple objects, where, solely on the basis of their properties of scaling and self-similarity, one is led to the conclusion that particular objects—including fractals—have non-integer Hausdorff dimensions. Because of the significant technical advances made by Abram Samoilovitch Besicovitch allowing computation of dimensions for highly irregular or "rough" sets, this dimension is also commonly referred to as the Hausdorff–Besicovitch dimension.

<span class="mw-page-title-main">Square matrix</span> Matrix with the same number of rows and columns

In mathematics, a square matrix is a matrix with the same number of rows and columns. An n-by-n matrix is known as a square matrix of order . Any two square matrices of the same order can be added and multiplied.

<span class="mw-page-title-main">Packing problems</span> Problems which attempt to find the most efficient way to pack objects into containers

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life packaging, storage and transportation issues. Each packing problem has a dual covering problem, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.

In mathematics, the Leech lattice is an even unimodular lattice Λ24 in 24-dimensional Euclidean space, which is one of the best models for the kissing number problem. It was discovered by John Leech. It may also have been discovered by Ernst Witt in 1940.

<span class="mw-page-title-main">Sphere packing</span> Geometrical structure

In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space. However, sphere packing problems can be generalised to consider unequal spheres, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.

<span class="mw-page-title-main">Discrete geometry</span> Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

<span class="mw-page-title-main">Lattice (group)</span> Periodic set of points

In geometry and group theory, a lattice in the real coordinate space is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of , the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.

<span class="mw-page-title-main">Kakeya set</span> Shape containing unit line segments in all directions

In mathematics, a Kakeya set, or Besicovitch set, is a set of points in Euclidean space which contains a unit line segment in every direction. For instance, a disk of radius 1/2 in the Euclidean plane, or a ball of radius 1/2 in three-dimensional space, forms a Kakeya set. Much of the research in this area has studied the problem of how small such sets can be. Besicovitch showed that there are Besicovitch sets of measure zero.

<span class="mw-page-title-main">Arrangement of hyperplanes</span> Partition of space by a hyperplanes

In geometry and combinatorics, an arrangement of hyperplanes is an arrangement of a finite set A of hyperplanes in a linear, affine, or projective space S. Questions about a hyperplane arrangement A generally concern geometrical, topological, or other properties of the complement, M(A), which is the set that remains when the hyperplanes are removed from the whole space. One may ask how these properties are related to the arrangement and its intersection semilattice. The intersection semilattice of A, written L(A), is the set of all subspaces that are obtained by intersecting some of the hyperplanes; among these subspaces are S itself, all the individual hyperplanes, all intersections of pairs of hyperplanes, etc. (excluding, in the affine case, the empty set). These intersection subspaces of A are also called the flats ofA. The intersection semilattice L(A) is partially ordered by reverse inclusion.

<span class="mw-page-title-main">Close-packing of equal spheres</span> Dense arrangement of congruent spheres in an infinite, regular arrangement

In geometry, close-packing of equal spheres is a dense arrangement of congruent spheres in an infinite, regular arrangement. Carl Friedrich Gauss proved that the highest average density – that is, the greatest fraction of space occupied by spheres – that can be achieved by a lattice packing is

In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors.

In mathematics, the E8 lattice is a special lattice in R8. It can be characterized as the unique positive-definite, even, unimodular lattice of rank 8. The name derives from the fact that it is the root lattice of the E8 root system.

<span class="mw-page-title-main">Convex polytope</span> Convex hull of a finite set of points in a Euclidean space

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.

In linear algebra, an eigenvector or characteristic vector is a vector that has its direction unchanged by a given linear transformation. More precisely, an eigenvector, , of a linear transformation, , is scaled by a constant factor, , when the linear transformation is applied to it: . The corresponding eigenvalue, characteristic value, or characteristic root is the multiplying factor .

In mathematics, the square root of a matrix extends the notion of square root from numbers to matrices. A matrix B is said to be a square root of A if the matrix product BB is equal to A.

The 8-demicubic honeycomb, or demiocteractic honeycomb is a uniform space-filling tessellation in Euclidean 8-space. It is constructed as an alternation of the regular 8-cubic honeycomb.

In mathematics, a sequence of n real numbers can be understood as a location in n-dimensional space. When n = 8, the set of all such locations is called 8-dimensional space. Often such spaces are studied as vector spaces, without any notion of distance. Eight-dimensional Euclidean space is eight-dimensional space equipped with the Euclidean metric.

In digital signal processing, multidimensional sampling is the process of converting a function of a multidimensional variable into a discrete collection of values of the function measured on a discrete set of points. This article presents the basic result due to Petersen and Middleton on conditions for perfectly reconstructing a wavenumber-limited function from its measurements on a discrete lattice of points. This result, also known as the Petersen–Middleton theorem, is a generalization of the Nyquist–Shannon sampling theorem for sampling one-dimensional band-limited functions to higher-dimensional Euclidean spaces.

In the mathematical fields of numerical analysis and approximation theory, box splines are piecewise polynomial functions of several variables. Box splines are considered as a multivariate generalization of basis splines (B-splines) and are generally used for multivariate approximation/interpolation. Geometrically, a box spline is the shadow (X-ray) of a hypercube projected down to a lower-dimensional space. Box splines and simplex splines are well studied special cases of polyhedral splines which are defined as shadows of general polytopes.

In mathematics, the theory of finite sphere packing concerns the question of how a finite number of equally-sized spheres can be most efficiently packed. The question of packing finitely many spheres has only been investigated in detail in recent decades, with much of the groundwork being laid by László Fejes Tóth.

References