Chapitre 1

Pavages, problèmes de pavage

Fig. 1.1 – Pavage par des losanges

1.1 Une définition

Ce que l’on regroupe sous la dénomination “pavages”, 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 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, ou voire totalement différente.

Un problème de pavage est la donnée suivante

– Un espace X, et une région Y ⊂ 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.

– Un 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.U, l’image par l’élément g de G du sous-ensemble U de X.

– Un ensemble (la plupart du temps fini) de tuiles {T_{i}}_{i∈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 intérieur, T̆_{i}, et d’un bord, ∂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 = ℝ^{2} et d’un ensemble fini de tuiles polygonales.

Le 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écisement encore, peut-on écrire

Y = ⋃_{g∈A} g.T_{i(g)},

où A est un sous-ensemble de G, et tel que de plus, pour deux éléments g et h de A

g ≠ h ⟹ g.T̆_{i(g)} ∩ h.T̆_{i(h)} = ∅.

On imposera en général des règles ou contraintes supplémentaires. Voici quelques exemples particulièrement importants de contraintes :

– 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é groupe de paveur ; dans cette situation, la “forme” de la tuile n’a pas beaucoup d’importance et la “théorie” des pavages s’identifie à celle des groupes discrets, comme nous le verrons plus tard.

– Règles locales. On impose assez souvent des règles de constructions locales. Par exemple, si on a quatre tuiles {T_{i}}_{i} ∈ {1, …, 4}, on peut exiger que les images de T_{1} rencontrent toujours une image de T_{2} mais jamais une image de T_{4}, etc.

– 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.

1.1.1 Premiers exemples

Pavage carré

C’est le carrelage des salles de bains, très certainement le plus antique. Ici Y = X = ℝ^{2} est le plan euclidien, on considère une seule tuile T = [0, 1] × [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 = ℤ^{2} est le groupe des translations de vecteurs entiers.

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), (\frac{1}{2}, \frac{\sqrt{3}}{2}). Le groupe de paveur est alors le groupe engendré par la rotation d’angle \frac{π}{3} de centre (0, 0) et la translation de vecteur (0, 1).

Problème A : pavage par des losanges

Le pavage triangulaire va nous permettre d’introduire un problème (que nous appellerons 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 ∪ 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 ℝ^{2}. 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

La région Y peut-elle être pavée par les losanges L_{1}, L_{2}, L_{3} avec “groupe” de symétries G (figure 1.1) ?.

La réponse dépend bien entendu de la région Y. Nous allons par la suite décrire une “obstruction” 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.

Problème B : un jeu de morpion

Fig. 1.2 – Un jeu de morpion sur un triangle

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 (Problème B), qui n’est pas à première vue un problème de pavage.

On se donne un triangle de points construit de la manière suivante : soit X_{n} le triangle équilatéral de sommet (0, 0), (n, 0), (\frac{n}{2}, \frac{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 :

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 1.2) ?

1.1.2 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 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 [2] et vulgarisée par Thurston [7]. 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é galerie, Jean-René Geofroy présente un programme Xmaple permettant d’obtenir des pavages autosimilaires et quelques images qu’il obtient ainsi.

Premières références

Presque tout ce qui suit est tiré d’une merveilleuse prépublication de William Thurston [8], plus tard partiellement publiée dans [7]. Par ailleurs, le programme sous 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 Geometry Center

http ://www.geom.umn.edu/

En y butinant, vous y trouverez quelques programmes et appliquettes Java autour des pavages (en anglais : tilings). En particulier, la page

http ://www.geom.umn.edu/graphics/pix/Special Topics/Tilings/

contient des images de pavages. Voici une autre référence plus didactique.

www.math.okstate.edu/mathdept/dynamics/lecnotes/

Les adresses suivantes fournissent des exemples de pavages autosimilaires :

http ://www.inma.ucl.ac.be/ canterini/ http ://iml.univ-mrs.fr :80/ siegel/ http ://iml.univ-mrs.fr/presentation/gal/imldac/structures/berthe.html

1.2 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 présentation finie. Nous expliquerons cette notion dans le prochain paragraphe. Nous montrerons que réciproquement tout groupe de présentation 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.

1.2.1 Groupe libre, groupe de présentation finie

Un groupe est de génération finie s’il possède un nombre fini de générateurs. Le prototype de tels groupes est le groupe libre à n-générateurs F_{n}. Nous allons passer un peu de temps à rappeler la définition de ce groupe.

Groupe libre

On se donne tout d’abord n lettres s_{i}, i ∈ {1, …, n}. Un mot est une expression formelle du type suivant

s_{i_{1}}^{p_{1}}s_{i_{2}}^{p_{2}} … s_{i_{k}}^{p_{k}},  (1.1)

où les p_{i} sont des entiers relatifs. On a une opération naturelle qui a deux mots associe leur concaténé

C : (s_{i_{1}}^{p_{1}}s_{i_{2}}^{p_{2}} … s_{i_{k}}^{p_{k}}, b_{i_{1}}^{p_{1}}b_{i_{2}}^{p_{2}} … b_{i_{l}}^{p_{l}}) ↦ s_{i_{1}}^{p_{1}}s_{i_{2}}^{p_{2}} … s_{i_{k}}^{p_{k}}b_{i_{1}}^{p_{1}}b_{i_{2}}^{p_{2}} … b_{i_{l}}^{p_{l}}

On note le concaténé de deux mots m_{0} et m_{1} sous la forme m_{0} ∘ 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 mot réduit est un mot, où dans l’expression (1.1), on suppose de plus que i_{j} ≠ i_{j+1} et p_{i} ≠ 0. Par convention, le mot 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 ∘ a^{p} ∘ a^{q} ∘ c, alors on remplace m par b ∘ a^{p+q} ∘ c si p + q ≠ 0, et par b ∘ c si p + q = 0, puis on itère. Au bout d’un nombre fini d’étapes, on arrivera à un mot réduit.

Le groupe libre sur les lettres s_{i}, i ∈ {1, …, 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}.m_{1} = R(m_{0} ∘ 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 groupe libre F_{n} à n générateurs s_{i}, i ∈ {1, …, n}. On le note aussi F (S), pour S = {s_{1}, …, s_{n}}. Ce groupe est universel dans le sens suivant : si b_{1}, …, 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).

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}, …, s_{n}}, et l’ensemble des relations R = {R_{1}, …, R_{k}}, où les R_{k} sont des éléments du groupe libre F (S). Un tel groupe se note symboliquement

G =< S|R >=< s_{1}, …, s_{n}|R_{1} = … = R_{k} = 1 > .

Par définition G = F (S)/N(R), où N(R) est l’intersection de tous les sousgroupes 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

m_{0} = g_{1}.R_{k_{1}}.g_{1}^{−1}. . . . .g_{l}.R_{k_{l}}.g_{l}^{−1}.m_{1}.

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.

Exemples

Donnons quelques exemples très simples. Dans ces exemples S_{n} désigne le groupe des permutations de {1, …, n} .

< a|a^{2} = 1 > = ℤ/2ℤ,
< a, b|aba^{−1}b^{−1} = 1 > = ℤ^{2},
< a, b, c|aba^{−1}b^{−1} = aca^{−1}c^{−1} = cbc^{−1}b^{−1} = 1 > = ℤ^{3},
< a, b, c|c^{−1}ab = aba^{−1}b^{−1} = 1 > = ℤ^{2}.
< a, b|a^{2} = b^{2} = (ab)^{3} = 1 > = S_{3}.
< a, b, c|a^{2} = b^{2} = c^{2} = (ab)^{3} = (bc)^{3} = (ac)^{3} = 1 > = S_{4}.

Exercice : vérifiez les égalités ci-dessus.

1.2.2 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 2-graphe de Cayley.

Graphe orienté étiqueté

Un graphe orienté est constitué d’un ensemble de sommets V, et d’un ensemble d’arêtes A ⊂ V ×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 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 réalisation simpliciale. Celle-ci est l’espace topologique obtenu, en “collant” des intervalles à chaque arête abstraite. Dans cette réalisation simpliciale, mathématiquement un 1-complexe, les arêtes ont homéomorphes à des intervalles.

1-Graphe de Cayley

Le graphe de Cayley (pour le moment le 1-graphe) d’un groupe G engendré finiment par les générateurs (s_{1}, …, s_{n}) est le graphe orienté défini de la manière suivante :

– les sommets sont les éléments du groupe,

– les arêtes étiquetées s_{i} sont tous les couples (g, gs_{i}). 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 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 ℤ^{2}, différent du réseau usuel.

Fig. 1.3 – Graphe de Cayley de < a, b, c|abc^{−1} = ca^{−1}b^{−1} = 1 >

Un graphe de Cayley n’est pas nécessairement planaire. Le graphe de Cayley de

< a, b, c|aba^{−1}b^{−1} = aca^{−1}c^{−1} = cbc^{−1}b^{−1} = 1 >= ℤ^{3}

n’est pas naturellement planaire, c’est le réseau cubique dans ℝ^{3}.

Morphismes de groupe

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

< a, b, c|aba^{−1}b^{−1} = aca^{−1}c^{−1} = cbc^{−1}b^{−1} = 1 > = ℤ^{3},
< a, b, c|c^{−1}ab = aba^{−1}b^{−1} = 1 > = ℤ^{2}.

Il existe dans cette application un morphisme de groupe f : ℤ^{3} → ℤ^{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.

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.s_{1}), puis on suit s_{4}, 4 fois de suite, puis on remonte (en sens inverse) les arêtes étiquetées s_{2}, 2 fois de suite.

On remarque que dans cette interprétation les mots réduits deviennent des 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|abc^{−1} = ca^{−1}b^{−1} = 1 >, les mots

L_{1} = aba^{−1}b^{−1},
L_{2} = aca^{−1}c^{−1},
L_{3} = cbc^{−1}b^{−1},

correspondent aux trois losanges de la figure 1.4. Le lecteur attentif commencera à voir une certaine similarité avec le problème A.

2-Graphe de Cayley

Continuons sur la lancée de la précédente observation. Supposons que G est défini par les générateurs S = {s_{1}, …, s_{p}} et les relations R = {R_{1}, …, R_{k}}.

Fig. 1.4 – 3 losanges

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}.R_{k_{1}}.g_{1}^{−1}. . . . .g_{l}.R_{k_{l}}.g_{l}^{−1}.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 tuiles étiquetées par les relations R_{i}. Pour chaque relation R_{i} = s_{i_{1}}^{p_{1}} … s_{i_{k}}^{p_{k}}, on considère le polygone régulier ayant n = ∑ |p_{i}| 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|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 “collant” au 1-graphe 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.

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|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 1.5).

