Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 491, № 1, стр. 5-10

1. ПЛАН ДОКАЗАТЕЛЬСТВА

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

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

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

Имея построенную последовательность комплексов, далее будем действовать по следующему плану:

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

2. Вторую серию букв алфавита введем для всевозможных входящих и выходящих ребер во все вершины.

3. Теперь последовательность букв (слово) может кодировать последовательность вершин, которые мы проходим вдоль пути, лежащем на произвольном комплексе. Выпишем все последовательности букв длины 7, которые не представляют никакого пути ни на одном из комплексов. Занесем все такие последовательности в список запрещенных и объявим их нулями, введя соответствующие определяющие соотношения.

4. Рассмотрим произвольную плитку T. Существует два кратчайших пути, соединяющих ее противоположные вершины – по двум соседним сторонам или по двум другим соседним сторонам. Такую пару путей объявим эквивалентными. Проделаем эту операцию для всехвозможных комбинаций 4 цветов вершин, составляющих плитку. Для каждой плитки вводятся две пары эквивалентных путей. Всего мы вводим конечное число таких эквивалентностей, так как существует конечное множество типов плиток. Отметим, что последовательность, кодирующая указанные пути, имеет длину 7: вершина A, выходящее ребро, входящее ребро, вершина B, выходящее ребро, входящее ребро, вершина C. Для каждой такой пары эквивалентных путей мы вводим соответствующее определяющее соотношение для кодирующих их слов.

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

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

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

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

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

10. Таким образом, с последовательностью комплексов будет связана конечно определенная полугруппа, где словам соответствуют пути. Слова A и B равны в полугруппе, если существует цепочка локальных эквивалентностей слов A = A₁ ≡ ≡ A₂ ≡ ... A_k = B, такая, что для каждого $i < k$ можно выбрать комплекс из последовательности и два пути $C$ и $D$ на нем с одинаковыми началом и концом, причем:

1) кодировка $C$ соответствует слову ${{A}_{i}}$, кодировка D соответствует ${{A}_{{i + 1}}}$;

2) путь $D$ получается из $C$ заменой одного эквивалентного участка на другой.

Такая полугруппа будет конечно определенной и бесконечной нильполугруппой.

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

1. Локальная конечность. Каждый комплекс семейства состоит из конечного числа 4-циклов (плиток), соединенных друг с другом по сторонам. Узлы – это вершины плиток, существует конечное число типов узлов и конечное число типов выходящих из них ребер.

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

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

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

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

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

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

1.3. Основные составные части доказательства.

Определение 1. Макроплиткой ${{T}_{n}}$ уровня $n$ будем называть:

для n = 1 – простой цикл, состоящий из 4 вершин и 4 ребер, среди ребер мы выделяем верхнее, правое, левое и нижнее, в соответствии с естественной ориентацией;

для n > 1 – макроплитку ${{T}_{{n - 1}}}$, к которой применена операция разбиения: каждая ориентированная макроплитка 1-го уровня, из которой состоит ${{T}_{{n - 1}}}$, разбивается на шесть макроплиток 1-го уровня, ориентированных в соответствии со схемой на левой стороне рис. 1. Стрелками показаны верхние ребра в каждой из шести макроплиток разбиения. При разбиении образуется 7 вершин. Три из них – внутри первоначальной плитки, будем говорить, что они имеют типы $A$, $B$ и $C$. Еще четыре образуются на серединах верхней, правой, нижней и левой сторон: $U$, $R$, $D$, $L$ соответственно.

В соответствии со схемой иерархического разбиения, при переходе от ${{T}_{n}}$ к ${{T}_{{n + 1}}}$ добавляется несколько вершин. Некоторые вершины являются общими для соседних макроплиток, прилегающих друг к другу по стороне. Все вершины в макроплитке, кроме изначальных четырех (углов), создаются при каком-либо из разбиений.

Таким образом, макроплитка ${{T}_{n}}$ состоит из ${{6}^{{n - 1}}}$ макроплиток 1-го уровня, прилегающих друг к другу в соответствии с иерархической схемой.

