¿Una posible forma de demostrar la no ciclicidad de eventuales contraejemplos de la conjetura de Collatz?

Question

Llevo unos meses trabajando de forma recreativa en la conjetura de Collatz, y creo que he encontrado algo que podría demostrar al menos la mitad de la conjetura, que es la no existencia de ciclos no triviales. $\textbf{If you want to tl;dr}$ , basta con comprobar las ecuaciones enmarcadas. La primera es mi conjetura, y la segunda es un corolario que muestra que si la conjetura es correcta con todas las condiciones y todo, contradiría la existencia de patrones cíclicos no triviales. $\textbf{This is supposed to lead to a proof by contradiction}$ y hasta ahora, parece funcionar. Si no, podrías lo que he hecho para llegar a esta idea conjetural (porque lo estoy narrando cronológicamente para que más o menos puedas entender mi proceso). No he visto ninguna prueba revisada por pares de su inexistencia, así que supongo que sigue siendo un problema abierto por sí mismo. El hecho es que realmente creo que esta conjetura es manejable, sólo creo que no tengo el nivel necesario para abordar este tipo de cosas. De todas formas, lo primero es lo primero, no he usado el habitual $$a_0\in\mathbb N,~a_{n+1}=\left\{\begin{array}{cc}(3a_n+1)/2&a_n~\rm odd\\a_n/2&\rm otherwise\end{array}\right.$$ sino una subsecuencia más dinámica, que llamé al azar $(e_n)$ definido con $$e_0=\frac{a_0}{2^{\nu_2(a_0)}},~e_{n+1}=\frac{3e_n+1}{2^{\nu_2(3e_n+1)}}$$ donde $\nu_2$ es la valoración 2-ádica. Esto básicamente corta todos los números pares y básicamente mantiene la dinámica central de las secuencias. En primer lugar, tuve que demostrar por inducción que $$\begin{array}{ccccc} e_{n+1}&=&3^n\left(3e_0+1+\sum\limits_{k=1}^n\frac1{3^k}\prod\limits_{\ell=0}^{k-1}2^{\nu_2(3e_\ell+1)}\right)\prod\limits_{k=0}^n\frac1{2^{\nu_2(3e_k+1)}}&n\ge1&(1)\\ &=&3^n\left(3e_0+\left(\sum\limits_{k=0}^n\frac1{3^k}\prod\limits_{\ell=k}^n\frac1{2^{\nu_2(3e_\ell+1)}}\right)\prod\limits_{k=0}^n{2^{\nu_2(3e_k+1)}}\right)\prod\limits_{k=0}^n\frac1{2^{\nu_2(3e_k+1)}}&n\ge0&(2) \end{array}$$ Sin embargo, $\nu_2(3e_k+1)$ tiene un comportamiento muy caótico para $k\in\mathbb N$ así que tuve que atarlo de una forma u otra. El primer límite obvio es que $\nu_2(3e_k+1)\ge1$ a partir de cómo se define la secuencia, $3e_k+1$ es par. Por lo tanto, deduje que $$e_{n+1}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\le3^{n+1}e_0+\frac{3^n}{2^{n+1}}\left(\sum_{k=0}^n\left(\frac23\right)^k\right)\prod_{k=0}^n2^{\nu_2(3e_k+1)}$$ Desde $\sum\limits_{k=0}^n\left(\frac23\right)^k<3$ para todos $n\in\mathbb N$ descubrí que $$e_{n+1}\prod_{k=0}^n2^{\nu_2(3e_k+1)}<3^{n+1}e_0+\frac{3^{n+1}}{2^{n+1}}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\\ \iff\frac1{e_0}\left(e_{n+1}-\left(\frac32\right)^{n+1}\right)\prod_{k=0}^n2^{\nu_2(3e_k+1)}<3^{n+1}$$ Ahora, necesito usar un pequeño truco aquí. Voy a suponer $e_0$ sea mínima. De hecho, para todos los $(e_n)$ que no llega a la secuencia trivial, se puede demostrar que hay infinitas $k\in\mathbb N$ tal que para todo $n\ge k$ , $e_k\le e_n$ por lo que este truco puede describir literalmente cualquier contraejemplo de la conjetura de Collatz. Por lo tanto, obtenemos $$\prod_{k=0}^n2^{\nu_2(3e_k+1)}<\frac{3^{n+1}}{1-\frac1{e_0}\left(\frac32\right)^{n+1}}$$ sólo si $n+1 < \log_{3/2}e_0$ . Puesto que sabemos que para todo $e_0\le87\times2^{60}$ , $(e_n)$ no es un contraejemplo, tenemos $$\prod_{k=0}^n2^{\nu_2(3e_k+1)}<\frac{3^{n+1}}{1-\frac1{87\times2^{60}}\left(\frac32\right)^{n+1}}$$ para todos $n+1 < \log_{3/2}(87\times2^{60})\approx113.58\ldots$ Por lo tanto, tenemos que $$\sum_{k=0}^n\nu_2(3e_k+1)<(n+1)\log_23-\log_2\left(1-\frac1{87\times2^{60}}\left(\frac32\right)^{113}\right)$$ para $n\le112$ . Así que, para resumir, acabamos de acotar $\sum\limits_{k=0}^n\nu_2(3e_k+1)$ está limitada desde arriba por $(n+1)\log_23+c$ para alguna constante $c$ . Sin embargo, también podemos deducir que para todo $n\le107$ , $$\sum_{k=0}^n\nu_2(3e_k+1)<(n+1)\log_23$$ (Nota $107$ está aquí porque $\left\lfloor(n+1)\log_23\right\rfloor=\left\lfloor(n+1)\log_23-\log_2\left(1-\frac1{87\times2^{60}}\left(\frac32\right)^{n+1}\right)\right\rfloor$ para todo natural $n\le107$ ). En fin, básicamente, esta es mi conjetura :

Si $(e_n)$ no converge a 1 y que para todo $n\in\mathbb N$ tenemos $e_0\le e_n$ entonces para todo $n\in\mathbb N$ , $$\begin{array}{|c|}\hline\sum\limits_{k=0}^n\nu_2(3e_k+1)<(n+1)\log_23\\\hline\end{array}$$ Incluso tengo algunas pruebas numéricas que lo apoyan. Con un pequeño algoritmo que básicamente calcula, para cualquier $e_0$ la suma $\sum\limits_{k=0}^n\nu_2(3e_k+1)$ y comprueba si está o no por debajo de $(n+1)\log_23$ tanto tiempo como para todos $k\le n$ tenemos $e_0\le e_k$ . Comprobados todos los impar $e_0$ de $3$ à $29\;322\;479$ y funcionó, así que estoy bastante seguro de ello. ¿Cómo se relaciona esto con la no existencia de secuencias cíclicas? Bien, si asumimos esta conjetura y usando la fórmula $(2)$ tendríamos para un mínimo $e_0$ y $n\ge1$ $$\begin{array}{|c|}\hline e_{n+1}\ge 3^{n+1}\left(e_0+1/3+2/9\right)\frac1{3^{n+1}}=e_0+5/9>e_0\\\hline\end{array}$$ Pero esto significa que sólo podríamos alcanzar $e_0$ una vez, lo cual es una contradicción con la ciclicidad si funciona para todos los mínimos $e_0$ . Así que básicamente, si mi límite superior resulta ser correcto para todos los mínimos $e_0$ y $n\ge0$ (o $n\ge1$ ¡para ser prudente, pero de todos modos), esto implicaría esencialmente que no hay ningún ciclo no trivial ! Pongo esto aquí para que la gente pueda eventualmente encontrar una manera de probarlo. Obviamente lo he intentado yo mismo, pero me he dado cuenta de que puede que no sea lo suficientemente bueno para esto.

Answer 1

$$\frac{3e_0+1}{2^{\nu_2(3e_0+1)}}=e_1$$ puede reescribirse como $$(3+\frac{1}{e_0})=2^{\nu_2(3e_0+1)}\frac{e_1}{e_0}$$ Ahora tienes

$(3+\frac{1}{e_0})=2^{\nu_2(3e_0+1)}\frac{e_1}{e_0}$

$(3+\frac{1}{e_1})=2^{\nu_2(3e_1+1)}\frac{e_2}{e_1}$

...

$(3+\frac{1}{e_n})=2^{\nu_2(3e_n+1)}\frac{e_{n+1}}{e_n}$

Multiplicas cada LHS/RHS para obtener

$(3+\frac{1}{e_0})(3+\frac{1}{e_1})...(3+\frac{1}{e_n})=\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}$

