Perfect $2$-codes over arbitrary alphabets

Stellen Sie sich vor, Sie senden eine geheime Nachricht durch eine lärmende, chaotische Galaxie. Jedes Mal, wenn Sie einen Buchstaben übertragen, könnte ein schelmischer Weltraumkobold ihn gegen einen anderen austauschen oder ihn ganz verschlucken. Um diesem Chaos zu trotzen, senden Sie die Nachricht nicht einfach nur einmal; Sie bauen zusätzliche „Ersatzteile“ direkt in den Code ein. Dies ist die Welt der fehlerkorrigierenden Codes, des unsichtbaren Schutzschildes, der verhindert, dass Ihre Textnachrichten, Raumsonden und Streaming-Videos in Kauderwelsch verwandeln.

In diesem Universum ist ein „perfekter Code“ der heilige Gral. Es ist wie ein Packpuzzle, bei dem Sie eine riesige Kiste haben (alle möglichen Nachrichten) und versuchen, so viele „Schutzzonen“ (Ihre eigentlichen Nachrichten) wie möglich hineinzupassen. Jede Schutzzone hat einen Radius des Schutzes um sich herum. Wenn eine Nachricht von einem Kobold getroffen wird und sich leicht verändert, landet sie immer noch innerhalb einer dieser Schutzzonen, und der Empfänger weiß genau, welche ursprüngliche Nachricht gesendet wurde. Ein Code ist „perfekt“, wenn diese Schutzzonen wie ein Puzzleteil ineinandergreifen, ohne Lücken und ohne Überlappungen. Wenn das Puzzle Lücken hat, könnten Sie eine Nachricht verlieren; wenn es Überlappungen gibt, könnten Sie verwirrt werden, welche Nachricht gesendet wurde.

Jahrzehntelang haben Mathematiker versucht, die ultimative Version dieses Puzzles zu lösen: einen perfekten Code zu finden, der gleichzeitig zwei Fehler korrigieren kann (ein „perfekter 2-Code“) und dabei ein Alphabet beliebiger Größe verwendet. Sie fanden die perfekten Lösungen für das Korrigieren von drei oder mehr Fehlern sowie für das Korrigieren eines Fehlers, aber der Fall für das Korrigieren von genau zwei Fehlern mit einer „eigenartigen“ Alphabetgröße (einer, die keine einfache Primzahlpotenz ist, wie 10 oder 15) blieb ein hartnäckiges, ungelöstes Rätsel. Es ist der Unterschied zwischen dem Wissen, wie man einen Koffer perfekt mit 2, 4 oder 8 Gegenständen packt, aber keine Ahnung zu haben, ob das mit 6 oder 10 Gegenständen möglich ist.

Dieses Papier, geschrieben von Michael Bennett, taucht tief in genau dieses spezifische Rätsel ein. Der Autor setzt sich zum Ziel zu beweisen, dass für eine sehr große und spezifische Familie von „eigenartigen“ Alphabetgrößen perfekte 2-Codes schlichtweg nicht existieren. Das Papier nutzt nicht bloß Vermutungen; es setzt eine schwere Artillerie fortgeschrittener Mathematik ein – speziell Werkzeuge, die messen, wie nah Zahlen einander kommen können, ohne sich tatsächlich zu berühren –, um zu zeigen, dass ein solcher Code, falls er existieren würde, so unglaublich massiv und seltsam sein müsste, dass er die Gesetze der Arithmetik brechen würde.

Die Haupterkenntnis ist eine kraftvolle „No-Go“-Zone. Bennett beweist, dass der Versuch, einen perfekten 2-Code mit einer Alphabetgröße zu bauen, die eine Potenz von 2 multipliziert mit einer Potenz einer einzelnen Primzahl ist (wie $2^\alpha \times p^\beta$), aussichtslos ist. Konkret zeigt er, dass die beteiligte Primzahl, damit diese Codes theoretisch überhaupt möglich wären, größer als $10^{10}$ (zehn Milliarden) sein müsste und die Zweierpotenz ($\alpha$) größer als 20 sein müsste. Darüber hinaus müsste die Primzahl, falls ein solcher Code existierte, bei der Division durch 8 einen Rest von 3 hinterlassen.

