Perfect $2$-codes over arbitrary alphabets

Immagina di inviare un messaggio segreto attraverso una galassia rumorosa e caotica. Ogni volta che trasmetti una lettera, un dispettoso goblin spaziale potrebbe scambiarla con un'altra, oppure farla cadere del tutto. Per sopravvivere a questo caos, non invii il messaggio una sola volta; lo invii con dei "pezzi di ricambio" integrati direttamente nel codice. Questo è il mondo dei codici di correzione degli errori, lo scudo invisibile che impedisce ai tuoi messaggi di testo, alle tue sonde spaziali e ai tuoi video in streaming di trasformarsi in un ammasso di frasi senza senso.

In questo universo, un "codice perfetto" è il santo graal. È come un puzzle di incastri dove hai una scatola gigante (tutti i messaggi possibili) e cerchi di farci entrare quanti più "zone di sicurezza" (i tuoi veri messamenti) possibile. Ogni zona di sicurezza ha un raggio di protezione intorno a sé. Se un messaggio viene colpito da un goblin e cambia leggermente, finisce comunque all'interno di una di queste zone di sicurezza, e il ricevitore sa esattamente quale messaggio originale era stato inviato. Un codice è "perfetto" se queste zone di sicurezza si incastrano come un puzzle, senza lasciare buchi e senza sovrapposizioni. Se il puzzle presenta dei vuoti, potresti perdere un messaggio; se si sovrappone, potresti confondere il messaggio inviato con un altro.

Per decenni, i matematici hanno cercato di risolvere la versione definitiva di questo puzzle: trovare codici perfetti capaci di correggere due errori alla volta (un "codice perfetto 2") utilizzando un alfabeto di qualsiasi dimensione. Sebbene abbiano trovato le soluzioni perfette per correggere tre o più errori, e anche per correggerne uno, il caso per correggere esattamente due errori con una dimensione di alfabeto "strana" (una che non sia una semplice potenza di un numero primo, come 10 o 15) è rimasto un mistero ostinato e irrisolto. È la differenza tra sapere come imballare perfettamente una valigia con 2, 4 o 8 oggetti, ma non avere idea di come sia possibile farlo con 6 o 10 oggetti.

Questo articolo, scritto da Michael Bennett, scava profondamente in proprio quel mistero specifico. L'autore si propone di dimostrare che per una famiglia molto vasta e specifica di dimensioni di alfabeto "strane", i codici perfetti 2 semplicemente non esistono. L'articolo non si limita a indovinare; utilizza un pesante artigliere di matematica avanzata — specificamente strumenti che misurano quanto i numeri possano avvicinarsi tra loro senza toccarsi effettivamente — per dimostrare che, se un tale codice esistesse, dovrebbe essere così incredibilmente massiccio e strano da infrangere le leggi dell'aritmetica.

La scoperta principale è una zona di "divieto". Bennett dimostra che se provi a costruire un codice perfetto 2 usando una dimensione di alfabeto composta da una potenza di 2 moltiplicata per una potenza di un singolo numero primo ($2^\alpha \times p^\beta$), sei fuori strada. Nello specifico, dimostra che affinché questi codici siano teoricamente possibili, il numero primo coinvolto dovrebbe essere maggiore di $10^{10}$ (dieci miliardi), e la potenza di 2 dovrebbe essere maggiore di 20. Inoltre, se un tale codice esistesse, il numero primo dovrebbe lasciare un resto di 3 quando diviso per 8.

L'articolo va oltre. Esclude l'esistenza di questi codici perfetti per qualsiasi dimensione di alfabeto in cui il fattore primo più grande sia 13 o minore. In effetti, l'autore conferma una congettura di lunga data secondo cui non esistono codici perfetti 2 per molti numeri specifici, inclusi i casi in cui la dimensione dell'alfabeto è $2^\alpha \times p^\beta$ con valori piccoli di $\alpha$ (fino a 20). L'autore non dice solo che "è improbabile"; usa rigorose prove matematiche per dimostrare che le condizioni richieste affinché un tale codice esista portano a contraddizioni matematiche.

La storia del puzzle impossibile

Per capire cosa ha fatto Michael Bennett, guardiamo al puzzle che stava cercando di risolvere. Immagina una gigantesca griglia di tutte le parole che puoi formare con un certo alfabeto. Vuoi posizionare dei "fari" (le tue parole di codice) su questa griglia. Intorno a ogni faro, disegni un cerchio che copre tutte le parole che sono "abbastanza vicine" (entro una distanza di 2 errori). Affinché un codice sia perfetto, questi cerchi devono coprire l'intera griglia senza sovrapporsi.

I matematici sanno da tempo che se la dimensione del tuo alfabeto è una "potenza di un numero primo" (come 2, 3, 4, 8, 9, 16), esistono solo alcuni casi speciali in cui questo funziona perfettamente. Ma cosa succede se la dimensione del tuo alfabeto è qualcosa come 10, 12 o 20? Questi sono numeri "compositi" che non sono potenze di numeri primi. Per correggere un errore, sappiamo che esistono alcune soluzioni. Per correggere tre o più errori, sappiamo che non ne esistono. Ma per correggere due errori? Questa era la domanda aperta.

