El problema 3n+1 : elemental pero temible (I)

Piste verte Le 13 novembre 2011  - Ecrit par  Shalom Eliahou
Le 15 avril 2019  - Traduit par  Mariana Haim
Article original : Le problème 3n+1 : élémentaire mais redoutable (I) Voir les commentaires
Lire l'article en  

Entre todos los problemas matemáticos actualmente no resueltos, ¿cuál es el de enunciado más elemental ? Quizás sea el problema que presentamos aquí : accesible a cualquier escolar de 8 años, desafía a los investigadores desde hace décadas.

El problema $3n+1$ presenta un contraste cautivador : por un lado tiene un enunciado extremadamente simple, por el otro parece extremadamente difícil de resolver. ¿Pero cuál es este problema ? Definimos una regla de transformación sobre los naturales 1,2,3,... como sigue : dado un natural $n$ cualquiera,

  • si $n$ es par, lo dividimos por 2 ;
  • si $n$ es impar, lo multiplicamos por 3 y le sumamos 1.

Por ejemplo, aplicada al número 14, esta transformación da 7, y aplicada al 7 da 22. Escribiremos $14 \rightarrow 7$ y $7 \rightarrow 22$ para resumir, y también $14 \rightarrow 7 \rightarrow 22$ para acortar aún más [1].

De modo más general, vamos a escribir $n \rightarrow m$ para denotar que ’’$n$ se transforma en $m$’’ mediante iteraciones de la transformación de arriba.

El problema $3n+1$ es el siguiente : partamos de un entero positivo cualquiera y apliquémosle esta transformación de manera repetida. ¿Es cierto que tarde o temprano caeremos en el valor 1 ?

Todos los cálculos hechos hasta hoy nos confirman que sí. Pero nadie, después de décadas de planteado el problema, sabe cómo demostrarlo, y no es por no haberlo intentado. De hecho, según el gran Paul Erdös (1913-1996), los matemáticos no serían aún lo suficientemente maduros como para resolver este inocente problema [2].

Un poco de vocabulario

En virtud de quien pareciera ser su primer inventor (en los años 30), llamaremos transformación de Collatz a esta transformación. Además, llamaremos trayectoria de $n$ a la sucesión obtenida partiendo de $n$ e iterando esta transformación.

El problema $3n+1$ consiste entonces en determinar si es cierto que 1 pertenece a cualquier trayectoria.

En realidad esta transformación se conoce con varios nombres : Collatz, Kakutani, Syracuse, etc.

Tres ejemplos

Partamos primero del propio 1. ¿Cuál es su trayectoria ? Es la sucesión
\[ 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \ldots \,. \]
Vemos que caemos efectivamente sobre 1, después de 3 iteraciones ; luego la sucesión $1,4,2$ se repite indefinidamente. Diremos que se trata de un ciclo, en este caso de largo 3.

Como segundo ejemplo, partamos de $n=3$. Obtenemos la sucesión
\[ 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \ldots \,. \]
Nuevamente caemos en 1, esta vez después de 7 iteraciones.

Partiendo ahora de $n=7$, obtenemos la sucesión
\[ \begin{array}{l} & 7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \\ & \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow \ldots \end{array} \]
qui llega a $1$ después de 16 iteraciones

A esta altura, el lector está altamente motivado a elegir otros enteros de partida y a divertirse en calcular sus trayectorias. Es la mejor forma, de hecho, de dar vida, en el confort de su espacio mental, a cualquier tipo de objeto matemático : jugar con él, contextualizarlo, considerarlo bajo todas sus costuras, experimentar.

La trayectoria de 27

Algunas trayectorias son expectaculares y valen la pena de subrayar. La de $n=27$, por ejemplo, es una montaña rusa que sube a alturas inesperadas. Pero aún así, como verán después de algunas decenas de iteraciones, cae en 1.

Varios sitios en Internet permiten calcular estas trayectorias, por ejemplo este [3], o este en francés, citado en el artículo de Wikipedia dedicado a este problema [4].

El logo

El logo de este artículo representa todas las trayectorias que alcanzan el 1 en a lo sumo 18 iteraciones [5]. Una muy bonita animación [6] muestra su construcción progresiva, según el largo maximal de las trayectorias que varía de 1 a 18. Su autor es Jason Davies, quien aceptó gentilmente de proporcionármela en verde, azul y rojo, especialmente para esta serie de artículos, y a quien agradezco mucho. Se puede contemplar este logo en detalle haciendo clic sobre la siguiente imagen :