Fig. 1.5 – Les deux tuiles triangulaires

1.3 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écisement, 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|c^{−1}ab = aba^{−1}b^{−1} = 1 > .

Nous avons une courbe γ_{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 γ_{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

Proposition 1.1 Si Y est pavable par losanges, alors il existe des éléments g_{i} de F (a, b, c) tels que,

γ_{Y} = g_{1}L_{i_{1}}^{p_{1}}g_{1}^{−1} … g_{q}L_{i_{q}}^{p_{q}}g_{q}^{−1};

Autrement dit, γ_{Y} ∈ N(L_{1}, L_{2}, L_{3})

Nous pouvons énoncer cette dernière relation en théorie des groupes. Au mot γ_{Y}, nous associons l’élément I(Y), du groupe

H =< a, b, c|aba^{−1}b−1 = aca^{−1}c^{−1} = cbc^{−1}b^{−1} = 1 > .

Notons π la projection de H = ℤ^{3} dans G = ℤ^{2}, comme en 1.2.2. Nous savons que I(Y) ∈ Ker(π). D’après la proposition 1.1, si Y est pavable par losange alors I(Y) = 0. Enfin, Ker(π) est isomorphe à ℤ.

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

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 γ_{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 γ_{Y} etc. Comme c = ab dans G, il est facile de voir que, dire que γ_{Y} est nul dans G, signifie r = p = q. En conclusion

L’entier I(Y) est la somme des exposants de a dans le mot γ_{Y}.

Remarques

– 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.

– La nullité de I(Y) n’est pas suffisante pour conclure à l’existence d’un pavage. Il est facile de construire un contrexemple, 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 γ_{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 1.1 en plissant les yeux, le pavage par losanges apparait 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 [7].

1.4 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 γ_{Y_{n}}. Les trois segments possible utilisés pour barrer les points, correspondent à trois triominos, T_{1}, T_{2}, T_{3}, chacun obtenu en réunissant trois hexagones. La question est donc :

peut-on paver Y_{n} par des trionimos (figure 1.6) ?

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|a^{2} = b^{2} = c^{2} = (abc)^{2} = 1 > .

Les trionimos correspondent aux mots

T_{1} = c(ab)^{3}c(ab)^{3},
T_{2} = a(bc)^{3}a(bc)^{3},
T_{3} = b(ca)^{3}b(ca)^{3}.

Fig. 1.6 – Pavage par trionimo

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|a^{2} = b^{2} = c^{2} = T_{1} = T_{2} = T_{3} = 1 > .

L’article [8] continue sur cette lancée, et utilise une décomposition de la structure de T.

1.5 Compléments sur les pavages périodiques

1.5.1 Vers une théorie géométrique des groupes

Si l’on regarde le graphe de Cayley de

< a, b|aba^{−1}b^{−1} = 1 >= ℤ^{2},

de loin, il “ressemble” à ℝ^{2}. Voici une observation qui rend plus précise cette “ressemblance” : le segment (c’est-à-dire le chemin le plus court) entre deux points de ℤ^{2} peut être approché par une ligne brisée tracée dans le 1-graphe de Cayley. Plus les points sont loin, “meilleure” 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 à 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 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 ↦ volume(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 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 ℤ^{n}, ce type de croissance est polynômial ; pour les groupes F_{n}, il est exponentiel si n ≥ 2. Une observation importante et pas très difficile est la suivante

Si le groupe G pave périodiquement X, avec tuile compacte, alors X et G ont le même type de croissanc.

Par exemple, on en déduit que F_{2} ne peut pas paver ℝ^{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 derniers 25 années [3]

Theorem 1.2 (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.

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.

1.5.2 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 [1].

Theorem 1.3 Tout groupe de paveur de l’espace euclidien possède un sousgroupe d’indice fini formé de translations et en particulier abélien.

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.

Theorem 1.4 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.

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.

18 CHAPITRE 1. PAVAGES, PROBLÈMES DE PAVAGE

Chapitre 2

Pavages autosimilaires

2.1 Pavages et couvertures autosimilaires

Nous allons affaiblir la notion de pavage d’un espace topologique en introduisant celle de couverture : pour cela, on remplace la condition intérieurs des tuiles disjoints par la condition 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 ℝ ou ℂ, le groupe des symétries est le groupe de translation. On impose deux règles de construction supplémentaires, autosimilarité et répétitivité. On se donne donc un pavage (ou une couverture) dont les tuiles sont les tuiles T_{i}.

– autosimilarité : le pavage

X = ∪_{i∈I}F_{i}

est λ-autosimilaire (avec λ constante d’expansion élément de ℝ ou ℂ) si toute (image de) tuile F_{i} vérifie

λ.F_{i} = ∪_{j∈J_{i}⊂I}F_{j}.

De plus, on suppose que chaque type de tuile n’a qu’une subdivision possible après cette λ-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 ∈ J_{i}, alors F_{j} = g.h_{j}T_{k_{j}}, où h_{j} et k_{j} ne dépendent que de j.

– répétitivité : la condition signifie simplement que le type de combinatoire 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}.

La tuile correspondant à q = 0  Les 2 tuiles correspondant à q = 1

Les 3 tuiles correspondant à q = 2  Les 4 tuiles correspondant à q = 3

Les 5 tuiles correspondant à q = 4  Les 6 tuiles correspondant à q = 5

Les 8 tuiles correspondant à q = 6 Les 11 tuiles correspondant à q = 7 22 CHAPITRE 2. PAVAGES AUTOSIMILAIRES

Les 15 tuiles correspondant à q = 8 Les 20 tuiles correspondant à q = 9

Les 26 tuiles correspondant à q = 10 Les 34 tuiles correspondant à q = 11 Les 45 tuiles correspondant à

q = 12 Les 60 tuiles correspondant à

q = 13

Les 80 tuiles correspondant à q = 14 On a représenté dans les figures ci-contre 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.

Les 106 tuiles correspondant à q = 15

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 β-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 [8]. L’un des articles fondateurs du sujetest celui de G. Rauzy [5]

2.2 Définitions

Avant de nous lancer dans les constructions, nous allons énoncer et rappeler quelques définitions et propriétés utiles.

2.2.1 Nombres et entiers algébriques

Un nombre algébrique est un nombre complexe racine d’un polynôme à coefficient entiers. Ce nombre est un 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 β est un nombre algébrique, le polynôme à coefficient entiers et de plus bas degré annulant β est appelé polynôme minimal, son degré est le degré de β. Les autres racines de ce polynôme sont les conjugués de Galois de β. Un 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.

2.2.2 Développement en base β.

Nous sommes coutumiers des développements en base entière. Les développements en base non entière ont eux aussi leur intérêt, comme nous allons le voir. Fixons β un nombre réel plus grand que 1.

Une β-représentation du réel (positif) x est une suite (avec virgule) infinie d’entiers positifs ou nuls d_{k}d_{k−1} … d_{0}, d_{−1} … telle que

x = ∑_{i=−∞}^{d=k} d_{i}β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 ….

Généralisons cette situation. Les propriétés suivantes sont assez faciles à montrer. Tout nombre admet au moins une β-représentation. Une β-représentation est 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 β. Toute nombre admet une unique représentation stricte. Une représentation est 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.

Proposition 2.1 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.

Le nombre 1 va en particulier avoir 2 représentations faiblement propres, celle qui n’est stricte s’appelle suite de retenue, on la note carry(β). On a

carry(10) = 0, 99999999999 …
carry(nombre d’or) = 0, (10)

La suite de retenue de β apporte des informations sur β. Ainsi, nous avons

Proposition 2.2 Si la suite de retenue de β est périodique à partir d’uun certain rang, alors β est un nombre algébrique.

Démonstration. Dans la représentation en base β, la multiplication par β devient élémentaire, elle consiste à déplacer la virgule

β.d_{k} … d_{0}, d_{−1} ⋯ = d_{k} …, d_{0}d_{−1}, ….

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 β^{q}.1 − 1 a une β-représentation finie, ainsi β 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.

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

Proposition 2.3 Un β-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.

2.3 Automates finis

2.3.1 Définition

Une machine de type fini ou automate à états finis M sur un alphabet A consiste en la donnée suivante

– un ensemble fini S_{M} (ensemble des états de M),

– une application A × S_{M} ⟶ S_{M} (fonction de transition de M), – un élément fixé I de S_{M} (état initial),

– un sous ensemble particulier OK (états acceptés de M) de S_{M}, les autres étant appelés états d’échec.

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 A.

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

On dit que L(M) est 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.

2.3.2 Automate, développement en base β, autosimilarité

Automate et β-représentation

Les représentations faiblement propres constitue un langage fermé par préfixe. On a le résultat suivant

Theorem 2.4 β-Automate L’ensemble des β-représentations faiblement propres est un langage accepté par un automate fini M_{β} si et seulement si carry(β) est périodique à partir d’un certain rang.

Démonstration : Supposons dans un premier temps que

carry(β) = 0, a_{1} … a_{q} (c_{1} … c_{p})

soit périodique à partir d’un certain rang. On considère l’automate construit dans la figure 2.1 dans laquelle l’état d’échec et les flèches y menant n’ont

Fig. 2.1 – β-Automate

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(β) 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(β). 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(β) va être périodique.

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 λ-similitude.

Voici les étapes de la construction.

– Graphe : Nous construisons tout d’abord un graphe fini Γ 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.

– Capitales : Nous choisissons dans chaque tuile une capitale, de telle sorte que la λ-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.

– Étiquettes : Nous considérons l’alphabet fini D, constitué – des différences entre capitales,

– d’un symbole par type de tuile contenant 0.

– 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 à Γ 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.

Cet automate contient toute l’information sur la couverture autosimilaire. Ainsi, on associe chaque mot infini (avec virgule)

(xz_{k_{0}} … z_{0}, z_{1} …)

accepté par l’automate, le nombre en base λ

∑_{k=k_{0}}^{∞} z_{k}λ^{k}.

Les tuiles correspondent alors aux mots ayant la même partie fractionnaire.

Automate et algébricité de la constante d’expansion

L’existence de capitales, produite par l’automate, va nous permettre de montrer

La constante d’expansion d’un pavage autosimilaire est un entier algébrique

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

Il existe une constante K telle que pour deux capitales données c_{α} et c_{δ}, il existe une suite finie de capitales {c_{α} = c_{0}, …, c_{n} = c_{δ}} avec c_{j+1} − c_{j} ∈ R et n ≤ K|c_{α} − c_{δ}|.

Pour cela on prend pour 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é R est fini.

Ceci nous permet de conclure à l’algébricité de la constante d’expansion. La multiplication par λ transforme la différence de deux capitales en la différence de deux autres capitales Autrement dit, si R = {r_{i}}, on a

∀i, λr_{i} = ∑_{j} h_{ij}r_{j}, avec ∀(i, j) h_{ij} ∈ ℤ.

Autrement dit, λ est une valeur propre de la matrice H = (h_{ij}) ∈ M_{n}(ℤ). Le nombre λ, racine du polynôme caractéristique de H, est un entier algébrique.

2.4 Constructions de pavages autosimilaires

2.4.1 Une construction élémentaire

Nous allons commencer par construire un pavage de la droite réelle autosimilaire (de constante d’expansion β) à partir d’un nombre β dont la suite de retenue est périodique. Définissons tout d’abord pour toute β-représentation,

– sa β-partie entière : la suite finie d’entiers avant la virgule,

– sa β-partie fractionnaire : la suite finie d’entiers après la virgule.

Considérons les intervalles formés des éléments ayant la même β-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 auto-similaire de la droite.

2.4.2 Une construction duale

A partir de maintenant, nous supposerons que β est une unité de Pisot de degré 3.

On notera γ 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/γ.

Matrices, dilatation et contraction

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

Dans cette situation, nous avons deux sous-espaces propres de M(β), l’un U de dimension 1 sur lequel M_{β} agit par dilatation, l’autre S de dimension 2 sur lequel M_{β} agit par une similitude contractante de facteur le conjugué de Galois de β. On a

V (β) = U ⊕ S,

et on note π la projection de V (β) sur S parallèlement à U. Elle s’identifie à

(a, b, c) ↦ a + bγ + cγ^{2}.

Considérons ℤ(β) = ℤ^{3}, le réseau de ℝ^{3}. Nous appellerons les points de ℤ(β) des β-entiers et nous identifierons le point (a, b, c) avec le nombre a + bβ + cβ^{2}.

Nous allons montrer

Proposition 2.5 Soit x un β-entier, alors la β-représentation faiblement propre de x est périodique à partir d’un certain rang. En particulier, carry(β) est périodique.

Soit x un β-entier. L’algorithme de construction qui permet de construire la représentation strictement propre x_{β} de x peut-être interprété relativement à U et S. Remarquons tout d’abord que l’hyperplan S sépare les βentiers positifs des négatifs. Voici donc la procédure utilisée pour obtenir la β-représentation faiblement propre. Soit x un β-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 S.

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

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

Notre but est maintenant de produire une couverture autosimilaire de S de constante d’expansion 1/γ

Étapes de la construction

Remarquons tout d’abord que tout β-entier a une représentation stricte finie. Il possède en particulier une β-représentation faiblement propre infinie.

Pour tout x ∈ ℤ(β), nous considérons T_{x} le sous-ensemble de ℤ(β) formé des éléments ayant la même β-partie fractionnaire. Posons ensuite K_{x} = \overline{π(T_{x})}, nous allons montrer (en partie) les propriétés suivantes :

– les K_{x} sont compacts,

– les K_{x} forment un recouvrement localement fini,

– il n’y a qu’un nombre fini de K_{x} a translation près. Nous avons donc bien obtenu une couverture par translation de S. De plus, cette couverture est par construction autosimilaire de constante d’expansion 1/γ, où γ est le conjugué de Galois de β : en effet, l’action de M_{β} étant essentiellement la multiplication par β sur les β-entiers, nous avons

M_{β}(T_{x}) = ∪_{i}T_{y_{i}}.

Remarques

– Les ensembles K_{x} s’appellent les fractals de Rauzy, ils ne sont ni nécessairement connexes, ni simplement connexes.

– 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 nombre de Tribonacci étudié par G. Rauzy, sont connus [5].

– Le lecteur pourrait se demander à juste titre ce qui se passe lorsque l’on projette sur U les tuiles formées d’éléments ayant la même β-partie entière. En remarquant que la projection sur U s’identifie à l’application (a, b, c) ↦ a + bβ + cβ^{2}, il retrouvera la construction élémentaire.

2.4.3 Démonstrations

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 = ∑_{i=0}^{i=p}(a_{i} − b_{i})β^{i}.

Or chaque a_{i} et b_{i} est plus petit que [β] (partie entière de β), de plus π(β) = γ. On a donc

|π(x) − π(y)| ≤ 2[β] ∑_{i=0}^{i=∞} |γ|^{i} = 2[β]\frac{1}{1 − |γ|}.

Nous venons de montrer le diamètre de chaque fractal de Rauzy est borné par une constante.

Finitude locale

On montre assez facilement que chaque ensemble T_{x} admet un représentant dans le pavé S × [0, 1]. On note M le diamètre maximum des compacts K_{x} s ∈ S le disque de 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) × [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 S.

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 β-automate. Celui-ci permet de répondre à la question suivante : “étant donnée une suite (d_{k})_{k∈ℕ}, quels sont les nombres dont le β-développement faiblement propre se termine par cette suite ?”

En effet, on détermine le caractère faiblement propre sans connaître les coefficients 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 β). 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.

2.4.4 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 [6] 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 34 CHAPITRE 2. PAVAGES AUTOSIMILAIRES [4] a construit des pavages autosimilaires et répétitifs admettant un nombre de Perron quelconque comme constante d’expansion.

Bibliographie

[1] P. Buser, A geometric proof of Bieberbach’s theorems on crystallographic groups. Enseign. Math. (2) 31 (1985), no. 1-2, 137–145.

[2] J.H. Conway and J.C. Lagarias, Tiling with Polyominoes and Combinatorial Group Theory. J. Combinatorial Theory, Series A 53 (1990), 183–208.

[3] M. Gromov, Groups of polynomial growth and expanding maps. Inst. Hautes Études Sci. Publ. Math. No. 53 (1981), 53–73.

[4] R. Kenyon, The construction of self-similar tilings. Geom. Funct. Anal. 6 (1996), no. 3, 471–488.

[5] G. Rauzy, Nombres algébriques et substitutions Bull. Soc. Math. France 110 (1982), no 2, 147–178

[6] A. Siegel, Représentations géométrique, combinatoire et arithmétique des systèmes substitutifs de type Pisot Thèse de Doctorat, Université de la Méditérranée, 2000

[7] W. P. Thurston, Conway’s Tiling Groups. Amer. Math. Monthly 97 (1990), no. 8, 757–773.

[8] W. P. Thurston, Tilings and finite state automata AMS Colloquium Lecture Notes, non publié, 1989.