Desde aquí se obtiene

$$(3+\frac{1}{e_{max}})^{n+1}\leq\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\leq (3+\frac{1}{e_{min}})^{n+1}$$

Pero significa que en un cilindro donde $e_{n+1}=e_0$ tienes

$\prod_{k=0}^n2^{\nu_2(3e_k+1)}\gt 3^{n+1}$ o $\begin{array}{|c|}\hline\sum\limits_{k=0}^n\nu_2(3e_k+1)>(n+1)\log_23\\\hline\end{array}$

A menos que me haya equivocado al traducirlo a tus anotaciones, no coincide con lo que obtienes.

Answer 2

No estoy seguro de si esto ayuda: en nuestro documento de trabajo estudiamos ciclos en secuencias de Collatz para $3n+1$ y la forma generalizada $kn+1$ . Hemos comprobado empíricamente que los ciclos sólo se producen si la condición $\alpha=\lfloor n*log_2k\rfloor+1$ se cumple. Esto se aproxima a las consideraciones anteriores. La variable $\alpha$ es el número de divisiones que se realiza para llegar desde el primer número impar $v_1$ al número impar $v_{n+1}$ que forma el ciclo. La variable $n$ es la duración del ciclo.

Ejemplo $v_1=13$ , $k=5$ y $n=3$ :

