¿Qué importancia tiene la conjetura de Collatz?

Question

Me ha fascinado la Problema de Collatz desde que oí hablar de ella por primera vez en el instituto.

Tomemos cualquier número natural $n$ . Si $n$ es par, divídalo por $2$ para obtener $n / 2$ si $n$ es impar multiplícalo por $3$ y añada $1$ para obtener $3n + 1$ . Repite el proceso indefinidamente. La conjetura es que no importa con qué número se empiece, siempre se llegará finalmente a $1$ . [...]

Paul Erdos dijo sobre la conjetura de Collatz: "Las matemáticas aún no están preparadas para este tipo de problemas". Ofreció 500 dólares por su solución.

¿Qué importancia considera que tiene la respuesta a esta pregunta? ¿Por qué?

¿Especularía sobre lo que podría haber poseído a Paul Erdos para hacer semejante oferta?

EDIT: ¿Hay alguna razón para pensar que una prueba de la Conjetura de Collatz sería compleja (como la FLT) en lugar de simple (como PRIMES lo es en P)? ¿Y puede esta caracterización de FLT vs. PRIMES está en P ser más específica que una comparación de longitud de bits?

Answer 1

Hasta ahora, la mayoría de las respuestas han ido en la línea general de "Por qué son importantes los problemas difíciles", más que en la de "Por qué es importante la conjetura de Collatz"; intentaré abordar esta última.

Creo que la cuestión básica que se toca es:

¿De qué manera la factorización en primos de $a$ afectan a la factorización en primos de $a+1$ ?

Por supuesto, siempre se puede multiplicar la factorización en primos, añadir uno y luego factorizar de nuevo, pero esto desecha la información de la factorización en primos de $a$ . Tenga en cuenta que esta pregunta también tiene sentido en otras UFD, como $\mathbb{C}[x]$ .

Parece muy difícil dar respuestas a esta pregunta que no caigan bajo el epígrafe de "inmediatas", como primos distintos en cada factorización. Esto parece deberse en parte a que un pequeño cambio en la factorización de primos para $a$ (multiplicación por un primo, digamos) puede tener un gran cambio en la factorización de primos para $a+1$ (apoyo principal totalmente distinto quizás). Por lo tanto, es tentador considerar el acto de añadir 1 como un barajado esencialmente aleatorio de la factorización de primos.

Lo más sorprendente de la conjetura de Collatz es que parece estar haciendo una profunda afirmación sobre una sutil relación entre las factorizaciones primos de $a$ y $a+1$ . Obsérvese que la iteración de Collatz consta de tres pasos; dos de ellos son "pequeños" en términos de la factorización en primos, y el otro es la suma de uno:

• multiplicar por 3 tiene un pequeño efecto en la factorización.
• añadir 1 tiene un efecto (posiblemente) enorme en la factorización.
• factorizar una potencia de 2 tiene un efecto pequeño en la factorización (en el sentido de que no cambia las otras potencias primos en la factorización).

Así pues, la conjetura de Collatz parece decir que hay algún tipo de cantidad abstracta como la "energía" que no puede aumentarse arbitrariamente añadiendo 1. Es decir, no importa por dónde se empiece, y no importa a dónde nos lleve esta extraña acción de barajar primos de añadir 1, al final el acto de sacar 2s extrae suficiente energía del sistema como para que lleguemos a 1. Creo que por razones como ésta los matemáticos sospechan que la solución de la conjetura de Collatz abrirá nuevos horizontes y desarrollará nuevas e importantes técnicas en la teoría de números.

Answer 2

La conjetura de Collatz es el problema abierto más sencillo de las matemáticas. Puedes explicárselo a todos tus amigos no matemáticos, e incluso a niños pequeños que acaban de aprender a dividir por 2. No requiere entender la divisibilidad, sólo la igualdad.

La falta de conexiones entre esta conjetura y las teorías matemáticas existentes (como se denuncia en algunas otras respuestas) no es una insuficiencia de esta conjetura, sino de nuestras teorías.

Este problema ha llevado directamente al trabajo teórico de Conway que demuestra que preguntas muy similares son formalmente indecidibles un resultado ciertamente sorprendente.

El problema también está directamente relacionado con los autómatas celulares caóticos. Si observamos un número en base 6, veremos que multiplicar por 3 y dividir por 2 son la misma operación (sólo difieren en un factor de 6), es decir la ubicación del punto decimal), y la operación es local: cada nuevo dígito sólo depende de dos de los dígitos del paso anterior. Utilizando un 7º estado para las celdas que no forman parte del número, se obtiene un autómata celular muy sencillo en el que cada celda sólo tiene que mirar a un vecino para calcular su siguiente valor. _{(Wolfram Mathworld tiene alguna tontería sobre que una implementación de CA es difícil debido a los acarreos, pero no hay acarreos cuando se suma 1, porque después de multiplicar por 3 el último dígito es 0 (se convierte en un no-dígito porque el número era par así que debemos dividir por 6) o 3 (se convierte en 4), así que nunca hay acarreos).}

