StartseiteMathlog

8-dimensionale Kugelpackungen

Von / 16. März 2016 / 8 Kommentare
Mehr

Was Früchteverkäufer seit Jahrhunderten wissen, hat endlich auch die Mathematik bewiesen: Platzsparender als bei den kunstvoll aufgetürmten Orangen-Pyramiden auf dem Wochenmarkt kann man Kugeln nicht aufeinanderschichten. schrieb die ZEIT vor 17 Jahren. Thomas Hales hatte 1998 die Kepler-Vermutung über die dichteste 3-dimensionale Kugelpackung bewiesen, mit umfangreichen und kaum nachprüfbaren Computerrechnungen, weshalb manche die Gültigkeit des Beweises anzweifelten. 2014 veröffentlichte er dann einen formalen, computerlesbaren und von HOL überprüften Beweis, wonach die Zweifler wohl verstummt sind.

Überraschenderweise scheint die 8-dimensionale Version der Kepler-Vermutung einen viel kürzeren Beweis zu haben. Eine gestern auf dem ArXiv erschienene Arbeit The sphere packing problem in dimension 8 beweist die Optimalitaüt der durch das E8-Gitter gegebenen 8-dimensionalen Kugelpackung auf nur 22 Seiten (von denen ein Teil expositorisch ist, z.B. erhält man nebenbei noch eine Einführung in die Theorie der Modulformen). Der Beweis baut noch auf einer älteren Arbeit von Cohn und Elkies auf, die aber auch nur 25 Seiten lang war. Neben der Kürze überrascht an dem Beweis vor allem die Methodik: wichtigstes Werkzeug im Beweis sind Modulformen, die sonst eigentlich in der Zahlenheorie ein unverzichtbares Werkzeug sind. (Beispielsweise beim Beweis des Satzes von Fermat, für den Andrew Wiles gestern den Abelpreis erhielt.)

Kugelpackungen

Beim Kugelpackungsproblem geht es darum, Kugeln vom Radius 1 so im Raum unterzubrigen, dass sie sich nicht schneiden (die Mittelpunkte sollen also Abstand mindestens 2 haben) und dass sie ein möglichst grosses Volumen überdecken. Weil das Volumen im Raum natürlich unendlich ist, formalisiert man letztere Zielstellung dadurch dass man für jedes r>0 den Anteil des überdeckten Volumens innerhalb der Umgebung vom Radius r um den Nullpunkt betrachtet und dann den Limes Superior dieses Anteils für r gegen unendlich.

In Dimension 2 ist die hexagonale Packung die dichteste, die optimale Dichte ist \frac{\pi}{\sqrt{12}}, bewiesen 1940 von Fejes Toth. In Dimension 3 hat Hales, wie gesagt, bewiesen dass die optimale Dichte \frac{\pi}{\sqrt{18}} ist. In höheren Dimensionen war bisher nichts bekannt, Viazovskas Arbeit liefert jetzt \frac{\pi^4}{384} in Dimension 8.

E8-Gitter

Das Schlagwort E8 wird vielen aus der Physik bekannt sein, nicht zuletzt durcㅗ die Ende der Nuller Jahre diskutierte Exceptionally Simple Theory of Everything, die die größte exzeptionelle Lie-Gruppe E8 benutzte. Die Lie-Algebra dieser Lie-Gruppe wird schematisch durch ein Dynkin-Diagramm beschrieben. Ihr Wurzelsystem sieht so aus:
image
Man kann dieses Diagramm als Gitter im 8-dimensionalen Raum realisieren, was sich natürlich nicht zeichnen läßt, aber durch eine einfache Formel beschreiben: \left\{(x_1,\ldots,x_8)\in {\mathbb Z}^8\cup({\mathbb Z}+\frac{1}{2})^8: x_1+\ldots+x_8 \equiv 0\ mod\ 2\right\}. Die 8-dimensionalen Kugeln vom Radius 1 um diese Gitterpunkte liefern eine Kugelpackung der Dichte \frac{\pi^4}{384} und man vermutete schon seit längerem, dass dies die optimale 8-dimensionale Kugelpackung sei.

Fourier-Transformation

Die Fourier-Transformation einer integrierbaren Funktion f\colon{\mathbb R}^n\to{\mathbb R} ist definiert als \widehat{f}(y)=\int_{{\mathbb R}^n}f(x)e^{-2\pi ix.y}dx für y\in{\mathbb R}^n, wobei x.y das Skalarprodukt bezeichnet. Cohn und Elkies hatten in einer 2003 in den Annals of Mathematics veröffentlichten Arbeit gezeigt, dass man mittels der Fourier-Transformation sogenannter “zulässiger Funktionen” obere Schranken für die Dichte von Kugelpackungen beweisen kann.

