Sphere-Packing

Sphere-Packing ist ein klassisches Problem der Mathematik. Die Frage lautet: Wie stapelt man gleich große Kugeln so, dass möglichst wenig leerer Raum bleibt? Die Kugeln dürfen sich berühren, aber nicht überlappen. Jeder kennt die Antwort für den Alltag: Orangen im Supermarkt liegen in Schichten, jede Kugel sitzt in der Mulde zwischen drei Kugeln darunter. Diese Anordnung füllt etwa 74 Prozent des Raums, der Rest ist Luft. Dass es im dreidimensionalen Raum nicht besser geht, hat man erst 1998 bewiesen, obwohl Johannes Kepler es 1611 schon vermutet hatte.

Warum Obstkisten und Funksignale dasselbe Problem haben

Interessant wird Sphere-Packing, weil man es nicht nur in drei Dimensionen stellen kann. Mathematiker fragen auch nach vier, acht oder 24 Dimensionen. Ein Raum mit vielen Dimensionen ist einfach eine Liste von Zahlen: ein Punkt in acht Dimensionen ist ein Satz von acht Werten. Genau so beschreibt man technische Signale. Eine Funkübertragung oder eine gespeicherte Zahlenfolge ist ein Punkt in einem solchen Raum.

Daraus wird ein praktisches Problem der Nachrichtentechnik. Wer Daten überträgt, wählt eine Menge erlaubter Signale aus. Auf dem Weg kommt Störung dazu, das Signal verschiebt sich ein Stück. Der Empfänger nimmt das erlaubte Signal, das am nächsten liegt. Damit er sich nicht vertut, müssen die erlaubten Signale weit genug auseinanderliegen. Um jedes Signal liegt also eine Sicherheitskugel — und man will möglichst viele solcher Kugeln unterbringen. Das ist wörtlich Sphere-Packing.

Der Informationstheoretiker Claude Shannon hat diesen Zusammenhang in den 1940er-Jahren formuliert. Seine Grenze sagt, wie viele Daten ein gestörter Kanal maximal tragen kann. Fehlerkorrigierende Codes in Mobilfunk, DVDs und Festplatten sind Versuche, dieser Grenze nahezukommen.

Gitter, Zufall und der Sprung nach Dimension 8

Die einfachste Strategie ist ein Gitter: Man legt die Kugelmittelpunkte in ein regelmäßiges Muster und wiederholt es. In drei Dimensionen liefert das die Orangenpackung. In acht Dimensionen gibt es ein besonders gutes Gitter mit dem Namen E8, in 24 Dimensionen das Leech-Gitter. Für diese beiden Fälle wurde 2016 bewiesen, dass sie optimal sind. Die Mathematikerin Maryna Viazovska erhielt dafür 2022 die Fields-Medaille, die höchste Auszeichnung ihres Fachs.

Für fast alle anderen Dimensionen ist das beste Ergebnis unbekannt. Man kennt nur Ober- und Untergrenzen, also einen Bereich, in dem die Lösung liegen muss. Ein verbreiteter Irrtum ist, dass regelmäßige Gitter immer am besten sind. In sehr vielen Dimensionen liefern zufällig gestreute Kugeln überraschend gute Werte, und niemand weiß sicher, ob geordnete Muster dort überhaupt gewinnen.

Ein zweiter Punkt ist wichtig für das Verständnis. In hohen Dimensionen wird Packen dramatisch schlechter. Schon in zehn Dimensionen füllen die besten bekannten Packungen weniger als ein Prozent des Raums. Der Grund: Fast das gesamte Volumen eines hochdimensionalen Würfels sitzt in seinen Ecken, und dort passt keine Kugel hin.

Von der Handyverbindung bis zur Post-Quanten-Kryptografie

Im Alltag steckt Sphere-Packing unsichtbar in jeder stabilen Datenverbindung. Wenn ein Video trotz schwachem WLAN ohne Bildfehler läuft, arbeiten dort Codes, deren Aufbau auf Gitterpackungen zurückgeht. Auch die Modulation im 5G-Mobilfunk beruht darauf, Signalpunkte mit maximalem Abstand zu verteilen.

In Tech-News begegnet der Begriff derzeit meist im Zusammenhang mit Verschlüsselung. Verfahren der sogenannten Post-Quanten-Kryptografie sollen auch dann sicher bleiben, wenn es leistungsfähige Quantencomputer gibt. Viele dieser Verfahren beruhen auf Gittern in hunderten Dimensionen. Ihre Sicherheit hängt daran, dass es extrem schwer ist, in einem solchen Gitter den nächstgelegenen Punkt zu finden — genau die Frage, die beim Packen von Kugeln auftaucht. Das US-Normungsinstitut NIST hat 2024 erste solche Verfahren standardisiert.

Abgrenzen sollte man Sphere-Packing vom verwandten Problem der Raumaufteilung ohne Lücken. Dort fragt man, wie man einen Raum vollständig in gleiche Zellen zerlegt. Beim Sphere-Packing bleiben Lücken zwangsläufig, weil Kugeln keine Ecken ausfüllen. Beide Fragen tauchen in der Datenkompression auf, wenn Messwerte auf wenige Stufen gerundet werden.