Das Papier geht noch weiter und schließt die Existenz dieser perfekten Codes für jede Alphabetgröße aus, deren größter Primfaktor 13 oder kleiner ist. Tatsächlich bestätigt der Autor eine langjährige Vermutung, dass keine perfekten 2-Codes für viele spezifische Zahlen existieren, einschließlich Fällen, in denen die Alphabetgröße $2^\alpha \times p^\beta$ mit kleinen Werten von $\alpha$ (bis zu 20) ist. Der Autor sagt nicht nur „es ist unwahrscheinlich“; er nutzt rigorose mathematische Beweise, um darzulegen, dass die Bedingungen, die für die Existenz eines solchen Codes erforderlich wären, zu mathematischen Widersprüchen führen. Während das Papier nicht jede einzelne mögliche Alphabetgröße im Universum ausschließt, schließt es effektiv die Tür zu den meisten häufigen und interessanten „eigenartigen“ Größen und lässt nur einen winzigen, hochgradig eingeschränkten Schlitz der Möglichkeit offen, der Zahlen erfordern würde, die so groß sind, dass sie praktisch unvorstellbar sind.

Die Geschichte des unmöglichen Puzzles

Um zu verstehen, was Michael Bennett getan hat, betrachten wir das Puzzle, das er zu lösen versuchte. Stellen Sie sich ein riesiges Gitter aller Wörter vor, die Sie mit einem bestimmten Alphabet bilden können. Sie wollen „Leuchtfeuer“ (Ihre Codewörter) auf diesem Gitter platzieren. Um jedes Leuchtfeuer zeichnen Sie einen Kreis, der alle Wörter abdeckt, die „nah genug“ sind (innerhalb eines Abstands von 2 Fehlern). Damit ein Code perfekt ist, müssen diese Kreise das gesamte Gitter abdecken, ohne sich zu überschneiden.

Mathematiker wissen schon seit Langem, dass es bei einer „Primzahlpotenz“ (wie 2, 3, 4, 8, 9, 16) nur wenige spezielle Fälle gibt, in denen dies perfekt funktioniert. Aber was ist, wenn Ihre Alphabetgröße etwas wie 10, 12 oder 20 ist? Dies sind „zusammengesetzte“ Zahlen, die keine Primzahlpotenzen sind. Für das Korrigieren eines Fehlers wissen wir, dass einige Lösungen existieren. Für das Korrigieren von drei oder mehr Fehlern wissen wir, dass keine existieren. Aber für das Korrigieren von zwei Fehlern? Das war die offene Frage.

Bennetts Arbeit konzentriert sich auf eine spezifische Art von zusammengesetzten Zahlen: jene, die wie $2^\alpha \times p^\beta$ aussehen. Denken Sie an dies als eine Alphabetgröße, die durch das Multiplizieren vieler 2en mit vielen Kopien einer einzigen Primzahl $p$ (wie 5, 7, 11 usw.) gebildet wird. Die Frage war: Kann man einen perfekten 2-Code für diese Größen bauen?

Die mathematische Detektivarbeit

Bennett hat nicht einfach versucht, die Codes zu bauen und gescheitert; er hat bewiesen, dass sie nicht existieren können, indem er die „Wurzeln“ einer speziellen Polynomgleichung untersuchte. Denken Sie an diese Gleichung als eine Karte, die Ihnen sagt, wo die Leuchtfeuer liegen müssen, falls ein perfekter Code existiert. Falls ein perfekter Code existiert, muss diese Karte zwei spezifische ganzzahlige Punkte (Wurzeln) haben, die sehr nah beieinander liegen.

Der Durchbruch des Autors bestand in der Erkenntnis, dass diese beiden Punkte, nennen wir sie $r_1$ und $r_2$, „S-Einheiten“ sein müssen. In einfachen Worten bedeutet dies, dass ihre Primfaktoren nur aus einer sehr kleinen, spezifischen Liste von Zahlen stammen können (den Primzahlen, die die Alphabetgröße und die 2 teilen).

Hier liegt der clevere Teil: Bennett zeigte, dass diese zwei Zahlen $r_1$ und $r_2$ unglaublich nah beieinander liegen müssten – so nah, dass ihr Unterschied winzig im Vergleich zu ihrer Größe ist. Die berühmte Disziplin der Mathematik namens Diophantische Approximation (die untersucht, wie gut man Zahlen durch Brüche approximieren kann) lehrt uns jedoch, dass Zahlen mit eingeschränkten Primfaktoren normalerweise nicht so nah beieinander liegen können, es sei denn, sie sind sehr klein.

