La conjetura de Collatz

La conjetura de Collatz, también llamada problema 3n + 1, es quizá el problema abierto de matemáticas más fácil de enunciar. Se toma un número entero positivo cualquiera. Si es par, se divide entre dos. Si es impar, se multiplica por tres y se le suma uno. Con el resultado se repite lo mismo, una y otra vez. La conjetura afirma que, empiece donde empiece, la sucesión acaba siempre llegando a 1, donde entra en el ciclo 1, 4, 2, 1 y se queda dando vueltas. Se ha comprobado con ordenador para todos los números hasta cifras de veintiún dígitos, y nadie ha encontrado una excepción. Tampoco nadie ha conseguido demostrar que no la haya.

Un ejemplo corto: desde el 6 se va al 3, del 3 al 10, al 5, al 16, al 8, al 4, al 2 y al 1, en ocho pasos. Pero el comportamiento no es siempre tan manso. El 27, que parece inofensivo, necesita 111 pasos para llegar a 1, y por el camino sube hasta 9.232, más de trescientas veces su valor inicial, antes de desplomarse. El 97 tarda 118 pasos; el 871, 178. Números vecinos se comportan de manera completamente distinta: el 28 llega a 1 en 18 pasos, el 27 en 111. Esa mezcla de una regla trivial con trayectorias que parecen aleatorias es lo que ha convertido el problema en una obsesión para aficionados y profesionales.

El problema lleva el nombre de Lothar Collatz, un matemático alemán que se lo planteó en 1937 y que lo difundió de palabra en congresos durante años. Circuló sin publicarse, y por eso tiene muchos nombres: problema de Siracusa, porque se estudió en la universidad de ese nombre en Nueva York; problema de Kakutani o de Ulam, por los matemáticos que lo contaron; problema de Hasse. Jeffrey Lagarias, que en 1985 escribió el repaso que todavía sirve de referencia, recoge la historia y la famosa frase de Paul Erdős sobre él: «Las matemáticas todavía no están preparadas para problemas así».

Hay un argumento sencillo que hace creíble la conjetura. Cada paso impar multiplica el número por algo más de tres, pero el resultado, $3n + 1$, siempre es par, así que va seguido al menos de una división entre dos. Si se supone que, a la larga, los números pares e impares aparecen como si se tirara una moneda, cada paso impar va seguido en promedio de dos divisiones, y el efecto medio de ese bloque es multiplicar por $3/4$. Una trayectoria típica debería ir encogiendo. El argumento es convincente y falso como demostración: no hay ninguna garantía de que un número concreto se comporte como la media, y precisamente eso es lo que habría que demostrar.

La figura de abajo muestra lo que ese argumento predice y lo que no. Los tiempos de parada, los pasos hasta llegar a 1, crecen con el tamaño del número, más o menos en proporción a su logaritmo, pero con una dispersión enorme y una estructura curiosa: la nube forma bandas, porque números que se juntan pronto en la misma trayectoria comparten el resto del recorrido. Entre los números hasta 10.000, el que más tarda es el 6.171, con 261 pasos. La trayectoria del 27 se ve también en la figura superior: un ascenso irregular en dientes de sierra, un pico y una caída casi limpia, porque cuando se llega a una potencia de dos el descenso es directo.

Los resultados demostrados se han acercado a la conjetura sin alcanzarla. En 1976 Riho Terras probó que casi todos los números acaban por bajar de su valor inicial: la proporción de los que no lo hacen tiende a cero. En 2019 Terence Tao dio un paso mucho más fuerte, publicado en 2022: casi todas las trayectorias acaban alcanzando valores casi acotados. Dicho sin tecnicismos, para cualquier función que crezca hacia infinito, por despacio que sea, casi todos los números acaban cayendo por debajo de ella. Tao no demostró que se llegue a 1, y el «casi todos» deja fuera un conjunto de números que podría contener excepciones, pero es el resultado más cercano que se tiene.

Una demostración completa tendría que descartar dos cosas: que exista otro ciclo, distinto de 1, 4, 2, 1, y que exista una trayectoria que crezca sin límite. Sobre los ciclos se sabe bastante: cualquier otro ciclo tendría que ser larguísimo, con decenas de millones de pasos como mínimo, según cotas que mejoran cada vez que se amplía la verificación por ordenador. Sobre las trayectorias divergentes se sabe muy poco. La verificación numérica sigue avanzando: en 2021 David Barina publicó la comprobación de todos los números por debajo de $2^{68}$, unos 295 trillones, con técnicas que aprovechan tarjetas gráficas y descartan en bloque clases enteras de números.

Hay una razón de fondo para pensar que el problema es difícil de verdad, y no solo que nadie ha encontrado el truco. En 1972 John Conway estudió las reglas del mismo tipo, en las que el número se multiplica y se le suma algo según el resto que deja al dividir por un número fijo. Demostró que, para esa familia en general, la pregunta de si una trayectoria acaba llegando a un valor dado es indecidible: no existe ningún algoritmo que la responda para todas las reglas. Es el mismo tipo de límite que Alan Turing encontró para los programas de ordenador con su máquina de Turing. La regla $3n + 1$ es un caso concreto, y podría resolverse, pero vive en una familia donde el caso general no tiene solución.

Una consecuencia curiosa es que la conjetura se usa como banco de pruebas. Es un buen ejercicio de recursividad para enseñar a programar, y ha servido para poner a prueba demostradores automáticos y técnicas de reescritura, sin éxito por ahora. Mientras tanto, lo único seguro es lo que muestran las figuras: una regla que cabe en una línea produce trayectorias que nadie sabe predecir, y los números, uno tras otro, siguen llegando a 1.