8 votos

¿La inexistencia de la Collatz-"1-ciclo" por una prueba elemental - estoy perdiendo algo?

El llamado "1-ciclo" en el Collatz-problema ya fue desmentido por Ray Steiner 1977. Sin embargo, él utiliza trascendental de la teoría de números para conseguirlo, y Lagarias comentado, es sorprendente que tales armas pesadas son necesarios para que un pequeño resultado.
Creo que tengo una primaria prueba ahora, pero por lo general en la Collatz problema de sus pruebas son defectuosos, así que mejor pedir un chequeo cruzado. Como se propone en la BMV.meta voy a poner el problema de la descripción en esta pregunta y publicar mi intento de prueba en una propia respuesta.

La noción de 1-ciclos de comenzar con la definición de aumento de pasos $a_{k+1} = {3a_k +1\over 2} $ si $a_k$ es impar y la disminución de pasos $a_{k+1} = {a_k\over 2} $ si $a_k$ es incluso.
Si tenemos en cuenta el tipo simple de un ciclo, que se produce si $N$ el aumento de los pasos son seguidos por $B$ disminución de pasos, entonces vamos a llamar a este con Steiner, Simons, de Weger y otros el "1" ciclo de longitud $S=N+B$.

Con Steiner, podemos afirmar, que un número inicial de una que deseamos aumentar en N pasos debe tener la forma $a = 2^N \cdot k -1$ para cualquier entero $k \gt 0$ . El resultado de esa transformación, al que llamaremos b tiene la forma $b=3^N \cdot k -1 $ con el mismo parámetro k. Si b se transformaron por B la disminución de pasos y llega a c , entonces c tiene la forma $c={3^N \cdot k\ - 1 \over 2^B}$ Si $c=a$, entonces tenemos un ciclo y este es el "1-ciclo".
Ahora la identificación de un con c esto le da a la "crítica de la fórmula" $$ \tag{1.0} 2^N\cdot k - 1 = {3^N \cdot k -1 \over 2^B}$$ Simplemente cambiando da la más centrado formulario que aparece (el uso de letras diferentes) en J. Simón paráfrasis de R. Steiner está la prueba: $$ \tag{1.1} (2^S - 3^N)\cdot k = 2^B - 1 $$ donde también se $S$ es introducido como $S=N+B$ $2^S \gt 3^N$ se entiende. A continuación, la instrucción correspondiente es:

Para un 1-ciclo de cualquier longitud $N$ a existir debemos tener una solución en los enteros positivos $(N,S,B,k,a)$ en eq. (1.1) .

