Un gran premio para una conjetura refutada

Simplificando un poco, podemos decir que el trabajo de un matem¨¢tico consiste en enfrentarse a conjeturas, afirmaciones de las que estamos razonablemente seguros a partir de la observaci¨®n del mundo real o de nuestro conocimiento de los objetos matem¨¢ticos, pero cuya veracidad no podemos establecer m¨¢s all¨¢ de toda duda para convertirlas en teoremas.

Un ejemplo de conjetura procedente del mundo real ---donde las matem¨¢ticas est¨¢n m¨¢s pr¨®ximas al quehacer de un f¨ªsico o un bi¨®logo--- es la llamada Conjetura de Kepler, quien propuso, en 1611, que la intuici¨®n de los fruteros es correcta y la forma m¨¢s eficaz de colocar naranjas, la que deja menos huecos libres entre ellas, son esas pir¨¢mides que uno ve en cualquier fruter¨ªa del mundo, lo que los qu¨ªmicos ---que lo encuentran en la estructura de algunos compuestos--- llaman empaquetamiento c¨²bico compacto. La ventaja del punto de vista matem¨¢tico es que no hay que limitarse a la fruta, ni siquiera a objetos tridimensionales, y estos problemas de empaquetamiento de esferas tienen m¨²ltiples aplicaciones, por ejemplo a la hora de determinar la distribuci¨®n ¨®ptima de los sat¨¦lites de comunicaciones o de las antenas de telefon¨ªa m¨®vil. A principio del siglo XXI, casi 400 a?os despu¨¦s de que se propusiese la conjetura, Thomas Hales demostr¨® que Kepler estaba en lo cierto.

Entre las conjeturas que tratan con objetos puramente matem¨¢ticos podemos se?alar la que propone que, si bien la dificultad de comprobar que un n¨²mero es primo aumenta cuando lo hace el tama?o del n¨²mero, este aumento es moderado: el grado de dificultad viene dado por un polinomio en el n¨²mero de cifras del n¨²mero. Es importante observar que no se trata de intentar descomponer el n¨²mero y, si no se puede, concluir que es primo, porque el proceso de factorizaci¨®n s¨ª que se hace r¨¢pidamente mucho m¨¢s arduo a medida que el n¨²mero crece. De hecho, que encontrar primos grandes sea f¨¢cil mientras que factorizar n¨²meros grandes es dif¨ªcil es la base del sistema de seguridad m¨¢s usado en el comercio electr¨®nico. En 2002 Manindra Agrawal, Neeraj Kayal y Nitin Saxena demostraron que, efectivamente, existe un algoritmo que permite decidir, en tiempo polin¨®mico y con absoluta certeza, si un n¨²mero es o no primo.

Otra conjetura famosa es la de Hirsch, que trata sobre objetos llamados politopos, que no son otra cosa que poliedros, pero con m¨¢s de tres dimensiones. Aparecen de manera natural cuando se trata de asignar recursos, planificar producci¨®n, organizar turnos de trabajo, dise?ar carteras de inversi¨®n o formular estrategias de mercado, y la resoluci¨®n problemas de optimizaci¨®n sobre politopos ---conocida como programaci¨®n lineal--- se ha revelado de vital importancia desde mediados del siglo XX . Es por ello importante que el tiempo necesario para resolverlos no crezca demasiado deprisa cuando crece el tama?o de los datos, M¨¢s exactamente nos gustar¨ªa que existiese un algor¨ªtmo que resolviese nuestro problema de programaci¨®n lineal tardando , como en el caso de la primalidad, s¨®lo un tiempo polin¨®mico en la dimensi¨®n d del politopo (el n¨²mero de variables involucradas) y en el n¨²mero n de caras (las restricciones que definen el politopo). La principal dificultad es que no se sabe si el di¨¢metro del politopo es polin¨®mico en n y d.

El relieve de este premio, que recae por primera vez en un espa?ol queda de manifiesto si atendemos a algunos de los anteriores premiados"

En 1957 Warren Hirsch propuso la muy razonable conjetura de que el di¨¢metro de un politopo no puede superar n-d (si queremos ser precisos, se trata del llamado di¨¢metro combinatorio, porque hinchar un politopo no afecta a la dificultad de los problemas de programaci¨®n lineal asociados).

Ante una conjetura caben dos opciones: demostrarla convirti¨¦ndola en un teorema ---como en los dos ejemplos con los que hemos empezado---, o refutarla por medio de un contraejemplo. Para sorpresa general ---dado que se pensaba que la conjetura deb¨ªa ser cierta---, Francisco Santos Leal (Valladolid, 1968), catedr¨¢tico de Geometr¨ªa y Topolog¨ªa en la Universidad de Cantabria, dio en 2010 un contraejemplo a la Conjetura de Hirsch. Este alarde de ingenio, imaginaci¨®n y destreza t¨¦cnica le ha valido ser galardonado el pasado 12 de julio con el prestigioso Premio Fulkerson, concedido conjuntamente por la Mathematical Optimization Society y la American Mathematical Society y que reconoce resultados sobresalientes en el campo de la matem¨¢tica discreta.

El relieve de este premio, que recae por primera vez en un espa?ol ---que adem¨¢s trabaja en Espa?a---, queda de manifiesto si atendemos a algunos de los anteriores premiados. Entre ellos est¨¢n los ya mencionados Hales, Agrawal, Kayal y Saxena, y tambi¨¦n Kenneth Appel y Wolfgang Haken (por su demostraci¨®n del teorema de los cuatro colores), Maria Chudnovsky, Paul Seymour, Hendrik Lenstra o L¨¢szl¨® Lov¨¢sz.

El Premio Fulkerson se concede cada tres a?os, y se pueden otorgar hasta tres premios en cada ocasi¨®n. El hecho de que, por primera vez en sus 36 a?os de existencia, en esta ocasi¨®n haya habido un ¨²nico galardonado da fe de la singular importancia del resultado de Francisco Santos.

Adolfo Quir¨®s Graci¨¢n es profesor de la Universidad Aut¨®noma de Madrid y vicepresidente de la Real Sociedad Matem¨¢tica Espa?ola.