Апериодичная мозаика

Мозаика Пенроуза является примером апериодических мозаик. В любой мозаике, которая может быть получена из плиток Пенроуза, отсутствует трансляционная симметрия

Апериодичная мозаика — это непериодичное замощение с дополнительным свойством, что замощение не содержит бесконечно больших периодических кусков. Множество типов плиток (или протоплиток[англ.]) является набором непериодичных протоплиток[англ.], если копии этих плиток могут образовать только апериодичные мозаики. Мозаики Пенроуза[1][2] являются наиболее известными примерами апериодичных мозаик.

Апериодичные мозаики служат математическими моделями для квазикристаллов, физических тел, которые открыты в 1982 году Даном Шехтманом[3], получившим в 2011 году Нобелевскую премию[4]. Однако специфическая локальная структура этих материалов остаётся плохо понимаемой.

Некоторые методы построения апериодичных мозаик известны.

Определение и иллюстрация

Рассмотрим периодическую мозаику из единичных квадратов (она выглядит как бесконечная миллиметровка). Теперь разделим один квадрат на два прямоугольника. Мозаика, полученная таким образом, не является периодической — не существует сдвига, оставляющего эту мозаику неизменной. Ясно, что этот пример существенно менее интересен, чем мозаика Пенроуза. Чтобы исключить такие примеры, апериодическая мозаика определяется как не содержащая произвольно больших периодических частей.

Мозаика называется апериодической, если её оболочка содержит только апериодичные мозаики. Оболочка замощения содержит все переносы T+x замощения T вместе со всеми замощениями, которые могут быть приближены переносом T. Формально, это замыкание множества в локальной топологии[5]. В локальной топологии (соответствующей метрике) две плитки -близки, если они одинаковы в круге радиуса вокруг начала координат (возможно, после сдвига одной из плиток на расстояние, меньшее ).

Чтобы привести даже более простой пример, рассмотрим одномерное замощение T прямой, которое выглядит как …aaaaaabaaaaa… где a представляет интервал единичной длины, а b представляет интервал длины два. Тогда замощение T состоит из бесконечного числа копий a и одной копии b (скажем, с центром в точке 0). Теперь все переносы T являются мозаиками с одним b где-то и a в других местах. Последовательность мозаик, в которых b имеет центр в точках сходится (в локальной топологии) к периодической мозаике, состоящей только из плиток a. Таким образом, T не является апериодичной мозаикой, поскольку её замыкание содержит периодическую мозаику …aaaaaa….

Для многих «хороших» замощений (к примеру, подстановок плиток с конечным числом локальных узоров) выполняется утверждение: если мозаика не содержит периода и повторяющаяся (то есть каждая плитка встречается с одинаковой вероятностью по мере замощения) то она апериодична[6][5].

История

Первый раз вопрос о непериодичных мозаиках возник в 1961 году, когда логик Хао Ван попытался выяснить, может ли задача о домино быть разрешимой, то есть существует ли алгоритм определения, что заданный конечный набор протоплиток замощает плоскость. Ван нашёл алгоритмы перечисления наборов плиток, которые не могут быть уложены на плоскость, и наборов плиток, которые замощают плоскость периодично. Тем самым он показал, что такой алгоритм существует, если для любого конечного набора протоплиток, позволяющего замостить плоскость, также существует периодическое замощение.

В 1964 году Роберт Бергер[англ.] нашёл апериодический набор, тем самым показав, что задача замощения, фактически, неразрешима[7]. Это было первое такое множество, используемое в его доказательстве неразрешимости, и содержало 20 426 плиток Вана. Бергер позднее сократил число плиток до 104, а Ганс Лёйхли нашёл апериодический набор из 40 плиток Вана[8].

Даже меньший набор из шести апериодичных плиток (на базе плиток Вана) обнаружил Рафаэль Робинсон в 1971 году[9]. Роджер Пенроуз нашёл три других набора в 1973 и 1974 годах, сократив число необходимых плиток до двух, а Роберт Амманн[англ.] обнаружил несколько других наборов в 1977 году[8].

В 2010 году Соколар и Тейлор нашли набор из двух плиток одинакового вида (правильные шестиугольники), при этом одна плитка симметрична другой[10].

В 2023 году Д. Смит, Дж. С. Майерс, К. С. Каплан и Х. Гудман-Штраусс нашли семейство протоплиток, окончательно решающих задачу одной плитки, в том числе плитку простой 13-угольной формы[11].

Построения

Известно несколько способов построений апериодичных мозаик. Несколько построений основываются на бесконечных семействах апериодичных наборов плиток[12][13]. Эти найденные построения работают в большинстве случаев несколькими путями, главным образом с помощью некоторого вида апериодичной иерархической структуры. Не смотря на это, неразрешимость задачи домино обеспечивает, что должно быть бесконечно много различных построений и, фактически, существуют апериодичные наборы плиток, для которых нельзя доказать их апериодичность.

Апериодические мозаики Пенроуза могу быть образованы не только апериодическими наборами протоплиток, но и также с помощью подстановки и метода «вырежь-и-спроецируй». После обнаружения квазикристаллов апериодичные мозаики начинают интенсивно изучаться физиками и математиками. Метод «вырежь-и-спроецируй» Н. Г. де Брёйна для мозаик Пенроуза в конечном счёте превратился в часть теории множеств Мейера[14][15]. В настоящее время существует большое число литературы об апериодичных мозаиках[5].

Апериодичные иерархические замощения

К настоящему времени не существует формального определения, описывающего, когда мозаика имеет иерархическую структуру. Тем не менее, ясно, что подстановки плиток такую структуру имеет, так же, как и мозаики Бергера, Кнута, Лёйхли и Робинсона. Как и в случае термина «апериодичная мозаика», термин «апериодичная иерархическая мозаика» является удобным сокращением, означающим нечто вроде «набор плиток, допускающих только апериодичные мозаики с иерархической структурой».

Каждый из этих наборов плиток вынуждает любую мозаику из этих плиток иметь иерархическую структуру. (Во многих последующих примерах эта структура может быть описана как система подстановки плиток, как это описано ниже). Никакая мозаика из этих наборов плиток не может быть периодической просто потому, что никакой параллельный перенос не может оставить всю иерархическую структуру неизменной. Рассмотрим плитки Робинсона 1971 года:

Плитки Робинсона

Любое замощение этими плитками может только дать иерархию квадратных решёток — каждый оранжевый квадрат в углу большего квадрата, и так до бесконечности. Любой параллельный перенос должен быть меньше размера какого-либо квадрата, а потому не может оставить такую мозаику инвариантной.

Порция замощения плитками Робинсона

Робинсон доказал, что эти плитки должны образовывать структуру индуктивно. В результате плитки должны образовывать блоки, которые вместе представляют увеличенные варианты исходных плиток и так далее. Эта идея нахождения набора плиток, которые могут составлять только иерархические структуры, к настоящему времени используется для построения большинства известных апериодических наборов плиток.

Подстановки

Основные статьи: Подстановки плиток и L-система

Системы подстановки плиток дают богатый источник апериодичных мозаик. Говорят, что набор плиток, который вынуждает к возникновению структуры подстановки, является принуждённой структурой подстановки. Например, плитки «стул», показанные ниже, допускают подстановки и фрагмент подстановки плиток показан на рисунке. Эти подстановки плиток обязательно не являются периодическими, но плитка «стул» не является апериодичной — легко найти периодическое замощение этими плитками.

Система подстановки мозаики для плитки «стул».

Однако плитки, показанные ниже, вынуждает возникновение структуры подстановки плитки «стул», а потому являются апериодичными[16].

Плитки «Трилобит» и «Крест» принуждают структуру подстановки плитки «стул» — они могут образовывать только мозаики, в которых подстановка однозначно определена и, поэтому, мозаика является апериодичной.

Плитки Пенроуза, а вскоре после этого некоторые наборы плиток Аммана[17] были первыми примерами, основанными на вынужденных структурах подстановки плиток. Джошуа Соколар[18][19], Пенроуз, Роджер[20], Людвиг Данцер[21] и Чайм Гудман-Штраус[16] нашли несколько дополнительных наборов. Шахар Мозес дал первое общее построение, показав, что любое произведение одномерных систем подстановки может быть сделано вынужденным путём правил подстановки[13]. Чарльз Радин[англ.] нашёл вынуждающие правила для системы подстановки плиток для мозаики Конвея «Вертушка»[22]. В 1998 Гудман-Штраус показал, что локальные правила соединения могут быть найдены для любой структуры подстановки плиток, удовлетворяющей некоторым мягким условиям[12].

