CAE LA CONJETURA DEL GIRASOL
Tomemos los números del 1 al n y consideremos todas las formas de elegir algunos de ellos: hay 2ⁿ subconjuntos así. Ahora elijamos unos cuantos subconjuntos que compartan exactamente la misma parte común, y nada más. Los matemáticos llaman a esto un girasol: la parte compartida es el núcleo, y lo que queda de cada conjunto es un pétalo que no toca ningún otro pétalo.
Los girasoles son una herramienta básica de la combinatoria. El artículo enumera vínculos con los límites de ciertos circuitos lógicos, con el problema del «cap set», con la multiplicación rápida de matrices y con la teoría de la información.
Una pregunta de 1970
La pregunta más natural sobre ellos se remonta, según los autores, a un artículo de Paul Erdős de 1970. ¿Qué tamaño puede tener una colección de subconjuntos de {1, …, n} si ningún grupo de k de sus conjuntos forma un girasol?
En los años setenta, Erdős y Endre Szemerédi conjeturaron que una colección así debe ser exponencialmente más pequeña que los 2ⁿ subconjuntos posibles: como mucho cⁿ, para algún número c estrictamente menor que 2.
Durante décadas, las mejores cotas solo recortaban un poco, nunca lo suficiente para bajar la base de 2. Solo se había resuelto el caso de tres pétalos (k = 3), en 2016, gracias al gran avance sobre el problema del cap set y a una reducción debida a Alon, Shpilka y Umans.
La cota
Matija Bucić y Fankang He (Universidad de Viena) y Hyunwoo Lee (KAIST y el Institute for Basic Science, Corea del Sur) demuestran la conjetura para todo k ≥ 3. Su teorema principal: una colección sin girasol de k pétalos tiene como mucho
3 · (2 − 1/(16k³))ⁿ
miembros. La base queda justo por debajo de 2, pero es un número fijo por debajo de 2, y eso es exactamente lo que pedían Erdős y Szemerédi. Una construcción de 1997 muestra que, para k grande, el valor real no puede ser mucho menor.
De los conjuntos a los vectores
La demostración pasa por una versión del problema con vectores. Se dividen los números en n bloques de D elementos y se elige un elemento por bloque: cada elección es un vector. Varios vectores forman un girasol cuando, en cada posición, sus entradas son o todas iguales o todas distintas.
Los autores construyen después un «detector de girasoles»: una función que, sobre una colección sin girasoles, es distinta de cero solo cuando todas sus entradas son el mismo vector. El ingrediente nuevo consiste en escribir esta función, paso a paso, con polinomios de interpolación de grado bajo. Contar esos polinomios acota el tamaño de la colección (su Teorema 2). Un argumento probabilístico, con bloques aleatorios promediados sobre todos los tamaños de conjunto, traslada la cota a los conjuntos ordinarios.
Encontrada por una máquina, comprobada por otra
La declaración del artículo sobre la IA es inusualmente directa. La demostración del Teorema 2 la encontró ChatGPT 6 Astra Pro, tras una breve conversación que empezó pidiéndole que generalizara el argumento conocido para tres pétalos. Los autores necesitaban ese paso para otro objetivo: una versión inducida de un problema de grafos planteado por Szemerédi, que anuncian para una nota posterior.
El modelo escribió su demostración en el lenguaje del «slice rank». Los autores la reescribieron en el lenguaje del método polinómico, que consideran más accesible para los lectores. Afirman que verificaron todos los resultados y asumen toda la responsabilidad, y que la demostración ha sido verificada en Lean 4.35, un programa de comprobación de demostraciones, y que la verificación se publicará en el repositorio Palomar.
Lo que no resuelve
Los autores no intentaron optimizar la base. Para tres pétalos, no mejora la cota de 2017 de Naslund y Sawin, de aproximadamente 1,89. Y el problema hermano más fuerte, la conjetura del girasol de Erdős–Rado, sigue abierto: sus cotas siguen dependiendo mucho del tamaño de bloque D, que es justamente lo que ese problema prohíbe.