Conjetura de Collatz

Problema no resuelto en matemáticas :

Para números pares, divida entre 2;
Para números impares, multiplica por 3 y suma 1.

Con suficiente repetición, ¿todos los números enteros positivos convergen a 1?

(más problemas sin resolver en matemáticas)

Gráfico dirigido que muestra las órbitas de números pequeños bajo el mapa de Collatz, omitiendo números pares. La conjetura de Collatz establece que todos los caminos eventualmente conducen a 1.

La conjetura de Collatz ^[a] es uno de los problemas no resueltos más famosos de las matemáticas . La conjetura pregunta si la repetición de dos operaciones aritméticas simples eventualmente transformará cada número entero positivo en 1. Se trata de secuencias de números enteros en las que cada término se obtiene del término anterior de la siguiente manera: si el término anterior es par , el siguiente término es la mitad de el término anterior. Si el término anterior es impar, el siguiente término es 3 veces el término anterior más 1. La conjetura es que estas secuencias siempre llegan a 1, sin importar qué entero positivo se elija para iniciar la secuencia.

Lleva el nombre del matemático Lothar Collatz , quien introdujo la idea en 1937, dos años después de doctorarse. ^[4] La secuencia de números involucrada a veces se conoce como secuencia de granizo, números de granizo o números de granizo (porque los valores generalmente están sujetos a múltiples descensos y ascensos como granizo en una nube), ^[5] o como números maravillosos. ^[6]

Paul Erdős dijo sobre la conjetura de Collatz: "Es posible que las matemáticas no estén preparadas para tales problemas". ^[7] Jeffrey Lagarias afirmó en 2010 que la conjetura de Collatz "es un problema extraordinariamente difícil, completamente fuera del alcance de las matemáticas actuales". ^[8]

Planteamiento del problema

Números del 1 al 9999 y su correspondiente tiempo total de parada

Histograma de tiempos totales de parada para los números del 1 al 10 ⁸ . El tiempo total de parada está en el eje $x$ , la frecuencia en el eje $y$ .

Histograma de tiempos totales de parada para los números del 1 al 10 ⁹ . El tiempo total de parada está en el eje $x$ , la frecuencia en el eje $y$ .

Tiempo de iteración para entradas de 2 a 10 ⁷ .

Considere la siguiente operación sobre un número entero positivo arbitrario :

Si el número es par, divídelo entre dos.
Si el número es impar, triplícalo y suma uno.

En notación aritmética modular , defina la función $f$ de la siguiente manera:

f(n)={\begin{casos}n/2&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]3n+1&{\text{if } }n\equiv 1{\pmod {2}}.\end{casos}}

Ahora forme una secuencia realizando esta operación repetidamente, comenzando con cualquier número entero positivo y tomando el resultado de cada paso como entrada en el siguiente.

En notación:

a_{i}={\begin{casos}n&{\text{para }}i=0,\\f(a_{i-1})&{\text{para }}i>0\end {casos}}

a i

f

n

i

a i = f i (n)

La conjetura de Collatz es: Este proceso eventualmente alcanzará el número 1, independientemente del entero positivo elegido inicialmente. Es decir, para cada uno , hay alguno con . $n$ $i$ $a_{i}=1$

Si la conjetura es falsa, sólo puede deberse a que hay algún número inicial que da lugar a una secuencia que no contiene 1. Tal secuencia entraría en un ciclo repetitivo que excluye 1 o aumentaría sin límite. No se ha encontrado tal secuencia.

El $i$ más pequeño tal que $a i < a 0$ se llama tiempo de parada de $n$ . De manera similar, el $k$ más pequeño tal que $a k = 1$ se llama tiempo de parada total de $n$ . ^[2] Si uno de los índices $i$ o $k$ no existe, decimos que el tiempo de parada o el tiempo de parada total, respectivamente, es infinito.

La conjetura de Collatz afirma que el tiempo total de parada de cada $n$ es finito. También equivale a decir que todo $n \geq 2$ tiene un tiempo de parada finito.

Dado que $3 n + 1$ es par siempre que $n$ sea impar, se puede utilizar la forma "atajada" de la función Collatz:

f(n)={\begin{casos}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{ \frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{casos}}

Datos empiricos

Por ejemplo, comenzando con $n = 12$ y aplicando la función $f$ sin "atajo", se obtiene la secuencia 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

El número $n = 19$ tarda más en llegar a 1: 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2 , 1.

La secuencia para $n = 27$ , enumerada y gráficada a continuación, toma 111 pasos (41 pasos a través de números impares, en negrita), subiendo hasta 9232 antes de descender a 1.

27 , 82, 41 , 124, 62 , 31, 94, 47 , 142, 71 , 214, 107 , 322, 161, 484 , 242, 121 , 364, 182, 91 , 274, 137 , 412, 206, 10 3 , 310, 155 , 466, 233 , 700, 350, 175 , 526, 263 , 790, 395 , 1186, 593 , 1780 , 890, 445 , 1336, 668, 334, 167, 502 , 251 , 7 54, 377 , 1132, 566, 283 , 850, 425 , 1276, 638, 319 , 958, 479 , 1438, 719 , 2158 , 1079, 3238, 1619, 4858, 2429 , 7288 , 3644 , 1822, 911 , 2734, 1367 , 4102 , 2051 , 6154, 3077 , 9232, 4616, 2308, 1154, 577, 1732 , 866, 433, 1300 , 650, 325, 976 , 488, 244, 122, 61, 184, 92, 46 , 23, 70 , 35 , 106, 53 , 160, 80, 40, 20, 10, 5 , 16, 8, 4, 2, 1 (secuencia A008884 en el OEIS )

Los números con un tiempo total de parada mayor que el de cualquier valor inicial menor forman una secuencia que comienza con:

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171,... (secuencia A006877 en la OEIS ).

Los valores iniciales cuyo punto máximo de trayectoria es mayor que el de cualquier valor inicial menor son los siguientes:

1, 2, 3, 7, 15, 27, 255, 447, 639, 703, 1819, 4255, 4591, 9663, 20895, 26623, 31911, 60975, 77671, 113383, 138367, 159487, 270271, 665215, 704511, ... (secuencia A006884 en la OEIS )

El número de pasos para que $n$ llegue a 1 son

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, ... (secuencia A006577 en la OEIS )

El valor inicial que tiene el mayor tiempo total de parada mientras se

menos de 10 es 9, que tiene 19 pasos,

menos de 100 es 97, que tiene 118 pasos,

menos de 1000 es 871, que tiene 178 pasos,

menos de 10 ⁴ es 6171, que tiene 261 pasos,

menos de 10 ⁵ es77 031 , que tiene 350 escalones,

menos de 10 ⁶ es837 799 , que tiene 524 pasos,

menos de 10 ⁷ es8 400 511 , que tiene 685 escalones,

menos de 10 ⁸ es63 728 127 , que tiene 949 pasos,

menos de 10 ⁹ es670 617 279 , que dispone de 986 pasos,

menos de 10 ¹⁰ es9 780 657 630 , que tiene 1132 pasos, ^[9]

menos de 10 ¹¹ es75 128 138 247 , que tiene 1228 pasos,

menos de 10 ¹² es989 345 275 647 , que cuenta con 1348 pasos. ^[10] (secuencia A284668 en el OEIS )

Estos números son los más bajos con el recuento de pasos indicado, pero no necesariamente los únicos por debajo del límite dado. Como ejemplo,9 780 657 631 tiene 1132 pasos, al igual que9 780 657 630 .

Los valores iniciales que tienen el tiempo total de parada más pequeño con respecto a su número de dígitos (en base 2) son las potencias de dos , ya que $2 n$ se divide por la mitad $n$ veces para llegar a 1 y nunca aumenta.

Visualizaciones

Gráfico dirigido que muestra las órbitas de los primeros 1000 números.
El eje $x$ representa el número inicial, el eje $y$ representa el número más alto alcanzado durante la cadena hasta 1. Este gráfico muestra un eje $y$ restringido : algunos valores $de x$ producen intermedios tan altos como2,7 × 10 ⁷ (para $x = 9663$ )
El mismo gráfico que el anterior pero en escala logarítmica, por lo que se muestran todos los valores $de y .$ La primera línea gruesa hacia el centro del gráfico corresponde a la punta en 27, que alcanza un máximo en 9232.
El árbol de todos los números que tienen menos de 20 pasos.
El número de iteraciones necesarias para llegar a uno de los primeros 100 millones de números.

Argumentos de apoyo

Aunque la conjetura no ha sido probada, la mayoría de los matemáticos que han investigado el problema piensan que es cierta porque la evidencia experimental y los argumentos heurísticos la respaldan.

Evidencia experimental

A partir de 2020 ^[actualizar], la conjetura ha sido verificada por computadora para todos los valores iniciales hasta 2 ⁶⁸ ≈2,95 × 10 ²⁰ . Todos los valores probados hasta ahora convergen a 1. ^[11]

Esta evidencia informática todavía no es una prueba rigurosa de que la conjetura es cierta para todos los valores iniciales, ya que se pueden encontrar contraejemplos al considerar números enteros positivos muy grandes (o posiblemente inmensos), como en el caso de la conjetura refutada de Pólya y la conjetura de Mertens .

Sin embargo, tales verificaciones pueden tener otras implicaciones. Por ejemplo, se pueden derivar restricciones adicionales sobre el período y la forma estructural de un ciclo no trivial. ^[12]^[13]^[14]^{[ se necesita aclaración ]}

Una heurística probabilística

Si se consideran sólo los números impares en la secuencia generada por el proceso de Collatz, entonces cada número impar es en promedio3/4del anterior. ^[15] (Más precisamente, la media geométrica de las proporciones de resultados es3/4.) Esto produce un argumento heurístico de que cada secuencia de Hailstone debería disminuir en el largo plazo, aunque esto no es evidencia contra otros ciclos, sólo contra la divergencia. El argumento no es una prueba porque supone que las secuencias de Hailstone se ensamblan a partir de eventos probabilísticos no correlacionados. (Establece rigurosamente que la extensión de 2 ádicos del proceso de Collatz tiene dos pasos de división por cada paso de multiplicación para casi todos los valores iniciales de 2 ádicos).

tiempos de parada

Como lo demuestra Riho Terras , casi todos los números enteros positivos tienen un tiempo de parada finito. ^[16] En otras palabras, casi todas las secuencias de Collatz alcanzan un punto que está estrictamente por debajo de su valor inicial. La prueba 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 mostrar, utilizando densidad logarítmica , que casi todas (en el sentido de densidad logarítmica) las órbitas de Collatz descienden por debajo de cualquier función dada del punto de partida, siempre que esta función diverja hasta el infinito, sin importar cuán despacio. En respuesta a este trabajo, la revista Quanta escribió que Tao "obtuvo uno de los resultados más significativos sobre la conjetura de Collatz en décadas". ^[17]^[18]

límites inferiores

En una prueba asistida por computadora , Krasikov y Lagarias demostraron que el número de números 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]

