El aprendizaje autom¨¢tico ayuda a atacar problemas matem¨¢ticos cl¨¢sicos

El problema de Hadwiger-Nelson es posiblemente uno de los m¨¢s conocidos del ¨¢rea de la geometr¨ªa discreta. Se trata de la siguiente cuesti¨®n: ?cu¨¢l es el n¨²mero m¨ªnimo de colores que se necesitan para pintar el plano, de tal modo que siempre, al tomar dos puntos cualesquiera, con una distancia de una unidad entre ellos, estos hayan sido pintados con colores distintos? Aun siendo una pregunta aparentemente inocente, lleva sin respuesta m¨¢s de 70 a?os. Sin embargo, gracias a herramientas de aprendizaje autom¨¢tico, recientemente se ha conseguido avanzar en su comprensi¨®n.

Hasta el momento, se sabe que el n¨²mero de colores necesarios puede ser cinco, seis o siete. Para estudiar el n¨²mero m¨ªnimo de colores necesarios, basta con encontrar configuraciones concretas de puntos en el plano que no puedan pintarse con un n¨²mero ¨Cllam¨¦mosle n¨C de colores y cumplir la propiedad indicada. As¨ª, sabemos que necesitamos m¨¢s, al menos, n+1 colores para pintar el plano completo ¨Cque incluye ese dibujo espec¨ªfico¨C, si queremos que se verifique la propiedad.

En primer lugar, es f¨¢cil ver que, como m¨ªnimo, hacen falta tres colores. Efectivamente, tomando una disposici¨®n tan sencilla como los tres v¨¦rtices de un tri¨¢ngulo equil¨¢tero cuyo lado mide uno, ya necesitamos tres colores para colorearlos, de forma que no haya dos v¨¦rtices adyacentes con el mismo color ¨Csi no, estos puntos no cumplir¨ªan la propiedad buscada: estar¨ªan a distancia 1 y tendr¨ªan el mismo color¨C.

Refinando este tipo de argumento, a principios de los a?os 60 del siglo pasado, los hermanos Leo y William Moser encontraron una configuraci¨®n concreta de solo siete puntos del plano que necesita al menos cuatro colores para cumplir la propiedad que queremos, lo que demuestra que el n¨²mero m¨ªnimo es cuatro. M¨¢s recientemente, en el a?o 2018, el matem¨¢tico aficionado Aubrey de Grey encontr¨® una configuraci¨®n con m¨¢s de 1000 puntos del plano en la que era necesario, como m¨ªnimo, usar cinco colores para que se cumpliera la condici¨®n deseada.

Adem¨¢s, se sabe que el n¨²mero de colores no puede ser m¨¢s que siete, porque conocemos estrategias para colorear con estos colores el plano que consiguen nuestro objetivo. Por ejemplo, basta tomar una teselaci¨®n en forma de panal de abejas y pintar un hex¨¢gono de un color y los seis adyacentes de colores diferentes. Como el di¨¢metro de cada hex¨¢gono es inferior a ?, dos puntos cualesquiera a distancia, uno caen siempre en hex¨¢gonos diferentes, adyacentes, por tanto, pintados de diferente color.

Pero esto no resuelve el misterio, podr¨ªa haber otra coloraci¨®n, que todav¨ªa no conozcamos, que requiera menos colores y siga cumpliendo la propiedad. As¨ª pues, la respuesta puede ser cinco, seis o siete y, de momento, nadie sabe c¨®mo resolver este enigma.

Para seguir avanzando en la investigaci¨®n, una estrategia habitual en matem¨¢ticas es imponer restricciones m¨¢s d¨¦biles y resolver el problema resultante. Esto, muchas veces, permite encontrar enfoques para solucionar la pregunta original. En nuestro caso, para estudiar el problema de Hadwiger Nelson d¨¦bil, analizamos qu¨¦ pasa si permitimos que algunos de los puntos pintados de un mismo color est¨¦n a una distancia diferente a uno. Para ello, introducimos la noci¨®n de configuraci¨®n v¨¢lida de una coloraci¨®n del plano de n colores, con distancias (d1, d2, ¡­ dn) asociadas a cada color.

