Қайталанбайтын жазылымдар және апериодты мозаикалар

Кіріспе

Кез келген масштабта қайталамасыз жазық мозаиканың түрі.

Апериодты мозаика – бұл периодты емес мозаика, оның үстіне ол кез келген үлкен периодты аймақтарды немесе бөліктерді қамтымайды. Плитка түрлерінің жиынтығы (немесе протоплиткалар) егер осы плиткалардың көшірмелері тек периодты емес мозаикаларды құраса, апериодты болып саналады. Пенроуз мозаикалары – апериодты мозаикалардың жақсы белгілі мысалы. 2023 жылдың наурыз айында Дэвид Смит, Джозеф Сэмюэл Майерс, Крейг С. Каплан және Хайм Гудман Штраус төрт зерттеуші Дэвид Смит ашқан плитканың апериодты моноплитка екенін дәлелдеді, яғни Эйнштейн мәселесінің шешімі – кез келген пішіндегі апериодты плитканың болуын іздейтін мәселе. 2023 жылдың мамырында осы авторлар ұқсас, бірақ күштірек шектеулері бар хиральді апериодты моноплитканы жариялады. Апериодты мозаикалар квазикристалдар үшін математикалық модельдер болып табылады, олар 1982 жылы Дэн Шехтман ашқан физикалық қатты денелер, ол кейіннен 2011 жылы Нобель сыйлығын жеңіп алды. Дегенмен, осы материалдардың нақты жергілікті құрылымы әлі де толыққанды түсініксіз. Апериодты мозаикаларды құрудың бірнеше әдісі белгілі.

Анықтама және мысал

Бірлік квадраттар бойынша периодты плиткалауды қарастырайық (бұл шексіз граф қағазы сияқты). Енді бір шаршыны екі тіктөртбұрышқа бөліңіз. Осылайша алынған плиткалау периодты емес: бұл плиткалауды өзгеріссіз қалдыратын нөлдік емес ығысқан жоқ. Бірақ бұл мысал Пэнроуз плиткалауынан әлдеқайда аз қызықты. Мұндай жалықтыратын мысалдарды жоққа шығару үшін, апериодты плиткалауды кез келген үлкен периодты бөліктері жоқ плиткалау деп анықтайды. Плиткалау апериодты деп аталады, егер оның қабығы тек периодты емес плиткалауларды қамтыса. Плиткалаудың қабығында T-ның барлық трансляциялары T + x және T трансляцияларымен жуықтауға болатын барлық плиткалаулар бар. Формальды түрде, бұл жергілікті топологиядағы жиынның жабылуы. Жергілікті топологияда (сәйкес метрикада) екі плитка жақын болады, егер олар бастапқы нүктеден радиусы бар шар ішінде сәйкес келсе (мүмкін, плиткалаулардың біреуін 5-тен кішкентай шамаға ығыстырғаннан кейін). Жоғарыдағыдан қарапайым мысал келтірейік: a ұзындығы бір интервалды, b ұзындығы екі интервалды білдіретін түзудің бір өлшемді T плиткалауын қарастырайық. Осылайша, T плиткалауы a-ның шексіз көп көшірмесінен және b-нің бір көшірмесінен тұрады (орталығы 0 дейік). Енді T-ның барлық трансляциялары бір жерде бір b және қалғандары a болады. b ортасы орналасқан плиткалаулар тізбегі жергілікті топологияда тек a-дан тұратын периодты плиткалауға жақындайды. Осылайша T апериодты плиткалау емес, өйткені оның қабығында периодты плиткалау бар. Жақсы мінез-құлықты плиткалаулар үшін (мысалы, шектеулі жергілікті үлгілері бар алмастыру плиткалаулары): егер плиткалау периодты емес және қайталанатын болса (яғни әрбір бөлік плиткалаудың барлық жерінде біркелкі тығыздықпен кездеседі), онда ол апериодты. Бергердің шешілмейтіндігін дәлелдеуінде қолданған алғашқы жиын 20 426 Ванг плиткасын қажет етті. Бергер кейіннен жиынын 104-ке дейін қысқартты, ал Ханс Лёучли кейіннен 40 Ванг плиткасын қажет ететін апериодты жиынды тапты. 1971 жылы Рафаэль М. Робинсон алты апериодты плиткадан тұратын кішірек жиынды (Ванг плиткаларына негізделген) тапты. Роджер Пенроуз 1973 және 1974 жылдары тағы үш жиынды тапты, бұл қажетті плиткалар санын екіге дейін азайтты, ал Роберт Амман 1977 жылы бірнеше жаңа жиындарды тапты. Бүгінде апериодты плиткалаулар туралы көптеген әдебиеттер бар.

