Solución a la conjetura de Keller, un problema matemático que ha desconcertado a la ciencia 90 años

Informáticos y matemáticos de la Universidad Carnegie Mellon han resuelto la última y obstinada pieza de la conjetura de Keller, un problema de geometría que ha desconcertado a la ciencia 90 años.

Esta conjetura dice que un plano no puede ser cubierto completamente con cuadrados idénticos sin solaparse sin que al menos dos de ellos compartan uno de sus lados.

Al estructurar el rompecabezas como lo que los científicos de la computación llaman un problema de satisfacción, los investigadores resolvieron el problema con cuatro meses de frenética programación de computadoras y solo 30 minutos de computación usando un grupo de computadoras.

El equipo recurrió a un solucionador de SAT, --un programa de computadora que usa lógica proposicional para resolver problemas de satisfaciblidad (SAT)--, que ya sirvió para superar varios desafíos matemáticos antiguos, incluido el problema de triples de Pitágoras y la Factorización de Schur.

“El problema ha intrigado a muchas personas durante décadas, casi un siglo”, dijo en un comunicado el autor principal Marijn Heule --profesor de ciencias de la computación-- sobre la conjetura de Keller. “Este es realmente un escaparate de lo que se puede hacer ahora que antes no era posible”.

La conjetura de las baldosas

La conjetura, planteada por el matemático alemán Eduard Ott-Heinrich Keller, tiene que ver con las baldosas, específicamente, cómo cubrir un área con baldosas del mismo tamaño sin ningún espacio o superposición. La conjetura es que al menos dos de los mosaicos tendrán que compartir un borde y que esto es cierto para espacios de todas las dimensiones.

Es fácil demostrar que es cierto para los mosaicos bidimensionales y los cubos tridimensionales. En 1940, la conjetura había demostrado ser cierta para todas las dimensiones hasta seis. En 1990, sin embargo, los matemáticos demostraron que no funciona en la dimensión 10 o superior.

Fue entonces cuando la conjetura de Keller capturó la imaginación del coautor del estudio y también profesor de Matemáticas John Mackey, entonces estudiante de la Universidad de Hawai. Estaba intrigado porque el problema podía traducirse, utilizando la teoría de grafos discretos, a una forma que las computadoras pudieran explorar. En esta forma, llamada gráfica de Keller, los investigadores podrían buscar “camarillas”, subconjuntos de elementos que se conectan sin compartir una cara, refutando así la conjetura.

En 2002, Mackey hizo precisamente eso, descubriendo una camarilla en la dimensión ocho. Al hacerlo, demostró que la conjetura falla en esa dimensión y, por extensión, en la dimensión nueve. Eso dejó la conjetura sin resolver para la dimensión siete.

Cuando Heule llegó a la Universidad de Texas el año pasado, ya tenía la reputación de usar el solucionador SAT para resolver los problemas matemáticos pendientes.

Un solucionador de SAT requiere estructurar el problema usando una fórmula proposicional (A o no B) y (B o C), etc., para que el solucionador pueda examinar todas las variables posibles para combinaciones que satisfagan todas las condiciones.

“Hay muchas formas de hacer estas traducciones, y la calidad de la traducción por lo general hace o rompe su capacidad para resolver el problema”, dijo Heule.

Con 15 años de experiencia, Heule es experta en realizar estas traducciones. Uno de los objetivos de su investigación es desarrollar un razonamiento automatizado para que esta traducción se pueda realizar automáticamente, permitiendo que más personas utilicen estas herramientas en sus problemas.

Incluso con una traducción de alta calidad, la cantidad de combinaciones a verificar en la dimensión siete era alucinante --un número con 324 dígitos-- con una solución que no se veía por ninguna parte, incluso con una supercomputadora. Pero Heule y los demás aplicaron una serie de trucos para reducir el tamaño del problema. Por ejemplo, si una configuración de datos resultó inviable, podrían rechazar automáticamente otras combinaciones que se basaran en ella. Y dado que muchos de los datos eran simétricos, el programa podía descartar imágenes espejo de una configuración si llegaba a un callejón sin salida en una disposición.

Usando estas técnicas, redujeron su búsqueda a aproximadamente mil millones de configuraciones. Una vez que ejecutaron su código en un grupo de 40 computadoras, finalmente tuvieron una respuesta: la conjetura es cierta en la dimensión siete. Ep