Известия Российской академии наук. Серия математическая
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Изв. РАН. Сер. матем.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Известия Российской академии наук. Серия математическая, 2021, том 85, выпуск 6, страницы 126–163
DOI: https://doi.org/10.4213/im8978 (Mi im8978) 		 
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)

Конечно определенная нильполугруппа: комплексы с равномерной эллиптичностью

И. А. Иванов-Погодаевab, А. Я. Канель-Беловc

a Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный
b Bar-Ilan University, Israel
c College of Mathematics and Statistics, Shenzhen University, Shenzhen, China
PDF полного текста (846 kB) PDF английской версии (714 kB) Полный текст в HTML Список цитирования (3)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/im8978
Аннотация: Работа является первой в цикле, посвященном конструкции конечно определенной бесконечной нильполугруппы, удовлетворяющей тождеству $x^9=0$. Эта конструкция отвечает на проблему Л. Н. Шеврина и М. В. Сапира.
В первой части цикла (настоящей работе) построена последовательность вложенных комплексов, состоящих из квадратов (4-циклов) со следующим набором геометрических свойств.
1) Равномерная эллиптичность. Пространство называется равномерно-эллиптическим, если можно выбрать константу $\lambda>0$ такую, что в множестве кратчайших путей, соединяющих любые две точки $A$ и $B$, на расстоянии $D$ можно выбрать два пути, удаленных друг от друга на расстояние $\lambda D$. При этом расстояние между путями с общим началом и концом определяется как максимум расстояний между соответствующими точками.
2) Вложенность. Комплекс $n+1$ уровня получается на основе комплекса $n$ уровня добавлением нескольких вершин и ребер по определенным правилам.
3) Локальная преобразуемость. Пусть разрешено преобразовывать пути, заменяя путь по двум сторонам минимального квадрата на путь по другим двум сторонам. Два кратчайших пути с общими концами локально преобразуются друг в друга, если концы путей принадлежат вершинам одного квадрата вложенного комплекса.
Геометрические свойства построенной последовательности комплексов в дальнейшем используются для задания конечно определенных полугрупп.
Библиография: 62 наименования.
Ключевые слова: конечно определенные полугруппы, нильполугруппы, конечно определенные кольца, конечно определенные группы.
Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01377
Конкурс «Молодая математика России»
Работа была проведена с помощью Российского научного фонда (грант № 17-11-01377). Первый автор является победителем конкурса “Молодая математика России”.
Поступило в редакцию: 08.10.2019
Исправленный вариант: 01.11.2020
Англоязычная версия:
Izvestiya: Mathematics, 2021, Volume 85, Issue 6, Pages 1146–1180
DOI: https://doi.org/10.1070/IM8978
Реферативные базы данных:
Тип публикации: Статья
УДК: 512.53
MSC: 20M05

§ 1. Введение

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

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

Теорема 1.1. Существует конечно определенная бесконечная нильполугруппа, удовлетворяющая тождеству $x^9=0$.

Подобные построения затрагивают, с одной стороны, проблемы бернсайдовского типа, а с другой – проблемы построения конечно определенных объектов. Поэтому следует хотя бы кратко упомянуть историю вопроса в этой связи.

1.1. Проблемы бернсайдовского типа

Проблемы бернсайдовского типа оказали огромное влияние на развитие современной алгебры. Эта проблематика, охватывающая широкий круг вопросов как в теории групп, так и в смежных областях, стимулировала алгебраические исследования. Проблемам бернсайдовского типа посвящена обзорная статья Е. И. Зельманова [1].

Ясно, что группы, удовлетворяющие тождеству $x^2=1$, коммутативны. Для групп с тождеством $x^3=1$ доказать локальную конечность несколько труднее (и она была доказана самим Бернсайдом [2]). Вопрос о локальной конечности групп с тождеством $x^4=1$ стоял открытым чуть меньше 40 лет, см. [3], а с тождеством $x^6=1$ – свыше 50, см. [4].

Первый контрпример к неограниченной проблеме был найден Е. С. Голодом в 1964 г. на основе универсальной конструкции Голода–Шафаревича [5], [6]. Эта конструкция позволила также построить не локально конечные периодические группы неограниченной экспоненты.

В ограниченном случае получению контрпримеров предшествовало построение бесквадратных слов над трехбуквенным алфавитом, а также бескубных слов над алфавитом из двух букв, т. е. построению бесконечных нильполугрупп с тождествами $x^2=0$ и $x^3=0$. Вопрос о локальной конечности групп с тождеством $x^n = 1$ был решен отрицательно в знаменитых работах П. С. Новикова и С. И. Адяна [7], [8]: для любого нечетного $n > 4381$ было доказано существование бесконечной группы с $m>1$ образующими, удовлетворяющей тождеству $x^n = 1$. Результаты Новикова–Адяна А. И. Мальцев рассматривал как основное событие алгебры XX века. Эта оценка была улучшена до $n > 665$ С. И. Адяном [9]. Также С. И. Адян в кратком анонсе сообщил, что удалось улучшить оценку до $n \geqslant 101$ (см. [10]).

Работы П. С. Новикова и С. И. Адяна оказали огромное влияние на творчество И. А. Рипса, который в дальнейшем разработал метод канонической формы и также построил примеры бесконечных периодических групп, обладающих дополнительными свойствами. Позднее А. Ю. Ольшанский предложил геометрически наглядный вариант доказательства для нечетных $n>10^{10}$, см. [11], [12]. Для достаточно больших четных $n$ примеры бесконечных $2$-порожденных групп периода $n$ были построены независимо С. В. Ивановым и И. Г. Лысёнком. В условиях делимости на достаточно большую степень двойки, было исследовано строение свободных бернсайдовых групп [13]–[16]. Подробная библиография и история вопроса приведены в [9].

Бернсайдова проблематика естественным образом переносится из теории групп в теорию колец. В $\mathrm{PI}$-случае вопросы локальной конечности алгебраических алгебр решаются положительно. В ассоциативном случае соответствующий результат был получен И. Капланским и Д. Левицким. Чисто комбинаторное доказательство для ассоциативного случая получается из теоремы Ширшова о высоте [17], [18]. Теореме Ширшова о высоте посвящена обширная библиография (см., например, работы [19]–[22]). Для $\mathrm{PI}$-алгебр Ли соответствующий результат для нулевой характеристики был получен А. И. Кострикиным. Кроме того, в характеристике $p$ им вместе с Е. И. Зельмановым показана локальная нильпотентность алгебр Ли с тождеством $y\circ \operatorname{Ad}(x)^n=0$. В общем случае результат был получен Е. И. Зельмановым. Это позволило решить так называемую “ослабленную проблему Бернсайда”, т. е. доказать наличие максимальной конечной группы среди $k$-порожденных групп, удовлетворяющих тождеству $x^n=1$. Подробная библиография по этому вопросу изложена в монографии [23].

Проблемы бернсайдовского типа для полугрупп рассматривались в монографии М. В. Сапира, с участием М. В. Волкова и В. С. Губы [24].

1.2. Проблемы конечной определенности

Все имеющиеся примеры бесконечных периодических групп бесконечно определены. Чрезвычайно глубоким и вдохновляющим является следующий открытый вопрос (входящий список основных алгебраических проблем в теории групп).

Вопрос 1.1. Существует ли конечно определенная бесконечная периодическая группа?

Известна классическая теорема Хигмана о вложении рекурсивно определенных групп в конечно определенные.

В работе А. Ю. Ольшанского и М. В. Сапира [25] была построена конечно определенная группа, являющаяся расширением конечно порожденной бесконечной периодической группы с помощью циклической.

На проблематику, связанную с построением разного рода экзотических объектов с помощью конечного числа определяющих соотношений, обратил внимание В. Н. Латышев [26]. Им же была поставлена проблема существования конечно определенного нилькольца [27].

Вопрос 1.2 (В. Н. Латышев). Существует ли конечно определенное бесконечномерное нилькольцо?

В качестве продвижения в решении этого вопроса можно рассматривать результаты Г. П. Кукина, В. Я. Беляева о вложениях рекурсивно определенных объектов в конечно определенные [28], [29]. В. А. Уфнаровским был построен пример конечно определенной алгебры промежуточного роста [30]. В работе В. В. Щиголева [31] была изучена связь между понятиями ниль и нильпотентности конечно определенных алгебр в зависимости от количества определяющих соотношений и порождающих. Также построен пример алгебр с малым количеством определяющих соотношений, у которых все слова длины два нильпотентны. Кроме того, построению конечно определенных объектов и автоматному подходу в алгебраических структурах посвящен ряд других результатов [30], [32]–[39].

Фундаментальную проблему существования конечно определенной нильполугруппы поставили Л. Н. Шеврин и М. В. Сапир в Свердловской тетради [40; (3.61б)], а также в [41; вопрос 3.8].

Вопрос 1.3 (Л. Н. Шеврин, М. В. Сапир). Существует ли конечно определенная бесконечная нильполугруппа?

Авторам представляется, что полугрупповой вопрос предшествует кольцевому, а кольцевой – групповому. Этот вопрос привлекал внимание авторов в течение многих лет. Ряд результатов, таких как конструкция конечно определенной полугруппы с нецелой размерностью Гельфанда–Кириллова, построение алгебр с конечным базисом Грёбнера, но неразрешимой проблемой делителей нуля, возникли из работы над этой проблемой, см. [42]–[44]. Также был построен пример конечно определенной полугруппы, содержащий ненильпотентый ниль-идеал [45].

Теорема 1.2 (см. [46]). Существует конечно определенная полугруппа $H$ с множеством слов $G$ от образующих, удовлетворяющая следующим свойствам:

1) существует идеал, содержащий бесконечное множество элементов $I= LH$, где $L$ – буква в $H$;

2) если слово $A\in G$ представляется в виде $A = XYYZ$, где $X,Y,Z\in G$, то $LA = 0$.

Авторы признательны руководителям семинара “Теория колец” на кафедре высшей алгебры механико-математического факультета МГУ – В. Н. Латышеву и А. В. Михалёву за полезные обсуждения и постоянное, в течение ряда лет, внимание к работе. Мы также благодарны И. А. Рипсу, Л. Н. Шеврину, А. Х. Шеню, Н. К. Верещагину, А. Эршлер за полезные обсуждения, Ф. Дюранду, Ц. Селле, Л. А. Бокутю, Ю. Чэну, Т. Фернику за поддержку в участии на конференциях, А. С. Малистову за помощь в оформлении статьи. Особую благодарность мы выражаем А. Л. Семёнову за полезные советы и внимание к работе.

Результат о построении конечно определенной нильполугруппы докладывался авторами на конференциях [47]–[52] и семинарах1.

1.3. Схема зависимости материала и содержание параграфов

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

В § 1 обсуждаются проблемы бернсайдовского типа и конечной определенности и связанные с этим вопросы.

В § 2 обсуждается общая стратегия доказательства, а также смежные вопросы.

В § 3 обсуждаются чисто геометрические свойства комплекса, лежащего в основе построения.

В последующих параграфах (они будут опубликованы во второй и третьей работах цикла) продолжается построение конечно определенной нильполугруппы. Вводится параметризация, благодаря которой структура построенного геометрического комплекса оказывается связанной со структурой полугруппы. В частности, вводится алфавит букв, кодирующих вершины и ребра на комплексе. Детерминированность комплекса позволяет ввести определяющие соотношения на коротких отрезках путей. Кратчайшим путям на комплексе будут соответствовать ненулевые слова во введенной полугруппе.

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

§ 2. Конечная определенность, связь с информатикой, геометрические методы

2.1. Построение конечно определенных объектов и системы конечных автоматов

При построении разного рода объектов трудности вызывает контроль над следствиями из вводимых соотношений, в особенности тогда, когда следует доказать, что некое соотношение не является следствием заданных. Зачастую используются три метода контроля над соотношениями:

(1) базис Гребнера и бриллиантовая лемма;

(2) теория малых сокращений;

(3) реализация машины Тьюринга или машины Минского.

В конечно определенном случае вопросы, связанные с построением объектов, обладающих заданными свойствами, сильно усложняются и наибольшее значение приобретает третий метод. При этом буква интерпретируется как состояние конечного автомата, а слово – как цепочка взаимодействующих конечных автоматов. Если число соотношений конечно, то это взаимодействие локально, и мы получаем связь с задачами самоорганизации, типа задачи Майхилла о стрелка́х и так далее. На этом пути была решена задача о построении конечно определенных полугрупп с рекурсивной размерностью Гельфанда–Кириллова [46]. Отметим, что подобная техника довольно громоздка для построений, требующих малого роста. Например, не удалось пока построить конечно определенную полугруппу с размерностью Гельфанда–Кириллова, равной $2.5$.

На этом же пути был получен ответ на известный открытый вопрос, поставленный В. Н. Латышевым: была построена алгебра с неразрешимой проблемой делителей нуля и конечным базисом Грёбнера [46], а также алгебра с неразрешимой проблемой нильпотентности и конечным базисом Грёбнера [44]. Отметим, что для автоматных мономиальных алгебр (в частности, конечно определенных) а также алгебр с ограниченной переработкой аналогичный вопрос (также поставленный В. Н. Латышевым) решается положительно [53], [37], [54].

Задача о построении конечно определенной бесконечной нильполугруппы имеет интерпретацию в этих терминах. Рассмотрим цепочку локально взаимодействующих конечных автоматов. У них есть цвета корпусов. Если автомат объявляет себя нулем (совершает самоубийство), то вся цепочка погибает. Можно ли добиться того, чтобы преобразования были обратимы (если $u=v$, то $v=u$), при этом существовали сколь угодно длинные живые цепочки, и чтобы любая цепочка, у которой несколько раз подряд повторились цвета корпусов, погибала? Мы задаем локальный закон взаимодействия, а наш враг – задает внутренние состояния автоматов. Требуется достичь адекватного поведения цепочки автоматов.

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