Consider a periodic tiling by unit squares (it looks like infinite graph paper). Now cut one square into two rectangles. The tiling obtained in this way is non periodic: there is no non zero shift that leaves this tiling fixed. But clearly this example is much less interesting than the Penrose tiling. In order to rule out such boring examples, one defines an aperiodic tiling to be one that does not contain arbitrarily large periodic parts. A tiling is called aperiodic if its hull contains only non periodic tilings. The hull of a tiling contains all translates T + x of T, together with all tilings that can be approximated by translates of T. Formally this is the closure of the set in the local topology. In the local topology (resp. the corresponding metric) two tilings are close if they agree in a ball of radius around the origin (possibly after shifting one of the tilings by an amount less than ). To give an even simpler example than above, consider a one dimensional tiling T of the line that looks like where a represents an interval of length one, b represents an interval of length two. Thus the tiling T consists of infinitely many copies of a and one copy of b (with centre 0, say). Now all translates of T are the tilings with one b somewhere and as else. The sequence of tilings where b is centred at converges – in the local topology – to the periodic tiling consisting of as only. Thus T is not an aperiodic tiling, since its hull contains the periodic tiling

For well behaved tilings (e. g. substitution tilings with finitely many local patterns) holds: if a tiling is non periodic and repetitive (i. e. each patch occurs in a uniformly dense way throughout the tiling), then it is aperiodic. This first such set, used by Berger in his proof of undecidability, required 20,426 Wang tiles. Berger later reduced his set to 104, and Hans Läuchli subsequently found an aperiodic set requiring only 40 Wang tiles. A smaller set, of six aperiodic tiles (based on Wang tiles), was discovered by Raphael M. Robinson in 1971. Roger Penrose discovered three more sets in 1973 and 1974, reducing the number of tiles needed to two, and Robert Ammann discovered several new sets in 1977. Today there is a large amount of literature on aperiodic tilings.

Келесіге сәйкес келетін кезеңдік емес иерархиялық плиткалар

