Los primos de la conjetura de Collatz

Por Francisco R. Villatoro, el 3 febrero, 2020. Categoría(s): Ciencia • Matemáticas • Mathematics • Science ✎ 26

La conjetura de Collatz, o problema 3 x + 1, es muy famoso entre los matemáticos aficionados. Fascinante donde los haya, a día de hoy su resolución raya lo imposible. Quizás te hayas preguntado qué pasa cuando se sustituye el 3 por 5, o por 7, o por otro número primo. Se obtiene una conjetura similar si se realiza un cambio «inteligente» en la formulación del problema. Así se obtienen la conjetura de Roosendaal, o problema 5 x + 1, la conjetura de Oliveira e Silva, o problema 7 x + 1, y sus generalizaciones. Más aún, hay otros primos de estas conjeturas, como la conjetura de Barina, o problema 7 x ± 1. ¿Se podrán demostrar todas ellas con las mismas técnicas matemáticas? Quién sabe…

Estas conjeturas han sido verificadas para todos los números menores de ~ 5.7 × 1018 (3 + 1), 1016 (5 + 1), 1016 (7 + 1), y 1015 (7 x ± 1). Parecen verdaderas, pero no sabemos si lo son hasta que no haya una demostración rigurosa. Según Jeffrey C. Lagarias (Univ. Michigan), matemático experto en la conjetura de Collatz, «estos problemas son muy peligrosos porque la gente se obsesiona con ellos, cuando a día de hoy su resolución raya lo imposible». De hecho, el genial Terence Tao (Univ. California, Los Angeles) recomienda dedicar solo uno o dos días, todos los años, a pensar sobre estas conjeturas. En septiembre de 2019 logró un pequeño avance, que ha despertado mucho interés en los medios; aunque él mismo confiesa que no concibe que sea un avance significativo. La extensión del trabajo de Tao a estas otras conjeturas aún no ha sido publicado. Si eres matemático quizás te atrevas a recoger el guante. Pero en esta pieza me limitaré a presentar su definición.

Esta pieza está basada en Jeffrey C. Lagarias, «The 3x + 1 Problem and its Generalizations,» JournalThe American Mathematical Monthly 92: 3-23 (1985), doi: https://doi.org/10.1080/00029890.1985.11971528; Tomás Oliveira e Silva, «Computational verification of the 5x+1 and 7x+1 conjectures,» TOS, Universidade de Aveiro; Tomás Oliveira e Silva, «Computational verification of the 3x+1 conjecture,» TOS, Universidade de Aveiro; David Barina, «7x±1: Close Relative of Collatz Problem,» arXiv:1807.00908 [math.NT] (02 Jul 2018); Terence Tao, «The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3,» What’s New, 25 Aug 2011; Terence Tao, «Almost all Collatz orbits attain almost bounded values,» What’s New, 10 Sep 2019; y Kevin Hartnett, Un gran resultado matemático para un «problema peligroso»,» Investigación y Ciencia, 18 dic 2019; entre otras fuentes.

Esta pieza participa en el Carnaval de Matemáticas (@CarnaMat), en su septuagésima novena edición, X.6 (#CarnaMatX.6) “OAOA: Otros Algoritmos para las Operaciones Aritméticas”, organizado por @juanfisicahr en su blog «Esto no entra en el examen«.

Problema 3 x + 1: Toma un número natural positivo, si es par divídelo entre dos, si es impar multiplícalo por tres y súmale uno; si el resultado no es igual a uno, repite el proceso. La conjetura de Lothar Collatz (1937), redescubierta por Stanisław Ulam, Shizuo Kakutani, Bryan Thwaites, Helmut Hasse), entre otros, afirma que este proceso siempre acaba en un número finito de pasos. Notarás que si continúas más allá de uno entrarás en un ciclo infinito, pasando por uno, cuatro, dos, uno, cuatro, … Como vamos a generalizar este algoritmo, conviene escribirlo con símbolos matemáticos. La función de Collatz T_3(n) se define como T_3(n)=n/2, para n \equiv 0 \pmod{2}, y T_3(n)=3\,n + 1, en otro caso. La conjetura afirma que \forall n>1, \exists k>1, tal que T_3^k(n) = T_3(T_3(\cdots^{(k)}\cdots(T_3(n)))) = 1.

