Transformation du boulanger

La transformation du boulanger, avec étirement puis coupure de la «pâte» et superposition, est l’application du carré ${\displaystyle [0,1[\times [0,1[}$ dans lui-même définie par :

${\displaystyle S(x,y)={\begin{cases}(2x,{\frac {y}{2}})&{\text{si }}0\leqslant x<{\frac {1}{2}}\\(2x-1,{\frac {y+1}{2}}),&{\text{si }}{\frac {1}{2}}\leqslant x<1\end{cases}}}$

Concrètement, le carré, étiré horizontalement dans le rapport 2 et contracté verticalement dans le rapport 1/2, est coupé en deux dans le sens de la hauteur, et les deux morceaux sont superposés.

• 
  Carré de départ
• 
  Carré transformé
• 
  Illustration de l'itération de la transformation continue sur une image formée de points rouge et bleus initialement séparés.

Cette transformation est bijective, et préserve la mesure de Lebesgue deux-dimensionnelle (la mesure d'aire).

Cette version est souvent évoquée en théorie du chaos, à cause de la sensibilité aux conditions initiales lorsqu'on répète indéfiniment la transformation.

La version continue où le deuxième demi-pâton subit une rotation de 180° avant d'être placé sur le premier demi-pâton est définie par :

${\displaystyle T(x,y)={\begin{cases}(2x,{\frac {y}{2}})&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\(2-2x,1-{\frac {y}{2}}),&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$

La transformation du fer à cheval de Smale est une autre version où l'on tient compte du coude opéré par le repliement de la pâte.

Il existe des versions unidimensionnelles de ces deux transformations^[1], définies sur ${\displaystyle [0,1]}$ par ${\displaystyle t(x)={\begin{cases}2x&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\2-2x,&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$, appelée aussi fonction tente, et ${\displaystyle s(x)={\begin{cases}2x&{\text{si }}0\leqslant x\leqslant {\frac {1}{2}}\\2x-1,&{\text{si }}x>{\frac {1}{2}}\end{cases}}}$.

Il semblerait que c'est sous la forme unidimensionnelle que la transformation du boulanger ("baker's map") a été définie en 1937 par Eberhard Hopf^[2],[3].

Cette version a été introduite en 1997 par Jean-Paul Delahaye et Philippe Mathieu^{[4],[5],[6],[7]}.

On considère une image informatique formée de ${\displaystyle (n\times p)}$ pixels placés en ${\displaystyle (i,j)\in [|0,n-1|]\times [|0,p-1|]}$ ^[8],[9].

Dans la première étape (étirement), le pixel placé en ${\displaystyle (i,j)}$ est envoyé à la place${\displaystyle (i_{1},j_{1})=(\mathrm {quotient} (i,2),2j+\mathrm {reste} (i,2))}$ soit ${\displaystyle {\begin{cases}(i/2,2j)&{\text{si }}i{\text{ est pair}}\\(\lfloor i/2\rfloor ,2j+1)&{\text{si }}i{\text{ est impair}}\end{cases}}}$, ce qui donne une image de dimensions ${\displaystyle (n/2\times 2p)}$.

Dans la deuxième étape (repliement avec rotation), le pixel placé en ${\displaystyle (i_{1},j_{1})}$ est envoyé en ${\displaystyle (i',j')={\begin{cases}(i_{1},j_{1})&{\text{si }}j_{1}<p\\(n-1-i_{1},2p-1-j_{1})&{\text{si }}j_{1}\geqslant p\end{cases}}}$, ce qui redonne une image ${\displaystyle (n\times p)}$.

Par exemple, pour ${\displaystyle n=p=2}$, le tableau ${\displaystyle {\begin{array}{|c|c|c|}\hline (i,j)&j=0&j=1\\\hline i=0&a&b\\\hline i=1&c&d\\\hline \end{array}}}$ est transformé en ${\displaystyle {\begin{array}{|c|c|c|c|c|c|}\hline (i_{1},j_{1})&0&1&2&3\\\hline 0&a&c&b&d\\\hline \end{array}}}$ puis en ${\displaystyle {\begin{array}{|c|c|c|}\hline (i',j')&0&1\\\hline 0&a&c\\\hline 1&d&b\\\hline \end{array}}}$.

Pour ${\displaystyle n=p=3}$, ${\displaystyle {\begin{array}{|c|c|c|}\hline a&b&c\\\hline d&e&f\\\hline g&h&i\\\hline \end{array}}}$ est transformé en ${\displaystyle {\begin{array}{|c|c|c|c|c|c|c|}\hline a&d&b&e&c&f\\\hline g&&h&&i\\\hline \end{array}}}$, puis en ${\displaystyle {\begin{array}{|c|c|c|}\hline a&d&b\\\hline g&i&h\\\hline f&c&e\\\hline \end{array}}}$.

L'application de l'ensemble fini ${\displaystyle [|0,n-1|]\times [|0,p-1|]}$ dans lui-même est une permutation donc est d'ordre fini. Le temps de retour est le nombre d'étapes pour que tous les pixels reviennent à leur place originelle lorsqu'on effectue une succession de transformations du boulanger ; c'est le PPCM des temps de retour de chaque pixel^[6].

Pour ${\displaystyle (n,p)=(2^{k},2^{l})}$, le temps de retour est égal à ${\displaystyle k+l+1}$, mais on ne connait pas de loi générale donnant ce temps d'attente^[6].

Voici quelques valeurs des temps de retour pour une image carrée de ${\displaystyle (n\times n)}$ pixels^[6] ( A393817):

Davantage d’informations ...

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	1	3	6	5	72	60	18	7	660	556 920	770	1 008	985 320	339 660	34 320	9

Fermer