Neuer Rekord beim Kugelpacken aus unerwarteter Quelle

• Boaz Klartag führte im Gegensatz zu bisherigen Ansätzen Werkzeuge der konvexen Geometrie in das Problem des Kugelpackens in sehr hohen Dimensionen ein
• Klartags neue zufallsbasierte Methode erzeugt Ellipsoide mit größerem Volumen und übertrifft damit den bisherigen Rekord deutlich
• Dieser Ansatz ermöglicht es, dramatisch mehr Kugeln in hochdimensionalen Räumen zu packen
• Das Ergebnis belebt die Debatte über die Bedeutung von Ordnung und Symmetrie beim Packen neu
• Die Forschung erregt Aufmerksamkeit wegen möglicher Anwendungen in Bereichen wie Kryptografie und Kommunikation

---

Frühere Forschung zum Kugelpacken und ihre Grenzen

• Ein Vorteil der früheren Rogers-Methode war, dass das Ausgangsgitter nicht unbedingt effizient sein musste, solange man nur ein geeignetes Ellipsoid auswählte
• Allerdings können die Achsen eines Ellipsoids in hohen Dimensionen auf viele Arten verändert werden, sodass es zu viele Möglichkeiten gab, welche Form man wachsen lassen sollte
• Später kehrten Mathematiker zur Minkowski-Methode zurück, konzentrierten sich auf das Gitter selbst, spezialisierten sich auf Gittertheorie und entfernten sich von Rogers’ geometriezentriertem Ansatz
• Diese Strategie brachte schrittweise Verbesserungen beim Kugelpacken in hohen Dimensionen, führte gegenüber Rogers’ Methode aber nur zu geringfügigen Effizienzgewinnen
• Über Jahrzehnte gab es keinen großen Sprung, und die Entwicklung stagnierte

Eine Innovation aus externer Perspektive

• Boaz Klartag vom Weizmann Institute of Science ist ursprünglich kein Gittertheoretiker, sondern Spezialist für konvexe Geometrie
• Er interessierte sich schon lange für das Problem des Kugelpackens, hatte aber keine Gelegenheit, daran zu forschen
• Als er 2023 neue zeitliche Freiräume bekam, veranstaltete er mit Barak Weiss von der Tel Aviv University ein Seminar und untersuchte intensiv die klassische Literatur (Minkowski, Rogers)
• Klartag kam zu dem Schluss, dass Rogers’ Ellipsoid-Methode ineffizient gewesen sei, weil es an Know-how bei der Manipulation konvexer Körper fehlte
• Er war überzeugt, dass sich mit effizienteren Ellipsoiden ein neuer Rekord beim Kugelpacken erzielen ließe

Einführung eines zufallsbasierten Wachstumsalgorithmus

• Klartag wandte eine eigene Methode an, bei der die Grenze des Ellipsoids entlang jeder Achsenrichtung zufällig expandiert oder kontrahiert wird
• Wenn die Grenze einen Gitterpunkt berührt, stoppt das Wachstum in dieser Richtung, während es in anderen Richtungen weitergeht
• Dabei erkundet das Ellipsoid den Raum in unregelmäßiger Form und wird allmählich größer
• Da die zufallsbasierte Natur dazu führt, dass die erzeugten Ellipsoide jeweils unterschiedliche Volumina haben, führte er viele Versuche durch, um die Möglichkeit noch größerer Ellipsoide zu bewerten
• Innerhalb weniger Wochen bewies er, dass sich größere Ellipsoide als bei Rogers erzeugen lassen

Neuer Rekord und Auswirkungen

• Die neue Ellipsoid-Methode erreicht seit Rogers (1947) die größte Verbesserung der Effizienz beim Kugelpacken
• In Dimension d ermöglicht sie es, d-mal mehr Kugeln zu packen als der vorherige Ansatz
  • 100 Dimensionen → etwa 100-mal mehr, 1.000.000 Dimensionen → etwa 1.000.000-mal mehr Kugelpackung
• Mit Einsichten aus der konvexen Geometrie durchbrach Klartag innerhalb weniger Monate einige langjährige zentrale Probleme zu Gittern und Kugelpackung
• Sein Erfolg rückt erneut die Ansicht in den Vordergrund, dass auf Ordnung und Symmetrie basierende Packungen die dichtesten Packungen erreichen können
• Demgegenüber konkurrieren in jüngerer Zeit auch Forschungen, die behaupten, man müsse Unordnung statt regelmäßiger Gitter nutzen

Bewertung und Ausblick