Плитканың конгруэнтті көшірмелері үшін прототильдердің барлық Евклид жазықтығын жаппай жабу қажет, өзара жабыспау (шекаралардан басқа) және жабылмаған бөліктерді қалдырмау шарттарымен. Сондықтан плитканы құрайтын плиткалардың шекаралары геометриялық тұрғыдан сәйкес келуі керек. Бұл барлық плиткаларға – периодты және апериодты плиткаларға – қатысты жалпы ереже. Кейде осы геометриялық сәйкестік шарты плиткалар жиынтығын апериодты болуға мәжбүрлеу үшін жеткілікті, мысалы, төменде талқыланатын Робинсон плиткалары үшін. Кейде қосымша сәйкестік ережелері қажет болады. Бұл әдетте шекаралар арқылы бірнеше плиткаға сәйкес келетін түстер немесе белгілерді қамтиды. Ван плиткалары көбінесе мұндай қосымша ережелерді қажет етеді. Кейбір жағдайларда, прототильдердің шекараларын өзгерту арқылы сәйкестік ережелерін геометриялық сәйкестік шарттарымен толығымен алмастыруға болады. Пенроуз плиткасы (P1) бастапқыда төрт прототильден және бірнеше сәйкестік ережелерінен тұрады. Төрт плитканың бірі бесбұрыш. Бұл бесбұрыш прототилін шекарасында қосымша шығыңқылықтары мен ойыстары бар үш түрлі бесбұрышты пішінмен алмастыруға болады, нәтижесінде үш түрлі плитка пайда болады. Қалыптасқан шекаралары бар қалған үш прототильмен бірге, алты прототиль жиынтығы түпнұсқа төрт плитка сияқты бірдей апериодты плиткаларды жасайды, бірақ алты плитка үшін қосымша сәйкестік ережелері қажет емес, геометриялық сәйкестік шарты жеткілікті. Сондай-ақ, Робинсонның төмендегі прототильдері құрылымды визуалды тануды жеңілдету үшін белгілермен жабдықталған, бірақ бұл белгілер геометриялық шекаралар арқылы орнатылған сәйкестік ережелерін күшейтпейді. Бүгінгі күні плитканың иерархиялық құрылымы бар кезде сипатталатын ресми анықтама жоқ; алайда, Бергер, Кнут, Лёхли, Робинсон және Амманның плиткалары сияқты, алмастыру плиткаларының да осы қасиетке ие екені анық. "Апериодты плитка" термині сияқты, "апериодты иерархиялық плитка" термині де ыңғайлы қысқарту, "иерархиялық құрылыммен тек апериодты плиткаларды ғана қабылдайтын плиткалар жиынтығы" дегенді білдіреді. Апериодты плиткалар үшін, қосымша сәйкестік ережелері болсын болмасын, сәйкестік шарттары плиткаларға белгілі бір иерархиялық құрылымды жүктеуге мәжбүрлейді, бұл өз кезегінде периодтық құрылымдарды мүмкін емес етеді. Бұл плиткалар жиынтығының әрқайсысы, олармен жасалған кез келген плиткада, нақты бір иерархиялық құрылымды жүзеге асырады. (Көптеген кейінгі мысалдарда бұл құрылымды алмастыру плиткасы жүйесі ретінде сипаттауға болады; бұл төменде сипатталған). Мұндай плиткалар жиынтығымен жасалған ешбір плитка периодты бола алмайды, себебі ешбір аударма бүкіл иерархиялық құрылымды өзгермейтін күйде қалдыра алмайды. Робинсонның 1971 жылғы плиткаларын қарастырайық: осы плиткалардың кез келген плиткасы тек шаршы торлардың иерархиясын ғана көрсете алады: кез келген қызғылт түсті шаршының ортасы сонымен қатар үлкен қызғылт түсті шаршының бұрышы болып табылады, және т.б. Кез келген аударма шаршының бір өлшемінен кіші болуы керек, сондықтан мұндай плитканы өзгермейтін күйде қалдыра алмайды. Робинсон бұл плиткалар осы құрылымды индуктивті түрде құрауы керектігін дәлелдейді; іс жүзінде плиткалар өздері түпнұсқа плиткалардың үлкен нұсқалары ретінде бірігіп тұратын блоктар құрауы керек. Бұл идея – тек иерархиялық құрылымдарды қабылдай алатын плиткалар жиынтығын табу – бүгінгі күнге дейін ең танымал апериодты плиткалар жиынтығын құруда қолданылған. Алайда, осы жолмен жасалған плиткалар бірегей емес, тіпті Евклид тобының изометрияларына дейін емес, мысалы, аудармалар мен айналымдар. Робинсон плиткаларынан жасалған жазықтықтың толық плиткасында төрт қолға дейін шексізке дейін созылатын ақаулар (дәліздер деп те аталады) болуы мүмкін немесе болмауы мүмкін, сонымен қатар төрт әріптен тұратын Σ алфавиті үшін Σ-ден шексіз сөздерді кодтауға мүмкіндік беретін қосымша таңдаулар бар. Қорыта айтқанда, Эвклидтік изометриялармен байланысты емес, көптеген түрлі плиткалар бар, олардың барлығы міндетті түрде апериодты, және Робинсон плиткаларынан туындайды.