2.2. Схема доказательства. Мозаики

Пусть $W$ – бесквадратное слово над алфавитом из трех букв. Если каждое его неподслово (т. е. антислово) объявить нулем, то естественно возникающая полугруппа слов обладает тождеством $x^2=0$. Однако естественная конструкция, связанная с заданием множества нулевых слов как подслов слов из некоторого семейства, в конечно определенном случае работает плохо.

Невозможно задать конечно определенную ненильпотентную нильполугруппу только мономиальными соотношениями, т. е. соотношениями типа $v=0$. Ибо если есть конечный список запретов и бесконечное слово без запрещенных подслов, то есть и бесконечное периодическое слово также без запрещенных подслов.

Действительно, пусть $W$ – бесконечное слово без запрещенных подслов. Разобьем его на подслова длины $l$, где $l$ превосходит длину каждого из запрещенных подслов. В силу бесконечности $W$ и конечности алфавита, в $W$ есть подслово вида $ABA$, где длина $A$ равна $l$. Тогда бесконечное периодическое слово с периодом $AB$ не содержит запрещенных подслов.

Что если от одномерных расположений (слов) перейти к двумерным? Известно, что существуют конечные наборы многоугольников (плиток), которыми можно замостить плоскость лишь непериодически. Впервые такой набор был построен Робертом Бергером [55]. В дальнейшем были построены более простые примеры, например, Рафаэлем Робинсоном [56]. Широко известна также мозаика Пенроуза. Итак, имеются контактные правила, для которых:

– существует замощение всей плоскости, удовлетворяющее запретам;

– однако таких периодических замощений не существует.

Поэтому если можно было бы умножать слева-справа-сверху-снизу, то такого рода объекты можно было бы построить.

Но как придать всему этому смысл? Будем интерпретировать элементы полугруппы как пути на мозаике (дальнейший анализ показывает, что удобно иметь дело с кратчайшими путями – иначе можно много раз проходить один и тот же цикл). Буквы кодируют плитки и переходы между ними. Если локальный непорядок (два символа плитки без символа перехода между ними и так далее), то произведение нуль. Кроме того, если локальный участок не располагается на мозаике или не располагается как участок кратчайшего пути, то он также нулевой.

Если же любую пару узлов, соединяемую кратчайшим путем с кодом $s_1$, можно соединить кратчайшим путем с кодом $s_2$ и наоборот, то $s_1=s_2$.

Итак, пусть существует периодическое слово $U=W^n$. Начинаем добавлять клетки к слову $U$, локально перебрасывая пути. Оно окружается мозаикой. Поскольку $U$ периодично, то не может быть расположено на нашей мозаике. Поэтому в какой-то момент вставлять клетки не получится и мы доберемся до локального участка, несовместимого с мозаикой. Тем самым устанавливается равенство слова $U=W^n$ нулю.

Таким образом, возникает мозаика со своей глобальной структурой, которая и обеспечивает апериодичность. Локальные правила задают эту самую структуру и путь, “перекидывание” которого задает область на мозаике. Возникают три языка: геометрический язык, описывающий глобальное поведение комплекса, комбинаторно геометрический язык контактов (локальных правил) и полугрупповой язык соотношений – переброски путей. Для решения задачи следует научиться переводить с одного языка на другой и, главное, обеспечить саму эту возможность.

Возможность перевода с языка контактов на глобальный язык связана с утверждениями типа теоремы Х. Гудмана-Штраусса [57]. Теорема Х. Гудмана- Штраусса утверждает, что любую плоскую мозаику, связанную с подстановочной системой (плоской $\operatorname{DOLL}$-системой), можно задать локальными правилами. Наш подход, использующий реберную структуру, ближе к подходу Тома Ферника и Николя Бедериде [58].

2.3. Апериодические мозаики. “Демо-версия” доказательства

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

Наличие апериодических мозаик связано со следующим обстоятельством. Рассмотрим работу машины Тьюринга на клетчатой ленте. Движение головки и обмен сигналами можно перевести на язык укладки плиток на фазовой диаграмме “пространство-время”. Из этого выводится алгоритмическая неразрешимость проблемы дополнения заданного набора плиток до замощения плоскости.

Алгоритмическая неразрешимость проблемы замощения, когда изначально ничего не положено, доказывается технически сложнее. Здесь “пространство” и “время” перемешиваются. Строятся замощения, в некоторых местах которых вынуждается один шаг машины Тьюринга, в других – два шага и так далее. Линии, отвечающие работе машины, образуют некую структуру. Дальнейшее совершенствование и упрощение конструкций приводит к апериодическим мозаикам, ставшим классическими (плитки Амманна, мозаики Пенроуза и др.).

В 1961 г. Хао Вангом [59] были рассмотрены квадратные плитки с разноцветными сторонами. Разные плитки можно прикладывать друг к другу сторонами одного цвета. Был поставлен вопрос, существуют ли конечные наборы таких плиток, с помощью которых могут быть получены только непериодические замощения плоскости. Первым такой набор был построен Робертом Бергером [55], основная идея которого состояла в том, что замощения моделировали работу машины Тьюринга. При этом использовалось несколько тысяч плиток. Позднее были придуманы наборы, содержащие небольшое количество плиток. Например, интересна конструкция Рафаэля Робинсона [56]. В этой связи можно также упомянуть мозаики Пенроуза и Амманна, состоящие из многоугольников, которыми, при заданных условиях, можно замостить плоскость лишь непериодически. Различные примеры апериодических мозаик содержатся также в работе [60].

2.3.2. Иерархия и апериодичность

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

Пример 2.1. Плитки могут быть квадратами $A$ и $B$, при этом, чтобы составить квадрат $A$ второго уровня, нужно взять четыре квадрата $A$, $A$, $A$, $B$. А чтобы составить квадрат $B$, нужно взять четыре квадрата $B$, $A$, $B$, $A$.

Таким образом, получается иерархическая система. Каждую плитку можно разбить на требуемое число уровней иерархии. Можно показать, что получаемое замощение будет непериодично. Аналогичный способ построения используется в подстановочных системах, например, c помощью подстановок $1\to 10$, $0\to 01$ получается бескубное слово

$$ \begin{equation*} 1001011001101001 \dots\,. \end{equation*} \notag $$

Оказывается, что язык граничных условий и язык иерархий схожи. А именно, любую иерархическую систему можно задать конечным числом граничных условий.

Пусть имеется конечное число типов плиток, причем заданы правила иерархии, по которым плитка уровня $n$ составляется из нескольких плиток уровня $n-1$. Тогда для начального набора плиток первого уровня можно задать конечную систему граничных условий так, чтобы задавалась мозаика, получаемая при иерархическом способе задания.

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

2.3.3. Демо-версия доказательства

Рассмотрим одну из классических мозаик – знаменитую мозаику Пенроуза (см. рис. 2).

Конструкция мозаики Пенроуза. Используются плитки двух видов – толстый и тонкий ромбы. Есть граничные условия: стороны каждого ромба раскрашены в две пары цветов. Соприкасаться два ромба могут только сторонами двух цветов, образующих пару. На рис. 2 цвета обозначены внешними и внутренними насечками двух типов.

Конструкция полугруппы мозаики Пенроуза. Легко видеть, что возможно конечное количество типов узлов-вершин, где сходятся несколько плиток. Кроме того, ребра в мозаике могут иметь десять возможных направлений. Можно выписать все возможные типы узлов и обозначить их буквами алфавита. Теперь последовательность букв (слово) будет кодировать последовательность узлов, которые мы проходим вдоль пути.

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

Некоторые пути на мозаике можно объявить эквивалентными: например, путь по двум соседним ребрам ромба эквивалентен пути по другой паре сторон. Можно выписать все такие эквивалентности для разных вариантов получающихся узлов и получить полный конечный список. Тогда с помощью локальных замен можно переводить одни пути в другие.

Таким образом, с мозаикой Пенроуза можно связать конечно определенную полугруппу, где словам соответствуют пути. Запрещенные пути – это нулевые слова. Можно также запретить пути, которые не являются кратчайшими между двумя узлами. Для этого нужно сначала внести в список запрещенных такие короткие пути. После этого можно показать, что с помощью локальных замен любой некратчайший путь приводится к виду, содержащему запрещенный короткий подпуть.

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

Почему нужна другая мозаика. Проблема заключается в том, что на мозаике Пенроуза есть пути, которые недостаточно сильно меняются локальными заменами, т. е. недостаточно “извиваются”. Это приводит к тому, что можно сконструировать путь, каждый локальный кусок которого может быть вложен в мозаику, но весь путь не может быть вложен. Локальные замены меняют его незначительно и преобразовать его в достаточной мере, чтобы диагностировать несоответствие мозаике, не получается.

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

2.4. Язык контактов vs язык соотношений. Подклейки

Итак, если осуществлять нашу программу на базе классических мозаик, то возникают трудности, связанные с тем, что в некоторых направлениях геодезические пути не поддаются изгибу и вокруг них ничего из переброски не наращивается. А именно, достаточно протяженный в двух измерениях кусок мозаики не обеспечивает вычислительный процесс.

Перевод с языка соотношений (т. е. движения геодезического пути) на язык контактов является задачей более сложной и обеспечить его возможность не так просто. Чтобы локальное шевеление геодезической заполнило достаточную область, пространство должно быть равномерно-эллиптическим. Пространство называется равномерно-эллиптическим, если любые две точки $A$ и $B$ на расстоянии $D$ соединяются системой геодезических, образующих диск ширины $\lambda\cdot D$ для некоторой глобальной константы $\lambda>0$. (Априори не очевидно, что такое пространство существует.) Такое пространство следует собрать из мозаики и установить аналог теоремы Гудмана-Штраусса для этой сборки.

Равномерно-эллиптическое пространство строится из подстановочной системы, указанной на рис. 3, при этом следует озаботиться тем, чтобы степени узлов были бы ограничены, что усложняет конструкцию, вынуждая сделать композицию разных подстановок.

Мы хотим добиться того, что никакой узел $X$ на пути из A в B не являлся бы обязательным пунктом посещения (узким местом). Для этого вводятся подклейки. Для некоторых путей $AXB$ мы будем вклеивать макроплитку $AXBZ$, где $Z$ – новая создаваемая вершина, вне плоскости $AXB$. На дальнейших этапах разбиения проводятся подклейки к подклейкам. Если путь устроен так, что мы входим внутрь подклейки, а потом возвращаемся из нее, то участок на пути, находящийся вне базовой плоскости все время является односвязным.

Это, в частности, означает, что нельзя деформировать участок пути в подклейку так, чтобы он частично стал лежать в базовой плоскости. Кроме того, размеры подклеек к плиткам, подклеек к подклейкам и т.д. экспоненциально убывают достаточно быстро. Тем самым, помимо всего прочего, обеспечивается гомотопическая тривиальность комплекса, образованного “подклейками”.

2.5. Последовательная канонизация. Завершение доказательства

Доказательство завершается так. Рассмотрим слово. Надо его либо привести к кодировке, соответствующей пути на комплексе (тем самым оно непериодично), либо к нулю. Оно последовательно приводится к $k$-каноническому виду и при этом $k$ растет, т. е. оно состоит из участков границ плиток $k$-го уровня иерархии, кроме начала и конца, целиком содержащихся в плитке уровня $k-1$ (возможно в подклейке $(k-1)$-го уровня) и при этом являющихся $(k-1)$-каноническими.

Далее с помощью соотношений (в том числе отвечающих выходу в подклейку) проверяется согласование соседних участков пути, расположенных на границах плиток $k$-го уровня, их нахождение в $(k+1)$-м уровне или возможность находиться в двух соседних плитках $(k+1)$-го уровня. Отсутствие согласования означает, что пути с такой кодировкой не существует на комплексе, т. е. в этом случае слово можно привести к нулю.

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

Согласование означает возможность преобразования к $(k+1)$-каноническому виду, после чего процесс повторяется. Он заканчивается канонической формой слова. В нашем случае каноничность не означает однозначности, поскольку можно выбирать разные стороны плиток. Наверное, существует такой выбор, но он более сложен и ситуация похожа на теорию канонической формы элементов в гиперболических группах (или, в более общем случае, в группах с неположительной кривизной), развитую И. А. Рипсом, когда вначале строится предканоническая форма (для данного уровня иерархии), а потом осуществляется выбор.

2.6. Специфика геометрических методов в полугрупповом случае

Интерпретация соотношений в полугруппах через “rewriting diagram” похожа на применение диаграмм ван Кампена в теории групп. Рассмотрение мозаик также родственно работе с диаграммами ван Кампена в теории групп. Использование путей по ребрам в плиточных замощениях и групп связанных с ними, встречается в работах Дж. Конвея [61]. С помощью групповой техники он показал отсутствие различных разбиений. Приведем модельный пример.

Пример 2.2. Рассмотрим шахматную доску, из которой вырезаны две противоположные угловые клетки. Тогда ее нельзя разбить на доминошки $1\times 2$.

Предположим, что такое разбиение существует. Рассмотрим доминошки как клетки в диаграмме ван Кампена. Букве $a$ сопоставим вертикальную стрелку, букве $b$ – горизонтальную, обратным буквам – обратные стрелки. Вертикальная доминошка отвечает соотношению $a^2ba^{-2}b^{-1}=e$, а горизонтальная – $b^2a^{-1}b^{-2}a=1$. Границе квадрата с вырезанными углами отвечает путь $a^7bab^7a^{-7}b^{-1}a^{-1}b^{-7}$. Будем интерпретировать групповые слова как элементы группы $S_3$. Если сопоставить элементу $a$ транспозицию элементов $1$ и $2$, а элементу $b$ – транспозицию $2$ и $3$, то $a^2=b^2=e$ и соотношения выполнены, в то же время как $a^7bab^7a^{-7} b^{-1}a^{-1}b^{-7}=(ab)^4=ab\ne e$ есть трехчленный цикл.