Ciclos

En esta parte, considere la forma abreviada de la función Collatz.

f(n)={\begin{casos}{\frac {n}{2}}&{\text{if }}n\equiv 0{\pmod {2}},\\[4px]{ \frac {3n+1}{2}}&{\text{if }}n\equiv 1{\pmod {2}}.\end{casos}}

ciclo

(a 0, a 1, ..., a q)

f (a 0) = a 1

f (a 1) = a 2

f (a q) = un 0

El único ciclo conocido es $(1,2)$ del período 2, llamado ciclo trivial.

Duración del ciclo

Se sabe que la duración de un ciclo no trivial es al menos186 265 759 595 . Si se puede demostrar que para todos los números enteros positivos menos de las secuencias de Collatz llegan a 1, entonces este límite se elevaría a $3\times 2^{69}$ 355 504 839 929 . ^[20]^[13] De hecho, Eliahou (1993) demostró que el período $p$ de cualquier ciclo no trivial es de la forma

p=301994a+17087915b+85137581c

a

b

c

b \geq 1

ac = 0

fraccionaria continua

en 3 / en 2

^[13]

k ciclos

Un $k$ -ciclo es un ciclo que se puede dividir en $k$ subsecuencias contiguas, cada una de las cuales consta de una secuencia creciente de números impares, seguida de una secuencia decreciente de números pares. ^[14] Por ejemplo, si el ciclo consta de una única secuencia creciente de números impares seguida de una secuencia decreciente de números pares, se llama 1 ciclo .

Steiner (1977) demostró que no existe otro ciclo que el trivial $(1; 2)$ . ^[21] Simons (2005) utilizó el método de Steiner para demostrar que no existen los 2 ciclos. ^[22] Simons & de Weger (2005) ampliaron esta prueba hasta 68 ciclos; no hay $k$ -ciclo hasta $k = 68$ . ^[14] Hercher amplió el método aún más y demostró que no existe ningún ciclo k con $k \leq91$ . ^[20] A medida que continúan las búsquedas exhaustivas por computadora, se pueden descartar valores $k mayores.$ Para exponer el argumento de manera más intuitiva; no tenemos que buscar ciclos que tengan menos de 92 subsecuencias, donde cada subsecuencia consta de subidas consecutivas seguidas de caídas consecutivas.

Otras formulaciones de la conjetura.

En reversa

Los primeros 21 niveles del gráfico de Collatz se generaron de abajo hacia arriba. El gráfico incluye todos los números con una longitud de órbita de 21 o menos.

Existe otro enfoque para probar la conjetura, que considera el método ascendente de hacer crecer el llamado gráfico de Collatz . La gráfica de Collatz es una gráfica definida por la relación inversa

R(n)={\begin{casos}\{2n\}&{\text{if }}n\equiv 0,1,2,3,5\\[4px]\left\{2n, {\frac {n-1}{3}}\right\}&{\text{if }}n\equiv 4\end{cases}}{\pmod {6}}.

Entonces, en lugar de demostrar que todos los números enteros positivos finalmente conducen a 1, podemos intentar demostrar que 1 conduce hacia atrás a todos los números enteros positivos. Para cualquier número entero $n$ , $n \equiv 1 (mod 2)$ si y solo si $3 n + 1 \equiv 4 (mod 6)$ . De manera equivalente, $norte - 1 / 3 \equiv 1 (mod 2)$ si y sólo si $n \equiv 4 (mod 6)$ . Conjeturalmente, esta relación inversa forma un árbol excepto por el bucle 1–2–4 (el inverso del bucle 4–2–1 de la función inalterada $f$ definida en la sección Declaración del problema de este artículo).

Cuando la relación $3 n + 1$ de la función $f$ se reemplaza por la relación sustitutiva común "atajo" $3 norte + 1 / 2$ , el gráfico de Collatz está definido por la relación inversa,

R(n)={\begin{casos}\{2n\}&{\text{if }}n\equiv 0,1\\[4px]\left\{2n,{\frac {2n- 1}{3}}\right\}&{\text{if }}n\equiv 2\end{cases}}{\pmod {3}}.