• $v_{n+1} = 5^3 * 13 * (1 + \frac{1}{5 * 13}) * (1 + \frac{1}{5 * 33}) * (1 + \frac{1}{5 * 83}) * 2^{-7}$ = 13
• $\alpha = \lfloor 3*log_25\rfloor+1$ = 7

Nuestra hipótesis se mantiene para todos los ciclos conocidos. Tal vez esta información sea útil para su análisis posterior.

Answer 3

Se trata de una matriz de n en función de k = pasos impar. Los números pares descienden a un número impar (dividido por 2) y los números Impares saltan a la columna de la izquierda (3n +1). Será útil para visualizar porque el ciclo 1,4,2,1 es el único ciclo posible. En caso contrario,

$f\left ( n \right )= n$ y esto sólo es posible cuando n = 1, tomando el impar n. Esto implica que la función toma un valor de la forma

$f_{0}^{k}\left ( n \right )= \frac{n\times 2^{x}}{2^{x}}$

y los números pares de la forma $n\times 2^{x}$ son los números de donde sale n y por tanto la función no vuelve a pasar por esos números. En la matriz, siempre están por encima de n y la función siempre se mueve hacia abajo para los pares y hacia la izquierda-arriba para los Impares, buscando su número par correspondiente. Es fácil ver que la función a partir de n siempre deja atrás los números que darían lugar a otro ciclo distinto de 4, 2,1. Matemáticamente, por ahora, no sé cómo expresarlo, es como si la función tuviera que hacer el ciclo inverso para que esto ocurra. P.D.: Desconozco tu demostración(¿correcta o incorrecta?) pero creo que podría ser útil para demostrar la inexistencia de otro ciclo que no sea 1,2,4,1.

Answer 4

Aunque los detalles de tu "subsecuencia más dinámica" son diferentes, me acuerdo de algunos trabajos que he realizado con el resultado de que si:

• Existe un ciclo de Collatz con $\alpha$ números pares (seguidos de $\frac{n}{2}$ ) y $\beta$ Números impar (seguidos de $\frac{3n+1}{2}$ ).
• La conjetura de Collatz es cierta para todos los números enteros entre 1 y $M$ . (Quizás porque lo has verificado con un programa informático de fuerza bruta.

Entonces $\log_2 3 < 1 + \frac{\alpha}{\beta} < \log_2 (3 + \frac{1}{M})$

En $M$ aumenta, los límites de $\frac{\alpha}{\beta}$ (una aproximación racional de $\log_2{3}-1$ ) se hacen más estrictos, y el límite inferior de $\alpha + \beta$ (el número de pasos del ciclo) es mayor.

La deficiencia fundamental de este planteamiento es que los números racionales son densos en los reales lo que significa que, por muy estricta que sea la cota superior de la desigualdad, siempre habrá algunos posible $\frac{\alpha}{\beta}$ reflejando algún ciclo de Collatz teóricamente posible.