\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=\=\. $$ 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*} \&=&\mathbb{Z}/2\mathbb{Z},\\ \&=&\mathbb{Z}^{2},\\ \&=&\mathbb{Z}^{3},\\ \&=&\mathbb{Z}^{2}.\\ \&=&\mathcal{S}_{3}.\\ \&=&\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{$\$}} \label{fig:triang1} \end{figure} \par\noindent Un graphe de Cayley n'est pas nécessairement planaire. Le graphe de Cayley~de\vspace*{-3pt} $$ \={\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*} \&=&\mathbb{Z}^{3},\\ \&=&\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 $\$, 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 $$ \. $$ 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 $$ \, $$ 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=\. $$ 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 =\. $$ 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 $$ \. $$ 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=\. $$ 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 $$ \=\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}