Perfect $2$-codes over arbitrary alphabets

Stel je voor dat je een geheime boodschap verstuurt door een lawaaierige, chaotische Melkweg. Elke keer dat je een letter verzendt, kan een ondeugende ruimtegobelijn de letter vervangen door een andere, of hem er simpelweg tussenuit laten vallen. Om te overleven in deze chaos, stuur je de boodschap niet slechts één keer; je stuurt hem met extra "reserveonderdelen" die direct in de code zijn ingebouwd. Dit is de wereld van foutcorrigerende codes, het onzichtbare schild dat je tekstberichten, ruimtesondes en streamingvideo's behoedt voor het veranderen in wartaal.

In dit universum is een "perfecte code" de heilige graal. Het is als een puzzel waarbij je een enorme doos hebt (alle mogelijke berichten) en je probeert er zoveel mogelijk "veilige zones" (je werkelijke berichten) in te passen. Elke veilige zone heeft een beschermingsstraal om zich heen. Als een bericht door een goblin wordt geraakt en licht verandert, landt het nog steeds binnen een van deze veilige zones, en weet de ontvanger precies wat de oorspronkelijke boodschap was. Een code is "perfect" als deze veilige zones in elkaar passen als een legpuzzel, zonder gaten en zonder overlap. Als de puzzel gaten heeft, kun je een bericht verliezen; als ze overlappen, kun je in de war raken over welke boodschap is verzonden.

Decennialang hebben wiskundigen geprobeerd om de ultieme versie van deze puzzel op te lossen: het vinden van perfecte codes die tegelijkertijd twee fouten kunnen herstellen (een "perfecte 2-code") met een alfabet van elke grootte. Ze vonden de perfecte oplossingen voor het herstellen van drie of meer fouten, en voor het herstellen van één fout, maar de situatie voor het herstellen van exact twee fouten met een "vreemd" alfabetformaat (één dat geen eenvoudige macht van een priemgetal is, zoals 10 of 15) bleef een hardnekkig, onopgelost mysterie. Het is het verschil tussen weten hoe je een koffer perfect kunt inpakken met 2, 4 of 8 items, maar geen idee hebben of dat mogelijk is met 6 of 10 items.

Dit artikel, geschreven door Michael Bennett, duikt diep in dat specifieke mysterie. De auteur zet uit om te bewijzen dat voor een zeer grote en specifieke familie van "vreemde" alfabetgroottes, perfecte 2-codes simpelweg niet bestaan. Het artikel gebruikt niet alleen een gok; het gebruikt een zwaar arsenaal aan geavanceerde wiskunde — specifiek hulpmiddelen die meten hoe dicht getallen bij elkaar kunnen komen zonder elkaar daadwerkelijk aan te raken — om aan te tonen dat als een dergelijke code zou bestaan, deze zo ongelooflijk massief en vreemd zou moeten zijn dat het de wetten van de rekenkunde zou breken.

De belangrijkste bevinding is een krachtige "no-go"-zone. Bennett bewijst dat als je probeert een perfecte 2-code te bouwen met een alfabetgrootte die een macht van 2 vermenigvuldigd is met een macht van een enkel priemgetal (zoals $2^\alpha \times p^\beta$), je kansloos bent. Specifiek laat hij zien dat voor deze codes zelfs theoretisch mogelijk te zijn, het betrokken priemgetal groter zou moeten zijn dan $10^{10}$ (tien miljard), en de macht van 2 groter dan 20 zou moeten zijn. Bovendien, als een dergelijke code bestond, zou het priemgetal een restwaarde van 3 moeten hebben bij deling door 8.

Het artikel gaat nog verder. Het sluit het bestaan van deze perfecte codes uit voor elke alfabetgrootte waarbij de grootste priemfactor 13 of kleiner is. Sterker nog, de auteur bevestigt een langdurige conjectuur dat er geen perfecte 2-codes bestaan voor veel specifieke getallen, waaronder gevallen waar de alfabetgrootte $2^\alpha \times p^\beta$ is met kleine waarden van $\alpha$ (tot 20). De auteur zegt niet alleen "het is onwaarschijnlijk"; hij gebruikt rigoureuze wiskundige bewijzen om aan te tonen dat de voorwaarden die vereist zijn voor een dergelijke code leiden tot wiskundige tegenstrijdigheden. Hoewel het artikel niet elke enkele mogelijke alfabetgrootte in het universum uitsluit, sluit het de deur op een effectieve manier voor de meest voorkomende en interessante "vreemde" groottes, waardoor er slechts een piepklein, zeer beperkt strookje mogelijkheid overblijft dat getallen vereist die zo groot zijn dat ze praktisch onvoorstelbaar zijn.

Het Verhaal van de Onmogelijke Puzzel

Om te begrijpen wat Michael Bennett deed, kijken we naar de puzzel die hij probeerde op te lossen. Stel je een gigantisch rooster voor van alle woorden die je kunt maken met een bepaat alfabet. Je wilt "bakens" (je codewoorden) op dit rooster plaatsen. Rondom elk baken teken je een cirkel die alle woorden dekt die "dichtbij genoeg" zijn (binnen een afstand van 2 fouten). Voor een code om perfect te zijn, moeten deze cirkels het hele rooster dekken zonder te overlappen.

Wiskundigen weten al een tijdje dat als je alfabetgrootte een "priemmacht" is (zoals 2, 3, 4, 8, 9, 16), er slechts enkele speciale gevallen zijn waarin dit perfect werkt. Maar wat als je alfabetgrootte iets is als 10, 12 of 20? Dit zijn "samengestelde" getallen die geen priemmachten zijn. Voor het herstellen van één fout weten we dat er oplossingen bestaan. Voor het herstellen van drie of meer fouten weten we dat er geen bestaan. Maar voor het herstellen van twee fouten? Dat was de openstaande vraag.