• Innerhalb der Fachwelt gibt es derzeit eine Debatte darüber, ob Klartags Packungsmethode dem wirklichen Optimum nahekommt oder ob noch Spielraum für weitere Verbesserungen besteht
• Die Antwort auf diese Frage ist auch für praktische Anwendungen wie Kryptografie und Nachrichtentechnik von großer Bedeutung
• Noch ist sie nicht in der praktischen Anwendung angekommen, wird aber in Ingenieurkreisen bereits als neue Technologie aufmerksam verfolgt
• Klartag hofft, dass dieses Ergebnis die Verbindung zwischen konvexer Geometrie und Gittertheorie stärkt
• Er wünscht sich, dass die Trennung zwischen den beiden Feldern überwunden wird und diese Verbindung sich auch auf die Lösung von Gitterproblemen jenseits des Kugelpackens ausweitet

[GN⁺]

Hacker-News-Kommentare

• Das Geständnis, dass es immer schwer ist, den Eltern zu erklären, dass der eigene Beruf wirklich existiert; besonders unangenehm wird es, wenn man sagen muss: „Ich erforsche geometrische Formen, aber nur solche ohne Einbuchtungen.“
  • Aus meiner Erfahrung ist es am besten, den Beruf mit schwer verständlichem Fachjargon zu erklären. Im Grunde gibt es drei Möglichkeiten: Gibt man eine relativ einfache Erklärung, die die Eltern verstehen könnten, wirkt die Arbeit zu leicht und man bekommt die Reaktion „Dafür wirst du wirklich bezahlt?“. Erklärt man richtig, warum es wichtig ist, wird die Erklärung zu lang, die Eltern werden ungeduldig und bereuen, überhaupt gefragt zu haben. Oder man sagt es kurz mit komplizierten Fachbegriffen; dann versteht zwar niemand, worum es geht, aber es klingt irgendwie beeindruckend. Das ist noch die beste Option.
  • Ich betreibe ein Mikro-Business, das Bauteile für Geräte der Hochenergiephysik herstellt, und wenn ich anderen meine Arbeit erkläre, finde ich noch immer keinen guten Weg, weil das Thema extrem fremdartig, nischig und mehrere Stufen von allem entfernt ist, womit die meisten Menschen im Alltag je Berührung hatten.
  • Ich sage einfach nur: „Ich arbeite mit Computern“, und dann kommt bequem die Antwort „Ah, ja, guter Job“ und das Gespräch ist beendet.
  • Für mich ist weniger die Frage „Was machst du beruflich?“ schwierig als die Anschlussfrage „Wozu ist das nützlich / wofür wird das verwendet?“. Es ist immer schwer, die lange Kette von der Grundlagenforschung bis zur tatsächlichen Anwendung kurz und wirkungsvoll zu erklären.
  • Immerhin ist sphere packing eng mit Kernproblemen der Informationstheorie verbunden, und darin liegt auch ein historischer Kontext und eine wichtige Bedeutung, weil es letztlich mit der höheren Zuverlässigkeit des Bell-Systems zusammenhängt. (Bei konvexen Körpern weiß ich das nicht so genau.)
• Jemand berichtet von Erfahrungen damit, Verfahren zum Packen von Kugeln (sphere packing) für einen Kompressionsalgorithmus für Vektordaten zu nutzen; der theoretische Ansatz funktionierte nur dann gut, wenn die Daten sehr gleichmäßig waren, und ließ sich auf reale Daten nur schwer anwenden.
  • Um unstrukturierte (nicht gleichmäßige) Daten in gleichmäßigere Daten zu überführen, ist der übliche Trick, Domänenwissen zu nutzen, um Asymmetrien zu verringern. Zum Beispiel kann man ausnutzen, dass Daten selbst bei hochdimensionaler Struktur lokal durch Rauschen oft ziemlich gleichmäßig werden. Berechnet und speichert man Zentroiden, werden diese gleichmäßiger, und man kann jeden Vektor getrennt als Zentroid-Index und Vektor-Offset speichern. Die Indizes eignen sich für effiziente Entropiekompression, und die Offsets sind nun fast gleichmäßig, sodass sich die bestehende sphere-packing-Strategie leichter anwenden lässt.
  • Wurde vermutlich schon ausprobiert, aber man könnte prüfen, ob sich durch Vorkompression die Sparsity der Vektoren verringern und so die Gleichförmigkeit erhöhen lässt.
  • Der scherzhafte Hinweis, dass man vorsichtig sein sollte, wenn man echte Vektoren „groped“ — also „betastet“ —, wobei das wohl ein Tippfehler von group war.
  • Hinweis darauf, dass der theoretische Rahmen auf praktischere Aufgaben — also nicht homogene Daten — ausgeweitet werden sollte. Wenn reale Anwendungsfälle zu vielfältig sind, ist ein allgemeiner Ansatz vielleicht schwierig, aber trotzdem lohnt es sich, diese Erweiterung zu verfolgen.
  • Der Hinweis, dass in alten kommerziell wichtigen Bereichen die leicht erreichbaren Erfolge, also die low-hanging fruits, meist schon geerntet wurden.
