# Pavage apériodique

En mathématiques, et plus particulièrement en géométrie, un pavage apériodique est un pavage ne contenant pas de sections périodiques arbitrairement grandes. Les pavages de Penrose$^,$ sont les exemples les plus connus de pavages apériodiques, mais il existe plusieurs autres méthodes pour en construire.
Les pavages apériodiques servent de modèles mathématiques pour les quasi-cristaux, des objets physiques découverts en 1982 par Dan Shechtman, mais dont la structure locale exacte est encore mal comprise.

## Définitions

On appelle pavage apériodique un pavage (non périodique) ne contenant pas de parties périodiques arbitrairement grandes (pour éviter des pavages non périodiques tels qu'un pavage périodique déformé en un nombre fini d'endroits, et qu'un pavage périodique déformé en un nombre infini d'endroits « isolés » (distribués « non uniformément »)).
Plus formellement, soit $T=\{T_{k}\subset \mathbb {R} ^{d}\}_{1\leq k\leq n}$ un ensemble de n tuiles de l'espace euclidien à d dimensions ; notant S l'ensemble des translatés $\{T_{k}+x\,:\,x\in \mathbb {R} ^{d}\}_{1\leq k\leq n}$, l’enveloppe de T est l'adhérence de S dans la topologie dite locale, pour laquelle deux tuiles sont de distance $<\varepsilon$ si elles coïncident dans une boule de centre l'origine et de rayon $1/\varepsilon$, éventuellement après une translation de norme $<\varepsilon$. Avec ces définitions, un pavage est apériodique si son enveloppe ne contient que des pavages non périodiques. On vérifie ainsi, par exemple, que partant d'un pavage périodique et modifiant un nombre fini de tuiles, l'enveloppe du pavage non périodique résultant est le pavage périodique initial, et donc que le pavage modifié n'est pas apériodique.
Pour de nombreux pavages « réguliers », comme ceux construits plus bas, on a le résultat suivant : si un tel pavage est non périodique et que chaque type de tuile apparait de manière « uniformément dense » (c'est-à-dire que la proportion des tuiles de ce type dans les boules de rayon R tend vers une limite non nulle quand R tend vers l'infini), alors le pavage est apériodique.
Un ensemble de tuiles est dit apériodique (en) si ces tuiles ne peuvent former que des pavages non périodiques, qui sont alors nécessairement apériodiques.

## Historique

Les premiers pavages apériodiques apparurent en 1961, lorsque Wang Hao essaya de déterminer si le problème des dominos (en) était décidable, c'est-à-dire s'il existait un algorithme permettant de savoir si un ensemble fini donné de tuiles pouvait paver le plan. Wang construisit un algorithme énumérant les ensembles de tuiles ne pavant pas le plan, et un autre énumérant les ensembles pavant le plan périodiquement, ce qui démontrait que le problème était décidable si, comme il le conjecturait alors, tout ensemble permettant un pavage permettait aussi un pavage périodique. Mais, en 1966, Robert Berger (en) découvrit une preuve de l'indécidabilité du problème, à l'aide d'un exemple explicite d'ensemble apériodique de tuiles. Ce premier exemple utilisait 20426 tuiles (appelées par la suite des tuiles de Wang (en)) ; Berger lui-même obtint ensuite un ensemble de 104 tuiles, à son tour ramené à 40 tuiles par Hans Läuchli (en).
En 1971, un ensemble de 6 tuiles (dérivées de tuiles de Wang) fut construit par Raphael Robinson. Mais c'est la découverte par Roger Penrose de trois ensembles apériodiques, dont des ensembles de deux tuiles (en 1973 et 1974) qui devait populariser le problème, en raison de l'aspect esthétique des pavages obtenus ; Robert Ammann construisit plusieurs nouveaux ensembles en 1977. La question de l'existence d'une tuile qui serait apériodique à elle seule est restée ouverte jusqu'en 2023,
Les pavages de Penrose peuvent être construits non seulement à partir d'un ensemble de tuiles apériodique, mais par les deux méthodes décrites ci-dessous de substitution et de coupe et projection. Après la découverte des quasi-cristaux et de leur structure non périodique en 1984, les pavages apériodiques firent l'objet d'études intensives par les physiciens et les mathématiciens. La méthode de coupe et projection (due, pour les pavages de Penrose, à N.G. de Bruijn) devint un cas particulier de la théorie des ensembles de Meyer (en)$^,$. En 2013, une vaste littérature s'était développée autour des pavages apériodiques.
La question de savoir s'il existe une tuile seule dont le pavage apériodique permet de recouvrir le plan porte le nom de « Problème einstein » (par un jeu de mots clin d’œil à Einstein : une tuile d'un pavage se dit en allemand « Stein », et une seule tuile est donc « ein Stein ») et est restée en suspens jusqu'en 2023 bien que plusieurs tuiles répondant presque à cette condition aient été découvertes à partir de 1996$^,$.
En 2023, David Smith, Joseph Samuel Myers, Craig S. Kaplan (en) et Chaim Goodman-Strauss (en) ont proposé un pavage avec une seule tuile sans retournement, qu'ils ont appelé le « spectre ».