Bennett's artikel richt zich op een specifiek type samengesteld getal: die die eruitzien als $2^\alpha \times p^\beta$. Zie dit als een alfabetgrootte die is opgebouwd door een heleboel 2'en te vermenigvuldigen met een heleboel kopieën van een enkel priemgetal $p$ (zoals 5, 7, 11, enz.). De vraag was: Kun je een perfecte 2-code voor deze groottes bouwen?

Het Wiskundige Detectiewerk

Bennett probeerde niet alleen codes te bouwen die faalden; hij bewees dat ze niet konden bestaan door te kijken naar de "wortels" van een speciale polynoomvergelijking. Denk aan deze vergelijking als een kaart die aangeeft waar de bakens moeten staan als een perfecte code bestaat. Als een perfecte code bestaat, moet deze kaart twee specifieke gehele punten (wortels) hebben die heel dicht bij elkaar liggen.

De doorbraak van de auteur was het besef dat deze twee punten, laten we ze $r_1$ en $r_2$ noemen, "S-units" moeten zijn. In gewone mensentaal betekent dit dat hun priemfactoren alleen afkomstig kunnen zijn uit een zeer kleine, specifieke lijst van getallen (de priemgetallen die de alfabetgrootte en het getal 2 delen).

Hier is het slimme deel: Bennett toonde aan dat voor een perfecte code te bestaan, deze twee getallen $r_1$ en $r_2$ ongelooflijk dicht bij elkaar zouden moeten liggen — zo dicht dat hun verschil minuscuul is vergeleken met hun grootte. Echter, een beroemde tak van de wiskunde genaamd Diophantische benadering (die bestudeert hoe goed je getallen kunt benaderen met breuken) vertelt ons dat getallen met beperkte priemfactoren meestal niet zo dicht bij elkaar kunnen komen, tenzij ze zeer klein zijn.

Bennett combineerde dit met een specifieke vergelijking afgeleid van de geometrie van het probleem:
$$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$$
Deze vergelijking is de "smoking gun". Het koppelt de alfabetgrootte $q$ direct aan de afstand tussen de twee wortels.

De Grote Onthulling

Met behulp van deze vergelijking en krachtige instrumenten uit de getaltheorie, bewees Bennett een reeks "onmogelijkheid"-resultaten:

1. Het "Kleine Priemgetal" Verbod: Als de grootste priemfactor van je alfabetgrootte 13 of kleiner is, is een perfecte 2-code onmogelijk. Hij deed dit door alle mogelijke paren getallen op te stellen die de wortels zouden kunnen zijn en aan te tonen dat geen van hen aan de vergelijking voldoet.
2. De "Enorm Groot Getal" Barrière: Voor het algemene geval waar het alfabet $2^\alpha \times p^\beta$ is, bewees hij dat als een code wel zou bestaan, het priemgetal $p$ groter dan $10^{10}$ (tien miljard) zou moeten zijn. Nog restrictiever: de macht van 2 ($\alpha$) zou groter dan 20 moeten zijn.
3. De "Mod 8" Regel: Als een dergelijke code bestond, zou het priemgetal $p$ een getal moeten zijn dat een restwaarde van 3 geeft bij deling door 8 (zoals 3, 11, 19, enz.).

Het artikel zegt in feite: "We hebben de kleine getallen gecontroleerd, en die werken niet. Voor de grote getallen zegt de wiskunde dat ze zo enorm zouden moeten zijn en aan zulke strikte regels zouden moeten voldoen dat ze in de praktijk feitelijk niet bestaan."

De Schröder-Hipparchus Verrassing

Een van de meest genotvolle delen van het artikel is hoe het gebruik maakt van een getallenreeks uit de klassieke combinatoriek genaamd Schröder-Hipparchus getallen (ook wel bekend als super-Catalan getallen). Deze getallen, die gewoon verschijnen in problemen over het tellen van manieren om haakjes te plaatsen of paden op een rooster, verschijnen plotseling midden in het bewijs van de foutcorrigerende code.

Bennett gebruikte deze getallen om een complexe vergelijking uit te breiden naar een reeks termen. Het is alsof je een verborgen patroon vindt in een chaotische ruis. Door de vergelijking uit te breiden met deze getallen, kon hij aantonen dat de termen te snel groeien om de "nabijheid" toe te staan die vereist is voor een perfecte code te bestaan, tenzij de betrokken getallen absurd groot zijn.

Het Eindoordeel

Dus, wat is de kern van het verhaal? Het artikel bevestigt een langdurige verdenking in de wiskundige gemeenschap: Perfecte 2-codes over willekeurige alfabetten bestaan waarschijnlijk niet.

Hoewel het artikel niet beweert dat het de ene perfecte code heeft gevonden die misschien in het universum verborgen ligt (omdat het bewijst dat als er een bestaat, deze groter moet zijn dan $10^{10}$ en aan onmogelijke beperkingen moet voldoen), sluit het effectief de overgrote meerderheid van de gevallen uit. Het sluit de deur voor alfabetgroottes zoals 10, 15, 21 en vele anderen, en duwt de mogelijkheid van een oplossing zo ver in het rijk van gigantische getallen dat het als praktisch niet-bestaand wordt beschouwd.

Het werk van de auteur is een triomf van het "negatieve" bewijs. In plaats van een schat te vinden, heeft hij bewezen dat de schatkist leeg is, of althans dat de sleutel om hem te openen een slot vereist dat nog niet is uitgevonden. Voor iedereen die probeert foutcorrigerende codes te bouwen voor deze specifieke alfabetgroottes, is de boodschap duidelijk: stop met zoeken naar een perfecte 2-code; die is er niet.