Para cualquier número entero $n$ , $n \equiv 1 (mod 2)$ si y sólo si $3 norte + 1 / 2 \equiv 2 (mod 3)$ . De manera equivalente, $2 norte - 1 / 3 \equiv 1 (mod 2)$ si y sólo si $n \equiv 2 (mod 3)$ . Conjeturalmente, esta relación inversa forma un árbol excepto por un bucle 1-2 (el inverso del bucle 1-2 de la función f(n) revisado como se indicó anteriormente).

Alternativamente, reemplace el $3 n + 1$ con $norte' / H (norte')$ donde $n' = 3 n + 1$ y $H (n')$ es la potencia más alta de 2 que divide $n'$ (sin resto ). La función resultante $f$ asigna números impares a números impares. Ahora supongamos que para algún número impar $n$ , al aplicar esta operación $k$ veces se obtiene el número 1 (es decir, $f k (n) = 1$ ). Luego, en binario , el número $n$ se puede escribir como la concatenación de cadenas $w k w k -1 ... w 1$ donde cada $w h$ es un extracto finito y contiguo de la representación de $1 / 3 horas$ . ^[23] La representación de $n$ por lo tanto tiene los repetidos de $1 / 3 horas$ , donde cada repetición se rota opcionalmente y luego se replica hasta un número finito de bits. Esto sólo ocurre en binario. ^[24] Conjeturalmente, cada cadena binaria $s$ que termina con un '1' se puede alcanzar mediante una representación de esta forma (donde podemos agregar o eliminar '0's iniciales a $s$ ).

Como una máquina abstracta que calcula en base dos.

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

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

Ejemplo

El número inicial 7 se escribe en base dos como 111 . La secuencia de Collatz resultante es:

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

Como una secuencia de paridad

Para esta sección, considere la función Collatz en la forma ligeramente modificada

f(n)={\begin{casos}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{ 2}}&{\text{if }}n\equiv 1\end{casos}}{\pmod {2}}.

Esto se puede hacer porque cuando $n$ es impar, $3 n + 1$ siempre es par.

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 0 = n$ y $a i +1 = f (a i)$ .

¿Qué operación se realiza? $3 norte + 1 / 2$ o $norte / 2$ , depende de la paridad. La secuencia de paridad es la misma que la secuencia de operaciones.

Usando esta forma para $f (n)$ , se puede demostrar que las secuencias de paridad para dos números $myn$ concordarán $en$ los primeros $k$ $términos$ si y sólo si $myn$ son equivalentes módulo $2$ $k$ . Esto implica que cada número se identifica de forma única por su secuencia de paridad y, además, si hay múltiples ciclos de Hailstone, sus correspondientes ciclos de paridad deben ser diferentes. ^[2]^[16]

Aplicar la función $f$ $k$ veces al número $n = 2 k a + b$ dará el resultado $3 c a + d$ , donde $d$ es el resultado de aplicar la función $f$ $k$ veces a $b$ , y $c$ es cuántos aumentos se encontraron durante esa secuencia. Por ejemplo, para $25 a + 1$ hay 3 aumentos a medida que 1 itera hasta 2, 1, 2, 1 y finalmente hasta 2, por lo que el resultado es $33 a + 2$ ; para $22 a + 1$ solo hay 1 aumento ya que 1 sube a 2 y cae a 1, por lo que el resultado es $3 a + 1$ . Cuando $b$ es $2 k - 1$ entonces habrá $k$ aumentos y el resultado será $3 k a + 3 k - 1$ . La potencia de 3 multiplicando $a$ es independiente del valor de $a$ ; depende sólo del comportamiento de $b$ . Esto permite predecir que ciertas formas de números siempre conducirán a un número menor después de un cierto número de iteraciones: por ejemplo, $4 a + 1$ se convierte en $3 a + 1$ después de dos aplicaciones de $f$ y $16 a + 3$ se convierte en $9 a + 2$ después de cuatro aplicaciones de $f$ . Sin embargo, si esos números más pequeños continúan hasta 1 depende del valor de $a$ .

Como sistema de etiquetas

Para la función Collatz en la forma

$f(n)={\begin{casos}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{ 2}}&{\text{si }}n\equiv 1.\end{casos}}{\pmod {2}}$

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

a \to antes de Cristo

b \to a

c \to 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 etiqueta se detiene en cualquier palabra de longitud inferior a 2. (Adaptado de De Mol.)

La conjetura de Collatz establece de manera equivalente que este sistema de etiquetas, con una cadena finita arbitraria de $a$ como palabra inicial, eventualmente se detiene (consulte Sistema de etiquetas para ver un ejemplo resuelto).

Extensiones a dominios más grandes

Iterando sobre todos los números enteros

Una extensión de la conjetura de Collatz es incluir todos los números enteros, no sólo los enteros positivos. Dejando de lado el ciclo 0 → 0 al que no se puede ingresar desde afuera, hay un total de cuatro ciclos conocidos, en los que todos los números enteros distintos de cero parecen caer eventualmente bajo la iteración de $f$ . Estos ciclos se enumeran aquí, comenzando con el conocido ciclo de $n$ positivo :

Los valores impares se enumeran en negrita grande. Cada ciclo se enumera con su miembro de menor valor absoluto (que siempre es impar) primero.