For a tiling congruent copies of the prototiles need to pave all of the Euclidean plane without overlaps (except at boundaries) and without leaving uncovered pieces. Therefore the boundaries of the tiles forming a tiling need to match geometrically. This is generally true for all tilings, aperiodic and periodic ones. Sometimes these geometric matching condition is enough to force a tile set to be aperiodic, this is e. g. the case for Robinsion's tilings discussed below. Sometimes additional matching rules are required to hold. These usually involve colors or markings that have to match over several tiles across boundaries. Wang tiles usually require such additional rules. In some cases it has been possible to replace matching rules by geometric matching conditions altogether by modifying the prototiles at their boundary. The
Penrose tiling (P1) originally consists of four prototiles together with some matching rules. One of the four tiles is a pentagon. One can replace this pentagon prototile by three distinct pentagonal shapes that have additional protrusions and indentations at the boundary making three distinct tiles. Together with the three other prototiles with suitably adapted boundaries one gets a set of six prototiles that essentially create the same aperiodic tilings as the original four tiles, but for the six tiles no additional matching rules are necessary, the geometric matching condition suffice. Also note that Robinsion's protiles below come equipped with markings to make it easier to visually recognize the structure, but these markings do not put more matching rules on the tiles as are already in place through the geometric boundaries. To date, there is not a formal definition describing when a tiling has a hierarchical structure; nonetheless, it is clear that substitution tilings have them, as do the tilings of Berger, Knuth, Läuchli, Robinson and Ammann. As with the term "aperiodic tiling" itself, the term "aperiodic hierarchical tiling" is a convenient shorthand, meaning something along the lines of "a set of tiles admitting only non periodic tilings with a hierarchical structure". For aperiodic tilings, whether additional matching rules are involved or not, the matching conditions forces some hierarchical structure on the tilings that in turn make period structures impossible. Each of these sets of tiles, in any tiling they admit, forces a particular hierarchical structure. (In many later examples, this structure can be described as a substitution tiling system; this is described below). No tiling admitted by such a set of tiles can be periodic, simply because no single translation can leave the entire hierarchical structure invariant. Consider Robinson's 1971 tiles:

Any tiling by these tiles can only exhibit a hierarchy of square lattices: the centre of any orange square is also a corner of a larger orange square, ad infinitum. Any translation must be smaller than some size of square, and so cannot leave any such tiling invariant. Robinson proves these tiles must form this structure inductively; in effect, the tiles must form blocks which themselves fit together as larger versions of the original tiles, and so on. This idea – of finding sets of tiles that can only admit hierarchical structures – has been used in the construction of most known aperiodic sets of tiles to date. However, the tiling produced in this way is not unique, not even up to isometries of the Euclidean group, e. g. translations and rotations. A complete tiling of the plane constructed from Robinsion's tiles may or may not have faults (also called corridors) going off to infinity in up to four arms and there are additional choices that allow for the encoding of infinite words from Σω for an alphabet Σ of up to four letters. In summary there are uncountably many different tilings unrelated by Euclidean isometries, all of them necessarily nonperiodic, that can arise from the Robinsion's tiles.

Ауыстырулар

Тасымалдау плиткалау жүйелері апериодикалық плиткалаудың мол көзін ұсынады. Ауыстыру құрылымын пайда етуге мәжбүрлейтін плиткалар жиынтығы ауыстыру құрылымын күшейтеді. Мысалы, төменде көрсетілген кресло плиткалары ауыстыруды қабылдайды, ал ауыстыру плиткалауының бір бөлігі оң жақта көрсетілген. Бұл ауыстыру плиткалаулары міндетті түрде периодты емес, дәл сол тәсілмен жоғарыда сипатталғандай, бірақ кресло плиткасының өзі апериодты емес – геометриялық сәйкес келу шарттарын қанағаттандыратын белгіленбеген кресло плиткалары арқылы периодты плиткалауларды табу оңай. Дегенмен, төменде көрсетілген плиткалар кресло ауыстыру құрылымын пайда болуға мәжбүрлейді, сондықтан олар өздері апериодты. Пенроуз плиткалары, одан кейін Амманның бірнеше түрлі плиткалар жиынтығы, ауыстыру плиткалау құрылымын нақты түрде пайда етуге мәжбүрлеуге негізделген алғашқы мысал болды. Джошуа Соколар, Роджер Пенроуз, Людвиг Данцер және Хайм Гудман Штраус Чарльз Радин Конвейдің шүмекті ауыстыру плиткалау жүйесін жүзеге асыратын ережелерді тапты. 1998 жылы Гудман Штраус, кейбір жұмсақ шарттар сақталғанда, кез келген ауыстыру плиткалау құрылымын күштеу үшін жергілікті сәйкестендіру ережелерін табуға болатынын көрсетті. Кесу және жобалау плиткалауларының толық (алгебралық) сипаттамасы әлі жоқ, бірақ көптеген қажетті немесе жеткілікті шарттар белгілі.