## Constructions

On connait plusieurs constructions de pavages apériodiques, basées parfois sur des familles infinies d'ensembles de tuiles apériodiques$^,$. Ces constructions ne reposent que sur quelques méthodes générales, principalement consistant à forcer une structure hiérarchique non périodique. Cependant, le fait que le problème des dominos soit indécidable entraîne qu'il doit exister une infinité de méthodes de construction distinctes, et même des ensembles de tuiles apériodiques pour lesquels cette apériodicité est indémontrable.

### Pavages apériodiques hiérarchisés

Il n'y a pas actuellement d'accord sur une définition rigoureuse de ce qu'est une structure hiérarchique pour un pavage ; il est néanmoins clair que les pavages de substitution en ont une, ainsi que les pavages de Berger, de Knuth, de Läuchli et de Robinson. L'expression « tuiles apériodiques hiérarchisées » se rencontre parfois comme abréviation pour « ensemble de tuiles ne permettant que des pavages non périodiques ayant une structure hiérarchique ». En fait, les pavages correspondant à un tel ensemble sont nécessairement apériodiques, parce qu'aucune translation ne peut laisser la structure hiérarchique entière invariante.
Ainsi, Robinson a défini en 1971 l'ensemble de tuiles suivant :
Un pavage par ces tuiles fait nécessairement apparaître une hiérarchie de grilles carrées : chaque carré orange entoure le coin d'un carré orange de taille supérieure. Une translation donnée est nécessairement de taille plus petite qu'un de ces carrés, et ne peut donc le laisser invariant.
Robinson a démontré que cette hiérarchie est forcée par ses tuiles, les blocs qu'elles forment étant des copies plus larges des mêmes tuiles.
La même idée est utilisée dans la construction de la plupart des ensembles apériodiques de tuiles connus actuellement.

### Substitutions

Un pavage par substitution (en) est un pavage dans lequel un ensemble de tuiles se combine pour former une tuile identique à l'une des tuiles initiales, mais agrandie ; on peut donc également les construire (ou plus exactement en construire des portions finies aussi grandes qu'on veut) en substituant à chaque étape de construction cet ensemble à chacune des tuiles de l'étape précédente, ce qui peut se formaliser à l'aide d'un type d'automate qu'on appelle un L-système. Ces pavages sont nécessairement apériodiques, mais l'ensemble de tuiles lui-même ne l'est pas toujours. Ainsi, les tuiles « en chaise » ci-dessous peuvent former la structure de substitution dite également « en chaises », mais aussi de nombreux pavages périodiques.
En revanche, les tuiles ci-dessous (dites « crabes et trilobites ») forcent la structure en chaise, et sont donc apériodiques.
Les tuiles de Penrose furent le premier exemple de pavage apériodique obtenu en forçant une structure de substitution à apparaître ; peu de temps après, Robert Ammann découvrit plusieurs ensembles de tuiles ayant la même propriété. Joshua Socolar$^,$, Roger Penrose, Ludwig Danzer et Chaim Goodman-Strauss obtinrent par la suite d'autres ensembles. Shahar Mozes obtint la première construction générale, en montrant que tout produit de systèmes de substitution à une dimension peut être forcé par un ensemble convenable de tuiles. Charles Radin construisit des règles (et des tuiles) forçant le pavage en moulin à vent. En 1998, Goodman-Strauss montra que toute structure de pavage par substitution (satisfaisant quelques conditions supplémentaires assez faibles) pouvait être forcée par des règles locales, et donc par des ensembles de tuiles apériodiques.

### Projections

