\( \newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACC}{\mathcal{C}} \newcommand{\ACV}{\mathcal{V}} \newcommand{\ACQ}{\mathcal{Q}} \)

Tuiles et pavages

Cours M2 - MIT
Victor Poupet
\(\newcommand{\vector}[2]{\left(\begin{array}{cc}{#1}\\{#2}\end{array}\right)}\)

Présentation du problème

Origine lointaine


Théorèmes (1935-1970)
Si la classe considérée est assez riche pour exprimer les mathématiques usuelles, alors il n'existe pas de programme qui décide si une formule de cette classe est ou non un théorème

Origine moderne


Problème (Domino Problem)

Entrée : un ensemble fini de tuiles.

Question : peut-on paver le plan avec elles ?

Différents modèles...

Tuiles de Wang



Définition
Un pavage du plan est le placement de copies des tuiles bord-à-bord de façon à ce que les couleurs en contact coincident.

On peut aussi paver des carrés, des tores, etc.

Réflexion préliminaire


Définition
Un ensemble de tuiles est apériodique s'il peut paver le plan, mais jamais périodiquement

Sous-shifts

Tuiles de Wang faciles à définir mais pas pratiques à utiliser.

→ sous-shifts de type fini

  • Plan discret
  • Ensemble fini de décorations
  • Configuration : associe à chaque cellule une décoration
  • Ensemble fini de motifs interdits

Définition
Un pavage est une configuration ne contenant aucun motif interdit.

Informellement :

  • Un jeu de tuiles est un ensemble de règles qui peuvent être vérifiées localement
  • Il existe une taille \(N\) telle que si toute fenêtre de taille \(N \times N\) est correcte alors la configuration est un pavage

Équivalence

Proposition
Le Domino Problem avec des tuiles de Wang est équivalent à la formulation par motifs interdits

Preuve. On convertit une instance de l’un en instance équivalente de l’autre

  • Un sens facile (✎ lequel ?)
  • Soit un ensemble de motifs interdits
    • motifs interdits de taille \(\leq m × n\)
    • couleurs horizontales : motifs \((m − 1) × n\)
    • couleurs verticales : motifs \(m × (n − 1)\) tuiles à partir de chaque motif \(n × m\) autorisé

Avec contrainte

Théorème (Wang)
Étant donné un jeu de tuiles \(\tau\) et une tuile \(t ∈ \tau\), il est indécidable de savoir s’il existe un pavage contenant \(t\)

✎ Preuve


→ Il existe un pavage si et seulement si la machine ne termine pas sur l’entrée vide

Périodicité

Définition

Définition
Une configuration est périodique si elle est invariante par translation d’un vecteur non nul
Défintion
Une configuration est bi-périodique si elle est périodique selon deux vecteurs indépendants
Définition
Un jeu de tuiles est apériodique s’il admet un pavage mais qu’il n’admet pas de pavage périodique

Quelle périodicité ?

$$\overrightarrow{p_1} = \vector{x_1}{y_1} \qquad\overrightarrow{p_2} = \vector{x_2}{y_2}$$

$$x_2\overrightarrow{p_1} - x_1\overrightarrow{p_2} = \vector{0}{x_2y_1 − x_1y_2}$$

$$y_2\overrightarrow{p_1} - y_1\overrightarrow{p_2} = \vector{y_2x_1 - y_1x_2}{0}$$

Proposition
Si un ensemble de tuiles admet un pavage périodique, alors il en admet un bi-périodique
Remarque
Un pavage bi-périodique a une période verticale et une horizontale

→ Un ensemble de tuiles est aperiodique s’il pave le plan mais n’admet aucun pavage horizontalement et verticalement périodique

Quasi-périodicité

Définition
Un motif \(m\) est récurrent dans une configuration \(\ACC\) s’il existe un entier \(n\) tel que \(m\) apparaît dans toute fenêtre de taille \(n \times n\) dans \(\ACC\)
Définition
Une configuration \(\ACC\) est quasi-périodique si tous les motifs qu’elle contient sont récurrents
Théorème
Si un jeu de tuiles pave le plan, il admet un pavage quasi-périodique

✎ Preuve (double compacité !)

Un jeu de tuiles apériodique

Exemple pour s'insipirer

Robinson 1970


Idées :

Idée générale

Idées :

Lignes bleues

Rectangles bleus

Rectangles et infini


Pas grave

Carrons les rectangles


→ les rectangles deviennent carrés

Les bras

Croisements

Note
Au plus un croisement est une propriété locale

Alignement

Proposition
Des carrés connectés par des bras ont la même taille

Preuve par l’absurde en considérant le plus petit mal aligné


Rmq : Comme des bras infinis ne peuvent pas apparaître dans une configuration bi-périodique, on peut supposer que tout carré a un voisin dans chaque direction

La grille de départ


Induction

On veut des carrés arbitrairement grands

Les groupes de 9

Au centre

Un pavage valide

Résumé de la construction

Construction complète

Structure

Strucure imposée (récurrence)


Rmq : Carrés infinis possibles (angles ou droites)

Et l'indécidabilité ?

Apériodicité insuffisante pour conclure

→ On injecte du calcul dans la structure auto-similaire