Votre boulanger est-il discret? (1/2)

Quelle différence faites-vous entre l’infini et le « très très grand »? Comment vous représentez-vous l’ensemble des nombres rationnels contenus dans l’intervalle [0,1]? Bon, je ne vous sens pas franchement emballés par mes questions métaphysiques, mais ne zappez pas tout de suite! Pour y répondre, je vous propose un phénomène bluffant qui non seulement prend vos intuitions à contre-pied, mais qui illustre également la différence qualitative entre fini et infini, discret et continu. Et si au pire vous n’y comprenez rien, l’effet spectaculaire en vaut la peine, promis!

PART1: quelle différence entre fini et infini?

Pour bien mélanger son pétrin, le boulanger prend un carré de pâte, l’étire dans un sens puis le replie pour retomber sur son carré initial et il recommence: il étire puis replie pendant une bonne demi-heure (ça muscle!):

La transformation du boulanger

Si au lieu de faire ça avec une pâte à pain, on s’amuse à faire la même chose avec une image numérique, l’image se brouille très vite:Assez rapidement l’image se brouille…

Evidemment, comme on ne peut pas étirer chaque pixel on a un tout petit peu triché: pour étirer une ligne, on est obligé d’interpénétrer chaque ligne paire avec la ligne impaire suivante avant de replier le tout.

Les mystères de l’éternel retour

L’avantage sur la pâte à pain, c’est que c’est moins fatigant à faire et surtout ça va beaucoup plus vite. Au lieu de s’arrêter au bout d’une dizaine de mélanges comme ce feignant de boulanger, on peut laisser le logiciel tourner des milliers de fois. C’est le miracle de la technique. Mais le plus miraculeux c’est surtout qu’au bout d’un moment, l’image du départ revient comme par magie!

Magique!

Cette transformation très simple aurait-elle des propriétés spéciales? Même pas: on trouve sur internet plein d’autres transformations très différentes qui bouclent sur elles-mêmes de la même façon. Par exemple celle du photomaton qui « disperse » l’image initiale dans les quatre quarts du carré avant de recommencer:

La transformation du photomaton appliquée à l’image de la Joconde

Je me disais qu’il devait être affreusement compliqué de démontrer que « ça boucle », d’autant que le nombre d’itérations nécessaires pour retomber sur ses pieds est très sensible au nombre de pixels de l’image. La démonstration que propose JP Delahaye [1] est pourtant incroyablement simple.

Numérotons les pixels de l’image de 1 à N en fonction de leur position. La  transformation du boulanger envoie le pixel en position X1 à une position X2 qui lui est exclusivement réservée. La transformation du boulanger est donc une bijection entre les N pixels de l’image.  Appliquons  itérativement  cette transformation bijective à notre pixel situé  initialement en position X1, il devient:
X1->X2->X3->X4->….->XN
Puisque la transformation est bijective et qu’il n’y a que N pixels possibles, un peu de réflexion vous convaincra que notre point reviendra fatalement à sa position d’origine en X1 au bout d’un certain nombre d’itérations. Ansi à chaque pixel de l’image correspond un cycle de longueur inférieure à N, cycle au terme duquel il revient à sa position de départ. Tous les pixels appartenant à un cycle de longueur 10, reviennent à leur position initiale au bout de 10 transformations, 20, 30, 40 etc.
Evidemment deux pixels différents peuvent appartenir à des cycles de  longueurs différentes l1 et l2, mais ils seront tous les deux revenus à leur position initiale au bout de l1*l2 cycles.
On peut en principe connaître la liste de toutes les longueurs de cycles correspondant aux pixels d’une image. Supposons par exemple qu’il n’y ait que trois cycles possibles, de longueur 3, 7 et 10. L’image reviendra identique à elle-même au bout de 3*7*10=210 itérations.
De façon générale, si l’on connaît toutes les longueurs de cycle d’une image, le « temps de retour » de l’image sera égal au plus petit commun multiple de toutes les longueurs de cycles. Dans le pire des cas (si chaque point appartient à un cycle de longueur différente) l’image initiale revient au bout de N! cycles. Ca peut être long, mais ça marche à tous les coups!

Tout s’explique!
Ce raisonnement est valable quelle que soit la nature de la transformation (Boulanger, photomaton ou autre), il suffit juste qu’elle soit bijective. Rigolo non? Au passage, cette démonstration aide à comprendre pourquoi au cours des itérations on voit de temps en temps apparaître  l’image initiale un peu brouillée: c’est le cas chaque fois que le nombre d’itérations est un multiple des longueurs de cycles les plus fréquentes. Les très nombreux pixels correspondant à ces cycles sont alors revenus à leur position initiale – c’est ce qui fait qu’on reconnaît l’image- mais pas les autres -c’est ce qui fait que l’image est floue: