Conjetura de Collatz

La conjetura ha sido comprobada por ordenador para todos los valores iniciales hasta 2 ⁷¹ ≈2,36 × 10 ²¹ . Todos los valores probados hasta ahora convergen a 1. ^{[ 12 ]}

Esta evidencia computacional aún no es una prueba rigurosa de que la conjetura sea cierta para todos los valores iniciales, ya que se pueden encontrar contraejemplos al considerar enteros positivos muy grandes, como en el caso de la conjetura de Pólya y la conjetura de Mertens , que fueron refutadas .

Sin embargo, tales verificaciones pueden tener otras implicaciones. Ciertas restricciones sobre cualquier ciclo no trivial, como límites inferiores para la longitud del ciclo, pueden demostrarse en función del valor del término más bajo del ciclo. Por lo tanto, las búsquedas computacionales para descartar ciclos con un término más bajo pequeño pueden reforzar estas restricciones. ^{[ 13 ] [ 14 ] [ 15 ]}

Si se consideran únicamente los números impares en la secuencia generada por el proceso de Collatz, entonces cada número impar es, en promedio , 3/4 del anterior . [ ^{16 ] (} Más precisamente, la media geométrica de las razones de los resultados es 3/4 ) . Esto proporciona un argumento heurístico de que toda secuencia de Hailstone debería disminuir a largo plazo, aunque esto no es evidencia en contra de otros ciclos, sino solo en contra de la divergencia. Sin embargo , el argumento no es una prueba, ya que asume que las secuencias de Hailstone se componen de eventos probabilísticos no correlacionados. (Sí establece rigurosamente que la extensión 2-ádica del proceso de Collatz tiene dos pasos de división por cada paso de multiplicación para casi todos los valores iniciales 2-ádicos).

Como demostró Riho Terras , casi todo entero positivo tiene un tiempo de parada finito. ^{[ b ] [ 17 ]} En otras palabras, casi toda secuencia de Collatz alcanza un punto que está estrictamente por debajo de su valor inicial. La demostración se basa en la distribución de vectores de paridad y utiliza el teorema del límite central .

En 2019, Terence Tao mejoró este resultado al demostrar, utilizando la densidad logarítmica , que casi todas las órbitas de Collatz (en el sentido de la densidad logarítmica) descienden por debajo de cualquier función dada del punto de partida, siempre que esta función diverja al infinito, por muy lentamente que lo haga. En respuesta a este trabajo, Quanta Magazine escribió que Tao «obtuvo uno de los resultados más significativos sobre la conjetura de Collatz en décadas». ^{[ 9 ] [ 18 ]}

En una demostración asistida por computadora , Krasikov y Lagarias demostraron que el número de enteros en el intervalo [1, x ] que eventualmente llegan a 1 es al menos igual a x ^0.84 para todo x suficientemente grande . ^{[ 19 ]}

A partir de 2025, el límite más conocido sobre la duración del ciclo es217 976 794 617 (355 504 839 929 sin atajo). ^{[ 12 ]} En 1993, Eliahou demostró que el período p de cualquier ciclo no trivial es de la forma $${\displaystyle p=301994a+17087915b+85137581c}$$ donde a , b y c son enteros no negativos, b ≥ 1 y ac = 0. Este resultado se basa en la expansión ^en fracción continua simple de ln 3 / ln 2. ^{[ 14} ]

Un k -ciclo es un ciclo que se puede particionar en k subsecuencias contiguas, cada una de las cuales consiste en una secuencia creciente de números impares, seguida de una secuencia decreciente de números pares. ^{[ 15 ]} Por ejemplo, si el ciclo consiste en una única secuencia creciente de números impares seguida de una secuencia decreciente de números pares, se denomina 1-ciclo .