• Zustimmung zu Klartags Aussage, dass „konvexe Körper sehr mächtig und äußerst nützlich sind“. Zwar sei man kein Mathematiker, habe aber oft erlebt, dass Convex-Hull-Algorithmen an unerwarteten Stellen in ganz unterschiedlichen Problemen auftauchen, besonders bei der automatischen Palettenzerlegung in Bildern; dazu ein Link auf das Paper Convex Hull and automatic palette decomposition
• Verwunderung darüber, dass Klartags neue sphere-packing-Methode im Vergleich zum bisherigen Stand in Dimension d offenbar d-mal so viele Kugeln packen kann: also in 100 Dimensionen 100-mal mehr, in einer Million Dimensionen sogar eine Million Mal mehr. Die Frage ist, ob das in verschiedenen Kommunikationssystemen tatsächlich Dutzende bis Hunderte Male mehr Bandbreite oder deutlich geringeren Energieverbrauch bedeuten würde.
  • In der Praxis wird die Dichte mit höherer Dimension exponentiell schlechter, nämlich ungefähr n^2/2^n, sodass sich die theoretische lineare Verbesserung nicht direkt in realer Performance niederschlägt. Das ist also nützlich für Daten mit natürlich hochdimensionaler Struktur, aber bei digitalen Daten — wo man im Grunde nur die Länge festlegt — kann man kleine Dimensionen wählen. Details zu sphere packing: wikipedia link
• Die Meinung, Mathematiker sollten einige Jahre nach dem ersten PhD die Möglichkeit haben, noch einen zweiten Doktortitel in einem benachbarten statt demselben Fachgebiet zu erwerben.
  • Der grundlegende Zweck eines PhD ist der Nachweis, dass man unabhängig forschen kann. Tatsächlich wechseln viele Forschende nach der Promotion in andere Bereiche oder ändern ihre Interessenschwerpunkte; ab diesem Punkt steht dann die „Forschung“ selbst im Zentrum.
  • Als Beispiel, dass so etwas tatsächlich möglich ist: Der bekannte Mathematiker Bela Bollobas hat zwei Doktortitel, einen in diskreter Geometrie und einen in Funktionalanalysis. In der heutigen Wissenschaft wäre es allerdings sehr schwer, so etwas noch einmal zu versuchen.
  • Mit solcher institutioneller Flexibilität in der gesamten Wissenschaft könnten Techniken und Ideen aus verschiedenen Bereichen schneller zirkulieren und den wissenschaftlichen Fortschritt beschleunigen. Besonders in einem Fach wie der Mathematik, wo Verbindungen zwischen Teilgebieten wichtig sind, wäre der Nutzen wohl noch größer.
• Anfängerfrage, ob optimales sphere packing immer mit regulären Gittern verbunden ist; in 2D und 3D scheint das so zu sein, aber die Frage ist, ob sich das auf ND erweitern lässt.
  • Es gibt neben 2 und 3 Dimensionen auch in 8 Dimensionen (E₈-Gitter) und 24 Dimensionen (Leech-Gitter) Fälle, in denen bewiesen wurde, dass das beste Packing die Form eines regulären Gitters hat. Das wurde 2017 von Maryna Viazovska und Kolleg:innen gezeigt; dazu gibt es die Links Paper 1, Paper 2, Erklär-PDF. In anderen Dimensionen könnte es jedoch Gegenbeispiele geben, bei denen das optimale Packing kein reguläres Gitter ist, und in manchen Dimensionen sind unregelmäßige Formen sogar dichter.
  • Nicht unbedingt. Auch in 3D gibt es neben dem Packing als lattice (reguläres Gitter) unzählige nicht-gitterförmige Packungen, bei denen die horizontalen Verschiebungen von Schicht zu Schicht variieren. Diese haben trotzdem dieselbe Dichte wie das FCC lattice. In höheren Dimensionen gibt es sogar die Vermutung, dass optimales Packing wegen mangelnder Symmetrie immer nicht-gitterförmig ist.
• Die Frage, ab welcher minimalen Dimension diese neue sphere-packing-Struktur besser ist als die bisher besten bekannten Dichten in den Dimensionen, für die diese schon bewiesen wurden.
• Der Ausblick, ob die Ergebnisse dieser Forschung in Kryptografie und Kommunikation praktisch zur Entwicklung sichererer, zuverlässigerer und energieeffizienterer Kommunikationssysteme genutzt werden könnten; ein sehr spannendes Forschungsfeld.
• Eine witzige Analogie aus der realen Physik, in der von „Cow Packing“ die Rede ist — etwa theoretischen Untersuchungen dazu, Kühe mit optimaler Dichte zu packen —, mitsamt dem Hinweis auf mögliche praktische Anwendungen.
• Sphere packing taucht in Anwendungsfeldern wirklich in sehr vielen verschiedenen Problemen auf, was es besonders interessant macht; Vorfreude darauf, das Paper gründlich zu lesen.