🔢 mathematics

A dual linear programming bound for sphere packing in dimension 36

Diese Arbeit konstruiert einen expliziten dual-zulässigen Punkt für das Cohn-Elkies-Lineare-Programm in Dimension 36 und beweist damit, dass die theoretische obere Schranke für die Kugelpackungsdichte die beste bekannte Packung (Kschischang-Pasupathy) um mindestens den Faktor 32,91 übersteigt, wodurch demonstriert wird, dass die derzeit beste bekannte Packung nicht optimal ist, und erstmals duale Schranken für Dimensionen über 32 erweitert werden.

Ursprüngliche Autoren: Rifat Jumagulov

Veröffentlicht 2026-07-14

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Rifat Jumagulov

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, so viele identische, unsichtbare Ballons wie möglich in einen riesigen, 36-dimensionalen Raum zu packen, ohne dass sie sich überschneiden. Dies ist das Problem der „Kugelpackung“ (Sphere Packing). Jahrzehntelang haben Mathematiker versucht, die absolut dichteste Methode dafür zu finden, aber in den meisten Dimensionen haben sie nur eine „beste Vermutung“ (den aktuellen Rekord) und eine „theoretische Decke“ (das durch die Mathematik erlaubte absolute Limit).

In den Dimensionen 8 und 24 wissen wir, dass die Decke und der Boden sich berühren; die beste Vermutung ist bewiesen perfekt. Aber in Dimension 36 existierte immer eine Lücke. Die Arbeit von Rifat Jumagulov fungiert wie ein superpräzises Lineal, das diese Lücke misst und etwas Überraschendes beweist: Die aktuelle beste Vermutung ist weit entfernt vom theoretischen Limit.

Der „Magische Spiegel“-Test

Um das theoretische Limit zu finden, verwenden Mathematiker ein Werkzeug namens Cohn–Elkies-Lineares Programm. Stellen Sie sich dieses Programm als einen „magischen Spiegel“ vor, der eine vorgeschlagene Packungsanordnung reflektiert. Wenn die Anordnung wirklich die beste ist, sollte der Spiegel eine perfekte Reflexion zeigen. Wenn der Spiegel einen Fehler zeigt, ist die Anordnung nicht die beste.

Lange Zeit wurde die am besten bekannte Packung in 36 Dimensionen (die Kschischang–Pasupathy-Packung) als starker Anwärter angesehen. Die Arbeit konstruiert ein spezifisches „duales“ Objekt – eine komplexe mathematische Form, die aus Modulformen aufgebaut ist (welche wie komplizierte, sich wiederholende Muster in der Welt der komplexen Zahlen funktionieren) – um als dieser Spiegel zu dienen.

Die große Enthüllung

Wenn der Autor diesen neuen Spiegel auf die Kschischang–Pasupathy-Packung richtet, ist die Reflexion nicht nur ein wenig daneben; sie ist völlig anders. Die Mathematik beweist, dass das theoretische Limit für 36 Dimensionen mindestens 32,91-mal dichter ist als die derzeit beste bekannte Packung.

Um dies einzuordnen: Wenn die aktuelle beste Packung eine spärliche Streuung von Murmeln auf einem Boden wäre, legt das theoretische Limit nahe, dass man über 32-mal so viele Murmeln in denselben Raum passen könnte, ohne dass sie sich berühren. Die Arbeit schließt explizit die Idee aus, dass die Cohn–Elkies-Methode jemals beweisen könnte, dass der aktuelle Rekord optimal ist. Die Lücke ist einfach zu groß.

Wie sie es geschafft haben: Die „Cut-and-Run“-Strategie

Den Bau dieses Spiegels zu vollziehen, war nicht einfach. Der Autor musste ein massives Puzzle lösen, das aus 72 verschiedenen mathematischen Zutaten bestand.

