La dynamique homomorphe de la suite de Collatz

vendredi 20 janvier 2012
par  Webmestre IREM

PNG - 9.6 ko

Andrzej STOS – Laboratoire de Mathématiques de l’Université Blaise Pascal

Si un nombre est pair, on le divise par 2. S’il est impair, on le multiplie par 3, on lui ajoute 1 et on divise le résultat par 2.

Qui pourrait croire qu’un algorithme si simple puisse conduire à une grande complexité ?

Ainsi, en commençant avec n=10, on obtient la suite suivante :

10 \rightarrow 5 \rightarrow; 8 \rightarrow 4 \rightarrow 2 \rightarrow 1.

Une fois tombée sur 1, la suite tourne en rond :

 1 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow ...

Selon la conjecture de Syracuse (autre terminologie pour cette suite), quelle que soit la valeur initiale n choisie, la suite finira toujours dans la boucle 1,4,2,1,4,2,1,4, .... Très simple, n’est-ce pas ? Proposé dans les années 30 par Lothar Collatz, puis par Stanislaw Ulam dans les années 50, le problème a attiré quelques esprits brillants. P. Erdös l’a qualifiée comme "Hopeless, absolutely hopeless". Il voulait dire que les méthodes connues à ce jour ne laissaient pas espérer un progrès rapide. L’histoire a donné raison à Erdös et la conjecture reste ouverte. Comme quoi, les apparences sont parfois trompeuses...

Ce problème ne sera donc pas résolu dans ce texte ! Mais parce qu’en mathématiques on aime bien faire un petit dessin, entrevoir des généralisations et réaliser des connexions inattendues, on se propose d’explorer la suite de Collatz à l’aide d’un graphique dans le plan complexe.

Dans ce but, on remarque que la suite de Collatz est définie par le processus récursif suivant : son terme initial u_0 est un nombre entier choisi au hasard. Pour définir u_{n+1}, on regarde la parité de u_n. Si u_n est pair, on pose u_{n+1}=u_n/2 et si u_n est impair, on pose u_{n+1}=(3u_n+1)/2. Autrement dit, notre suite est le résultat des itérations de la fonction suivante :

f(n) =\frac{ 1}{4}( 1 + 4n - (-1)n(1 + 2n)).

Puisque (-1)n n’est rien d’autre que \cos(π n), on se propose de regarder la fonction f(z) d’une variable complexe définie par

f(z) = \frac{1}{4}( 1 + 4z -  \cos(πz)(1 + 2z))

.

Etant donnée une valeur initiale z dans le plan complexe, quel est le comportement de la suite des itérés de z par f ? Une fois une valeur initiale choisie, est-ce que la suite des termes successifs s’échappe vers l’infini, c’est-à-dire est-ce que le module des termes peut être arbitrairement grand ? Ou bien, au contraire, la suite reste-t-elle toujours bornée, c’est-à-dire existe-t-il un disque contenant tous les termes de la suite ?

Sur l’image on voit le carré [-3.4, -2.6]x[-0.4i, 0.4i]. En commençant par un point dans la zone noire, on obtient une suite bornée. Les points en jaune foncé donnent lieu à une suite qui s’échappe assez lentement. Dans la zone jaune clair la suite s’échappe rapidement.

L’interprétation visuelle de la conjecture de Syracuse est de voir que tous les points entiers de l’axe des abscisses sont en noir.

PNG - 107 ko

Et voici quelques autres rectangles autour de l’axe des réels dans le plan complexe.

  • [-12.1, -11.9] x [-0.1i, 0.05i] :

PNG - 193.6 ko

  • [-16.09, -15.91] x [-0.1i, 0.1i] :

PNG - 138.3 ko

  • [0.5, 3.5] x [-0.75i, 0.75i] :

PNG - 71.7 ko

  • [5.85, 6.15] x [-0.075i, 0.075i] :

PNG - 106.3 ko

Cela ressemble à un jeu d’enfant, mais en réalité il s’agit bien d’un domaine mathématique plutôt serieux. On l’appelle dymamique holomorphe.


Agenda

<<

2017

 

<<

Août

 

Aujourd'hui

LuMaMeJeVeSaDi
31123456
78910111213
14151617181920
21222324252627
28293031123
Aucun évènement à venir les 6 prochains mois

Annonces

Les projets de programmes de mathématiques au collège (CFEM)

La Commission Française pour l’Enseignement des Mathématiques a publié une page dédiée, qui contient des analyses et des commentaires.

http://www.cfem.asso.fr/actualites/...