Тем же методом решаются многие другие олимпиадные задачи на раскраску, но в то же время и такие, которые раскраской не делаются (подробности см. [62]).

Тем не менее мозаики и диаграммы ван Кампена существенно различаются. Например, свойства величин углов имеют далеко не полное отражение. Аналогия между мозаиками и группами довольно глубокая, но не вполне формализована. Имеется классический результат об алгоритмической разрешимости проблемы равенства слов в группе с одним соотношением. Имеется и аналогичный вопрос об алгоритмической разрешимости проблемы разбиения плоскости транслятами одной фигуры. Для связных фигур такая алгоритмическая разрешимость доказана, а в общем случае вопрос остается открытым.

Далее, при разбиении квадрата на домино возникают подквадратики $2\times 2$, разбитые на пары доминошек. Такую пару можно повернуть на $90^\circ$ и сделать флип. Такими флипами можно от одного разбиения перейти к любому другому. Аналогичный факт верен и для разбиения на $k$-миношки и для многих других разбиений. Данный факт родственен конечной порождаемости группы $\pi_2$ комплекса (с учетом действия фундаментальной группы $\pi_1$). Хорошо бы прояснить аналогию.

В полугруппах геометрические идеи работают не совсем так, как в группах, и в нашем случае эффекты “углов” лучше представлены. По всей видимости, полугрупповая теория может пролить свет на мозаики. Более того, есть некая близость теории полугрупп к кольцам как к “квантовой взвеси”, так что и кольцевая теория, если будет построена, даст дополнительное понимание. Возможно, наш подход окажется полезным и для других построений в полугруппах и кольцах.

2.7. Апериодические замощения в нашей конструкции

Как уже говорилось, существуют конечные наборы многоугольников (плиток), которыми можно замостить плоскость лишь непериодически. Методы построения таких мозаик, как правило, опираются на иерархические правила построения: задаются универсальные правила построения плиток уровня $n+1$ из плиток уровня $n$, для нескольких типов плиток $A_1,\dots,A_k$. Х. Гудман-Штраусс [57] показал, что иерархические мозаики можно получить, задав конечное число локальных правил. Таким образом, локальные условия (конечность набора) могут приводить к глобальному эффекту (непериодичности замощения).

Итак, основной задачей является конструирование мозаики, в которой указанные выше трудности были бы решены. Для этого она должна обладать несколькими следующими свойствами.

1. Локальная конечность. Речь идет о конечности числа возможных типов узлов, конечности изначально задаваемых пар эквивалентных путей, а также конечности списка запрещенных путей.

2. Возможность “шевеления” любого пути. Любой достаточно длинный путь, соединяющий узлы $A$ и $B$, может быть переведен локальными заменами в другой путь, отличающийся достаточно сильно от начального.

Более точно, пусть длина пути равна $n$ и точка $M$ – его середина (или такая точка, что расстояния вдоль путей $AM$ и $MB$ различаются на 1). Пусть $AM'B$ – эквивалентный путь, $M'$ – соответствующая $M$ точка. Пусть $R_{AMB}(n)$ – максимальное расстояние от $M$ до $M'$ по всем эквивалентным путям $AM'B$. Требуемое нами условие означает, что $R_{AMB}(n)$ является неограниченной возрастающей функцией от $n$.

3. Апериодичность. На мозаике не должно быть путей, отвечающих периодическим словам.

Как уже говорилось, мы используем геометрическую интерпретацию для алгебраических построений. Запрет для двух (или более) плиток находиться рядом друг с другом схож с запретом для двух букв стоять рядом в разрешенном слове. Возникает интерпретация слова как последовательности плиток на выложенной мозаике. Апериодичность мозаики приводит к непериодичному характеру таких “плиточных слов”. В свою очередь, непериодических замощений можно добиться, если применять иерархический способ построения.

В связи с этим используются языки плиточных примыканий и иерархий. Эти языки во многом схожи, например, заданные правила иерархии, когда плитки $A_1,\dots,A_k$ уровня $n+1$ составляются из плиток $A_1,\dots,A_k$ уровня $n$, можно выразить с помощью конечного множества локальных правил для набора $A_1,\dots,A_k$. Эти локальные правила будут порождать те же непериодические мозаики, что и исходные правила иерархии.

Дальнейшее развитие этих языков приводит к появлению более универсального языка путей на графе. Таким образом, плиточная мозаика рассматривается как граф, где вершины это узлы мозаики, а ребра – границы плиток. В этом смысле понятие плитки можно обобщить, рассматривая их уже как локальные подграфы, из которых с помощью локальных правил можно составлять граф, покрывающий плоскость.

Аналогом буквы будет тип вершины графа, а аналогом слова – путь, проходящий через несколько вершин. Аналогом соотношения будет эквивалентность между путями с общими концами: например, в простом $4$-цикле $ABCD$ выполнено соотношение $ABC=ADC$. Кроме таких, есть также мономиальные соотношения, выражающие идею о невозможности существования какого-то пути на мозаике. Также для обеспечения необходимого контроля над множеством ненулевых слов вводятся мономиальные соотношения, обнуляющие слова, соответствующие некратчайшим путям. Оказывается, что при этом можно обойтись конечным числом соотношений. Немономиальные соотношения при этом не меняют длины слова.

Язык путей на мозаике-графе позволяет выразить те же концепции и определить те же мозаики, что и языки иерархических плиток или граничных условий. Таким образом, возникает связанная с мозаикой конечно определенная полугруппа с набором свойств, индуцированных мозаикой.

Для построения нильполугруппы используется мозаика, сгенерированная с помощью следующего иерархического правила разбиения (рис. 3).

От мозаики нужно потребовать ряд дополнительных свойств. В частности, любой длинный путь должен допускать возможность “шевеления”, т. е. локальных преобразований над ним, позволяющих в достаточной мере менять его. Для достижения этого свойства к плоской мозаике производятся “подклейки”, представляющие собой небольшие плоские подграфы, не лежащие в исходной плоскости и позволяющие обходить “узкие места” на исходном плоском графе. Структура подклеек также имеет иерархическую природу и так же может быть задана на языке преобразований путей конечным образом.

В итоге мы получаем граф, обладающий набором важных для нас свойств, в котором любой путь, соединяющий произвольные точки $A$ и $B$, является членом семейства геодезических эквивалентных друг другу путей, соединяющих эти точки. Причем эквивалентность двух путей из этого семейства может быть получена путем цепочки локальных преобразований, переводящих один путь в другой. “Шевеление” пути играет роль передачи информации. Фактически, определяющие соотношения задают правила передачи информации по пути. Если задан произвольный длинный путь, мы можем начать работать над ним, совершая локальные преобразования. При этом возможна альтернатива:

1) в результате этой работы можно получить внутри некратчайший подпуть, либо подпуть указанный в числе запрещенных; в этом случае наш путь представляет нулевое слово;

2) в результате этой работы мы восстанавливаем некоторый кусок мозаики, внутри которого лежит пучок геодезических путей, эквивалентных нашему.

Мозаика не может содержать в себе путей, выражаемых периодическим словом. Таким образом, все периодические слова могут быть приведены к нулю локальными преобразованиями. При этом геодезические пути, лежащие на мозаике, не приводятся к нулю и могут иметь любую длину. Таким образом, полугруппа, соответствующая построенному графу-мозаике, будет конечно определенной нильполугруппой.

2.8. Конечно определенные полугруппы

Рассмотрим алфавит $\Omega$, состоящий из конечного числа букв. Слова, составленные из букв, образуют полугруппу относительно операции приписывания одного слова к другому. Кроме того, есть специальная буква $0$ (нуль) такая, что $W0=0W=0$ для любого слова $W$ из полугруппы. Определяющим соотношением в полугруппе считается равенство вида $W_1=W_2$, где $W_1$ и $W_2$ – некоторые слова, причем одно из них может быть нулем (или нулевым словом). В этом случае соотношение называется мономиальным. Для натурального $n$ степенью слова $W^n$ называется слово $WW\dots W$, где $W$ выписано $n$ раз подряд. Рассмотрим полугруппу, факторизованную по введенным соотношениям. Элемент полугруппы (слово) называется нильэлементом, если существует натуральное $n$ такое, что $W^n=0$. Если все элементы полугруппы являются нильэлементами, то вся полугруппа называется нильполугруппой. Разумеется, наша полугруппа содержит нуль.

Мы пользуемся геометрической интерпретацией: буквам отвечают вершины специального графа, а словам – пути в этом графе. И если слово не может быть представлено путем на графе, оно всегда будет приводиться к нулю.

2.8.1. Плитки и непериодические замощения

Начнем с чистой геометрии. Мы задаем конечный набор граничных условий (как можно прикладывать плитки друг к другу), и через задание локальных условий достигается глобальный эффект. Задание граничных условий схоже с заданием определяющих соотношений в полугруппе, этим объясняется интерес к плиткам и замощениям.

2.8.2. Узлы на мозаике и пути по границам плиток

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

Назовем узлами вершины мозаики, где сходятся несколько плиток. Ясно, что в плоской мозаике с конечным набором типов плиток возможно конечное число видов узлов. Обозначим их буквами конечного алфавита. Последовательность букв (слово) соответствует пути на мозаике. Некоторые слова могут вообще не встречаться на мозаике, а другие – встречаться в разных местах.

Третий подход к конструированию мозаик состоит в определении конечного списка невозможных путей, а также задании конечного числа пар эквивалентных путей. С помощью такого языка можно задавать мозаики так же, как и с использованием иерархических систем плиток или граничных условий на плитки.

Мы будем строить такую мозаику в два приема. На первом этапе построим ее плоскую часть, которую будем считать базовой. Она будет строиться в виде иерархического графа. На втором этапе мы покажем, как к построенному графу производятся подклейки – плоские и конечные подграфы, лежащие в другой плоскости, но имеющие с базовым графом несколько общих ребер. В результате получится $2$-комплекс, вложенный в трехмерное пространство.

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

В дальнейших параграфах мы построим мозаику, где выполнены указанные выше свойства.

§ 3. Геометрическая структура комплекса

3.1. Иерархическое построение

Построим комплекс уровня $n$ с помощью итерационного процесса. На каждом шаге мы будем иметь дело с графом, причем простые циклические пути из четырех ребер будем называть плитками.

Комплекс уровня $1$ представляет собой простой цикл из четырех вершин $CUL$, $CUR$, $CDR$, $CDL$. Комплекс уровня $2$ – это граф на рис. 4. Таким образом, на втором этапе у нас имеется шесть плиток. Будем называть их, согласно их положению, левой верхней, левой нижней, правой нижней, правой верхней, средней, нижней.

Будем считать, что вершины $A$, $B$, $C$, $U$, $L$, $R$, $D$ имеют глубину $0$, а изначальные четыре вершины (углы) имеют глубину, равную $-1$. Будем также называть их угловыми. Кроме этого, угловые вершины будут появляться при операции подклейки (см. ниже).

С комплексом будут производиться итерации двух типов: разбиение и подклейка.

Определение 3.1. Макроплиткой уровня $n$ назовем: для $n=1$ обычную плитку (простой $4$-цикл), которую будем также называть минимальной; для $n>1$ результат применения следующей операции разбиения к макроплитке уровня $n-1$: каждая плитка данной макроплитки разбивается на шесть новых плиток согласно правилу на рис. 5. Cоздаются новые четыре вершины на границе разбиваемой плитки (в серединах ее сторон) и три вершины внутри нее. Одна из четырех возможных ориентаций определяется согласно положению (одному из шести) разбиваемой плитки в ее родительской макроплитке (рис. 6).

Проводимые при разбиении ребра будем называть внутренними ребрами, принадлежащими разбиваемой макроплитке. Иначе говоря, макроплитка, которой принадлежит ребро, является минимальной по включению из тех макроплиток, которые содержат данное ребро целиком как внутреннее. Таким образом, принадлежность ребра определяется раз и навсегда, при его появлении. Уровнем ребра будем называть уровень макроплитки, которой оно принадлежит. Типами внутренних ребер будем называть $8$ видов ребер, образующихся при разбиениях (рис. 7). Также для каждого внутреннего ребра определим две стороны $A$ и $B$, расположенные, как указано на рис. 7. Есть также $4$ типа граничных ребер (это ребра изначального цикла из $4$ вершин): левое, правое, верхнее и нижнее. Пусть они также пронумерованы от $9$ до $12$. Граничные ребра комплекса относятся к этим типам. Также к ним относятся границы создаваемых подклеенных макроплиток (см. ниже). Будем считать, что граничные ребра принадлежат макроплиткам, сторонами которых они являются.

Замечание 3.1. Далее в тексте термин ребро означает ребро макроплитки, а не ребро графа, если только из контекста не следует обратное. В то же время, входящее или выходящее ребро – как раз ребро графа, входящее в данную вершину.

Определим типы вершин на комплексе.

Определение 3.2. Все вершины, встречающиеся на комплексе, мы разделим на следующие категории.

1) Угловые (лежащие в углах подклеенных макроплиток или всего комплекса). Тип угловой вершины определим как один из четырех вариантов углов, в котором она может находиться: $\mathbb{CUL}$, $\mathbb{CUR}$, $\mathbb{CDR}$, $\mathbb{CDL}$ (corner up-left и так далее). Угловые вершины принадлежат максимальной макроплитке, где они являются углами.

2) Краевые (лежащие на стороне подклеенной макроплитки или всего комплекса). Каждая такая вершина лежит в середине стороны некоторой макроплитки, прилегающей к краю. Тип краевой вершины определим в соответствии с тем, серединой какой стороны в этой макроплитке она является: $\mathbb{L}$, $\mathbb{R}$, $\mathbb{D}$, $\mathbb{U}$. Краевые вершины принадлежат той макроплитке, на середине стороны которой они лежат.