Steiner (1977) demostró que no hay ningún 1-ciclo aparte del trivial (1; 2) . ^{[ 20 ]} Simons (2005) utilizó el método de Steiner para demostrar que no hay ningún 2-ciclo. ^{[ 21 ]} Simons y de Weger (2005) extendieron esta demostración hasta 68-ciclos; no hay ningún k -ciclo hasta k = 68. [ ^{15 ] Hercher} extendió aún más el método y demostró que no existe ningún k -ciclo con k ≤ 91. [ ^{22 ] A} medida que continúan las búsquedas exhaustivas por computadora, se pueden descartar valores de k mayores . Para expresar el argumento de manera más intuitiva; no tenemos que buscar ciclos que tengan menos de 92 subsecuencias, donde cada subsecuencia consiste en ascensos consecutivos seguidos de descensos consecutivos.

Existe otro enfoque para demostrar la conjetura, que considera el método ascendente de crecimiento del llamado grafo de Collatz , un grafo definido por la relación inversa.$${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{si }}n\equiv 0,1,2,3,5\\\left\{2n,{\frac {n-1}{3}}\right\}&{\text{si }}n\equiv 4\end{cases}}{\pmod {6}}.}$$

Así pues, en lugar de probar que todos los enteros positivos conducen finalmente a 1, podemos intentar probar que 1 conduce en sentido inverso a todos los enteros positivos. Para cualquier entero n , n ≡ 1 (mod 2) si y solo si 3 n + 1 ≡ 4 (mod 6) . De forma equivalente, n − 1 / 3 ≡ 1 (mod 2) si y solo si n ≡ 4 (mod 6) . Conjeturalmente, esta relación inversa forma un árbol para los enteros positivos, excepto por el bucle 1–2–4 (el inverso del bucle 4–2–1 de la función f sin modificar definida en la sección «Planteamiento del problema » de este artículo).

Cuando la relación 3 n + 1 de la función f se reemplaza por la relación de "atajo" sustituto común ⁠ 3 n + 1 / 2 ⁠ , el gráfico de Collatz se define por la relación inversa, $${\displaystyle R(n)={\begin{cases}\{2n\}&{\text{si }}n\equiv 0,1\\\left\{2n,{\frac {2n-1}{3}}\right\}&{\text{si }}n\equiv 2\end{cases}}{\pmod {3}}.}$$

Para cualquier entero n , n ≡ 1 (mod 2) si y solo si ⁠ 3 n + 1 / 2 ⁠ ≡ 2 (mod 3) . De forma equivalente, ⁠ 2 n − 1 / 3 ⁠ ≡ 1 (mod 2) si y solo si n ≡ 2 (mod 3) . Conjeturadamente, esta relación inversa forma un árbol para enteros positivos excepto por un bucle 1-2 (el inverso del bucle 1-2 de la función f(n) revisada como se indicó anteriormente).

Alternativamente, reemplace el 3 n + 1 con ⁠ n ′ / H ( n ′ ) ⁠ donde n ′ = 3 n + 1 y H ( n ′ ) es la mayor potencia de 2 que divide a n ′ (sin resto ). La función resultante f mapea de números impares a números impares. Ahora supongamos que para algún número impar n , aplicar esta operación k veces produce el número 1 (es decir, f ^k ( n ) = 1 ). Entonces en binario , el número n se puede escribir como la concatenación de cadenas w _k w _{k −1} ... w ₁ donde cada w _h es un extracto finito y contiguo de la representación de ⁠ 1 / 3 ^h ⁠ . ^{[ 23 ]} La representación de n, por lo tanto, contiene los repetitivos de 1/3 h , donde cada repetidor se rota opcionalmente y luego se replica hasta un número finito de bits. Esto solo ocurre en binario. ^{[ 24 ]} Conjeturalmente, toda cadena binaria ^s que termina con un '1' puede ser alcanzada por una representación de esta forma ( donde podemos agregar o eliminar '0' iniciales a s ). 

Las aplicaciones repetidas de la función de Collatz pueden representarse como una máquina abstracta que maneja cadenas de bits . La máquina realizará los siguientes tres pasos en cualquier número impar hasta que solo quede un 1 :