Problema 5 x + 1: Toma un número natural positivo, si es par divídelo entre dos, si es divisible entre tres, pero no es par, divídelo entre tres, y en otro caso multiplícalo por cinco y súmale uno; si el resultado no es igual a uno, repite el proceso. La conjetura de Eric Roosendaal (2003) afirma que este proceso siempre acaba en un número finito de pasos. La función de Collatz T_5(n) se define como T_5(n)=n/2, para n \equiv 0 \pmod{2}, T_5(n)=n/3, para n \equiv 0 \pmod{3}, y T_5(n)=5\,n + 1, en otro caso. La conjetura afirma que \forall n>1, \exists k>1, tal que T_5^k(n) = 1.

Problema 7 x + 1: Toma un número natural positivo, si es par divídelo entre dos, si es divisible entre tres divídelo entre tres, si es divisible entre cinco divídelo entre cinco, y en otro caso multiplícalo por siete y súmale uno; si el resultado no es igual a uno, repite el proceso. La conjetura de Tomás Oliveira e Silva (2003) afirma que este proceso siempre acaba en un número finito de pasos. La función de Collatz T_7(n) se define como T_7(n)=n/2, para n \equiv 0 \pmod{2}, T_7(n)=n/3, para n \equiv 0 \pmod{3}, T_7(n)=n/5, para n \equiv 0 \pmod{5}, y T_7(n)=7\,n + 1, en otro caso. La conjetura afirma que \forall n>1, \exists k>1, tal que T_7^k(n) = 1.

Problema p x + 1: Sea p un número primo. Toma un número natural positivo, si es divisible entre un número primo menor que p divídelo entre p, y en otro caso multiplícalo por p y súmale uno; si el resultado no es igual a uno, repite el proceso. La conjetura de Collatz generalizada afirma que este proceso siempre acaba en un número finito de pasos. La función de Collatz T_p(n) se define como T_p(n)=n/q, para n \equiv 0 \pmod{q}, con q < p un número primo, y T_p(n)=p\,n + 1, en otro caso. La conjetura afirma que \forall n>1, \exists k>1, tal que T_p^k(n) = 1.

Problema 7 x ± 1: Toma un número natural positivo, si es par divídelo entre dos, si su resto es uno al dividirlo por cuatro multiplícalo por siete y súmale uno, y, en otro caso, es decir, si su resto es tres al dividirlo por cuatro multiplícalo por siete y réstale uno; si el resultado no es igual a uno, repite el proceso. La conjetura de David Barina (2018) afirma que este proceso siempre acaba en un número finito de pasos. La función de Collatz T_{7\pm}(n) se define como T_{7\pm}(n)=n/2, para n \equiv 0 \pmod{2}, T_{7\pm}(n)=7\,n+1, para n \equiv 1 \pmod{4}, y T_{7\pm}(n)=7\,n-1, para n \equiv 3 \pmod{4}. La conjetura afirma que \forall n>1, \exists k>1, tal que T_{7\pm}^k(n) = 1.

Lagarias (1985) y Tao (2011) presentan un argumento intuitivo por el que la conjetura de Collatz (problema 3 x + 1) debería ser cierta. Si n es impar, entonces T_3(n)=3\,n+1 es par, y por tanto T_3^2(n)=(3\,n+1)/2; si n es par, puede ser T_3(n)=n/2, o bien impar, dando T_3^2(n)=3\,n/2+1, o bien par, dando T_3^2(n)=n/4. Sea n un número natural positivo elegido de forma aleatoria tal que su distribución de probabilidad sea uniforme módulo cuatro, es decir, tal que la probabilidad de que sea múltiplo de cuatro sea 1/4, y de que no lo sea fuese 3/4. En dicho caso, T_3^2(n) también seguirá una distribución uniforme módulo cuatro; con probabilidad 3/4 esta función incrementará el número n en un factor de 3/2, y con probabilidad 1/4 lo incrementará en un factor de 1/4. Si se expresa la magnitud (tamaño) de n de forma logarítmica, el incremento esperado de dicho tamaño tras la aplicación de la función T_3^2(n) será de

\frac{3}{4}\,\log\frac{3}{2}+\frac{1}{4}\,\log\frac{1}{4}=-\frac{1}{4}\,\log\frac{32}{27}<0,

que implica que el tamaño del número n tenderá a decrecer. Asumiendo que la conjetura es cierta hasta n-1, también lo sería para n porque en promedio será T_3^{2k}(n)<n, para k>1 suficientemente grande. Por supuesto, este argumento intuitivo no permite construir una demostración rigurosa porque solo se aplica para el comportamiento promedio, lo que no prohíbe que existan casos excepcionales que lo incumplan siempre que su medida sea nula (su probabilidad sea cero).