Die Falle: Als der Autor versuchte, das Puzzle mit Standard-Computermathematik (Gleitkommazahlen) zu lösen, wurde der Computer verwirrt und lieferte eine „Geisterantwort“, die gut aussah, aber eigentlich fehlerhaft war.
Die Lösung: Der Autor verwendete „exakte rationale Arithmetik“, was so ist, als würde man mit perfekten Brüchen statt mit unordentlichen Dezimalzahlen rechnen. Er nutzte eine „Schnittebenen-Methode“ (Cutting-Plane-Method): Er löste eine kleinere Version des Puzzles, fand heraus, wo die Antwort gegen die Regeln verstieß, schnitt diesen schlechten Teil heraus und löste es erneut. Es dauerte nur eine einzige Runde des Schneidens, um die perfekte, exakte Lösung zu finden.

Das „Tail“-Problem (Der Schwanz-Effekt)

Der schwierigste Teil war der Beweis, dass die mathematische Form bis zur Unendlichkeit positiv bleibt (nicht negativ wird). Die Form besteht aus zwei Teilen: einem vorhersagbaren „Hauptkörper“ und einem wackeligen „Schwanz“ (Tail).

Der Hauptkörper ist riesig und positiv.
Der Schwanz ist winzig und wackelig.
Der Autor musste beweisen, dass der Hauptkörper so stark ist, dass er den wackeligen Schwanz immer überlagert.

Normalerweise verwenden Mathematiker eine Standard-Sicherheitsmarge, um dies zu beweisen. Aber in Dimension 36 war die Standardmarge zu locker; sie wäre haarscharf gescheitert. Der Autor erfand eine „Lift-bewusste“ Sicherheitsmarge – einen intelligenteren Weg, den wackeligen Schwanz zu messen, der berücksichtigt, wie die mathematischen Teile gestapelt sind. Diese neue Marge war 10 Milliarden Mal präziser als die alte, was es ermöglichte, die Lücke mit einem massiven Sicherheitsbuffer zu schließen.

Was dies bedeutet (und was es nicht bedeutet)

Die Arbeit ist ein rigoröser Beweis, keine Simulation oder Vermutung. Jede Zahl wurde mit exakter Arithmetik überprüft, und der Code ist verfügbar, damit jeder ihn verifizieren kann.

Die Arbeit stellt jedoch auch klar, was sie nicht getan hat. Sie findet nicht die neue, dichtere Packung, die in diese 32,91-mal größere Lücke passt. Sie beweist lediglich, dass der aktuelle Rekord weit vom Limit entfernt ist. Das Finden der tatsächlichen dichteren Packung bleibt ein Mysterium. Der Autor merkt an, dass, obwohl die Lücke riesig ist, der Beweis, dass das theoretische Limit tatsächlich höher als die wahre optimale Dichte ist (starke Nicht-Schärfe), derzeit unmöglich ist, da uns die Werkzeuge fehlen, um ein so niedriges oberes Limit zu berechnen.

Kurz gesagt: Die Arbeit zieht den Vorhang beiseite, um zu zeigen, dass die „bekannteste“ Packung in 36 Dimensionen noch weit vom Ziel entfernt ist und kein Maß an Verfeinerung der aktuellen Methode beweisen kann, dass sie der Gewinner ist. Das Rennen ist weit offen, und die Ziellinie ist viel weiter entfernt, als man zuvor gedacht hatte.

Technisches Resümee: Eine duale lineare Programmierungs-Schranke für die Kugelpackung in Dimension 36