Bennett kombinierte dies mit einer spezifischen Gleichung, die aus der Geometrie des Problems abgeleitet wurde:
$$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$$
Diese Gleichung ist der „rauchende Colt“. Sie verknüpft die Alphabetgröße $q$ direkt mit dem Abstand zwischen den beiden Wurzeln.

Die große Enthüllung

Unter Verwendung dieser Gleichung und mächtiger Werkzeuge der Zahlentheorie bewies Bennett eine Reihe von „Unmöglichkeits“-Ergebnissen:

1. Das Verbot der „kleinen Primzahlen“: Wenn der größte Primfaktor Ihrer Alphabetgröße 13 oder kleiner ist, ist ein perfekter 2-Code unmöglich. Er tat dies, indem er alle möglichen Paare von Zahlen auflistete, die die Wurzeln sein könnten, und zeigte, dass keines von ihnen die Gleichung erfüllt.
2. Die „Riesen-Zahlen“-Barriere: Für den allgemeinen Fall, in dem das Alphabet $2^\alpha \times p^\beta$ ist, bewies er, dass, falls ein Code existieren sollte, die Primzahl $p$ größer als $10^{10}$ (zehn Milliarden) sein müsste. Noch restriktiver ist, dass die Zweierpotenz ($\alpha$) größer als 20 sein müsste.
3. Die „Mod 8“-Regel: Falls ein solcher Code existierte, müsste die Primzahl $p$ eine Zahl sein, die bei der Division durch 8 einen Rest von 3 hinterlässt (wie 3, 11, 19 usw.).

Das Papier besagt im Wesentlichen: „Wir haben die kleinen Zahlen überprüft, und sie funktionieren nicht. Für die großen Zahlen sagt die Mathematik, dass sie so enorm groß sein müssten und so strengen Regeln folgen müssten, dass sie praktisch nicht existieren.“

Die Überraschung der Schröder-Hipparchus-Zahlen

Einer der erfreulichsten Teile des Papers ist, wie es eine Zahlenfolge aus der klassischen Kombinatorik verwendet, die Schröder-Hipparchus-Zahlen (auch bekannt als Super-Catalan-Zahlen). Diese Zahlen, die normalerweise in Problemen über die Anzahl der Möglichkeiten zur Anordnung von Klammern oder Pfaden auf einem Gitter auftauchen, erscheinen plötzlich mitten im Beweis für den fehlerkorrigierenden Code.

Bennett nutzte diese Zahlen, um eine komplexe Gleichung in eine Reihe von Termen zu expandieren. Es ist, als fände man ein verborgenes Muster in einem chaotischen Rauschen. Indem er die Gleichung unter Verwendung dieser Zahlen expandierte, konnte er zeigen, dass die Terme zu schnell wachsen, um die „enge Nähe“ zuzulassen, die für einen perfekten Code erforderlich wäre, es sei denn, die beteiligten Zahlen sind absurd groß.

Das abschließende Urteil

Was ist also die Quintessenz? Das Papier bestätigt einen lang gehegten Verdacht in der mathematischen Gemeinschaft: Perfekte 2-Codes über beliebige Alphabete existieren höchstwahrscheinlich nicht.

Obwohl das Papier nicht behauptet, den einen perfekten Code gefunden zu haben, der sich vielleicht im Universum versteckt (da es beweist, dass er, falls er existiert, größer als $10^{10}$ sein müsste und unmögliche Bedingungen erfüllen müsste), schließt es effektiv die große Mehrheit der Fälle aus. Es schließt die Tür zu Alphabetgrößen wie 10, 15, 21 und vielen anderen und drängt die Möglichkeit einer Lösung so weit in den Bereich der gigantischen Zahlen, dass sie als praktisch nicht existent gilt.

Die Arbeit des Autors ist ein Triumph des „negativen“ Beweises. Anstatt einen Schatz zu finden, hat er bewiesen, dass die Schatzkiste leer ist, oder zumindest, dass der Schlüssel zum Öffnen ein Schloss erfordert, das noch nicht erfunden wurde. Für jeden, der versucht, fehlerkorrigierende Codes für diese spezifischen Alphabetgrößen zu bauen, ist die Botschaft klar: Suchen Sie nicht nach einem perfekten 2-Code; er ist nicht da.