3) Внутренние. В этой категории определим три типа внутренних вершин: $\mathbb{A}$, $\mathbb{B}$, $\mathbb{C}$, отвечающих внутренним узлам макроплиток, эти вершины создаются внутри разбиваемой макроплитки. Будем считать, что эти вершины принадлежат данной макроплитке. Иначе говоря, такие вершины принадлежат минимальной по включению макроплитке, содержащей их.

4) Боковые (лежащие на границе между двумя макроплитками, на внутреннем ребре). Типы боковых вершин будут соответствовать всем упорядоченным парам из множества $\{ \mathbb{U}, \mathbb{R}, \mathbb{D}, \mathbb{L}\}$, а именно, $\mathbb{DR}$, $\mathbb{RD}$, $\mathbb{DL}$ и так далее. Будем считать, что в упорядоченной паре первой называется буква, соответствующая $A$-стороне внутреннего ребра, на котором лежит вершина. Все боковые вершины создаются в серединах сторон разбиваемой макроплитки. Тип боковой вершины определяет, серединой каких именно сторон она является в двух макроплитках, где она является серединой сторон. Это как раз те макроплитки, которые разбивались при создании данной вершины. Будем считать, что боковые вершины принадлежат макроплитке, которой принадлежит данное внутреннее ребро.

В дальнейшем вершину типа $\mathbb{A}$ для простоты будем называть $A$-вершиной или $A$-узлом. Аналогично для других типов. Вообще, вершины на графе мы также будем называть узлами.

Заметим, что тип вершины определяется при ее создании и в дальнейшем не меняется. Например, если вершина была боковой вершиной и после какой-то подклейки оказалась на краю подклеенной макроплитки, то она все равно останется боковой и принадлежащей той макроплитке, внутреннему ребру которой она принадлежит.

Определим глубину новых вершин. Будем считать, что краевые и боковые вершины принадлежат тем ребрам, на которых они создаются. Все создаваемые при разбиении вершины получают глубину на $1$ больше, чем максимальная глубина вершины до разбиения. Из построения ясно, что у любого ребра макроплитки хотя бы один из концов является вершиной, созданной на предыдущем шаге. Следовательно, создаваемая вершина в середине ребра получает глубину на $1$ большую, чем максимальная глубина двух концов ребра.

Определение 3.3. Операция разбиения, примененная ко всему комплексу, есть результат одновременного применения разбиения ко всем плиткам первого уровня в комплексе.

Определение 3.4. Операция подклейки. При подклейке мы рассматриваем все пути $X_1X_2YZ_2Z_1$ из пяти вершин (и четырех ребер) такие, что:

1) вершины $X_1$, $Y$, $Z_1$ не являются тремя углами из четырех никакой макроплитки;

2) вершины $X_1$, $Z_1$ являются боковыми или краевыми вершинами глубины $k-1$, где $k$ – максимальная глубина вершины в комплексе;

3) вершина $X_2$ является серединой $X_1Y$, а $Z_2$ – серединой $Z_1Y$, т. е. $X_2$ и $Z_2$ являются боковыми или краевыми вершинами глубины $k$, созданными в комплексе самыми последними, при последней операции разбиения;

4) вершина $Y$ имеет глубину $k-2$;

5) путь $X_1X_2YZ_2Z_1$ выбран так, что уровень ребра, которому принадлежит вершина $X_1$ больше уровня ребра вершины $Z_1$.

Допустим, ребра, которым принадлежат $X_1$ и $Z_1$, имеют один уровень. В этом случае мы считаем, что ребро $X_1$ имеет меньший номер в нумерации ребер, входящих в вершину $Y$, которая определяется индуктивно по глубине, см. ниже.

Далее, для каждого такого пути создаются шесть новых вершин $T_1$, $T_2$, $T_3$, $T_A$, $T_B$, $T_C$, не лежащих в плоскости $X_1YZ_1$, а также проводятся новые ребра $X_1 T_2$, $X_2 T_A$, $X_2 T_B$, $T_2 T_B$, $T_C T_B$, $T_C T_A$, $T_2 T_1$, $T_3 T_1$, $T_3 Z_1$, $T_C Z_1$, $T_A Z_2$ и появляется новая подклеенная макроплитка $X_1YZ_1T_1$ (рис. 8).

Созданные вершины будем называть подклеенными, причем $T_1$ присваивается глубина $k-1$, а вершинам $T_2$, $T_3$, $T_A$, $T_B$, $T_C$ – глубина $k$. Вершину $T_1$ будем считать угловой, вершины $T_2$, $T_3$ – краевыми, а вершины $T_A$, $T_B$, $T_C$ – внутренними.

Типы вершин ($A$, $B$, $C$, $U$, $UL$ и т. п.) и типы ребер не меняются при проведении подклейки.

Вершину $Y$ будем называть ядром подклейки. Макроплитку, которой принадлежит ядро подклейки, будем называть базовой плоскостью подклейки. Макроплитки, которым принадлежат ребра $YX_1$ и $YZ_1$ (это может быть и одна макроплитка) будем называть макроплитками, к которым подклеивается новая подклеенная область.

При операции подклейки проводятся новые ребра, являющиеся внутренними ребрами в подклеенной макроплитке, а также два граничных ребра – нижнее и правое. Рассмотрим те из проведенных новых ребер, которые одним концом лежат на верхнем и левом ребрах подклеиваемой макроплитки, т. е. тех ребрах, которыми она подклеивается к остальному комплексу. Будем называть их ребрами входа и выхода в данную подклейку. Если путь проходит по такому ребру, то мы будем говорить, что путь вошел в данную подклеенную макроплитку или вышел из нее, в зависимости от направления пути. Заметим, что ребра входа и выхода могут появиться также после разбиения уже подклеенной макроплитки.

Примечание 3.1. Заметим, что в подклеенной макроплитке по построению определяется верхняя, а, следовательно, и остальные стороны: она выглядит так же, как если бы к плитке $X_1YZ_1T_1$ применили разбиение, считая сторону $X_1Y$ верхней. Также можно считать, что в этой макроплитке $T_2$ середина стороны $T_1X_1$, а $T_3$ – середина стороны $T_1Z_1$.

Определение 3.5. Комплексами $1$, $2$ и $3$ уровня будем называть макроплитки соответственно $1$, $2$ и $3$ уровней.

Комплексом $n$ уровня для $n\geqslant 4$ становится комплекс $n-1$ уровня, к которому применены разбиение и затем подклейка.

Иногда мы будем рассматривать плоские части комплекса. Так мы будем называть отдельно рассматриваемые макроплитки, полученные разбиениями изначальной плитки, а также отдельно рассматриваемые подклеенные макроплитки. Плоским путем будем называть путь, полностью лежащий в некоторой макроплитке $T$. Этот путь не содержит ребер, ведущих в подклеенные к $T$ макроплитки, но может содержать ребра, входящие и выходящие на границу $T$.

Замечание 3.2. Начиная с четвертого уровня комплекса (и при построении пятого уровня), путь $X_1YZ_1$ из определения операции подклейки может частично лежать в базовой плоскости, а частично в подклеенной части (если $Z_1$ появилась при предыдущей подклейке в качестве вершины $T_2$ или $T_3$). На больших уровнях комплекса весь путь из определения подклейки может лежать полностью в подклеенных плитках. Таким образом, возникают подклейки к частям подклеенных когда-то макроплиток и так далее, т. е. подклеенная макроплитка подклеивается либо к одной, либо к двум другим макроплиткам (к двум в случае, когда два ребра подклейки принадлежат разным макроплиткам). Заметим также, что уровень обеих этих макроплиток не менее чем на $1$ превосходит уровень подклеиваемой макроплитки.

Замечание 3.3. В итоге мы всегда будем рассматривать комплексы конечного уровня. Предельного перехода применяться не будет.

Лемма 3.1 (об ограниченности роста степени вершины). Для каждой вершины $Z$ существует такое натуральное $N$, что, начиная с уровня макроплитки $N$, степень (число входящих ребер) вершины $Z$ не меняется, т. е. она одинакова для макроплиток уровня $N$ и $N+k$ для любого натурального $k$.

Доказательство. Рассмотрим некоторую плитку $T$. У нее четыре угла: $X$, $Y$, $P$, $Q$ (рис. 9).

При разбиении некоторые углы разбиваются ребрами, а некоторые – нет. Заметим, что левый и правый верхние углы не будут разбиты ребрами, какой бы ни был уровень макроплитки. Действительно, левый верхний угол переходит в себя при разбиении и поэтому никогда не будет разбит ребрами. К правому верхнему углу, на следующем уровне разбиения, меньшая плитка прикладывается левым верхним углом, т. е. и при последующих разбиениях ребер не появится.

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

Итак, внутри каждого угла каждой макроплитки будет проведено, максимум, два ребра.

Разбиение плиток, начиная с некоторого момента, перестает менять степень выбранной вершины. Лемма доказана.

Следствие 3.1. 1) Каждая вершина заданной глубины $x$ выступает в качестве ядра подклейки для ограниченного количества подклеек.

2) В каждую вершину входит ограниченное количество ребер различных уровней, включая ребра из подклеек.

Первое утверждение следует из того, что каждая вершина бывает ядром подклейки только один раз, когда ее глубина на $2$ меньше максимальной глубины. Докажем второе. Для выбранной вершины из ее собственной макроплитки ребер идет конечное число. Ребра одного уровня проводятся в вершину при одновременном создании нескольких подклеек, где данная вершина лежит на ребре подклейки. Таких подклеек одновременно создается конечное число, так как ядра всех этих подклеек находятся на расстоянии $2$ от нашей вершины.

3.2. Нумерация на входящих в вершину ребрах

Для каждой вершины пронумеруем входящие в нее ребра. Нумеруются именно способы входа в вершину, т. е. в случае, если вершина лежит на некоторой стороне или внутреннем ребре макроплитки, эта сторона или ребро даст два входящих в вершину ребра.

Будем делать это сначала для ребер вершин глубины $-1$ и $0$. У таких вершин нет ребер в подклейке. Все плоские ребра можно пронумеровать по уровням. Сначала даем номера всем ребрам самого большого уровня, потом на один меньшего и так далее. При равных уровнях нумеруем по часовой стрелке.

Допустим, что все входящие ребра в вершины глубины $k$ пронумерованы. Пронумеруем все ребра из вершины $X$ глубины $k+1$. Все входящие ребра в ту же плоскость, которой принадлежит вершина $X$, можно опять пронумеровать по уровням, от большего к меньшему, а при равных уровнях – по часовой стрелке. Рассмотрим все ребра, выходящие из $X$ в подклеенные области. Пронумеруем сначала ядра этих областей, от меньшей глубины к большей, при равной глубине сначала боковые и краевые вершины, потом внутренние типа $C$, потом $A$ и $B$. Заметим, что $X$ не может лежать в двух подклейках, ядра которых имеют одну и ту же глубину и одновременно являются боковыми или краевыми, а также внутренними одного типа. Действительно, в этом случае две подклейки возникают одновременно с разными ядрами глубины $n-2$ при максимальной глубине $n$. В этом случае расстояние между ядрами в момент подклейки будет не более $4$. В этом случае ядра не могут одновременно быть внутренними вершинами одного типа или одновременно быть боковыми или краевыми.

Теперь покажем, как пронумеровать ребра для подклеек с одним и тем же ядром. Рассмотрим некоторое ребро $r$ из $X$ в подклеенную область $T$. Эта область (макроплитка) $T$ подклеивается к остальному комплексу по двум своим сторонам, причем $X$ лежит на одной из них. Отметим, что $X$ не может быть ядром данной подклейки, так как ядро по отношению к подклейке является верхней левой вершиной, а из верхней левой вершины макроплитки не выходит внутренних ребер.

Две стороны, по которым подклеивается $T$, являются входящими ребрами в ядро данной подклейки $T$. У ядра подклейки глубина меньше, и нумерация на ребрах уже задана. Поставим в соответствие ребру $r$ номер ребра, соответствующего стороне, на которой $X$ не лежит. Совпадение номеров у ребер $r_1$ и $r_2$ означает, что они идут в одну и ту же подклейку. Фактически мы пронумеровали все подклейки, в которых участвует вершина $X$.

Рассмотрим теперь все ребра в подклейке из $X$, имеющие некоторый одинаковый уровень $s$. Пронумеруем все ребра, соответствующие одинаковому номеру подклейки (входящего в соответствующее ядро ребра, на котором $X$ не лежит). Заметим, что выходящие ребра из вершины на границе макроплитки, если они имеют один уровень, то тогда у них разный тип ребра. Таким образом, у таких ребер разный тип ребра и их можно пронумеровать от меньшего к большему. Далее так нумеруем все ребра для каждого номера подклейки от меньшего к большему.

Проделав эту операцию по очереди для уровней ребра $s$ от большего к меньшему, можно пронумеровать все ребра в выделенную вершину любой заданной глубины.

Лемма 3.2 (о боковых и краевых вершинах). 1) Каждая боковая или краевая вершина лежит на середине стороны в какой-либо макроплитке или в двух макроплитках одного уровня, лежащих в одной плоскости.

2) Если боковая или краевая вершина не находится на границе исходного комплекса первого уровня, то она лежит на одном из восьми внутренних ребер (рис. 7) в некоторой макроплитке, либо лежит на границе подклеенной макроплитки.

Доказательство. В комплексе первого уровня свойство выполняется. На втором уровне также все верно для всех созданных боковых вершин.

Пусть для уровня $k$ комплекса все эти свойства выполнены. Для уже существующих боковых и краевых вершин оба свойства будут сохраняться при дальнейших разбиениях и подклейках. Если новая краевая вершина возникла при подклейке, то это она использовалась в качестве $T_2$ или $T_3$ из определения подклейки, и в качестве макроплитки можно взять как раз подклеенную в тот момент макроплитку. Созданная при разбиении вершина, очевидно, лежит на середине стороны только что разбитой плитки. Если это подклеенное ребро или граница начального комплекса первого уровня, то такая плитка одна (и тогда это граница подклеенной макроплитки, либо всего комплекса), в остальных случаях таких макроплиток две.

