Matemáticos resuelven un problema de Ronald Graham que llevaba 55 años sin solución

Los matemáticos han completado la demostración de la conjetura de Ronald Graham de hace 55 años para todos los números primos lo bastante grandes. El último intervalo pendiente lo resolvieron Lisa Sauermann y Huy Tuan Pham: su nuevo trabajo explica cómo ordenar correctamente los números para que la suma sucesiva nunca vuelva a dar un valor ya obtenido. Junto con tres trabajos anteriores, la demostración cubre conjuntos de cualquier tamaño.

El problema surgió en 1971 y se formula alrededor de la aritmética modular. Es más fácil imaginar una esfera del reloj. En la recta numérica habitual, tras el 6 viene el 7, luego el 8 y así sucesivamente, mientras que en la esfera del reloj después del 11 vuelve a aparecer el 0. En la formulación matemática, el tamaño de esa esfera ficticia lo fija un número primo p. Por ejemplo, para p = 7 se usan los residuos 0, 1, 2, 3, 4, 5 y 6, tras lo cual la cuenta vuelve a empezar en cero.

Así que 3 + 4 en aritmética modular módulo 7 da 0, y 5 + 4 da 2: la suma usual es 9, pero tras dar una vuelta completa queda el residuo 2. Ese sistema es el que crea la dificultad que no existe al sumar números positivos ordinarios.

Graham propuso tomar cualquier conjunto de residuos distintos no nulos y colocarlos en algún orden. Luego hay que contar sumas parciales sucesivas: primero el primer número, luego el primero más el segundo, después los tres primeros, los cuatro primeros, y así hasta el final. La conjetura afirma que siempre se pueden reordenar los elementos de modo que ninguna de las sumas parciales obtenidas se repita.

En un ejemplo pequeño la condición se ve enseguida. Tomemos los números 1, 2 y 5 módulo 7 y dispongámoslos como 1, 2, 5. La primera suma parcial es 1, la segunda es 3 y la tercera vuelve a ser 1, porque 1 + 2 + 5 = 8 y el residuo de 8 al dividir por 7 es 1. Hay una repetición, por tanto ese orden no vale.

Ahora cambiemos el orden a 2, 1, 5. Las sumas parciales serán 2, 3 y 1. Los tres valores son distintos, por lo que el nuevo orden cumple la condición de Graham. En un conjunto pequeño es fácil encontrar la permutación adecuada a mano. La conjetura exige probar que existe un orden apropiado para cualquier conjunto permitido, por grande o incómodo que sea.

Existe otra forma de ver el problema, y es precisamente la que ayuda a entender las demostraciones. Si dos sumas parciales coincidieron, entonces los números entre ellas suman cero módulo p. Por eso, en lugar de seguir una enorme cantidad de sumas acumuladas, se puede buscar dentro de la secuencia tramos consecutivos cuya suma sea cero. Si no hay tales tramos, las sumas parciales no se repiten.

Imagínese una permutación larga de los números. En algún punto aparecen varios elementos contiguos cuya suma es cero. Todo lo acumulado antes del comienzo de ese tramo, al terminarlo, vuelve al mismo valor. La cuestión se reduce a lo siguiente: ordenar los números de modo que en ninguna parte de la secuencia aparezca un tramo nulo de ese tipo.

Es en este punto donde la formulación simple se transforma en un problema combinatorio complejo. Cuanto mayor es el conjunto, más tramos posibles hay que considerar. Además, el tamaño del propio conjunto cambia mucho la naturaleza del problema. Si hay muy pocos números en comparación con p, las opciones de colocación son relativamente pocas, pero las coincidencias aleatorias son difíciles de controlar de forma directa. Si el conjunto ocupa casi todo el círculo de residuos disponible, surge otra estructura que se puede aprovechar. Para tamaños intermedios ninguno de esos enfoques funcionaba bien durante mucho tiempo.

El primer gran caso se cerró por el lado de conjuntos muy grandes. Alp Müesser y Alexey Pokrovsky demostraron que una permutación aleatoria suele estar bastante cerca del resultado deseado. Apartaban temporalmente varios números elegidos de forma especial, mezclaban los demás y luego usaban los elementos reservados para corregir los tramos nulos detectados. El método apareció dentro de un trabajo más general sobre combinatoria.

En la otra dirección avanzaron Benjamin Bedert y Noah Kravitz. En 2024 demostraron la conjetura para conjuntos que son muy pequeños en comparación con p, ampliando considerablemente el límite conocido anteriormente. Su resultado explotó otra estructura del problema y no podía simplemente extenderse a conjuntos de tamaño intermedio.