PNG - 165.6 ko

Récord actual

Un investigador portugués, Tomás Oliveira e Silva, tiene desde 2009 el récord de verificación del problema $3n+1$ por computadora [7]. Verificó que, efectivamente, la trayectoria de todo entero positivo menor a $5 \times 10^{18}$, es decir a 5 billones de billones, contiene al 1. Para empujar la verificación más lejos aún, sus cálculos se retomarán sobre una plataforma más potente en 2012. [8]

Elemental ...

Para comprender el enunciado del problema $3n+1$, vemos que es suficiente conocer los números naturales, saber distinguir los pares de los impares y finalmente manejar operaciones aritméticas simples : sumar 1, multiplicar por 3, dividir por 2. Nada más. Por lo tanto, es accesible a cualquier niño de 8 años normalmente escolarizado, que puede inmediatamente ponerse a calcular trayectorias y a observar su evolución.

... pero temible

El perfil típico del problema $3n+1$ es el de una función simple de definir y de calcular pero cuyo comportamiento luego de iteraciones es dificil de predecir. Es un sistema dinámico discreto [9]. Cientos de investigadores, desde hace décadas, intentaron e intentan resolver este problema que parece tan inocente. De esto surgió una gran cantidad de publicaciones científicas, con resultados parciales y estudios de problemas análogos. Pero hasta hoy, no ha surgido la solución.

Felizmente, un experto llamado Jeff Lagarias decidió crear y mantener, sin interrupción desde 1985, una lista comentada de todos los artículos dedicados a este problema [10]. De hecho, publicó recientemente un libro muy completo sobre el tema, ’’The Ultimate Challenge : The $3x+1$ Problem’’ [11].

¿De todas maneras, es molesto, no ? Los matemáticos, a pesar de su potencia, su profundidad, su eficacia, sus arsenales conceptuales, sus tesoros de ingeniosidad, se tropiezan con un problema que un niño de 8 años puede entender en unos instantes.

Dos sub-problemas

El problema $3n+1$ es una apuesta sobre el comportamiento a largo plazo de las trayectorias de los enteros positivos para la transformación de Collatz ; en concreto, se apuesta que toda trayectoria contiene al 1.

Además de esta apuesta específica, es natural preguntarse cuáles son los comportamientos posibles a largo plazo de una trayectoria cualquiera. Hay dos posibilidades para cada trayectoria :

  • está acotada,
  • no está acotada.

Decir que está acotada significa que por más lejos que se llegue en su recorrido, sus términos son siempre inferiores a cierto techo, cierta cota. Es el caso por ejemplo de la trayectoria del 3, que queda indefinidamente por debajo del 16. La del 7 está acotada por 52, como podemos ver más arriba. Observemos que una trayectoria acotada terminará siempre por contener repeticiones, y por lo tanto por enroscarse en un ciclo. Conocemos bien el ciclo 1, 4, 2, 1, pero ¿hay otros ?

Por otra parte, una trayectoria no acotada tendría la propiedad de dirigirse inexorablemente al infinito, por más que su recorrido se realice en forma de dientes de sierra. Dicho de otra forma, caminando lejos sobre la trayectoria, encontraremos un término que supere 100, yendo más lejos, encontraremos otro superior a 1000, y más lejos aún, otro que supere el 10000, etc. Técnicamente hablando, diríamos que una trayectoria tal diverge.

El problema $3n+1$ se reduce entonces a dos sub-problemas :

  • ¿Es cierto que el único ciclo es 1, 4, 2, 1 ?
  • ¿Es cierto que no hay trayectorias divergentes ?

Hasta hoy, no se tiene solución para ninguno de estos dos sub-problemas. La solución de uno u otro sería de hecho considerada como un gran progreso.

Para comprender mejor esta situación, ilustrémosla en contextos ligeramente diferentes.

Sobre los enteros negativos