La conjetura generalizada de Collatz es la afirmación de que cada número entero, bajo iteración por $f$ , eventualmente cae en uno de los cuatro ciclos anteriores o el ciclo 0 → 0. (El ciclo 0 → 0 solo se incluye para completar).

Iterando sobre racionales con denominadores impares

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

Cuando se utiliza la definición de "atajo" del mapa de Collatz, se sabe que cualquier secuencia de paridad periódica es generada exactamente por 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 la periodicidad ^[2] ).

Si un ciclo de paridad tiene longitud $n$ e incluye números impares exactamente $m$ veces en índices $k 0 < \dots < k m -1$ , entonces el único racional que genera inmediata 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. Es generado repetidamente por la fracción

{\frac {3^{3}2^{0}+3^{2}2^{2}+3^{1}2^{3}+3^{0}2^{6} }{2^{7}-3^{4}}}={\frac {151}{47}}

{\frac {151}{47}}\rightarrow {\frac {250}{47}}\rightarrow {\frac {125}{47}}\rightarrow {\frac {211}{47}}\ flecha derecha {\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 por la fracción

{\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 una correspondencia uno a uno, un ciclo de paridad debe ser irreducible , es decir, no divisible en subciclos idénticos. A modo de ilustración 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ón5/7cuando se reduce a los términos más bajos.

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 racional no es múltiplo de 3, entonces todos los iterados tienen el mismo denominador y la secuencia de numeradores se puede obtener aplicando la generalización " $3 n + d$ ^{" [26]} de la función de Collatz

T_{d}(x)={\begin{casos}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}},\\[ 4px]{\frac {3x+d}{2}}&{\text{if }}x\equiv 1{\pmod {2}}.\end{casos}}

extensión 2-ádica

La función

T(x)={\begin{casos}{\frac {x}{2}}&{\text{if }}x\equiv 0{\pmod {2}}\\[4px]{\ frac {3x+1}{2}}&{\text{if }}x\equiv 1{\pmod {2}}\end{casos}}

enteros de 2 ádicos conserva la medida ergódica^[2]

\mathbb {Z} _ {2}

Defina la función vectorial de paridad $Q$ que actúa como $\mathbb {Z} _ {2}$

Q(x)=\sum _ {k=0}^{\infty }\left(T^{k}(x)\mod 2\right)2^{k}.

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

Una formulación equivalente de la conjetura de Collatz es que

Q\left(\mathbb {Z} ^{+}\right)\subset {\tfrac {1}{3}}\mathbb {Z} .

Iterando sobre números reales o complejos

El mapa de Collatz se puede extender a la línea real eligiendo cualquier función que evalúe cuándo es un número entero par y cuándo o (para la versión "atajada") cuándo es un entero impar. Esto se llama función de interpolación . Una forma sencilla de hacer esto es elegir dos funciones y , donde: $x/2$ $x$ $3x+1$ $(3x+1)/2$ $x$ ${\ Displaystyle g_ {1}}$ ${\ Displaystyle g_ {2}}$

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

g_{2}(n)={\begin{cases}0,&n{\text{ is even,}}\\1,&n{\text{ is odd,}}\end{cases}}

y usarlos como interruptores para nuestros valores deseados:

f(x)\triangleq {\frac {x}{2}}\cdot g_{1}(x)\,+\,{\frac {3x+1}{2}}\cdot g_{2}(x)

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

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

