Conjetura relajada de Collatz 3x+1

Question

Los Collatz $3x+1$ La conjetura afirma que cualquier número entero positivo puede reducirse eventualmente a $1$ mediante la aplicación iterativa de los mapas $x \mapsto 3x+1$ siempre que $x$ es impar y $x \mapsto x/2$ siempre que $x$ está en paz.

Aunque la conjetura de Collatz sigue abierta, me pregunto si la siguiente versión relajada es más sencilla. En esta versión relajada se nos permite aplicar mapas en cualquier orden manteniendo los números enteros. Es decir, si $x$ es impar, todavía tenemos que aplicar el $x \mapsto 3x+1$ mapa; pero para incluso $x$ tenemos la libertad de elegir entre $x \mapsto 3x+1$ y $x \mapsto x/2$ . La conjetura es que para cualquier número entero positivo, podemos reducirlo a $1$ con alguna secuencia iterativa de mapas.

Claramente, la conjetura de Collatz implicaría la versión relajada. Pero puede ocurrir que la versión relajada sea mucho más sencilla. ¿Lo es?

La pregunta se inspira en la discusión de la secuencia http://oeis.org/A109732 que es una permutación de los enteros positivos de impar si la versión relajada de la $3x-1$ La variante de la conjetura de Collatz es válida.

ACTUALIZACIÓN. El número mínimo de iteraciones para alcanzar $1$ en esta versión relajada viene dada por http://oeis.org/A127885 y este número suele ser menor que el de la conjetura de Collatz, dado por http://oeis.org/A006577 .

Answer 1

Preveo que esta conjetura debilitada puede demostrarse con algo de ayuda informática. Básicamente hay que demostrar la siguiente afirmación:

Reclamación Existe un número natural $k$ tal que, para cada clase de residuo $n \hbox{ mod } 2^k$ existe $1 \leq j \leq k$ y una secuencia de movimientos de Collatz que puede aplicarse a una entrada de esta clase de residuo que implica $j$ divisiones por dos y como máximo $j \frac{\log 2}{\log 3}$ aplicaciones de $x \mapsto 3x+1$ . (Obsérvese que mientras no se divida por $2$ más de $k$ veces, sólo es necesario conocer la clase de residuo del mod $2^k$ para poder describir el árbol de movimientos disponibles de Collatz).

De hecho, si esta afirmación fuera cierta, entonces cualquier $n$ podría iterarse hasta un número menor que $n$ independientemente de la clase de residuo mod $2^k$ uno comenzó con. Esto reduciría el problema a un número finito de entradas que pueden ser tratadas por el ordenador.

En principio, la afirmación anterior puede probarse numéricamente para cualquier $k$ . Espero que la proporción de clases de residuos que violan la afirmación disminuya de forma superexponencial en $k$ Así pues, para $k$ suficientemente grande no debería haber ningún contraejemplo entre los $2^k$ clases de residuos, por lo que para $k$ suficientemente grande la afirmación debería ser cierta. La única cuestión es si su verificación está dentro de la capacidad de cálculo actual.

[Para justificar por qué creo que la proporción de infractores es super-exponencial: incluso si uno sólo hace la iteración ordinaria de Collatz, la desigualdad de Chernoff dará un límite superior exponencial $O(e^{-cn})$ en la proporción de infractores, básicamente porque se está ejecutando una ruina del jugador (paseo aleatorio con deriva negativa). Si uno tiene la opción de aplicar hasta $a$ aplicaciones de $x \mapsto 3x+1$ primero, luego se tiene $a$ diferentes opciones que cada uno tiene $O_a(e^{-cn})$ y que sólo están débilmente correlacionados, por lo que esperaría que la probabilidad de que todos ellos fracasen baje a $O_a(e^{-acn})$ . Dejar $a$ crecen lentamente hasta el infinito da la predicción de decaimiento superexponecial].

Para ilustrar la afirmación, he aquí cómo se desarrolla para los pequeños $k$ :

