[figure]

Pavages de Wang

Une tuile de Wang est un carré dont les quatre côtés sont marqués (avec un signe particulier ou une couleur, par exemple). On réalise un pavage de Wang en plaçant de telles tuiles côte à côte (sans les faire tourner), de façon que les marques adjacentes soient identiques ; un pavage de Wang est donc une application f de ℤ^{2} vers le jeu de tuiles, respectant certaines contraintes (locales). Problème de Wang : un jeu (fini) de tuiles de Wang donné permet-il de paver le plan? Ce problème est décidable s’il existe un algorithme qui prend en entrée un jeu de tuiles de Wang, et dit si l’on peut paver le plan avec ce jeu.

[figure]

Exemples de jeux de tuiles

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

2 8 9 3 ^{6 2 1 4} ^{1 4 5 2}

3 1 2 1 ^{4 5 4 5} ^{5 9 8 6}

On ne peut pas paver le plan avec ce deuxième jeu de tuiles :

2 2 2 3 ^{1 1 1 2} ^{3 1 2 1}

Exercice : démontrez-le !

[figure]

Solutions

Premier jeu de tuiles : on pave un rectangle 2 × 3, qui fournit un pavage de période (3, 2).

2 8 9 3 ^{3 1 2 1} ^{1 4 5 2}

5 9 8 6 ^{6 2 1 4} ^{4 5 4 5}

Deuxième jeu de tuiles : il n’y a qu’une façon d’aligner les tuiles horizontalement, or le rapport 1/2 n’est pas le même sur le bord haut et sur le bord bas.

2 2 2 3 ^{3 1 2 1} ^{1 1 1 2}

[figure]

Périodicité

Un pavage de Wang f est doublement périodique s’il existe a et b tous deux non nuls tels que

f(x + a, y) = f(x, y + b) = f(x, y)

quel que soit (x, y) ∈ ℤ^{2}. Un pavage est simplement périodique s’il existe (a, b) non nul tel que f(x + a, y + b) = f(x, y) pour tout (x, y) ∈ ℤ^{2}. Théorème (Wang) : si un jeu de tuiles permet de réaliser un pavage simplement périodique, alors il permet aussi de réaliser un pavage doublement périodique. Preuve : on se contentera du cas b = 0. Un jeu de tuiles de Wang est apériodique s’il permet de paver le plan, mais pas de façon périodique.

[figure]

Théorèmes et conjectures

Théorème : si un jeu de tuiles de Wang permet de paver des carrés arbitrairement grands, il permet de paver le plan entier. Preuve : c’est le lemme de Koenig. Théorème (Wang) : s’il n’existe pas de jeu de tuiles apériodique, alors le problème de Wang est décidable. Conjecture (Wang) : il n’existe pas de jeu de tuiles apériodique. Théorème (Berger 1966) : il existe des jeux de tuiles apériodiques, et le problème de Wang n’est pas décidable. Berger a exhibé un jeu apériodique de 20426 tuiles…

[figure]

Suites de Beatty

Au réel α, on associe la suite de Beatty de terme général A(α)_{i} = ⌊iα⌋, où i ∈ ℤ. La suite B(α) de terme général

B(α)_{i} = A(α)_{i+1} − A(α)_{i}

est la représentation équilibrée de α; elle est aussi connue sous les noms de suite caractéristique, ou suite de Christoffel. Remarque : si k ⩽ α ⩽ k + 1 (où k ∈ ℤ) alors les termes de la suite B(α) sont égaux à k ou à k + 1. De plus :

|ℓα − ∑_{j⩽i<j+ℓ} B(α)_{i}| < 1

Note du relecteur : cette inégalité n’a aucun intérêt. Le présentateur veut juste se faire mousser.

Note du présentateur : le relecteur est prié d’aller voir là-haut sur la colline.

[figure]

Automates à deux bandes

Un automate à deux bandes est un quadruplet (Q, Σ, Δ, γ) où Q est l’ensemble (fini) des états, Σ l’alphabet d’entrée, Δ l’alphabet de sortie et γ ⊂ Q × Σ × Δ × Q est la table des transitions. Soient x ∈ Σ^{ℤ} et y ∈ Δ^{ℤ} deux mots biinfinis ; on dira que l’automate associe y à x s’il existe une suite (s_{i})_{i∈ℤ} d’états telle que

(s_{i}, x_{i}, y_{i}, s_{i+1}) ∈ γ pour tout i ∈ ℤ

[figure]

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