1. Agregue 1 al extremo (derecho) del número en binario (dando 2 n + 1 );
2. Suma esto al número original mediante suma binaria (dando 2 n + 1 + n = 3 n + 1 );
3. Elimine todos los ceros finales ( es decir, divida repetidamente por 2 hasta que el resultado sea impar).

 111 111 1 1011 0 1011 1 10001 0 10001 1 1101 00 1101 1 101 000 101 1 1 0000

Para esta sección, considere la forma abreviada de la función de Collatz. $${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{si }}n\equiv 0\\{\frac {3n+1}{2}}&{\text{si }}n\equiv 1\end{cases}}{\pmod {2}}.}$$

Si P(...) es la paridad de un número, es decir P(2 n ) = 0 y P(2 n + 1) = 1 , entonces podemos definir la secuencia de paridad de Collatz (o vector de paridad) para un número n como p _i = P( a _i ) , donde a ₀ = n , y a _{i +1} = f ( a _i ) .

La operación que se realiza, 3n + 1/2 o n / 2 , depende de la paridad. La secuencia de paridad es la misma que la secuencia de operaciones .

Utilizando esta forma para f ( n ) , se puede demostrar que las secuencias de paridad de dos números m y n coincidirán en los primeros k términos si y solo si m y n son equivalentes módulo 2k . Esto implica que cada número se identifica de forma única por su secuencia de paridad, y además ^, que si existen múltiples ciclos de Hailstone, entonces sus ciclos de paridad correspondientes deben ser diferentes. ^{[ 2 ] [ 17 ]}

Aplicar la función f k veces al número n = 2 ^k a + b dará como resultado 3 ^c a + d , donde d es el resultado de aplicar la función f k veces a b , y c es la cantidad de incrementos encontrados durante esa secuencia. Por ejemplo, para 2 ⁵ a + 1 hay 3 incrementos cuando 1 itera a 2, 1, 2, 1 y finalmente a 2 por lo que el resultado es 3 ³ a + 2 ; para 2 ² a + 1 hay solo 1 incremento cuando 1 sube a 2 y baja a 1 por lo que el resultado es 3 a + 1 . Cuando b es 2 ^k − 1 entonces habrá k incrementos y el resultado será 3 ^k a + 3 ^k − 1 . La potencia de 3 que multiplica a es independiente del valor de a ; depende solo del comportamiento de b . Esto permite predecir que ciertas formas de números siempre darán como resultado un número menor después de un cierto número de iteraciones: por ejemplo, 4a + 1 se convierte en 3a + 1 después de dos aplicaciones de f y 16a + 3 se convierte en 9a + 2 después de cuatro aplicaciones de f . Sin embargo, que esos números menores sigan llegando a 1 depende del valor de a .

Para la función Collatz en formato abreviado

${\displaystyle f(n)={\begin{cases}{\frac {n}{2}}&{\text{si }}n\equiv 0\\{\frac {3n+1}{2}}&{\text{si }}n\equiv 1.\end{cases}}{\pmod {2}}}$

Las secuencias de granizo se pueden calcular mediante el sistema de 2 etiquetas con reglas de producción.

a → antes de Cristo , b → a , c → aaa .

En este sistema, el entero positivo n está representado por una cadena de n copias de a , y la iteración de la operación de etiquetado se detiene en cualquier palabra de longitud menor a  2. (Adaptado de De Mol.)

La conjetura de Collatz afirma de forma equivalente que este sistema de etiquetas, con una cadena finita arbitraria de la letra "a" como palabra inicial, finalmente se detiene (véase Sistema de etiquetas para un ejemplo resuelto).

Una extensión de la conjetura de Collatz consiste en incluir todos los enteros, no solo los enteros positivos. Dejando de lado el ciclo 0 → 0, al que no se puede acceder desde fuera, existen un total de cuatro ciclos conocidos, en los que todos los enteros distintos de cero parecen caer finalmente bajo la iteración de f . Estos ciclos se enumeran aquí, comenzando con el conocido ciclo para n positivo : 

