www.wikidata.de-de.nina.az

Kusszahl In der Geometrie ist die n displaystyle n te auch Kontaktzahl die maximale Anzahl an n displaystyle n dimension

Kusszahl

In der Geometrie ist die -te Kusszahl (auch Kontaktzahl) die maximale Anzahl an -dimensionalen Einheitskugeln (Kugeln mit Radius 1), die gleichzeitig eine weitere solche Einheitskugel im euklidischen Raum berühren können, ohne dass Überschneidungen auftreten. Von Gitterkusszahlen spricht man, wenn die Mittelpunkte der Kugeln in einem Gitter angeordnet sind. Als Kusszahlenproblem ist das Fehlen einer allgemeinen Formel zur Berechnung der Kusszahlen bekannt.

Kusszahlen in verschiedenen Dimensionen Bearbeiten

Die erste Kusszahl ist 2.
Die zweite Kusszahl ist 6.

n = 1:  In einer Dimension ist die Einheitskugel keine Kugel, sondern eine Strecke, deren Endpunkte den Abstand 1 vom Ursprung haben. Hier kann an beide Endpunkte jeweils eine weitere Strecke angefügt werden, sodass die Kusszahl für eine Dimension offensichtlich 2 ist.

n = 2:  In der zweiten Dimension ist die Einheitskugel keine Kugel, sondern ein Kreis mit Radius 1. Anschaulich entspricht damit das Problem der Ermittlung der Kusszahl in dieser Dimension der Aufgabe, möglichst viele Münzen so anzuordnen, dass sie alle eine gleich große zentrale Münze berühren. Es ist leicht zu sehen (und zu beweisen), dass die Kusszahl für die zweite Dimension 6 ist.

n = 3:  In der dritten Dimension ist die Ermittlung der Kusszahl nicht so einfach; vgl. die Graphik rechts. Es ist leicht, zwölf Kugeln so anzuordnen, dass sie die zentrale Kugel berühren (beispielsweise so, dass ihre Mittelpunkte die Ecken eines Kuboktaeders bilden). Man erkennt aber noch viel Leerraum zwischen den Kugeln und fragt sich, ob eine dreizehnte Kugel hinzugefügt werden kann. Dieses Problem war Thema eines berühmten Streites zwischen Isaac Newton und dem Mathematiker David Gregory, den diese 1692 über die Keplerschen Vermutung führten. Newton behauptete, das Maximum sei zwölf, Gregory meinte, es sei dreizehn. Im 19. Jahrhundert erschienen die ersten Veröffentlichungen, die behaupteten, den Beweis für Newtons Behauptung zu enthalten. Nach heutigen Standards wurden formelle Beweise jedoch erst 1953 von Kurt Schütte und Bartel Leendert van der Waerden und 1956 von John Leech erbracht.

n = 4:  Erst Anfang des 21. Jahrhunderts wurde bewiesen, dass die Kusszahl für die vierte Dimension 24 ist.

n > 4:  Ferner sind die Kusszahlen für die Dimensionen  n = 8  (240) und  n = 24  (196.560) bekannt; im 24-dimensionalen Raum werden die Kugeln auf den Punkten des Leech-Gitters platziert, sodass kein Platz übrig ist. Die exakten Kusszahlen für die Dimensionen 8 und 24 wurden 1979 unabhängig voneinander von Andrew M. Odlyzko und Neil J. A. Sloane bzw. Vladimir Levenshtein ermittelt.

Die folgende Tabelle gibt die bekannten Grenzen für die Kusszahl bis zur Dimension 24 wieder.

Die dritte Kusszahl ist 12.
Die mittige Kugel (rot) wird von
6 Kugeln (grün) in gleicher Ebene,
3 Kugeln (gelb) darüber und
3 Kugeln (blau, 60° gegen gelbe verdreht) darunter berührt.
Das exponentielle Wachstum der Kusszahlen; Dimensionen 1 bis 24. Die graue Fläche ist durch die oberen und unteren Grenzen (s. Tabelle) begrenzt.
Kusszahlen in den Dimensionen 1…24
Dimen-
sion		 Kusszahl Dimen-
sion		 Kusszahl
untere
Grenze		 obere
Grenze		 untere
Grenze		 obere
Grenze
1 2 13 1154 2069
2 6 14 1606 3183
3 12 15 2564 4866
4 24 16 4320 7355
5 40 44 17 5346 11.072
6 72 78 18 7398 16.572
7 126 134 19 10.688 24.812
8 240 20 17.400 36.764
9 306 364 21 27.720 54.584
10 500 554 22 49.896 82.340
11 582 870 23 93.150 124.416
12 840 1.357 24 196.560