Soit q = \frac{n}{m} un rationnel positif ; construisons un automate à deux bandes M_{q} qui réalise (en un certain sens) la multiplication par q d’un réel donné par sa représentation équilibrée. Les états de M_{q} sont les valeurs possibles de q⌊x⌋ − ⌊qx⌋ lorsque x décrit ℝ. Comme −q < ⌊qx⌋ − q⌊x⌋ < 1, et que ces valeurs sont des multiples de \frac{1}{m}, on aura M_{q} = \{−\frac{n−1}{m}, −\frac{n−2}{m}, …, \frac{m−2}{m}, \frac{m−1}{m}\}. Les alphabets d’entrée et de sortie sont des parties finies de ℤ; les transitions de M_{q} sont les quadruplets (s, a, b, t) tels que s + qa = b + t. On vérifie que, si B(α) peut être écrit avec l’alphabet Σ et B(qα) avec l’alphabet Δ, alors l’automate associe B(qα) à B(α) : pour s’en convaincre, prendre s_{i} = qA(α)_{i} − A(qα)_{i}.

[figure]

Multiplication par 3

Exemple : l’automate à deux bandes M_{3} ci-dessous effectue la multiplication par 3 d’un réel α ∈ [\frac{1}{3}, \frac{2}{3}]; plus précisément, si α ∈ [\frac{1}{3}, \frac{2}{3}] alors l’automate associe B(3α) à B(α).

[figure: −2; −1; 0; 1,2; 1,2; 0,1; 0,1; 1,1; 0,2]

[figure]

Exemple de multiplication par 3

α = \frac{2}{5} a pour représentation équilibrée … 00101 … 3α = \frac{6}{5} a pour représentation équilibrée … 11112 …

\begin{matrix}i & 0 & 1 & 2 & 3 & 4 & 5 \\ A(α)_{i} & 0 & 0 & 0 & 1 & 1 & 2 \\ A(3α)_{i} & 0 & 1 & 2 & 3 & 4 & 6 \\ s_{i} & 0 & −1 & −2 & 0 & −1 & 0 \\ x_{i} & 0 & 0 & 1 & 0 & 1 & 0 \\ y_{i} & 1 & 1 & 1 & 1 & 2 & 1 \\ s_{i+1} & −1 & −2 & 0 & −1 & 0 & −1 \end{matrix}

[figure]

Multiplication par \frac{1}{2}

De même, l’automate à deux bandes M_{1/2} ci-dessous associe B(α/2) à B(α) pour α ∈ [0, 2] ; l’alphabet d’entrée est {0, 1, 2} tandis que l’alphabet de sortie est {0, 1}.

[figure: 0; \frac{1}{2}; 1,0; 1,1; 2,1; 2,1; 0,0; 0,0]

[figure]

Le jeu de tuiles de Kari et Čulik

À la transition (s, a, b, t) nous associons la tuile de Wang ci-dessous :

s ab t

À l’automate M_{3} exhibé précédemment, nous associons donc le jeu de 6 tuiles T_{3} ci-dessous :

0 0 1−1 ^{−10 1−2} ^{−21 2−1}

−11 2 0 ^{−21 1 0} ^{0 0 2−2}

Il est clair que ce jeu ne permet pas, à lui tout seul, de paver le plan.

[figure]

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

[figure: 0′; \frac{1}{2}; 1,0; 1,1; 1,0′; 2,1; 2,1; 0′,0; 0′,0]

[figure]

À cet automate nous associons donc le jeu de tuiles T′_{1/2} ci-dessous.

0′ 0′ 0 0′  ^{0′ 2 1 0′}  ^{0′ 1 0 ^{\frac{1}{2}}}  ^{0′ 1 0′ ^{\frac{1}{2}}}

\frac{1}{2} 0′ 0 ^{\frac{1}{2}}  ^{^{\frac{1}{2}} 2 1 ^{\frac{1}{2}}}  ^{^{\frac{1}{2}} 1 1 0′}

Ce jeu ne permet pas non plus de paver le plan entier : les tuiles avec un 2 sur la rangée supérieure et celles avec un 0 sur la rangée inférieure ne peuvent être utilisées ; les deux tuiles restantes ne peuvent alors suffire. Remarquons au passage que l’on peut paver trois rangées horizontales consécutives avec ce jeu ; mais, ensuite, on est bloqué ! Notons M l’automate obtenu en réunissant M_{3} et M′_{1/2}, et T = T_{3} ∪ T′_{1/2}.