Для уровней $1$ и $2$ комплекса заметим, что все стороны плиток, не лежащие на границе, являются частью какого-то большего ребра, классифицируемого, как одного из восьми типов на рис. 7. Заметим, что если боковая вершина лежит на внутреннем ребре определенного типа, то при дальнейших подклейках и разбиениях этот тип не меняется. При этом создаваемые при разбиении внутренние ребра, очевидно, принадлежат одному из этих восьми типов.

Если ребро, при разбиении которого образовалась вершина не является границей для всего комплекса или подклеенной макроплитки, то оно принадлежит одному из восьми типов на рис. 7 для какой-то макроплитки. Значит и вершина тоже принадлежит такому ребру. Лемма доказана.

3.3. Пути на комплексе

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

Путь, идущий по макроплитке, может быть локально преобразован.

Лемма 3.3 (о переброске пути). Пусть $XYZT$ – некоторая макроплитка. Рассмотрим путь $XYZ$ (состоящий из двух соседних макроребер). Тогда, если разрешается менять подпуть из двух соседних ребер любой плитки на подпуть из двух других ребер (с общими началом и концом у этих подпутей), то путь $XYZ$ может быть преобразован в $XTZ$ – путь по другим двум макроребрам.

Доказательство. Будем доказывать по индукции. Для случая, когда макроплитка – это плитка, преобразование можно сделать сразу. Шаг индукции можно совершить, выполняя локальные преобразования по правилам, показанным на рис. 10. Лемма доказана.

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

Определение 3.6. Замены подпутей из пары соседних ребер плитки на подпуть из другой пары будем называть локальными заменами. А возможность с помощью таких замен достичь некоторого состояния, будем называть локальным преобразованием.

Определение 3.7. Будем считать форму пути нулевой, если она содержит подпуть длины $2$ по ребру некоторой минимальной плитки (туда-обратно).

Лемма 3.4 (о выносе пути на границу). Пусть начало и конец пути $P$, проходящего по макроплитке $T$, лежат на границе $T$. Тогда можно реализовать одну из двух возможностей:

1) $P$ может быть локально преобразован в нулевую форму;

2) $P$ может быть локально преобразован в форму $P'$ так, что $P'$ полностью лежит на границе $T$.

Кроме того, любой кратчайший путь, соединяющий противоположные углы или середины противоположных сторон макроплитки, имеет длину $2^n$ и может быть локально преобразован в любой из двух путей по границе (полупериметр) с теми же концами.

Доказательство. Будем доказывать индукцией по уровню макроплитки. Любой путь по минимальной плитке и так лежит на ее границе. Рассмотрим макроплитку уровня $n$ и ее разбиение на $6$ (макро)плиток уровня $n-1$. Путь $P$ разбивается на несколько участков, каждый из которых имеет начало и конец на границе какой-то из этих подплиток. По предположению индукции эти участки можно локально преобразовать в форму $P_1$ так, чтобы весь путь $P_1$ проходил только по границам подплиток.

Замечание 3.4. Символы $L$, $U$, $R$, $D$, $A$, $B$, $C$ обычно обозначают типы вершин. Соответственно, внутри макроплитки крупного уровня может быть несколько вершин, имеющих один и тот же тип. Но в данном предложении макроплитка фиксирована, так что логично для обозначения принадлежащих ей вершин использовать те же буквы.

Обозначим буквами $L$, $U$, $R$, $D$ середины соответственно левой, верхней, правой, нижней сторон $T$, и внутренние вершины – как $A$, $B$, $C$.

Пусть $P_1$ содержит $A$ один раз. Войти и выйти $P_1$ может только по трем ребрам (направленным в сторону $U$, $L$ и $C$). Если вход и выход – по одному ребру, то условие 1) выполнено.

Пусть во входе и выходе задействованы ребра в сторону $U$ и $L$. Если, например, выйти в сторону $L$, то сойти с ребра мы не можем (так как $P_1$ проходит только по границам макроплиток $n-1$ уровня) и вернуться назад тоже (так как тогда будет выполнено 1). Заметим, что тогда $P_1$ содержит подпуть $LAU$ или $UAL$, в обоих случаях этот подпуть согласно лемме о переброске пути можно локально преобразовать, чтобы он проходил по границе макроплитки $T$ и, таким образом, не содержал $A$.

Если во входе и выходе задействованы ребра в сторону $L$ и $C$, то $P_1$ содержит подпуть $LAC$ или $CAL$ и он может быть преобразован в форму соответственно $LXC$ или $CXL$, где $X$ – левый нижний угол, и в этом случае опять форма не будет содержать $A$.

Если во входе и выходе задействованы ребра в сторону $U$ и $C$, то $P_1$ содержит подпуть $UAC$ или $CAU$ и он может быть преобразован в форму соответственно $UBC$ или $CBU$, и тоже форма не будет содержать $A$.

Проделав аналогичные рассуждения для симметричного случая вершины $B$, мы можем заключить, что путь можно преобразовать в форму $P_2$ такую, что она либо вообще не содержит $A$ и $B$, либо содержит кусок $UBC$ или $CBU$ (который может быть преобразован в $UAC$ или $CAU$ соответственно).

Если $P_2$ не содержит $A$ и $B$ и содержит $C$, то войти и выйти из $C$ можно только по ребрам, ведущим в левый нижний и правый нижний углы. В этом случае можно применить лемму о переброске пути для участка, содержащего эти углы и $C$, и получить форму, не содержащую вершин $A$, $B$, $C$.

Пусть $P_2$ содержит кусок $UBC$ или $CBU$. Рассмотрим, как $P_2$ проходит через $C$: один вход (или выход) в сторону $B$, другой не может идти в сторону $A$, так как $P_2$ не содержит $A$, значит, он идет в сторону нижнего левого или нижнего правого угла. Если это нижний правый угол $Y$, то $P_2$ содержит кусок $UBCY$ или $YCBU$. Применяя лемму о переброске путей, $UBCY$ переводится в $UBRY$ и далее в $UZRY$, где $Z$ – правый верхний угол. Аналогично, $YCBU$ переводится в $YRZU$. Если это нижний левый угол $X$, то $P_2$ содержит кусок $UBCX$ или $XCBU$. Аналогично, применяя лемму 3.3 о переброске пути, переводим $UBCX$ в $UACX$ и далее в $UALX$, а потом в $UWLX$, где $W$ – левый верхний угол. Аналогично, $XCBU\Rightarrow XCAU \Rightarrow XLAU \Rightarrow XLWU$.

Таким образом, мы получим форму, не содержащую вершин $A$, $B$, $C$. В этом случае, если нельзя выполнить условие 1), то весь путь проходит по границе $T$, и выполнено условие 2).

Последнее утверждение леммы 3.4 является следствием из первого с учетом леммы о переброске пути. Лемма доказана.

Лемма 3.5 (о “шевелении” пути). Пусть $P$ – путь, состоящий из макроребра $XY$ некоторой макроплитки $T$ уровня не менее $4$. Обозначим середину $XY$ как $H$, середины $XH$ и $HY$ – как $G_1$ и $G_2$. В соответствии с определением подклеек, существует подклеенная макроплитка, три угла которой лежат на макроребре: это $G_1$, $H$ и $G_2$. Тогда $P$ может быть локально преобразован в форму $P'$, состоящую из трех частей: первая – $XG_1$, третья – $G_2Y$, а вторая представляет собой путь по двум соседним ребрам подклеенной макроплитки, два других ребра которой являются частью $P$.

Доказательство. Достаточно проследить разбиение $T$ (на три уровня в глубину). Обозначим середины $G_1H$ и $HG_2$ как $G_3$ и $G_4$. Так как $G_3$ и $G_4$ будут иметь уровень на $2$ больше, чем $H$, значит, была проведена подклейка для пути $G_1G_3HG_4G_2$. Пусть $F$ – созданная при этой подклейке угловая вершина. По лемме о переброске пути, $G_1HG_2$ можно локально преобразовать в $G_1FG_2$. Лемма доказана.

Лемма 3.6 (о выделении локального участка). Пусть $n$ – уровень макроплитки и путь $P$ лежит внутри нее.

1) Пусть оба края $P$ лежат на границе $T$. Тогда если путь $P$ имеет длину не менее $5\times 2^{n-2}$, то он может быть локально преобразован в нулевую форму $P'$.

2) Пусть один край $P$ лежит в углу или на середине стороны $T$, а второй край – внутри $T$ (часть пути может проходить по границе $T$). Тогда если путь $P$ имеет длину $2^{n}$, он может быть локально преобразован в нулевую форму $P'$.

Доказательство. 1) Согласно лемме о выносе на границу можно считать, что весь путь $P$ проходит по границе $T$. Пусть при этом не образовалось нулевой формы, т. е. путь покрывает какую-то часть границы $T$, совершая движение либо по часовой стрелке либо против. Отметим на границе $T$ восемь точек – углы и середины сторон. Заметим, что расстояние между соседними отмеченными точками (углом и серединой стороны) равно $2^{n-2}$. Наш путь включает в себя не менее $5$ из отмеченных точек. Тогда найдутся две отмеченные точки, диаметрально противоположные относительно $T$ и такие, что путь $P$ полностью покрывает половину границы между ними. Заметим при этом, что хотя бы одна из этих отмеченных точек не является концевой для $P$. Пользуясь леммой о переброске (с примечанием), можно перевести подпуть из половины границы на другую половину. Ясно, что получившаяся форма будет нулевой.

2) Будем доказывать индукцией по уровню макроплитки. Для уровней $1$ и $2$ утверждение легко проверяется. Допустим, уровень макроплитки равен $n$, а для меньших $n$ это верно. Будем размечать пути скобками: открывающей скобкой отметим вершину, где путь заходит внутрь некоторой макроплитки, а закрывающей – где выходит. Из всех локально эквивалентных пути $P$ путей выберем такой путь $Q$, в котором меньше всего скобок. Заметим, что подпуть $Q$, начинающийся с открывающей скобки, заканчивающийся закрывающей и не содержащий скобок внутри, попадает под условия леммы о выносе пути на границу и его можно преобразовать в форму, где скобок будет меньше. Также заметим, что один край $Q$ на границе, т. е. первая скобка (если она есть) обязана быть открывающей. Тогда в $Q$ не может быть закрывающих скобок, только открывающие.

Если $Q$ не содержит скобок, то он проходит по границе макроплитки, и тогда оба конца пути лежат на границе, что не так по условию.

Обозначим через $H$ одну из шести подплиток $T$, в которой лежит конец пути $Q$. Заметим, что если путь заходит в какую-либо подплитку, то выйти из нее он уже не может, так как в этом случае в пути будет закрывающая скобка.

Обозначим через $X$ первую вершину на пути, такую что вся оставшаяся часть лежит в $H$. Ясно, что $X$ – один из углов одной из шести подплиток $T$. Разобьем $Q$ на два подпути $Q_1$ и $Q_2$, до и после $X$. Заметим, что $Q_1$ проходит лишь по границам и по внутренним ребрам $T$. Таким образом, можно считать, что $Q_1$ проходит по внутренним ребрам и границам макроплитки второго уровня.

Теперь проверим, что на макроплитке уровня $2$ любой путь $Q_1$, начинающийся на границе, ведущий в подплитку $H$ и не содержащий закрывающих скобок, приводится либо к нулевой форме, либо к виду $S_1S_2$, где $S_1$ имеет длину не более $2$, а $S_2$ лежит в $H$. В силу вышесказанного, достаточно рассмотреть случаи, когда $Q_1$ имеет длину $3$ и оканчивается во внутренней вершине, либо имеет длину $4$ и лежит на границе макроплитки. Требуемое утверждение проверяется перебором путей, подчиняющихся указанным ограничениям, и подплиток $H$, в которых эти пути оканчиваются. Детали перебора предоставляются читателю.

Итак, можно считать, что начальная часть $S_1$ пути не длиннее $2\times 2^{n-2}$. Тогда оставшаяся часть пути лежит в $H$, и в ней можно выбрать кусок длины $2^{n-1}$. К нему можно применить предположение индукции. Лемма доказана.

Лемма 3.7 (о непродолжаемом пути). Рассмотрим некоторую макроплитку $T$, являющуюся подплиткой более крупной макроплитки. Пусть путь $P$ лежит в $T$, причем начало и конец $P$ лежат в серединах противоположных сторон $T$. Тогда любые плоские пути вида $WP$ или $PW$, где длина $W$ более длины $P$, могут быть приведены к нулевой форме.

Доказательство. Случаи $WP$ и $PW$ аналогичны, рассмотрим $PW$. Пусть $a$ – это та сторона $T$, в середине $X$ которой заканчивается $P$ и начинается $W$. Пусть путь, выйдя из $X$, идет внутрь макроплитки $T$ либо по ее стороне $a$. Обозначим через $r$, его первое ребро. Если $r$ уходит внутрь макроплитки $T$, то к пути $Pr$ применима вторая часть леммы о выделении локального участка. Пусть $r$ лежит на стороне. Тогда один из двух путей $Q_1$ или $Q_2$ c теми же концами, что и $P$ (и локально эквивалентных ему по лемме о выносе пути на границу), тоже будет содержать $r$. В этом случае $Q_1r$ или $Q_2r$ содержит ребро, которое проходится туда-обратно.

Значит, из $X$ путь может выйти только в макроплитку $T'$, соседствующую с $T$ по стороне $a$. Допустим, существует вершина $Y$ из пути $W$, лежащая на границе $T'$, отличная от $X$. В этом случае кусок пути $W$ от $X$ до $Y$ может быть локально преобразован так, что он будет проходить по границе $T'$. Но тогда выход этого куска из $X$ будет по стороне $a$, и в этом случае опять можно локально преобразовать $P$, чтобы $PW$ содержал туда и обратно по одному ребру. Если такой вершины $Y$ не найдется, то все остальные вершины $W$ лежат внутри $T'$, т. е. можно воспользоваться леммой о выделении локального участка. Лемма доказана.