L'articolo di Bennett si concentra su un tipo specifico di numero composito: quelli che hanno la forma $2^\alpha \times p^\beta$. Pensa a questo come a una dimensione di alfabeto creata moltiplicando un sacco di 2 per un sacco di copie di un singolo numero primo $p$ (come 5, 7, 11, ecc.). La domanda era: puoi costruire un codice perfetto 2 per queste dimensioni?

Il lavoro investigativo matematico

Bennett non ha solo provato a costruire i codici fallendo; ha dimostrato che non potevano esistere guardando le "radici" di una speciale equazione polinomiale. Pensa a questa equazione come a una mappa che ti dice dove devono trovarsi i fari se un codice perfetto esiste. Se un codice perfetto esiste, questa mappa deve avere due punti interi specifici (radici) che sono molto vicini tra loro.

La svolta dell'autore è stata realizzare che questi due punti, chiamiamoli $r_1$ e $r_2$, devono essere "unità S". In parole povere, significa che i loro fattori primi possono provenire solo da una lista molto piccola e specifica di numeri (i numeri primi che dividono la dimensione dell'alfabeto e il numero 2).

Ecco la parte astuta: Bennett ha dimostrato che, per un codice perfetto, questi due numeri, $r_1$ e $r_2$, dovrebbero essere incredibilmente vicini tra loro — così vicini che la loro differenza è minuscola rispetto alla loro dimensione. Tuttavia, una famosa branca della matematica chiamata approssimazione di Diophantus (che studia quanto bene si possano approssimare i numeri con le frazioni) ci dice che i numeri con fattori primi limitati di solito non possono avvicinarsi così tanto tra loro a meno che non siano molto piccoli.

Bennett ha combinato questo con un'equazione specifica derivata dalla geometria del problema:
$$q(r_2 - r_1)^2 = 2(r_1 + r_2) + q - 6$$
Questa equazione è la "pistola fumante". Collega direttamente la dimensione dell'alfabeto $q$ alla distanza tra le due radici.

La grande rivelazione

Utilizzando questa equazione e potenti strumenti della teoria dei numeri, Bennett ha dimostrato una serie di risultati di "impossibilità":

1. Il divieto dei "Piccoli Primi": Se il fattore primo più grande della dimensione del tuo alfabeto è 13 o minore, un codice perfetto 2 è impossibile. Lo ha fatto elencando tutte le possibili coppie di numeri che potrebbero essere le radici e dimostrando che nessuna di esse si adatta all'equazione.
2. La barriera dei "Numeri Enormi": Per il caso generale in cui l'alfabeto è $2^\alpha \times p^\beta$, ha dimostrato che se un codice avesse esistito, il numero primo $p$ avrebbe dovuto essere maggiore di $10^{10}$ (dieci miliardi). Ancora più restrittivamente, la potenza di 2 ($\alpha$) avrebbe dovuto essere maggiore di 20.
3. La regola del "Mod 8": Se un tale codice esistesse, il numero primo $p$ avrebbe dovuto essere un numero che lascia un resto di 3 quando diviso per 8 (come 3, 11, 19, ecc.).

L'articolo dice essenzialmente: "Abbiamo controllato i numeri piccoli, e non funzionano. Per i numeri grandi, la matematica dice che dovrebbero essere così enormi e seguire regole così strette da essere praticamente inesistenti".

La sorpresa di Schröder-Hipparchus

Uno dei parti più deliziosi dell'articolo è come utilizza una sequenza di numeri dalla combinatoria classica chiamati numeri di Schröder-Hipparchus (noti anche come numeri super-Catalan). Questi numeri, che di solito compaiono in problemi relativi al conteggio dei modi per disporre parentesi o percorsi su una griglia, appaiono improvvisamente nel mezzo della dimostrazione del codice correttore d'errore.

Bennett ha usato questi numeri per espandere un'equazione complessa in una serie di termini. È come trovare un modello nascosto in un rumore caotico. Espandendo l'equazione usando questi numeri, ha potuto dimostrare che i termini crescono troppo velocemente per permettere la "stretta vicinanza" richiesta da un codice perfetto, a meno che i numeri coinvolti non siano assurdamente grandi.

Il verdetto finale

Quindi, qual è la conclusione? L'articolo conferma un sospetto di lunga data nella comunità matematica: i codici perfetti 2 su alfabeti arbitrari probabilmente non esistono.

Sebbene l'articolo non sostenga di aver trovato l'unico codice perfetto che potrebbe nascondersi nell'universo (perché dimostra che se ne esiste uno, deve essere più grande di $10^{10}$ e seguire vincoli impossibili), esso esclude efficacemente la stragrande maggioranza dei casi. Chiude la porta a dimensioni di alfabeto come 10, 15, 21 e molte altre, e spinge la possibilità di una soluzione così lontano nel regno dei numeri giganti da renderla praticamente inesistente.

Il lavoro dell'autore è un trionfo della prova "negativa". Inveve di trovare un tesoro, ha dimostrato che il forziere è vuoto, o almeno che la chiave per aprirlo richiede una serratura che non è ancora stata inventata. Per chiunque stia cercando di costruire codici correttori di errori per queste specifiche dimensioni di alfabeto, il messaggio è chiaro: smettere di cercare un codice perfetto 2; non c'è.