Es fácil demostrar que este AC es caótico: Si se cambian los dígitos interiores en cualquier manera, la región de dígitos afectados siempre crece linealmente con el tiempo (por $\log_6 3$ dígitos por paso). Esto evita cualquier ingeniería de los patrones de dígitos, que se aleatorizan rápidamente. Si el dígito final se comporta aleatoriamente, entonces la conjetura es cierta. Claramente cualquier avance en la conjetura de Collatz tendría consecuencias inmediatas para la dinámica simbólica .

Emil Post sistemas de etiquetas (que creó en 1920 expresamente para estudiar la fundamentos de las matemáticas ) se han estudiado durante muchas décadas, y han sido la base de las máquinas de Turing universales más pequeñas (así como de otros sistemas universales) desde 1961. En 2007, Liesbeth De Mol descubrió que el problema de Collatz puede codificarse como el siguiente sistema de etiquetas:

$\begin{eqnarray} \hspace{2cm} \alpha & \longrightarrow & c \, y \\ \hspace{2cm} c & \longrightarrow & \alpha \\ \hspace{2cm} y & \longrightarrow & \alpha \alpha \alpha \\ \end{eqnarray}$

En dos pasadas, este sistema de etiquetas procesa la palabra $\alpha^{n}$ en $\alpha^{n/2}$ o $\alpha^{(3n+1)/2}$ en función de la paridad de $n$ . Se sabe que los sistemas de etiquetas más grandes son universales, y cualquier avance en el problema 3x+1 será seguido con atención por este campo.

En resumen, el problema de Collatz es lo suficientemente sencillo como para que cualquiera pueda entenderlo y, sin embargo, no sólo está relacionado con la teoría de números (como se describe en otras respuestas), sino con cuestiones de decidibilidad, caos y los fundamentos de las matemáticas y de la computación. Es lo mejor que se puede hacer para un problema que hasta un niño pequeño puede entender.

Answer 3

Muchos matemáticos, y entre ellos algunos famosos, han intentado varias formas de atacar este problema, y sigue siendo tan difícil de resolver como cuando se planteó por primera vez. Así pues, la importancia del problema radica en que habrá que crear ideas matemáticas realmente nuevas para resolverlo, y tales ideas pueden ser útiles en otros ámbitos en los que estén en juego problemas "verdaderamente importantes". Obsérvese que el propio Erdős ha dicho algo parecido a que "aún no tenemos las matemáticas para resolver este problema".

Answer 4

No creo que se trate de un problema conceptualmente importante. Es un ejemplo de problema realista que puede comprobarse numéricamente hasta un valor grande y que se ha resistido a una solución durante muchos años. No todos los problemas de este tipo son automáticamente importantes (por ejemplo, la inexistencia de números perfectos Impares).

Una analogía con el significado del último teorema de Fermat es adecuada. Antes de que se estableciera el vínculo entre la FLT y las conjeturas profundas de las curvas elípticas, no había una importancia global en saber si la FLT era cierta o no. (Creo que el vínculo entre la FLT y la conjetura abc se estableció más o menos al mismo tiempo). Sí, el trabajo sobre la FLT fue responsable de desarrollos útiles en la teoría algebraica de números, pero al mismo tiempo no estuvo claro durante mucho tiempo que resolver el problema, o más bien encontrar un contraejemplo, tuviera alguna otra repercusión.

Si mañana alguien demostrara que la conjetura de Collatz es una consecuencia de la conjetura abc o de algún otro problema importante sin resolver, entonces cambiaría de opinión sobre su importancia (porque, como en el caso del vínculo entre la conjetura de modularidad y la FLT, un contraejemplo de Collatz tendría implicaciones reales en otros campos de las matemáticas). Pero mientras permanezca aislada, sin implicaciones para otros problemas, no creo que por sí sola sea una cuestión matemáticamente profunda. Lo mismo ocurre con los números perfectos impar: a menos que alguien demuestre que la existencia de un número perfecto impar tiene efectos en otros lugares que no esperamos (como un contraejemplo a la FLT que tenga una implicación muy inesperada para las curvas elípticas), no creo que la corriente dominante considere que los números perfectos impar sean importantes tampoco.

Desde el punto de vista pedagógico, sin embargo, reconozco que se trata de un buen problema para mostrar a los estudiantes no familiarizados con las matemáticas avanzadas que realmente existen problemas matemáticos sin resolver. La gente no necesariamente se da cuenta de esto, por ejemplo, pueden pensar que todo puede ser resuelto por ordenadores o algo así.

Answer 5

Creo que el $3x+1$ El problema se considera un caso de prueba para la teoría ergódica, es decir, demostrar que ciertas expectativas probabilísticas son verdaderas para las órbitas de un sistema específico. Hay trabajos de Sinai, Lagarias y otros que ofrecen modelos probabilísticos, similares a las predicciones asintóticas realizadas en cuestiones sobre distribución de números primos, en los que las predicciones son fiables, pero probarlas en algún caso particular (primos gemelos, $n^2+1$ Goldbach, ...) es un problema abierto desde hace siglos.

Esto es análogo a las pruebas de trascendencia o irracionalidad de números concretos: demostrar que lo que es "cierto con probabilidad 1" se cumple realmente en un caso concreto es extremadamente difícil y hace avanzar la teoría. Aparte de eso, no hay problemas fuera de la $3x+1$ conjetura que utilizan la misma iteración, por lo que es un sumidero y no una fuente en el gráfico de aplicaciones de la teoría.