Los valores impares se muestran en negrita y en letras grandes. Cada ciclo se enumera con su miembro de menor valor absoluto (que siempre es impar) en primer lugar.

La conjetura generalizada de Collatz es la afirmación de que todo entero, bajo la iteración de f , eventualmente cae en uno de los cuatro ciclos anteriores o en el ciclo 0 → 0.

El mapa de Collatz se puede extender a números racionales (positivos o negativos) con denominadores impares en su mínima expresión. Un número se considera par o impar según su numerador. La fórmula del mapa es la misma que cuando el dominio son los enteros: un racional par se divide por 2; un racional impar se multiplica por 3 y luego se le suma 1. Un hecho estrechamente relacionado es que el mapa de Collatz se extiende al anillo de enteros 2-ádicos , que contiene como subanillo el anillo de racionales con denominadores impares.

Al utilizar la definición "abreviada" del mapa de Collatz, se sabe que cualquier secuencia de paridad periódica es generada por exactamente un racional. ^{[ 25 ]} Por el contrario, se conjetura que todo racional con un denominador impar tiene una secuencia de paridad eventualmente cíclica (Conjetura de Periodicidad ^{[ 2 ]} ).

Si un ciclo de paridad tiene longitud n e incluye números impares exactamente m veces en los índices k ₀ < ⋯ < k _{m −1} , entonces el único racional que genera inmediatamente y periódicamente este ciclo de paridad es

