Kusszahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Geometrie ist die -te Kusszahl (auch Kontaktzahl) die maximale Anzahl an -dimensionalen Einheitskugeln, also Kugeln mit Radius 1, die gleichzeitig eine weitere solche Einheitskugel im euklidischen Raum berühren können, ohne dass Überschneidungen auftreten. Zusätzlich kann die Bedingung aufgestellt werden, dass die Mittelpunkte der Kugeln in einem Gitter liegen müssen (Gitterkusszahlen). Als Kusszahlenproblem ist das Fehlen einer allgemeinen Formel zur Berechnung der Kusszahlen bekannt.

Kusszahlen in verschiedenen Dimensionen[Bearbeiten | Quelltext bearbeiten]

Die Kusszahl für die erste Dimension ist 2.
Die Kusszahl für die zweite Dimension ist 6.

: In einer Dimension ist die Einheitskugel 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.

: In der zweiten Dimension ist die Einheitskugel 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.

12 Kugeln (blau) um eine weitere (rot), sodass alle diese berühren, ohne dass Überlappungen auftreten

: In der dritten Dimension ist die Berechnung 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). Dabei bleibt aber eine Menge Platz übrig, und es ist nicht offensichtlich, dass dieser Platz nicht ausreicht, um eine dreizehnte Kugel hinzuzufügen. Tatsächlich ist so viel Platz vorhanden, dass zwei beliebige Kugeln aus den zwölf äußeren ihre Plätze tauschen können, ohne den Kontakt zur zentralen Kugel zu verlieren. Dieses Problem war Thema einer berühmten Streitigkeit zwischen den Mathematikern Isaac Newton und David Gregory, die beide 1692 anlässlich einer Diskussion zur Keplerschen Vermutung führten. Newton behauptete, das Maximum sei zwölf, Gregory meinte, es sei dreizehn. Im 19. Jahrhundert erschienen die ersten Veröffentlichungen,[1][2][3] 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[4] und 1956 von John Leech[5] erbracht.

: Erst Anfang des 21. Jahrhunderts wurde bewiesen, dass die Kusszahl für die vierte Dimension 24 ist.[6]

: 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 von Andrew M. Odlyzko und Neil J. A. Sloane[7] bzw. Vladimir Levenshtein[8] ermittelt.

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

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–12[10]
Dimension Kusszahl
untere Grenze obere Grenze
1 2
2 6
3 12
4 24
5 40 44
6 72 78
7 126 134
8 240
9 306 364
10 500 554
11 582 870
12 840 1.357
Kusszahlen in den Dimensionen 13–24
Dimension Kusszahl
untere Grenze obere Grenze
13 1.154[11] 2.069
14 1.606[11] 3.183
15 2.564 4.866
16 4.320 7.355
17 5.346 11.072
18 7.398 16.572
19 10.688 24.812
20 17.400 36.764
21 27.720 54.584
22 49.896 82.340
23 93.150 124.416
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 (276.032), (438.872), (991.792), (2.948.552), (331.737.984) und (1.368.532.064) bekannt.[12]

Gitterkusszahlen in verschiedenen Dimensionen[Bearbeiten | Quelltext bearbeiten]

Die exakten Gitterkusszahlen sind für 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–12
Dimension Gitterkusszahl
1 2
2 6
3 12
4 24
5 40
6 72
7 126
8 240
9 272
10 ≥ 336
11 ≥ 438
12 a ≥ 756
Gitterkusszahlen in den Dimensionen 13–24
Dimension Gitterkusszahl
13 ≥ 918
14 ≥ 1.422
15 ≥ 2.340
16 ≥ 4.320
17 ≥ 5.346
18 ≥ 7.398
19 ≥ 10.668
20 ≥ 17.400
21 ≥ 27.720
22 ≥ 49.896
23 ≥ 93.150
24 b 196.560
Die Gitterpackungen für die Dimensionen 12 und 24 haben eigene Namen:
b Leech-Gitter[16] (nach John Leech)

Berechnung[Bearbeiten | Quelltext bearbeiten]

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

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

 .

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

.

Das obige Gleichungssystem hat insgesamt Gleichungen für die N Vektoren x, dazu kommen die Hälfte[19] von für die Matrix y; insgesamt also Gleichungen. Wegen der relativen Größe der zu testenden Zahl N 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

 ,[20]

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 | Quelltext bearbeiten]

Anmerkungen und Referenzen[Bearbeiten | Quelltext 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. a b https://www.wolframalpha.com/input/?i=kissingnumber Beweis von Zinov'ev und Eriscon
  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. http://www.research.att.com/~njas/lattices/kiss.html
  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 m < n 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).

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

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