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. ; reprise de l'article du Scientific American dans le premier chapitre du livre 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 un ensemble de n tuiles de l'espace euclidien à d dimensions ; notant S l'ensemble des translatés , l’enveloppe de T est l'adhérence de S dans la topologie dite locale, pour laquelle deux tuiles sont de distance si elles coïncident dans une boule de centre l'origine et de rayon , éventuellement après une translation de norme . 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 si ces tuiles ne peuvent former que des pavages non périodiques, qui sont alors nécessairement apériodiques.
Historique vignette|upright=1.2|Pavage de Wang minimal, avec onze tuiles de Wang en quatre couleurs, décrit par Jeandel et Rao en 2015Emmanuel Jeandel et Michael Rao, dans .. Les premiers pavages apériodiques apparurent en 1961, lorsque Wang Hao essaya de déterminer si le é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, 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 ) ; Berger lui-même obtint ensuite un ensemble de 104 tuiles, à son tour ramené à 40 tuiles par Hans Läuchli, section 11.1..
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 . En 2013, une vaste littérature s'était développée autour des pavages apériodiques.
vignette|Pavage apériodique à l'aide d'une tuile unique et de sa retournée
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, et Chaim Goodman-Strauss 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 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 BruijnN. G. de Bruijn, Nederl. Akad. Wetensch. Indag. Math. 43, 39–52, 53–66 (1981). Algebraic theory of Penrose's nonperiodic tilings of the plane, I, II. 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é obtenuesVoir, par exemple, le compte-rendu de T. T. Q. Le dans .
Autres techniques, généralisations
Plusieurs autres principes de construction ont été découverts. Ainsi, 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 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 ;