Este argumento intuitivo también se aplica a los problemas p x + 1, y 7 x ± 1. Animo al lector interesado a desarrollarlo por su propia cuenta, porque aún siendo un poco engorroso, no es difícil. Y esto es todo lo que quería contar en esta ocasión sobre los primos de la conjetura de Collatz.



26 Comentarios

  1. La imagen de lo que me parece que es una representación de algún lugar del conjunto de Mandelbrot ¿tiene relación y, en su caso, cuál es con las conjeturas?

    1. Obduliez:

      Que yo sepa, no hay una reformulación del enunciado de la conjetura de Collatz en términos de su fractal (sería interesante que alguien me corrigiese si es que me equivoco).

      Una observación: En la entrada en «Gaussianos» que adjunta Juan Carlos, un lector de seudónimo «AM» menciona (en los comentarios) que si el fractal fuese simplemente conexo y simétrico respecto al eje real, entonces la conjetura sería cierta. No creo que eso sea cierto, no sigo su argumento (y no he visto nunca dicha afirmación en un artículo serio). Debe notarse que en el caso de un espacio con dimensión «fractal» hay que tener cuidado con lo que se entiende por «simplemente conexo». La teoría del grupo fundamental que se encuentra en cualquier texto de topología algebraica requiere por lo menos que el espacio en donde se encajan los círculos (cuyas clases de homotopia definirán el grupo fundamental de dicho espacio) tengan por lo menos el tipo de homotopia de un CW complejo y eso es problemático si el espacio en cuestión tiene dimensión fractal. No quiero dar a entender que no se pueda definir análogos del grupo fundamental en espacios más generales, sólo quiero señalar que el argumento de los comentarios parece malo por obviar esta clase de cosas.

      Saludos.

    2. Obduliez, como con todo método iterativo se puede obtener un fractal extendiendo la función de Collatz al plano complejo. Hay varias opciones. El fractal que muestro en mi pieza es de Jeffrey P. Dumont, Clifford A.Reiter, «Visualizing generalized 3x+1 function dynamics,» Computers & Graphics 25: 883-898 (2001), doi: https://doi.org/10.1016/S0097-8493(01)00129-7 [PDF]. Se usa una variante de la formulación de Riho Terras, Acta Arithmetica (1976), T3(z)=(3^m(z)*x+m(z))/2, donde m(z)=mod(int(|z|),2), es decir, 0 si la parte entera del módulo de z es par, y 1 si es impar; en concreto, Dumont y Reiter sustituyen m(z) = sin²(π z/2).

      Hay otros fractales propuestos en la literatura, como Joseph L. Pe, «The 3x+1 fractal,» Computers & Graphics 28: 431-435 (2004), doi: https://doi.org/10.1016/j.cag.2004.03.010; Wang Xingyuan, Yu Xuejing, «Visualizing generalized 3x + 1 function dynamics based on fractal,» Applied Mathematics and Computation 188: 234-243 (2007), doi: https://doi.org/10.1016/j.amc.2006.07.168; etc.

      Se ha propuesto usar el análisis de los sistemas dinámicos detrás de estos fractales para atacar la conjetura, por ejemplo, Pablo Castañeda, «A dynamical approach towards Collatz conjecture,» arXiv:1910.08497 [math.DS] (18 Oct 2019), https://arxiv.org/abs/1910.08497 .

    1. Ramiro, Alex Kontorovich es un experto en esta conjetura (habiendo publicado artículos con Lagarias), pero la línea de ataque que destacas, buscar un contraejemplo usando modelos estocásticos, es muy poco prometedora; en este tipo de problemas, demostrar la existencia de un contraejemplo sin construirlo de forma explícita es imposible. Los contraejemplos, si existen, son de «medida cero» para cualquier «medida» concebible en los números naturales positivos y con modelos estocásticos solo se podría demostrar que existe un contraejemplo con probabilidad uno, lo que no resuelve la conjetura (como bien sabes).

      1. Ostras! ¿Probar que existe un contraejemplo con probabilidad uno no sirve? ¿No estaríamos probando que existe un contraejemplo sí o sí y por lo tanto es falsa?

        1. Estimado Pedro:

          Francis está en lo correcto; demostrar que la probabilidad de que un enunciado sea correcto es uno no implica que dicha sentencia sea correcta.

          Contraejemplo: Suponga que Usted elige un número real al azar y que este resulta ser un número entero e imagine que yo pretendo demostrarle que dicho número entero es irracional de la siguiente manera: «Puesto que la probabilidad de elegir un número irracional al azar en los números reales es uno (hecho que se sigue de la densidad de los irracionales en los reales) concluyo que el número entero elegido por Pedro es irracional». Claramente esto es absurdo.

          Un saludo Pedro.

        2. Pedro:

          La clave no es la idea de «infinitud», es «medida» (de la cual el concepto de «probabilidad» es un caso particular). «Medida» es una abstracción de la idea de tamaño y «σ-algebra» (estructura necesaria para definir «medida») abstrae el uso de patrones de medida. Dada la σ-algebra de Borel en el plano (cuyos elementos pueden tomarse como cuadrados abiertos) se dice que un conjunto Ω del plano tiene «medida cero» si «tiene menor área que cualquier cuadrito»; es decir, si dado cualquier número δ>0 puedes cubrir a Ω con un número contable de cuadritos cuya suma de áreas es menor que δ.

          Puedes probar fácilmente que los números enteros o racionales tienen medida cero en los reales Hint: Tú σ-algebra serán los intervalos cerrados en la línea real [objetos con longitud] y necesitarás el argumento diagonal de Cantor

          Con lo anterior puedes notar que el concepto de probabilidad (medida) se trata de asignar «tamaños» a ciertos espacios (respecto a un patrón de medida) pero esto no tiene relación directa con los posibles valores de verdad de enunciados sobre dichos espacios.

          Un video sobre una bonita aplicación de la teoría de la medida a la música https://www.youtube.com/watch?v=cyW5z-M2yzw

          Un hilo en math stack exchange sobre comportamientos paradójicos en teoría de la probabilidad
          https://math.stackexchange.com/questions/2140493/counterintuitive-examples-in-probability
          Saludos.

      2. Gracias por el comentario Francis; estoy en total acuerdo en que es muy poco prometedor lo que se propone en el hilo. Simplemente quise colocarlo porque me pareció muy linda la analogía precisa de las órbitas del problema 3x+1 con el movimiento browniano y la lógica con la que Conway demostró la indecibilidad de algunas generalizaciones y pensé que era buena idea compartirlo; me deslumbró la idea de pensar variantes del enunciado de Collatz como máquinas de Turing ejecutando programas (órbitas 3x+1) sólo eso.

        Lamento si causé ruido o desvié el tema de la entrada.

        Gran entrada.

  2. Es una buena forma de dejar a un incrédulo con un euro en el bolsillo.
    Si es par me das la mitad , pero piensa que si es impar te lo multiplico por tres y le sumo uno, hay esta el truco.

  3. Hola, he tenido que hacer un pequeño script para entenderlo del todo. Ahora si.
    Impresionante, yo creo que no hay quien lo pare.
    Aunque para mi los números empiezan en el 0 y acaban en el 9.

  4. Ostras. Menos mal, que me lo dices.
    Ya me estaba volviendo loco.
    Pero se pueden usar para cosas similares. Juegos etc. creo claro.

    Un abrazo y muchas gracias.

  5. Como esto va de Conjeturas me atreveré ha decir.

    Explicación Sencilla para la conjetura de Fermat.
    He observado que las ternas pitagóricas a la potencia de 2
    a*a + b*b = z*z

    Cumplen con una característica fácil de comprobar.
    z*z/b*b + z*z/a*a  =  z*z/b*b  *  z*z/a*a  
     

    Que es lo mismo que decir:

    X + Y = X * Y 
    o si se prefiere
    X + X = X * X

    El único numero entero que lo cumple es el 2

    2 + 2 = 2 * 2

    Al no ser posible satisfacer esa condición por ningún otro numero solo el 2
    Explica que no existan ha ninguna otra potencia.

    Sencillo.

  6. Es interesante, aunque he buscado información en español dese hace tiempo no conocía alguna generalización de la conjetura de Collatz. Por desgracia también me llevará a replantearme algunas conjeturas y revisar un borrador de artículo que ya había enviado.

    De todas formas dejo aquí un hilo sobre otra extensión de la conjetura de Collatz. Mi conjetura difiere en dos situaciones a estas conjeturas 1) cambia el 3n+1 por 3n+b con b impar y dice quedado cualquier número entero se generará siempre algún ciclo. Este ciclo no tiene que ser único de echo al parecer mientras mayor sea b, mayor será el ciclo:

    https://twitter.com/Mlver_Historias/status/1234292662381039617

  7. Ok, ok no había leído bien las conjeturas 5x+1 y 7x+1, por eso pensé que tenia conflictos con unas conjeturas que he desarrollado, pero todo lo contrario. Mis conjeturas siguen siendo válidas solo que estas son mas rebuscadas, creo que me dará algo de trabajo pero puedo trabajar en ambas. Respecto a la px+1, uff esa la veo mucho mas complicada, ni siquiera sé como plantearla :S

Deja un comentario