Problemstellung
Die vorliegende Arbeit befasst sich mit dem Kugelpackungsproblem in der Dimension $d=36$ , wobei der Schwerpunkt auf der Cohn–Elkies-Schranke für lineare Programmierung (LP) liegt. Während die LP-Schranke in den Dimensionen 8 und 24 bekannt als scharf gilt, bleibt ihre Schärfe in allen anderen Dimensionen eine offene Frage. Der Autor untersucht, ob die Cohn–Elkies-Schranke, bezeichnet als $\delta_{LP}(d)$ , die optimale Dichte der derzeit besten bekannten Packung, $\delta^*(d)$ , zertifizieren kann. In Dimension 36 ist die beste bekannte Packung die Kschischang–Pasupathy-Konfiguration mit einer Zenterdichte von $2^{18}/3^{10}$ . Das Ziel besteht darin, einen „dual-zulässigen Punkt“ (eine spezifische Hilfsfunktion) zu konstruieren, der eine untere Schranke für $\delta_{LP}(36)$ liefert, die strikt größer ist als die Dichte der Kschischang–Pasupathy-Packung. Ein Erfolg würde beweisen, dass keine Cohn–Elkies-Funktion die bekannte Packung als optimal zertifizieren kann.

Methodik
Die Konstruktion folgt der Methode von Cohn und Triantafillou unter Verwendung des Raums der Gewicht-18 Modulformen für die Kongruenzuntergruppe $\Gamma_0(24)$ . Der Kern der Methode besteht darin, ein Paar von Modulformen $(g, \tilde{g})$ des Gewichts $k=18$ (wobei $k=d/2$ ) zu finden, das spezifische Koeffizientenbeschränkungen erfüllt, um eine gültige Verteilung für die LP-Schranke zu erzeugen.

Das Paper beschreibt zwei kritische methodische Innovationen, die erforderlich waren, um dieses Problem in Dimension 36 zu lösen, wo bisherige Methoden (die erfolgreich in Dimensionen bis 32 waren) auf numerische und theoretische Hindernisse stießen:

Constraint-Generation (Schnittmengenverfahren-Formulierung):
Eine naive lineare Programmierungsrelaxation, die lediglich die Nichtnegativität der Koeffizienten bis zu einem endlichen $n$ erzwingt, produzierte ein Optimum, das unmittelbar nach dem erzwungenen Bereich negativ wurde (speziell für $n \equiv 3, 9, 15, 21 \pmod{24}$ ). Umgekehrt war ein vollständig beschränktes Problem mit Hunderten von Zeilen für Floating-Point-Solver numerisch singulär und zu groß für exakte dichte Simplex-Verfahren.
- Lösung: Der Autor verwendet einen Constraint-Generation-Ansatz. Ein exaktes rationales LP wird auf einem kleinen Arbeitssatz gelöst. Verletzte Zeilen (in denen die Koeffizienten negativ sind) werden exakt identifiziert, dem Beschränkungssatz hinzugefügt und das LP wird neu gelöst. In Dimension 36 konvergierte dieser Prozess in einer einzigen Runde und lieferte einen exakten rationalen Eckpunkt, dessen $q$ -Entwicklungen weit über den erzwungenen Bereich hinaus nicht-negativ bleiben.
Lift-bewusste Deligne-Konstante:
Der Beweis der „schließlichen Positivität“ (dass Koeffizienten für alle $n > n_0$ nicht-negativ bleiben) erfordert die Begrenzung des cusp-Teils der Modulformen. Die Standard-Deligne-Schranke verwendet eine $\ell_1$ -Norm der Koordinaten in der Newform-Lift-Basis.
- Lösung: Der Autor stellt fest, dass die naive $\ell_1$ -Norm in diesem Kontext „verlustreich“ ist, da das Zertifikat von einem einzelnen tiefen Oldform-Lift (der Level-Eins Newform verschoben um $e=24$ ) dominiert wird. Die naive Konstante verfehlte den Verifizierungsschwellenwert geringfügig. Der Autor führt eine „lift-bewusste“ Konstante $C_w = \sum_{f,e} |\lambda_{f,e}| e^{-(k-1)/2}$ ein, welche den Beitrag tiefer Lifte durch den Faktor $e^{-(k-1)/2}$ unterdrückt. Diese verfeinerte Konstante ist um zehn Größenordnungen kleiner, wodurch die Verifizierung mit einer signifikanten Marge abgeschlossen werden konnte.

