Carlos Beltrán nos habla de su solución del Problema 17 de la lista de Smale

Hace unos meses, concretamente en junio de este año 2011, el matemático español Carlos Beltrán recibió el Premio José Luis Rubio de Francia 2010, que entrega la RSME, por la resolución junto a Luis Miguel Pardo (su director de tesis) del problema 17 de la lista de Smale, de la que hablábamos el martes en este post.

La noticia apareció en multitud de medios de comunicación, al menos en sus ediciones online (pueden encontrarse muchos de esos artículos de forma sencilla utilizando cualquier buscador). Y en ellas se explicaba muy por encima en qué consiste este problema 17 y qué había hecho Carlos en relación con él, pero, como es normal, no se profundizaba demasiado.

Por ello me puse en contacto con Carlos durante este verano, invitándole a colaborar con Gaussianos en este sentido. Lo que hice fue pedirle una colaboración en forma de artículo en el que nos explicara en qué consiste este problema 17 de la lista de Smale y qué es exactamente lo que habían conseguido Luis Miguel Pardo y él mismo. Y la verdad es que desde el primer momento mostró una muy buena predisposición a dicha colaboración. Aquí tenéis el artículo en cuestión.

Carlos Beltrán y el problema 17 de la lista de Smale

Uno de los bloques constructivos de las matemáticas es la resolución de ecuaciones polinomiales. Posiblemente todos recordamos cuando en el colegio nos pedían encontrar la incógnita de una ecuación como por ejemplo . Esta ecuación, llamada de segundo grado porque el mayor exponente de la es 2, tiene una conocida fórmula que la resuelve, y se pueden calcular exactamente sus dos soluciones: .

En problemas prácticos, sucede frecuentemente que tenemos que resolver ecuaciones más complicadas, como por ejemplo (que tiene grado 3), o (que tiene grado 24). También puede suceder que tengamos que encontrar dos variables (¡o tres, o cinco, o quinientas variables!). Por ejemplo, supongamos que tenemos que encontrar que satisfacen las dos siguientes ecuaciones:

En general, no existe una fórmula que nos dé la solución de esta clase de sistemas de ecuaciones. Además, suele suceder que existen muchas soluciones para un sistema así.

Los matemáticos e ingenieros han desarrollado diversos métodos para resolver este tipo de sistemas. Entre los más populares está el llamado método de homotopía, que consiste en lo siguiente:

Tomamos otro sistema que sea parecido al que queremos resolver, pero más sencillo. Por ejemplo, podemos tomar

que es un sistema de ecuaciones tan noble como cualquier otro. Ahora, supongamos que deformamos este sistema hasta el que queremos resolver y vamos mirando cómo cambia la solución. Uno esperaría que si tenemos un sistema muy parecido al sencillo, por ejemplo

entonces la solución de este sistema sea muy parecida a . Pues bien, ésta es la idea: deformamos un poquito el primer sistema, calculamos su solución, lo deformamos otro poquito, calculamos la solución, y así vamos haciendo que el sistema original se vaya pareciendo al que queremos resolver cada vez más. Si hacemos las cosas bien, con un poco de suerte, al final la solución deformada que tendremos debería parecerse mucho a una solución del sistema que queríamos resolver.

El lector atento puede tal vez notar que hay un detalle que falta mencionar aquí: si tenemos algo muy parecido a una solución, entonces existe una forma de acercarnos más a esa solución. Para ello se utiliza un método cuyo origen se debe al mismísimo Sir Isaac Newton. Utilizando este método (el método de Newton) podemos hacer funcionar la idea de la deformación que acabamos de mencionar.

Este esquema, si bien puede parecer complicado en un principio, es bastante sencillo de implementar en un ordenador. Y (si uno tiene las precauciones necesarias y utiliza unos cuantos trucos que los expertos han desarrollado en las últimas décadas) parece ser tremendamente exitoso en la práctica. Claro que, como matemático que es el que escribe, lo de parece ser no deja de ser un poco molesto: ¡en realidad, no se puede garantizar que un método funciona rápido y bien simplemente porque lo hayamos usado unas cuantas veces y haya funcionado aparentemente! El estudio riguroso del problema de los métodos de homotopía es necesario para garantizar al usuario que lo que el ordenador está haciendo es correcto y que el método es eficaz.