• $k=1$ : Si $n=0 \hbox{ mod } 2$ la afirmación es verdadera (se divide por 2 inmediatamente), de lo contrario es falsa.
• $k=2$ : Si $n=0,2 \hbox{ mod } 4$ la afirmación es verdadera como antes; si $n=1 \hbox{ mod } 4$ la afirmación también es cierta (aplicar $3x+1$ y luego dividir por 2 dos veces); pero $n=3 \hbox{ mod } 4$ sobrevive como un contraejemplo.
• $k=3$ De la discusión anterior, los únicos contraejemplos potenciales son $n=3,7 \hbox{ mod } 8$ . Lamentablemente, no hay más eliminaciones en esta fase.
• $k=4$ : de lo anterior, los candidatos supervivientes son $n=3,7,11,15 \hbox{ mod } 16$ . Se puede eliminar $n=3 \hbox{ mod } 16$ aquí (aplicar $3x+1$ , luego dividir por dos, luego aplicar $3x+1$ y luego dividir por dos tres veces más), pero lamentablemente no hay más eliminaciones en esta etapa, dejando $7,11,15 \hbox{ mod } 16$ como las clases de residuos supervivientes.

El número de supervivientes crece lentamente en $k$ aquí porque el decaimiento superexponencial aún no ha entrado en acción, pero creo que lo hará eventualmente, y espero que mientras esté al alcance de la verificación informática.

Answer 2

Voy a escribir $\longrightarrow$ para algunas iteraciones estándar y $\implies$ para algunas iteraciones posiblemente no estándar. La conjetura relajada de Collatz es que para todo $x$ , $x \implies 1$ . Llamaré contraejemplos a la conjetura escapes .

En primer lugar, ya que es un buen ejemplo de la notación, un lema: para todo $a$ , $4 a \implies 9 a + 1$ .

Prueba: $4a \implies 12 a + 1 \longrightarrow 36a + 4 \longrightarrow 18a + 2 \longrightarrow 9 a + 1$ .

$\square$

Esto es lo que trataré de mostrar:

Teorema: Si $x$ es el menor de los escapes, entonces $4x \implies 1$ .

Prueba: Por consideraciones elementales, $x \equiv 3 \pmod{4}$ . Si $x \equiv 2 \pmod{3}$ entonces $\frac{2 x - 1}{3} \longrightarrow 2 x \longrightarrow x$ . Así que en este caso, $2 x$ no puede ser un fugitivo, y tampoco $4 x$ .

El siguiente caso es $x \equiv 0 \pmod{3}$ . Escriba $x = 12k+3$ . Usando el lema, $4x \implies 27k+7$ . Observe que $x > 9k+2 \rightarrow 27k+7$ si $k$ es impar. Ahora bien, si $x \equiv 15 \pmod{24}$ también tenemos que $4x \implies 1$ .

También es posible que $x \equiv 3 \pmod{24}$ . En ese caso, tenemos $x = 24 j + 3$ y $x \longrightarrow 27j+4$ . Esto significa que $j$ no puede ser uniforme. Así que volvemos a profundizar, con $x = 48i + 27 \longrightarrow 81i+49$ . Esto significa que $i$ no puede ser impar. Pero también, $4x = 4(48i+27) \implies 81i + 92$ Así que si $i$ está en paz, el siguiente paso nos lleva a $x$ . Esto cubre todos los $x \equiv 0 \pmod{3}$ casos.

Hasta ahora, nuestro resultado es que si $x \implies 4x$ entonces $x \equiv 7 \pmod{12}$ . Ahora me ocuparé de ese caso. Supongamos que $x \implies 4x$ y $x = 24k + 7$ . Entonces tenemos:

$4x = 4(24k+7) \implies 9(24k+7)+1 = 216k+64 \longrightarrow 108k+32 \longrightarrow 54k+16$ .

Pero también, $18k+5 \longrightarrow 54k+16$ . Esto significa que $18k+5$ también es un fugitivo, pero no puede serlo, ya que es menor que $x$ . Así que la hipótesis es falsa y tenemos $x = 24k + 19$ en su lugar.