Schätzungen zeigen, dass das Wachstum der Kusszahlen exponentiell ist; vgl. Graphik neben der Tabelle. Die Basis des exponentiellen Wachstums ist unbekannt.

Über die Kusszahlen in noch höheren Dimensionen ist eher wenig bekannt; untere Schranken sind etwa für die Dimensionen  n = 32  (276.032),  n = 36  (438.872),  n = 40  (991.792),  n = 44  (2.948.552),  n = 64  (331.737.984) und  n = 80  (1.368.532.064) bekannt.

Gitterkusszahlen in verschiedenen Dimensionen Bearbeiten

Die exakten Gitterkusszahlen sind für die Dimensionen 1 bis 9 und 24 bekannt.
Die folgende Tabelle gibt die Gitterkusszahlen bzw. die bekannten unteren Grenzen bis zur Dimension 24 wieder:

Gitterkusszahlen in den Dimensionen 1..24
Dimension Gitterkusszahl Dimension Gitterkusszahl
1 2 13 ≥ 918
2 6 14 ≥ 1422
3 12 15 ≥ 2340
4 24 16 ≥ 4320
5 40 17 ≥ 5346
6 72 18 ≥ 7398
7 126 19 ≥ 10.668
8 240 20 ≥ 17.400
9 272 21 ≥ 27.720
10 ≥ 336 22 ≥ 49.896
11 ≥ 438 23 ≥ 93.150
12 ⁠a ≥ 756 24 ⁠b 196.560

Die Gitterpackungen für die Dimensionen 12 und 24 haben eigene Namen:

a 
Coxeter-Todd-Gitter (nach Harold Scott MacDonald Coxeter und John Arthur Todd)
b 
Leech-Gitter (nach John Leech)

Berechnung Bearbeiten

Werden die Kugelradien auf normiert und der Ursprung des Koordinatensystems in den Mittelpunkt der zentralen Kugel gelegt, dann muss bei küssenden Kugeln das folgende System von Ungleichungen erfüllt sein:

Dabei laufen und von bis und ist die Sequenz der Vektoren zu den Kugelmittelpunkten, ist die Norm (Länge) des Vektors . Aus Symmetriegründen reicht es, wenn der zweite Allquantor sich über alle , mit erstreckt.
In einem -dimensionalen reellen Vektorraum wird daraus nach Übergang zu den Normquadraten in Matrixschreibweise

Dabei sind die Vektoren als Spaltenvektoren aufgefasst, und ist der entsprechende Zeilenvektor (Transponierte Matrix), das Skalarprodukt. Dieses System von Ungleichungen geht nach Umformung und Einführung von Hilfsvariablen über in das Gleichungssystem

Das obige Gleichungssystem hat insgesamt Gleichungen für die Vektoren , dazu kommen die Hälfte von für die Matrix ; insgesamt also Gleichungen. Wegen der relativen Größe der zu testenden Zahl der küssenden Kugeln stößt man schnell an die praktischen Grenzen der Berechenbarkeit.

Abschätzungen
Die allgemeine Form der unteren Grenze für -dimensionale Gitterkennzahlen ist gegeben durch

wobei die Riemannsche Zeta-Funktion ist. Diese Grenze wird durch den Satz von Minkowski-Hlawka (nach Hermann Minkowski und Edmund Hlawka) spezifiziert.

Siehe auch Bearbeiten

Literatur Bearbeiten

Weblinks Bearbeiten