$\qquad \qquad$ (los otros dos útiles representaciones de los críticos de la ecuación son $$ \pequeño (2^S - 3^N)\cdot k = (2^S - 2^N )/2^N \quad , 2^S \gt 3^N \quad \text{ o }\\ \pequeño 2^B = {2^S\más de 2^N}={3^N \cdot k -1 \más de 2^N\cdot k-1}$$

El uso de los resultados de trascendental de la teoría de números y racional de la aproximación lineal de las formas de logaritmos Steiner demostrado, que no es $2^B$ satisfactorio que la fórmula excepto $B=1$,$N=1$,$k=1$ y $ a=1, b = 2 = {3a+1\over 2}, a=1={b \over 2} $, lo que se llama el "trivial ciclo".

Pregunta: ¿cómo puede ser probado por la primaria significa, que la fórmula (1.1) no haya otras soluciones?

En realidad, esta pregunta está pidiendo ayuda: para comprobar mi prueba de tentativa, que voy a estado en una respuesta a continuación.


El Steiner-la prueba no está en línea, pero John Simons ha utilizado cuando él extendió la Steiner-método para el 2-ciclo. Su artículo que contiene una paráfrasis es en línea en AMS . Tenga en cuenta que el uso de letras diferentes para las variables a ser coherente con mis propios mayores discusiones

[Añadido]: Empíricamente, la última muestra de la forma de la crítica de la ecuación nunca puede ser satisfecho por $N \gt 1, k \ge 1$ debido a la rhs cae empíricamente entre el fuerte de los límites $$ \small {3^N\over 2^N} \lt {3^N \cdot k -1 \over 2^N\cdot k-1} \lt \Big\lceil {3^N \over 2^N} \Big\rceil \qquad \text{ for }K=1 \ldots \infty$$
(y por lo tanto nunca se llega al siguiente entero por encima de $(3/2)^N$), donde el derecho de la desigualdad se conforma con que conjeturó atado en el Waring-problema, pero que aún no está comprobada.

2voto

Jorrit Reedijk Puntos 129

[update2]: se encontró, que el dado consideraciones a continuación no son completamente suficientes para refutar la existencia de un "trivial" de la solución en la ecuación (1.1) y por lo tanto la refutar de un trivial ciclo, como se pide en la pregunta. Sin embargo, algunos modular restricciones están formulados
(Gracias a Steven a señalar las deficiencias del argumento)[/update2]


Empiezo con la fórmula (1.1) en mi pregunta $$ (2^S - 3^N)\cdot k = 2^B - 1$$ Comprobamos modular condiciones en $k,2^B$ $3^N$ de compatibilidad.

Comenzamos suponiendo que no podría ser una solución existente, donde también se $2^S = 2^N \cdot 2^B \gt 3^N$ e lo $S \gt N \cdot \log_2 3 \approx N \cdot 1.59 $ e lo $B \gt N \cdot 0.59 $

Nos fijamos en k primero:

  1. Corol.: $k \lt 2^B-1$ para cualquier caso no trivial $N \gt 1$.
    Prueba: es obvio que la $ k \le 2^B-1 $, por lo que podemos comprobar, si $k = 2^B-1$ . Esto le da a $ (2^S - 3^N)\cdot (2^B - 1) = 2^B - 1$ y, a continuación, $(2^S - 3^N) = 1 $
    Pero porque consecutivos potencias de 2 y 3 no cuentan con la diferencia de 1 a excepción de $2^2$ $3^1$ debemos tener
    $ \qquad k \lt 2^B-1 $

  2. Corol.: $k \gt 1 $ para cualquier no-trivial ciclo de $N \gt 1$
    Prueba: Supongamos $k=1$. Entonces la ecuación puede escribirse como
    $ \qquad 2^S - 3^N = 2^B - 1 $
    $ \qquad 2^S - 2^B = 3^N - 1 $
    $ \qquad 2^B \cdot (2^N - 1) = 3^N - 1 $
    Nos fijamos en N:
    una. si N es par, entonces la parenthese en el lado izquierdo tiene el primefactor 3 pero no la rhs, por lo que N no puede ser incluso
    b. si N es impar, entonces la parenthese en el lado derecho tiene el primefactor 2 sólo a la primera potencia, por lo $B=1$ y estamos de nuevo llegar a la "trivial ciclo" como única solución

  3. Corol.: $ 3 \le k \le 2^B-3 $ : la posibilidad de un número entero de solución para los principales ecuación depende de modular las restricciones sobre el residuo $3^{-N} \pmod{2^B}$, y por lo tanto la posibilidad de un trivial ciclo.
    Prueba:
    Primero k no puede ser porque a $2^B-1$ es extraño por lo tanto $ 3 \le k \le 2^B-3 $.
    Lo siguiente que escriba los números en modular términos de $ \pmod{2^B}$
    $\qquad 2^S = 2^B \cdot 2^N$
    $\qquad 3^N = 2^B \cdot n + r $ necesariamente $ n \le 2^N - 1$ también $0 \lt r \lt 2^B$
    $\qquad k \equiv 1/r \pmod{2^B}$ debido a la ecuación (1.1) $(2^S - 3^N)\cdot k=2^B-1$ hace $ ( - 3^N)\cdot k \equiv -1 \pmod{2^B}$ . (También debe ser menor que $2^B$)
    Llegamos entonces
    $$ (2^B \cdot 2^N - (2^B \cdot n + r))\cdot k = 2^B - 1 \\ 2^B \cdot (2^N - n)\cdot k - 2^B = r\cdot k -1 \\ (2^N - n)\cdot k = {r\cdot k -1\más de 2^B } +1 $$ En la ecuación del lado izquierdo siempre es $lhs \ge k$, pero el $rhs \le k$ , por lo que esta ecuación sólo puede contener, si ambos lados de la igualdad de k.
    3.1) Para la lhs, esto significa, que el $2^N - n = 2^N - \lfloor 3^N/2^B \rfloor = 1 $
    3.2) Para la rhs esto significa, que k debe ser un divisor de a $2^B-1$ y también debe mantener $k \le r$. La prueba de que la propiedad de la rhs ya estaba dado en un post anterior .

Condición 3.1) no se investigó más a fondo aquí.

Desde 3.2), que fue la intención de la parte para refutar el trivial de 1 ciclo por lo general, se puede
al menos la conclusión, de que el siguiente se tiene:

  1. si $2^B-1$ no tiene divisores (por lo tanto es una de mersenne prime), o ...
  2. si $ 3^N \lt 3^{-N} \pmod{2^B}$ o ...
  3. si el residuo de $ 3^{-N} \pmod{2^B}$ no es un divisor de a $2^B-1$ ...

a continuación, las asociadas a 1 ciclo no puede existir.


Por desgracia, los últimos tres condiciones no se han formulado como una función de N, por lo que este acercamiento elemental todavía no permiten excluir infinitas clases de 1-ciclos (por ejemplo, no se conoce aún, si el número de Mersenne-de los números primos es infinito)

1voto

user157172 Puntos 1

La prueba es mucho más sencilla que eso. Sea odd2 que el segundo entero impar en la secuencia y odd1 ser el punto de partida. Por definición odd2 = (3 * odd1 + 1) / 2 ^ n para algún n entero. En un uno ciclo, odd2 = odd1. Odd1 así = (3 * odd1 + 1) / 2 ^ n así, odd1 = 1/(2^n-3) desde odd1 es un número entero y positivo, y 1 es 2 positivo ^ n-3 debe ser positivo y menor que / igual que el numerador de 1. Desde el 2 ^ n-3 es un entero y lo

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X