Data una raccolta di punti nello spazio, riesci a trovare un certo tipo di curva che li attraversi tutti? Questa domanda, una versione di quello che viene chiamato il problema dell'interpolazione, ha interessato i matematici sin dall'antichità. All'inizio di quest'anno, i matematici Eric Larson ed Isabel Vogt risolto completamente.
Ma mentre il lavoro ha suscitato molta eccitazione tra i matematici puri, l'interpolazione ha conseguenze pratiche che si estendono ben oltre il regno della geometria. L'interpolazione è fondamentale per archiviare e comunicare dati elettronici, costruire schemi crittografici e altro ancora. Ecco perché puoi graffiare un CD e continuare a sentire la musica, o sporcare un codice QR e continuare a scansionarlo. Ecco perché le missioni spaziali come il programma Voyager potrebbero inviare immagini digitali chiare sulla Terra. Ecco perché un cluster di computer può eseguire un calcolo complesso anche se uno di quei computer non funziona correttamente.
Queste applicazioni si basano tutte su un uso dell'interpolazione straordinariamente bello e concettualmente semplice: i cosiddetti codici Reed-Solomon e i codici che si basano su di essi.
Punto per punto
Supponiamo di voler inviare un messaggio composto da due numeri: 2 e 7. È possibile che alcuni dei dati che stai trasmettendo vengano persi o danneggiati: il 2 potrebbe passare a -2, per esempio. Quindi, invece di inviare semplicemente i dati, puoi aggiungere ulteriori informazioni per aiutare il destinatario a identificare e correggere gli errori che potrebbero verificarsi. Questo è ciò che viene chiamato codice di correzione degli errori.
L'esempio più semplice di tale codice prevede la trasmissione dello stesso messaggio più volte. Per consentire al destinatario di identificare se si è verificato un errore, inviare lo stesso messaggio due volte: 2, 7, 2, 7. Se i numeri nelle posizioni corrispondenti non corrispondono (ad esempio, se la trasmissione legge invece 2, 7, −2, 7), il destinatario saprà che uno di loro è sbagliato, ma non quale. Per consentire loro di capirlo e correggere l'errore, invia lo stesso messaggio tre volte: 2, 7, 2, 7, 2, 7. Il destinatario deve semplicemente prendere la maggioranza dei voti per capire il messaggio previsto.
Ma questo mezzo per correggere gli errori è estremamente inefficiente. Ecco un approccio più intelligente: codificare il messaggio come una curva e inviare informazioni sufficienti per consentire al destinatario di ricostruire quella curva.
Nel nostro semplice caso di trasmissione di 2 e 7, la curva sarebbe la linea y = 2x + 7. Valutare questa curva a due valori predeterminati di xe trasmettere il risultato y-i valori. Il destinatario ora ha due punti, e poiché il problema dell'interpolazione ci dice che due punti determinano una linea univoca, il destinatario deve semplicemente trovare la linea che passa per i punti che ha ricevuto. I coefficienti della linea rivelano il messaggio previsto.
Per evitare errori, aggiungi ancora una volta informazioni extra. Qui, invii il y-valore che corrisponde ad un altro predeterminato x-coordinata. Se i tre punti non cadono sulla stessa linea, c'è un errore. E per capire dove si trova l'errore, devi semplicemente inviare un altro valore, il che significa che hai inviato quattro numeri in totale, anziché i sei richiesti dal metodo precedente.
Il vantaggio cresce con la dimensione del messaggio. Supponiamo che tu voglia inviare un messaggio più lungo: 1,000 numeri. Il codice meno efficiente richiederebbe l'invio di 2,000 numeri per identificare un errore e 3,000 per correggerlo. Ma se usi il codice che prevede l'interpolazione di un polinomio attraverso punti dati, hai solo bisogno di 1,001 numeri per trovare l'errore e 1,002 per correggerlo. (Puoi aggiungere più punti per identificare e correggere più potenziali errori.) All'aumentare della lunghezza del tuo messaggio, la differenza di efficienza tra i due codici diventa più netta.
Il codice più efficiente è chiamato codice Reed-Solomon. Dalla sua introduzione nel 1960, i matematici hanno compiuto ulteriori progressi, sviluppando algoritmi in grado di correggere più errori con maggiore efficienza. "È molto elegante, pulito, concreto", ha detto Svastica Kopparty, matematico e informatico all'Università di Toronto. "Può essere insegnato a uno studente del secondo anno in mezz'ora."
I codici Reed-Solomon sono stati particolarmente utili per memorizzare e trasmettere informazioni elettronicamente. Ma lo stesso concetto è stato essenziale anche nella crittografia e nel calcolo distribuito.
Prendi la condivisione segreta: supponiamo che tu voglia distribuire un segreto tra più parti in modo che nessuna persona possa accedere all'intero segreto, ma insieme possono farlo. (Immaginate una chiave di crittografia, per esempio, o un codice di lancio di un missile.) Codifichi i numeri in un polinomio, valuti quel polinomio in un insieme predeterminato di punti e distribuisci ciascuno dei risultati a una persona diversa.
Più recentemente, i codici Reed-Solomon sono stati impiegati in aree come il cloud computing e la tecnologia blockchain. Supponiamo che tu debba eseguire un calcolo troppo complicato per il tuo laptop, quindi hai un grande cluster di calcolo che lo esegue, ma ora devi verificare che il calcolo che ottieni sia corretto. I codici Reed-Solomon ti consentono di richiedere informazioni aggiuntive che il cluster probabilmente non sarà in grado di produrre se non ha eseguito il calcolo correttamente. "Questo funziona magicamente", ha detto Giada Nardi, ricercatore presso l'Istituto di Matematica di Rennes in Francia. "Questo processo è davvero meraviglioso e il modo in cui si basa su [questi codici] mi fa impazzire".
Ma i codici Reed-Solomon hanno anche un vincolo importante. Sono costruiti in modo tale da poter valutare il tuo polinomio solo su un insieme di valori fisso (e solitamente relativamente piccolo). Cioè, sei limitato a utilizzare un determinato insieme di numeri per codificare il tuo messaggio. La dimensione di quel set, o alfabeto, a sua volta limita la lunghezza dei messaggi che puoi inviare, e più grande provi a creare il tuo alfabeto, maggiore è la potenza di calcolo di cui avrai bisogno per decodificare quei messaggi.
E così i matematici hanno cercato un codice ancora più ottimale.
Codici futuri
Un codice più generale e più potente ti consentirebbe di archiviare o inviare messaggi più lunghi senza dover aumentare le dimensioni del tuo alfabeto. Per fare ciò, i matematici hanno ideato codici che implicano l'interpolazione di una funzione - che vive in uno spazio speciale associato a una curva più complicata - attraverso punti dati su quella curva. Questi cosiddetti codici di geometria algebrica "sono venuti dal nulla e sono migliori di qualsiasi altro codice che sappiamo creare [con un alfabeto più piccolo]", ha detto Kopparty. “Questo batte tutto. È stato un vero shock”.
C'è solo un problema. In pratica, implementare un codice Reed-Solomon è molto, molto più semplice che implementare un codice di geometria algebrica. "Questo è lo stato dell'arte, ma è ancora oggetto di indagine per trasformarlo davvero in qualcosa di pratico", ha affermato il crittologo Simone Abelardo. "Riguarda una matematica piuttosto astratta ed è difficile gestire questi codici su un computer".
Per ora, non è preoccupante: nelle applicazioni del mondo reale, i codici Reed-Solomon e le relative forme di correzione degli errori sono sufficienti. Ma potrebbe non essere sempre così. Ad esempio, se in futuro saranno disponibili potenti computer quantistici, saranno in grado di farlo rompere i protocolli di crittografia odierni. Di conseguenza, i ricercatori hanno cercato schemi in grado di resistere agli attacchi quantistici. Uno dei principali contendenti per tali schemi richiederebbe qualcosa di più forte dei codici Reed-Solomon. Alcune versioni dei codici di geometria algebrica potrebbero funzionare. Altri ricercatori sperano nel ruolo che i codici della geometria algebrica potrebbero svolgere nel cloud computing.
Ma anche in assenza di tali potenziali usi, "nella storia della matematica, a volte si scoprono cose nuove che al giorno d'oggi non hanno davvero applicazioni", ha detto Elena Berardi, ricercatore presso la Eindhoven University of Technology nei Paesi Bassi che lavora sui codici della geometria algebrica. "Ma poi, dopo 50 anni, scopri che potrebbe essere utile per qualcosa di completamente inaspettato", proprio come l'antico problema dell'interpolazione stesso.