Определение 2. Проводимые при разбиении ребра будем называть внутренними ребрами, принадлежащими разбиваемой макроплитке. Уровнем ребра будем называть уровень макроплитки, которой оно принадлежит. Будем считать, что изначальные четыре вершины (углы) имеют глубину, равную –1. Создаваемые при первом разбиении вершины $A$, $B$, $C$, $U$, $L$, $R$, $D$ имеют глубину 0. Определим глубину новых вершин. Все создаваемые при разбиении вершины получают глубину на 1 больше, чем максимальная глубина вершины до разбиения. Из построения ясно, что у любого ребра макроплитки хотя бы один из концов является вершиной, созданной на предыдущем шаге. Следовательно, создаваемая вершина в середине ребра получает глубину на 1 большую, чем максимальная глубина двух концов ребра. Типами внутренних ребер будем называть 8 видов ребер, образующихся при разбиениях, они отмечены как 1–8 на левой части рис. 1. Есть также 4 типа граничных ребер: левое, правое, верхнее и нижнее. Граничные ребра комплекса относятся к этим типам. К ним же относятся границы подклеенных макроплиток (см. ниже).

Определение 3. Определим операцию подклейки.

Мы рассматриваем все пути ${{X}_{1}}{{X}_{2}}Y{{Z}_{2}}{{Z}_{1}}$ из пяти вершин (и четырех ребер), такие что:

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

2) вершины ${{X}_{1}}$, ${{Z}_{1}}$ являются боковыми вершинами глубины $k - 1$, где $k$ – максимальная глубина вершины;

3) вершины X₂ является серединой ${{X}_{1}}Y$, а ${{Z}_{2}}$ – серединой ${{Z}_{1}}Y$, т.е. ${{X}_{2}}$ и ${{Z}_{2}}$ являются боковыми вершинами глубины k, созданными самыми последними, при последней операции разбиения;

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

5) путь ${{X}_{1}}{{X}_{2}}Y{{Z}_{2}}{{Z}_{1}}$ выбран так, что уровень ребра, на котором лежит вершина X₁, больше уровня ребра вершины ${{Z}_{1}}$.

В случае, когда обе вершины ${{X}_{1}}$ и ${{Z}_{1}}$ имеют один уровень ребра, ориентация пути выбирается следующим образом:

случай А) ${{X}_{1}}$ и ${{Z}_{1}}$ лежат на ребрах разного типа. Тогда ${{X}_{1}}$ выбирается как вершина с большим номером типа ребра;

случай В) ${{X}_{1}}$ и ${{Z}_{1}}$ лежат на одном ребре. Тогда для внутреннего ребра ${{X}_{1}}$ выбирается как вершина, лежащая ближе к краю макроплитки. Для внешнего ребра ${{X}_{1}}$ выбирается как предшествующая и ${{Z}_{1}}$ при обходе контура по часовой стрелке.

Далее для каждого такого пути создаются шесть новых вершин ${{T}_{1}}$, ${{T}_{2}}$, ${{T}_{3}}$, ${{T}_{A}}$, ${{T}_{B}}$, ${{T}_{C}}$, не лежащих в плоскости ${{X}_{1}}Y{{Z}_{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}_{1}}Y{{Z}_{1}}{{T}_{1}}$ (рис. 2).

Созданные вершины будем называть подклеенными, причем ${{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}}$ – внутренними.

Тип вершин вдоль пути ${{X}_{1}}{{X}_{2}}Y{{Z}_{2}}{{Z}_{1}}$ не меняется при проведении подклейки.

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

Примечание 1. Заметим, что в подклеенной макроплитке по построению определяется верхняя, а следовательно, и остальные стороны: она выглядит так же, как если бы к плитке ${{X}_{1}}Y{{Z}_{1}}{{T}_{1}}$ применили разбиение, считая сторону ${{X}_{1}}Y$ верхней. Также можно считать, что в этой макроплитке ${{T}_{2}}$ – середина стороны ${{T}_{1}}{{X}_{1}}$, а ${{T}_{3}}$ – середина стороны ${{T}_{1}}{{Z}_{1}}$.

Определение 4. Комплексом ${{K}_{n}}$ уровня $n$ будем называть:

для $n = 1,2,3$ – макроплитку ${{T}_{n}}$;

для n > 3 – комплекс ${{T}_{{n - 1}}}$, к которому сначала применена операция разбиения, а затем операция подклейки.

