New lower bounds for constant-weight codes via seeded bit-swap tabu search

Stellen Sie sich vor, Sie versuchen, einen Koffer für eine Reise zu packen, aber mit einer sehr seltsamen Regel: Jeder Gegenstand, den Sie einpacken, muss exakt die gleiche Größe haben, und keine zwei Gegenstände dürfen sich zu ähnlich sein. Wenn sie sich zu ähnlich sind, könnten sie sich im Dunkeln vermischen und Chaos verursachen. In der Welt der digitalen Kommunikation ist dieser „Koffer“ eine Nachricht, die „Gegenstände“ sind Muster aus Nullen und Einsen (Bits), und die „Größe“ ist die Anzahl der Einsen im Muster. Dies ist das Rätsel der konstanten Gewicht-Codes (constant-weight codes). Wissenschaftler nutzen diese Codes, um Daten zuverlässig über verrauschte Kanäle zu senden, wie etwa WLAN oder Tiefraumfunk, um sicherzustellen, dass der Empfänger selbst dann noch feststellen kann, was gesendet wurde, wenn ein paar Bits durcheinandergebracht wurden. Das Ziel ist einfach, aber unglaublich schwer: So viele einzigartige, unterscheidbare Gegenstände wie möglich in den Koffer zu packen, ohne dass sie zusammenstoßen. Je größer der Koffer ist (also wie viele Codes man unterbringen kann), desto mehr Informationen kann man gleichzeitig senden.

Hier tritt William Echols auf den Plan, der beschloss, dieses Verpackungsproblem mit einer cleveren Wendung anzugehen. Anstatt mit einem leeren Koffer zu beginnen und wahllos Gegenstände hineinzuwerfen, in der Hoffnung, dass sie passen, nutzte er einen „geimpften“ (seeded) Ansatz. Denken Sie an Folgendes: Wenn Sie eine bessere Lego-Burg bauen wollen, fangen Sie nicht einfach bei Null an; Sie nehmen eine bereits großartige, bestehende Burg, nehmen ein paar Steine heraus und tauschen sie aus, um zu sehen, ob Sie die Burg noch größer oder stabiler machen können. Echols nutzte eine Computermethode namens Tabu-Suche, die wie ein sehr hartnäckiger Entdecker ist, der sich weigert, seine Schritte zu wiederholen (um Schleifen zu vermeiden), und stattdessen immer neue Wege ausprobiert. Indem er diesen Entdecker mit bereits existierenden, hochwertigen Code-Designs „impfte“, leitete er ihn dazu an, 124 brandneue, größere Packanordnungen zu finden, die zuvor noch nie entdeckt worden waren. Diese neuen Anordnungen verbessern die unteren Schranken dafür, wie viele Nachrichten wir gleichzeitig senden können, und sie helfen uns sogar zu verstehen, wie viele Kugeln eine zentrale Kugel berühren können – ein Konzept, das als „Kissing Number“ (Berührungszahl) bekannt ist.

Das Verpackungsrätsel und der magische Samen

In der digitalen Welt sind Daten einfach eine lange Kette aus Nullen und Einsen. Um die Robustheit zu erhöhen, erlauben wir manchmal nur Zeichenfolgen, die eine bestimmte Anzahl von Einsen haben. Wenn wir zum Beispiel sagen, das „Gewicht“ ist 5, muss jede Zeichenfolge genau fünf Einsen und den Rest Nullen haben. Stellen Sie sich nun vor, Sie haben eine Sammlung dieser Zeichenfolgen. Um Fehler zu vermeiden, muss jede Zeichenfolge in Ihrer Sammlung deutlich genug von jeder anderen anderen Zeichenfolge verschieden sein. Wenn zwei Zeichenfolgen zu ähnlich sind, könnte ein wenig Rauschen ausreichen, um eine in die andere zu verwandeln, und der Empfänger würde verwirrt werden. Der „Abstand“ zwischen ihnen wird dadurch gemessen, wie viele Stellen sich unterscheiden.

Die große Frage in diesem Bereich lautet: Was ist die maximale Anzahl an Zeichenfolgen, die Sie in Ihre Sammlung passen können? Diese maximale Anzahl wird als $A(n, d, w)$ bezeichnet, wobei $n$ die Länge der Zeichenfolge, $d$ der erforderliche Mindestabstand und $w$ die Anzahl der Einsen ist. Seit Jahrzehnten versuchen Mathematiker und Informatiker, die größten möglichen Sammlungen für verschiedene Einstellungen zu finden. Sie haben einige großartige Sammlungen gefunden, aber oft wissen sie nicht, ob sie die absolut größte gefunden haben. Sie wissen nur, dass sie nicht besser als eine bestimmte Anzahl sein können.

Die „geimpfte“ Strategie

Frühere Versuche, diese Maximalzahlen mithend Hilfe von Computersuchen zu finden, fühlten sich oft so an, als würde man in einem dunklen Wald umherwandern. Die Computer begannen mit zufälligen Vermutungen, und obwohl sie manchmal gute Pfade fanden, blieben sie oft in lokalen Lichtungen stecken, die wie der Gipfel eines Berges aussah, aber nicht der eigentliche Gipfel waren. Sie hielten dort inne, in dem Glauben, den besten Code gefunden zu haben, während direkt hinter dem nächsten Hügel ein viel größerer wartete.