Por ejemplo, el ciclo de paridad (1 0 1 1 0 0 1) tiene una longitud de 7 y cuatro términos impares en los índices 0, 2, 3 y 6. Se genera repetidamente mediante la fracción $${\displaystyle {\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {151}{47}}}$$ ya que este último conduce al ciclo racional $${\displaystyle {\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\rightarrow {\frac {340}{47}}\rightarrow {\frac {170}{47}}\rightarrow {\frac {85}{47}}\rightarrow {\frac {151}{47}}.}$$

Cualquier permutación cíclica de (1 0 1 1 0 0 1) está asociada a una de las fracciones anteriores. Por ejemplo, el ciclo (0 1 1 0 0 1 1) se produce mediante la fracción $${\displaystyle {\frac {3^{3}2^{1}+3^{2}2^{2}+3^{1}2^{5}+3^{0}2^{6}}{2^{7}-3^{4}}}={\frac {250}{47}}.}$$

Para que exista una correspondencia biunívoca, un ciclo de paridad debe ser irreducible , es decir, no particionable en subciclos idénticos. Como ejemplo de esto, el ciclo de paridad (1 1 0 0 1 1 0 0) y su subciclo (1 1 0 0) están asociados a la misma fracción 5 / 7 cuando se reducen a su mínima expresión .

En este contexto, asumir la validez de la conjetura de Collatz implica que (1 0) y (0 1) son los únicos ciclos de paridad generados por números enteros positivos (1 y 2, respectivamente).

Si el denominador impar d de un número racional no es múltiplo de 3, entonces todas las iteraciones tienen el mismo denominador y la secuencia de numeradores se puede obtener aplicando la generalización "3n + d" [ 26 ] ^{de la función} de Collatz . $${\displaystyle T_{d}(x)={\begin{cases}{\frac {x}{2}}&{\text{si }}x\equiv 0{\pmod {2}},\\{\frac {3x+d}{2}}&{\text{si }}x\equiv 1{\pmod {2}}.\end{cases}}}$$

La función $${\displaystyle T(x)={\begin{cases}{\frac {x}{2}}&{\text{si }}x\equiv 0{\pmod {2}}\\{\frac {3x+1}{2}}&{\text{si }}x\equiv 1{\pmod {2}}\end{cases}}}$$ está bien definido en el anillo${\displaystyle \mathbb {Z} _ {2}}$de enteros 2-ádicos , donde es continua y preserva la medida con respecto a la medida 2-ádica. Además, se sabe que su dinámica es ergódica . ^{[ 2 ]}

Defina la función vectorial de paridad Q que actúa sobre${\displaystyle \mathbb {Z} _ {2}}$como $${\displaystyle Q(x)=\sum _{k=0}^{\infty }\left(T^{k}(x){\bmod {2}}\right)2^{k}.}$$

La función Q es una isometría 2-ádica . ^{[ 27 ]} En consecuencia, toda secuencia de paridad infinita ocurre para exactamente un entero 2-ádico, de modo que casi todas las trayectorias son acíclicas en${\displaystyle \mathbb {Z} _ {2}}$.

Una formulación equivalente de la conjetura de Collatz es que $${\displaystyle Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .}$$

El mapa de Collatz se puede extender a la recta real eligiendo cualquier función que se evalúe como${\displaystyle x/2}$cuando${\displaystyle x}$es un número entero par y a cualquiera de las dos${\displaystyle 3x+1}$o${\displaystyle (3x+1)/2}$(para la versión "abreviada") cuando${\displaystyle x}$es un número entero impar. Esto se llama función de interpolación . Una forma sencilla de hacerlo es elegir dos funciones.${\displaystyle g_{1}}$y${\displaystyle g_{2}}$, dónde:

${\displaystyle g_{1}(n)={\begin{cases}1,&n{\text{ es par,}}\\0,&n{\text{ es impar,}}\end{cases}}}$

${\displaystyle g_{2}(n)={\begin{cases}0,&n{\text{ es par,}}\\1,&n{\text{ es impar,}}\end{cases}}}$

y utilizarlos como interruptores para los valores deseados:

${\displaystyle f(x)={\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)}$.

Una de esas opciones es${\displaystyle g_{1}(x)=\cos ^{2}\left({\tfrac {\pi }{2}}x\right)}$y${\displaystyle g_{2}(x)=\sin ^{2}\left({\tfrac {\pi }{2}}x\right)}$Las iteraciones de este mapa conducen a un sistema dinámico , investigado posteriormente por Marc Chamberland. ^{[ 28 ]} Demostró que la conjetura no se cumple para números reales positivos, ya que existen infinitos puntos fijos , así como órbitas que escapan monótonamente al infinito. La función${\displaystyle f}$tiene dos ciclos atractivos de período${\displaystyle 2}$:${\displaystyle (1;\,2)}$y${\displaystyle (1.1925...;\,2.1386...)}$Además, se conjetura que el conjunto de órbitas no acotadas es de medida${\displaystyle 0}$.

Letherman, Schleicher y Wood extendieron el estudio al plano complejo . ^{[ 29 ]} Utilizaron la función de Chamberland para el seno y el coseno complejos y añadieron el término adicional.${\displaystyle {\tfrac {1}{\pi }}\left({\tfrac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)\,+}$${\displaystyle h(z)\sin ^{2}(\pi z)}$, dónde${\displaystyle h(z)}$es cualquier función completa . Dado que esta expresión se evalúa a cero para enteros reales, la función extendida

${\displaystyle {\begin{aligned}f(z)=\;&{\frac {z}{2}}\cos ^{2}\left({\frac {\pi }{2}}z\right)+{\frac {3z+1}{2}}\sin ^{2}\left({\frac {\pi }{2}}z\right)\,+\\&{\frac {1}{\pi }}\left({\frac {1}{2}}-\cos(\pi z)\right)\sin(\pi z)+h(z)\sin ^{2}(\pi z)\end{aligned}}}$

es una interpolación del mapa de Collatz al plano complejo. La razón para agregar el término extra es para hacer que todos los enteros sean puntos críticos de${\displaystyle f}$Con esto, demuestran que ningún entero pertenece a un dominio de Baker , lo que implica que cualquier entero es o bien periódico o pertenece a un dominio errante . Conjeturaron que esto último no es cierto, lo que implicaría que todas las órbitas de los enteros son finitas.

La mayoría de los puntos tienen órbitas que divergen hacia el infinito. Colorear estos puntos según la velocidad de su divergencia produce la imagen de la izquierda, para${\displaystyle h(z)=0}$. Las regiones negras internas y la región externa son los componentes de Fatou , y el límite entre ellas es el conjunto de Julia de${\displaystyle f}$, que forma un patrón fractal , a veces llamado "fractal de Collatz".

Existen muchas otras formas de definir una función de interpolación compleja, como por ejemplo, utilizar la exponencial compleja en lugar del seno y el coseno:

${\displaystyle f(z)={\frac {z}{2}}+{\frac {1}{4}}(2z+1)\left(1-e^{i\pi z}\right)}$,

que exhiben dinámicas diferentes. En este caso, por ejemplo, si${\displaystyle \operatorname {Im} (z)\gg 1}$, entonces${\displaystyle f(z)\approx z+{\tfrac {1}{4}}}$. El conjunto de Julia correspondiente, que se muestra a la derecha, consta de una cantidad incontable de curvas, llamadas pelos o rayos .

La sección anterior , "Como secuencia de paridad", proporciona una forma de acelerar la simulación de la secuencia. Para avanzar k pasos en cada iteración (usando la función f de esa sección), divida el número actual en dos partes: b (los k bits menos significativos, interpretados como un entero) y a (el resto de los bits como un entero). El resultado de avanzar k pasos viene dado por

f ^k (2 ^k a + b ) = 3 ^{c ( b , k )} a + d ( b , k ) .

Los valores de c (o mejor 3c ⁾ y d se pueden precalcular para todos los posibles números b de k bits , donde d ( b , k ) es el resultado de aplicar la función f k veces a b , y c ( b , k ) es el número de números impares encontrados en el camino. ^{[ 30 ]} Por ejemplo, si k = 5 , se puede avanzar 5 pasos en cada iteración separando los 5 bits menos significativos de un número y usando

c (0...31, 5) = { 0, 3, 2, 2, 2, 2, 2, 4, 1, 4, 1, 3, 2, 2, 3, 4, 1, 2, 3, 3, 1, 1, 3, 3, 2, 3, 2, 4, 3, 3, 4, 5 },

d (0...31, 5) = { 0, 2, 1, 1, 2, 2, 2, 20, 1, 26, 1, 10, 4, 4, 13, 40, 2, 5, 17, 17, 2, 2, 20, 20, 8, 22, 8, 71, 26, 26, 80, 242 }.

Esto requiere 2k ^{preprocesamiento} y almacenamiento para acelerar el cálculo resultante en un factor de k , una compensación espacio-temporal .

Con el propósito específico de buscar un contraejemplo a la conjetura de Collatz, este preprocesamiento conduce a una aceleración aún más importante, utilizada por Tomás Oliveira e Silva en sus confirmaciones computacionales de la conjetura de Collatz hasta valores grandes de n . Si, para algunos b y k dados , la desigualdad 

f ^k (2 ^k a + b ) = 3 ^{c ( b )} a + d ( b ) < 2 ^k a + b

^Si se cumple para todo a , entonces el primer contraejemplo, si existe, no puede ser b módulo 2k . ^{[ 13 ]} Por ejemplo, el primer contraejemplo debe ser impar porque f (2n ) = n , menor que 2n ; y debe ser 3 mod 4 porque f2 ( 4n + 1) = 3n + 1 , menor que 4n + 1. Para cada valor inicial a que no es un contraejemplo de la conjetura de Collatz, hay un k para el cual se cumple tal desigualdad, por lo que verificar la conjetura de Collatz para un valor inicial es tan bueno como verificar una clase de congruencia completa. A medida que ^k aumenta , la búsqueda solo necesita verificar aquellos residuos b que no son eliminados por valores más bajos de k . Solo una fracción exponencialmente pequeña de los residuos sobrevive. ^{[ 31 ]} Por ejemplo, los únicos residuos que sobreviven módulo 32 son 7, 15, 27 y 31. 

Los enteros divisibles por 3 no pueden formar un ciclo, por lo que no es necesario comprobarlos como contraejemplos. ^{[ 32 ]}