Метод вырежь-и-спроецируй

Мозаики без периодов могут быть получены путём проекции многомерных структур в пространство с меньшей размерностью и при некоторых обстоятельствах могут существовать плитки, которые препятствуют этим структурам иметь период, а потому мозаики будут апериодичными. Плитки Пенроуза являются первым и наиболее известным примером таких плиток, как было замечено в новаторской работе де Брёйна[23]. Существует незаконченное (алгебраическое) описание мозаик «вырежь и спроецируй», которые могут быть сделаны вынужденными путём правил соединения, хотя известно множество необходимых и достаточных условий[24].

Некоторые мозаики, полученные методом «вырежь и спроецируй». Секущие плоскости все параллельны плоскости, которая определяет мозаику Пенроуза (четвёртая мозаика в третьем ряду). Эти мозаики находятся все в различных локальных классах изоморфизмов, то есть они локально различимы.

Другие техники

Было найдено лишь несколько других видов построений. В частности, Яркко Кари дал апериодичный набор плиток Вана, основанный на произведениях на 2 или на 2/3 вещественных чисел, закодированных рядами плиток (кодировка связана с последовательностями Штурма[англ.], полученными как разности последовательных элементов последовательности Битти), с апериодичностью, главным образом связанной с фактом, что 2n/3m никогда не равно 1 для любого из положительных целых чисел n и m[25]. Этот метод позднее был приспособлен Гудманом-Штраусом для получения строго апериодичного набора плиток на гиперболической плоскости[26]. Шахар Мозес нашёл много альтернативных построений апериодичных наборов плиток, некоторые в более экзотичном окружении, например в полупростых группах Ли[27]. Блок и Вайнбергер использовали гомологические методы для построения апериодичных наборов плиток для всех неаменабельных многообразий[28]. Джошуа Соколар также дал другой способ вынуждения непереодичности в терминах альтернирующих условий[29]. Это в общем случае ведёт к много меньшим наборам плиток, чем набор, полученный из подстановок.

Физика апериодичных замощений

Основная статья: Квазикристалл

Апериодичные мозаики считались чисто математическими объектами до 1984 года, когда физик Дан Шехтман объявил об открытии разновидности алюминиево-марганцевого сплава, который давал чёткую дифрактограмму с недвусмысленной пятикратной симметрией[3]. Таким образом, эта субстанция должна быть кристаллической субстанцией с икосоэдральной симметрией. В 1975 году Роберт Амманн[англ.] уже расширил построение Пенроуза на трёхмерный икосоэдральный эквивалент. В таких случаях термин «замощение» принимает смысл «заполнение пространства». Фотонные устройства сейчас строятся как апериодичные последовательности различных слоёв, которые апериодичны в одном направлении и периодичны в двух других. Структура квазикристаллов Cd-Te оказалась состоящей из атомных слоёв, в которых атомы расположены в плоском апериодичном виде. Иногда энергетический минимум или максимум энтропии проявляется именно на таких апериодичных структурах. Стейнхардт показал, что сцеплённые десятиугольники Гуммельт позволяют применение принципа экстремума и тем самым дают связь между математическими непериодичными мозаиками и структурой квазикристаллов[30]. Наблюдалось явление, когда волны Фарадея[англ.] образовывали большие фрагменты апериодичных мозаик[31]. Физика этого открытия воскресила интерес к непропорциональным структурам и частотам и появилось предположение о связи апериодичных мозаик с явлением интерференции[32].

Путаница в терминологии

Термин апериодичный используется в математической литературе о мозаиках многими способами (а также в других областях математики, таких как динамические системы и теория графов, в совершенно другом смысле). Для мозаик термин апериодичный иногда используется как синоним непериодичности. Непериодичная мозаика — это мозаика, у которой нет нетривиального параллельного переноса. Иногда термин используется, явно или неявно, для описания мозаик, образованных апериодичным набором протоплиток. Часто термин туманно использовался для описания структур физических апериодических веществ, а именно, квазикристаллов, или чего-то непериодичного с некоторого рода глобальным порядком.