Las reglas que definen a la transformación de Collatz, según la paridad del número considerado, conservan todo el sentido si se las aplica a los enteros negativos. Por ejemplo, $-1$ es impar, y se transforma en $3 \times (-1)+1$ es decir en $-2$. Asimismo, $-2 \rightarrow -1$. Observamos entonces, sobre los enteros negativos, un ciclo de largo 2. Ahora bien, ¡sorpresa, no es el único ! Conocemos incluso otros dos :

  • la trayectoria de $-5$, que da un ciclo de largo 5 :
    PNG
  • la de $-17$, que da un ciclo de largo 18 :

Esta presencia de tres ciclos diferentes sobre los entero negativos [12] vuelve aún más interesante la predicción según la cual habría uno solo sobre los enteros positivos.

La variante $5n+1$

Una ligera variante de la transformation de Collatz, en que reemplazamos $3n+1$ por $5n+1$, permite ilustrar simultáneamente los dos sub-problemas. En efecto, para acelerar un poco el camino sobre las trayectorias, reemplazamos $3n+1$ por $(5n+1)/2$ en lugar de por $5n+1$ [13]. Dicho de otro modo, consideremos la siguiente transformación :

  • si $n$ es par, se divide por 2, como antes ;
  • si $n$ es impar, se transforma en $(5n+1)/2$.

Utilizaremos el símbolo $\succ$ para denotar a esta nueva transformación. He aquí un ejemplo de la trayectoria de 1 :
\[1 \succ 3 \succ 8 \succ 4\succ 2\succ 1 \succ \ldots,\]
un bonito ciclo de largo 5. He aquí otro ciclo, esta vez de largo 7 :
\[ 13 \succ 33 \succ 83 \succ 208 \succ 104 \succ 52 \succ 26 \succ 13 \succ \ldots. \]

Partamos ahora de $n=7$. Aquí, un nuevo fenómeno se manifiesta. Miremos los 16 primeros términos de la trayectoria de 7 :
\[ \begin{array}{ll} & 7\succ 18\succ 9\succ 23\succ 58\succ 29\succ 73\succ 183\succ 458 \succ 229 \\& \succ 573\succ 1433\succ 3583\succ 8958\succ 4479\succ 11198. \end{array} \]
Esto trepa bien rápido. Vayamos un poco más lejos en la trayectoria, hasta el milésimo término por ejemplo. Encontramos entonces
\[ 6.857.007.305.798.959.806.990.948.240.228.589.098.703.203.749, \]
un número de 46 cifras. ¿Seguimos ? Agradezco mucho a Jonathan Chappelon que quiso, para este artículo, llevar el cálculo de esta trayectoria hasta su término 21 millonésimo. El número obtenido es tan grande que no puede mostrarse aquí : ¡tiene más de un millón de cifras (exactamente 1.016.568) ! Hay efectivamente une fuerte creencia de que la trayectoria de 7 no está acotada, pero nadie hasta hoy a podido demostrarlo. Peor aún : se piensa que la mayoría de las trayectorias de esta transformación son divergentes, pero nadie sabe probar que existe al menos una que lo sea.

Trayectorias divergentes

¿Por qué entonces parecería haber trayectorias divergentes con $(5n+1)/2$ pero no con $3n+1$, o lo que es lo mismo, no con $(3n+1)/2$ ? Estas también son apenas observaciones empíricas, que necesitan ser probadas ; pero ¿de dónde puede venir esta aparente diferencia de comportamiento ?

Esta es una posible explicación intuitiva. Ella se basa en algunas aproximaciones, una hipótesis osada pero factible y, a fin de cuentas, sobre el hecho de que 5/4 es superior a 1 mientras que 3/4 no lo es.

Caminemos a lo largo de la trayectoria de 7 por ejemplo, primero para la transformación $\succ$, es decir $(5n+1)/2.$ Para pasar de cada término al siguiente, lo multiplicamos por 1/2 si es par, o por aproximadamente 5/2 si es impar. Admitamos que, en el recorrido, encontramos poco a poco tantos pares como impares [14]. Entonces, si caminamos hasta el 21 millonésimo término por ejemplo, este debería valer aproximadamente
\[ 7 \cdot \left(\frac12\right)^{10.500.000} \cdot \left(\frac52\right)^{10.500.000}, \]
es decir
\[ 7 \cdot \left(\frac54\right)^{10.500.000}. \]
Pero como 5/4 es más grande que 1, sus potencias sucesivas crecen indefinidamente. El número de arriba tiene 1.017.556 cifras antes de la coma, lo que da una muy buena aproximación del 21 millonésimo término de la trayectoria de 7 del que se sabe que tiene 1.016.568 dígitos.