Определение 3.8. Пусть $r$ – выходящее ребро из вершины $X$. Пусть $X$ – боковая или краевая вершина, разделяющая некоторые макроплитки $U$ и $W$ (или лежащая на границе некоторой макроплитки $U$). Ребро $r$ называется главным ребром, если оно лежит на границе между $U$ и $W$ (или просто на границе $U$). Если же $X$ – внутренняя вершина в макроплитке $U$, тогда $r$ – главное ребро, если $r$ лежит на одном из внутренних ребер макроплитки $U$.

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

Определение 3.10. Пусть $P$ – некоторый паттерн. В рамках данного определения путь $W$ будем называть достаточно большим путем, содержащим $P$, если выполнены следующие условия:

1) путь $W$ представляется в виде $W_1W_2W_3$, где паттерн $W_2$ есть $P$;

2) длина как $W_1$, так и $W_3$ не менее удвоенной длины $W_2$.

Мертвым будем называть такой паттерн $P$, что любой достаточно большой путь $W$, собственным подпутем которого является путь с паттерном $P$, может быть локально преобразован к нулевой форме.

Лемма 3.8 (о мертвых паттернах). Рассмотрим некоторую макроплитку $T$ и обозначим в ней внутренние вершины $A$, $B$, $C$ и боковые $U$, $R$, $D$, $L$ (аналогично обозначениям при разбиениях). Тогда паттерны $AUB$, $ACB$, $CXD$ (где $X$ – нижняя левая, либо нижняя правая вершина) являются мертвыми.

Доказательство. Пути с паттернами $AUB$ и $ACB$ локально преобразуются друг в друга, так что достаточно рассмотреть один из этих случаев. Пусть $n$ – уровень $T$. Пусть $W_1ACBW_2$ – достаточно большой путь, содержащий подпуть с паттерном $ACB$. Заметим, что длина пути с паттерном $ACB$ равна $2^{n-1}$. Допустим, что $W_1$ не содержит вершин на границе $T$.

Если на $W_1$ есть вершины, лежащие на внутренних ребрах $T$, то участок пути от первой такой вершины $K$ до $A$ может быть локально преобразован так, чтобы он проходил только по внутренним ребрам $T$. Заметим, что таким внутренним ребром может быть только ребро от $A$ до середины левой стороны, в других случаях путь $W_1ACB$ либо будет содержать участок, который он проходит туда, а потом обратно, либо будет содержать подпуть по границе средней подплитки $T$ длиной более $2^{n-1}$, т. е. может быть преобразован к нулевой форме.

Тогда можно считать, что $W_1$ состоит из двух участков $W_{11}$ и $W_{12}$, причем $W_{11}$ проходит внутри левой верхней или левой нижней подплитки $T$, а $W_{12}$ – по ребру от середины левой стороны $T$ до $A$. Длина $W_1$ не менее $2^{n-1}$. Применяя лемму о выделении локального участка, получаем, что путь $W_1$, заканчивающийся в $A$, приводится к нулевой форме.

Итак, пусть теперь $W_1$ и, аналогично, $W_2$ содержат вершины на границе $T$. Рассмотрим разбиение макроплитки $T$ на $6$ дочерних подплиток (в соответствии с операцией разбиения) и будем локально преобразовывать $W$ так, чтобы он проходил по границам этих дочерних подплиток. Тогда из вершины $B$ путь должен идти по ребру к $R$, а в $A$ путь должен входить по ребру из $L$, в остальных случаях образуется обход подплитки по трем ее сторонам (и этот кусок преобразуется к нулевой форме). Таким образом, в $W$ можно выделить подпуть, проходящий по макроплитке $T$, начало которого в $L$ и конец в $R$. Можно воспользоваться леммой о непродолжаемом пути и получить требуемое.

Для паттерна $CXD$ пусть $T'$ – макроплитка, соседняя с $T$ по нижней стороне. Заметим, что выход из вершины $D$ обязательно должен быть внутрь макроплитки $T'$, иначе можно применить лемму о выделении локального участка для нижней дочерней подплитки $T$. Заметим, что длина пути с паттерном $CXD$ равна $2^{n-1}$, где $n$ – уровень $T$ (и $T'$). Дальнейшая часть пути не менее, чем вдвое длиннее, т. е. не менее $2^{n}$. Если далее на пути не встречается вершин на границе $T'$, то можно применить лемму о выделении локального участка. Пусть на пути встретится вершина $Z$ на границе $T'$. Преобразуем кусок $DZ$, чтобы он проходил по периметру $T'$.

Но тогда из $D$ путь $W$ продолжится по граничной между $T$ и $T'$ стороне. Таким образом, теперь опять можно применить лемму о переброске пути для нижней дочерней подплитки $T$ и получить требуемую нулевую форму. Лемма доказана.

Примечание 3.3. Ясно, что и паттерны $BUA$, $BCA$, $DXC$ (где $X$ – нижняя левая, либо нижняя правая вершина) тоже мертвые, доказательство полностью аналогично.

Лемма 3.9 (о мертвых путях в нижней подплитке). Рассмотрим некоторую макроплитку $T$ уровня $n$. Пусть путь $XYZ$ лежит в $T$, причем $Y$ – левый нижний угол $T$, $XY$ лежит на внутреннем ребре, идущем из левого нижнего угла $T$ во внутреннюю вершину $C$, а $YZ$ лежит на нижней стороне $T$. Тогда для любых плоских путей $W_1$, $W_2$, длины которых более $2^{n+1}$, путь $W_1XYZW_2$ можно локально преобразовать к нулевой форме.

Доказательство. Обозначим середину нижней стороны $T$ через $D$. Пусть $T'$ – нижняя подплитка $T$. Рассмотрим некоторый плоский путь $W_1XYZW_2$ c длинами $W_1$, $W_2$, большими $2^{n+1}$. Учитывая длину путей $W_1$ и $W_2$, они имеют вершины на границе макроплиток уровня $n$. Тогда их можно преобразовать так, чтобы они проходили по границам макроплиток уровня $T'$ или выше (не заходя в более мелкие плитки). Ясно, что $W_1$ должен проходить через $C$, а $W_2$ – через $D$, иначе возникает очевидный кусок с нулевой формой. Таким образом, после преобразования путь будет содержать подпуть с паттерном $CXD$, длина которого $2^{n-1}$ и который является мертвым согласно лемме о мертвых паттернах. Следовательно, для указанных $W_1$ и $W_2$ наш путь можно преобразовать к нулевой форме. Лемма доказана.

Замечание 3.5. Доказательство аналогично переносится на случай, когда $Y$ – правый нижний угол и $XY$ идет по внутреннему ребру от $C$.

Определение 3.11. Некорректным участком пути будем называть такой подпуть $XYZ$, что вершина $Y$ лежит на границе некоторой макроплитки $T$, а вершины $X$ и $Z$ лежат внутри $T$ (не на границе).

Лемма 3.10 (о некорректных участках). Пусть существует некорректный участок $XYZ$ в макроплитке $T$ уровня $n$, причем $T$ – минимальная макроплитка, содержащая $XYZ$ в качестве некорректного участка. Тогда для любых плоских путей $W_1$, $W_2$ длины более $2^{n+2}$ путь $W_1XYZW_2$ может быть локально преобразован к нулевой форме.

Доказательство. Пусть $U$ – родительская макроплитка для $T$. Пусть $W_1$ не содержит вершины, лежащей на границе $U$. В силу минимальности выбора $T$ вершина $Y$ лежит в углу либо в середине стороны $T$. Если на $W_1$ нет вершины, лежащей на границе $T$, то к пути $W_1XY$ можно применить лемму о выделении локального участка. Значит, на пути $W_1$ есть вершины, лежащие на внутренних ребрах $U$ (в частности, на границе $T$). Пусть $K$ – первая вершина в $W_1$, лежащая на внутреннем ребре $U$. Тогда по лемме о выносе пути на границу участок пути $W_1XY$ от $K$ до $Y$ может быть локально преобразован так, что он будет проходить только по внутренним ребрам $U$. Заметим, что тогда участок пути $W_1$ от начала до $K$ лежит в некоторой подплитке $U$, обозначим ее $T'$.

Допустим сначала, что $K$ и $Y$ лежат на одном внутреннем ребре (разделяющему $T$ и $T'$). Тогда после преобразования участка от $K$ до $Y$ весь путь от начала $W_1$ до $Y$ лежит в макроплитке $T'$ и заканчивается в середине стороны или в углу. Таким образом, к нему применима лемма о выделении локального участка.

Пусть теперь $K$ и $Y$ лежат на разных внутренних ребрах. Тогда участок от $K$ до $Y$, проходящий по внутренним ребрам $U$, обязан будет пройти через один из концов внутреннего ребра, на котором лежит $K$. Пусть это вершина $F$ (учитывая, что $F$ не на краю $U$, это может быть лишь одна из трех внутренних вершин). Тогда длина участка пути он начала до $F$ меньше $2^n$, иначе к нему применима лемма о выделении локального участка. Тогда длина участка от $F$ до $Y$ более $3\times 2^n$, т. е. более $6$ внутренних ребер $U$. В этом случае, очевидно, что этот участок может быть преобразован к нулевой форме.

Итак, будем считать, что $W_1$ и, аналогично, $W_2$ содержат вершины, лежащие на границе $U$. Тогда, с учетом леммы о выносе пути на границу, пути $W_1$ и $W_2$ внутри $U$ проходят по внутренним ребрам, не менее крупным, чем ребра $XY$ и $YZ$. Кроме того, если вдоль пути встречается вершина на более крупном ребре, то и далее путь проходит по столь же крупным ребрам.

Как уже было сказано выше, вершина $Y$ лежит в углу $T$, либо в середине стороны. Из иерархии разбиений следует, что из всех углов, кроме нижнего левого, и из середины нижней стороны выходит не более одного ребра внутрь $T$, так что $Y$ может лежать только на середине левой, правой или верхней стороны или в левом нижнем углу.

1) Пусть $Y$ – левый нижний угол. Из этого угла внутрь выходят два ребра, оба – к внутренним C-вершинам: одна в макроплитке $T$, другая в нижней дочерней подплитке $T$. То есть путь $XYZ$ попадает под условие леммы о нижней подплитке и все доказано.

2) Пусть $Y$ – середина левой стороны. Из этой вершины выходят три ребра и поэтому есть три варианта расположения пути $XYZ$. В двух случаях можно применить лемму о нижней подплитке. Оставшийся случай изображен на рис. 11.

Из вершины $Z$ дальше путь может пойти:

i) в вершину $B$; в этом случае кусок $BZYX$ по лемме о переброске пути преобразуется в $BXYX$, т. е. в нулевую форму;

ii) в вершину $P$; в этом случае кусок $YZP$ преобразуется в $YDP$ и для участка $XYD$ можно применить лемму о нижней подплитке;

iii) в вершину $A$. Посмотрим, куда путь может пойти дальше. Если это вершина $Q$, то участок $YZAQ$ преобразуется в $YZPQ$ и далее в $YDPQ$, после чего опять можно применить лемму о нижней подплитке. Во втором случае, если путь идет в вершину $U$, то путь $XYZAU$ сразу можно привести к нулевой форме: $XYZAU\to XYZBU \to XYXBU$.

3) Пусть $Y$ – середина правой стороны. Этот случай симметричен второму, только вместо левой верхней подплитки мы имеем дело с правой нижней. Все рассуждения полностью аналогичны второму случаю.

4) Пусть $Y$ – середина верхней стороны. Из этой вершины исходят четыре ребра (рис. 12).

В случае, когда $X$ и $Z$ не лежат на внутреннем ребре типа $1$ (идущем из $Y$ к внутренней вершине $A$ макроплитки $T$), получается ситуация, полностью аналогичная второму и третьему случаям, рассмотренным выше. На этот раз вместо левой верхней подплитки мы имеем дело с правой верхней. Итак, пусть верхняя правая подплитка $T$ – это $T'$ и, ради определенности, $X$ лежит на ребре, уходящем из $Y$ к внутренней вершине $A$ макроплитки $T$, а $Z$ – на одном из трех ребер, попадающих в $T'$ (отмечены пунктиром на рис. 12).

Учитывая соглашение в начале доказательства, получаем, что $W_1$ проходит по внутренним ребрам $T$ или более крупных макроплиток. Тогда либо $W_1XY$ содержит нулевую форму, либо $W_1$ проходит через внутреннюю вершину $A$ макроплитки $T$. Теперь рассмотрим путь $W_2$. Докажем, что этот путь может быть либо приведен к нулевой форме, либо локально преобразован в путь, начинающийся с макроребра $YB$.

В случае, если он начинается с $Z_1$, мы сразу получаем, что $W_2$ проходит через внутреннюю вершину $B$. В случае $Z_3$ путь идет по внутренним ребрам макроплитки, выделенной серым цветом на рис. 12. Таким образом, он может быть локально преобразован и будет проходить через $B$ либо через $C$. В случае $Z_2$ он также проходит через $C$.

В обоих этих случаях далее путь идет по одному из участков $YCA'F$ или $YCB'F$, указанных длинным пунктиром (либо $W_2$ пройдет через $B$, либо будет может быть приведен к нулевой форме).

Таким образом, $W_2$ теперь проходит через вершину $F$. Пусть $W_2$ покидает макроплитку $T$, уходя в соседнюю макроплитку по правой стороне (короткий пунктир). Тогда длина оставшейся части $W_2$ (после $F$) более, чем $2^{n+2}-2^{n+1}=2^{n+1}$. При этом эта часть пути $W_2$ оказывается внутри макроплитки, такой же по уровню, что и $T'$ и начинается в середине ее стороны. Тогда к этой части пути применима лемма о выделении локального участка и лемма о вынесении пути на границу, что сводит доказательство к рассматриваемым ниже случаям.