Echols erkannte, dass der Schlüssel darin lag, nicht bei Null anzufangen. Er nutzte eine Technik namens geimpfte Initialisierung (seeded initialization). Anstatt einen zufälligen Startpunkt zu generieren, nahm er einen bekannten, hochwertigen Code (einen „Seed“ bzw. Samen) und nutzte diesen, um die Suche zu starten.

Er ging dies auf zwei spielerische Arten an:

1. Direktes Impfen (Direct Seeding): Er nahm einen bestehenden Code und fügte ihm ein zusätzliches Wort hinzu, das sorgfältig ausgewählt wurde, um den geringsten „Ärger“ (Distanzdefizite) zu verursachen. Dies schuf einen etwas größeren, etwas unordentlichen Startpunkt.
2. Nachbarschafts-Impfen (Neighbor Seeding): Er betrachtete Codes für leicht unterschiedliche Probleme. Wenn er beispielsweise einen Code der Länge 30 wollte, nahm er einen hervorragenden Code der Länge 29, fügte bei jedem Wort eine Null hinzu, um sie auf die Länge 30 zu bringen, und nutzte diesen dann als Startpunkt. Oder er nahm einen Code der Länge 31, schnitt eine Null ab und verwendete ihn so.

Sobald er diese „geimpften“ Startpunkte hatte, führte er seine Bit-Swap-Tabu-Suche durch. Stellen Sie sich diese Suche wie ein Spiel mit Stühlen vor, bei dem die Stühle die Positionen der Einsen in den Zeichenfolgen sind. Der Algorithmus tauscht Bits hin und her, um die Zeichenfolgen unterscheidbarer zu machen. Der „Tabu“-Teil bedeutet, dass der Algorithmus sich an die Züge erinnert, die er gerade gemacht hat, und sich weigert, diese sofort rückgängig zu machen, was ihn zwingt, neues Terrain zu erkunden, anstatt im Kreis zu laufen.

Die Ergebnisse: 124 Neuentdeckungen

Durch die Verwendung dieser klugen Impfstrategie fand Echols 124 neue Konstruktionen, die die bisherigen Bestleistungen übertrafen. Dies sind nicht nur winzige Verbesserungen; einige sind massive Sprünge.

Zum Beispiel:

• Für einen Code der Länge 39 mit spezifischen Einschränkungen lag der bisherige Rekord bei 1.014 Wörtern. Die neue Methode fand 1.118 Wörter. Das ist ein Gewinn von 104!
• Für die Länge 40 sprang der Rekord von 1.170 auf 1.230.
• Für die Länge 56 ging die Zahl von 2.414 auf 2.477.

Diese Zahlen stellen die maximale Anzahl an eindeutigen Nachrichten dar, die wir nun garantieren können zu senden, ohne Verwirrung zu stiften, für diese spezifischen Einstellungen. Das Paper behauptet nicht, dass dies die absolut maximal möglichen Werte sind (die wahre mathematische Grenze), aber es beweist, dass wir definitiv besser sein können, als wir dachten. Es hebt die „untere Schranke“ nach oben, was bedeutet, dass wir sicher wissen, dass wir mindestens so viele Gegenstände in den Koffer passen können.

Kissing Numbers: Ein überrasbender Nebeneffekt

Hier wird die Geschichte noch interessanter. Das Paper berührt auch ein Konzept namens Kissing Numbers (Berührungszahlen). Stellen Sie sich vor, Sie haben eine riesige Kugel in der Mitte eines Raumes. Wie viele andere Kugeln der gleichen Größe können Sie um sie herum packen, sodass sie alle die zentrale Kugel berühren, ohne sich gegenseitig zu überlappen? Im dreidimensionalen Raum ist die Antwort 12. Aber in höheren Dimensionen (wie 32 oder 33 Dimensionen) ist die Antwort viel schwerer zu finden.

Die Mathematik dieser Kissing Numbers ist tief mit den von Echols gefundenen konstanten Gewicht-Codes verbunden. Da er die Codes für spezifische Parameter (insbesondere $A(n, 8, 8)$) verbesserte, verbesserte er automatisch die unteren Schranken für die Kissing Numbers in den Dimensionen 32, 33, 34 und 37.

Für die Dimension 32 ($\tau_{32}$) lautete die bisherige Schätzung, dass zumindest 345.408 Kugeln die zentrale Kugel berühren könnten. Mit den neuen Codes steigt diese Zahl auf 346.432. Es ist eine kleine prozentuale Steigerung, aber in der Welt der hochdimensionalen Geometrie ist das Finden auch nur einer einzigen zusätzlichen Kugel, die passt, ein bedeutender Sieg.

Das Fazit

William Echols hat nicht nur ein paar bessere Codes gefunden; er hat gezeigt, dass man durch eine kluge Art und Weise, wie man seine Suche beginnt – indem man „Samen“ aus vorhandenem Wissen nutzt, anstatt blind zu starten – viel bessere Lösungen finden kann. Das Paper beweist, dass 124 spezifische Verbesserungen möglich sind, und es gibt uns eine neue, höhere Untergrenze dafür, wie viel Daten wir zuverlässig in diese digitalen Zeichenfolgen packen können. Es ist eine Erinnerung daran, dass der beste Weg, vorwärts zu kommen, manchmal darin besteht, auf den Schultern dessen zu stehen, was wir bereits wissen, anstatt zu versuchen, alles wieder von Grund auf neu aufzubauen.