Zum Inhalt springen

Kusszahl

aus Wikipedia, der freien Enzyklopädie

In der Geometrie ist die <math>n</math>-te Kusszahl (auch Kontaktzahl) die maximale Anzahl an <math>n</math>-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

Datei:Kissing-1d.svg
Die erste Kusszahl ist 2.
Datei:Kissing-2d.svg
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,<ref>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.</ref><ref>S. Günther: Ein stereometrisches Problem. In: Archiv Math. Physik. Band 57, 1875, S. 209–215.</ref><ref>R. Hoppe: Bemerkung der Redaction. In: Archiv Math. Physik. (Grunert) Band 56, 1874, S. 307–312</ref> 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<ref>Schütte, van der Waerden: Das Problem der dreizehn Kugeln. In: Math. Annalen. Band 125, 1953, S. 325–334.</ref> und 1956 von John Leech<ref>Leech: The Problem of Thirteen Spheres. In: The Mathematical Gazette. Band 40, 1956, S. 22–23</ref> erbracht.

Datei:12Kugeln berühren 1Kugel.jpg
Die dritte Kusszahl ist 12.
Die mittige rote Kugel wird von 6 grünen Kugeln in gleicher Ebene, 3 gelben Kugeln darüber und 3 um 60° gegen die gelben verdrehten blauen Kugeln darunter berührt.

n = 4:  Erst Anfang des 21. Jahrhunderts wurde bewiesen, dass die Kusszahl für die vierte Dimension 24 ist.<ref>{{#invoke:Vorlage:Literatur|f}}</ref>

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<ref>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</ref> bzw. Vladimir Levenshtein<ref>Vladimir I. Levenshtein: О границах для упаковок в n-мерном евклидовом пространстве. Nr. 6, Dokl. Akad. Nauk SSSR 245 1979. S. 1299–1303</ref> ermittelt.

Datei:Kissing growth.svg
Das exponentielle Wachstum der Kusszahlen; Dimensionen 1 bis 24. Die graue Fläche ist durch die oberen und unteren Grenzen (s. Tabelle) begrenzt.

Die folgende Tabelle gibt die bekannten Grenzen für die Kusszahl bis zur Dimension 24 wieder.<ref>Hans D. Mittelmann, Frank Vallentin: High accuracy semidefinite programming bounds for kissing numbers. Vorlage:ArXiv</ref>

Kusszahlen in den Dimensionen 1…24<ref>Folge A001116 in OEIS</ref>
Dimen-
sion		 Kusszahl Dimen-
sion		 Kusszahl
untere
Grenze		 obere
Grenze		 untere
Grenze		 obere
Grenze
1 2 13 1154<ref name="wolframalpha">https://www.wolframalpha.com/input/?i=kissingnumber Beweis von Zinov'ev und Ericson</ref> 2069
2 6 14 1606<ref name="wolframalpha" /> 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.<ref>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</ref>

Gitterkusszahlen in verschiedenen Dimensionen

Die exakten Gitterkusszahlen sind für die Dimensionen 1 bis 9 und 24 bekannt.<ref>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.</ref><ref>Neil J. A. Sloane, Gabriele Nebe: Table of Highest Kissing Numbers Presently Known.</ref>
Die folgende Tabelle gibt die Gitterkusszahlen bzw. die bekannten unteren Grenzen bis zur Dimension 24 wieder:

Dimen-
sion		 Gitter-
kusszahl 		Dimen-
sion		 Gitter-
kusszahl
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
0 | span | sup}} class="fussnoten-marke" data-annotationpair-m="{{#invoke:URLutil|anchorencode|1=a|2=1}}">{{#invoke:TemplUtl|nowiki1|a}}</{{#ifeq: | 0 | span | sup}}>{{#switch:0|10|11=|#default={{#invoke:TemplatePar|match 1=1=+ 2=SUP=n 3=gruppe=* template=Vorlage:FN cat=Wikipedia:Vorlagenfehler/Fußnoten

}}{{#switch: ERROR

{{#switch: Vorlage:Str match |[|] = ERROR |(Direkteingabe der Klammern)}} {{#switch: Vorlage:Str match |91|93 = ERROR |(HTML-Entität dezimal)}} {{#switch: Vorlage:Str match |5b|5d = ERROR |(HTML-Entität hexadezimal)}} {{#switch: Vorlage:Str match |lbrack|rbrack = ERROR |(benannte HTML-Entität)}}

=Vorlage:FN, Fehler in Parameter 1: Keine eckigen Klammern verwenden, das führt sonst zu Verwechslungen mit dem offiziellen MediaWiki-Belegsystem. }}}} 12 || ≥ 756 || <templatestyles src="FN/styles.css" /> <{{#ifeq: | 0 | span | sup}} class="fussnoten-marke" data-annotationpair-m="{{#invoke:URLutil|anchorencode|1=b|2=1}}">{{#invoke:TemplUtl|nowiki1|b}}</{{#ifeq: | 0 | span | sup}}>{{#switch:0|10|11=|#default={{#invoke:TemplatePar|match

1=1=+ 2=SUP=n 3=gruppe=* template=Vorlage:FN cat=Wikipedia:Vorlagenfehler/Fußnoten

}}{{#switch: ERROR

{{#switch: Vorlage:Str match |[|] = ERROR |(Direkteingabe der Klammern)}} {{#switch: Vorlage:Str match |91|93 = ERROR |(HTML-Entität dezimal)}} {{#switch: Vorlage:Str match |5b|5d = ERROR |(HTML-Entität hexadezimal)}} {{#switch: Vorlage:Str match |lbrack|rbrack = ERROR |(benannte HTML-Entität)}}

=Vorlage:FN, Fehler in Parameter 1: Keine eckigen Klammern verwenden, das führt sonst zu Verwechslungen mit dem offiziellen MediaWiki-Belegsystem. }}}} 24 || 196.560