Если из $F$ путь $W_2$ идет к вершине $Q$, то оба возможных куска $YCA'FQ$ и $YCB'FQ$ по лемме о выносе пути на границу приводятся к виду $YQFQ$, т. е. к нулевой форме. Если путь из $F$ идет в $S$, то кусок $YCA'FS$ (или $YCBFS$) приводится к $YDBRS$ по лемме о переброске пути, применяемой последовательно для кусков этого пути.

Итак, $W_1$ проходит через внутреннюю вершину $A$ макроплитки $T$, а $W_2$ – через внутреннюю вершину $B$. Теперь получившийся путь имеет подпуть с мертвым паттерном $AUB$. Заметим теперь, что оставшиеся участки путей $W_1$ и $W_2$ превосходят требуемые в определении мертвого паттерна. Таким образом, мы можем применить лемму о мертвых паттернах и привести путь $W_1XYZW_2$ к нулевой форме. Лемма 3.10 доказана.

Примечание 3.4. Рассуждения не сильно меняются, если рассмотренная макроплитка $T$ имеет уровень $3$ или меньше. В этом случае вершина $Z_1$ совпадает с $D$, а $Z_3$ с $C$.

Лемма 3.11 (о корректности путей). Предположим, что путь $P$ представляет собой проход по двум соседним сторонам некоторой макроплитки $T$. Тогда любые локальные преобразования не могут привести $P$ к нулевой форме, а также к форме, содержащей некорректный участок.

Доказательство. Сначала покажем, что $P$ не приводится к нулевой форме. Для двух точек комплекса определено расстояние как наименьшая из длин соединяющих их путей. Докажем, что путь, проходящий по двум соседним сторонам макроплитки, является кратчайшим для вершин в его концах. Действительно, для плитки уровня $n$ кратчайший путь можно вынести на периметр, применяя соответствующую лемму. Путь по периметру соединяющий противоположные точки, имеет длину $2^n$.

Локальные преобразования не меняют длину пути. В случае, если после очередного преобразования появляется нулевая форма, путь не может быть кратчайшим.

Допустим теперь, что наш путь по двум сторонам макроплитки уровня $n$ можно привести к форме, содержащей некорректный участок $XYZ$.

Пусть $P$ соединяет левый нижний угол с правым верхним. Тогда $T$ вкладывается в макроплитку уровня $n+1$ в качестве левой верхней, при этом $P$ является подпутем аналогичного пути из левого верхнего угла в правый верхний в более крупной макроплитке. Операцию вложения макроплитки в более крупную можно повторить любое число раз. Если $P$ соединяет правый нижний угол с левым верхним, то $T$ можно вложить в макроплитку уровня $n+1$ в качестве нижней подплитки. Пусть $P$ становится частью пути из левого нижнего угла в правый верхний. Далее вложения можно делать как для случая выше.

Итак, $P$ является подпутем сколь угодно протяженного от него в обе стороны пути $P'$, идущего по сторонам достаточно большой макроплитки и соединяющего ее левый нижний и правый верхний углы. По лемме о некорректных участках, если $P$ приводится к пути, содержащему некорректный участок, то $P'$ приводится к нулю. Но это невозможно, как уже показано выше. Лемма доказана.

Замечание 3.6. Можно показать, что путь по двум соседним сторонам макроплитки после любого числа преобразований имеет форму $W_1UW_2$, где пути $W_1$, $W_2$ (которые могут быть просто одной вершиной) полностью лежат на границах макроплитки, причем у подпути $U$ концы лежат на границе, а все остальные вершины лежат строго внутри.

Лемма 3.12 (о расстоянии от края до выхода в подклейку). Пусть вершина $X$ лежит на краю некоторой макроплитки $T$, принадлежащей комплексу $K$, вершина $Y$ принадлежит $T$, но не находится на ее границе, а из $Y$ существует выход в подклеенную макроплитку уровня $n \geqslant 2$, не содержащую вершин на границе $T$. Тогда расстояние от $X$ до $Y$ в комплексе $K$ (длина кратчайшего пути по ребрам) не менее $2^{n-1}$.

Доказательство. Сначала заметим, что для любых вершин $X$ и $Y$ на комплексе операция подклейки не меняет расстояния между ними, понимаемого в смысле количества ребер графа в кратчайшем соединяющем пути. Действительно, если $X$ и $Y$ после подклейки оказываются соединенными более коротким путем. Каждый его подпуть, соединяющий две точки на границах подклеенной макроплитки, может быть локально преобразован в подпуть, не заходящий внутрь этой подклейки, согласно лемме о вынесении пути на границу. В этом случае более короткий путь существует и до подклейки.

Вернемся к утверждению леммы. Проведем доказательство индукцией по уровню макроплитки $T$. Для уровней $2$ и $3$ подклеек внутри $T$ не проводится. Для уровня $4$ ближайшая вершина с подклеенным ребром в макроплитку, не содержащую $X$, лежит в середине любого ребра, выходящего на середину любого из граничных ребер. Расстояние от нее до границы $T$ будет равно $2$, при этом подклеенная макроплитка будет иметь уровень $2$.

Пусть уровень $T$ равен $k\,{>}\,4$. Возьмем кратчайший путь $XWY$. Можно считать, что $W$ не содержит вершин на границе $T$. Кроме того, можно считать, что $Y$ не лежит внутри какой-то из подплиток $T$, иначе $X$ можно взять на границе этой подплитки. Значит, $Y$ обязательно лежит на одном из ребер, которые разделяют макроплитку $T$ на $6$ макроплиток при разбиении. Опять используя минимальность пути, замечаем, что $Y$ лежит в углу подклеенной макроплитки. Из определения подклейки получаем, что уровень $Y$ был на $1$ меньше максимального в тот момент, когда эта подклейка производилась. Если после этого разбиений не было, то расстояние $XY$ не менее $2$, а также макроплитка при $Y$ – второй уровень. Если после этого провели $l\geqslant 1$ разбиений, расстояние $XY$ увеличилось в $2^l$ раз, а уровень макроплитки при $Y$ возрос на $l$. Учитывая, что подклейки не меняют расстояний между точками, это завершает доказательство. Лемма доказана.

Лемма 3.13 (об ограниченности пути, уходящего в подклеенную часть). 1) Предположим, что путь $P$ имеет вид $V_1AV_2BV_3CV_4$, где ребра из вершин $A$, $B$, $C$ ведут в подклеенные области, а участки $V_1$, $V_2$, $V_3$, $V_4$ являются плоскими. Тогда путь $P$ не может быть плоским (лежать в одной макроплитке).

2) Предположим, что путь $P$ начинается в вершине $X$, выход из $X$ идет в подклеенную макроплитку уровня $n$. Кроме того, пусть $P$ не содержит ребер-выходов из подклеенных плиток. Тогда, если длина пути не менее $2^{n+1}$, то он может быть приведен к нулевой форме.

Доказательство. 1) Допустим, что путь проходит в подклеенной макроплитке $T$. Тогда $T$ – та макроплитка, куда уходит ребро из $C$. Таким образом, путь от $A$ до $C$ проходит по краю $T$. Рассмотрим макроплитку (или две макроплитки), к которой подклеивается $T$. Тогда путь от начала до $C$ проходит по этой одной или двум макроплиткам, при этом два раза проходит по ребру в подклеенную область, что невозможно. (Один переход возможен при переходе от одной макроплитке к другой.)

2) Пусть $X_i$ – вершины $P$, где происходят входы в подклеенные макроплитки $T_i$ и $X_1$ – это $X$. Пусть их всего $s$. Предположим, что уровень $T_i$ равен $n_i$, $n_1=n$. Учитывая, что уровень подклеенной макроплитки, как минимум, на $1$ меньше, чем уровень каждой из макроплиток, к которым она подклеивается, получаем $n_1>n_2>\dots >n_s$.

По лемме о выделении локального участка длина $X_i X_{i+1}$ менее $2^{n_i}$. Тогда суммарная длина пути $P$ меньше, чем $2^n+2^{n-1}+\dots+ 2^3+2^2<2^{n+1}$. Лемма доказана.