Ahora, considera:

$4x = 4(24k+19) \implies 216k + 172 \longrightarrow 108k + 86 \longrightarrow 54k + 43 \longrightarrow 162k + 130 \longrightarrow 81k+65$ .

Por un razonamiento similar, $k \neq 3 \pmod{4}$ o bien podemos continuar la cadena dos pasos más para conseguir un escape menor que $x$ . Finalmente,

$x = 24k+19 \longrightarrow 72k+58 \longrightarrow 36k + 29 \longrightarrow 108k + 88 \longrightarrow 54k + 44 \longrightarrow 27k + 22$ .

muestra que $k$ no puede ser par, y sustituyendo $k = 4 j + 1$ :

$27k + 22 = 108j + 49 \longrightarrow 324j + 148 \longrightarrow 162j + 74 \longrightarrow 81j + 37 < x$

completa la prueba, ya que son todos los casos.

$\square$

Corolario: si la conjetura de Collatz es falsa y el menor contraejemplo conduce a sí mismo, entonces ese número no es un contraejemplo de la conjetura relajada de Collatz. En otras palabras, si $y$ es el menor número que satisface $\neg(y \longrightarrow 1)$ entonces $y \longrightarrow y$ implica $y \implies 1$ . Esta es una versión más débil de lo que originalmente pensé que había demostrado.

Corolario: Si $4x$ es un fugitivo, entonces hay un fugitivo más pequeño que $x$ . Esto me sugiere una estrategia de descenso recursivo en la que intentamos mostrar $z \implies 4k < 4x$ . Pero no está claro si los cálculos numéricos nos llevarán más lejos.

Answer 3

Actualización : Véase el final del post.

Habiendo abandonado mi enfoque anterior He encontrado otra aproximación al problema asistida por ordenador que debería funcionar heurísticamente y que no está sujeta a las obstrucciones de mi aproximación anterior.

Definir un movimiento legal para ser una función afín $x \mapsto ax+b$ que es la composición de un número finito de los mapas $x \mapsto \frac{x}{2}$ y $x \mapsto 3x+1$ (permitiendo repeticiones). Por ejemplo, $x \mapsto \frac{9x+a}{4}$ será un movimiento legal para $a = 4, 5, 7, 8, 10, 15, 16$ y, de forma más general, los movimientos legales adoptan la forma $x \mapsto \frac{3^n x + a}{2^m}$ para algunos números naturales $n,m,a$ con $a$ no divisible por $3$ (excepto cuando $n=0$ ). Obsérvese que mientras los movimientos generadores $x \mapsto \frac{x}{2}$ y $x \mapsto 3x+1$ pueden asignar números enteros a medios enteros, que a su vez pueden ser asignados a otros racionales diádicos (racionales cuyo denominador es una potencia de 2), no pueden convertir medios enteros (u otros racionales diádicos no enteros) de nuevo en enteros. Por lo tanto, si un movimiento legal toma un número natural $x$ a un número natural $y$ todos los pasos intermedios en ese movimiento deben ser también números naturales, y así $y$ se puede llegar desde $x$ mediante una iteración relajada de Collatz. Dado que, por supuesto, se puede obtener de cualquier potencia de $2$ a $1$ por un movimiento legal, y se puede utilizar $x \mapsto 3x+1$ para obtener de un múltiplo de $3$ a un no múltiplo de $3$ la conjetura relajada de Collatz se deduce ahora de

Conjetura Dado cualquier número natural $x_0$ que no es un múltiplo de $3$ existe una potencia de $2$ que es accesible desde $x_0$ por un movimiento legal.

En el enfoque anterior, la estrategia consistía en iterar $x_0$ a algo más pequeño. Aquí vamos a adoptar el enfoque opuesto de hacer en su lugar $x_0$ más grande en busca de una potencia de dos, pero aprovechando la flexibilidad disponible en la configuración relajada para "apuntar" hacia dónde van los iterados hasta cierto punto.

