Pavage apériodique

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 ${\displaystyle 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 ${\displaystyle \{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 ${\displaystyle <\varepsilon }$ si elles coïncident dans une boule de centre l'origine et de rayon ${\displaystyle 1/\varepsilon }$, éventuellement après une translation de norme ${\displaystyle <\varepsilon }$. Avec ces définitions, un pavage est apériodique si son enveloppe ne contient que des pavages non périodiques[4]. 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[4].

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.

Pavage de Wang minimal, avec onze tuiles de Wang en quatre couleurs, décrit par Jeandel et Rao en 2015[5].

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[6]. 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)[7].

En 1971, un ensemble de 6 tuiles (dérivées de tuiles de Wang) fut construit par Raphael Robinson[8]. 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[1] ; Robert Ammann (en) construisit plusieurs nouveaux ensembles en 1977[7]. La question de l'existence d'une tuile qui serait apériodique à elle seule reste ouverte, bien que plusieurs tuiles répondant presque à cette condition aient été découvertes à partir de 1996[9].

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)[10] - [11]. En 2013, une vaste littérature s'était développée autour des pavages apériodiques[4].

Pavage apériodique à l'aide d'une tuile unique et de sa retournée

Pavage animé.

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 mot 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[9]; année durant laquelle une telle tuile semble avoir été découverte[12]. Toutefois un recouvrement apériodique du plan à l'aide de cette tuile nécessite l'utilisation de la tuile et de sa retournée (par une symétrie axiale).

Depuis, les mêmes auteurs[13] ont proposé un pavage avec une seule tuile sans retournement ; la tuile précédente, par sa forme, est appelée le « chapeau d'Einstein », la nouvelle est le « spectre »

On connait plusieurs constructions de pavages apériodiques, basées parfois sur des familles infinies d'ensembles de tuiles apériodiques[14] - [15]. 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 :

Les tuiles de Robinson

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.

Fragment de pavage par les tuiles de Robinson

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.

Le pavage en chaises.

En revanche, les tuiles ci-dessous (dites « crabes et trilobites ») forcent la structure en chaise, et sont donc apériodiques[16].

Les tuiles « crabes et trilobites » ne permettent que des pavages où apparait la structure de substitution en chaises.

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 (en) découvrit plusieurs ensembles de tuiles ayant la même propriété[17]. Joshua Socolar[18] - [19], Roger Penrose[20], Ludwig Danzer[21] et Chaim Goodman-Strauss [16] 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[15]. Charles Radin construisit des règles (et des tuiles) forçant le pavage en moulin à vent[22]. 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[14].

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[23]. 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[24].

Quelques pavages obtenus par la méthode de coupe et projection. Les plans de coupe sont tous parallèles à celui définissant le pavage de Penrose (le quatrième pavage de la troisième ligne). Ces pavages peuvent tous être distingués localement les uns des autres.

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[3] – 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[30]. En 1975, Robert Ammann (en) 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[31], 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[31]. On a observé que des ondes de Faraday pouvaient former de larges plages de motifs apériodiques[32] ; 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[33].

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.

• Pavage de Girih (en)
• Quasi-cristal
• Zellige

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Aperiodic tiling » (voir la liste des auteurs).

• Pavages, sur le site Images des mathématiques du CNRS
• (en) The Geometry Junkyard
• (en) Aperiodic Tilings
• (it) Film (en italien) sur les pavages de Penrose