{\begin{aligned}f(z)\triangleq \;&{\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 adicional es hacer que todos los números enteros sean puntos críticos . Con esto, muestran que ningún número entero está en un dominio de Baker , lo que implica que cualquier número entero es eventualmente periódico o pertenece a un dominio errante . Conjeturaron que este último no es el caso, lo que haría que todas las órbitas enteras fueran finitas. $f$

La mayoría de los puntos tienen órbitas que divergen hasta el infinito. Al colorear estos puntos según la rapidez con la que divergen se produce la imagen de la izquierda, por ejemplo . 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 , que forma un patrón fractal , a veces llamado "fractal de Collatz". $h(z)\triangleq 0$ $f$

Hay muchas otras formas de definir una función de interpolación compleja, como usar la exponencial compleja en lugar de seno y coseno:

f(z)\triangleq {\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 , entonces . El conjunto de Julia correspondiente, que se muestra a la derecha, consta de incontables curvas, llamadas pelos o rayos . $\operatorname {Im} (z)\gg 1$ $f(z)\approx z+{\tfrac {1}{4}}$

Optimizaciones

Compensación tiempo-espacio

La sección anterior Como secuencia de paridad proporciona una manera 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 número entero) y $a$ (el resto de los bits como un número entero). El resultado de saltar hacia adelante $k$ está dado por

f k (2 k una + segundo) = 3 c (segundo, k) una + re (segundo, k)

Los valores de $c$ (o mejor $3 c$ ) y $d$ se pueden precalcular para todos los números de $k bits posibles$ $b$ , 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 que se encuentran en el camino. ^[30] Por ejemplo, si $k = 5$ , se pueden 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 $2 k$ de cálculo previo y almacenamiento para acelerar el cálculo resultante en un factor de $k$ , una compensación espacio-temporal .

Restricciones modulares

Con el propósito especial de buscar un contraejemplo a la conjetura de Collatz, este cálculo previo 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

holds for all $a$ , then the first counterexample, if it exists, cannot be $b$ modulo $2 k$ .^[12] For instance, the first counterexample must be odd because $f (2 n) = n$ , smaller than $2 n$ ; and it must be 3 mod 4 because $f 2 (4 n + 1) = 3 n + 1$ , smaller than $4 n + 1$ . For each starting value $a$ which is not a counterexample to the Collatz conjecture, there is a $k$ for which such an inequality holds, so checking the Collatz conjecture for one starting value is as good as checking an entire congruence class. As $k$ increases, the search only needs to check those residues $b$ that are not eliminated by lower values of $k$ . Only an exponentially small fraction of the residues survive.^[31] For example, the only surviving residues mod 32 are 7, 15, 27, and 31.

Syracuse function

If $k$ is an odd integer, then $3 k + 1$ is even, so $3 k + 1 = 2 a k'$ with $k'$ odd and $a \geq 1$ . The Syracuse function is the function $f$ from the set $I$ of positive odd integers into itself, for which $f (k) = k'$ (sequence A075677 in the OEIS).

Some properties of the Syracuse function are:

For all $k \in I$ , $f (4 k + 1) = f (k)$ . (Because $3(4 k + 1) + 1 = 12 k + 4 = 4(3 k + 1)$ .)
In more generality: For all $p \geq 1$ and odd $h$ , $f p - 1 (2 p h - 1) = 2 \times 3 p - 1 h - 1$ . (Here $f p - 1$ is function iteration notation.)
For all odd $h$ , $f (2 h - 1) \leq 3 h - 1 / 2$

La conjetura de Collatz es equivalente a la afirmación de que, para todo $k$ en $I$ , existe un número entero $n \geq 1$ tal que $f n (k) = 1$ .

Generalizaciones indecidibles

En 1972, John Horton Conway demostró que una generalización natural del problema de Collatz es algorítmicamente indecidible . ^[32]

Específicamente, consideró funciones de la forma

{g(n)=a_{i}n+b_{i}}{\text{ when }}{n\equiv i{\pmod {P}}},

a 0, b 0, ..., a P - 1, b P - 1

g (n)

P = 2

a 0 = 1 / 2

segundo 0 = 0

un 1 = 3

segundo 1 = 1

Dados

g

n

, ¿la secuencia de iteraciones

g k (n)

llega a

1

es indecidible, al representar el problema de la detención de esta manera.

Más cerca del problema de Collatz está el siguiente problema universalmente cuantificado :

Dado

g

, ¿la secuencia de iteraciones

g k (n)

llega a

1

, para todo

n > 0

Modificar la condición de esta manera puede hacer que un problema sea más difícil o más fácil de resolver (intuitivamente, es más difícil justificar una respuesta positiva, pero podría ser más fácil justificar una negativa). Kurtz y Simon ^[33] demostraron que el problema universalmente cuantificado es, de hecho, indecidible e incluso más alto en la jerarquía aritmética ; específicamente, es $Π 02$ -completo. Este resultado de dureza se mantiene incluso si se restringe la clase de funciones $g$ fijando el módulo $P$ en 6480. ^[34]

Las iteraciones de en una versión simplificada de esta forma, con todas iguales a cero, se formalizan en un lenguaje de programación esotérico llamado FRACTRAN . $b_{i}$

En la cultura popular

En la película Incendies , un estudiante de posgrado en matemáticas puras explica la conjetura de Collatz a un grupo de estudiantes universitarios. Deja sus estudios en espera por un tiempo para abordar algunas preguntas no resueltas sobre el pasado de su familia. Al final de la película, la conjetura de Collatz resulta haber presagiado un descubrimiento inquietante y difícil que ella hace sobre su familia. ^[35]^[36]

Ver también

Wikimedia Commons tiene medios relacionados con la conjetura de Collatz .

Notas a pie de página

^ También se conoce como el problema (o conjetura ) $3 n + 1$ , el problema (o conjetura ) $3$ $x$ $+ 1$ , la conjetura de Ulam (después de Stanisław Ulam ), el problema de Kakutani (después de Shizuo Kakutani ), la conjetura de Thwaites (después de Bryan Thwaites ), el algoritmo de Hasse (después de Helmut Hasse ), o el problema de Syracuse (después de la Universidad de Syracuse ). ^[1]^[3]

Otras lecturas

The Ultimate Challenge: The 3 $x$ + 1 Problem , ^[8] publicado en 2010 por la American Mathematical Society y editado por Jeffrey Lagarias , es un compendio de información sobre la conjetura de Collatz, métodos para abordarla y generalizaciones. Incluye dos artículos de estudio del editor y cinco de otros autores sobre la historia del problema, generalizaciones, enfoques estadísticos y resultados de la teoría de la computación . También incluye reimpresiones de los primeros artículos sobre el tema, incluido el artículo de Lothar Collatz .

Referencias

^ Maddux, Cleborne D.; Johnson, D. Lamont (1997). Logotipo: una retrospectiva . Nueva York: Haworth Press. pag. 160.ISBN 0-7890-0374-0. El problema también se conoce con varios otros nombres, entre ellos: conjetura de Ulam, problema de Hailstone, problema de Syracuse, problema de Kakutani, algoritmo de Hasse y problema de Collatz.
^ abcdefg Lagarias, Jeffrey C. (1985). "El problema 3 x + 1 y sus generalizaciones". El Mensual Matemático Estadounidense . 92 (1): 3–23. doi :10.1080/00029890.1985.11971528. JSTOR 2322189.
^ Según Lagarias (1985), ^[2] p. 4, el nombre "problema de Siracusa" fue propuesto por Hasse en la década de 1950, durante una visita a la Universidad de Siracusa .
^ O'Connor, JJ; Robertson, EF (2006). "Lothar Collatz". Escuela de Matemáticas y Estadística de la Universidad de St Andrews, Escocia.
^ Recogida, Clifford A. (2001). Maravillas de los números . Oxford: Prensa de la Universidad de Oxford. págs. 116-118. ISBN 0-19-513342-0.
^ Hofstadter, Douglas R. (1979). Gödel, Escher, Bach . Nueva York: Libros básicos. págs. 400–2. ISBN 0-465-02685-0.
^ Chico, Richard K. (2004). ""E16: El problema del 3x+1"". Problemas no resueltos en teoría de números (3ª ed.). Springer-Verlag . págs. 330–6. ISBN 0-387-20860-7. Zbl 1058.11001.
^ ab Lagarias, Jeffrey C. , ed. (2010). El desafío definitivo: el problema del 3 x + 1 . Sociedad Matemática Estadounidense . ISBN 978-0-8218-4940-8. Zbl 1253.11003.
^ Levaduras, Gary T.; Vermeulen, Mike (diciembre de 1992). "3 x + 1 programas de búsqueda". Computadoras y Matemáticas con Aplicaciones . 24 (11): 79–99. doi :10.1016/0898-1221(92)90034-F.
^ Roosendaal, Eric. "Registros de retraso 3x+1" . Consultado el 14 de marzo de 2020 .(Nota: los "registros de retraso" son registros de tiempo total de parada).
^ Barina, David (2020). "Verificación de convergencia del problema de Collatz". La revista de supercomputación . 77 (3): 2681–2688. doi :10.1007/s11227-020-03368-x. S2CID 220294340.
^ ab Garner, Lynn E. (1981). "Sobre el algoritmo Collatz 3n + 1". Actas de la Sociedad Matemática Estadounidense . 82 (1): 19–22. doi : 10.1090/S0002-9939-1981-0603593-2 . JSTOR 2044308.
^ abc Eliahou, Shalom (1993). "El problema 3x + 1: nuevos límites inferiores en duraciones de ciclos no triviales". Matemáticas discretas . 118 (1): 45–56. doi : 10.1016/0012-365X(93)90052-U .
^ abc Simons, J.; de Weger, B. (2005). "Límites teóricos y computacionales para m-ciclos del problema 3n + 1" (PDF) . Acta Aritmética . 117 (1): 51–70. Código bibliográfico : 2005AcAri.117...51S. doi : 10.4064/aa117-1-3 . Archivado desde el original el 18 de marzo de 2022 . Consultado el 28 de marzo de 2023 .{{cite journal}}: CS1 maint: bot: original URL status unknown (link)
↑ Lagarias (1985), ^[2] apartado "Un argumento heurístico".
^ ab Terras, Riho (1976). "Un problema de tiempo de parada en números enteros positivos" (PDF) . Acta Aritmética . 30 (3): 241–252. doi : 10.4064/aa-30-3-241-252 . SEÑOR 0568274.
^ Tao, Terence (2022). "Casi todas las órbitas del mapa de Collatz alcanzan valores casi acotados". Foro de Matemáticas, Pi . 10 : e12. arXiv : 1909.03562 . doi : 10.1017/fmp.2022.8 . ISSN 2050-5086.
^ Hartnett, Kevin (11 de diciembre de 2019). "Un matemático demuestra un resultado enorme en un problema 'peligroso'". Revista Quanta .
^ Krasikov, Ilia; Lagarias, Jeffrey C. (2003). "Límites para el problema 3x + 1 utilizando desigualdades en diferencias". Acta Aritmética . 109 (3): 237–258. arXiv : matemáticas/0205002 . Código bibliográfico : 2003AcAri.109..237K. doi :10.4064/aa109-3-4. SEÑOR 1980260. S2CID 18467460.
^ ab Hercher, C. (2023). "No hay m-ciclos de Collatz con m <= 91" (PDF) . Diario de secuencias enteras . 26 (3): Artículo 23.3.5.
^ Steiner, RP (1977). "Un teorema sobre el problema de Siracusa". Actas de la Séptima Conferencia de Manitoba sobre Matemáticas Numéricas . págs. 553–9. SEÑOR 0535032.
^ Simons, John L. (2005). "Sobre la inexistencia de 2 ciclos para el problema 3x + 1". Matemáticas. comp . 74 : 1565–72. Código Bib : 2005MaCom..74.1565S. doi : 10.1090/s0025-5718-04-01728-4 . SEÑOR 2137019.
^ Colussi, Livio (9 de septiembre de 2011). "Las clases de convergencia de la función Collatz". Informática Teórica . 412 (39): 5409–5419. doi : 10.1016/j.tcs.2011.05.056 .
^ Hew, Patrick Chisan (7 de marzo de 2016). "Trabajar en binario protege las repeticiones de 1/3 h: comentario sobre 'Las clases de convergencia de la función Collatz' de Colussi'". Informática Teórica . 618 : 135-141. doi : 10.1016/j.tcs.2015.12.033 .
^ Lagarias, Jeffrey (1990). "El conjunto de ciclos racionales para el problema 3x+1". Acta Aritmética . 56 (1): 33–53. doi : 10.4064/aa-56-1-33-53 . ISSN 0065-1036.
^ Belaga, Edward G.; Mignotte, Mauricio (1998). "Integrar la conjetura 3x+1 en un contexto 3x+d". Matemáticas Experimentales . 7 (2): 145-151. doi :10.1080/10586458.1998.10504364. S2CID 17925995.
^ Bernstein, Daniel J.; Lagarias, Jeffrey C. (1996). "El mapa de conjugación 3x + 1". Revista Canadiense de Matemáticas . 48 (6): 1154-1169. doi : 10.4153/CJM-1996-060-x . ISSN 0008-414X.
^ Chamberland, Marc (1996). "Una extensión continua del problema 3 x + 1 a la recta real". Dinámico. Continúe. Sistemas de Impulsos Discretos . 2 (4): 495–509.
^ Letherman, Simón; Schleicher, Dierk; Madera, Reg (1999). "El problema (3 n + 1) y la dinámica holomorfa". Matemáticas Experimentales . 8 (3): 241–252. doi :10.1080/10586458.1999.10504402.
^ Scollo, Giuseppe (2007). «Buscando récords de clase en el problema 3x+1 mediante la infraestructura grid de COMETA» (PDF) . Jornadas de Puertas Abiertas de Grid en la Universidad de Palermo .
^ Lagarias (1985), ^[2] Teorema D.
^ Conway, John H. (1972). "Iteraciones impredecibles". Proc. 1972 Conferencia de Teoría de Números, Univ. Colorado, Roca . págs. 49–52.
^ Kurtz, Estuardo A.; Simón, Janos (2007). "La indecidibilidad del problema generalizado de Collatz". En Cai, J.-Y.; Cooper, SB; Zhu, H. (eds.). Actas de la 4ª Conferencia Internacional sobre Teoría y Aplicaciones de Modelos de Computación, TAMC 2007, celebrada en Shanghai, China, en mayo de 2007 . págs. 542–553. doi :10.1007/978-3-540-72504-6_49. ISBN 978-3-540-72503-9.Como PDF
^ Ben-Amram, Amir M. (2015). "Mortalidad de funciones afines iteradas por partes sobre números enteros: decidibilidad y complejidad". Computabilidad . 1 (1): 19–56. doi :10.3233/COM-150032.
^ Emmer, Michele (2012). Imagine Math: entre la cultura y las matemáticas . Publicación Springer . págs. 260–264. ISBN 978-8-847-02426-7.
^ Mazmanian, Adam (19 de mayo de 2011). "RESEÑA DE LA PELÍCULA: 'Incendies'". Los tiempos de Washington . Consultado el 7 de diciembre de 2019 .

enlaces externos

Mateos, Keith. "3 x + 1 página".
Un proyecto informático voluntario en curso Archivado el 30 de agosto de 2021 en Wayback Machine por David Bařina verifica la convergencia de la conjetura de Collatz para valores grandes. (mayor progreso hasta el momento)
( BOINC ) Proyecto informático voluntario Archivado el 4 de diciembre de 2017 en Wayback Machine que verifica la conjetura de Collatz para valores mayores.
Un proyecto informático voluntario en curso realizado por Eric Roosendaal verifica la conjetura de Collatz para valores cada vez mayores.
Otro proyecto informático voluntario en curso realizado por Tomás Oliveira e Silva continúa verificando la conjetura de Collatz (con menos estadísticas que la página de Eric Roosendaal pero con mayores avances).
Weisstein, Eric W. "Problema de Collatz". MundoMatemático .
Problema de Collatz en PlanetMath ..
Nochella, Jesse. "Caminos de Collatz". Proyecto de demostraciones de Wolfram .
Eisenbud, D. (8 de agosto de 2016). ¿Irrompible? La conjetura de Collatz (vídeo corto). Numéfilo. Archivado desde el original el 11 de diciembre de 2021, a través de YouTube.
Eisenbud, D. (9 de agosto de 2016). ¿Irrompible? Conjetura de Collatz (metraje adicional). Numéfilo. Archivado desde el original el 11 de diciembre de 2021, a través de YouTube.
Alex Kontorovich [Delaware] (presentación) (30 de julio de 2021). El problema matemático más simple que nadie puede resolver (video corto). Veritasium - a través de YouTube.
¿Están las computadoras preparadas para resolver este problema matemático notoriamente difícil de manejar?