[figure]

Des pavages apériodiques, enfin !

Théorème : T permet de réaliser une infinité non dénombrable de pavages apériodiques du plan. Preuve : fixons α ∈ [\frac{1}{3}, 2]. L’automate M permet de calculer B(3α) si α ∈ [\frac{1}{3}, \frac{2}{3}], B(α/2) si α ∈ [\frac{2}{3}, 2]. Inversement, il existe une entrée B(α/3) si α ∈ [1, 2] ou B(2α) si α ∈ [\frac{1}{2}, 1] à laquelle cet automate associe B(α). Traduisons ceci en termes de pavages : à chaque α ∈ [\frac{1}{3}, 2] on peut associer un pavage du plan. Si α et β ne sont pas commensurables, leurs représentations équilibrées ne peuvent apparaître dans un même pavage.

[figure]

Apériodicité de T

Théorème : le jeu de tuiles T est apériodique. Preuve : par l’absurde. Soit f un pavage (doublement) périodique réalisé avec T, de périodes horizontale a et verticale b. Chaque rangée est réalisée avec des tuiles de l’un des jeux T_{3} ou T′_{1/2} (grâce à l’introduction de la lettre 0′). Comme aucun de ces jeux ne permet à lui tout seul de paver le plan, chacun d’eux sert au moins une fois. Pour fixer les idées, supposons la rangée 0 formée avec le jeu T_{3}.

[figure]

Notons n_{i} la somme des marques des arêtes supérieures des tuiles f(i, j) pour 1 ⩽ j ⩽ b; le report entrant par l’arête gauche de la tuile f(i, 1) étant égal au report sortant par l’arête droite de la tuile f(i, b) on a n_{i−1} = q_{i}n_{i} où q_{i} vaut 3 ou \frac{1}{2} selon que c’est le jeu T_{3} ou le jeu T′_{1/2} qui est utilisé pour paver la rangée i. La périodicité impose alors

n_{b} = n_{0} = q_{1}q_{2} … q_{b}n_{b}

comme la rangée 0 est pavée avec le jeu T_{3}, on a n_{0} ≠ 0 donc q_{1}q_{2} … q_{b} = 1 mais ceci est contradictoire.

[figure]

Conclusion

Le jeu apériodique que l’on a construit comporte treize tuiles. On peut remplacer les marques placées sur les côtés par des couleurs ; en notant que les couleurs utilisées sur les côtés horizontaux peuvent fort bien être reprises pour les côtés verticaux, on constate que cinq couleurs suffisent (alors que, dans la construction, sept marques différentes ont été utilisées). Il semble que ce jeu apériodique soit le plus petit connu, à ce jour.

[figure]

Complément personnel

Notons φ l’application qui, à α ∈ [\frac{1}{3}, \frac{2}{3}[ associe 3α et à α ∈ [1, 2[ associe \frac{α}{2}. Notons g : α ∈ [\frac{1}{3}, 2[ ↦ \frac{ln α+ln 3}{ln 6} ; g réalise une bijection de [\frac{1}{3}, 2[ sur [0, 1[. Considérons alors g ∘ φ ∘ g^{−1} ; notant s = \frac{ln 3}{ln 6} on a g(x) = x + 1 − s si 0 ⩽ x < s et g(x) = x − s si s ⩽ x < 1. g est donc une rotation de l’intervalle [0, 1[. Comme 2 et 3 sont multiplicativement indépendants, s est irrationnel, et les orbites sous l’action de g sont codables par des mots sturmiens (cf. Agreg 94). L’apparition de mots sturmiens (biinfinis) ne doit pas surprendre, ceux-ci étant les mots apériodiques de complexité minimale.

[figure]

Références

Hao Wang. Proving theorems by pattern recognition II. Bell System Tech. J., 40 : 1-41, 1961.

Robert Berger. The undecidability of the domino problem. Memoirs of the AMS, 66 : 201-213, 1966.

Jarkko Kari. A small aperiodic set of Wang tiles. Discrete Mathematics, 160 : 259-264, 1996.

Karel Čulik II. An aperiodic set of 13 Wang tiles. Discrete Mathematics, 160 : 245-251, 1996.

Cyril Allauzen, Bruno Durand. Pavages du plan : indécidabilité et apériodicité. Rapport de Recherche 95-28, École Normale Supérieure de Lyon.

Merci à Jean Berstel, Karel Čulik, Bruno Durand et, last but not least, Yves Duval.