Más concretamente, afirmo que la conjetura anterior se desprende de la siguiente afirmación (en principio verificable numéricamente).

Reclamación Existe $n,m$ con $3^n > 2^m$ y un intervalo $[a_-,a_+]$ de una longitud mínima de $4 \times 3^n$ tal que $x \mapsto \frac{3^n x + a}{2^m}$ es un movimiento legal para cada número natural $a \in [a_-,a_+]$ que no es un múltiplo de $3$ .

De hecho, supongamos que hemos verificado esta afirmación para algunos $n,m$ . Entonces tenemos

Lema de expansión de intervalos Si $[x_-, x_+]$ es un intervalo con $x_-, x_+$ números naturales (excluyendo el caso degenerado cuando $x_-=x_+$ es un múltiplo de $3$ ), entonces todo número natural $y$ en el intervalo $[ \lceil \frac{3^n (x_-+1)+a_-}{2^m} \rceil, \lfloor \frac{3^n (x_+-1)+a_+}{2^m} \rfloor]$ que no es un múltiplo de $3$ puede ser alcanzado por un movimiento legal desde algún número natural en $[x_-,x_+]$ que no es un múltiplo de $3$ .

Prueba Basta con demostrar que $y$ es alcanzable mediante movimientos legales desde dos elementos consecutivos de $[x_-, x_+]$ (o sólo uno, si $x_-=x_+$ ). De la reclamación, $y$ es accesible desde cualquier $x$ con $$ \frac{3^n x + a_-}{2^m} \leq y \leq \frac{3^n x + a_+}{2^m}$$ (el hecho de que esos $\frac{3^n x + a}{2^m}$ con $a$ divisible por $3$ se omiten en la reivindicación no es un problema aquí, ya que estos sólo generan múltiplos de $3$ y $y$ se supone que no es un múltiplo de $3$ ). Esta restricción limita $x$ a un intervalo. Por la hipótesis de $y$ el punto final derecho de este intervalo es al menos $x_-+1$ y el extremo izquierdo es como máximo $x_+-1$ por lo que la intersección de este intervalo contiene dos elementos consecutivos de $[x_-,x_+]$ (o sólo uno, si $x_-=x_+$ ), dando lugar al lema. $\Box$

Tenga en cuenta que si $[x_-,x_+]$ tiene una longitud $h$ entonces el nuevo intervalo $[ \lceil \frac{3^n (x_-+1)+a_-}{2^m} \rceil, \lfloor \frac{3^n (x_+-1)+a_+}{2^m} \rfloor]$ tiene una longitud mayor que $\frac{3^n}{2^m} h$ , ya que $a_+ - a_- \geq 4 \cdot 3^n$ . Si se itera el lema de expansión del intervalo desde un punto de partida arbitrario $x_0$ que no es un múltiplo de $3$ se crea una secuencia de intervalos $[x_{-,k},x_{+,k}]$ de longitud $\gg (3^n/2^m)^k$ con y punto medio $\alpha_k (3^n/2^m)^k$ para algunos números reales $\alpha_k$ que forman una secuencia de Cauchy y, por tanto, convergen a algún límite $\alpha$ como $\alpha \to \infty$ , tal que todo número natural de este intervalo que no sea múltiplo de $3$ puede ser alcanzado por un movimiento legal de $x_0$ . Porque $\log (3^n/2^m) / \log 2$ es irracional, vemos por la teorema de la equidistribución que $\log ( \alpha (3^n/2^m)^k ) / \log 2$ puede ser arbitrariamente cercano a un número entero, por lo que en particular el intervalo $[x_{-,k},x_{+,k}]$ contendrá una potencia de dos para un número infinito de $k$ , dando la conjetura (por supuesto, las potencias de dos no son múltiplos de 3).

