Kiss number
In geometry , the -th kiss number (also contact number ) is the maximum number of one - dimensional unit spheres ( spheres with radius 1). which at the same time can touch another such unit sphere in Euclidean space without overlapping. Of lattice kiss numbers is when the centers of the balls in a grid are arranged. A known kiss number problem is the lack of a general formula to calculate kiss numbers.
Kiss numbers in different dimensions
: In one dimension the unit sphere is not a sphere, but a segment whose endpoints are 1 from the origin . Here, a further line can be added to both end points so that the kiss number for one dimension is obviously 2.
: In the second dimension , the unit sphere is not a sphere, but a circle with radius 1. The problem of determining the kiss number in this dimension corresponds to the task of arranging as many coins as possible so that they all touch a central coin of the same size. It is easy to see (and prove) that the kiss number for the second dimension is 6.
: In the third dimension , finding the kiss number is not that easy; see. the graphic on the right. It is easy to arrange twelve spheres so that they touch the central sphere (for example, so that their centers form the corners of a cuboctahedron ). But you can still see a lot of empty space between the spheres and wonder whether a thirteenth sphere can be added. This problem was the subject of a famous argument between Isaac Newton and the mathematician David Gregory , which they led in 1692 over the Kepler conjecture . Newton said the maximum was twelve, Gregory said it was thirteen. In the 19th century, the first publications claiming to contain evidence for Newton's claim appeared. However, by today's standards, formal evidence was not provided until 1953 by Kurt Schütte and Bartel Leendert van der Waerden and in 1956 by John Leech .
: It was only at the beginning of the 21st century that it was proven that the kiss number for the fourth dimension is 24.
: Furthermore, the kiss numbers for the dimensions n = 8 (240) and n = 24 (196,560) are known; in the 24-dimensional space the balls are placed on the points of the leech grid so that there is no space left. The exact kiss numbers for dimensions 8 and 24 were determined independently in 1979 by Andrew M. Odlyzko and Neil JA Sloane or Vladimir Levenshtein.
The following table shows the known limits for the number of kisses up to dimension 24.
dimension | Kiss number | |
---|---|---|
lower limit | upper limit | |
1 | 2 | |
2 | 6th | |
3 | 12 | |
4th | 24 | |
5 | 40 | 44 |
6th | 72 | 78 |
7th | 126 | 134 |
8th | 240 | |
9 | 306 | 364 |
10 | 500 | 554 |
11 | 582 | 870 |
12 | 840 | 1,357 |
dimension | Kiss number | |
---|---|---|
lower limit | upper limit | |
13 | 1,154 | 2,069 |
14th | 1,606 | 3,183 |
15th | 2,564 | 4,866 |
16 | 4,320 | 7,355 |
17th | 5,346 | 11,072 |
18th | 7,398 | 16,572 |
19th | 10,688 | 24,812 |
20th | 17,400 | 36,764 |
21st | 27,720 | 54,584 |
22nd | 49,896 | 82,340 |
23 | 93,150 | 124,416 |
24 | 196,560 |
Estimates show that the growth in kiss numbers is exponential ; see. Graphic next to the table. The basis of exponential growth is unknown.
Little is known about the kiss numbers in even higher dimensions; lower bounds are known for the dimensions (276.032), (438.872), (991.792), (2.948.552), (331.737.984) and (1.368.532.064).
Lattice kiss numbers in different dimensions
The exact grid kiss numbers are known for the dimensions 1 to 9 and 24. The following table shows the lattice kiss numbers and the known lower limits up to dimension 24:
dimension | Lattice kiss number |
---|---|
1 | 2 |
2 | 6th |
3 | 12 |
4th | 24 |
5 | 40 |
6th | 72 |
7th | 126 |
8th | 240 |
9 | 272 |
10 | ≥ 336 |
11 | ≥ 438 |
12 a | ≥ 756 |
dimension | Lattice kiss number |
---|---|
13 | ≥ 918 |
14th | ≥ 1,422 |
15th | ≥ 2,340 |
16 | ≥ 4,320 |
17th | ≥ 5,346 |
18th | ≥ 7,398 |
19th | ≥ 10,668 |
20th | ≥ 17,400 |
21st | ≥ 27,720 |
22nd | ≥ 49,896 |
23 | ≥ 93,150 |
24 b | 196,560 |
Die Gitterpackungen für die Dimensionen 12 und 24 haben eigene Namen:
calculation
If the spherical radii are normalized to 1/2 and the origin of the coordinate system is placed in the center of the central sphere, then the following system of inequalities must be fulfilled for N kissing spheres:
Here m and n run from 1 to N and is the sequence of the vectors to the N spherical centers, || a || is the norm (length) of the vector a . For reasons of symmetry it is sufficient if the second universal quantifier extends over all m , n with m < n .
In a D -dimensional real vector space , this becomes after transition to the standard squares in matrix notation
- .
The vectors x are understood as column vectors, and x T is the corresponding row vector ( transposed matrix ), the scalar product . This system of inequalities is transformed into the system of equations after transformation and the introduction of auxiliary variables
- .
The above system of equations has a total of equations for the N vectors x , plus half of those for the matrix y ; all in all equations. Because of the relative size of the number N of kissing balls to be tested, the practical limits of predictability are quickly reached.
Estimates
The general form of the lower bound for -dimensional lattice measures is given by
- ,
where is the Riemann zeta function . This limit is specified by the Minkowski-Hlawka theorem (after Hermann Minkowski and Edmund Hlawka ).
See also
Notes and references
- ↑ C. Bender: Determination of the greatest number of equal balls that can be placed on a ball of the same radius as the rest. In: Archive Math. Physics. (Grunert) Volume 56, 1874, pp. 302-306.
- ^ S. Günther: A stereometric problem. In: Archive Math. Physics. Volume 57, 1875, pp. 209-215.
- ^ R. Hoppe: Comment from the editorial team. In: Archive Math. Physics. (Grunert) Volume 56, 1874, pp. 307-312
- ↑ Schütte, van der Waerden: The problem of the thirteen balls. In: Math. Annals. Volume 125, 1953, pp. 325-334.
- ↑ Leech: The Problem of Thirteen Spheres. In: The Mathematical Gazette. Volume 40, 1956, pp. 22-23
- ^ Oleg R. Musin: The kissing number in four dimensions . In: Annals of Mathematics . Vol. 168, No. 1 , 2008, p. 1-32 , arxiv : math / 0309430 .
- ^ Andrew M. Odlyzko , Neil JA Sloane : New bounds on the number of unit spheres that can touch a unit sphere in n dimensions. In: J. Combin. Theory. Ser. A, Vol. 26, 1979, No. 2, pp. 210-214
- ↑ Vladimir I. Levenshtein : О границах для упаковок в n-мерном евклидовом пространстве . No. 6, Docl. Akad. Nauk SSSR 245 1979. pp. 1299-1303
- ^ Hans D. Mittelmann, Frank Vallentin: High accuracy semidefinite programming bounds for kissing numbers . arxiv : 0902.1105
- ↑ Follow A001116 in OEIS
- ↑ a b https://www.wolframalpha.com/input/?i=kissingnumber Proof from Zinov'ev and Ericson
- ^ Yves Edel, EM Rains, NJA Sloane: On Kissing Numbers in Dimensions 32 to 128 . In: The Electronic Journal of Combinatorics. Volume 5, Issue 1, 1998
- ^ John Horton Conway , Neil JA Sloane : The Kissing Number Problem. and Bounds on Kissing Numbers. In: John Horton Conway, Neil JA Sloane: Sphere Packings, Lattices, and Groups. 2nd Edition. Springer-Verlag, New York 1993. pp. 21-24 and 337-339, ISBN 0-387-98585-9 .
- ^ Neil JA Sloane , Gabriele Nebe : Table of Highest Kissing Numbers Presently Known. http://www.research.att.com/~njas/lattices/kiss.html
- ↑ Eric W. Weisstein : Coxeter-Todd grid . In: MathWorld (English).
- ↑ Eric W. Weisstein : Leech grid . In: MathWorld (English).
- ↑ Sergei Kucherenko et al .: New formulations for the Kissing Number Problem , in: Discrete Applied Mathematics, Volume 155, Issue 14, September 1, 2007, pages 1837–1841, doi: 10.1016 / j.dam 2006.05.012 . The author works with spherical radii standardized to 1.
- ↑ d. H. an auxiliary matrix , of which only the coefficients with m < n are required. In particular, they can be set to 0, and the matrix can optionally be assumed to be symmetric, antisymmetric or a triangular matrix.
- ↑ because of symmetry
- ↑ Eric W. Weisstein : Minkowski-Hlawka Theorem . In: MathWorld (English).
literature
- Florian Pfender , Günter M. Ziegler : Kissing Numbers, Sphere Packings, and Some Unexpected Proofs . Notices of the American Mathematical Society, pp. 873-883. ( PDF )
- Eric W. Weisstein : Kissing Number . In: MathWorld (English).
- Robert Calderbank: Interview with Neil Sloane (English)
- Christine Bachoc, Frank Vallentin: New upper bounds for kissing numbers from semidefinite programming . In: Journal of the American Mathematical Society. Volume 21, 2008, pp. 909-924. arxiv : math.MG/0608426
- John Horton Conway, Neil James Alexander Sloane, Eiichi Bannai: Sphere packings, lattices, and groups . Springer, 1999. ISBN 978-0-387-98585-5 . limited online version (Google books)
- Casselman on the Kissing Number problem and its history, Notices of the AMS, 2004, Issue 8, PDF file