Wichtigste Ergebnisse
Das Paper konstruiert einen expliziten dual-zulässigen Punkt $(g, \tilde{g})$ und leitet die folgenden Ergebnisse ab:

Duale Schranke: Das konstruierte Zertifikat stellt fest, dass die Cohn–Elkies-Schranke für lineare Programmierung in Dimension 36 die folgende Bedingung erfüllt:
$\delta_{LP}(36) \geq 146.1036\dots = 32.9104\dots \times \frac{2^{18}}{3^{10}}$
Vergleich zur bekannten Packung: Diese untere Schranke übersteigt die Dichte der Kschischang–Pasupathy-Packung ( $2^{18}/3^{10}$ ) um den Faktor von mindestens 32,91.
Implikation: Folglich kann keine Cohn–Elkies-Hilfsfunktion die Kschischang–Pasupathy-Packung in Dimension 36 als optimal zertifizieren. Die LP-Schranke ist strikt höher als die Dichte der besten bekannten Packung.
Rigorosität der Verifizierung: Das Zertifikat ist exakt. Der duale Punkt ist ein rationaler Vektor mit ca. 128-stelligen Zählern. Die Nichtnegativität der Koeffizienten wird durch exakte Arithmetik bis $n=800$ verifiziert. Für $n > 800$ wird die schließliche Positivität unter Verwendung der lift-bewussten Deligne-Konstante und expliziter Tail-Bounds bewiesen, wobei alle Konstanten mittels Outward-Rounded-Intervallarithmetik zertifiziert wurden.

Bedeutung und Ansprüche
Das Paper beansprucht mehrere signifikante Beiträge zum Feld der Kugelpackungen und Modulformen:

Erweiterung bekannter Schranken: Dies ist die erste duale Schranke, die in einer Dimension über 32 konstruiert wurde. Es erweitert die bestehende Tabelle von Cohn und Triantafillou (die $d=12, 16, 20, 28, 32$ abdeckte), Li ( $3 \le d \le 13$ ) und de Courcy-Ireland et al. ( $d=6$ ).
Methodischer Fortschritt: Das Paper hebt hervor, dass die Constraint-Generation-Formulierung essenziell ist, um die tail-safe Optima in hohen Dimensionen zu erreichen, in denen exakte dichte LPs unpraktikabel sind. Zudem zeigt es, dass die lift-bewusste Deligne-Konstante für die rigorose Verifizierung in Fällen notwendig ist, die von tiefen Oldform-Liften dominiert werden – ein Szenario, in dem Standard-Schranken versagen.
Natur des Ergebnisses: Der Autor merkt an, dass während die duale Aussage stark ist (die Lücke ist groß), die „strikte Nicht-Schärfe“ (der Beweis von $\delta_{LP}(36) > \delta_{max}(36)$ , wobei $\delta_{max}$ die wahre optimale Dichte ist) außerhalb der Reichweite liegt. Eine strikte Nicht-Schärfe würde eine unabhängige obere Schranke unterhalb von $32,91 \times \delta^*$ erfordern, ein Schwellenwert, der mit bestehenden Drei-Punkt-Schranken-Techniken derzeit nicht erreichbar ist.
Reproduzierbarkeit: Die Arbeit betont, dass die Verifizierung ausschließlich auf exakter rationaler Linearantwort und Intervallarithmetik beruht, unabhängig von Computer-Algebra-Systemen mit Modulform-Mechanismen. Alle Codes, Belege und exakten Daten werden als ergänzende Dateien bereitgestellt.

Das Paper schließt mit der Feststellung, dass die Dimension 36 ein qualitativ anderes Regime darstellt, in dem die bekannte Rekordpackung im Verhältnis zur LP-Schranke schwach ist, was die duale Aussage stark, aber die Frage der strikten Optimalität jedoch schwieriger macht.