El siguiente argumento heurístico sugiere que la afirmación debería ser cierta para un tamaño suficientemente grande $n,m$ con $3^n/2^m$ cerca de $1$ . En este régimen tenemos $n \approx r \log 2$ y $m \approx r \log 3$ para algunos grandes $r$ . Un movimiento legal de la forma $x \mapsto \frac{3^n+a}{2^m}$ puede ser generado por $n$ aplicaciones de $x \mapsto 3x+1$ y $m$ aplicaciones de $x \mapsto x/2$ , en cualquier orden; así que hay $\binom{n+m}{m}$ formas de generar un movimiento legal, que según la fórmula de Stirling es $$ \approx \exp( r (\log 6 \log\log 6 - \log 2 \log\log 2 - \log 3 \log\log 3) ) \approx \exp(1.196 r)$$ hasta los términos de orden inferior. Por otro lado, un cálculo utilizando la ley de los grandes números sugiere que el tamaño típico del desplazamiento $a$ es $$\approx 3^n \approx 2^m \approx \exp( r \log 2 \log 3 ) \approx \exp(0.762 r),$$ ignorando de nuevo los términos de orden inferior (de hecho, yo esperaría que $a$ para tener una distribución aproximadamente logarítmica normal alrededor de una cantidad de esta magnitud, y obedecer una ley de Benford, en el espíritu de este trabajo de Lagarias y Soundararajan .). Así, para $r$ grandes hay significativamente más movimientos legales que probables compensaciones $a$ y la única restricción obvia en el desplazamiento $a$ es que no son múltiplos de tres. La heurística estándar (basada en la Problema de cobro de cupones ) sugieren entonces que la afirmación debería ser válida para $r$ lo suficientemente grande.

He hecho algunos cálculos, pero los intervalos que he encontrado se quedan un poco cortos. Por ejemplo, cuando $n=7$ y $m=9$ (por lo que se consideran jugadas legales de la forma $x \mapsto \frac{2187x+a}{512}$ ) He podido encontrar un intervalo de longitud 134, pero no más, en el que cada turno $a$ en este intervalo que no era un múltiplo de 3 daba una jugada legal. Hay varios términos de orden inferior en el análisis (incluyendo un factor logarítmico que surge del problema del recolector de cupones) que pueden requerir que uno tome $r$ ser relativamente grande para crear los intervalos de la longitud requerida en la reclamación, dado que la diferencia entre las dos tasas de crecimiento exponencial en el análisis heurístico es algo escasa.

p.d. Una consecuencia de la conjetura original o de la conjetura relajada de Collatz es que se puede llegar a $1$ a partir de cualquier número natural inicial $x_0$ multiplicando por cocientes de números naturales y sus iterados de Collatz. Esta afirmación más débil es de hecho un teorema, debido a Applegate y Lagarias .

UPDATE : Lamentablemente, el mismo contraejemplo de $-1$ que bloqueó el enfoque anterior, bloquea también este enfoque. Una variante del análisis del lema de expansión revela que después de aplicar $n$ copias de $x \mapsto 3x+1$ y $m$ copias de $x \mapsto x/2$ a partir de $-1$ se debería poder llegar a $\lfloor \frac{-3^n+a_+}{2^m} \rfloor$ (si no es un múltiplo de 3) o $\lfloor \frac{-3^n+a_+}{2^m} \rfloor - 1$ (en caso contrario); pero $-1$ sólo puede iterar a números negativos, por lo que $a_+ < 3^n + 2^m \leq 2 \cdot 3^n$ . Desde $a_-$ es positivo, esto evita que el intervalo $[a_-,a_+]$ siendo de longitud $4 \cdot 3^n$ como se desee. Así que eso fue algo decepcionante; aun así, dejaré mis dos respuestas sobre esta cuestión por si es útil para algún intento futuro de este problema. Es interesante que mientras el problema se plantea para números positivos, el contraejemplo negativo -1 a la conjetura (y sus parientes) están de alguna manera al acecho detrás de las escenas para sabotear una serie de ataques que de otro modo serían viables.