Die “zulässigen Funktionen” sind Funktionen, für die \mid f(x)\mid \le C(1+\mid x\mid)^{-n-\delta}, \mid\widehat{f}(y)\mid\le (1+\mid y\mid)^{-n-\delta} mit geeigneten Konstanten C und δ gilt. Für eine beliebige solche Funktion mit f(x)\le 0 für \mid x\mid \ge 1 und \widehat{f}(y)\ge 0 für alle y bewiesen Cohn und Elkies, dass \frac{f(0)}{\widehat{f}(0)}\frac{\pi^\frac{n}{2}}{2^n\Gamma(\frac{n}{2}+1)} eine obere Schranke für die Dichte jeder n-dimensionalen Kugelpackung liefert. Für n=8 gibt das die obere Schranke \frac{f(0)}{\widehat{f}(0)}\frac{1}{16}\frac{\pi^4}{384} und um die Optimalität des E8-Gitters zu beweisen muss man dann also “nur” noch eine den Ungleichungen genügende zulässige Funktion finden, für die \frac{f(0)}{\widehat{f}(0)}=16 ist.

Modulformen

Die Konstruktion einer solchen Funktion f benutzt verschiedene Modulformen, nämlich die j-Funktion j(z)=\frac{1728}{E_4(z)^3}{E_4(z)^3-E_6(z)^2} (E4 und E6 bezeichnen hier die Eisensteinreihen) und die Thetafunktionen \theta_{00}(z)=\sum_{n\in{\mathbb Z}}e^{\pi in^2z}, \theta_{01}(z)=\sum_{n\in{\mathbb Z}}(-1)^ne^{\pi in^2z}, \theta_{10}(z)=\sum_{n\in{\mathbb Z}}e^{\pi i(n+\frac{1}{2})^2z} .

Der Ausdruck für die gesuchte Funktion ist dann ziemlich kompliziert, er besteht aus 8 Summanden, die jeweils Integrale von verschiedenen Kombinationen dieser Funktionen sind, der fünfte Summand sieht beispielsweise so aus: \int_{-1}^i 128(\frac{\theta_{00}(z)^4+\theta_{01}(z)^4}{\theta_{10}(z)^8}+ \frac{\theta_{00}(z)^4+\theta_{10}(z)^4}{\theta_{01}(z)^8})e^{\pi i\parallel x\parallel^2z}dz, die anderen Summanden sind ähnlich kompliziert. Mittels der Symmetrieeigenschaften und der Abschätzungen für Fourierkoeffizienten von Modulformen wird in der neuen Arbeit letztlich bewiesen, dass die konstruierte Funktion f die gewünschten Eigenschaften hat und es also nach Cohn-Elkies keine dichteren Kugelpackungen als das E8-Gitter geben kann.

Maryna Viazovska (2016). The sphere packing problem in dimension 8 ArXiv arXiv: 1603.04246v1
Cohn, H., & Elkies, N. (2003). New upper bounds on sphere packings I Annals of Mathematics, 157 (2), 689-714 DOI: 10.4007/annals.2003.157.689

Stichworte: , , , ,
Mehr

Kommentare (8)

  1. #1 schlappohr
    16. März 2016

    “[…] und dass sie ein möglichst grosses Volumen überdecken.”

    Da habe ich gerade ein Verständnisproblem: Ist das überdeckte Volumen nicht allein durch die Anzahl der Kugeln gegeben? Und warum soll das Volumen möglichst groß sein? Ich dachte, das Ziel bei der Kugelpackung wäre es, das Volumen der kleinsten konvexen Hülle möglichst _klein_ zu bekommen.

  2. #2 Thilo
    16. März 2016

    Das Volumen aller Kugeln zusammengenommen ist natürlich unendlich. Es geht darum einen möglichst hohen prozentualen Anteil des gesamten Raumes überdeckt zu haben. Das wäre natürlich auch wieder unendlich durch unendlich geteilt. Für ein endliches Teilgebiet, etwa die Kugel vom Radius R um den Nullpunkt, kann man aber berechnen, wieviel Prozent überdeckt werden. Dann betrachtet man den Grenzwert dieser Prozentzahlen für R gegen unendlich. (Genauer den Limes Superior, weil die Folge nicht unbedingt konvergiert.) Um diesen Wert geht es.

  3. #3 schlappohr
    16. März 2016

    Ok, ich hatte das Bild mit den Orangen im Kopf und bin von einer endlichen Anzahl Kugel ausgegangen. Im unendlichen Fall ergibt das mit der Hülle natürlich keinen Sinn, weil die dann auch unendlich groß ist. Stattdessen soll die Kugeldichte soll maximal werden.
    Verstanden, danke.

  4. #4 Christian Berger
    20. März 2016

    Man kann die Anwendungen in der Quellcodierung schon fast riechen.

  5. #5 Thilo
    24. März 2016

    Nachtrag: mit analogen Methoden ist jetzt auch bewiesen worden, dass das Leech-Gitter die optimale 24-dimensionale Kugelpackung liefert: https://arxiv.org/pdf/1603.06518v1.pdf

  6. #6 Thilo
    10. Juli 2016

    A breakthrough in sphere packing: the search for magic functions https://arxiv.org/pdf/1607.02111v1.pdf

  7. #7 Thilo
    19. Januar 2017

    Und ein Artikel für das breitere mathematische Publikum in den Notices of the AMS: https://www.ams.org/journals/notices/201702/rnoti-p102.pdf