Por otra parte, el mismo razonamiento con $(3n+1)/2$ haría intervenir una gran potencia de 3/4, que es menor que 1, por lo que sus potencias sucesivas tienden a 0. Es esto mismo que parece impedir la existencia de trayectorias divergentes para la transformación de Collatz.

Ciclos

Entre los resultados parciales conocidos sobre el problema $3n+1$, está el que afirma que si existiera, contra toda predicción, un ciclo distinto del 1, 4, 2, 1, entonces sería necesariamente gigantesco. Veamos un enunciado más preciso.

Teorema. La transformación de Collatz no admite, sobre los naturales, ningún ciclo de largo comprendido entre 4 y 17.000.000.000.

¿Cómo probar una tal afirmación ? En una continuación de este artículo, lo haremos en tres etapas :

  • primero, mostrando que todo ciclo da lugar a una condición muy restrictiva sobre sus términos,
  • luego, deduciendo de esta condición una estimación fina de la proporción de números pares e impares en el ciclo,
  • finalmente, invocando la teoría de las aproximaciones racionales de un número real.

Para ser eficaz, la tercera etapa utiliza el hecho de que la conjetura del problema $3n+1$ es válida hasta $5\cdot 10^{18}$, lo que fue probado por Tomás Oliveira e Silva.

Conclusión

Innumerables problemas abiertos desafían a las matemáticas. Pero entre ellos, el más elemental ¿no sería el problema $3n+1$ ? Lo que vuelve esto tan convincente es :

  • la accesibilidad de su enunciado a un público muy joven ;
  • su propiedad de ser inmediatamente experimentable a mano.

Esta pregunta podría suscitar un debate en Images des Mathématiques, y contribuir al intercambio de otros problemas abiertos sorprendentes.

Post-scriptum :

El autor agradece a Avner Bar-Hen, Etienne Ghys y Bruno Martin por sus comentarios, y a Carole Gaboriau por su asistencia técnica.
El autor y la redacción de Images des maths agradecen por su atenta lectura a los relectores cuyos seudónimos son los siguientes : Christophe Boilley, Gilles Damamme, Joël Merker, P.Levallois, struffi, Simon Billouet y Jérôme Buzzi.

Article original édité par Étienne Ghys

Notes

[1Los matemáticos son adeptos incorregibles — por necesidad — al ahorro de notación.

[2Yo intenté, durante un congreso en 1995 en el lago Balatonlelle en Hungría, iniciar una conversación con él sobre este problema. Su reacción al tema es muy conocida, como pude verificarlo instantáneamente : ’’That’s hopeless’’, dijo (es decir, ’’no hay esperanza’’).

[3Gracias a Joël Merker por este enlace.

[5Falta la arista $1\rightarrow 4$ por razones ligadas al programa de diseño de grafos.

[6Gracias a Avner Bar-Hen por este enlace.

[8Nota de traducción : por actualizaciones de esta información, consultar aquí

[9Para otro ejemplo de sistema dinámico discreto en Images des Mathématiques, ver el artículo Tourner en rond avec une rotation de Sylvie Ruette.

[10Ver enlace hacia ’’3X+1 Problem’’ en su página web.

[11American Mathematical Society, 2010. Entre otras virtudes, este libro tiene la de subrayar la riqueza de los vínculos entre el problema $3n+1$ y diversas ramas de la matemática, y reproduce varios artículos fundacionales sobre el tema. El enlace a ’’Book : The Ultimate Challenge : The 3x+1 Problem’’ en la página web de Lagarias permite acceder a algunas secciones del libro, del cual también está accesible una síntesis en inglés de 27 páginas en el enlace hacia ’’Preview Material’’.

[12Se conjetura que son los únicos.

[13Observemos que si $n$ es impar, entonces $5n+1$ es par, y entonces se transformaría en $(5n+1)/2$ en el paso siguiente.

[14Esta es la hipótesis osada pero factible.

Partager cet article

Pour citer cet article :

Mariana Haim — «El problema 3n+1 : elemental pero temible (I)» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - El autor agradece a Jason Davies, creador del logo.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?