Басқа әдістер

Тек бірнеше түрлі конструкциялар ғана табылған. Ерекше айта келерлік жайт, Жарко Кари нақты сандарды плиткалардың қатарымен кодтау арқылы 2 немесе 2/3-ке көбейтуге негізделген Ван плиткаларының апериодты жиынтығын ұсынды (кодтау Битти тізбегінің тізбектес элементтерінің айырмасы ретінде құрылған Штурм тізбегімен байланысты), апериодтылықтың негізгі себебі 2n/3m ешқандай оң бүтін n және m үшін 1-ге тең болмайды. Бұл әдіс кейін Гудман Штраус тарапынан гиперболалық жазықтықтағы плиткалардың күшті апериодты жиынтығын алу үшін бейімделді. Шахар Мозес апериодты плиткалар жиынтығының көптеген басқа конструкцияларын тапты, олардың кейбіреулері экзотикалық жағдайларда, мысалы, жартылай қарапайым Ли тобында кездеседі. Блок пен Вайнбергер гомологиялық әдістерді қолданып, барлық аманативті емес көпқырлылар үшін апериодты плиткалар жиынтығын құрды. Джошуа Соколар да апериодтылықты қамтамасыз етудің тағы бір жолын, яғни алмастыру шартын ұсынды. Бұл, әдетте, алмастыру арқылы алынғандарға қарағанда әлдеқайда кіші плиткалар жиынтығына әкеледі.

Физика

Апериодты плиткалар 1984 жылға дейін математикалық артефакттар ретінде қарастырылды, бірақ физик Дэн Шехтман алюминий-марганец қорытпасының жаңа фазасын ашқаннан кейін жағдай өзгерді. Бұл фаза бес есе симметриясы бар анық дифрактограмманы көрсетті. Фарадей толқындары апериодты үлгілердің кең аумақтарын құрауы байқалды. Осы жаңалық физикада өлшемсіз құрылымдар мен жиіліктерге деген қызығушылықты қайта жақтандырып, апериодты плиткаларды интерференция құбылыстарымен байланыстыруға мүмкіндік берді.

Терминологияға қатысты түсініспеушіліктер

Апериодтық термин математикалық әдебиетте (және динамикалық жүйелер немесе граф теориясы сияқты басқа математикалық салаларда да, мүлдем басқа мағыналармен) түрліше қолданылған. Тильдерге қатысты, апериодтық термин кейде периодтық емес терминмен мағынасы бірдей ретінде қолданылған. Периодтық емес тиль – бұл кез келген тривиалды емес трансляциямен өзгермейтін тиль. Кейде бұл термин апериодты прототильдер жиынымен жасалған тильді жасырын немесе ашық түрде сипаттаған. Көптеген жағдайларда апериодтық термин қарастырылып отырған құрылымдарды сипаттау үшін, яғни физикалық апериодты қатты денелерді, атап айтқанда квазикристалдарды, немесе қандай да бір жаһандық ретпен емес нәрсені білдіру үшін дұрыс емес қолданылған. "Тиль" сөзін қолдану да қиын, оның анықтамасы түсінікті болғанымен. Мысалы, бір ғана Пенроуз тилі жоқ: Пенроуз ромбы шексіз көп тильдерді қабылдайды (оларды жергілікті түрде ажырату мүмкін емес). Ортақ шешім – терминдерді техникалық жазуда мұқият қолдануға тырысу, бірақ бейресми терминдердің кең қолданылуын мойындау.