« Pavage apériodique » : différence entre les versions

Un article de Wikipédia, l'encyclopédie libre.
Modification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
Dfeldmann (discuter | contributions)
97 660 modifications
(Aucune différence)

Version du 2 février 2014 à 12:06

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.

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

On appelle pavage apériodique un pavage (non-périodique) ne contenant pas de parties périodiques arbitrairement grandes (pour éviter des contre-exemples tel qu'un pavage périodique déformé en un nombre infini d'endroits isolés).

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 locale, pour laquelle deux tuiles sont de distance si elles coïncident dans une boule de centre l'origine et de rayon 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 quandR 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

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[5]. Ce premier exemple utilisait 20426 tuiles (appelées par la suite des tuiles de Wang (en)) ; Berger lui-même obtient ensuite un ensemble de 104 tuiles, qui fut ensuite ramené à 40 tuiles par Hans Läuchli (en)[6].

En 1971, un ensemble de 6 tuiles (dérivées de tuiles de Wang) fut construit par Raphael M. Robinson (en)[7]. 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 Ammannconstruisit plusieurs nouveaux ensembles en 1977[6].

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. deBruijn) devint un cas particulier de la théorie des ensembles de Meyer (en)[8],[9]. En 2013, une vaste littérature s'est développée autour des pavages apériodiques[4].

Constructions

On connait plusieurs constructions de pavages apériodiques, basées parfois sur des familles infinies d'ensembles de tuiles apériodiques[10],[11]. 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 (en). 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 dont 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

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

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é[13]. Joshua Socolar[14],[15], Roger Penrose[16], Ludwig Danzer[17] et Chaim Goodman-Strauss [12] 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[11]. Charles Radin construisit ds règles (et des tuiles) forçant le pavage en moulin à vent[18]. 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[10].

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 séminal de de Bruijn[19]. 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[20].

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

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 multiplications 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[21]. Cette méthode fut ensuite adaptée par Goodman-Strauss oiyr obtenir un ensemble de tuiles « fortement apériodique » pavant le plan hyperbolique[22]. 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[23]. Block et Weinberger utilisèrent des méthodes homologiques pour construire des ensembles apériodiques pavant toutes les variétés « moyennables»[24]. Joshua Socolar obtint également des conditions forçant l'apériodicité, les conditions alternantes[25] ; 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

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[26]. 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[27], 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[27]. On a observé que des ondes de Faraday pouvaient former de larges plages de motifs apériodiques[28] ; 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[29].

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 non-triviale 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 tuiles de Penrose peuvent être assemblées 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

Références

  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)
  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 (DOI 10.1103/PhysRevLett.53.1951, Bibcode 1984PhRvL..53.1951S)
  4. ↑ a b et c (en) M. Baake et Uwe Grimm, Aperiodic Order. Vol 1: A Mathematical Invitation, Cambridge University Press,
  5. ↑ (en) Robert Berger, « The undecidability of the domino problem », Memoirs of the American Mathematical Society, no 66,‎ , p. 1–72
  6. ↑ a et b Grünbaum and Shephard, section 11.1.
  7. ↑ (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)
  8. ↑ (en) J.C. Lagarias, « Meyer's concept of quasicrystal and quasiregular sets », Commun. Math. Phys., no 179, {{Article}} : paramètre « date » manquant, p. 356–376
  9. ↑ (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
  10. ↑ a et b (en) Chaim Goodman-Strauss, « Matching rules and substitution tilings », Annals of Mathematics, Annals of Mathematics, vol. 147, no 1,‎ , p. 181–223 (DOI 10.2307/120988, JSTOR 120988, lire en ligne)
  11. ↑ 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)
  12. ↑ a et b (en) Chaim Goodman-Strauss, « A small aperiodic set of planar tiles », European Journal of Combinatorics, vol. 20, no 5,‎ , p. 375–384 (DOI 10.1006/eujc.1998.0281)
  13. ↑ (en) Branko Grünbaum, Geoffrey C. Shephard, Tilings and Patterns, W.H. Freeman & Company, (ISBN 0-7167-1194-X)
  14. ↑ (en) Marjorie Senechal, Quasicrystals and geometry, Cambridge University Press, 1995 (corrected paperback edition, 1996) (ISBN 0-521-57541-9)
  15. ↑ (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)
  16. ↑ (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
  17. ↑ (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)
  18. ↑ (en) Charles Radin, « The pinwheel tilings of the plane », Annals of Mathematics, Annals of Mathematics, vol. 139, no 3,‎ , p. 661–702 (DOI 10.2307/2118575, JSTOR 2118575)
  19. ↑ 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
  20. ↑ 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
  21. ↑ (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)
  22. ↑ (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)
  23. ↑ (en) Shahar Mozes, « Aperiodic tilings », Inventiones Mathematicae, vol. 128, no 3,‎ , p. 603–611 (DOI 10.1007/s002220050153, Bibcode 1997InMat.128..603M)
  24. ↑ (en) J. Block, « Aperiodic tilings, positive scalar curvature and amenability of spaces », Journal of the AMS, vol. 5, no 4,‎ , p. 907–918
  25. ↑ (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)
  26. ↑ « The Nobel Prize in Chemistry 2011 », Nobelprize.org (consulté le )
  27. ↑ a et b Paul J. Steinhardt, « A New Paradigm for the Structure of Quasicrystals » [archive du ] (consulté le )
  28. ↑ (en) W. S. Edwards and S. Fauve, Parametrically excited quasicrystalline surface waves, Phys. Rev. E 47, (1993) R788 – R791
  29. ↑ (en) Levy J-C. S., Mercier D., Stable quasicrystals, Acta Phys. Superficierum 8(2006)115

Liens externes


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