Апериодические замощения и алгебраические конструкции и computer-science, занятие 1

Построение разного рода алгебраических «монстров» по сути явлется задачей computer science (и находит здесь свою мотивировку). Слово из порождающих букв алгебраической системы интерпретируется как совокупность конечных автоматов, обменивающихся между собой сигналами. Так удается построить, например, полугруппу, заданную конечным набором соотношений, такую, что количество элементов записанными словами длины не меньше $n$ растет как $n^100+n$.
Этим интересна и важна проблема Шеврина-Сапира о существовании бесконечной полугруппы, заданной конечным набором определяющих соотношений степень каждого элемента которой равна нулю. Мы программируем солдат и законы локального взаимодействия между ними. Наш злейший враг задает внутренние состояния солдат в шеренге. Надо обеспечить осмысленность поведения в любом случае — выявление периодичности. Решение этой задачи было найдено благодаря теории апериодических замощений. Известна олимпиадная задача: если есть бесконечное слово, удовлетворяющее конечной системе запретов, то есть и периодическое слово, удовлетворяющее той же системк запретов. В то же время уже в двумерье существуют конечные системы запретов, которым удовлетворяют только апериодические мозаики. Для решения проблемы Шеврина–Сапира потребовалось придать смысл умножению слева-справа-сверху-снизу. Взаимодействие автоматного и геометрического подхода оказалось интересным как с точки зрения алгебры, так и computer-science.
В теории замощений есть много красивых и идейных конструкций. Известны примеры конечных наборов плиток, с помощью которых можно замостить плоскость только непериодическим способом. Впервые такой пример построил Роберт Бергер в 1966 году. Есть и лаконичные примеры из небольшого числа плиток, например, знаменитые мозаики Пенроуза и Робинсона. Для получения таких конструкций широко используется подстановочный метод, когда из нескольких маленьких плиток собирается более крупная плитка того же типа, что позволяет получать непериодические замощения. Знаменитая теорема Мозеса–Гудмана–Штраусса позволяет получать из заданных подстановочных систем (путем введения локальных правил примыкания) наборы, допускающие только канонические подстановочные способы замощения (см. материалы прошедших в 2013 и 2018 году Летних Конференций Турнира Городов. Данная тематика активно развивается, в частности во Франции, и в работе на ЛКТГ приняли активное участие Т. Ферник и П. Гийон. Апериодическим замощениям был посвящен замечательный курс на прошлой школе Guilhem Gamard и Дарьи Пчелиной.
Если рассмотреть пути на мозаике в качестве элементов полугруппы, то такая полугруппа наследует некоторые свойства мозаики. Это открывает возможность построения моста между различными областями математики. В результате получается новый метод конструирования конечно определенных объектов и кроме того открывается возможность использования геометрических методов в информатике. Наша цель — в применении апериодических мозаик для построения бесконечной конечно определенной нильполугруппы. Мы коснемся приложений к теории групп (совместно с Анной Эршлер). В книге «Гиперболические группы» (секция 4.7.A) М.Л.Громов обсуждает вопрос: обязательно ли негиперболическая группа, с неположительной кривизной должна содержать подгруппу, изоморфную $\mathbb{Z}^2$?. Он выражает уверенность, что можно построить компактное полугиперболическое (неположительной кривизны) пространство, в которое можно отобразить $\mathbb{R}^2$, но фундаментальная группа которых не содержит $\mathbb{Z}^2$. Основанием для такой уверенности служит существование апериодических мозаик. Мы рассмотрим подходы к построению такой группы.
В рамках курса будут изложены базовые сведения о используемых понятиях, таких как апериодические мозаики, полугруппы, группы, кольца.