<templatestyles src="FN/styles.css" />{{#switch:0|10|11=|#default= {{#if: Die Gitterpackungen für die Dimensionen 12 und 24 haben eigene Namen:

|1=1=+ |2=2=+ |3=3=* |4=gruppe=/^[^=%[%]%!]*$/ |5=floatfix=boolean |template=Vorlage:FNZ |cat=Wikipedia:Vorlagenfehler/Fußnoten }}{{#switch: ERROR 

 |{{#switch: Vorlage:Str match |[|] = ERROR |(Direkteingabe der Klammern)}}
 |{{#switch: Vorlage:Str match |91|93 = ERROR |(HTML-Entität dezimal)}}
 |{{#switch: Vorlage:Str match |5b|5d = ERROR |(HTML-Entität hexadezimal)}}
 |{{#switch: Vorlage:Str match |lbrack|rbrack = ERROR |(benannte HTML-Entität)}}

=Vorlage:FNZ, Fehler in Parameter 1: Keine eckigen Klammern verwenden, das führt sonst zu Verwechslungen mit dem offiziellen MediaWiki-Belegsystem. }}}}

  • <templatestyles src="FN/styles.css" />{{#if: ||
    }}<{{#if: |span|div}} class="fussnoten-inhalt references {{#if: ||{{#if: {{#invoke:TemplUtl|faculty|}}|fussnoten-floatfix}} }}">{{#invoke:TemplUtl|nowiki1|b}}{{#if: | | }}{{#ifeq: Leech-Gitter<ref>{{#if: | {{{author}}} | Eric W. Weisstein }}: Leech-Gitter. In: MathWorld (englisch). {{#if: LeechLattice | {{#ifeq: {{#property:P2812}} | LeechLattice | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref> (nach John Leech)|-||<{{#if: |span|div}} class="reference-text">Leech-Gitter<ref>{{#if: | {{{author}}} | Eric W. Weisstein }}: Leech-Gitter. In: MathWorld (englisch). {{#if: LeechLattice | {{#ifeq: {{#property:P2812}} | LeechLattice | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref> (nach John Leech)</{{#if: |span|div}}>}}</{{#if: |span|div></div}}>{{#switch:0|10|11=|#default={{#invoke:TemplatePar|match

|1=1=+ |2=2=+ |3=3=* |4=gruppe=/^[^=%[%]%!]*$/ |5=floatfix=boolean |template=Vorlage:FNZ |cat=Wikipedia:Vorlagenfehler/Fußnoten }}{{#switch: ERROR 

 |{{#switch: Vorlage:Str match |[|] = ERROR |(Direkteingabe der Klammern)}}
 |{{#switch: Vorlage:Str match |91|93 = ERROR |(HTML-Entität dezimal)}}
 |{{#switch: Vorlage:Str match |5b|5d = ERROR |(HTML-Entität hexadezimal)}}
 |{{#switch: Vorlage:Str match |lbrack|rbrack = ERROR |(benannte HTML-Entität)}}

=Vorlage:FNZ, Fehler in Parameter 1: Keine eckigen Klammern verwenden, das führt sonst zu Verwechslungen mit dem offiziellen MediaWiki-Belegsystem. }}}} | |Vorlage:FNBox, Parameter 1 leer oder nicht korrekt angegeben.

}}}}

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

|1=1=+ |2=2=+ |3=3=* |4=gruppe=/^[^=%[%]%!]*$/ |5=floatfix=boolean |template=Vorlage:FNZ |cat=Wikipedia:Vorlagenfehler/Fußnoten }}{{#switch: ERROR 

 |{{#switch: Vorlage:Str match |[|] = ERROR |(Direkteingabe der Klammern)}}
 |{{#switch: Vorlage:Str match |91|93 = ERROR |(HTML-Entität dezimal)}}
 |{{#switch: Vorlage:Str match |5b|5d = ERROR |(HTML-Entität hexadezimal)}}
 |{{#switch: Vorlage:Str match |lbrack|rbrack = ERROR |(benannte HTML-Entität)}}

=Vorlage:FNZ, Fehler in Parameter 1: Keine eckigen Klammern verwenden, das führt sonst zu Verwechslungen mit dem offiziellen MediaWiki-Belegsystem. }}}}

  • <templatestyles src="FN/styles.css" />{{#if: ||
    }}<{{#if: |span|div}} class="fussnoten-inhalt references {{#if: ||{{#if: {{#invoke:TemplUtl|faculty|}}|fussnoten-floatfix}} }}">{{#invoke:TemplUtl|nowiki1|b}}{{#if: | | }}{{#ifeq: Leech-Gitter<ref>{{#if: | {{{author}}} | Eric W. Weisstein }}: Leech-Gitter. In: MathWorld (englisch). {{#if: LeechLattice | {{#ifeq: {{#property:P2812}} | LeechLattice | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref> (nach John Leech)|-||<{{#if: |span|div}} class="reference-text">Leech-Gitter<ref>{{#if: | {{{author}}} | Eric W. Weisstein }}: Leech-Gitter. In: MathWorld (englisch). {{#if: LeechLattice | {{#ifeq: {{#property:P2812}} | LeechLattice | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref> (nach John Leech)</{{#if: |span|div}}>}}</{{#if: |span|div></div}}>{{#switch:0|10|11=|#default={{#invoke:TemplatePar|match

|1=1=+ |2=2=+ |3=3=* |4=gruppe=/^[^=%[%]%!]*$/ |5=floatfix=boolean |template=Vorlage:FNZ |cat=Wikipedia:Vorlagenfehler/Fußnoten }}{{#switch: ERROR 

 |{{#switch: Vorlage:Str match |[|] = ERROR |(Direkteingabe der Klammern)}}
 |{{#switch: Vorlage:Str match |91|93 = ERROR |(HTML-Entität dezimal)}}
 |{{#switch: Vorlage:Str match |5b|5d = ERROR |(HTML-Entität hexadezimal)}}
 |{{#switch: Vorlage:Str match |lbrack|rbrack = ERROR |(benannte HTML-Entität)}}

=Vorlage:FNZ, Fehler in Parameter 1: Keine eckigen Klammern verwenden, das führt sonst zu Verwechslungen mit dem offiziellen MediaWiki-Belegsystem. }}}}

Berechnung

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

<math>\exist</math> <math>x \Big(</math><math>\forall</math> <math>n: ||x_n||=1 \land \forall n\neq m : ||x_n-x_m|| \ge 1\Big)</math>

Dabei laufen <math>m</math> und <math>n</math> von <math>1</math> bis <math>N</math> und <math>x = (x_n)_{n \in \{1\dots{N}\}}</math> ist die Sequenz der Vektoren zu den <math>N</math> Kugelmittelpunkten, <math>||a||</math> ist die Norm (Länge) des Vektors <math>a</math>.<ref>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.</ref> Aus Symmetriegründen reicht es, wenn der zweite Allquantor sich über alle <math>m</math>, <math>n</math> mit <math>m < n</math> erstreckt.
In einem <math>D</math>-dimensionalen reellen Vektorraum <math>\R^D</math> wird daraus nach Übergang zu den Normquadraten in Matrixschreibweise

<math>\exist x \Big(\forall n: {x_n}^Tx_n=1 \land \forall m<n : (x_n-x_m)^T(x_n-x_m) \ge 1\Big)</math> .

Dabei sind die Vektoren <math>x</math> als Spaltenvektoren aufgefasst, und <math>x^T</math> ist der entsprechende Zeilenvektor (Transponierte Matrix), <math>a^T\!b</math> das Skalarprodukt. Dieses System von Ungleichungen geht nach Umformung und Einführung von Hilfsvariablen <math>y_{m n}</math><ref>d. h. einer Hilfsmatrix <math>y = (y_{m n})_{N\times{N}}</math>, von der nur die Koeffizienten mit <math>m < n</math> benötigt werden. Insbesondere können die <math>y_{nn}</math> auf 0 festgelegt werden, und die Matrix wahlweise als symmetrisch, antisymmetrisch oder als Dreiecksmatrix angenommen werden.</ref> über in das Gleichungssystem

<math>\exist x,y: \sum_{n=1}^N ({x_n}^Tx_n -1)^2 + \sum_{\begin{smallmatrix}(m,n)\in{N}\times{N}\\m<n\end{smallmatrix}} \big((x_n-x_m)^T(x_n-x_m)-1-{y_{mn}}^2\big)^2 = 0</math>.

Das obige Gleichungssystem hat insgesamt <math>D\!\cdot\!{N}</math> Gleichungen für die <math>N</math> Vektoren <math>x</math>, dazu kommen die Hälfte<ref>wegen Symmetrie</ref> von <math>N\!\cdot\!(N\!-\!1)</math> für die Matrix <math>y</math>; insgesamt also <math>D\!\cdot\!{N} + N\!\cdot\!(N\!-\!1)/2</math> Gleichungen. Wegen der relativen Größe der zu testenden Zahl <math>N</math> der küssenden Kugeln stößt man schnell an die praktischen Grenzen der Berechenbarkeit.

Abschätzungen
Die allgemeine Form der unteren Grenze für <math>n</math>-dimensionale Gitterkennzahlen ist gegeben durch

<math>\eta \geq \frac{\zeta(n)}{2^{n-1}}</math> ,<ref>{{#if: | {{{author}}} | Eric W. Weisstein }}: Minkowski-Hlawka Theorem. In: MathWorld (englisch). {{#if: Minkowski-HlawkaTheorem | {{#ifeq: {{#property:P2812}} | Minkowski-HlawkaTheorem | | {{#if: {{#property:P2812}} | {{#ifeq: 0 | 0 | }} | {{#ifeq: 0 | 0 | }} }} }} }}</ref>

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

Siehe auch

Literatur

Weblinks

[{{canonicalurl:Commons:Category:{{#if:Kissing number problem|Kissing number problem|Kusszahl}}|uselang=de}} Commons: {{#if:Kusszahl|Kusszahl|{{#if:Kissing number problem|Kissing number problem|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|X|x= |0|-= |S|s= – Sammlung von Bildern |1|= – Sammlung von Bildern{{#if: 

    | {{#switch: {{#invoke:TemplUtl|faculty|1}}/{{#invoke:TemplUtl|faculty|1}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default= – }}{{#if: Kissing number problem 

   | {{#ifeq: {{#invoke:Str|left|kissing number problem|9}} 
       | category:
| FEHLER: Ohne Category: angeben!}}}}

Vorlage:Wikidata-Registrierung

[[wikt:{{#if:|{{{lang}}}:}}{{#if:|{{{1}}}|{{#invoke:WLink|getArticleBase}}}}|Wiktionary: {{#if:|{{{2}}}|{{#if:|{{{1}}}|{{#invoke:WLink|getArticleBase}}}}}}]]{{#switch: 1

|1|= – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen |0|-= |X|x= |#default= –

}}{{#if:| {{#ifeq: {{{lang}}} | de | {{#ifeq: 0 | 0 | }} | ({{#invoke:Multilingual|format|{{{lang}}}|slang=!|shift=m}}) }}}}

{{#invoke:TemplatePar|check 

  |opt= 1= 2= lang= suffix=
  |template=Vorlage:Wiktionary
  |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt
  }}

Anmerkungen und Referenzen

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Kusszahl&oldid=511117“