¿CUÁNTOS COLORES PARA PINTAR EL ESPACIO? CON UNA REGLA TÍPICA, NO MÁS DE 2d
Toma cada punto de un plano y dale un color a cada uno. Una sola regla: dos puntos separados exactamente una unidad nunca pueden tener el mismo color. ¿Cuál es el menor número de colores que funciona?
Es el problema de Hadwiger-Nelson, que data de 1950 y es, en palabras de los autores, uno de los problemas abiertos más famosos de la geometría discreta. Durante mucho tiempo se supo que la respuesta estaba entre 4 y 7. Un avance reciente elevó la cota inferior a 5. La respuesta exacta sigue siendo desconocida.
Cambiar la regla
La distancia no tiene por qué medirse con una regla corriente. Los matemáticos definen muchas otras normas —maneras de medir longitudes—, cada una descrita por su «bola unidad», el conjunto de puntos a distancia como máximo 1 del centro. Para la distancia habitual es una bola redonda; para otras normas puede ser cualquier forma convexa simétrica respecto a su centro.
Para cualquier norma en el plano, la respuesta al problema de coloración está entre 4 y 7. En d dimensiones, es como mucho exponencial en d para cualquier norma, y para muchas normas naturales —incluida la euclídea habitual— es también al menos exponencial: el número de colores se dispara a medida que crece la dimensión.
¿Es esa explosión la regla? Noga Alon (Universidad de Princeton y Universidad de Tel Aviv), Matija Bucić (Universidad de Viena) y James Davies (Universidad de Leipzig) estudiaron una norma típica. No existe una manera natural de elegir una norma «al azar», así que recurren a una noción topológica: una propiedad se cumple para una norma típica si las excepciones forman un conjunto despreciable («magro»). Un trabajo anterior de Alon, Bucić y Lisa Sauermann había demostrado que una norma típica necesita como mucho 2ᵈ colores, y se preguntaba cuán cerca estaba eso de la verdad.
Lineal, no exponencial
La respuesta: muy lejos. El nuevo artículo demuestra que
- para una norma típica en el espacio de d dimensiones, 2d colores bastan siempre;
- esto es lo mejor posible: un conjunto abierto de normas requiere al menos 2d colores. Así que algunas normas necesitan exactamente 2d.
En diez dimensiones, una norma típica necesita como mucho veinte colores, mientras que la distancia habitual necesita un número que crece de forma exponencial. Según los autores, es también la primera vez que el número cromático se determina con exactitud para una norma «estrictamente convexa» en cualquier dimensión d.
La cota inferior usa una trampa ingeniosa. Se buscan 2d puntos situados todos exactamente a una unidad unos de otros, salvo dos, a y b, que están a media unidad. Se añade la imagen especular de toda la configuración respecto a a. Con menos de 2d colores, tanto b como su imagen especular se verían obligados a tomar el color de a, pero están exactamente a una unidad el uno del otro. Contradicción. Un lema de estabilidad muestra que esta configuración sobrevive a cualquier pequeña modificación de la norma.
Un corredor solitario en muchas dimensiones
La cota superior colorea cada punto según dónde cae una proyección bien elegida del mismo, en franjas de anchura 1/(2d). Para que funcione hace falta un ingrediente clave que los autores describen como una versión matricial y en muchas dimensiones de la famosa conjetura del corredor solitario (lonely runner conjecture):
sup sobre x de minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)
donde ‖t‖ es la distancia de t al entero más cercano, para n vectores cualesquiera aᵢ en k dimensiones de los cuales cualesquiera k son independientes. Este enunciado también resuelve una conjetura de I. J. Schoenberg de 1978 sobre la «obstrucción de la visión» (view obstruction) —una pregunta sobre lo gruesas que deben ser unas placas periódicas para bloquear toda visión hacia el infinito—, que los autores consideran uno de los problemas abiertos más clásicos del área, así como una conjetura relacionada de Henze y Malikiosis.
La máquina en los agradecimientos
Los autores son explícitos: «ChatGPT 6 Pro nos proporcionó la demostración del último ingrediente que necesitábamos en la prueba del Teorema 1, a saber, la del Lema 7, tras una discusión prolongada», en la que habían compartido sus propias observaciones, incluida la idea de la inducción y la estrategia general. «El argumento de la cota inferior también se encontró con la ayuda de ChatGPT 6 Pro».
Quedan preguntas. El valor exacto 2d está demostrado en un conjunto abierto de normas, no para todas las típicas. Y para la distancia euclídea ordinaria, los autores esperan estrictamente más de 2d colores en todas las dimensiones, algo ya conocido en las dimensiones 2, 4, 7, 8 y de 9 en adelante, pero todavía abierto en las dimensiones 3, 5 y 6.