Commons: Kusszahl – Sammlung von Bildern, Videos und Audiodateien
Wiktionary: Kusszahl – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Anmerkungen und Referenzen Bearbeiten

  1. C. Bender: Bestimmung der größten Anzahl gleich Kugeln, welche sich auf eine Kugel von demselben Radius, wie die Übrigen, auflegen lassen. In: Archiv Math. Physik. (Grunert) Band 56, 1874, S. 302–306.
  2. S. Günther: Ein stereometrisches Problem. In: Archiv Math. Physik. Band 57, 1875, S. 209–215.
  3. R. Hoppe: Bemerkung der Redaction. In: Archiv Math. Physik. (Grunert) Band 56, 1874, S. 307–312
  4. Schütte, van der Waerden: Das Problem der dreizehn Kugeln. In: Math. Annalen. Band 125, 1953, S. 325–334.
  5. Leech: The Problem of Thirteen Spheres. In: The Mathematical Gazette. Band 40, 1956, S. 22–23
  6. Oleg R. Musin: The kissing number in four dimensions. In: Annals of Mathematics. Vol. 168, Nr. 1, 2008, S. 1–32, arxiv:math/0309430.
  7. Andrew M. Odlyzko, Neil J. A. Sloane: New bounds on the number of unit spheres that can touch a unit sphere in n dimensions. In: J. Combin. Theory. Ser. A, Band 26, 1979, Nr. 2, S. 210–214
  8. Vladimir I. Levenshtein: О границах для упаковок в n-мерном евклидовом пространстве. Nr. 6, Dokl. Akad. Nauk SSSR 245 1979. S. 1299–1303
  9. Hans D. Mittelmann, Frank Vallentin: High accuracy semidefinite programming bounds for kissing numbers. arxiv:0902.1105
  10. Folge A001116 in OEIS
  11. ↑ https://www.wolframalpha.com/input/?i=kissingnumber Beweis von Zinov'ev und Ericson
  12. Yves Edel, E. M. Rains, N. J. A. Sloane: On Kissing Numbers in Dimensions 32 to 128. In: The Electronic Journal of Combinatorics. Band 5, Heft 1, 1998
  13. John Horton Conway, Neil J. A. Sloane: The Kissing Number Problem. und Bounds on Kissing Numbers. In: John Horton Conway, Neil J. A. Sloane: Sphere Packings, Lattices, and Groups. 2. Auflage. Springer-Verlag, New York 1993. S. 21–24 und 337–339, ISBN 0-387-98585-9.
  14. Neil J. A. Sloane, Gabriele Nebe: Table of Highest Kissing Numbers Presently Known.
  15. Eric W. Weisstein: Coxeter-Todd-Gitter. In: MathWorld (englisch).
  16. Eric W. Weisstein: Leech-Gitter. In: MathWorld (englisch).
  17. Sergei Kucherenko et al.: New formulations for the Kissing Number Problem, in: Discrete Applied Mathematics, Volume 155, Issue 14, 1. September 2007, Seiten 1837–1841, doi:10.1016/j.dam.2006.05.012. Der Autor arbeitet mit auf 1 normierten Kugelradien.
  18. d. h. einer Hilfsmatrix , von der nur die Koeffizienten mit benötigt werden. Insbesondere können die auf 0 festgelegt werden, und die Matrix wahlweise als symmetrisch, antisymmetrisch oder als Dreiecksmatrix angenommen werden.
  19. wegen Symmetrie
  20. Eric W. Weisstein: Minkowski-Hlawka Theorem. In: MathWorld (englisch).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der Geometrie ist die n displaystyle n te Kusszahl auch Kontaktzahl die maximale Anzahl an n displaystyle n dimensionalen Einheitskugeln Kugeln mit Radius 1 die gleichzeitig eine weitere solche Einheitskugel im euklidischen Raum beruhren konnen ohne dass Uberschneidungen auftreten Von Gitterkusszahlen spricht man wenn die Mittelpunkte der Kugeln in einem Gitter angeordnet sind Als Kusszahlenproblem ist das Fehlen einer allgemeinen Formel zur Berechnung der Kusszahlen bekannt Inhaltsverzeichnis 1 Kusszahlen in verschiedenen Dimensionen 2 Gitterkusszahlen in verschiedenen Dimensionen 3 Berechnung 4 Siehe auch 5 Literatur 6 Weblinks 7 Anmerkungen und ReferenzenKusszahlen in verschiedenen Dimensionen Bearbeiten nbsp Die erste Kusszahl ist 2 nbsp Die zweite Kusszahl ist 6 n 1 In einer Dimension ist die Einheitskugel keine Kugel sondern eine Strecke deren Endpunkte den Abstand 1 vom Ursprung haben Hier kann an beide Endpunkte jeweils eine weitere Strecke angefugt werden sodass die Kusszahl fur eine Dimension offensichtlich 2 ist n 2 In der zweiten Dimension ist die Einheitskugel keine Kugel sondern ein Kreis mit Radius 1 Anschaulich entspricht damit das Problem der Ermittlung der Kusszahl in dieser Dimension der Aufgabe moglichst viele Munzen so anzuordnen dass sie alle eine gleich grosse zentrale Munze beruhren Es ist leicht zu sehen und zu beweisen dass die Kusszahl fur die zweite Dimension 6 ist n 3 In der dritten Dimension ist die Ermittlung der Kusszahl nicht so einfach vgl die Graphik rechts Es ist leicht zwolf Kugeln so anzuordnen dass sie die zentrale Kugel beruhren beispielsweise so dass ihre Mittelpunkte die Ecken eines Kuboktaeders bilden Man erkennt aber noch viel Leerraum zwischen den Kugeln und fragt sich ob eine dreizehnte Kugel hinzugefugt werden kann Dieses Problem war Thema eines beruhmten Streites zwischen Isaac Newton und dem Mathematiker David Gregory den diese 1692 uber die Keplerschen Vermutung fuhrten Newton behauptete das Maximum sei zwolf Gregory meinte es sei dreizehn Im 19 Jahrhundert erschienen die ersten Veroffentlichungen 1 2 3 die behaupteten den Beweis fur Newtons Behauptung zu enthalten Nach heutigen Standards wurden formelle Beweise jedoch erst 1953 von Kurt Schutte und Bartel Leendert van der Waerden 4 und 1956 von John Leech 5 erbracht n 4 Erst Anfang des 21 Jahrhunderts wurde bewiesen dass die Kusszahl fur die vierte Dimension 24 ist 6 n gt 4 Ferner sind die Kusszahlen fur die Dimensionen n 8 240 und n 24 196 560 bekannt im 24 dimensionalen Raum werden die Kugeln auf den Punkten des Leech Gitters platziert sodass kein Platz ubrig ist Die exakten Kusszahlen fur die Dimensionen 8 und 24 wurden 1979 unabhangig voneinander von Andrew M Odlyzko und Neil J A Sloane 7 bzw Vladimir Levenshtein 8 ermittelt Die folgende Tabelle gibt die bekannten Grenzen fur die Kusszahl bis zur Dimension 24 wieder 9 nbsp Die dritte Kusszahl ist 12 Die mittige Kugel rot wird von 6 Kugeln grun in gleicher Ebene 3 Kugeln gelb daruber und 3 Kugeln blau 60 gegen gelbe verdreht darunter beruhrt nbsp Das exponentielle Wachstum der Kusszahlen Dimensionen 1 bis 24 Die graue Flache ist durch die oberen und unteren Grenzen s Tabelle begrenzt Kusszahlen in den Dimensionen 1 24 10 Dimen sion Kusszahl Dimen sion KusszahluntereGrenze obereGrenze untereGrenze obereGrenze1 2 13 1154 11 20692 6 14 1606 11 31833 12 15 2564 48664 24 16 4320 73555 40 44 17 5346 11 0726 72 78 18 7398 16 5727 126 134 19 10 688 24 8128 240 20 17 400 36 7649 306 364 21 27 720 54 58410 500 554 22 49 896 82 34011 582 870 23 93 150 124 41612 840 1 357 24 196 560Schatzungen zeigen dass das Wachstum der Kusszahlen exponentiell ist vgl Graphik neben der Tabelle Die Basis des exponentiellen Wachstums ist unbekannt Uber die Kusszahlen in noch hoheren Dimensionen ist eher wenig bekannt untere Schranken sind etwa fur die Dimensionen n 32 276 032 n 36 438 872 n 40 991 792 n 44 2 948 552 n 64 331 737 984 und n 80 1 368 532 064 bekannt 12 Gitterkusszahlen in verschiedenen Dimensionen BearbeitenDie exakten Gitterkusszahlen sind fur die Dimensionen 1 bis 9 und 24 bekannt 13 14 Die folgende Tabelle gibt die Gitterkusszahlen bzw die bekannten unteren Grenzen bis zur Dimension 24 wieder Gitterkusszahlen in den Dimensionen 1 24 Dimension Gitterkusszahl Dimension Gitterkusszahl1 2 13 9182 6 14 14223 12 15 23404 24 16 43205 40 17 53466 72 18 73987 126 19 10 6688 240 20 17 4009 272 21 27 72010 336 22 49 89611 438 23 93 15012 a 756 24 b 196 560Die Gitterpackungen fur die Dimensionen 12 und 24 haben eigene Namen a Coxeter Todd Gitter 15 nach Harold Scott MacDonald Coxeter und John Arthur Todd b Leech Gitter 16 nach John Leech Berechnung BearbeitenWerden die Kugelradien auf 1 2 displaystyle 1 2 nbsp normiert und der Ursprung des Koordinatensystems in den Mittelpunkt der zentralen Kugel gelegt dann muss bei N displaystyle N nbsp kussenden Kugeln das folgende System von Ungleichungen erfullt sein displaystyle exists nbsp x displaystyle x Big nbsp displaystyle forall nbsp n x n 1 n m x n x m 1 displaystyle n x n 1 land forall n neq m x n x m geq 1 Big nbsp Dabei laufen m displaystyle m nbsp und n displaystyle n nbsp von 1 displaystyle 1 nbsp bis N displaystyle N nbsp und x x n n 1 N displaystyle x x n n in 1 dots N nbsp ist die Sequenz der Vektoren zu den N displaystyle N nbsp Kugelmittelpunkten a displaystyle a nbsp ist die Norm Lange des Vektors a displaystyle a nbsp 17 Aus Symmetriegrunden reicht es wenn der zweite Allquantor sich uber alle m displaystyle m nbsp n displaystyle n nbsp mit m lt n displaystyle m lt n nbsp erstreckt In einem D displaystyle D nbsp dimensionalen reellen Vektorraum R D displaystyle mathbb R D nbsp wird daraus nach Ubergang zu den Normquadraten in Matrixschreibweise x n x n T x n 1 m lt n x n x m T x n x m 1 displaystyle exists x Big forall n x n T x n 1 land forall m lt n x n x m T x n x m geq 1 Big nbsp Dabei sind die Vektoren x displaystyle x nbsp als Spaltenvektoren aufgefasst und x T displaystyle x T nbsp ist der entsprechende Zeilenvektor Transponierte Matrix a T b displaystyle a T b nbsp das Skalarprodukt Dieses System von Ungleichungen geht nach Umformung und Einfuhrung von Hilfsvariablen y m n displaystyle y mn nbsp 18 uber in das Gleichungssystem x y n 1 N x n T x n 1 2 m n N N m lt n x n x m T x n x m 1 y m n 2 2 0 displaystyle exists x y sum n 1 N x n T x n 1 2 sum begin smallmatrix m n in N times N m lt n end smallmatrix big x n x m T x n x m 1 y mn 2 big 2 0 nbsp Das obige Gleichungssystem hat insgesamt D N displaystyle D cdot N nbsp Gleichungen fur die N displaystyle N nbsp Vektoren x displaystyle x nbsp dazu kommen die Halfte 19 von N N 1 displaystyle N cdot N 1 nbsp fur die Matrix y displaystyle y nbsp insgesamt also D N N N 1 2 displaystyle D cdot N N cdot N 1 2 nbsp Gleichungen Wegen der relativen Grosse der zu testenden Zahl N displaystyle N nbsp der kussenden Kugeln stosst man schnell an die praktischen Grenzen der Berechenbarkeit Abschatzungen Die allgemeine Form der unteren Grenze fur n displaystyle n nbsp dimensionale Gitterkennzahlen ist gegeben durch h z n 2 n 1 displaystyle eta geq frac zeta n 2 n 1 nbsp 20 wobei z displaystyle zeta nbsp die Riemannsche Zeta Funktion ist Diese Grenze wird durch den Satz von Minkowski Hlawka nach Hermann Minkowski und Edmund Hlawka spezifiziert Siehe auch Bearbeitendichteste KugelpackungLiteratur BearbeitenFlorian Pfender Gunter M Ziegler Kissing Numbers Sphere Packings and Some Unexpected Proofs Notices of the American Mathematical Society S 873 883 PDF Eric W Weisstein Kissing Number In MathWorld englisch Christine Bachoc Frank Vallentin New upper bounds for kissing numbers from semidefinite programming In Journal of the American Mathematical Society Band 21 2008 S 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 eingeschrankte Online Version Google books Casselman zum Kissing Number Problem und seiner Geschichte Notices of the AMS 2004 Heft 8 PDF DateiWeblinks Bearbeiten nbsp Commons Kusszahl Sammlung von Bildern Videos und Audiodateien nbsp Wiktionary Kusszahl Bedeutungserklarungen Wortherkunft Synonyme UbersetzungenAnmerkungen und Referenzen Bearbeiten C Bender Bestimmung der grossten Anzahl gleich Kugeln welche sich auf eine Kugel von demselben Radius wie die Ubrigen auflegen lassen In Archiv Math Physik Grunert Band 56 1874 S 302 306 S Gunther Ein stereometrisches Problem In Archiv Math Physik Band 57 1875 S 209 215 R Hoppe Bemerkung der Redaction In Archiv Math Physik Grunert Band 56 1874 S 307 312 Schutte van der Waerden Das Problem der dreizehn Kugeln In Math Annalen Band 125 1953 S 325 334 Leech The Problem of Thirteen Spheres In The Mathematical Gazette Band 40 1956 S 22 23 Oleg R Musin The kissing number in four dimensions In Annals of Mathematics Vol 168 Nr 1 2008 S 1 32 arxiv math 0309430 Andrew M Odlyzko Neil J A Sloane New bounds on the number of unit spheres that can touch a unit sphere in n dimensions In J Combin Theory Ser A Band 26 1979 Nr 2 S 210 214 Vladimir I Levenshtein O granicah dlya upakovok v n mernom evklidovom prostranstve Nr 6 Dokl Akad Nauk SSSR 245 1979 S 1299 1303 Hans D Mittelmann Frank Vallentin High accuracy semidefinite programming bounds for kissing numbers arxiv 0902 1105 Folge A001116 in OEIS a b https www wolframalpha com input i kissingnumber Beweis von Zinov ev und Ericson Yves Edel E M Rains N J A Sloane On Kissing Numbers in Dimensions 32 to 128 In The Electronic Journal of Combinatorics Band 5 Heft 1 1998 John Horton Conway Neil J A Sloane The Kissing Number Problem und Bounds on Kissing Numbers In John Horton Conway Neil J A Sloane Sphere Packings Lattices and Groups 2 Auflage Springer Verlag New York 1993 S 21 24 und 337 339 ISBN 0 387 98585 9 Neil J A Sloane Gabriele Nebe Table of Highest Kissing Numbers Presently Known Eric W Weisstein Coxeter Todd Gitter In MathWorld englisch Eric W Weisstein Leech Gitter In MathWorld englisch Sergei Kucherenko et al New formulations for the Kissing Number Problem in Discrete Applied Mathematics Volume 155 Issue 14 1 September 2007 Seiten 1837 1841 doi 10 1016 j dam 2006 05 012 Der Autor arbeitet mit auf 1 normierten Kugelradien d h einer Hilfsmatrix y y m n N N displaystyle y y mn N times N nbsp von der nur die Koeffizienten mit m lt n displaystyle m lt n nbsp benotigt werden Insbesondere konnen die y n n displaystyle y nn nbsp auf 0 festgelegt werden und die Matrix wahlweise als symmetrisch antisymmetrisch oder als Dreiecksmatrix angenommen werden wegen Symmetrie Eric W Weisstein Minkowski Hlawka Theorem In MathWorld englisch Abgerufen von https de wikipedia org w index php title Kusszahl amp oldid 220766934