Использование слов «мозаика» или «замощение» также проблематично, даже при явном определении терминов. Например, нет единой мозаики Пенроуза — ромбы Пенроуза подразумевают бесконечное число мозаик (которые не различить локально). Обычно пытаются избежать применения этих терминов в технической литературе, но термины широко распространены как неформальные.

См. также

Примечания

  1. ↑ Gardner, 1977, с. 111–119.
  2. ↑ Gardner, 1988.
  3. ↑ 1 2 Schechtman, Blech, Gratias, Cahn, 1984, с. 1951–1953.
  4. ↑ Нобелевская премия по химии 2011.
  5. ↑ 1 2 3 Baake, Grimm, 2013.
  6. ↑ Может показаться, что здесь присутствует тавтология, однако отсутствие периода означает, что в данном варианте мозаики периода нет, а апериодичность мозаики означает, что нельзя с помощью тех же плиток создать периодическую мозаику.
  7. ↑ Berger, 1966, с. 1–72.
  8. ↑ 1 2 Grünbaum, Shephard, 1986, с. section 11.1.
  9. ↑ Robinson, 1971, с. 177–209.
  10. ↑ Socolar, Taylor, 2010.
  11. ↑ David Smith, Joseph Samuel Myers, Craig S. Kaplan, and Chaim Goodman-Strauss. An aperiodic monotile (2023). Дата обращения: 21 марта 2023. Архивировано 21 марта 2023 года.
  12. ↑ 1 2 Goodman-Strauss, 1998, с. 181–223.
  13. ↑ 1 2 Mozes, 1989, с. 39–186.
  14. ↑ Lagarias, 1996, с. 356–376.
  15. ↑ Moody, 1997, с. 403–441.
  16. ↑ 1 2 Goodman-Strauss, 1999, с. 375–384.
  17. ↑ Grünbaum, Shephard, 1986.
  18. ↑ Senechal, 1995.
  19. ↑ Socolar, 1989, с. 10519–51.
  20. ↑ Penrose, 1997, с. 467–497.
  21. ↑ Nischke, Danzer, 1996, с. 221–236.
  22. ↑ Radin, 1994, с. 661–702.
  23. ↑ de Bruijn, 1981, с. 39–52, 53–66.
  24. ↑ Le, 1997, с. 331–366.
  25. ↑ Kari, 1996, с. 259–264.
  26. ↑ Goodman-Strauss, 2005, с. 119–132.
  27. ↑ Mozes, 1997, с. 603–611.
  28. ↑ Block, Weinberger, 1992, с. 907–918.
  29. ↑ Socolar, 1990, с. 599–619.
  30. ↑ Steinhardt.
  31. ↑ Edwards, Fauve, 1993.
  32. ↑ Levy, Mercier, 2006, с. 115.