Por ejemplo, si n=4, los colores son azul, verde, amarillo y naranja, y las distancias 1,5 ¨Casociada al color azul¨C, 0,2 ¨Cal verde¨C, 1 ¨Cal amarillo¨C, 3,7 ¨Cal naranja¨C, una configuraci¨®n v¨¢lida con estos valores es un conjunto de puntos en los que toda pareja de puntos coloreada con el mismo color est¨¢ a una distancia mayor que la distancia asociada a ese color. En el ejemplo, no puede haber dos puntos azules a menos de 1,5 de distancia o dos verdes a menos de 0,2.

As¨ª, encontrar una configuraci¨®n v¨¢lida de seis colores con distancias asociadas (1,1,1,1,1,1) supondr¨ªa demostrar que la respuesta al problema de Hadwiger-Nelson es, como mucho, seis. Encontrar una configuraci¨®n de cinco colores y con distancias (1,1,1,1,1) ser¨ªa incluso mejor, ya que resolver¨ªa completamente el problema. Y, aun siendo menos ambiciosos, hallar configuraciones de este tipo permite aumentar nuestro conocimiento sobre el problema general.

Recientemente, un equipo de investigadores del Zuse Institute Berlin (ZIB) y de la Technische Universit?t Berlin (TU Berlin) han obtenido un avance en esta direcci¨®n. Konrad Mundinger, Sebastian Pokutta, Christoph Spiegel y Max Zimmer han dado con una configuraci¨®n v¨¢lida de seis colores (1,1,1,1,1,d), donde el valor de d est¨¢ entre 0,354 y 0,657. Dicho de otro modo, los puntos coloreados con los cinco primeros colores mantienen la condici¨®n con una distancia unidad, mientras que para el sexto color se relaja la condici¨®n: puede haber un par de puntos pintados de este color a una distancia menor, entre 0,354 y 0,657. Este resultado mejora resultados previos del a?o 1996, ampliando el margen de posible elecci¨®n para d.

Pero, adem¨¢s, lo que es realmente interesante es el papel que ha jugado el aprendizaje autom¨¢tico en la obtenci¨®n de este resultado. Su idea, a grandes rasgos, ha sido entrenar una red neuronal para encontrar representaciones que cumpliesen las condiciones deseadas, intentando que el valor de d fuera lo mayor posible. Este tipo de redes neuronales no son capaces de resolver el problema de manera exacta, sino que obtienen propuestas de soluciones aproximadas, testeando un enorme n¨²mero de combinaciones posibles, lo que resulta una tarea inalcanzable para el ser humano.

Entonces, la red neuronal funciona a modo de ¡°or¨¢culo aproximado¡±, y es trabajo de los investigadores interpretar la informaci¨®n generada y dar forma a esta v¨ªa de exploraci¨®n en una posible soluci¨®n. Con estas t¨¦cnicas los autores han sido capaces de obtener diversas construcciones que mejoran todas las conocidas hasta el momento. Por ejemplo, han construido una teselaci¨®n de tipo peri¨®dica (en la imagen) que usa seis colores, en la que el sexto color, el rojo, es el que cumple con las condiciones m¨¢s laxas.

Este tipo de t¨¦cnicas computacionales son muy prometedoras y es posible que en el futuro permitan tratar otros problemas que hoy en d¨ªa son inabordables, como, por ejemplo, el estudio del mismo problema en el espacio ¨Cen lugar del plano¨C, o el problema de Hadwiger-Nelson en su totalidad.

Juanjo Ru¨¦ es profesor agregat del Departamento de Matem¨¢ticas de la Universitat Polit¨¨cnica de Catalunya (UPC), miembro del Instituto de Matem¨¢ticas de la UPC (IMTech) e investigador adscrito al Centre de Recerca Matem¨¤tica (CRM).

?gata A. Tim¨®n G Longoria, coordinadora de la Unidad de Cultura Matem¨¢tica del ICMAT.

Caf¨¦ y Teoremas es una secci¨®n dedicada a las matem¨¢ticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matem¨¢ticas (ICMAT), en la que los investigadores y miembros del centro describen los ¨²ltimos avances de esta disciplina, comparten puntos de encuentro entre las matem¨¢ticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar caf¨¦ en teoremas. El nombre evoca la definici¨®n del matem¨¢tico h¨²ngaro Alfred R¨¦nyi: ¡°Un matem¨¢tico es una m¨¢quina que transforma caf¨¦ en teoremas¡±.

Edici¨®n, traducci¨®n y coordinaci¨®n: ?gata Tim¨®n Garc¨ªa-Longoria. Es coordinadora de la Unidad de Cultura Matem¨¢tica del Instituto de Ciencias Matem¨¢ticas (ICMAT)