Wikipédia

Pavage apériodique

type de pavage

En mathématiques, et plus particulièrement en géométrie, un pavage apériodique est un pavage non périodique ne contenant pas de sections périodiques arbitrairement grandes. Les pavages de Penrose[1],[2] sont les exemples les plus connus de pavages apériodiques, mais il existe plusieurs autres méthodes pour en construire.

Les tuiles de Penrose, un ensemble de tuiles ne permettant que des pavages non périodiques du plan, comme ci-dessous.
Un exemple de pavage de Penrose avec les tuiles apériodiques ci-dessus.

Les pavages apériodiques servent de modèles mathématiques pour les quasi-cristaux, des objets physiques découverts en 1982 par Dan Shechtman[3], mais dont la structure locale exacte est encore mal comprise.

Définitions modifier

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[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.

Historique modifier

 
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 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 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[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 »

Constructions modifier

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 modifier

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 modifier

Article connexe : L-Système.

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 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 modifier

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.

Autres techniques, généralisations modifier

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   n'est jamais égal à 1 si n et m sont des entiers non nuls[25]. Cette méthode fut ensuite adaptée par Goodman-Strauss pour obtenir un ensemble de tuiles « fortement apériodique » pavant le plan hyperbolique[26]. 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[27]. Block et Weinberger utilisèrent des méthodes homologiques pour construire des ensembles apériodiques pavant toutes les variétés « moyennables»[28]. Joshua Socolar obtint également des conditions forçant l'apériodicité, les conditions alternantes[29] ; 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 modifier

Article principal : Quasi-cristal.

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 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].

Questions de terminologie modifier

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.

Voir aussi modifier

Articles connexes modifier

Bibliogrpahie modifier

  • Philippe Pajot, « La tuile qu'on n'attendait plus », La Recherche, no 575,‎ , p. 71 (ISSN 0029-5671, lire en ligne, consulté le ).

Notes et références modifier

Notes modifier

  1. ↑ a et b (en) Martin Gardner, « Mathematical Games », Scientific American, vol. 236,‎ , p. 111–119.
  2. ↑ (en) Martin Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman & Co, (ISBN 0-7167-1987-8) ; reprise de l'article du Scientific American dans le premier chapitre du livre
  3. ↑ a et b (en) D. Schechtman, I. Blech, D. Gratias et J.W. Cahn, « Metallic Phase with long-range orientational order and no translational symmetry », Phys. Rev. Letters, vol. 53, no 20,‎ , p. 1951–1953 (lire en ligne).
  4. ↑ a b et c (en) M. Baake et Uwe Grimm, Aperiodic Order. Vol 1 : A Mathematical Invitation, Cambridge University Press,
  5. ↑ Emmanuel Jeandel et Michael Rao, dans « An aperiodic set of 11 Wang tiles ».
  6. ↑ (en) Robert Berger, « The undecidability of the domino problem », Memoirs of the American Mathematical Society, no 66,‎ , p. 1–72
  7. ↑ a et b Grünbaum 1986, section 11.1.
  8. ↑ (en) Raphael M. Robinson, « Undecidability and Nonperiodicity for Tilings of the Plane », Inventiones mathematicae, vol. 12, no 3,‎ , p. 177–209 (DOI 10.1007/BF01418780, Bibcode 1971InMat..12..177R)
  9. ↑ a et b Delahaye
  10. ↑ (en) J.C. Lagarias, « Meyer's concept of quasicrystal and quasiregular sets », Commun. Math. Phys., no 179,‎ , p. 356–376 (lire en ligne)
  11. ↑ (en) R.V. Moody, « Meyer sets and their duals », The Mathematics of Long Range Aperiodic Order, NATO ASI Series C, no 489,‎ , p. 403–441 (lire en ligne)
  12. ↑ (en) David Smith, Joseph Samuel Myers, Craig S. Kaplan et Chaim Goodman-Strauss, « An aperiodic monotile », sur cs.uwaterloo.ca, .
  13. ↑ David Smith, Joseph Samuel Myers, Craig S. Kaplan et Chaim Goodman-Strauss, « A chiral aperiodic monotile », Arxiv,‎ (DOI 10.48550/arXiv.2305.17743)
  14. ↑ a et b (en) Chaim Goodman-Strauss, « Matching rules and substitution tilings », Annals of Mathematics, vol. 147, no 1,‎ , p. 181–223 (lire en ligne)
  15. ↑ a et b (en) S. Mozes, « Tilings, substitution systems and dynamical systems generated by them », Journal d'Analyse Mathématique, vol. 53, no 1,‎ , p. 139–186 (DOI 10.1007/BF02793412)
  16. ↑ a et b (en) Chaim Goodman-Strauss, « A small aperiodic set of planar tiles », Journal européen de combinatoire, vol. 20, no 5,‎ , p. 375–384 (DOI 10.1006/eujc.1998.0281)
  17. ↑ Grünbaum 1986
  18. ↑ (en) Marjorie Senechal, Quasicrystals and geometry, Cambridge University Press, 1995 (corrected paperback edition, 1996), 286 p. (ISBN 978-0-521-57541-6 et 0-521-57541-9, lire en ligne)
  19. ↑ (en) J.E.S. Socolar, « Simple octagonal and dodecagonal quasicrystals », Phys. Rev. A, vol. 39,‎ , p. 10519–51 (DOI 10.1103/PhysRevB.39.10519, Bibcode 1989PhRvB..3910519S)
  20. ↑ (en) R. Penrose, « Remarks on Tiling: details of a 1 + ε + ε2-aperiodic set », The mathematics long range aperiodic order, NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci., vol. 489,‎ , p. 467–497
  21. ↑ (en) K.-P. Nischke et L. Danzer, « A construction of inflation rules based on n-fold symmetry », Disc. and Comp. Geom., vol. 15, no 2,‎ , p. 221–236 (DOI 10.1007/BF02717732)
  22. ↑ (en) Charles Radin, « The pinwheel tilings of the plane », Annals of Mathematics, Annals of Mathematics, vol. 139, no 3,‎ , p. 661–702 (JSTOR 2118575, lire en ligne)
  23. ↑ N. 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
  24. ↑ Voir, par exemple, le compte-rendu de T. T. Q. Le dans (en) T.T.Q. Le, « Local rules for quasiperiodic tilings », The mathematics long range aperiodic order, NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci., vol. 489,‎ , p. 331–366
  25. ↑ (en) Jarkko Kari, « A small aperiodic set of Wang tiles », Discrete Mathematics, vol. 160, nos 1–3,‎ , p. 259–264 (DOI 10.1016/0012-365X(95)00120-L)
  26. ↑ (en) Chaim Goodman-Strauss, « A strongly aperiodic set of tiles in the hyperbolic plane », Inventiones mathematicae, vol. 159, no 1,‎ , p. 119–132 (DOI 10.1007/s00222-004-0384-1, Bibcode 2004InMat.159..119G)
  27. ↑ (en) Shahar Mozes, « Aperiodic tilings », Inventiones mathematicae, vol. 128, no 3,‎ , p. 603–611 (DOI 10.1007/s002220050153, Bibcode 1997InMat.128..603M)
  28. ↑ (en) J. Block, « Aperiodic tilings, positive scalar curvature and amenability of spaces », Journal of the AMS, vol. 5, no 4,‎ , p. 907–918
  29. ↑ (en) Joshua Socolar, « Weak matching rules for quasicrystals », Comm. Math. Phys., vol. 129, no 3,‎ , p. 599–619 (DOI 10.1007/BF02097107, Bibcode 1990CMaPh.129..599S)
  30. ↑ « The Nobel Prize in Chemistry 2011 », Nobelprize.org (consulté le )
  31. ↑ a et b Paul J. Steinhardt, « A New Paradigm for the Structure of Quasicrystals » [archive du ] (consulté le )
  32. ↑ (en) W. S. Edwards and S. Fauve, Parametrically excited quasicrystalline surface waves, Phys. Rev. E 47, (1993) R788 – R791
  33. ↑ (en) Levy J-C. S., Mercier D., Stable quasicrystals, Acta Phys. Superficierum 8(2006)115

Bibliographie modifier

Liens externes modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Pavage_apériodique&oldid=213028691 ».