%Format: LaTeX
%
% Colloque "Algorithmique et Programmation", Luminy 1998
% Pavages et p{\'e}riodicit{\'e}
% Auteur: Bruno Petazzoni bpetazzoni@sancerre.ac-idf.jussieu.fr

\documentclass[portrait,a4]{seminar}\nofiles

\usepackage{amssymb,semlayer,fancybox}
\usepackage[applemac]{inputenc}
\usepackage[francais]{babel}
\usepackage{bruno}
\usepackage{epic,autograph}         % pour dessiner des automates

\newcommand{\wangtile}[4]{%
 \setlength\unitlength{2pt}
 \begin{picture}(18,18)
 \put(1,1){\line(1,0){16}}
 \put(17,1){\line(0,1){16}}
 \put(1,1){\line(0,1){16}}
 \put(1,17){\line(1,0){16}}
 \put(2,9){\makebox(0,0)[l]{\small #1}}
 \put(9,16){\makebox(0,0)[tc]{\small #2}}
 \put(9,2){\makebox(0,0)[bc]{\small #3}}
 \put(16,9){\makebox(0,0)[r]{\small #4}}
 \end{picture}
}

\newcommand{\ooo}[1]{$-{#1}$}

\newcommand{\titre}[1]{%
 \noindent\rule{0pt}{4pt}\par
 \begin{center}
  \shadowbox{\Large\textsf{#1}}
 \end{center}
}

\begin{document}

\slideframe{Oval}
\pagestyle{plain}

% vue 1

\begin{slide*}

\titre{Pavages de Wang}

Une \emph{tuile de Wang} est un carr{\'e} dont les quatre c{\^o}t{\'e}s sont 
marqu{\'e}s (avec un signe particulier ou une couleur, par exemple).

On r{\'e}alise un \emph{pavage de Wang} en pla{\c c}ant de telles tuiles 
c{\^o}te {\`a} c{\^o}te (sans les faire tourner), 
de fa{\c c}on que les marques adjacentes soient 
identiques; un pavage de Wang est donc une application $f$ 
de $\Z^2$ vers le jeu de tuiles, respectant certaines 
contraintes (locales).

Probl{\`e}me de Wang: un jeu (fini) de tuiles de Wang donn{\'e} 
permet-il de paver le plan ?

Ce probl{\`e}me est \emph{d{\'e}cidable} s'il existe un algorithme qui 
prend en entr{\'e}e un jeu de tuiles de Wang, et dit si l'on peut paver 
le plan avec ce jeu.

\vfill
\end{slide*}

% vue 2

\begin{slide*}

\titre{Exemples de jeux de tuiles}

On peut paver le plan avec ce premier jeu de tuiles:

\begin{center}
\wangtile2893 \wangtile6214 \wangtile1452 

\wangtile3121 \wangtile4545 \wangtile5986 
\end{center}

\bigskip

On ne peut pas paver le plan avec ce deuxi{\`e}me jeu de tuiles:

\begin{center}
\wangtile2223 \wangtile1112 \wangtile3121
\end{center}

Exercice: d{\'e}montrez-le!

\vfill
\end{slide*}

% vue 3

\begin{slide*}

\titre{Solutions}

Premier jeu de tuiles: on pave un rectangle $2 \times 3$, qui fournit 
un pavage de p{\'e}riode $(3,2)$.

\begin{center}
\wangtile2893 \wangtile3121 \wangtile1452

\wangtile5986 \wangtile6214 \wangtile4545 
\end{center}

\bigskip

Deuxi{\`e}me jeu de tuiles: il n'y a qu'une fa{\c c}on d'aligner les tuiles 
horizontalement, or le rapport 1/2 n'est pas le m{\^e}me sur le bord haut 
et sur le bord bas.

\begin{center}
 \wangtile2223 \wangtile3121 \wangtile1112 
\end{center}

\vfill
\end{slide*}

% vue 4

\begin{slide*}

\titre{P{\'e}riodicit{\'e}}

Un pavage de Wang $f$ est \emph{doublement p{\'e}riodique} s'il existe $a$ et $b$ 
tous deux non nuls tels que 
$$
 f(x+a,y) = f(x,y+b) = f(x,y)
$$ 

quel que soit $(x,y)\in\Z^2$.

Un pavage est \emph{simplement p{\'e}riodique} s'il existe $(a,b)$ non nul 
tel que $f(x+a,y+b)=f(x,y)$ pour tout $(x,y)\in\Z^2$.

Th{\'e}or{\`e}me (Wang): si un jeu de tuiles permet de r{\'e}aliser 
un pavage simplement p{\'e}riodique, alors il permet aussi de r{\'e}aliser 
un pavage doublement p{\'e}riodique.

Preuve: on se contentera du cas $b=0$.

Un jeu de tuiles de Wang est \emph{ap{\'e}riodique} s'il permet 
de paver le plan, mais pas de fa{\c c}on p{\'e}riodique.

\vfill
\end{slide*}

% vue 5

\begin{slide*}

\titre{Th{\'e}or{\`e}mes et conjectures}

Th{\'e}or{\`e}me: si un jeu de tuiles de Wang permet de paver des carr{\'e}s 
arbitrairement grands, il permet de paver le plan entier.

Preuve: c'est le lemme de Koenig.

Th{\'e}or{\`e}me (Wang): s'il n'existe pas de jeu de tuiles ap{\'e}riodique, 
alors le probl{\`e}me de Wang est d{\'e}cidable.

Conjecture (Wang): il n'existe pas de jeu de tuiles ap{\'e}riodique.

Th{\'e}or{\`e}me (Berger 1966): il existe des jeux de tuiles ap{\'e}riodiques, 
et le probl{\`e}me de Wang n'est pas d{\'e}cidable.

\emph{Berger a exhib{\'e} un jeu ap{\'e}riodique de 20426 tuiles…}

\vfill
\end{slide*}

% vue 6

\begin{slide*}

\titre{Suites de Beatty}

Au r{\'e}el $\alpha$, on associe la \emph{suite de Beatty} de terme g{\'e}n{\'e}ral 
$A(\alpha)_i = \lfloor i \alpha \rfloor$, o{\`u} $i\in\Z$.

La suite $B(\alpha)$ de terme g{\'e}n{\'e}ral 
$$
 B(\alpha)_i = A(\alpha)_{i+1} - A(\alpha)_i 
$$
 
est la \emph{repr{\'e}sentation {\'e}quilibr{\'e}e} 
de $\alpha$; elle est aussi connue sous les noms de 
\emph{suite caract{\'e}ristique}, ou \emph{suite de Christoffel}.

Remarque: si $k≤\alpha≤k+1$ (o{\`u} $k\in\Z$) alors les termes de 
la suite $B(\alpha)$ sont {\'e}gaux {\`a} $k$ ou {\`a} $k+1$. De plus:
$$
 \left| \ell\alpha - \sum_{j≤i<j+\ell} B(\alpha)_i \right| < 1 
$$

\emph{\small Note du relecteur: cette in{\'e}galit{\'e} n'a aucun int{\'e}r{\^e}t. 
Le pr{\'e}sentateur veut juste se faire mousser.}
\smallskip

\emph{\small Note du pr{\'e}sentateur: le relecteur est pri{\'e} d'aller 
voir l{\`a}-haut sur la colline.}

\vfill
\end{slide*}

% vue 7

\begin{slide*}

\titre{Automates {\`a} deux bandes}

Un \emph{automate {\`a} deux bandes} est un quadruplet 
$(Q,\Sigma,\Delta,\gamma)$ o{\`u} $Q$ est l'ensemble (fini) des {\'e}tats, 
$\Sigma$ l'alphabet d'entr{\'e}e, $\Delta$ l'alphabet de sortie et 
$\gamma \subset Q \times \Sigma \times \Delta \times Q$ est 
la table des transitions.

Soient $x \in \Sigma^\Z$ et $y \in \Delta^\Z$ deux mots biinfinis; 
on dira que l'automate associe $y$ {\`a} $x$ s'il existe une suite 
$(s_i)_{i\in\Z}$ d'{\'e}tats telle que 
$$
 (s_i,x_i,y_i,s_{i+1}) \in \gamma \mbox{ pour tout } i\in\Z 
$$

\vfill
\end{slide*}

% vue 8

\begin{slide*}

\titre{Multiplication par $q=\frac{n}{m}$}

Soit $q=\frac{n}{m}$ un rationnel positif; 
construisons un automate {\`a} deux bandes $M_q$ 
qui r{\'e}alise (en un certain sens) la multiplication par $q$ d'un r{\'e}el 
donn{\'e} par sa repr{\'e}sentation {\'e}quilibr{\'e}e.

Les {\'e}tats de $M_q$ sont les valeurs 
possibles de $q \lfloor x \rfloor - \lfloor qx \rfloor$ 
lorsque $x$ d{\'e}crit $\R$.

Comme 
$-q < \lfloor qx \rfloor - q \lfloor x \rfloor < 1$, 
et que ces valeurs sont des multiples de $\frac{1}{m}$, 
on aura $M_q = \bigl\{ - \frac{n-1}{m}, - \frac{n-2}{m}, \ldots, 
 \frac{m-2}{m}, \frac{m-1}{m} \bigr\}$.

Les alphabets d'entr{\'e}e et de sortie sont des parties finies 
de $\Z$; les transitions de $M_q$ sont les quadruplets $(s,a,b,t)$ 
tels que $s+qa=b+t$. 

On v{\'e}rifie que, si $B(\alpha)$ peut {\^e}tre {\'e}crit avec l'alphabet $\Sigma$ 
et $B(q\alpha)$ avec l'alphabet $\Delta$, alors l'automate associe 
$B(q\alpha)$ {\`a} $B(\alpha)$: pour s'en convaincre, prendre 
$s_i = q A(\alpha)_i - A(q\alpha)_i$.

\vfill
\end{slide*}

% vue 9

\begin{slide*}

\titre{Multiplication par 3}

Exemple: l'automate {\`a} deux bandes $M_3$ ci-dessous effectue la multiplication 
par 3 d'un r{\'e}el $\alpha\in\bigl[\frac{1}{3},\frac{2}{3}\bigr]$; 
plus pr{\'e}cis{\'e}ment, si $\alpha \in \bigl[\frac{1}{3},\frac{2}{3}\bigr]$ 
alors l'automate associe $B(3\alpha)$ {\`a} $B(\alpha)$.
\bigskip

\begin{center}
\setlength\unitlength{3pt}
\begin{picture}(50,30)(0,0)

\thinlines

\letstate A=(5,15) \drawstate(A){$-2$}
\letstate B=(25,15) \drawstate(B){$-1$}
\letstate C=(45,15) \drawstate(C){$0$}

\setprofcurve{+3}
\drawcurvedtrans(A,B){$1{,}2$}
\drawcurvedtrans(B,C){$1{,}2$}
\drawcurvedtrans(B,A){$0{,}1$}
\drawcurvedtrans(C,B){$0{,}1$}

\setprofcurve{+12}
\drawcurvedtrans(A,C){$1{,}1$}
\drawcurvedtrans(C,A){$0{,}2$}

\end{picture}
\end{center}

\vfill
\end{slide*}

% vue 10

\begin{slide*}

\titre{Exemple de multiplication par 3}

$\alpha=\frac{2}{5}$ a pour repr{\'e}sentation {\'e}quilibr{\'e}e $\ldots 00101 \ldots$

$3\alpha=\frac{6}{5}$ a pour repr{\'e}sentation {\'e}quilibr{\'e}e $\ldots 11112 \ldots$

\begin{center}
\begin{tabular}{|r|r|r|r|r|r|r|}
\hline
$i$            & 0    & 1    & 2    & 3    & 4    & 5    \\
\hline
$A(\alpha)_i$  & 0    & 0    & 0    & 1    & 1    & 2    \\
\hline
$A(3\alpha)_i$ & 0    & 1    & 2    & 3    & 4    & 6    \\
\hline
$s_i$          & 0    & $-1$ & $-2$ & 0    & $-1$ & 0    \\
\hline
$x_i$          & 0    & 0    & 1    & 0    & 1    & 0    \\
\hline
$y_i$          & 1    & 1    & 1    & 1    & 2    & 1    \\
\hline
$s_{i+1}$      & $-1$ & $-2$ & 0    & $-1$ & 0    & $-1$ \\
\hline
\end{tabular}
\end{center}

\vfill
\end{slide*}

% vue 11

\begin{slide*}

\titre{Multiplication par $\frac{1}{2}$}

De m{\^e}me, l'automate {\`a} deux bandes $M_{1/2}$ ci-dessous associe $B(\alpha/2)$ 
{\`a} $B(\alpha)$ pour $\alpha\in[0,2]$; l'alphabet d'entr{\'e}e est 
$\{0,1,2\}$ tandis que l'alphabet de sortie est $\{0,1\}$.
\bigskip

\begin{center}
\setlength\unitlength{3pt}
\begin{picture}(30,30)(0,0)

\thinlines

\letstate A=(5,15) \drawstate(A){$0$}
\letstate B=(25,15) \drawstate(B){$\frac{1}{2}$}

\setprofcurve{+3}
\drawcurvedtrans(A,B){$1{,}0$}
\drawcurvedtrans(B,A){$1{,}1$}

\drawloop[t](A){$2{,}1$}
\drawloop[t](B){$2{,}1$}
\drawloop[b](A){$0{,}0$}
\drawloop[b](B){$0{,}0$}

\end{picture}
\end{center}

\vfill
\end{slide*}

% vue 12

\begin{slide*}

\titre{Le jeu de tuiles de Kari et \v{C}ulik}

{\`A} la transition $(s,a,b,t)$ nous associons la tuile de Wang ci-dessous:

\begin{center}
\wangtile{$s$}{$a$}{$b$}{$t$}
\end{center}

{\`A} l'automate $M_3$ exhib{\'e} pr{\'e}c{\'e}demment, nous associons donc le jeu 
de 6 tuiles $T_3$ ci-dessous:

\begin{center}
\wangtile001{\ooo1} \wangtile{\ooo1}01{\ooo2} \wangtile{\ooo2}12{\ooo1} 

\wangtile{\ooo1}120 \wangtile{\ooo2}110 \wangtile002{\ooo2} 
\end{center}

Il est clair que ce jeu ne permet pas, {\`a} lui tout seul, de paver le plan.

\vfill
\end{slide*}

% vue 13

\begin{slide*}

Pour des raisons techniques qui s'{\'e}clairciront plus tard, nous 
utiliserons pour la multiplication par $\frac{1}{2}$ l'automate 
$M_{1/2}'$ ci-dessous: ses {\'e}tats sont $0'$ et $\frac{1}{2}$; 
l'alphabet d'entr{\'e}e est $\{0',1,2\}$, celui de sortie 
est $\{0,0',1\}$. Les {\'e}tats sont $0'$ et $\frac{1}{2}$; 
ses transitions sont celles de $M_{1/2}$ (dans lesquelles on remplace 
l'{\'e}tat et la lettre d'entr{\'e}e 0 par $0'$), 
plus une nouvelle transition $(0',1,0',\frac{1}{2})$.
\bigskip

\begin{center}
\setlength\unitlength{3pt}
\begin{picture}(30,30)(0,0)

\thinlines

\letstate A=(5,15) \drawstate(A){$0'$}
\letstate B=(25,15) \drawstate(B){$\frac{1}{2}$}

\setprofcurve{+6}
\drawcurvedtrans(A,B){$1{,}0$}
\drawcurvedtrans(B,A){$1{,}1$}
\drawtrans(A,B){$1{,}0'$}

\drawloop[t](A){$2{,}1$}
\drawloop[t](B){$2{,}1$}
\drawloop[b](A){$0'{,}0$}
\drawloop[b](B){$0'{,}0$}

\end{picture}
\end{center}

\vfill
\end{slide*}

% vue 14

\begin{slide*}

{\`A} cet automate nous associons donc le jeu de tuiles $T_{1/2}'$ 
ci-dessous.

\begin{center}
\wangtile{$0'$}{$0'$}0{$0'$} 
\wangtile{$0'$}21{$0'$} 
\wangtile{$0'$}10{$\frac{1}{2}$} 
\wangtile{$0'$}1{$0'$}{$\frac{1}{2}$} 

\wangtile{$\frac{1}{2}$}{$0'$}0{$\frac{1}{2}$} 
\wangtile{$\frac{1}{2}$}21{$\frac{1}{2}$} 
\wangtile{$\frac{1}{2}$}11{$0'$} 
\end{center}

Ce jeu ne permet pas non plus de paver le plan entier: les tuiles avec un 
2 sur la rang{\'e}e sup{\'e}rieure et celles avec un 0 sur la rang{\'e}e inf{\'e}rieure 
ne peuvent {\^e}tre utilis{\'e}es; les deux tuiles restantes ne peuvent alors 
suffire.

Remarquons au passage que l'on peut paver trois rang{\'e}es 
horizontales cons{\'e}cutives avec ce jeu; mais, ensuite, on est bloqu{\'e}!

Notons $M$ l'automate obtenu en r{\'e}unissant $M_3$ et $M_{1/2}'$, 
et $T = T_3 \cup T_{1/2}'$.

\vfill
\end{slide*}

% vue 15

\begin{slide*}

\titre{Des pavages ap{\'e}riodiques, enfin!}

Th{\'e}or{\`e}me: $T$ permet de r{\'e}aliser une infinit{\'e} non d{\'e}nombrable de pavages 
ap{\'e}riodiques du plan.

Preuve: fixons $\alpha\in\bigl[\frac{1}{3},2\bigr]$. L'automate $M$ permet de 
calculer $B(3\alpha)$ si $\alpha\in\bigl[\frac{1}{3},\frac{2}{3}\bigr]$, 
$B(\alpha/2)$ si $\alpha\in\bigl[\frac{2}{3},2\bigr]$. 
Inversement, il existe une entr{\'e}e $B(\alpha/3)$ si 
$\alpha\in[1,2]$ ou $B(2\alpha)$ si $\alpha\in\bigl[\frac{1}{2},1\bigr]$ 
{\`a} laquelle cet automate associe $B(\alpha)$.

Traduisons ceci en termes de pavages: {\`a} chaque 
$\alpha\in\bigl[\frac{1}{3},2\bigr]$ on peut associer un pavage du plan. 
Si $\alpha$ et $\beta$ ne sont pas commensurables, leurs repr{\'e}sentations 
{\'e}quilibr{\'e}es ne peuvent appara{\^\i}tre dans un m{\^e}me pavage.

\vfill
\end{slide*}

% vue 16

\begin{slide*}

\titre{Ap{\'e}riodicit{\'e} de $T$}

Th{\'e}or{\`e}me: le jeu de tuiles $T$ est ap{\'e}riodique.

Preuve: par l'absurde. 

Soit $f$ un pavage (doublement) p{\'e}riodique r{\'e}alis{\'e} avec $T$, 
de p{\'e}riodes horizontale $a$ et verticale $b$. 
Chaque rang{\'e}e est r{\'e}alis{\'e}e avec des tuiles de l'un des jeux $T_3$ ou 
$T_{1/2}'$ (gr{\^a}ce {\`a} l'introduction de la lettre $0'$). 

Comme aucun de ces jeux ne permet {\`a} lui tout seul de paver le plan, 
chacun d'eux sert au moins une fois. 

Pour fixer les id{\'e}es, supposons la rang{\'e}e 0 form{\'e}e avec le jeu $T_3$.

\vfill
\end{slide*}

% vue 17

\begin{slide*}

Notons $n_i$ la somme des marques des ar{\^e}tes sup{\'e}rieures des tuiles 
$f(i,j)$ pour $1≤j≤b$; le report entrant par l'ar{\^e}te gauche de 
la tuile $f(i,1)$ {\'e}tant {\'e}gal au report sortant par l'ar{\^e}te droite 
de la tuile $f(i,b)$ on a $n_{i-1} = q_i n_i$ o{\`u} $q_i$ vaut 3 ou 
$\frac{1}{2}$ selon que c'est le jeu $T_3$ ou le jeu $T_{1/2}'$ qui 
est utilis{\'e} pour paver la rang{\'e}e $i$.

La p{\'e}riodicit{\'e} impose alors 
$$
 n_b = n_0 = q_1 q_2 \ldots q_b n_b 
$$

comme la rang{\'e}e 0 est pav{\'e}e avec le jeu $T_3$, on a $n_0 \ne 0$ 
donc $q_1 q_2 \ldots q_b = 1$ mais ceci est contradictoire.

\vfill
\end{slide*}

% vue 18

\begin{slide*}

\titre{Conclusion}


Le jeu ap{\'e}riodique que l'on a construit comporte treize tuiles. 
On peut remplacer les marques plac{\'e}es sur les c{\^o}t{\'e}s par des couleurs; 
en notant que les couleurs utilis{\'e}es sur les c{\^o}t{\'e}s horizontaux 
peuvent fort bien {\^e}tre reprises pour les c{\^o}t{\'e}s verticaux, on constate 
que \emph{cinq} couleurs suffisent (alors que, dans la construction, 
sept marques diff{\'e}rentes ont {\'e}t{\'e} utilis{\'e}es).

Il semble que ce jeu ap{\'e}riodique soit le plus petit connu, {\`a} ce jour.

\vfill
\end{slide*}

% vue 19

\begin{slide*}

\titre{Compl{\'e}ment personnel}

Notons $\varphi$ l'application qui, {\`a} 
$\alpha\in\bigl[\frac{1}{3},\frac{2}{3}\bigr[$ associe $3\alpha$ 
et {\`a} $\alpha\in[1,2\mathclose[$ associe $\frac{\alpha}{2}$. 
Notons $g:\alpha\in\bigl[ \frac{1}{3},2 \bigr[ 
 \mapsto \frac{\ln \alpha+\ln 3}{\ln 6}$; $g$ r{\'e}alise une bijection 
de $\bigl[\frac{1}{3},2\bigr[$ sur $[0,1\mathclose[$. 

Consid{\'e}rons alors $g \circ \varphi \circ g^{-1}$; 
notant $s=\frac{\ln 3}{\ln 6}$ on a 
$g(x)=x+1-s$ si $0≤x<s$ et $g(x)=x-s$ si $s≤x<1$. 
$g$ est donc une \emph{rotation} de l'intervalle $[0,1\mathclose[$. 
Comme 2 et 3 sont multiplicativement ind{\'e}pendants, $s$ est irrationnel, 
et les orbites sous l'action de $g$ sont codables par 
des mots sturmiens (cf. Agreg 94).

L'apparition de mots sturmiens (biinfinis) ne doit pas surprendre, 
ceux-ci {\'e}tant les mots ap{\'e}riodiques de complexit{\'e} minimale.

\vfill
\end{slide*}

% vue 20

\begin{slide*}

\titre{R{\'e}f{\'e}rences}

\small
\textsc{Hao Wang}. Proving theorems by pattern recognition II. 
\emph{Bell System Tech. J.}, 40:1-41, 1961.

\textsc{Robert Berger}. The undecidability of the domino problem. 
\emph{Memoirs of the AMS}, 66:201-213, 1966.

\textsc{Jarkko Kari}. A small aperiodic set of Wang tiles. 
\emph{Discrete Mathematics}, 160:259-264, 1996.

\textsc{Karel  \v{C}ulik II}. An aperiodic set of 13 Wang tiles. 
\emph{Discrete Mathematics}, 160:245-251, 1996.

\textsc{Cyril Allauzen, Bruno Durand}. Pavages du plan: ind{\'e}cidabilit{\'e} 
et ap{\'e}riodicit{\'e}. 
\emph{Rapport de Recherche 95-28}, {\'E}cole Normale Sup{\'e}rieure de Lyon.

Merci {\`a} \textsc{Jean Berstel}, \textsc{Karel \v{C}ulik}, 
\textsc{Bruno Durand} et, 
\emph{last but not least}, \textsc{Yves Duval}.

\vfill
\end{slide*}

\end{document}

% vue 

\begin{slide*}

\titre{}

\titre{Encore une autre id{\'e}e}

On peut repr{\'e}senter ce syst{\`e}me dynamique par des 
\emph{trajectoires d'{\'e}changes d'intervalles}. Le public est invit{\'e} 
{\`a} contempler le dessin.

\vfill
\end{slide*}

