Dada una colección de puntos en el espacio, ¿puedes encontrar cierto tipo de curva que pase por todos ellos? Esta pregunta, una versión de lo que se llama el problema de la interpolación, ha interesado a los matemáticos desde la antigüedad. A principios de este año, los matemáticos Eric Larson y isabel vogt lo resolvió completamente.
Pero si bien el trabajo ha generado mucho entusiasmo entre los matemáticos puros, la interpolación tiene consecuencias prácticas que se extienden mucho más allá del ámbito de la geometría. La interpolación es fundamental para almacenar y comunicar datos electrónicos, construir esquemas criptográficos y más. Es por eso que puede rayar un CD y seguir escuchando música, o ensuciar un código QR y seguir escaneándolo. Es por eso que las misiones espaciales como el programa Voyager podrían enviar imágenes digitales claras a la Tierra. Es por eso que un grupo de computadoras puede realizar un cálculo complejo incluso si una de esas computadoras no funciona correctamente.
Todas estas aplicaciones se basan en un uso de la interpolación sorprendentemente hermoso y conceptualmente sencillo: los llamados códigos Reed-Solomon y los códigos que se basan en ellos.
Punto por punto
Digamos que desea enviar un mensaje que consta de dos números: 2 y 7. Es posible que algunos de los datos que está transmitiendo se pierdan o se corrompan; el 2 podría convertirse en −2, por ejemplo. Entonces, en lugar de simplemente enviar los datos, puede agregar información adicional para ayudar al destinatario a identificar y corregir los errores que puedan surgir. Esto es lo que se llama un código de corrección de errores.
El ejemplo más simple de dicho código consiste en transmitir el mismo mensaje varias veces. Para permitir que el destinatario identifique si ocurrió un error, envíe el mismo mensaje dos veces: 2, 7, 2, 7. Si los números en las posiciones correspondientes no coinciden (por ejemplo, si la transmisión dice 2, 7, −2, 7), el destinatario sabrá que uno de ellos está equivocado, pero no cuál. Para que lo averigüen y corrijan el error, envíe el mismo mensaje tres veces: 2, 7, 2, 7, 2, 7. El destinatario simplemente necesita obtener la mayoría de votos para descifrar el mensaje deseado.
Pero este medio de corregir errores es tremendamente ineficiente. Aquí hay un enfoque más inteligente: codifique el mensaje como una curva y envíe solo la información suficiente para permitir que el destinatario reconstruya esa curva.
En nuestro caso simple de transmitir 2 y 7, la curva sería la línea y = 2x + 7. Evalúe esta curva en dos valores predeterminados de xy transmitir el resultado y-valores. El destinatario ahora tiene dos puntos, y debido a que el problema de interpolación nos dice que dos puntos determinan una línea única, el destinatario simplemente tiene que encontrar la línea que pasa por los puntos que recibió. Los coeficientes de la línea revelan el mensaje deseado.
Para evitar errores, una vez más agrega información adicional. Aquí, usted envía el y-valor que corresponde a otro predeterminado x-coordinar. Si los tres puntos no caen en la misma línea, hay un error. Y para averiguar dónde está el error, simplemente envíe un valor más, lo que significa que ha enviado cuatro números en total, en lugar de los seis requeridos por el método anterior.
La ventaja crece con el tamaño del mensaje. Supongamos que desea enviar un mensaje más largo: 1,000 números. El código menos eficiente requeriría enviar 2,000 números para identificar un error y 3,000 para corregirlo. Pero si usa el código que implica interpolar un polinomio a través de puntos dados, solo necesita 1,001 números para encontrar el error y 1,002 para corregirlo. (Puede agregar más puntos para identificar y corregir más errores potenciales). A medida que aumenta la longitud de su mensaje, la diferencia de eficiencia entre los dos códigos se hace más marcada.
El código más eficiente se llama código Reed-Solomon. Desde su introducción en 1960, los matemáticos han hecho más avances, desarrollando algoritmos que pueden corregir más errores con mayor eficiencia. “Es muy elegante, limpio, concreto”, dijo fiesta swastik, matemático e informático de la Universidad de Toronto. “Se puede enseñar a un estudiante de segundo año en media hora”.
Los códigos Reed-Solomon han sido particularmente útiles para almacenar y transmitir información electrónicamente. Pero el mismo concepto también ha sido fundamental en criptografía y computación distribuida.
Por ejemplo, compartir secretos: supongamos que desea distribuir un secreto entre varias partes de modo que ninguna persona pueda acceder a todo el secreto, pero juntos pueden hacerlo. (Imagine una clave de cifrado, por ejemplo, o un código de lanzamiento de misiles). Codifica los números en un polinomio, evalúa ese polinomio en un conjunto predeterminado de puntos y distribuye cada uno de los resultados a una persona diferente.
Más recientemente, los códigos Reed-Solomon se han empleado en áreas como la computación en la nube y la tecnología blockchain. Digamos que necesita ejecutar un cómputo que es demasiado complicado para su computadora portátil, por lo que tiene un gran grupo de cómputo ejecutándolo, pero ahora necesita verificar que el cómputo que recibe es correcto. Los códigos Reed-Solomon le permiten solicitar información adicional que el clúster probablemente no podrá producir si no ha realizado el cálculo correctamente. “Esto funciona mágicamente”, dijo Jade Nardi, investigador del Instituto de Matemáticas de Rennes en Francia. “Este proceso es realmente maravilloso, y la forma en que se basa en [estos códigos] me deja boquiabierto”.
Pero los códigos Reed-Solomon también tienen una restricción importante. Están construidos de tal manera que solo puede evaluar su polinomio en un conjunto de valores fijos (y generalmente relativamente pequeños). Es decir, está limitado a usar un cierto conjunto de números para codificar su mensaje. El tamaño de ese conjunto, o alfabeto, a su vez restringe la longitud de los mensajes que puede enviar, y cuanto más grande intente hacer su alfabeto, más poder computacional necesitará para decodificar esos mensajes.
Y así, los matemáticos buscaron un código aún más óptimo.
Códigos futuros
Un código más general y más potente le permitiría almacenar o enviar mensajes más largos sin necesidad de aumentar el tamaño de su alfabeto. Para hacer esto, los matemáticos idearon códigos que implican interpolar una función, que vive en un espacio especial asociado a una curva más complicada, a través de puntos dados en esa curva. Estos llamados códigos de geometría algebraica “surgieron de la nada, y son mejores que cualquier otro código que sepamos hacer [con un alfabeto más pequeño]”, dijo Kopparty. “Esto lo supera todo. Fue un verdadero shock”.
Solo hay un problema. En la práctica, implementar un código Reed-Solomon es mucho, mucho más fácil que implementar un código de geometría algebraica. “Esto es lo último en tecnología, pero aún está bajo investigación para convertirse realmente en algo práctico”, dijo el criptólogo. Simón Abelardo. "Se trata de matemáticas bastante abstractas, y es difícil manejar estos códigos en una computadora".
Por ahora, eso no es preocupante: en las aplicaciones del mundo real, los códigos Reed-Solomon y las formas relacionadas de corrección de errores son suficientes. Pero ese podría no ser siempre el caso. Por ejemplo, si en el futuro se dispone de potentes ordenadores cuánticos, podrán romper los protocolos criptográficos de hoy. Como resultado, los investigadores han estado buscando esquemas que puedan resistir los ataques cuánticos. Un competidor principal para tales esquemas requeriría algo más fuerte que los códigos Reed-Solomon. Ciertas versiones de códigos de geometría algebraica podrían funcionar. Otros investigadores tienen esperanzas sobre el papel que podrían desempeñar los códigos de geometría algebraica en la computación en la nube.
Pero incluso en ausencia de tales usos potenciales, "en la historia de las matemáticas, a veces descubres cosas nuevas que realmente no tienen aplicaciones hoy en día", dijo Elena Berardini, investigador de la Universidad Tecnológica de Eindhoven en los Países Bajos que trabaja en códigos de geometría algebraica. “Pero luego, después de 50 años, descubres que podría ser útil para algo completamente inesperado”, al igual que el antiguo problema de la interpolación.