En 2025 un grupo de matemáticos avanzó aún más la frontera por el lado de conjuntos grandes. Demostraron la existencia del orden deseado para conjuntos de tamaño no menor que cierta potencia del número total de residuos posibles. Pero entre la región cubierta por los métodos para conjuntos pequeños y la de conjuntos grandes aun quedaba una amplia brecha. Especialmente incómodos eran los conjuntos de tamaño intermedio, por ejemplo los que contienen una fracción notable de todos los números posibles.

Sauermann y Pham optaron por otro camino. En vez de intentar construir de inmediato la secuencia perfecta, los matemáticos toman un orden aleatorio y lo van corrigiendo gradualmente. Si aparece un tramo cuya suma es cero, el último elemento de ese tramo se intercambia con otro número situado más adelante. La permutación destruye el tramo problemático y permite seguir comprobando la secuencia.

Idear la corrección en sí no es difícil. Mucho más complicado es demostrar que el proceso no se atasque. Los autores identificaron tres maneras principales en que el algoritmo puede fallar. Un tramo nulo puede aparecer demasiado cerca del final de la secuencia, cuando ya no queda ningún número adecuado para el intercambio. Varios tramos problemáticos pueden amontonarse y empezar a interferir entre sí. Finalmente, corregir un tramo puede crear accidentalmente otro tramo nulo más adelante en la cadena.

Para afrontar esos tres casos a la vez, los matemáticos necesitaron anti‑concentración. El sentido del método puede explicarse sin fórmulas. Imagine que de un conjunto grande se seleccionan al azar varios números y se suman módulo p. Para la demostración es importante mostrar que el resultado de esa suma aleatoria no cae con demasiada frecuencia en un valor predeterminado, por ejemplo en 0.

Si una gran cantidad de conjuntos diferentes diera siempre la misma suma, los tramos nulos aparecerían con demasiada frecuencia y el procedimiento de corrección podría fallar. Sauermann y Pham demostraron lo contrario: las sumas aleatorias están suficientemente bien distribuidas entre los valores posibles. Ningún resultado individual alcanza una probabilidad tan grande como para que las coincidencias peligrosas sean inevitables.

Para esa estimación los autores usaron el análisis de Fourier. En este caso el método no se aplica al procesamiento de sonido o imagen, sino como una herramienta matemática para estudiar la distribución de las sumas. Permite descomponer una distribución compleja en componentes más simples y estimar hasta qué punto las sumas aleatorias pueden acumularse alrededor de un mismo valor.

A continuación los autores calcularon por separado la probabilidad de cada escenario capaz de detener las correcciones. Todas las estimaciones juntas mostraron que la probabilidad de fallo se mantiene por debajo del 100%. Para una demostración probabilística basta con ese límite: si el proceso aleatorio no falla siempre, existe al menos una permutación para la cual todas las correcciones funcionan y no hay sumas parciales repetidas.

El resultado resultó incluso más fuerte que la mera existencia. Según la valoración de los autores, su procedimiento transforma con éxito una permutación aleatoria en una adecuada al menos en el 90% de los casos en el rango de tamaños considerado. En otras palabras, las secuencias necesarias no están escondidas entre combinaciones extremadamente raras, sino que aparecen con bastante frecuencia.

El trabajo de Sauermann y Pham cerró precisamente el rango intermedio que no cedía a métodos anteriores. Si se combina el nuevo trabajo con los resultados para conjuntos pequeños y grandes, la conjetura de Graham queda demostrada para conjuntos de cualquier tamaño cuando p es un primo suficientemente grande.

Queda, sin embargo, una salvedad formal. Graham formuló la conjetura para cada número primo, sin exigir que p fuera enorme. La cadena moderna de demostraciones garantiza el resultado solo a partir de cierto valor suficientemente grande. Los autores no calcularon el umbral exacto inferior. Por tanto, un número finito de primos más pequeños queda formalmente fuera de la demostración general, aunque el problema central de 55 años para primos grandes ya está resuelto.

La historia del problema remite además a otra afición de Ronald Graham. El matemático practicaba seriamente el malabarismo y más tarde publicó trabajos sobre sus leyes matemáticas. Se ha sugerido que la idea de la conjetura pudo surgir de una pregunta semejante sobre el orden de los lanzamientos: si distintos objetos pasan distinto tiempo en el aire, ¿se puede diseñar una secuencia de lanzamientos de modo que no vuelvan simultáneamente dos objetos? Tras 55 años, la versión matemática de esa pregunta ha hallado respuesta con ayuda de la aleatoriedad, que primero genera desorden y luego ayuda a demostrar la existencia de un orden estricto.