\input bruno

\titre{Pavages: quasi-p{\'e}riodicit{\'e}}

On fixe un ensemble $\cal T$ fini de tuiles.
\smallskip

Une \emph{configuration} est une application $c:\Z^2 \mapsto {\cal T}$. 
\smallskip

Un \emph{motif} carr{\'e} de c{\^o}t{\'e} $n$ est une application 
$m:\cro[1,n]\times\cro[1,n] \mapsto {\cal T}$. 
On note $\ell(m)=n$.
\smallskip

Le motif $m$ \emph{appara{\^\i}t} dans la configuration $c$ s'il existe 
$(i,j)\in\Z^2$ tel que $m$ soit la restriction de $c$ {\`a} 
$\cro[i,i+n-1]\times\cro[j,j+n-1]$; 
on dit aussi que $m$ est \emph{extrait} de $c$. 
On d{\'e}finit de fa{\c c}on analogue la notion de motif extrait d'un autre motif 
(plus grand).
\smallskip

On note ${\cal M}_n(c)$ 
l'ensemble des motifs carr{\'e}s de c{\^o}t{\'e} $n$ extraits de $c$, 
et $\displaystyle {\cal M}(c) = \bigcup_{n�1} {\cal M}_n(c)$.
\smallskip

Soit $d$ une autre configuration; on note $c \prec d$ si 
${\cal M}(c) \subset {\cal M}(d)$. La relation $\prec$ 
est un pr{\'e}ordre sur l'ensemble des configurations. 
\smallskip

Nous dirons que $c$ est \emph{quasi-p{\'e}riodique} si, quel que 
soit le motif $m\in{\cal M}(c)$, il existe $n_m�\ell(m)$ 
tel que $m$ appara{\^\i}t dans tout motif carr{\'e} de c{\^o}t{\'e} $n_m$ 
extrait de $c$.
\smallskip

Exemple: si $c$ est doublement p{\'e}riodique, de p{\'e}riodes $p$ et $q$, 
alors $c$ est quasi-p{\'e}riodique avec $n_m=\ell(m)+2\max(p,q)-2$.
\smallskip

Exemple: la configuration $c$ d{\'e}finie par $c(i,j):\delta_{i,0}\delta_{j,0}$ 
n'est pas quasi-p{\'e}riodique.
\smallskip

Soient $m$ un motif et $c$ une configuration; consid{\'e}rons 
l'ensemble des $n�1$ tels que $m$ appara{\^\i}t dans tout motif carr{\'e} 
de c{\^o}t{\'e} $n$ extrait de $c$. 
Le \emph{rang} de $m$ vis-{\`a}-vis de cette configuration, not{\'e} $\rho_c(m)$, 
est le plus petit {\'e}l{\'e}ment de cet ensemble s'il n'est pas vide, 
$+�$ sinon. Notons que $\rho_c(m)�\ell(m)$.
\smallskip

Un motif $m$ apparaissant dans une configuration $c$ est \emph{r{\'e}gulier} 
pour cette configuration si $\rho_c(m)<+�$; sinon, il est dit 
\emph{critique}.
\smallskip

Remarque: $c$ est quasi-p{\'e}riodique ssi tous les motifs extraits de $c$ 
sont r{\'e}guliers pour $c$.
\smallskip

Lemme 1: si $m$ est critique pour $c$, il existe $d \prec c$ tel que 
$m \notin {\cal M}(c)$.
\smallskip

Preuve: notons $n=\ell(m)$. 
Il existe un motif $m_0 \in {\cal M}_n(c)$ distinct de $m$, 
et ayant une infinit{\'e} d'occurrences dans $c$. Il existe alors un motif 
$m_1 \in {\cal M}_{n+2}(c)$ ayant une infinit{\'e} d'occurrences dans $c$, 
au centre duquel appara{\^\i}t $m_0$, et dans lequel n'appara{\^\i}t pas $m$. 
On peut poursuivre ind{\'e}finiment cette construction: 
supposons obtenu un motif $m_k \in {\cal M}_{n+2k}$, ayant une infinit{\'e} 
d'occurrences dans $c$; il existe un motif $m_{k+1} \in {\cal M}_{n+2(k+1)}$, 
ayant une infinit{\'e} d'occurrences dans $c$, 
au centre duquel appara{\^\i}t $m_k$, et dans lequel n'appara{\^\i}t pas $m$. 
Superposons ces motifs, leur centre commun {\'e}tant en $(0,0)$: on 
obtient une configuration $d$ extraite de $c$, et ne contenant pas 
le motif $m$.
\smallskip

Th{\'e}or{\`e}me: $c$ est quasi-p{\'e}riodique ssi $c$ est minimal vis-{\`a}-vis de 
$\prec$.
\smallskip

Preuve du sens direct: soit $d \prec c$. Tout motif $m \in {\cal M}(c)$ 
appara{\^\i}t dans tout carr{\'e} de c{\^o}t{\'e} $\rho_c(m)$ extrait de $c$, et {\`a} plus forte 
raison dans tout carr{\'e} de c{\^o}t{\'e} $\rho_c(m)$ extrait de $d$, 
donc $m \in {\cal M}(d)$, si bien que $c \prec d$.
\smallskip

Preuve de la r{\'e}ciproque: supposons $c$ non quasi-p{\'e}riodique. 
Soit $m$ un motif critique de $c$; d'apr{\`e}s le lemme 1, 
il existe une configuration $d$ extraite de $c$ mais dans laquelle 
$m$ n'appara{\^\i}t pas. $d$ minore \emph{strictement} $c$ pour 
la relation $\prec$, si bien que $c$ n'est pas minimal 
pour cette relation.
\smallskip

Lemme 2: si $m$ est critique pour $c$, et si $c \prec d$, 
alors $m$ est critique pour $d$.
\smallskip

Preuve: pour tout $n$, $m$ est absent d'au moins un motif de c{\^o}t{\'e} 
$n$ extrait de $c$, donc de $d$.
\smallskip

Th{\'e}or{\`e}me: si le jeu de tuiles $\cal T$ permet de paver le plan, 
alors il permet de le paver de fa{\c c}on quasi-p{\'e}riodique.
\smallskip

Preuve: soit $c$ un pavage r{\'e}alis{\'e} avec $\cal T$. Si $c$ ne poss{\`e}de 
qu'un nombre fini de motifs critiques, on peut les {\'e}liminer l'un 
apr{\`e}s l'autre avec le lemme 1, pour obtenir un pavage quasi-p{\'e}riodique.
\smallskip

Sinon, comme l'ensemble des motifs est d{\'e}nombrable, on peut, toujours avec 
le lemme 1, construire une suite $(c_k)_{k\in\N}$ de pavages 
tels que $c_{k+1} \prec c_k \prec c$. Soit $m_k \in {\cal M}_k(c_k)$: 
le proc{\'e}d{\'e} d'extraction diagonale utilis{\'e} pour la preuve du lemme 1 
peut {\^e}tre utilis{\'e} {\`a} nouveau ici, pour obtenir un pavage $\gamma$ 
extrait de $c$, et ne contenant aucun motif critique.
\smallskip

Remarque: cette preuve n'est pas constructive.
\smallskip

D{\'e}finition: la \emph{fonction de quasi-p{\'e}riodicit{\'e}} d'une configuration 
$c$ quasi-p{\'e}riodique est l'application $f_c$ qui, {\`a} $n\in\N$, associe 
$f_c(n) = \min \{ \rho_c(m) \mid m \in {\cal M}_n(c) \}$. 
$f_c(n)$ est donc le plus petit naturel $N$ tel que, dans tout motif 
carr{\'e} de c{\^o}t{\'e} $N$, tous les motifs de c{\^o}t{\'e} $n$ apparaissent au moins 
une fois.
\smallskip

Th{\'e}or{\`e}me: $f$ est strictement croissante.
\smallskip

Preuve: que $f$ soit croissante est claire. Pour la croissance 
stricte, observer la figure ci-dessous.
\smallskip

% Macros pomp{\'e}es dans TeX in practice

\catcode`\@=11

\def\ZeroBox#1{\wd#1=0pt \ht#1=0pt \dp#1=0pt}
\def\ZeroBoxOut#1{\ZeroBox{#1}\box#1}

\newdimen\ScaleLength
\def\SetScale#1{\ScaleLength=#1}
\SetScale{3pt}

\newdimen\LineThickness
\def\SetLineThickness#1{\LineThickness=#1}
\SetLineThickness{1pt}

\newbox\GraphDataBox
\def\SetGraphDataBox#1{\dimen0=#1
\setbox\GraphDataBox=%
 \hbox{\hskip -0.5 \dimen0
 \vrule height 0.5 \dimen0
        depth  0.5 \dimen0
        width  1.0 \dimen0}%
 \ZeroBox\GraphDataBox}%
\SetGraphDataBox{3pt}

\def\DrawDataBox(#1,#2){\setbox0=\hbox{%
 \hskip #1\ScaleLength
 \raise #2\ScaleLength \copy\GraphDataBox}%
 \ZeroBoxOut{0}%
}

\def\hline(#1,#2)#3{\setbox0=\hbox{%
 \hskip #1\ScaleLength 
 \raise #2\ScaleLength \hbox{%
  \vrule height 0.5 \LineThickness
         depth 0.5 \LineThickness
         width #3\ScaleLength}}%
 \ZeroBoxOut{0}%
}

\def\vline(#1,#2)#3{\setbox0=\hbox{%
 \hskip #1\ScaleLength 
 \hskip -0.5 \LineThickness
 \raise #2\ScaleLength \hbox{%
  \vrule height #3\ScaleLength
         depth 0pt width \LineThickness}}%
 \ZeroBoxOut{0}%
}

\def\PutData(#1,#2)#3{%
 \setbox\GraphDataBox=\hbox{#3}%
 \ZeroBox\GraphDataBox
 \DrawDataBox(#1,#2)%
}
\catcode`\@=12

\leavevmode\vskip 50\ScaleLength
\leavevmode\hskip 0.3\hsize
\hline(0,0){40}
\vline(0,0){40}
\hline(0,40){15}
\hline(30,40){10}
\vline(40,0){40}
\hline(15,35){10}
\hline(15,45){10}
\vline(15,35){10}
\vline(25,35){10}
\SetLineThickness{0.4pt}
\vline(0,40){5}
\hline(0,45){15}
\hline(25,35){5}
\vline(30,35){15}
\vline(15,45){5}
\hline(15,50){15}
\hline(30,45){15}
\hline(40,0){5}
\vline(45,0){45}
\PutData(1,1){$m$}
\PutData(1,42){$m'$}
\PutData(16,36){$\mu$}
\PutData(16,47){$\mu'$}
\PutData(0,-1){$\underbrace{\kern 45\ScaleLength}_{\textstyle f_c(n)}$}
\PutData(15,34){$\underbrace{\kern 10\ScaleLength}_{\textstyle n}$}
\bigskip\bigskip

$m$ est un motif carr{\'e} de c{\^o}t{\'e} $\ell(m)=f_c(n)-1$, et dans lequel 
n'apparaissent pas tous les motifs carr{\'e}s de c{\^o}t{\'e} $n$. 
$m'$ est le motif carr{\'e} de c{\^o}t{\'e} $\ell(m')=\ell(m)+1=f_c(n)$ obtenu en "bordant" 
$m$ par une rang{\'e}e au-dessus et une colonne {\`a} droite. 
$\mu$ est un motif carr{\'e} de c{\^o}t{\'e} $\ell(\mu)=n$ qui n'appara{\^\i}t pas dans $m$; 
comme il appara{\^\i}t n{\'e}cessairement dans $m'$, il est cal{\'e} contre le bord 
haut ou le bord droit de celui-ci. 
Soit alors $\mu'$ le motif carr{\'e} de c{\^o}t{\'e}  $\ell(\mu')=\ell(mu)+1$ 
obtenu en bordant $\mu$ comme il a {\'e}t{\'e} fait pour $m$. 
$\mu'$ n'appara{\^\i}t pas dans $m'$ (sinon, $\mu$ appara{\^\i}trait dans $m$) 
donc $f_c(n+1)>f_c(n)$.
\smallskip

D{\'e}finition: la \emph{fonction de complexit{\'e}} de la configuration 
$c$ est l'application $g_c$ qui, {\`a} $n\in\N$, associe le cardinal 
de ${\cal M}_n(c)$. Il est clair que $g_c$ est croissante.
\smallskip

Th{\'e}or{\`e}me: soit $c$ une configuration quasi-p{\'e}riodique. Les 
assertions suivantes sont {\'e}quivalentes:
\smallskip

{\leftskip 20pt
\item� $c$ est p{\'e}riodique

\item� la suite de terme g{\'e}n{\'e}ral $f_c(n)-n$ stationne

\item� $g_c$ stationne

\item� il existe un indice $n_0$ tel que $g_c(n_0+1)=g_c(n_0)$
\par}
\smallskip

Preuve: $1 \Rightarrow 2$ et  $3  \Leftrightarrow 4$ sont clairs; 
$2 \Rightarrow 3$ se d{\'e}duit 
de la majoration $g_c(n)�\bigl(f_c(n)-n+1\bigr)^2$; 
pour $3 \Rightarrow 1$, il suffit de noter que, $n_0$ d{\'e}signant 
l'indice {\`a} partir duquel $g_c$ stationne, toute bande (horizontale 
ou verticale) de largeur $n_0$ est p{\'e}riodique.
\smallskip

Th{\'e}or{\`e}me: $c$ est quasi-p{\'e}riodique ssi $f_c(n)-n$ est born{\'e}.
\smallskip

\endsignal