Durante la década de los 90, Stephen Smale (medalla Fields) y Michael Shub, demostraron que este proceso se puede realizar de una forma totalmente rigurosa: dado un sistema inicial bueno con solución conocida, casi siempre se puede deformar esta solución hasta obtener otra del sistema final. Lo de casi siempre es necesario por motivos técnicos, pero Shub y Smale clarificaron este punto totalmente, diciendo cuándo se puede hacer. Posteriormente este algoritmo fue mejorado por otros autores para ser más rápido y eficaz. Ahora mismo se puede decir que este punto se entiende completa o casi completamente.
Todavía no hemos hablado de la elección del par inicial, esto es, del sistema inicial bueno y de su solución. El método de Shub y Smale funciona una vez que el par inicial ha sido correctamente escogido.

Los mismos Shub y Smale demostraron que existe un par inicial que garantiza que casi siempre este método funcionará rápida y correctamente (esto es lo que queremos decir por bueno), aunque su resultado existencial no permitía de hecho construir un algoritmo. En este contexto, Smale incluyó la tarea de terminar este estudio en su lista de problemas para el siglo XXI. Un punto clave en el problema de Smale es que se pedía una garantía matemática de que, en general, el algoritmo debe funcionar en tiempo polinomial, que es una forma técnica de decir que sea un algoritmo eficiente.

Unos años después, Luis Miguel Pardo y el que escribe (ambos de la Universidad de Cantabria) resolvimos el problema demostrando que eligiendo el par inicial al azar mediante un determinado proceso técnico se obtiene (con altísima probabilidad) un buen candidato para comenzar la homotopía, ¡esto es, que el par inicial se debe elegir al azar! Esta introducción del azar en los algoritmos ha dado muchos frutos en otros problemas (tenemos por ejemplo el test de primalidad de Miller-Rabin, que data de 1975 pero sigue siendo utilizado hoy en día). Resulta que, bien utilizada, se puede usar para resolver el problema 17 de Smale.

Siempre que se encuentra un algoritmo que utiliza la elección de números al azar nos surge otra pregunta: ¿se podrá encontrar otro algoritmo que no necesite dicha elección? En el caso de los test de primalidad, hubo que esperar hasta 2002 para que a Agrawal, Kayal y Saxena se les ocurriese una versión del test de primalidad que no necesitase la elección de números al azar. En el caso de sistemas de ecuaciones polinomiales, todavía a nadie se le ha ocurrido una forma de hacerlo, aunque Burgisser y Cucker encontraron un algoritmo que, no necesitando estas elecciones azarosas, funciona en lo que podemos llamar tiempo casipolinomial. Esto significa que casi satisface el requerimiento habitual para considerar que un algoritmo es eficiente.

La propuesta de Burgisser y Cucker es un gran avance en este campo. Quitar el casi que aparece en su algoritmo, manteniendo la falta de necesidad de elecciones al azar, supondría encontrar un algoritmo determinista para el problema 17, todo un hito en la comprensión de la resolución de sistemas de ecuaciones polinomiales.

Para quien quiera profundizar más os dejo este trabajo de Carlos y Luis Miguel

• C. Beltrán, Luis Miguel Pardo. «Fast linear homotopy to find approximate zeros of polynomial systems» Foundations of Computational Mathematics11, issue 1 (2011), pp 95-129

que podéis encontrar en la web de Carlos junto con otros documentos interesantes.

Y para terminar, no quiero desaprovechar la oportunidad que me ofrece este post para recordar otros grandes logros de matemáticos españoles en los últimos tiempos que han aparecido en Gaussianos a modo de colaboración por parte de los propios protagonistas:

• Isabel Fernández y Pablo Mira y su invitación al ICM 2010.
• Francisco Santos y su contraejemplo para la conjetura de Hirsch.
• Javier Cilleruelo y Carlos Vinuesa y la resolución, junto a Imre Ruzsa, de la conjetura de los conjuntos generalizados de Sidon.
• Javier Fernández de Bobadilla y María Pe Pereira y la resolución de la conjetura de Nash.
• Daniel Peralta-Salas y Alberto Enciso y su resolución de la conjetura sobre la ecuación de Euler.

Este artículo sirve como contribución con la edición 2.7 del Carnaval de Matemáticas, que en esta ocasión organiza La Aventura de la Ciencia.