Des pavages non périodiques du plan, par exemple, peuvent également être obtenus par projection de pavages périodiques d'un espace de plus grande dimension (ou plus précisément de la coupure d'un tel pavage par un plan) ; dans certains cas, il existe des ensembles de tuiles forçant cette structure de pavage, et ces ensembles sont donc apériodiques. Les tuiles de Penrose sont un exemple de cette situation, comme le montra le travail fondateur de de Bruijn. On ne connait pas encore de caractérisation algébrique complète des pavages obtenus par coupe et projection qui peuvent être forcés par des ensembles de tuiles, mais de nombreuses conditions nécessaires ou suffisantes ont été obtenues.

### Autres techniques, généralisations

Plusieurs autres principes de construction ont été découverts. Ainsi, Jarkko Kari (en) a déterminé un ensemble apériodique de tuiles de Wang utilisant la multiplication par 2 ou 2/3 de nombres réels codés par des lignes de tuiles (le codage est lié aux suites sturmiennes formées de différences successives des termes de suites de Beatty), l'apériodicité résultant principalement de ce que $2^{n}/3^{m}$ n'est jamais égal à 1 si n et m sont des entiers non nuls. Cette méthode fut ensuite adaptée par Goodman-Strauss pour obtenir un ensemble de tuiles « fortement apériodique » pavant le plan hyperbolique. Shahar Mozes découvrit d'autres constructions d'ensembles apériodiques, parfois dans des contextes plus exotiques, par exemple dans des groupes de Lie semi-simples. Block et Weinberger utilisèrent des méthodes homologiques pour construire des ensembles apériodiques pavant toutes les variétés « moyennables». Joshua Socolar obtint également des conditions forçant l'apériodicité, les conditions alternantes ; celles-ci produisent généralement des ensembles de tuiles beaucoup plus petits que ceux obtenus par la méthode de substitution.

## Physique des pavages apériodiques

Les pavages apériodiques étaient considérés comme des curiosités mathématiques jusqu'à ce que Dan Shechtman annonce en 1984 la découverte, dans un alliage d'aluminium et de manganèse, d'une phase donnant un diagramme de diffraction présentant une indiscutable symétrie d'ordre cinq – et donc d'un cristal admettant une symétrie du groupe de l'icosaèdre ; il reçut le prix Nobel de chimie en 2011 pour cette découverte. En 1975, Robert Ammann avait déjà étendu la construction de Penrose à un équivalent tridimensionnel basé sur l'icosaèdre ; il fallut cependant attendre les travaux de Gummelt et Steinhard vers 1995 pour comprendre comment ces pavages apériodiques mathématiques pouvaient effectivement apparaître dans des structures physiques, sans pourtant qu'on ait encore, en 2014, complètement élucidé les mécanismes effectivement à l'œuvre dans les exemples connus. Des dispositifs photoniques sont souvent construits par des superpositions apériodiques de couches « cristallines », et sont donc apériodiques dans une direction, mais périodiques dans les deux autres. Des quasi-cristaux de Cd-Te sont au contraire formés de couches apériodiques, mais toutes identiques. Steinhardt a montré qu'on pouvait appliquer un principe extrémal à une structure, définie par Gummelt, de décagones se chevauchant, démontrant dans ce cas l'identification entre le pavage mathématique et la structure physique du quasi-cristal. On a observé que des ondes de Faraday pouvaient former de larges plages de motifs apériodiques ; cette découverte a ravivé l'intérêt pour les structures de périodes non commensurables, suggérant une relation entre pavages apériodiques et phénomènes d'interférences.

## Questions de terminologie

Le terme apériodique est utilisé fréquemment sans définition rigoureuse dans la littérature mathématique sur les pavages, ainsi d'ailleurs que dans d'autres domaines comme la théorie des systèmes dynamiques ou la théorie des graphes ; en particulier, il est souvent simplement synonyme de « non périodique », c'est-à-dire tel qu'aucune translation de vecteur non nul ne le laisse invariant. En physique, on parle de solide apériodique (c'est-à-dire de quasi-cristal) pour désigner des structures non périodiques possédant une sorte d'ordre global.
Malgré sa définition ne présentant pas d'ambiguïté, même le mot « pavage » est parfois problématique. Ainsi, la notion de pavage de Penrose est mal définie : les losanges de Penrose peuvent être assemblés d'une infinité de façon (non distinguables localement). En pratique, la littérature technique définit soigneusement sa terminologie dans chaque cas, mais reconnait l'absence de définitions générales consensuelles.