\documentclass[XUPS,XML,SOM,Unicode,francais,NoFloatCountersInSection]{cedram}
\setcounter{tocdepth}{2}
%\XUPScorrections
\usepackage{graphicx}
\graphicspath{{xups01-02_figures}}

\newtheorem{theorem}{Theorem}[part]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposit}[theorem]{Proposition}
\theoremstyle{remark}
\newtheorem*{Remarques*}{Remarques}

\let\<\langle
\let\>\rangle

\let\oldS\S
\def\S{\oldS\kern2pt}
\DeclareMathOperator{\carry}{\textit{carry}}

\begin{document}
\let\partname\chaptername
\frontmatter
\title{Pavages}
\author[\initial{F.} \lastname{Labourie}]{\firstname{François} \lastname{Labourie}}
\address{Laboratoire de Mathématiques,
UMR 8628 du CNRS, Bât 425, Université Paris-Sud,
91405 Orsay, France}
\email{francois.labourie@univ-cotedazur.fr}
\urladdr{https://flab.perso.math.cnrs.fr/}

\thanks{Journées X-UPS 2001. Pavages. Éditions de l'École poly\-technique, 2001}

\maketitle
\enlargethispage{\baselineskip}
\noindent
\begin{minipage}{\textwidth}
\tableofcontents
\end{minipage}

\mainmatter
\begin{figure}[htb]
\centerline{\includegraphics[scale=.5]{triangloz}}
\caption{Pavage par des losanges}
\label{fig:pavloz}
\end{figure}

\part{Pavages, problèmes de pavage}

\section{Une définition}
Ce que l'on regroupe sous la dénomination \og pavages\fg,
recouvre un champ de recherches
géométriques très actif dont le principal
intérêt est de se trouver au confluent de nombreux
domaines mathématiques: théorie des groupes
discrets, théorie des nombres, probabilités,
algorithmique, systèmes dynamiques, analyse. Le terme
pavage lui-même désigne plus une problématique, une
source d'exemples et de constructions, qu'une notion
mathématique bien définie, comme celle de groupe ou
de corps dont la définition axiomatique est cruciale.

Nous allons commencer par donner la définition d'un
{\it problème de pavage}, tout en gardant à l'esprit
que celle-ci n'est là que pour les commodités de
l'exposé. Elle ne sera donc ni précise, ni optimale; elle s'accordera sans doute avec l'idée que s'en font
la plupart des mathématiciens travaillant dans le sujet,
même si chacun sera amené à produire une
définition plus précise, voire totalement
différente.

Un problème de pavage est la donnée suivante:\enlargethispage{\baselineskip}
\begin{itemize}
\item Un {\it espace} $X$, et une région $Y\subset X$ de
$X$. Cet espace $X$ a le plus souvent des structures
supplémentaires qui le rendent raisonnable:
topologie, distance, structure affine, mesure. Parmi les
espaces les plus utilisés signalons les plans
euclidien ou hyperbolique.
\item Un {\it groupe de symétries} $G$. Il s'agit d'un
sous-groupe des transformations de $X$, qui préserve
la structure si $X$ en a une. On note $g\cdot U$, l'image par
l'élément $g$ de $G$ du sous-ensemble $U$ de $X$.
\item Un ensemble (la plupart du temps fini) de {\it tuiles}
$\{T_{i}\}_{i\in I}$. Chacune de ces tuiles $T_{i}$ est un
sous-ensemble de $X$. Elle est (en général) la
réunion disjointe d'un {\it intérieur},
$\breve{T_{i}}$, et d'un bord, $\partial T_{i}$. Bien
sûr lorsque $X$ est un espace topologique, il s'agira
de l'intérieur et du bord topologique. Un exemple
à garder en tête dès maintenant est celui de
$X=\mathbb{R}^{2}$ et d'un ensemble fini de tuiles
polygonales.
\end{itemize}

Le {\it problème de pavage} que nous cherchons à
résoudre est le suivant: $Y$
peut-il être pavé par les tuiles $T_{i}$ avec groupe de
symétries $G$. Autrement dit, peut-on décrire $Y$
comme la réunion d'images par~$G$ des tuiles $T_{i}$ de
telle sorte que les intérieurs soient disjoints. Plus
précisément encore, peut-on écrire
\begin{eqnarray*}
Y=\bigcup_{g\in A}g\cdot T_{i(g)},
\end{eqnarray*}
où $A$ est un sous-ensemble de $G$, et tel que de plus,
pour deux éléments~$g$ et~$h$ de $A$
\begin{eqnarray*}
g\not=h\implies g\cdot \breve{T}_{i(g)}\cap h\cdot \breve{T}_{i(h)}=\emptyset.
\end{eqnarray*}

On imposera en général des règles ou contraintes
supplémentaires. Voici quelques exemples
particulièrement importants de contraintes:
\begin{itemize}
\item {\it Pavages périodiques}. Dans cette situation, $Y=X$, on se
contente d'une seule tuile et on exige que $A$ soit un sous-groupe de $G$, alors appelé {\it
groupe de paveur}; dans cette situation, la \og forme\fg
de la tuile n'a pas beaucoup d'importance et la
\og théorie\fg des pavages s'identifie à celle des
groupes discrets, comme nous le verrons plus tard.
\item {\it Règles locales.} On impose assez souvent des
règles de constructions locales. Par exemple, si on a quatre tuiles
$\{T_{i}\}_i\in\{1,\ldots,4\}$, on peut
exiger que les images de $T_{1}$
rencontrent toujours une image de $T_{2}$ mais jamais une
image de $T_{4}$, {\it etc}.
\item{\it Pavages autosimilaires ou fractals}. Nous en
donnerons une définition formelle plus tard; pour le
moment, signalons qu'il s'agit de pavages de l'espace
euclidien, présentant une répétition par
changement d'échelle.
\end{itemize}

\Subsection{Premiers exemples}
\subsubsection*{Pavage carré} C'est le carrelage des salles de bains,
très certainement le plus antique. Ici $Y=X={\mathbb
R}^{2}$ est le plan euclidien, on considère une seule
tuile $T=[0,1]\times [0,1]$ et $G$ est le groupe des
isométries du plan euclidien. Il s'agit d'un des plus
simples exemples de pavages périodiques; ici $A={\mathbb
Z}^2$ est le groupe des translations de vecteurs
entiers.\enlargethispage{1.5\baselineskip}

\subsubsection*{Pavage triangulaire}
Un autre très simple exemple est celui du plan euclidien
pavé périodiquement par des triangles
équilatéraux. On prend comme tuile $T$ le
triangle équilatéral de sommets $(0,0)$, $(1,0)$,
$(\sfrac{1}{2},\sfrac{\sqrt{3}}{2})$. Le groupe de paveur est
alors le groupe engendré par la rotation d'angle
$\sfrac{\pi}{3}$ de centre $(0,0)$ et la translation de
vecteur $(0,1)$.

\subsubsection*{Problème A: pavage par des losanges}

Le pavage triangulaire va nous permettre d'introduire un
problème (que nous appellerons {\it problème~A} par
la suite) dont l'énoncé est élémentaire,
mais la solution moins. On considère tout
d'abord le plan euclidien pavé par des triangles
équilatéraux comme précédemment. On remarque que
la tuile de base $T$ a trois voisins avec laquelle elle
partage une arête, $T_{1}$, $T_{2}$ et $T_{3}$. Cette
observation nous permet de définir trois losanges
$L_{i}=T\cup T_{i}$. Ces trois losanges sont les tuiles de
notre problème de pavage. Le groupe $G$ est toujours le
groupe des isométries de $\mathbb{R}^2$. \hbox{Enfin}, on
prend pour $Y$ un polygone borné, connexe, de
bord connexe et formé de la réunions de tels
triangles. Par définition, $Y$ est bien
sûr pavé par des triangles, la question est

{\it La région $Y$ peut-elle être pavée par les
losanges $L_{1}$, $L_{2}$, $L_{3}$ avec \og groupe\fg de
symétries $G$ (figure \ref{fig:pavloz})?}.

La réponse dépend bien entendu de la région $Y$.
Nous allons par la suite décrire une \og obstruction\fg au
pavage par des losanges, c'est-à-dire un invariant
facilement calculable permettant d'affirmer qu'un région
ne peut pas être pavé par des losanges. Cette
obstruction va nous amener à parler plus longuement des
groupes de type fini et des pavages périodiques.

\subsubsection*{Problème B: un jeu de morpion}
La méthode que nous expliquerons pour résoudre le problème
$A$ est générale. Elle permet de s'attaquer à de
nombreux problèmes du même type et de résoudre
le problème suivant ({\it problème B}), qui n'est pas
à première vue un problème de pavage.

\begin{figure}[htbp]
\centerline{\includegraphics[width=50mm]{trianpoint}}
\caption{Un jeu de morpion sur un triangle}
\label{fig:morpion}
\end{figure}

On se donne un {\sl triangle de points} construit de la
manière suivante: soit $X_{n}$ le triangle
équilatéral de sommet $(0,0)$, $(n,0)$,
$(\sfrac{n}{2},\sfrac{n\sqrt{3}}{2})$; ce triangle est lui
même la réunion de petits triangles
équilatéraux du pavage triangulaire. On prend pour
triangle de points $T_{n}$ les sommets de ces petits
triangles. La question est la suivante:

{\it Peut-on jouer au morpion sur $T_{n}$? c'est-à-dire
barrer tous les points de $T_{n}$, trois par trois, par
des segments parallèles aux côtés de $X_{n}$,
de telle sorte que chaque point de $T_{n}$ se trouve sur
un segment et un seul (figure \ref{fig:morpion})?}

\subsection{Plan de cette note et premières références}

Nous allons tout d'abord parler longuement des groupes de
présentation finie et de leur lien avec les pavages
périodiques. Nous expliquerons comment associer à
chaque groupe de ce type un espace géométrique, son {\it
graphe de Cayley}. Nous verrons tout
groupe de présentation finie comme le groupe de paveur de
son graphe de Cayley.

Nous utiliserons ces notions pour aborder le problème A
et donner une méthode générale pour aborder ce
type de question, méthode due à Conway \cite{Conway}
et vulgarisée par Thurston \cite{Thurston1}. Nous
esquisserons le début d'une solution pour le
problème B.

Ces trois paragraphes sont solidaires. Dans le suivant, de
taille sensiblement, plus importante, nous étudierons
les pavages autosimilaires. En utilisant des rudiments de
théorie des nombres, nous construirons de tels pavages,
nous montrerons de plus le lien qu'ils entretiennent avec
les systèmes dynamiques et les automates à nombre
fini d'états.

Enfin dans un appendice appelé {\sl galerie}, Jean-René
Geoffroy présente un programme Xmaple permettant d'obtenir
des pavages autosimilaires et quelques images qu'il
obtient ainsi.\enlargethispage{\baselineskip}

\subsubsection*{Premières références} Presque tout ce qui suit est tiré
d'une merveilleuse prépublication de William Thurston
\cite{Thurston2}, plus tard partiellement publiée dans
\cite{Thurston1}. Par ailleurs, le programme sous {\it
XMaple} permettant d'obtenir des pavages autosimilaires
a été écrit par Jean-René Geoffroy,
actuellement doctorant à l'Université Paris-Sud,
lors d'un stage de Magistère sous ma direction.
Jean-René a également produit les figures liées
les pavages autosimilaires. Nous donnerons d'autres
références plus tard, mais signalons le site du {\it
Geometry Center}

{\par\noindent\smaller
\url{http://www.geom.uiuc.edu/}}

\noindent En y butinant, vous y trouverez quelques programmes et
appliquettes Java autour des pavages (en anglais: tilings).
En particulier, la page
{\par\noindent\smaller
\url{http://www.geom.uiuc.edu/graphics/pix/Special_Topics/Tilings/}}

\noindent contient des images de pavages\footnote{N.d.E: \emph{l'auteur ajoute les pages ci-dessous qui ne sont plus actives}. Voici une autre référence plus didactique:
{\par\noindent\smaller
\url{http://www.math.okstate.edu/mathdept/dynamics/lecnotes/}}
\par\noindent
Les adresses suivantes fournissent des exemples de pavages
autosimilaires:
{\par\noindent\smaller
\url{http://www.inma.ucl.ac.be/~canterini/}}
{\par\noindent\smaller
\url{http://iml.univ-mrs.fr:80/~siegel/}}
{\par\noindent\smaller
\url{http://iml.univ-mrs.fr/presentation/gal/imldac/structures/berthe.html}}.}.

\section{Pavages périodiques}

Nous avons donné plus haut la définition d'un pavage
périodique de groupe de paveur $A$. Dans les exemples
que nous avons donnés, les groupes de paveurs sont des
groupes ayant un nombre fini de générateurs, c'est
en fait le cas de manière plus générale sous des
hypothèses tout à fait raisonnables sur l'espace
pavé et la tuile fondamentale. De~manière plus
précise, le groupe de paveurs est de {\it
présentation finie}. Nous expliquerons cette notion
dans le prochain paragraphe. Nous montrerons que
réciproquement tout groupe de présentation \hbox{finie} est
le groupe de paveurs d'un espace $X$ défini par la
présentation; certains des objets géométriques
liés à $X$ permettent d'appréhender $A$
géométriquement. Enfin en conclusion, nous donnerons
quelques compléments de nature historique sur ces
différents sujets.

\subsection{Groupe libre, groupe de présentation finie}

Un groupe est de {\it génération finie} s'il
possède un nombre fini de générateurs. Le prototype de tels groupes est le {\it groupe libre à
$n$-générateurs} $F_{n}$. Nous allons passer un
peu de temps à rappeler la définition de ce groupe.
\subsubsection*{Groupe libre}
On se donne tout d'abord $n$ {\it lettres} $s_{i}$, $i\in
\{1,\ldots, n\}$. Un {\it mot} est une expression formelle
du type suivant
\begin{eqnarray}\label{1}
s_{i_{1}}^{p_{1}} s_{i_{2}}^{p_{2}}\ldots s_{i_{k}}^{p_{k}},
\end{eqnarray}
où les $p_{i}$ sont des entiers relatifs. On a une
opération naturelle qui a deux mots associe leur {\it
concaténé}
$$
C: (s_{i_{1}}^{p_{1}} s_{i_{2}}^{p_{2}}\ldots
s_{i_{k}}^{p_{k}},b_{i_{1}}^{p_{1}} b_{i_{2}}^{p_{2}}\ldots
b_{i_{l}}^{p_{l}})\longmapsto s_{i_{1}}^{p_{1}}
s_{i_{2}}^{p_{2}}\ldots s_{i_{k}}^{p_{k}}b_{i_{1}}^{p_{1}}
b_{i_{2}}^{p_{2}}\ldots b_{i_{l}}^{p_{l}}
$$
On note le concaténé de deux mots $m_{0}$ et
$m_{1}$ sous la forme $m_{0}\circ m_{1}$. Il est alors clair
que l'opération concaténation est associative. Pour
le moment cependant, ce n'est pas une loi de groupe.

Un {\it mot réduit} est un mot, où dans l'expression
(\ref{1}), on suppose de plus que $i_{j}\not=i_{j+1}$ et
$p_{i}\not=0$. Par convention, le mot {\it vide}, sans
aucune lettre, est noté 1 et est considéré comme
un mot réduit. Il est clair qu'il existe une application
$R$ associant à tout mot un mot réduit en utilisant
récursivement la règle de réduction suivante.
Si $m=b\circ a^p\circ a^q\circ c$, alors on remplace $m$ par
$b\circ a^{p+q}\circ c$ si $p+q\not=0$, et par $b\circ c$ si
$p+q=0$, puis on itère. Au bout d'un nombre fini
d'étapes, on arrivera à un mot réduit.

Le {\it groupe libre} sur les lettres $s_{i}$, $i\in
\{1,\ldots, n\}$ est alors le groupe dont les
éléments sont les mots réduits et dont la loi de
groupe est la~loi
$$
m_{0}\cdot m_{1}=R(m_{0} \circ m_{1}).
$$

Il est facile de vérifier que l'on a bien une structure
de groupe dont l'élément neutre est le mot vide.
Le groupe ainsi construit s'appelle le {\it groupe libre
$F_{n}$ à $n$ générateurs $s_{i}$, $i\in
\{1,\ldots, n\}$}. On le note aussi $F(S)$, pour
$S=\{s_{1},\ldots,s_{n}\}$. Ce
groupe est {\it universel} dans le sens suivant: si $b_{1},
\ldots, b_{n}$ sont $n$ éléments d'un groupe $G$,
alors il existe un unique morphisme $f$ du groupe $F(S)$
vers $G$ tel que $f(s_{i})=b_{i}$. En particulier, tout
groupe $G$ ayant $S$ comme ensemble de générateurs
s'identifie à un quotient de $F(S)$: avec les notations
précédentes, $G$~est isomorphe à $F(S)/\ker(f)$.
\subsubsection*{Groupe de présentation finie}
Nous allons maintenant pouvoir définir ce qu'est un
groupe de présentation finie, engendré par
l'ensemble des générateurs
$S=\{s_{1},\ldots,s_{n}\}$, et l'ensemble des {\it
relations} $R=\{R_{1},\ldots,R_{k}\}$, où les $R_{k}$
sont des éléments du groupe libre $F(S)$. Un tel
groupe se note symboliquement\vspace*{-3pt}
$$
G=\<S\mid R\>=\<s_{1},\ldots,s_{n}\mid
R_{1}=\cdots=R_{k}=1\>.
$$
Par définition $G=F(S)/N(R)$, où $N(R)$ est
l'intersection de tous les sous-groupes distingués
contenant tous les $R_{i}$. Cela signifie que deux
éléments $m_{0}$ et $m_{1}$ de $F(S)$ représente le
même élément dans $G$, si on peut écrire\vspace*{-3pt}
\Changel
$$
m_{0}=g_{1}\cdot R_{k_{1}}\cdot g_{1}^{-1}\cdots g_{l}\cdot R_{k_{l}}\cdot g_{l}^{-1}\cdot m_{1}.
$$

\Changelback

Cette apparente simplicité est en fait redoutable: il
est ainsi par exemple très difficile à partir
simplement des générateurs et des relations de
savoir si un groupe est fini ou non.

\subsubsection*{Exemples}
Donnons quelques exemples très simples. Dans ces
exem\-ples, $\mathcal{S}_{n}$ désigne le groupe des
permutations de $\{1,\ldots,n\}$.\vspace*{-3pt}
\begin{eqnarray*}
\<a\mid a^{2}=1\>&=&\mathbb{Z}/2\mathbb{Z},\\
\<a,b\mid aba^{-1}b^{-1}=1\>&=&\mathbb{Z}^{2},\\
\<a,b,c \mid aba^{-1}b^{-1}=aca^{-1}c^{-1}=cbc^{-1}b^{-1}=1\>&=&\mathbb{Z}^{3},\\
\<a,b,c \mid c^{-1}ab=aba^{-1}b^{-1}=1\>&=&\mathbb{Z}^{2}.\\
\<a,b \mid a^{2}=b^{2}=(ab)^3 =1\>&=&\mathcal{S}_{3}.\\
\<a,b,c \mid a^{2}=b^{2}=c^{2}=(ab)^3 =(bc)^{3}=(ac)^{3}=1\>&=&\mathcal{S}_{4}.
\end{eqnarray*}

\subsubsection*{Exercice} Vérifiez les égalités ci-dessus.

\subsection{Graphe de Cayley} Nous avons annoncé que sous des
hypothèses géométriquement raisonnables sur
l'espace $X$ et les tuiles, le groupe de paveur est de
génération finie. Admettons le. Nous allons montrer
maintenant que tout groupe $G$ de génération finie
et lui-même le groupe de paveurs de son {\it $2$-graphe de
Cayley}.

\subsubsection*{Graphe orienté étiqueté}
Un {\it graphe orienté} est constitué d'un ensemble
de sommets $V$, et d'un ensemble d'arêtes $A\subset
V\times V$. On pense le graphe comme un objet
géométrique et dans cette optique on voit chaque
couple $(v_{0},v_{1})$ d'éléments de $V$ comme une
flèche joignant $v_{0}$ à $v_{1}$. On peut aussi,
cela nous sera utile par la suite, ajouter des
étiquettes aux arêtes, on parle alors de {\it
graphes étiquetés}; Par convention, lorsque l'on
réalise graphiquement un graphe sur une figure, si on a
l'arête $(v_{0},v_{1})$ et l'arête $(v_{1},v_{0})$
au lieu de dessiner deux arêtes fléchées
joignant les sommets, on dessine simplement une seule
arête sans signe d'orientation. Par abus de langage, on
confond par la suite le graphe abstrait tel que nous venons
de le définir, et sa {\it réalisation
simpliciale}. Celle-ci est l'espace topologique obtenu, en \og collant\fg des
intervalles à chaque arête abstraite. Dans cette
réalisation simpliciale, mathématiquement un
{$1$-complexe}, les arêtes ont homéomorphes à des
intervalles.\enlargethispage{\baselineskip}

\subsubsection*{$1$-Graphe de Cayley}
Le {\it graphe de Cayley} (pour le moment le $1$-graphe)
d'un groupe $G$ engendré finiment par les
générateurs $(s_{1},\ldots,s_{n})$ est le graphe
orienté défini de la manière suivante:
\begin{itemize}
\item les sommets sont les éléments du groupe,
\item les arêtes étiquetées $s_{i}$ sont tous
les couples $(g,gs_{i})$.
\end{itemize}
Remarquons ainsi que de chaque sommet part (et arrive)
exactement $n$ arêtes, une exactement pour chaque
étiquette $s_{i}$. Bien sûr, le graphe de Cayley
dépend du choix des systèmes générateurs,
cependant sa {\it géométrie asymptotique} ne
dépend que du groupe. Enfin, il est facile de voir que
le groupe lui même agit sur son graphe de Cayley. Voici
un exemple de graphe de Cayley pour $\mathbb Z^{2}$,
différent du réseau usuel.
\begin{figure}[htbp]
\centerline{\includegraphics[width=80mm]{triang1}}
\caption{Graphe de Cayley de\\ \centerline{$\<a,b,c\mid
abc^{-1}=ca^{-1}b^{-1}=1\>$}} \label{fig:triang1}
\end{figure}
\par\noindent
Un graphe de Cayley n'est pas nécessairement planaire. Le graphe de Cayley~de\vspace*{-3pt}
$$
\<a,b,c \mid
aba^{-1}b^{-1}=aca^{-1}c^{-1}=cbc^{-1}b^{-1}=1\>={\mathbb
Z}^{3}
$$
n'est pas naturellement planaire, c'est le réseau
cubique dans $\mathbb R^{3}$.
\subsubsection*{Morphismes de groupe}\label{morphisme}
Si $G_{1}$ est un groupe engendré par $S$, si $f$ est
un morphisme de $G_{1}$ sur $G_{2}$, tel que $f(S)$ engendre
$G_{2}$, alors le morphisme se voit comme une application
géométrique envoyant arête sur arête du
graphe du premier sur le graphe du second.

Voici un exemple simple à partir de\vspace*{-3pt}\enlargethispage{\baselineskip}
\begin{eqnarray*}
\<a,b,c \mid aba^{-1}b^{-1}=aca^{-1}c^{-1}=cbc^{-1}b^{-1}=1\>&=&\mathbb{Z}^{3},\\
\<a,b,c \mid c^{-1}ab=aba^{-1}b^{-1}=1\>&=&\mathbb{Z}^{2}.
\end{eqnarray*}
Il existe dans cette application un morphisme de groupe
$f:\mathbb{Z}^{3}\rightarrow\mathbb{Z}^{2}$, tel que
$f(a)=a$, $f(b)=b$ et $f(c)=c$. Géométriquement,
cela correspond à la projection du graphe cubique sur le
graphe triangulaire du plan.
\subsubsection*{Mots et lacets}
Nous avons vu précédemment que le choix d'un
système $S$ de générateurs du groupe $G$ donne
naissance à un morphisme~$f$ du groupe libre
$F(S)$ vers $G$. Nous allons maintenant en donner la version
géométrique. L'observation fondamentale est la
suivante: chaque mot en les générateurs donne
naissance à un chemin dans le graphe de Cayley partant
de chaque sommet de ce graphe; en effet il faut concevoir
chaque mot comme une suite d'instructions. Ainsi le mot
$s_{1}s_{4}^{4}s_{2}^{-1}$ signifie: partant d'un sommet
quelconque $g$, on suit l'arête étiqueté $s_{1}$
(on arrive donc en $g\cdot s_{1}$), puis on suit $s_{4}$, quatre fois
de suite, puis on remonte (en sens inverse) les arêtes
étiquetées~$s_{2}$, deux fois de suite.

On remarque que dans cette interprétation les mots
réduits devien\-nent des {\it chemin réduits},
c'est-à-dire qui ne rebroussent jamais chemin.

Il est maintenant clair que les lacets (chemin fermé)
correspondent alors aux mots triviaux dans $G$,
c'est-à-dire aux éléments de $\ker(f)$. Par
exemple, dans $\<a,b,c\mid abc^{-1}=ca^{-1}b^{-1}=1\>$, les
mots
\begin{eqnarray*}
L_{1}&=&aba^{-1}b^{-1},\\
L_{2}&=&aca^{-1}c^{-1},\\
L_{3}&=&cbc^{-1}b^{-1},
\end{eqnarray*}
correspondent aux trois losanges de la figure
\ref{fig:3los}.
\begin{figure}[htbp]
\centerline{\includegraphics[width=40mm]{3los}}
\caption{Trois losanges} \label{fig:3los}
\end{figure}
Le lecteur attentif commencera à voir une certaine
similarité avec le problème A.
\subsubsection*{$2$-Graphe de Cayley}

Continuons sur la lancée de la précédente
observation. Supposons que $G$ est défini par
\begin{itemize}
\item
les générateurs $S=\{s_{1},\ldots,s_{p}\}$
\item
et les relations $R=\{R_{1},\ldots, R_{k}\}$.
\end{itemize}
Par définition,
tout mot $m$ trivial dans $G$, est un élément de
$N(R)$, c'est-à-dire un mot que l'on peut écrire
dans $F(S)$ sous la forme
$$
m=g_{1}\cdot R_{k_{1}}\cdot g_{1}^{-1}\cdots g_{l}\cdot R_{k_{l}}\cdot g_{l}^{-1}\cdot m_{1}.
$$
Interprétons cette relation géométriquement.
Elle signifie que tout lacet est composé de lacets
élémentaires. Un lacet élémentaire
constituant à suivre un chemin $g$, puis à suivre
l'instruction donné par une relation $R_{i}$, puis à
revenir par le même chemin $g$

Cette dernière observation va justifier l'introduction
du $2$-graphe de Cayley.

Nous allons introduire des {\it tuiles} étiquetées
par les relations $R_{i}$. Pour chaque relation
$R_{i}=s_{i_{1}}^{p_{1}}\cdots s_{i_{k}}^{p_{k}}$, on
considère le polygone régulier ayant $n=\sum \vert
p_{i} \vert$ côtés; de plus chaque arête est
orientée et étiquetée par l'un des $s_{i}$
suivant l'ordre du mot réduit $R_{i}$. Cela sera plus
facile à comprendre sur un exemple. Prenons notre groupe
habituel
$$
\<a,b,c \mid c^{-1}ab=aba^{-1}b^{-1}=1\>.
$$
Nous avons deux tuiles fondamentales, en forme de triangles.

Le $2$-graphe de Cayley $G_{2}$ est alors obtenu en
\og collant\fg au $1$\nobreakdash-gra\-phe de Cayley un exemplaire de chaque
tuile étiquetée à chaque sommet, le long du
chemin fermé défini par l'étiquette.

Naturellement, le groupe $G$ va agir sur cet espace
topologique, mathématiquement un $2$-complexe cellulaire.
Nous avons réalisé notre but.

{\it Les tuiles $R_{i}$, l'espace $X=G_{2}$ et le groupe $G$
formant un pavage périodique. Chaque groupe $G$ de
présentation finie est le groupe de paveurs d'un
espace topologique.}

Dans notre exemple favori
$$
\<a,b,c \mid c^{-1}ab=aba^{-1}b^{-1}=1\>,
$$
nous allons peindre l'une de ces tuiles en blanc, l'autre en
noir. Le $2$-graphe de Cayley est le plan euclidien pavé par
des triangles équilatéraux noirs et blancs; les
noirs ayant la pointe en haut, les blanc la pointe en bas
(figure \ref{fig:tuile1}).
\begin{figure}[htbp]
\centerline{\includegraphics[width=50mm]{triang2}}
\caption{Les deux tuiles triangulaires}
\label{fig:tuile1}
\end{figure}

\section{Une obstruction pour le problème A}
Il va être maintenant très facile de construire une
obstruction pour le problème $A$; plus
précisément, nous allons associer à chaque
région~$Y$ un invariant numérique dont la
nullité est imposée par la possibilité d'un pavage par
losanges.

Nous allons reformuler notre problème à l'aide de
notre groupe favori
$$
G=\<a,b,c \mid c^{-1}ab=aba^{-1}b^{-1}=1\>.
$$
Nous avons une courbe $\gamma_{Y}$ tracée dans le
$1$-graphe de Cayley, qui borde une région $Y$ dans le
$2$-graphe de Cayley. Rappelons que nous voulons savoir si
$Y$ est pavable par losanges.

Pour cela, rappelons que la courbe $\gamma_{Y}$ correspond
à un mot réduit (un élément du groupe libre
$F(a,b,c)$) qui devient trivial dans $G$. Les trois losanges
de base correspondent aux mots
$$
L_{1}=aba^{-1}b{-1},~ L_{2}=aca^{-1}c^{-1},~
L_{3}=cbc^{-1}b^{-1}.
$$

La remarque fondamentale est la suivante
\begin{proposit}\label{los}
{ Si $Y$ est pavable par losanges, alors il existe des
éléments $g_{i}$ de $F(a,b,c)$ tels que, $$
\gamma_{Y}=g_{1}L_{i_{1}}^{p_{1}}g_{1}^{-1}\cdots
g_{q}L_{i_{q}}^{p_{q}}g_{q}^{-1}. $$
Autrement dit,
$\gamma_{Y}\in N(L_{1},L_{2},L_{3})$ }
\end{proposit}
Nous pouvons énoncer cette dernière relation en
théorie des groupes. Au mot $\gamma_{Y}$, nous
associons l'élément $I(Y)$, du groupe
$$
H =\<a,b,c\mid
aba^{-1}b{-1}=aca^{-1}c^{-1}=cbc^{-1}b^{-1}=1\>.
$$
Notons $\pi$ la projection de $H=\mathbb Z^{3}$ dans
$G=\mathbb Z^{2}$, comme en \ref{morphisme}. Nous savons que
$I(Y)\in \ker(\pi)$. D'après la proposition \ref{los},
si $Y$ est pavable par losange alors $I(Y)=0$. Enfin,
$\ker(\pi)$ est isomorphe à $\mathbb Z$.

\smallskip
\centerline{\it L'entier $I(Y)$ est une
obstruction au problème} \centerline{\it du pavage de
la région bordée par $Y$:} \centerline{\it si
$I(Y)=0$, alors $Y$ ne peut-être pavée par des
losanges.}

\smallskip

Pour compléter notre programme, il faut donner une
procédure de calcul de $I(Y)$. Cela est facile, car
les groupes $G$ et $H$ sont abéliens. Nous pouvons donc
calculer $I(Y)$ de la manière suivante. Dans le mot~$\gamma_{Y}$ (vu comme élément de $H$) $a$, $b$ et
$c$ commutent. Nous pouvons donc écrire
$I(Y)=a^{p}b^{q}c^{r}$, ou $p$ est la somme des exposants de
$a$ dans le mot $\gamma_{Y}$ etc. Comme $c=ab$ dans $G$, il
est facile de voir que, dire que $\gamma_{Y}$ est nul dans
$G$, signifie $r=p=q$. En conclusion

\smallskip
\centerline {\it L'entier $I(Y)$ est la somme des exposants de $a$ dans le mot $\gamma_{Y}$.}

\begin{Remarques*}\mbox{}
\begin{itemize}
\item Voici un petit exercice: $I(Y)$ est la différence
du nombre de triangles noirs et blancs dans $Y$. Après
cet exercice, le lecteur aurait le bon droit d'être
furieux: il est évident dès le départ que
cette différence est une obstruction au problème
du pavage (pourquoi?). Mais bien sûr
la construction précédente
est plus générale et s'adaptera à d'autres cas.
\item La nullité de $I(Y)$ n'est pas suffisante pour
conclure à l'existence d'un pavage. Il est facile de
construire un contre-exemple, mais essayons d'expliquer cela
géométriquement. Nous avons vu que le graphe de
Cayley de $H$ est le réseau cubique. Dire que $I(Y)$
est nul signifie que le mot $\gamma_{Y}$ est un chemin
fermé dans le graphe de Cayley de $H$. Il~va alors border une région $A$ dans le
$2$-graphe de Cayley. Le~pavage par losanges est alors la
projection de cette région: en regardant la figure~\ref{fig:pavloz} en plissant les yeux, le pavage par
losanges apparaît en relief de telle sorte que les losanges
soient des faces de cube. Le~problème est le
suivant: la projection de $A$ peut très bien ne pas
être injective, autrement dit les losanges peuvent se
recouvrir. Pour éliminer ces recouvrements, il faut
travailler plus finement, toujours de manière
géométrique. Ceci est fait dans \cite{Thurston1}.
\end{itemize}
\end{Remarques*}

\section{Une indication pour le problème B}
Nous allons montrer comment transformer le jeu de morpion en
problème de pavage, et indiquer les étapes de sa
résolution. En fait, la réponse est
non: on ne peut jouer au morpion sur un triangle.

Nous considérons le pavage hexagonal en nid d'abeille,
de telle sorte que les points du triangle se trouvent au
centre des hexagones. Le triangle de points donne alors une
région $Y_{n}$ bornée par une courbe~$\gamma_{Y_{n}}$. Les trois segments possible utilisés
pour barrer les points, correspondent à trois {\it
triominos}, $T_{1}$, $T_{2}$, $T_{3}$, chacun obtenu en
réunissant trois hexagones. La question est donc:

\centerline{\it peut-on paver $Y_{n}$ par des triominos
(figure \ref{fig:hexa})?}
\begin{figure}[htbp]
\centerline{\includegraphics[scale=.3]{hexag}}
\caption{Pavage par triomino}
\label{fig:hexa}
\end{figure}
Il est en fait impossible de trouver un tel pavage. Nous
allons commencer par procéder comme précédemment. Le
pavage hexagonal est le $2$-graphe de Cayley du groupe
$$
\<a,b,c\mid a^{2}=b^{2}=c^{2}=(abc)^{2}=1\>.
$$
Les triominos correspondent aux mots
$$
T_{1}=c(ab)^{3}c(ab)^{3},\quad
T_{2}=a(bc)^{3}a(bc)^{3},\quad
T_{3}=b(ca)^{3}b(ca)^{3}.
$$
Le triangle $Y_{n}$ correspond au mot
$$
Y_{n}=(ab)^{n}(ca)^{n}(bc)^{n}.
$$
Il faut donc montrer que $Y_{n}$ est non trivial dans le
groupe
$$
T=\<a,b,c\mid a^{2}=b^{2}=c^{2}=T_{1}=T_{2}=T_{3}=1\>.
$$
L'article \cite{Thurston2} continue sur cette lancée, et
utilise une décomposition de la structure de $T$.
\section{Compléments sur les pavages périodiques}
\subsection{Vers une théorie géométrique des groupes}
Si l'on regarde le graphe de Cayley de
$$
\<a,b\mid aba^{-1}b^{-1}=1\>=\mathbb{Z}^{2},
$$
de loin, il \og ressemble\fg à $\mathbb{R}^2$. Voici
une observation qui rend plus précise cette
\og ressemblance\fg: le segment (c'est-à-dire le chemin
le plus court) entre deux points de $\mathbb{Z}^{2}$ peut
être approché par une ligne brisée tracée
dans le $1$-graphe de Cayley. Plus les points sont loin,
\og meilleure\fg est cette approximation, c'est-à-dire que
le rapport de la distance entre ces deux chemins par rapport
à la longueur du chemin tend vers 0.

En conclusion, on peut espérer que des invariants {\it
à grande échelle} de l'espace pavé (par
exemple du graphe de Cayley) vont nous donner des invariants
du groupe.

Nous allons définir, sans trop de rigueur, un invariant
de ce type: le {\it type de croissance}. Si $X$ est un
espace métrique, muni d'une mesure raisonnable (par
exemple finie sur les boules bornées, invariante par le
groupe des isométries), son type de croissance est le
type de croissance de la fonction
$$
f_{x}:r\longmapsto \hbox{volume}( \hbox{boule de rayon $r$,
centrée en $x$}).
$$
Ce type de croissance, par exemple exponentiel ou
polynômial, ne dépend pas du choix d'un point base
$x$. Pour les espaces euclidiens, cette croissance est
polynomiale, pour l'espace hyperbolique, elle est
exponentielle.

On peut définir le même invariant pour un groupe $G$
muni d'une présentation finie, le {\it type de
croissance} est alors celui de son graphe de Cayley vu
comme espace métrique; on vérifie aisément que
ce type de croissance ne dépend pas de la
présentation. Pour $\mathbb{Z}^{n}$, ce type de
croissance est polynômial; pour les groupes $F_{n}$, il
est exponentiel si $n\geq 2$. Une observation importante et
pas très difficile est la suivante:

\smallskip
\centerline{\it Si le groupe $G$ pave périodiquement
$X$, avec tuile compacte,} \centerline{\it alors $X$ et
$G$ ont le même type de croissance.}

\smallskip
Par exemple, on en déduit que $F_{2}$ ne peut pas paver
$\mathbb{R}^{n}$. Cet invariant très grossier fournit
donc déjà des informations intéressantes. Il~est
intéressant de le relier à la structure
algébrique du groupe. Voici dans cette veine, un des
résultats mathématiques frappants de ces
dernières 25 années \cite{Gromov}
\begin{theorem}[Gromov] Un groupe de présentation finie à
croissance polynomiale possède un sous-groupe d'indice
fini qui est nilpotent. En particulier, un tel groupe se
construit récursivement à partir de groupes
abéliens.
\end{theorem}
La théorie géométrique des groupes a connu des
développements spectaculaires ces derniers trente ans,
sous l'impulsion principalement de Mikhail Gromov. Le lien
entre géométrie de l'espace pavé
périodiquement et structure algébrique du groupe de
paveurs y est fondamental.

\subsection{Pavages périodiques de l'espace euclidien}
La question de comprendre et classifier les pavages
périodiques des espaces euclidiens est une question
ancienne dont les motivations cristallographiques sont
claires. Citons deux très beaux résultats de
Bieberbach du début du siècle, dont une
démonstration simple se trouve dans \cite{Buser}.
\begin{theorem}
Tout groupe de paveur de l'espace euclidien possède un
sous-groupe d'indice fini formé de translations et en
particulier abélien.
\end{theorem}
Effectivement, lorsque l'on regarde un papier peint, plus
généralement un pavage, on peut toujours le paver
par translations à partir d'une tuile rectangulaire,
peut-être plus grosse que les tuiles initiales.
\begin{theorem}
Les groupes de paveurs de l'espace euclidien de dimension
$n$ sont en nombre fini. Il existe en particulier
très exactement 17 groupes de paveurs du plan
euclidien.
\end{theorem}
Signalons que 16 de ces groupes de paveurs sont représentés dans les
pavages de l'Alhambra de Grenade. Le contraste est grand
avec le monde hyperbolique, il existe une infinité de
pavages différents du plan hyperbolique.

\part{Pavages autosimilaires}
\section{Pavages et couvertures autosimilaires}
Nous allons affaiblir la notion de pavage d'un espace
topologique en introduisant celle de {\it couverture}: pour
cela, on remplace la condition {\it intérieurs des
tuiles disjoints} par la condition {\it les tuiles forment
un recouvrement localement fini}. Nous allons nous
intéresser aux pavages et couvertures autosimilaires et répétitifs.
Donnons en la définition, l'espace pavé est $\mathbb
R$ ou $\mathbb C$, le groupe des symétries est le groupe
de translation. On impose deux règles de construction
supplémentaires, {\it autosimilarité} et {\it
répétitivité}. On se donne donc un pavage (ou
une couverture)
dont les tuiles sont les tuiles $T_{i}$.
\begin{itemize}
\item {\it autosimilarité}: le pavage
$$
X=\bigcup_{i\in I} F_{i}
$$
est $\lambda$-autosimilaire (avec $\lambda$ {\it constante d'expansion}
élément de $\mathbb R$ ou $\mathbb C$) si toute
(image de) tuile $F_{i}$ vérifie
$$
\lambda.F_{i}=\bigcup_{j\in J_{i}\subset I}F_{j}.
$$
De plus, on suppose que chaque type de tuile n'a qu'une
subdivision possible après cette
$\lambda$-similitude. C'est-à-dire, si $F_{i}=gT_{k}$, alors
dans la décomposition précédente $J_{i}$ ne
dépend que de $k$;
de plus, si $j\in J_{i}$, alors $F_{j}=g\cdot h_{j}T_{k_{j}}$, où
$h_{j}$ et $k_{j}$ ne dépendent que de $j$.

\item {\it répétitivité}: la condition signifie
simplement que le type de combinatoire {\it local} est
borné. Voici une définition un peu plus technique: pour
tout $r>0$, il existe $R$, tel que pour toute boule
$B_{r}$ de rayon $r$, et $B_{R}$ de rayon $R$, la partie
du pavage intersectant $B_{r}$ se reproduit quelque part
dans $B_{R}$.
\end{itemize}
\begin{figure}[p]
\smaller\smaller
\noindent
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r00c}\\
{La tuile correspondant à $q=0$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r01c}\\
{Les 2 tuiles correspondant à $q=1$}
\end{center}
\end{minipage}\par\medskip
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r02c}\\
{Les 3 tuiles correspondant à $q=2$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r03c}\\
{Les 4 tuiles correspondant à $q=3$}
\end{center}
\end{minipage}\par\medskip
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r04c}\\
{Les 5 tuiles correspondant à $q=4$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r05c}\\
{Les 6 tuiles correspondant à $q=5$}
\end{center}
\end{minipage}
\end{figure}

\begin{figure}[p]
\smaller\smaller
\noindent
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r06c}\\
{Les 8 tuiles correspondant à $q=6$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r07c}\\
{Les 11 tuiles correspondant à $q=7$}
\end{center}
\end{minipage}\par\medskip
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r08c}\\
{Les 15 tuiles correspondant à $q=8$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r09c}\\
{Les 20 tuiles correspondant à $q=9$}
\end{center}
\end{minipage}\par\medskip
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r10c}\\
{Les 26 tuiles correspondant à $q=10$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r11c}\\
{Les 34 tuiles correspondant à $q=11$}
\end{center}
\end{minipage}
\end{figure}

\begin{figure}[htb]
\smaller\smaller
\noindent
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r12c}\\
{Les 45 tuiles correspondant à $q=12$}
\end{center}
\end{minipage}\hfill
%%
\enlargethispage{1cm}
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r13c}\\
{Les 60 tuiles correspondant à $q=13$}
\end{center}
\end{minipage}\par\medskip
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{r14c}\\
{Les 80 tuiles correspondant à $q=14$}
\end{center}
\end{minipage}\hfill
%%
\begin{minipage}{50mm}
\begin{center}
\noindent\includegraphics[width=48mm]{15c}\\
{Les 106 tuiles correspondant à $q=15$}
\end{center}
\end{minipage}
\caption{On a représenté dans les figures ci-dessus les premières étapes de construction du pavage
autosimilaire associé à la racine de $X^{3}\!-\!X\!-\!1$: le nombre de tuiles de l'étape $q$
correspond au nombre de développements faiblement propres de longueur $q$.}
\end{figure}

Un pavage autosimilaire et répétitif est un pavage qui se reproduit
après changement d'échelle, et à type
combinatoire local borné. Nous allons tout d'abord
montrer que tout pavage autosimilaire est relié à un
automate fini. Ceci nous permettra de montrer que la
constante d'expansion est toujours un nombre algébrique
(racine d'un polynôme à coefficients entiers). Nous
construirons ensuite en utilisant des
$\beta$-développements des couvertures autosimilaires
associée à certains nombres algébriques.

Ma connaissance de cette construction provient de la partie
non publiée de la
prépublication déjà citée de W.\,Thurston
\cite{Thurston2}. L'un des articles fondateurs du sujet est
celui de G.\,Rauzy \cite{Rauzy}
\section{Définitions}
Avant de nous lancer dans les constructions, nous allons
énoncer et rappeler quelques définitions et
propriétés utiles.

\subsection{Nombres et entiers algébriques}
Un {\it nombre algébrique} est un nombre complexe racine
d'un polynôme à coefficient entiers. Ce~nombre est un
{\it entier algébrique} si le coefficient de plus haut
degré est 1. C'est une unité algébrique si de
plus le coefficient de plus bas degré est 1.

Si $\beta$ est un nombre algébrique, le polynôme à
coefficient entiers et de plus bas degré annulant
$\beta$ est appelé {\it polynôme minimal}, son degré
est le {\it degré} de $\beta$. Les autres racines de ce
polynôme sont les {\it conjugués de Galois} de $\beta$.
Un {\it nombre de Pisot} est un entier algébrique de
module plus grand que 1, dont tous les conjugués de
Galois (autre que lui même) sont de modules strictement
plus petit que 1; en particulier un nombre de Pisot est
réel.
\subsection{Développement en base \texorpdfstring{$\beta$}{beta}}
Nous sommes coutumiers
des développements en base entière. Les
dévelop\-pements en base non entière ont eux aussi
leur intérêt, comme nous allons le voir. Fixons
$\beta$ un nombre réel plus grand que 1.

Une $\beta$-représentation du réel (positif) $x$ est
une suite (avec virgule) infinie d'entiers positifs ou
nuls $d_{k}d_{k-1}\ldots d_{0},d_{-1}\ldots$
telle que
$$
x=\sum_{i=-\infty}^{d=k}d_{i}\beta{i}.
$$
Par convention, une suite qui se termine par une
infinité de 0 est notée de manière finie. Dans
le cas de la base décimale, tout nombre a une meilleure
représentation; ceci dit d'autres représentations
naturelles ont un rôle, par exemple on a
$$
1=0,9999999999\ldots.
$$
Généralisons cette situation. Les
propriétés suivantes sont assez faciles à
montrer. Tout nombre admet au moins une
$\beta$-représentation. Une $\beta$-représentation
est {\it stricte} si elle supérieure à toutes les
autres dans l'ordre lexicographique; en particulier chaque
coefficient est alors plus petit que la partie entière
de $\beta$. Toute nombre admet une unique représentation
stricte. Une représentation est {\it faiblement propre}
si chaque troncature (c'est-à-dire on ne considère
que la suite jusqu'à un certain rang) est stricte.
Toute représentation stricte est aussi faiblement propre. En
fait, il existe au plus 2 représentations faiblement
propres.
\begin{proposit}
Tout réel admet au plus $2$ représentations
faiblement propres. Il n'en admet qu'une si et seulement
si sa représentation stricte est infinie.
\end{proposit}

Le nombre 1 va en particulier avoir 2 représentations
faiblement propres, celle qui n'est stricte
s'appelle {\it suite de retenue}, on la note $\carry(\beta)$.
On a
\begin{eqnarray*}
\carry(10)&=&0,99999999999\ldots\\
\carry(\hbox{nombre d'or})&=&0,(10)
\end{eqnarray*}
La suite de retenue de $\beta$ apporte des informations sur
$\beta$. Ainsi, nous avons
\begin{proposit}
Si la suite de retenue de $\beta$ est périodique à
partir d'un certain rang, alors $\beta$ est un nombre algébrique.
\end{proposit}

{\it Démonstration.} Dans la représentation en base
$\beta$, la
multiplication par $\beta$ devient élémentaire, elle
consiste à déplacer la virgule
$$
\beta\cdot d_{k}\ldots d_{0},d_{-1}\dots =d_{k}\ldots,
d_{0}d_{-1},\dots.
$$
Dès lors, si la suite de retenue est périodique
de période $q$ à partir d'un certain rang, nous en
déduisons que $\beta^{q}\cdot 1 -1$ a une
$\beta$-représentation finie, ainsi $\beta$ est solution
d'un polynôme à coefficients entiers. Nous verrons un
peu plus tard que pour une unité de Pisot, la suite de
retenue est périodique.

\smallskip Enfin, la
suite de retenue permet de caractériser les
représentations faiblement propres: nous laissons au lecteur la
démonstration de la proposition suivante
\begin{proposit}\label{carryfaible}
Un $\beta$-développement est faiblement propre si et
seulement si chacun de ses translatés est plus petit
(au sens lexicographique) que la suite de retenue.
\end{proposit}

\section{Automates finis}
\subsection{Définition}

Une {\it machine de type fini} ou {\it automate à
états finis}~$M$ sur un alphabet $\mathcal{A}$ consiste
en la donnée suivante
\begin{itemize}
\item un ensemble fini $S_M$ ({\it ensemble des états de
$M$}),
\item une application $\mathcal{A} \times S_M \longrightarrow
S_M$ ({\it fonction de transition de $M$}),
\item un élément fixé $I$ de $S_M$
(\emph{état initial}),
\item un sous ensemble particulier $OK$ ({\itétats
acceptés de $M$}) de $S_{M}$, les autres étant
appelés {\it états d'échec}.
\end{itemize}

Il faut concevoir un tel automate comme un graphe fini
étiqueté: les sommets sont les états, de chaque
sommet part exactement une arête étiquetée par
chacune des lettres de $\mathcal{A}$.

La fonction d'un automate fini est de rejeter ou d'accepter
des mots sur l'alphabet $\mathcal{A}$. De manière plus
précise, chaque mot en $\mathcal{A}$ est conçu (comme
pour les graphes de Cayley) comme une suite d'instructions.
Partant de l'état initial $I$, un mot est {\it
accepté} s'il finit en un état de $OK$, il est
{\it refusé} sinon. L'ensemble de ces mots
acceptés, noté $L(M)$, est appelé {\it langage
de $M$}.

On dit que $L(M)$ est {\it fermé par préfixe} si
chaque préfixe d'un mot de $L(M)$ est dans $L(M)$.
Cela signifie qu'un mot (conçu comme
un chemin) passant par un état d'échec, est
nécessairement refusé. Du point de vue du graphe,
cela signifie que les flèches partant d'un état
d'échec, aboutisse à un échec. L'automate
accepte alors le même langage que celui obtenu en
regroupant tous les états d'échec en un seul; par
convention, dans cette situation, on ne représente pas
graphiquement l'état d'échec, ni les flèches y
conduisant.

Dans le cas d'un langage fermé par préfixe, on a une
bonne notion de mots infinis acceptés par la machine:
ce sont ceux dont tous les préfixes sont acceptés.

\subsection{Automate, développement en base \texorpdfstring{$\beta$}{beta}, autosimilarité}

\subsubsection*{Automate et \texorpdfstring{$\beta$}{beta}-représentation}
Les représentations faiblement~propres constitue un
langage fermé par préfixe. On a le résultat
suivant
\begin{theorem}[$\beta$-Automate]
L'ensemble des $\beta$-représentations faiblement
pro\-pres est un langage accepté par un automate fini
$M_\beta$ si et seulement si $\carry({\beta})$ est
périodique à partir d'un certain rang.
\end{theorem}

\begin{figure}[htbp]
\centerline{\includegraphics[width=100mm]{FSA}}
\caption{$\beta$-Automate }
\label{fig:autocarry}
\end{figure}

{\it Démonstration:} Supposons dans un premier temps
que
$$
\carry(\beta)=0,a_1\ldots a_q\,(c_1\ldots c_p)
$$
soit périodique à partir d'un certain rang. On
considère l'automate construit dans la figure
\ref{fig:autocarry} dans laquelle l'état d'échec et
les flèches y menant n'ont pas été
représentés. Le lecteur vérifiera que les seuls
mots acceptés sont ceux dont tout translaté est plus
petit que $\carry(\beta)$ et donc faiblement propre.

Réciproquement, supposons que l'on dispose d'un automate
fini qui reconnaisse le caractère faiblement propre d'un
développement. Cet automate va nous permettre de
reconstruire $\carry(\beta)$. Il suffit pour cela de choisir
à chaque sommet la flèche affectée du plus haut
coefficient. Comme il n'existe qu'un nombre fini
d'états, $\carry(\beta)$ va être périodique.

\subsubsection*{Automate et pavage autosimilaire}
Nous allons dans un premier temps construire un automate
associé à une couverture autosimilaire. Rappelons que chaque tuile n'a qu'un
type de subdivision possible après $\lambda$-similitude.

Voici les étapes de la construction.
\begin{itemize}
\item {\it Graphe:} Nous construisons tout d'abord un
graphe fini $\Gamma$ dont les sommets sont les types de
tuiles. Chaque tuile se subdivisant après expansion,
nous traçons $k$ flèches du type $x$ vers le type
$y$, si $y$ apparaît $k$ fois dans la subdivision de $x$.
\item {\it Capitales:} Nous choisissons dans chaque tuile
une capitale, de telle sorte que la $\lambda$-image d'une
capitale soit une capitale. Voici la manière de
procéder: dans le graphe précédent, on
choisit une flèche partant de chaque sommet; chaque
cycle dans ce sous-graphe définit une contraction
d'un type de tuile dans lui même; on choisit comme
capitale le point fixe de cette contraction; puis on
propage ces capitales aux tuiles aboutissant sur les
cycles.
\item{\it Étiquettes:} Nous considérons l'alphabet
fini $\mathcal{D}$, constitué
\begin{itemize}
\item des différences entre capitales,
\item d'un symbole par type de tuile contenant 0.
\end{itemize}
\item{\it Automate:} Chaque flèche
du type $x$ vers le type $y$ indique le choix
d'une tuile de type $y$ dans la subdivision de $x$; nous l'étiquetons par la
différence des deux capitales correspondantes. On
ajoute ensuite à $\Gamma$ un état initial $I$, les
flèches étiquetées $x$ (pour un certain type
de tuile) partent de $I$ vers le sommet $x$; un état
final $F$ d'échec, ou arrivent toutes les
étiquettes non représentées.
\end{itemize}
Cet automate contient toute l'information sur la couverture
autosimilaire. Ainsi, on associe chaque mot infini (avec
virgule)
$$
(xz_{k_{0}}\ldots z_{0},z_{1}\ldots)
$$
accepté par l'automate, le nombre en base $\lambda$
$$
\sum_{k=k_{0}}^{\infty}z_{k}\lambda^{k}.
$$
Les tuiles correspondent alors aux mots ayant la même
partie fractionnaire.
\subsubsection*{Automate et algébricité de la constante d'expansion}
L'existence de capitales, produite par l'automate, va nous
permettre de montrer

\smallskip

\centerline{\it La
constante d'expansion d'un pavage autosimilaire}
\centerline{\it est un entier algébrique}

\smallskip

On remarque qu'il existe un ensemble fini $\mathcal{R}$ de
différences (des nombres complexes) entre capitales,
vérifiant la propriété suivante.

{\it Il existe
une constante $K$ telle que pour deux capitales
données $c_\alpha$ et $c_\delta$, il existe une suite
finie de capitales $\lbrace
c_\alpha=c_0,\ldots,c_n=c_\delta \rbrace$ avec $
c_{j+1}-c_j\in R$ et $ n\leq K\vert
c_\alpha-c_\delta\vert$}.

Pour cela on prend pour
$\mathcal{R}$, l'ensemble des différences de capitales
dont la distance est inférieure à $3$ fois le
diamètre maximum des pavés. Par
répétitivité $\mathcal{R}$ est fini.

Ceci nous permet de conclure à l'algébricité de
la constante d'expansion. La multiplication par $\lambda$
transforme la différence de deux capitales en la
différence de deux autres capitales Autrement dit, si
$\mathcal{R}=\lbrace r_i \rbrace$, on a
$$
\forall i, \quad\lambda r_i=\sum_{j}h_{ij}r_j, \hbox{
avec }\forall (i,j)\quad h_{ij}\in\mathbb Z.
$$
Autrement dit, $\lambda$ est une valeur propre de la
matrice $H=(h_{ij})\in\mathcal{M}_n (\mathbb Z)$. Le nombre
$\lambda$, racine du polynôme caractéristique de
$H$, est un entier algébrique.

\section{Constructions de pavages autosimilaires}

\subsection{Une construction élémentaire}
Nous allons commencer par construire un pavage de la droite
réelle autosimilaire (de constante d'expansion $\beta$)
à partir d'un nombre $\beta$ dont la suite de retenue
est périodique. Définissons tout d'abord pour toute
$\beta$-représentation,
\begin{itemize}
\item sa {\it $\beta$-partie entière}: la suite finie
d'entiers avant la virgule,
\item sa {\it $\beta$-partie fractionnaire}: la suite finie
d'entiers après la virgule.
\end{itemize}

Considérons les intervalles formés des
éléments ayant la même $\beta$\nobreakdash-partie
entière de leur représentation faiblement propre. La
suite de retenue étant périodique, il n'y a qu'un
nombre fini d'intervalles à translation près. Cette
collection d'intervalles donne un pavage autosimilaire de la droite.
\subsection{Une construction duale}
\centerline{\it À partir de maintenant, nous supposerons que
$\beta$} \centerline{\it est une unité de Pisot de
degré $3$.}

\smallskip
On notera $\gamma$ son
conjugué de Galois. La construction que nous allons
présenter est duale (ou plutôt conjuguée) de la
précédente. Elle produit une couverture autosimilaire de
constante d'expansion $1/\gamma$.

\subsubsection*{Matrices, dilatation et contraction}

Nous allons tout d'abord considérer $\beta$ comme une
matrice. Soit $P(X)$ le polynôme minimal de $\beta$, et
$M_{\beta}$ la matrice compagnon de $P(X)$, agissant sur
l'espace vectoriel $V(\beta)=\mathbb R^{3}$.

Dans cette situation, nous avons deux sous-espaces propres
de $M(\beta)$, l'un $\mathcal{U}$ de dimension 1 sur lequel
$M_{\beta}$ agit par dilatation, l'autre~$\mathcal{S}$ de
dimension $2$ sur lequel $M_{\beta}$ agit par une
similitude contractante de facteur le conjugué de Galois
de $\beta$. On a
$$
V(\beta)=\mathcal{U} \oplus\mathcal{S},
$$
et on note $\pi$ la projection de $V(\beta)$ sur
$\mathcal{S}$ parallèlement à $\mathcal{U}$. Elle s'identifie
à
$$
(a,b,c)\longmapsto a+b\gamma +c\gamma^{2}.
$$

Considérons $\mathbb Z (\beta)=\mathbb{Z}^{3}$, le
réseau de $\mathbb R^{3}$. Nous appellerons les points de
$\mathbb Z(\beta)$ des $\beta$-entiers et nous
identifierons le point $(a,b,c)$ avec le nombre
$a+b\beta+c\beta^{2}$.

Nous allons montrer
\begin{proposit}
Soit $x$ un $\beta$-entier, alors la $\beta$-représentation
faiblement propre de $x$ est périodique à partir d'un certain
rang. En particulier, $\carry(\beta)$ est périodique.
\end{proposit}

Soit $x$ un $\beta$-entier. L'algorithme de construction
qui permet de construire la représentation strictement propre $x_\beta$ de $x$ peut-être interprété relativement à
$\mathcal{U}$ et $\mathcal{S}$. Remarquons tout d'abord que
l'hyperplan $\mathcal{S}$ sépare les $\beta$-entiers
positifs des négatifs. Voici donc la procédure
utilisée pour obtenir la $\beta$-représentation
faiblement propre. Soit $x$ un $\beta$-entier positif; à chaque étape, on soustrait le plus grand multiple de $1$ dans $V$ tel que $x-k*1$
reste du même côté de $\mathcal{S}$.

Ainsi les images de $x$ par cette opération restent dans une région bornée de~$V$: les composantes de $x$ selon $\mathcal{S}$ sont multipliées par un nombre
de module inférieur à $1$, celle selon $\mathcal{U}$ est maintenue dans un voisinage borné de zéro par soustraction.

Partant d'un $\beta$-entier, il n'y a qu'un nombre
fini de valeurs possibles. Autrement dit, le $\beta$-développement est nécessairement périodique à partir d'un certain rang.

\smallskip
\centerline{\it Notre but est maintenant de produire une couverture
autosimilaire de $\mathcal{S}$} \centerline{\it de
constante d'expansion $1/\gamma$.}

\subsubsection*{Étapes de la construction}

Remarquons tout d'abord que tout $\beta$\nobreakdash-en\-tier a
une représentation stricte finie. Il possède en
particulier une $\beta$-représentation faiblement propre
infinie.

Pour tout $x\in \mathbb Z (\beta)$, nous considérons
$T_{x}$ le sous-ensemble de $\mathbb Z(\beta)$ formé des
éléments ayant la même $\beta$-partie
fractionnaire. Posons ensuite $K_{x}=\overline{\pi(T_{x})}$,
nous allons montrer (en partie) les propriétés suivantes:
\begin{itemize}
\item les $K_{x}$ sont compacts,
\item les $K_{x}$ forment un recouvrement localement fini,
\item il n'y a qu'un nombre fini de $K_{x}$ a translation
près.
\end{itemize}
Nous avons donc bien obtenu une couverture par translation
de~$\mathcal{S}$. De~plus, cette couverture est par
construction autosimilaire de constante d'expansion
$1/\gamma$, où $\gamma$ est le conjugué de Galois de
$\beta$: en effet, l'action de $M_{\beta}$ étant
essentiellement la multiplication par $\beta$ sur les
$\beta$-entiers, nous avons
$$
M_{\beta}(T_{x})=\bigcup_{i} T_{y_{i}}.
$$

\begin{Remarques*}\mbox{}
\begin{itemize}
\item Les ensembles $K_{x}$ s'appellent les {\it fractals de
Rauzy}, ils ne sont ni nécessairement connexes, ni
simplement connexes.
\item On ne sait toujours pas si les fractals de Rauzy
pavent le plan, c'est-à-dire sont d'intérieurs
disjoints, seuls certains cas, en particulier celui du
{\it nombre de Tribonacci} étudié par G.\,Rauzy,
sont connus \cite{Rauzy}.
\item Le lecteur pourrait se demander à juste titre ce
qui se passe lorsque l'on projette sur $\mathcal{U}$ les
tuiles formées d'éléments ayant la même
$\beta$-partie entière. En remarquant que la
projection sur $\mathcal{U}$ s'identifie à
l'application $(a,b,c)\mapsto a+b\beta+c\beta^{2}$, il
retrouvera la construction élémentaire.
\end{itemize}
\Subsection{Démonstrations}
\subsubsection*{Compacité des tuiles} Si deux éléments $x$ et $y$ ont une représentation faiblement propre ayant
la même partie fractionnaire, leur différence
s'écrit
$$
x-y=\sum_{i=0}^{i=p}(a_{i}-b_{i})\beta^{i}.
$$
Or chaque $a_{i}$ et $b_{i}$ est plus petit que $[\beta]$
(partie entière de $\beta$), de plus $\pi(\beta)=\gamma$.
On a donc
$$
\vert \pi(x)-\pi(y)\vert\leq
2[\beta]\sum_{i=0}^{i=\infty}\vert
\gamma\vert^{i}=2[\beta]\,\frac{1}{1-\vert \gamma\vert}.
$$
Nous venons de montrer le diamètre de chaque fractal
de Rauzy est borné par une constante.
\subsubsection*{Finitude locale} On montre assez facilement
que chaque ensemble $T_x$ admet un représentant dans le
pavé $\mathcal{S}\times [0,1]$.
On note $M$ le diamètre maximum des compacts $K_x$
$s\in\mathcal{S}$ le disque de $\mathcal{S}$: $D(s,2M)$. Les seuls compacts intervenant dans le disque $D(s,M)$ sont ceux
qui sont inclus dans $D(s,2M)$, et donc en particulier admettent un représentant dans
le compact $D(s,2M)\times[0,1]$. Comme ces représentants sont éléments du réseau qui est discret, il n'y en a qu'un nombre
fini. Localement, seul un nombre fini de compacts s'intersectent et on en déduit que les $K_x$ forment un recouvrement
localement fini de $\mathcal{S}$.
\end{Remarques*}

\subsubsection*{Nombre fini de tuiles} Pour cela, il suffit de montrer
qu'il y a un nombre fini de $T_{x}$ à translation
près. Nous allons utiliser le $\beta$-automate. Celui-ci
permet de répondre à la question suivante: \og étant donnée une suite $(d_k)_{k\in\mathbb N}$,
quels sont les nombres dont le $\beta$-développement
faiblement propre se termine par cette suite?\fg

En effet, on détermine le caractère faiblement propre sans connaître les coef\-ficients précédents: l'automate
utilise seulement l'état dans lequel il s'est arrêté. Pour une suite donnée, on peut regarder l'ensemble $F(d)$
(éventuellement vide) des états de l'automate dont on peut partir pour que la suite de coefficients soit acceptée.
La forme d'un pavé est entièrement déterminée par cet ensemble (à une translation près puisque l'on peut ajouter une
combinaison linéaire finie de puissance de $\beta$).
Il n'y a qu'un nombre fini de $F(d)$ possibles (au plus $2^n$):
il n'y a donc qu'un nombre fini de formes.

\subsection{Questions et compléments}
La construction précédente pose un certain nombre de
problèmes non encore résolus: nous ne savons toujours pas
si nous sommes véritablement en présence d'un pavage. Un
résultat récent d'Anne Siegel \cite{Siegel} assure de l'existence d'un
algorithme permettant de déterminer à partir du nombre de
Pisot si la construction fournit oui ou non un pavage. Enfin par
ailleurs la répétitivité n'est pas toujours claire.

Signalons par contre que l'on peut améliorer le résultat sur
l'algébricité: on peut montrer que la constante d'expansion
est un nombre de Perron, c'est-à-dire un nombre dont tous les
conjugués de Galois (autre que son conjugué complexe) sont
de module plus petit. Réciproquement, R. Kenyon
\cite{Kenyon} a construit des pavages autosimilaires et
répétitifs admettant un nombre de Perron quelconque comme constante d'expansion.

\backmatter
\addtocontents{toc}{\protect \lsectionpart}
\bibliographystyle{jepplain+eid}
\bibliography{xups01-02}
\end{document}