Замечание 1. Начиная с четвертого уровня комплекса (и при построении пятого уровня) путь ${{X}_{1}}Y{{Z}_{1}}$ из определения операции подклейки может частично лежать в базовой плоскости, а частично в подклеенной части (если ${{Z}_{1}}$ появилась при предыдущей подклейке в качестве вершины ${{T}_{2}}$ или ${{T}_{3}}$). На больших уровнях комплекса весь путь из определения подклейки может лежать полностью в подклеенных плитках. Таким образом, возникают подклейки к частям подклеенных когда-то макроплиток и т.д.

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

Определение 5. Пусть $d(A,B)$ – стандартное расстояние между точками $A$ и $B$, длина пути по ребрам. Пучком путей ${{\Omega }_{n}}(A,B)$ с концами в точках $A$ и $B$ будем называть множество кратчайших путей на комплексе ${{K}_{n}}$, соединяющих точки $A$ и $B$. Пусть $s$ – длина всех этих путей. Тогда для пути $P$ определены точки комплекса, по которым он проходит: ${{P}_{0}} = A$, ${{P}_{1}}$, …, ${{P}_{{s - 1}}}$, ${{P}_{s}} = B$. На ${{\Omega }_{n}}(A,B)$ можно определить расстояние между путями. Пусть $P$, $Q \in {{\Omega }_{n}}(A,B)$. Расстоянием между путями $r(P,Q)$ будем называть $\mathop {max}\limits_{0 \leqslant i \leqslant s} d({{P}_{i}},{{Q}_{i}})$, т.е. максимальное расстояние между соответствующими точками двух путей с одинаковыми началом и концом.

Шириной пучка ${{\Omega }_{n}}(A,B)$ будем называть максимум $r(P,Q)$, где $P$, $Q \in {{\Omega }_{n}}(A,B)$, т.е. максимальное расстояние между принадлежащими ему двумя путями.

Теорема 1 (О существовании). В построенной последовательности геометрических комплексов ${{K}_{n}}$ выполнены следующие свойства:

1. Локальная конечность. Существует конечное число типов вершин, а также типов входящих и выходящих ребер.

2. Равномерная эллиптичность. Для любого натурального числа k существуют натуральные числа $N$ и $S$, такие что выполнено следующее свойство: в каждом комплексе ${{K}_{n}}$ для $n > N$ для любых точек $A$ и $B$ c расстоянием не менее $S$ пучок путей ${{\Omega }_{n}}(A,B)$ имеет ширину не менее $k$.

Теорема 2 (О детерминированности). Построенная последовательность комплексов ${{K}_{n}}$ обладает свойством детерминированности:

cуществует такая глобальная константа $N$, что все точки каждого из комплексов ${{K}_{n}}$ можно покрасить в $N$ цветов так, чтобы для любых четырех точек, образующих макроплитку 1-го уровня в комплексе ${{K}_{n}}$, по цветам трех из них можно однозначно установить цвет четвертой.

C построенной последовательностью комплексов ${{K}_{n}}$ можно связать конечно определенную полугруппу $S$ следующим образом.

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

Для слов $w$ длины <10, не кодирующих никакой путь на комплексе, а также для слов, кодирующих путь туда-обратно по одному и тому же ребру, вводятся определяющие соотношения $w = 0$.

Для каждой макроплитки уровня 1 семейства комплексов вводится определяющее соотношение $w = {v}$, где $w$ – кодировка пути по двум соседним сторонам макроплитки, а ${v}$ – кодировка пути с теми же началом и концом, но по двум другим сторонам. Кодировка каждого такого пути включает 7 букв – цвет начальной вершины, тип ребра выхода, тип ребра входа во вторую вершину, цвет второй вершины, тип ребра выхода из второй вершины, тип ребра входа в конечную вершину, цвет конечной вершины.

Теорема 3 (О полугруппе, связанной с последовательностью комплексов). Полугруппа $S$, связанная с последовательностью ${{K}_{n}}$, обладает следующими свойствами:

1. Слова, отвечающие путям различной длины, различны в полугруппе;

2. Слово, отвечающее кодировке пути по стороне макроплитки любого уровня, не может быть приведено к нулю определяющими соотношениями;

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

БЛАГОДАРНОСТИ

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

ИСТОЧНИКИ ФИНАНСИРОВАНИЯ

Работа была проведена с помощью Российского научного фонда (грант № 17-11-01377). Второй автор является победителем конкурса “Молодая математика России”.