Список литературы
1. E. I. Zelmanov, “On the nilpotency of nil algebras”, Algebra – some current trends (Varna, 1986), Lecture Notes in Math., 1352, Springer, Berlin, 1988, 227–240  crossref  mathscinet  zmath
2. W. Burnside, “On an unsettled question in the theory of discontinuous groups”, Q. J. Pure Appl. Math., 33 (1902), 230–238  zmath
3. И. Н. Санов, “Решение проблемы Бернсайда для показателя $4$”, Уч. зап. Ленингр. ун-та. Сер. матем., 10 (1940), 166–170  mathscinet  zmath
4. M. Hall, Jr., “Solution of the Burnside problem for exponent $6$”, Proc. Nat. Acad. Sci. U.S.A., 43 (1957), 751–753  crossref  mathscinet  zmath  adsnasa
5. Е. С. Голод, “О ниль-алгебрах и финитно-аппроксимируемых $p$-группах”, Изв. АН СССР. Сер. матем., 28:2 (1964), 273–276  mathnet  mathscinet  zmath; англ. пер.: E. S. Golod, “On nil-algebras and finitely approximable $p$-groups”, Amer. Math. Soc. Transl. Ser. 2, 48, Amer. Math. Soc., Providence, RI, 1965, 103–106  crossref
6. Е. С. Голод, И. Р. Шафаревич, “О башне полей классов”, Изв. АН СССР. Сер. матем., 28:2 (1964), 261–272  mathnet  mathscinet  zmath; англ. пер.: E. S. Golod, I. R. Šafarevič, “On class field towers”, Amer. Math. Soc. Transl. Ser. 2, 48, Amer. Math. Soc., Providence, RI, 1965, 91–102  crossref
7. П. С. Новиков, С. И. Адян, “О бесконечных периодических группах. I”, Изв. АН СССР. Сер. матем., 32:1 (1968), 212–244  mathnet  mathscinet  zmath; II:2, 251–524  mathnet  mathscinet  zmath; III:3, 709–731  mathnet  mathscinet  zmath; англ. пер.: P. S. Novikov, S. I. Adian, “Infinite periodic groups. I”, Math. USSR-Izv., 2:1 (1968), 209–236  crossref; II:2, 241–479  crossref; III:3, 665–685  crossref
8. С. И. Адян, Проблема Бернсайда и тождества в группах, Наука, М., 1975, 335 с.  mathscinet  zmath; англ. пер.: S. I. Adian, The Burnside problem and identities in groups, Ergeb. Math. Grenzgeb., 95, Springer-Verlag, Berlin–New York, 1979, xi+311 с.  mathscinet  zmath
9. С. И. Адян, “Проблема Бернсайда и связанные с ней вопросы”, УМН, 65:5(395) (2010), 5–60  mathnet  crossref  mathscinet  zmath; англ. пер.: S. I. Adian, “The Burnside problem and related topics”, Russian Math. Surveys, 65:5 (2010), 805–855  crossref  adsnasa
10. С. И. Адян, “Новые оценки нечетных периодов бесконечных бернсайдовых групп”, Избранные вопросы математики и механики, Сборник статей. К 150-летию со дня рождения академика Владимира Андреевича Стеклова, Труды МИАН, 289, МАИК «Наука/Интерпериодика», М., 2015, 41–82  mathnet  crossref  mathscinet  zmath; англ. пер.: S. I. Adian, “New estimates of odd exponents of infinite Burnside groups”, Proc. Steklov Inst. Math., 289 (2015), 33–71  crossref
11. А. Ю. Ольшанский, “О теореме Новикова–Адяна”, Матем. сб., 118(160):2(6) (1982), 203–235  mathnet  mathscinet  zmath; англ. пер.: A. Yu. Ol'shanskiĭ, “On the Novikov–Adyan theorem”, Math. USSR-Sb., 46:2 (1983), 203–236  crossref  adsnasa
12. А. Ю. Ольшанский, Геометрия определяющих соотношений в группах, Современная алгебра, Наука, М., 1989, 448 с.  mathscinet  zmath; англ. пер.: A. Yu. Ol'shanskii, Geometry of defining relations in groups, Math. Appl. (Soviet Ser.), 70, Kluwer Acad. Publ., Dordrecht, 1991, xxvi+505 с.  crossref  mathscinet  zmath
13. И. Г. Лысёнок, “Бесконечность бернсайдовых групп периода $2^k$ при $k > 13$”, УМН, 47:2(284) (1992), 201–202  mathnet  mathscinet  zmath; англ. пер.: I. G. Lysenok, “The infinitude of Burnside groups of period $2^k$ for $k \geq 13$”, Russian Math. Surveys, 47:2 (1992), 229–230  crossref
14. И. Г. Лысёнок, “Бесконечные бернсайдовы группы четного периода”, Изв. РАН. Сер. матем., 60:3 (1996), 3–224  mathnet  crossref  mathscinet  zmath; англ. пер.: I. G. Lysenok, “Infinite Burnside groups of even exponent”, Izv. Math., 60:3 (1996), 453–654  crossref  adsnasa
15. S. V. Ivanov, “The free Burnside groups of sufficiently large exponents”, Internat. J. Algebra Comput., 4:1-2 (1994), 1–308  crossref  mathscinet  zmath
16. S. V. Ivanov, “On the Burnside problem on periodic groups”, Bull. Amer. Math. Soc. (N.S.), 27:2 (1992), 257–260  crossref  mathscinet  zmath
17. А. И. Ширшов, “О некоторых неассоциативных ниль-кольцах и алгебраических алгебрах”, Матем. сб., 41(83):3 (1957), 381–394  mathnet  mathscinet  zmath
18. А. И. Ширшов, “О кольцах с тождественными соотношениями”, Матем. сб., 43(85):2 (1957), 277–283  mathnet  mathscinet  zmath
19. A. Belov-Kanel, L. H. Rowen, “Perspectives on Shirshov's Height theorem”, Selected works of A. I. Shirshov, Contemp. Mathematicians, Birkhäuser Verlag, Basel, 2009, 185–202  crossref  mathscinet  zmath
20. A. R. Kemer, “Comments on Shirshov's Height theorem”, Selected works of A. I. Shirshov, Contemp. Mathematicians, Birkhäuser Verlag, Basel, 2009, 223–229  crossref  mathscinet  zmath
21. А. Я. Белов, “Проблемы бернсайдовского типа, теоремы о высоте и о независимости”, Фундамент. и прикл. матем., 13:5 (2007)  mathnet  mathscinet  zmath; англ. пер.: A. Ya. Belov, “Burnside-type problems, theorems on height, and independence”, J. Math. Sci. (N.Y.), 156:2 (2009), 219–260  crossref
22. А. Я. Белов, М. И. Харитонов, “Субэкспоненциальные оценки в теореме Ширшова о высоте”, Матем. сб., 203:4 (2012), 81–102  mathnet  crossref  mathscinet  zmath; англ. пер.: A. Ya. Belov, M. I. Kharitonov, “Subexponential estimates in Shirshov's theorem on height”, Sb. Math., 203:4 (2012), 534–553  crossref  adsnasa
23. А. И. Кострикин, Вокруг Бернсайда, Наука, М., 1986, 232 с.  mathscinet  zmath; англ. пер.: A. I. Kostrikin, Around Burnside, Ergeb. Math. Grenzgeb. (3), 20, Springer-Verlag, Berlin, 1990, xii+220 с.  crossref  mathscinet  zmath
24. M. V. Sapir, Combinatorial algebra: syntax and semantics, With contributions by V. S. Guba, M. V. Volkov, Springer Monogr. Math., Springer, Cham, 2014, xvi+355 pp.  crossref  mathscinet  zmath
25. A. Yu. Ol'shanskii, M. V. Sapir, “Non-amenable finitely presented torsion-by-cyclic groups”, Publ. Math. Inst. Hautes Études Sci., 96, no. 1, 2003, 43–169  crossref  mathscinet  zmath
26. T. Gateva-Ivanova, V. Latyshev, “On recognizable properties of associative algebras”, [J. Symbolic Comput., 6:2-3 (1988), 371–388], Computational aspects of commutative algebras, Academic Press, London, 1988, 237–254  crossref  mathscinet  zmath
27. Днестровская тетрадь. Нерешенные проблемы теории колец и модулей, 4-е изд., ред. В. Т. Филиппов, В. К. Харченко, И. П. Шестаков, ИМ СО РАН, Новосибирск, 1993, 74 с.  mathscinet  zmath; англ. пер.: “Dniester notebook: unsolved problems in the theory of rings and modules”, Non-associative algebra and its applications, Lect. Notes Pure Appl. Math., 246, ред. V. T. Filippov, I. P. Shestakov, V. K. Kharchenko, Chapman & Hall/CRC, Boca Raton, FL, 2006, 461–516  mathscinet  zmath
28. G. Kukin, “The variety of all rings has Higman's property”, Algebra and analysis (Irkutsk, 1989), Amer. Math. Soc. Transl. Ser. 2, 163, Amer. Math. Soc., Providence, RI, 1995, 91–101  crossref  mathscinet  zmath
29. В. Я. Беляев, “Вложимость рекурсивно определенных инверсных полугрупп в конечно определенные”, Сиб. матем. журн., 25:2 (1984), 50–54  mathnet  mathscinet  zmath; англ. пер.: V. Ya. Belyaev, “Embedding recursively defined inverse semigroups in finitely presented semigroups”, Siberian Math. J., 25:2 (1984), 207–210  crossref
30. В. А. Уфнаровский, “О росте алгебр”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 1978, № 4, 59–65  mathscinet  zmath; англ. пер.: V. A. Ufnarovskii, “The growth of algebras”, Moscow Univ. Math. Bull., 33:4 (1978), 47–52
31. В. В. Щиголев, “О ниль и нильпотентных конечноопределённых алгебрах”, Фундамент. и прикл. матем., 6:4 (2000), 1239–1245  mathnet  mathscinet  zmath
32. Н. К. Иыуду, Стандартные базисы и распознаваемость свойств алгебр, заданных копредставлением, Дисс. … канд. физ.-матем. наук, МГУ, М., 1996, 73 с.
33. И. А. Иванов-Погодаев, “Алгебра с конечным базисом Грёбнера и неразрешимой проблемой делителей нуля”, Фундамент. и прикл. матем., 12:8 (2006), 79–96  mathnet  mathscinet  zmath; англ. пер.: I. A. Ivanov-Pogodaev, “Finite Gröbner basis algebra with unsolvable problem of zero divisors”, J. Math. Sci. (N.Y.), 152:2 (2008), 191–202  crossref
34. Д. И. Пионтковский, “Некоммутативные базисы Грёбнера, когерентность ассоциативных алгебр и делимость в полугруппах”, Фундамент. и прикл. матем., 7:2 (2001), 495–513  mathnet  mathscinet  zmath
35. Д. И. Пионтковский, “Базисы Грёбнера и когерентность мономиальной ассоциативной алгебры”, Фундамент. и прикл. матем., 2:2 (1996), 501–509  mathnet  mathscinet  zmath
36. В. А. Уфнаровский, “Комбинаторные и асимптотические методы в алгебре”, Алгебра – 6, Итоги науки и техн. Сер. Соврем. пробл. мат. Фундам. направления, 57, ВИНИТИ, М., 1990, 5–177  mathnet  mathscinet  zmath; англ. пер.: V. A. Ufnarovskij, “Combinatorial and asymptotic methods in algebra”, Algebra VI, Encyclopaedia Math. Sci., 57, Springer, Berlin, 1995, 1–196
37. А. Я. Белов, “Линейные рекуррентные уравнения на дереве”, Матем. заметки, 78:5 (2005), 643–651  mathnet  crossref  mathscinet  zmath; англ. пер.: A. Ya. Belov, “Linear recurrence equations on a tree”, Math. Notes, 78:5 (2005), 603–609  crossref
38. L. A. Bokut', G. P. Kukin, Algorithmic and combinatorial algebra, Math. Appl., 255, Kluwer Acad. Publ., Dordrecht, 1994, xvi+384 pp.  crossref  mathscinet  zmath
39. M. V. Sapir, “Algorithmic problems for amalgams of finite semigroups”, J. Algebra, 229:2 (2000), 514–531  crossref  mathscinet  zmath
40. Нерешенные задачи теории полугрупп, Свердловская тетрадь, № 3, Урал. гос. ун-т, Свердловск, 1989, 40 с.
41. O. G. Kharlampovich, M. V. Sapir, “Algorithmic problems in varieties”, Internat. J. Algebra Comput., 5:4-5 (1995), 379–602  crossref  mathscinet  zmath
42. A. Ya. Belov, I. A. Ivanov, “Construction of semigroups with some exotic properties”, Comm. Algebra, 31:2 (2003), 673–696  crossref  mathscinet  zmath
43. A. Ya. Belov, I. A. Ivanov, “Construction of semigroups with some exotic properties”, Acta Appl. Math., 85:1-3 (2005), 49–56  crossref  mathscinet  zmath
44. I. Ivanov-Pogodaev, S. Malev, “Finite Gröbner basis algebras with unsolvable nilpotency problem and zero divisors”, J. Algebra, 508 (2018), 575–588  crossref  mathscinet  zmath
45. I. Ivanov-Pogodaev, S. Malev, O. Sapir, “A construction of a finitely presented semigroup containing an infinite square-free ideal with zero multiplication”, Internat. J. Algebra Comput., 28:8 (2018), 1565–1573  crossref  mathscinet  zmath
46. И. А. Иванов-Погодаев, Машина Минского, свойства нильпотентности и размерность Гельфанда–Кириллова в конечно-определенных полугруппах, Дисс. … канд. физ.-матем. наук, МГУ, М., 2006, 77 с.
47. A. Belov, I. Ivanov-Pogodaev, “Construction of finitelly presented Nill but not nilpotent semigroup”, International conference on algebra and related topics (ICCA) (Guangzhou, 2009), The Center of Combinatorial Algebra, South China Normal Univ., 2009, 18
48. A. Belov-Kanel, I. Ivanov-Pogodaev, Finitely presented nil-semigroups and aperiodic tilings, CIRM, SubTile 2013 Pavages: systèmes dynamiques, combinatoire, théorie des nombres, décidabilité, géométrie discrète, géométrie non-commutative (Marseille, 2013) http://subtile2013.sciencesconf.org/conference/subtile2013/pages/Kanel_Belov_1.ppt
49. A. Ya. Belov, I. A. Ivanov-Pogodaev, “Construction of finitely presented infinite nil-semigroup”, Classical aspects of ring theory and module theory. Abstracts (Bedlewo, 2013), Stefan Banach International Mathematical Center, 2013, 14
50. И. А. Иванов-Погодаев, А. Я. Белов, “Построение конечно определенной ниль-полугруппы”, Алгебра и теория чисел: современные проблемы и приложения (Тула, 2014), Тул. гос. пед. ун-т им. Л. Н. Толстого, Тула, 2014, 30
51. A. Belov-Kanel, I. Ivanov-Pogodaev, “Construction of infinite finitely presented nilsemigroup”, Groups and rings, theory and applications, GRiTA2015 (Sofia, 2015), Institute of Mathematics and Informatics of the Bulgarian Academy of Sciences, Sofia, 2015, 10
52. A. Belov-Kanel, I. Ivanov-Pogodaev, “Construction of infinite finitely presented nilsemigroup”, First joint international meeting of the Israel mathematical union and the Mexican mathematical society (Oaxaca, 2015), Instituto Tecnologico de Oaxaca, 2015, 13
53. A. J. Belov, V. V. Borisenko, V. N. Latyshev, Monomial algebras, Plenum, New York, NY, 1998
54. Н. К. Иыуду, “Алгоритмическая разрешимость проблемы распознавания делителей нуля в одном классе алгебр”, Фундамент. и прикл. матем., 1:2 (1995), 541–544  mathnet  mathscinet  zmath
55. R. Berger, The undecidability of the domino problem, Ph.D. thesis, Harvard Univ., 1964  mathscinet
56. R. M. Robinson, “Undecidability and nonperiodicity for tilings of the plane”, Invent. Math., 12 (1971), 177–209  crossref  mathscinet  zmath  adsnasa
57. C. Goodman-Strauss, “Matching rules and substitution tilings”, Ann. of Math. (2), 147:1 (1998), 181–223  crossref  mathscinet  zmath
58. N. Bédaride, Th. Fernique, “When periodicities enforce aperiodicity”, Comm. Math. Phys., 335:3 (2015), 1099–1120  crossref  mathscinet  zmath  adsnasa
59. Wang Hao, “Proving theorems by pattern recognition – II”, Bell System Tech. J., 40:1 (1961), 1–41  crossref
60. T. Fernique, И. Иванов-Погодаев, А. Белов, И. Митрофанов, Апериодичные замощения [Aperiodic tilings], 25-я летняя конференция международного математического Турнира городов (Боровка, Беларусь, 2013), 2013 http://www.turgor.ru/lktg/2013/2/index.htm; англ. пер.: T. Fernique, I. Ivanov-Pogodaev, A. Belov, I. Mitrofanov, Aperiodic tilings, 25 summer conference International mathematical Tournament of towns (Borovka, Belarus, 2013) http://www.turgor.ru/lktg/2013/2/index.htm; И. Иванов-Погодаев, А. Канель-Белов, И. Митрофанов, Т. Ферник, Апериодические замощения http://lipn.univ-paris13.fr/~fernique/info/turgorod_rus2.pdf
61. J. H. Conway, J. C. Lagarias, “Tiling with polyominoes and combinatorial group theory”, J. Combin. Theory Ser. A, 53:2 (1990), 183–208  crossref  mathscinet  zmath
62. А. Я. Белов-Канель, И. Иванов-Погодаев, А. Малистов, И. Митрофанов, М. Харитонов, Замощения, раскраски и плиточные группы, 21-я летняя конференция международного математического Турнира городов (Теберда, 2009), 2009 http://www.turgor.ru/lktg/2009/4/index.php; англ. пер.: A. Belov-Kanel, I. Ivanov-Pogodaev, A. Malistov, I. Mitrofanov, M. Kharitonov, Pavements, colorings and tiling groups, 21-th summer conference International mathematical Tournament of towns (Teberda, 2009), 2009 http://www.turgor.ru/lktg/2009/4/index.php
Образец цитирования: И. А. Иванов-Погодаев, А. Я. Канель-Белов, “Конечно определенная нильполугруппа: комплексы с равномерной эллиптичностью”, Изв. РАН. Сер. матем., 85:6 (2021), 126–163; Izv. Math., 85:6 (2021), 1146–1180
Цитирование в формате AMSBIB
\RBibitem{IvaKan21}
\by И.~А.~Иванов-Погодаев, А.~Я.~Канель-Белов
\paper Конечно определенная нильполугруппа: комплексы с равномерной эллиптичностью
\jour Изв. РАН. Сер. матем.
\yr 2021
\vol 85
\issue 6
\pages 126--163
\mathnet{http://mi.mathnet.ru/im8978}
\crossref{https://doi.org/10.4213/im8978}
\zmath{https://zbmath.org/?q=an:1497.20060}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2021IzMat..85.1146I}
\transl
\jour Izv. Math.
\yr 2021
\vol 85
\issue 6
\pages 1146--1180
\crossref{https://doi.org/10.1070/IM8978}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000745286400001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85124245900}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/im8978
  • https://doi.org/10.4213/im8978
  • https://www.mathnet.ru/rus/im/v85/i6/p126
    • Эта публикация цитируется в следующих 3 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Статистика просмотров:
    Страница аннотации:604
    PDF русской версии:51
    PDF английской версии:24
    HTML русской версии:186
    Список литературы:27
    Первая страница:7
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024