Литература

  • The Nobel Prize in Chemistry 2011. — Nobelprize.org.
  • Martin Gardner. Mathematical Games // Scientific American. — 1977. — Январь (т. 236). — С. 111–119.
  • Martin Gardner. Penrose Tiles to Trapdoor Ciphers. — W H Freeman & Co, 1988. — ISBN 0-7167-1987-8.
  • Schechtman D., Blech I., Gratias D., Cahn J.W. Metallic Phase with long-range orientational order and no translational symmetry // Physical Review Letters. — 1984. — Т. 53, вып. 20. — С. 1951–1953. — doi:10.1103/PhysRevLett.53.1951. — Bibcode: 1984PhRvL..53.1951S.
  • Baake M., Grimm U. Aperiodic Order. Vol 1: A Mathematical Invitation. — Cambridge University Press, 2013.
  • Robert Berger. The undecidability of the domino problem // Memoirs of the American Mathematical Society. — 1966. — Т. 66. — С. 1–72.
  • Raphael M. Robinson. Undecidability and Nonperiodicity for Tilings of the Plane // Inventiones Mathematicae. — 1971. — Т. 12, вып. 3. — С. 177–209. — doi:10.1007/BF01418780. — Bibcode: 1971InMat..12..177R.
  • Lagarias J.C. Meyer's concept of quasicrystal and quasiregular sets // Commun. Math. Phys.. — 1996. — Т. 179, вып. 2. — С. 356–376.
  • Moody R.V. Meyer sets and their duals // The Mathematics of Long Range Aperiodic Order, NATO ASI Series C. — 1997. — Т. 489. — С. 403–441.
  • Chaim Goodman-Strauss. Matching rules and substitution tilings // Annals of Mathematics. — Annals of Mathematics, 1998. — Т. 147, вып. 1. — С. 181–223. — doi:10.2307/120988. — JSTOR 120988.
  • Chaim Goodman-Strauss. A small aperiodic set of planar tiles // European Journal of Combinatorics. — 1999. — Т. 20, вып. 5. — С. 375–384. — doi:10.1006/eujc.1998.0281.
  • Branko Grünbaum, Geoffrey C. Shephard. Tilings and Patterns. — W.H. Freeman & Company, 1986. — ISBN 0-7167-1194-X.
  • Marjorie Senechal. Quasicrystals and geometry. — Cambridge University Press, 1995. — ISBN 0-521-57541-9.
  • Socolar J.E.S. Simple octagonal and dodecagonal quasicrystals // Phys. Rev. B. — 1989. — Т. 39. — С. 10519–51. — doi:10.1103/PhysRevB.39.10519. — Bibcode: 1989PhRvB..3910519S.
  • Penrose R. 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.. — 1997. — Т. 489. — С. 467–497.
  • Nischke K.-P., Danzer L. A construction of inflation rules based on n-fold symmetry // Disc. and Comp. Geom.. — 1996. — Т. 15, вып. 2. — С. 221–236. — doi:10.1007/BF02717732.
  • Mozes S. Tilings, substitution systems and dynamical systems generated by them // Journal d'Analyse Mathématique. — 1989. — Т. 53, вып. 1. — С. 139–186. — doi:10.1007/BF02793412.
  • Charles Radin. The pinwheel tilings of the plane // Annals of Mathematics. — Annals of Mathematics, 1994. — Т. 139, вып. 3. — С. 661–702. — doi:10.2307/2118575. — JSTOR 2118575.
  • de Bruijn N. G. Algebraic theory of Penrose's nonperiodic tilings of the plane, I, II // Nederl. Akad. Wetensch. Indag. Math.. — 1981. — Т. 43. — С. 39–52, 53–66.
  • Le T.T.Q. Local rules for quasiperiodic tilings // The mathematics long range aperiodic order, NATO Adv. Sci. Inst. Ser. C. Math. Phys. Sci.. — 1997. — Т. 489. — С. 331–366. — doi:10.1007/978-94-015-8784-6_13.
  • Jarkko Kari. A small aperiodic set of Wang tiles // Discrete Mathematics. — 1996. — Т. 160, вып. 1–3. — С. 259–264. — doi:10.1016/0012-365X(95)00120-L.
  • Chaim Goodman-Strauss. A strongly aperiodic set of tiles in the hyperbolic plane // Inventiones Mathematicae. — 2005. — Т. 159, вып. 1. — С. 119–132. — doi:10.1007/s00222-004-0384-1. — Bibcode: 2004InMat.159..119G.
  • Shahar Mozes. Aperiodic tilings // Inventiones Mathematicae. — 1997. — Т. 128, вып. 3. — С. 603–611. — doi:10.1007/s002220050153. — Bibcode: 1997InMat.128..603M.
  • Block J., Weinberger S. Aperiodic tilings, positive scalar curvature and amenability of spaces // Journal of the AMS. — 1992. — Т. 5, вып. 4. — С. 907–918. — doi:10.1090/s0894-0347-1992-1145337-x.
  • Joshua Socolar. Weak matching rules for quasicrystals // Comm. Math. Phys.. — 1990. — Т. 129, вып. 3. — С. 599–619. — doi:10.1007/BF02097107. — Bibcode: 1990CMaPh.129..599S.
  • Paul J. Steinhardt. A New Paradigm for the Structure of Quasicrystals. Архивировано 23 февраля 2007 года.
  • Edwards W. S., Fauve S. Parametrically excited quasicrystalline surface waves // Physical Review E. — 1993. — Т. 47, вып. 2. — С. R788 – R791.
  • Levy J-C. S., Mercier D. Stable quasicrystals // Acta Phys. Superficierum. — 2006. — Т. 8. — С. 115.
  • Joshua E. S. Socolar1, Joan M. Taylor2. An aperiodic hexagonal tile // Journal of Combinatorial Theory Series A. — 2010. — arXiv:1003.4279v1.

Ссылки