Содержание к диссертации
Введение
1. Алгебра с конечным базисом Грёбнера, и неразрешимой пробле мой делителей нуля 9
1.1 План построения алгебры с идеалом соотношений, заданным конечным базисом Грёбнера, в которой вопрос, является ли элемент делителем нуля, алгоритмически неразрешим 9
1.2 Универсальная машина Тьюринга и определяющие соотношения 12
1.3 Делители нуля и остановка машины 14
2. Вспомогательные сведения о машине Минского 26
3. Реализация Машины Минского в конечно-определенной полугруппе 35
3.1 План построения полугруппы с полуцелой размерностью Гельфанда- Кириллова 35
3.2 Определяющие соотношения 36
3.3 Приведение к каноническому виду 38
3.4 Работа основного механизма 43
3.5 Система инвариантов 46
3.6 Преобразование для увеличения количества нормальных слов 51
4. Построение полугруппы с рекурсивной размерностью Гельфанда- Кириллова 52
4.1 План построения полугруппы с рекурсивной размерностью Гельфанда-Кириллова 52
4.2 Определяющие соотношения 54
4.3 Приведение к каноническому виду 55
4.4 Система инвариантов 60
4.5 Присоединение 63
4.6 Создание машины Минского в полугруппе 65
5. Конструкция конечно-определенной полугруппы, содержащей ненршьпотентныи ниль-идеал 69
Библиография 76
- Универсальная машина Тьюринга и определяющие соотношения
- Определяющие соотношения
- Работа основного механизма
- Приведение к каноническому виду
Введение к работе
Широко известна бернсайдова проблематика, охватывающая большой круг вопросов, как в теории групп, так и в смежных областях. Проблемам берисайдовского типа посвящена обзорная статья Е.И.Зельманова [20]. В РРслучае вопросы локальной конечности алгебраических алгебр решаются положительно. В ассоциативном случае соответствующий результат был получен И.Капланским и Д.Левицким. Чисто комбинаторное доказательство для ассоциативного случая получается из теоремы Ширшова о высоте [21], [22]. Для Р/-алгебр Ли соответствующий результат был получен Е.И.Зельмановым и А.И.Кострикиным. Подробная библиография но этому вопросу изложена в монографии [24].
Первый контрпример к "неограниченной" проблеме был найден Е. С. Голодом в 1964 году на основе универсальной конструкции Е. С. Голода- И. Р. Шафаревича. Вопрос о локальной конечности групп с тождеством хп = 1 был решен отрицательно в знаменитых работах П. С. Новикова и С. И. Адяна [1968]: было доказано существование для любого нечетного п ^ 4381 бесконечной группы с т > 1 образующими, удовлетворяющей тождеству хп = 1. Эта оценка была улучшена до п ^ 665 С. И. Адяном [1975]. Позднее А. Ю. Ольшанский предложил геометрически наглядный вариант доказательства для нечетных п > 1010. В конечно-определенном случае все подобные вопросы сильно усложняются. В этом направлении работают многие исследователи, и определенного прогресса достигли М. Сапир и И. Рипс.
Построения в группах, как правило, более сложны, чем в полугруппах. Например, вопрос о существовании конечно-порожденной ниль-полугруппы, то ость полугруппы, каждый элемент которой в некоторой степени обращается в нуль, имеет тривиальный положительный ответ: уже в алфавите из двух букв имеются слова сколь угодно большой длины, не содержащие трех подряд одинаковых подслов (кубов). Первая конструкция такого рода принадлежит Туэ [1912]. Однако, если потребовать от полугруппы возможность ее задания конечным числом определяющих соотношений, ситуация сильно усложняется - вопрос о суще-
Введение
ствоваиии такой полугруппы открыт (см. [Свердловская Тетрадь]).
На проблематику, связанную с построением разного рода экзотических объектов с помощью конечного числа определяющих соотношений обратил внимание В. Н. Латышев. Им же была поставлена проблема существования конечно определенного ниль-кольца [23].
В качестве продвижения в решении этого вопроса можно рассматривать результаты Хигмана, Г. П. Кукина, В. Я. Беляева о вложениях рекурсивно-о преде ленных объектов в конечно-определенные. [7], [9], в частности, теорема Хигмана о вложении рекурсивно-определенных групп в конечно-определенные. В этом контексте можно рассматривать результат о существовании конечно-определенной полугруппы, содержащей ненилыютентный ниль-идеал, рассматриваемый в настоящей диссертации.
Хотя до сих пор и не удается построить контрпримеры к проблемам Бернсайдовского типа с помощью конечного набора определяющих соотношений, были построены конечно определенные объекты с разного рода ''экзотическими" свойствами. В. А. Уфиаровским был построен пример конечно- опре де л еной алгебры с промежуточным ростом [3]. Этот пример представляет собой универсальную обертывающую алгебру алгебры Ли со степенным ростом. В данной диссертации приведена конструкция конечно определенной полугруппы с нецелой размерностью Гельфанда-Кириллова.
Для построения конечно-определенных полугрупп с подобными "экзотическими" свойствами чрезвычайно эффективным оказывается подход, связанный с использованием машины Минского. Машина Минского эквивалентна Машине Тьюринга^ но в ее конструкции используется только два регистра. Этим объясняется ее удобство при использовании в алгебраических конечно-определенных системах.
В настоящей диссертации данный подход используется для посторое-ния конечно-определенной полугруппы с размерностью Гельфанда- Кириллова, равной N + а, где а - некоторое рекурсивное число, JV - натуральное число, зависящее от а, В процессе построения в полугруппе реализуется машина Минского, вычисляющая соответствующее рекурсивное а. Кроме того, система соотношений определяет канонический вид слова для реализации требуемой размерности Гельфанда- Кириллова.
Построение разного рода конечно определенных экзотических объектов тесно связано с алгоритмической проблематикой. Известно, что про-
Введение
блема равенства в конечно-определенной полугруппе, а следовательно, и алгебре, алгоритмически неразрешима. С другой стороны, эта проблема разрешима, если идеал соотношений задан конечным базисом Грёбнера, замкнутым относительно композиция [12]. В этой связи В. Н. Латышев в 1980 году поставил опрос о существовании алгоритма определения, является ли данный элемент делителем пуля или нильпотеитом в случае, когда идеал соотношений задан конечным базисом Грёбнера.
Кроме этого, В. Н. Латышевым был поставлен также аналогичный вопрос для моиомиальных автоматных алгебр. Для этого случая существование алгоритма проверки, является ли данный элемент нильпотеитом, было установлено В. В. Борисенко, а существование алгоритма для делителей нуля - А. Я. Беловым и В. В. Борисенко [2]. Аналогичный результат для некоторого класса квадратичных алгебр был получен Н. К. Иы-уду [13], [14] а также Д. И. Пионтковским [15]. Все эти результаты вытекают из разрешимости системы линейных рекурентов на дереве [17]. Из результата работы [17] вытекает также существование алгоритма для установления делителей нуля для целого класса алгебр с ограниченой переработкой (аналогичной условию малых сокращений в теории групп.
Определение 0.0.1. Пусть на мономах алгебры А с фиксированной системой образующих есть порядок, для которого существует нормальный базис, т.е. базис из мономов, не представимых в виде линейной комбинации меньших. Алгебра А называется алгеброй с ограниченной переработкой справа, если при некотором d Є N для любого нормального слова W в алгебре А и любой образующей а.; выполняется равенство
Wm = W ( АуИ^-) (0.1)
где Xj Є F для всех j, кроме того, WWj суть нормальные слова алгебры A, \Wj\ ^ 2d, а слово W есть начальный кусок слова W длины \W\ — d.
Если множество слов нормального базиса образует регулярный язык, каждому слову отвечает вершина автомата и все коэффициенты А^- зависят только от типа вершины графа, отвечающего слову И7, то А есть автоматная алгебра с ограниченной переработкой справа.
Аналогичным образом определяется (автоматная) алгебра с ограниченной переработкой слева.
Один из основных результатов данной диссертации показывает, что условие ограниченной переработки является необходимым. Мы стро-
Введение
им алгебру с алгоритмически неразрешимой проблемой делителей нуля, и идеалом соотношений, заданным конечным базисом Грёбнера. Тем самым дается отрицательный ответ на вопрос, поставленный В.Ы. Латышевым.
Построение основано на подходе, связанным с использованием машины Минского. Для этого в полугруппе конструируется машина Минского, реализующая универсальную машину Тьюринга, одна элементарная операция работы которой соответствует умножению слева на выделенную букву. Остановка машины соответствует обнулению слова.
Таким образом, основные результаты диссертации таковы:
Построен пример алгебры, идеал соотношений которой задан конечным базисом Грёбнера, в которой вопрос, является ли элемент делителем нуля, алгоритмически неразрешим.
Построен пример конечно-определенной полугруппы с рекурсивной размерностью Гельфанда- Кириллова.
Построен пример бесконечной конечно-определенной полугруппы, содержащей ненильпотентный нильидеал.
Методы исследования. В работе использованы методы построения полугрупп с нулем и полугрупповых алгебр, е помощью введения определяющих соотношений. Основным элементом конструкции является реализация машины Минского. В первой главе реализуется универсальная машина для доказательства алгоритмической неразрешимости. При построении полугрупп с нецелой и рекурсивной размерностью Гельфанда-Кириллова машина используется как вычисляющий инструмент.
Практическая и теоретическая ценность. Работа носит теорети-
Введение
ческий характер.
Апробация работы. Основные результаты диссертации многократно докладывались на семинаре "Кольца и модули "кафедры высшей алгебры МГУ в 2000-2006 гг. , а также на следующих конференциях:
Международная алгебраическая конференция в честь Е. С. Ляпина, Санкт-Петербург, 1999.
65-th International Workshop in Algebra (AAA65) and Conference of Young Algebraists (CYA), Potsdam University, 2003.
Часть результатов опубликована в работе [10], автору диссертации принадлежит часть, относящаяся введению определяющих соотношений реализующих конструкцию обмена сигналами.
Отдельная часть результатов опубликована в статье [11], автору принадлежит часть, относящаяся к введению определяющих соотношений.
Основные результаты также опубликованы в сборниках тезисов докладов на международных конференциях (см. [??]).
Структура диссертации. Диссертация состоит из оглавления, введения, пяти глав и списка литературы, который включает 25 наименований.
Благодарности. Автор глубоко благодарен своем научным руководителям — доктору физико-математических наук профессору Алексею Яковлевичу Белову и доктору физико-математических наук Александру Васильевичу Михалеву за постановку задач, обсуждение результатов и постоянное внимание к работе.
Также автор хотел бы поблагодарить за внимание и обсуждения работы доктора физико-математических наук, профессора Латышева Виктора Николаевича, и доктора физико-математических наук, профессора Артамонова Вячеслава Александровича.
Автор выражает свою отдельную благодарность кандидату физико-математических наук Богданову Илье Игоревичу за детальное обсуждение работы.
Универсальная машина Тьюринга и определяющие соотношения
Для всех пар, кроме (4,3) определены функции q(i,j) - повое состояние после выполнения инструкции, t(i,j) - цвет, который принимает текущая клетка (головка уходит из нее после выполнения инструкции), vihj) ориентация пары (i,j), то есть (p(i,j) = 0, если (i,j) - левая пара или пара (4, 3) и ip(i,j) = 1, если (i,j) - правая пара. Введем следующие соотношения: Примечание. В случае, если в соотношении встречаются параметры, оно выписывается для всех указанных значений параметра. В случае, если фигурирует пара (г, j) - считается, что это любая пара, кроме (4,3). Пусть имеется слово tNLakbnQiPjMlfH(}R, соответствующее какому-то состоянию описанной машины. Как введенные соотношения помогают нам перейти к следующему состоянию? Соотношения (1.1)-(1.6) служат для того, чтобы можно было провести і с левого края до букв Q Pj} реализующих головку машины. Соотношения (1.17)-(1.21) служат для выведения s на правый край слова. Соотношения (1.7)-(1.16) и (1.20)-(1.24) непосредственно моделируют вычислительный процесс, указанный в плане построения: 1. Если (i.j) - левая пара, поделить к (степень буквы а) на 4 с остатком т. - соотношения (1.15),(1.16). Если же (i}j) - правая пара, нужно аналогично делить п - соотношения (1.7),(1.8); 2. Умножить п (или соответственно к) на 4 (так мы реализуем сдвиг клеток) и добавить к этому (г, j) - новый цвет перекрасившейся текущей ячейки.
Умножение производится с помощью преобразования Ьп —» din (или ак — с4к) - соотношения (1.12),(1.13) (для п) и (1.10),(1.11) (для к); 3. Заменить Qi на Q?(M) (в соответствии с инструкцией для (?,,? )) -соотношения (1.8) и (1.16); 4. Заменить Pj на остаток из пункта 1 - соотношения (1.8) и (1.16); 5. Заменить М на MQ ИЛИ МІ, в соответствии с ориентацией новой пары (i,j). - соотношения (1.11) и (1.16); 6. Восстановить новые значения степеней а и Ь: к — ак\ dn —+ bn -соотношения (1.20) - (1.24). Кроме того, соотношение (1.25) реализует остановку машины. Ясно, что полное состояние машины (вместе с лентой) описывается четырьмя числами: состоянием головки г, цветом текущей клетки j, числом к} кодирующим состояние клеток слева от головки и числом п, кодирующим состояние клеток справа от головки. Будем обозначать полное состояние машины как M(i,j,k,n). Определение 1.3.1. Будем считать, что полное состояние машины характеризуется четверкой (ijjjfc, тг), если, в данный момент: состояние головки г, цвет текущей клетки j, к — 2/Іо af n Y fLci / /, где cif - цвета клеток, перечисленные от головки тлево, Ь/ - цвета клеток, перечисленные от головки направо. Очевидно, что в обоих суммах всегда участвует конечное число ненулевых слагаемых, так как количество непустых ячеек всегда конечно. Каждое полное состояние однозначно определяет следующее полное состояние и так далее. Будем говорить, что машина переходит из состо яния M(ii,ji,ki,ni) в состояние M(i2,J2;k2,n2), если машина, начиная работу в состоянии М(гі, ji, к\,щ) за несколько шагов переходит в состояние M(i2,J2 2,n2) Нашей основной целью будет доказательство следующей теоремы: Теорема 1.3.1. Пусть машина Тьюринга, описанная выше, начинает работу в состоянии M(i,j,k,n).
Обозначим р — О, если (i,j) - левая пара или пара (4,3) и ip(i,j) — 1, если (i,j) - правая пара. Машина останавливается тогда и только тогда, когда слово LakbnQiPjMipHaR является делителем нуля в алгебре с определяющими соотношениями (1.1)-(1.25). Сначала докажем несколько предложений. Доказательство. Допустим сначала, что к 5. Тогда применяя tLa = Lta и несколько раз tab = ataA - соотношения (1.1) и (1.4), мы приводим слово tLakbn к виду Ьак Ча4Ъ. Далее, применяем ta% = ata?b, to?b = ata2b, ta2b = aiab tab = atb - соотношение (1.5) (при разных г), и получаем LaHbn. Если п 4, то па этом останавливаемся (и пункт 2 доказан). Если п 5, то соответствия пункту 1 мы добиваемся, применив несколько раз tb5 — btb4 - соотношение (1.6). Если 1 к 4, мы действуем аналогично, но в этом случае соотно шение to} — ata4- мы не применяем, пропуская этот этап. Предложение 1.3.2. Пусть к, п - неотрицательные целые числа, не равные пулю одновременно, 0 t(i,j) 3- цвет,, который принимает текущая клетка после выполнения инструкции (i\j), 0 q{i,j) 6-состояние головки после выполнения инструкции (i,j). Тогда, если (г, j) - правая пара, имеет место следующая эквивалентность:
Определяющие соотношения
Рассмотрим полугруппу с нулем S, порожденную словами в этом алфавите. Нашей целью будет задание конечного числа определяющих соотношений, создающих необходимую нам структуру на полугруппе S. В частности, нас будет особенно интересовать наличие канонической формы па полугруппе S: любое слово, не отвечающее канонической форме, равно нулю. Рассмотрим следующее множество соотношений: Предложение 3.3.1. Любое ненулевое слово имеет вид LnXRk. где X не содержит L и R, n,k 0. Если в слове нет букв L и R, то оно уже имеет требуемый вид при и = к — 0. Пусть в слове имеется буква L. Согласно соотношению (3.1), левее L должны быть тоже L, таким образом, слово имеет вид LnY, где слово Y не содержит L. Теперь, если в слове есть R, учитывая соотношение (3.2), получаем что слово представляется в требуемом виде. Предложение 3.3.2. Если W ф 0, то W = Xfkvnum, где X не содержит f, v, и, кроме того, k n m 0. Причем, если в слове W содероісится хотя бы одна букво, R, то W приводится к виду, не содержащему f, и, v. Согласно предложению (3.3.1), можно считать, что W = URn, где U не содержит R, и п 0. Рассмотрим слово U. Если в U нет букв /, v, и, то W уже имеет требуемый вид. Пусть, например, в U имеются одна или несколько букв /. Выберем крайнее справа вхождение. Слово U имеет вид X\fX2, где Х2 не содержит /. Так как U ф 0, то согласно соотношению (3.10), первой буквой в слове Х-2 могут быть только буквы Ь) /г, v, и, (Букв Rtt f слово Х2 i-re содержит.) Используя, что / коммутирует cbth,v,u- соотношение (3.21), получаем, что U X\X f. Теперь выберем крайнее справа вхождение / в слово Х\Х% и проведем аналогичные операции. Проведя указанные действия со всеми вхождениями / в слово [/, мы приведем U к виду X3fk, где к 0. Пусть, теперь, в U имеются одна или несколько букв v. Выберем крайнее справа вхождение. Слово U имеет вид YivY2l где Yi не содержит v. \
Так как U ф 0, то согласно соотношению (3.13), первой буквой в слове Уч могут быть только буквы b, h, /. и, (Букв R и v слово У2 не содержит.) Используя, что v коммутирует с 6, h, /, и - соотношение (3.22), получаем, что U = Y\Yiv. Теперь выберем крайнее справа вхождение v в слово Y\Y i и проведем аналогичные операции. Проведя указанные действия со всеми вхождениями v в слово U, мы приведем U к виду Y3vn.t где п 0. Пусть, теперь, в U имеются одна или несколько букв и. Выберем крайнее справа вхождение. Слово U имеет вид Z\uZ где Z% не содержит п. Так как U ф 0, то согласно соотношению (3.15), первой буквой в слове Z% может быть любая буква кроме L, i?, u) s. (Букв R и и слово Z2 не содержит.) Используя, что и коммутирует с всеми буквами, кроме L, R, s - соотношение (3.16), получаем, что U — ZiZ2u. Теперь выберем крайнее справа вхождение и в слово Z1Z2 и проведем аналогичные операции. Проведя указанные действия со всеми вхождениями и в слово U, мы приведем U к виду Z$um, где т 0. Заметим, что буквы и, v, f коммутируют между собой. Возвращаясь к рассмотрению всего слова W, получаем, что W = XfkvnumR\ где X не содержит /, v, и и к} п, т 0, I 0. Теперь, если I = 0, то есть если W не содержит R, то мы уже получили требуемый вид. Если же в слове содержится хотя бы одна буква R(l 1), то мы используем R2 = uR = vR = fR - соотношения (3.23), (3.24), (3.25) и получ&ом W = XfkvnumRl = XRk+n+l+m. В этом случае W приводится к виду, не содержащему /, v, и. Таким образом, получаем утверждение леммы. Предложение 3.3.3. Любое ненулевое слово W, не содержащее R име-ет вид XtfUlfkvnum, Согласно предложению (3.3.2), слово W можно представить в виде Xfkvnum, где X не содержит /, v, и. Рассмотрим слово X. Если в нем нет букв g и /г, то оно уже имеет требуемый вид при а = (3 = 0. Пусть, например, в слове имеются одна или несколько букв д.Возьмем крайнее левое вхождение. Тогда слово X имеет вид XigX2, где Х\ не содержит д. Согласно соотношению (3.9), первой буквой в слове Х2 могут быть только буквы Ь, /І, и, }, v, R. Заметим, что д коммутирует с Ь, /г, -
Соотношение (3.19), а /, v, иу R в слове Х2 не встречаются. Таким образом, можно продвинуть д на одну букву вправо. Теперь опять рассмотрим букву справа от д. Аналогично заключаем, что это может быть только b или h. Продолжая в том же духе, получаем, что X = Х д, где Хз не содержит д. Пусть теперь в слове имеются одна или несколько букв h.Возьмем крайнее левое вхождение. Тогда слово X имеет вид Y\hY2, где Y\ не со держит h. Согласно соотношению (3.12), первой буквой в слове Y2 могут быть только буквы , ?, u, /, v, В,. Заметим, что h коммутирует с , g, - соотношение (3.20), a /, v, и, В, в слове Уч не встречаются. Таким образом, можно продвинуть g на одну букву вправо. Теперь опять рассмотрим букву справа от д. Аналогично заключаем, что это может быть только t или д. Продолжая в том же духе, получаем, что X Y%h, где Уз не содержит /г. В итоге получаем требуемый вид. Предложение 3.3.4. Любое ненулевое слово W, не содержащее L, В, Qi, Q2 может быть представлено в одной из следующих форм: Согласно предложению (3.3.3), W можно привести к виду Xgah flvlu\ где X не содержит h, g, /, v, и, а также a, J5 Є {0,1}. Таким образом, X содержит лишь буквы а, 6, , s. Заметим, что s коммутирует с остальными буквами этой четверки - соотношение (3.17); произведение а и Ь (или t) равно пулю - соотношения (3.5), (3.6) и Ъ и і коммутируют - соотношение (3.18). Из этого следует, что X = snam или X = snbktm. Если имеет место первый вариант, то букв g, h7 /, v в слове быть уже не может, иначе оно приводится к нулю с помощью соотношения (3.5). Таким образом, получаем утверждение леммы. Предложение 3.3.5. Пусть ненулевое слово W не codepoicum, Qi, і Є {1,2}. Тогда: (і) Если W codepoicum L, то оно представляется в одном из следующих видов: 1. Llsnakum, где п, к, т 0, I I, если гп 0, то п 0/ 2. LlsngahPfW, где а,/3 Є {0,1}; кроме того р, i, j 0, п, I 1, если р 0, то а = 1, если і 0, то (3 = 1. (И) Если W содержит В, то оно представляется в одном из следующих видов: 1. snbmtlgahl3B, где п, т, І 0,кроме того а, (З Є {0,1}.
Работа основного механизма
Предложение 3.4.1. Пусть W = LlanspQibHmghRr , где I, р 1, г 2. a manoice п, к, m 0. Тогда: если р к то W = 0; если р к, то W = Llan+ksP-kQitm+kghnr. Допустим, р к. Применяя р раз Q\bs = aQ\t - соотношение (3.29), получаем W = Llan+pQibk 4m+pghRr. В данной форме не содержится s. Применим R2 — uR - соотношение (3.26). Учитывая, что и коммутирует со всеми буквами, кроме L, R и s - соотношение (3.16), мы можем привести слово к виду Lluan+pQib ptm+pghRr . Так как Lu = 0 - соотношение (3.4), получаем W = 0. Если р к, то применяя к раз Q\bs = aQ\i - соотношение (3.29), получаем требуемое. Предложение 3.4.2. Пусть W = LlanspQ2bktmghRr, где I, Допустим, р п. Применяя aQ2s — Q2bt - соотношение (3.27), получаем W = Llan pQ2bk+ptm+pghRT. В данной форме не содержится s. Применим R? = uR - соотношение (3.26). Учитывая, что и коммутирует со всеми буквами, кроме L, R и s - соотношение (3.16), мы можем привести слово к виду Lluan pQ2bk+4rfl+pghRr l. Так как Lu = 0 - соотношение (3.4), получаем W = 0. Если р к, применяя п раз aQ2s = Q2bt - соотношение (3.27), получаем требуемое. Предложение 3.4.3. Пусть W = LlanspQ1tmghRr; где I, р Докажем лемму индукцией по п.
При п = 0 она тривиальна, при п — 1 достаточно применить th = ht, sa = as, aQ\h = Q2th - соотношения (3.17), (3.20), (3.28). Докажем возможность перехода к меньшему п. Учитывая th = ht, sa = as - соотношения (3.17), (3.20), получим W = LlspanQihtmgRT Теперь применим aQ\h = Q2ih - соотношение (3.28): W = Llan 1spQ2tm+1ghRr. Теперь применяем предложение (3.4.2): Учитывая sQ2 = Q2s, sb = bs - соотношение (3.17): Применяя LQ2b = LQit - соотношение (3.26), получаем Теперь, применяя предложение (3.4.1) получаем Для п — 2 формула верна по предположению индукции. Так как Предложение 3.4.4, Пусть W = LlanspQ2tmghRr, vde I, Фактически это уже было доказано в предложении (3.4.3), после применения первого соотношения. Предложение 3.4.5. Пусть W = LlspQibktmghRT, где I, Тогда, если W 0fmoW = Llak+1sp+k+1Q2tm"k-2ghRr В дальнейшем будем учитывать, что s коммутирует с Q то есть при необходимости мы можем переносить все s влево или вправо от ft, и кроме того, h коммутирует с , то есть, h можно переносить влево или вправо от t. Применяя LQit = LQ2b - соотношение (3.26), затем к + 1 раз Q2bt = (1Q2S - соотношение (3.27), получаем то, что требуется. Предложение 3.4.6. Пусть W — LlspakQ2tmghR\ где I, Тогда, если W O, mo W = Llsp+k+1a?bk+Hm k"2ghRr Применяя Q2th = aQih - соотношение (3.28) и затем fc +1 раз aQ\t = Q\hs - соотношение (3.29), получаем то, что требуется. Предложение 3.4.7. Пусть W = LlspQitmghRr, где I, р I, г 2, т 0. Причем т не мооїсет быть представлено пи в одном из видов: 2п + Пусть т не представляется в указанных видах. Тогда п 4, Возьмем максимальное q} такое что 2q + 2 т.
Будем применять к слову W поочередно предложения (3.4.5) и (3.4.6). После q таких применений мы придем к одному из следующих видов, в зависимости от четности q: нечетное q\W = Llaqsp+ Q2tm 2q (JL hghRr четное q: W = L Q f - - ghRT. теперь, в случае нечетного q, применим Q2th = aQ\h - соотношение (3.28) и получим W = tia s Q - - ghR?. Так как мы выбрали максимальное q, имеем m — 2q — Jg — q — 2 = т — 2(q + 1)-q 2 q 0 и следовательно m — 2q — - — 1 gr + 1. Таким образом, мы можем применить m — 2q — -q 2 Jg — 1 раз aQ\t — Q\bs - соотношение (3.29). Получим слово, не содержащее t. При этом в слове присутствует как минимум, по одной букве а и Ъ. Учитывая, что g коммутирует с 6, получаем, W можно привести к виду, содержащему слово aQibg в качестве иодслова. Так как aQibg = 0 - соотношение (3.30) получаем W = 0. в случае четного q применим LQ\t = LQ2b - соотношение (3.26) и получим W = Llsp+ Q2bq+1tm 2q 2 lghRT, Теперь применяя т — 2q — jg — 1 раз Q$i — aQ2s - соотношение (3.27) и Учитывая, что g коммутирует с 6, получаем, W можно привести к виду, содержащему слово aQibg в качестве подслова. Значит, W = 0. Предложение 3.4.8. Пусть W = LlspQ2tmghRr, где I, р 1, г 2, т 0, причем т не может быть представлено ни в одном из видов: 2п + j / 2п + 2 + 1 для всех п 0. Тогда W = 0. Доказательство полностью аналогично доказательству предыдущей леммы, только на этот раз мы начинаем использовать предложения (3.3.2) и (3.3.3) начиная с предложения (3.3.3). Дальнейшее аналогично, с учетом того, что случаи четности q меняются местами. Итак, мы доказали, что непулевое слово содержащее L, ( и две R, приводится к виду LlspQiimghRr - предложения (3.3.1)-(3.4.4), причем, т представляется в виде 2п + jn или 2п + гА п + 1 - предложения (3.4.5)-(3.4.8).
Приведение к каноническому виду
Рассмотрим полугруппу с нулем 5, порожденную словами в этом алфавите. Нашей целью будет задание конечного числа определяющих соотношений, создающих необходимую нам структуру на полугруппе S. Рассмотрим следующее множество соотношений: 4. Построение полугруппы с рекурсивной размерностью Гельфаида- Кириллова 55 Предложение 4.3.1. Любое ненулевое слово лексикографически имеет вид LkXQ$} где X не codepoicum L и Qi} ft Є {0,1}; і Є {0,... n}, k 0. Доказательство. Если в слове нет букв L и ft, т0 оно уже имеет требуемый вид при к = /5 = 0. Пусть в слове имеется буква L. Согласно хЬ = О, где х ф L - соотношение (4.1), левее L должны быть тоже L, таким образом, слово лексикографически имеет вид LnY, где слово У не содержит L. Теперь, если в слове есть Qij учитывая Q%x — 0 - соот ношение (4.2), получаем что справа от Qi не может быть никаких букв. Таким образом, получаем требуемый вид. Предложение 4.3.2.
Пусть W - некоторое ненулевое слово. (і) Если W содержит QQ, то W приводится к виду, не содержащему }. Если W codepoicum f, но не codepoicum Qo, то W приводится к виду Xf, где X не содержит f. (И) Если W codepoicum g, то W приводится % виду, не содержащему v. Если W содержит v, но не codepoicum g, то W приводится к виду Xv, где X не codepoicum v, (Ш) Если W codepoicum E или L, mo W приводится к eudy, не содер-оісащему и. Если W содержит и, но не codepoicum ни L, ни Е то W приводится % виду Хи} zde X не codepoicum и. Доказательство, (і) Пусть W не содержит QQ, но содержит /. Выберем крайнее справа вхождение. Слово W имеет вид XifX2, где Х не содержит /. Так как W Ф 0, то согласно fx = 0, где х ф f,Q%,a- соотношение (4.3), первой буквой в слове Х 2 может быть только буква а. (Букв Qo и / слово Х2 ие содержит.) Учитывая, что fa = af - соотношение (4.14), / можно передвинуть на одну позицию вправо. Далее аналогично получаем, что второй буквой в слове Х2 также является а. Продолжая аналогично, получим X\fX2 = X\X if. Теперь выберем крайнее справа вхождение / в слово Х\Х% Повторяя описанные выше рассуждения можно получить вид W = Xfm. где т 1. Теперь применяя нужное число раз // — / - соотношение (4.10), получаем требуемый вид. Если W содержит Qo, учитывая предложение (4.3.1), имеем W = XQQ, где Qo ф X. К слову X применяем рассуждения из первого случая. Получаем W = YfQo, где Qo, / Y- Применяя fQo = Qo - соотношение (4.11), получаем вид, не содержащий /. (ii) и (iii) рассматриваются аналогично: учитывая соотношения (4.22) и (4.23), получаем, что слева от и могут находиться только буквы и ,t, а. Е7 L, а справа от v только буквы v, а, , д. Учитывая, что и и v коммутируют cant- соотношение (4.21), а также Е = Ещ д — vg -соотношения (4.19), (4.20), получаем, что требуется.
Предложение 4.3.3. Пусть W - некоторое ненулевое слово. Если W содерэюит L, то W приводится к виду, не содероісащему Е. Если W содержит Е. по не содероісит Е} то W приводится к виду ЕХ, где X не содержит Е. Доказательство. Пусть W не содержит Ь) но содержит Е. Выберем крайнее слева вхождение. Слово W имеет вид ХіЕХ%, где Х\ не содержит Е. Так как W ф 0, то согласно хЕ = О, где х ф L, а, Е -соотношение (4.18), последней буквой в слове Х\ может быть только буква а. (Букв L и Е слово Х\ не содержит.) Учитывая, что Еа = аЕ - соотношение (4.17), Е можно передвинуть на одну позицию влево. Далее аналогично получаем, что второй справа буквой в слове Х1 также является а. Продолжая аналогично, получим Х1ЕХ2 = EXiX2. Теперь выберем крайнее слева вхождение Е в слово XiX2- Повторяя описанные выше рассуждения можно получить вид W = ЕтХ, где т 1. Теперь применяя нужное число раз ЕЕ = Е - соотношение (4.16), получаем требуемый вид. Если W содержит L, учитывая предложение (4.3.1), имеем W LXy где L . X. К слову X применяем рассуждения из первого случая. Полу чаем W = LEY, где L, Е фУ. Применяя LE — L - соотношение (4.15), получаем вид, не содержапщй Е. Предложение 4.3.4. Пусть W - некоторое ненулевое слово, состоя-щее из букв a, t, g, причем g обязательно содержится в W, Тогда W aktmg, где либо т = 2к, либо т 2к+1. Доказательство. Учитывая gt — 0 и gg — 0 - соотношения (4.5), (4.6), справа от g могут быть только а. Учитывая да = ад- соотношение (4.13), д существует в единственном экземпляре и можно сделать ее крайней справа буквой. Получим Ug} где U состоит из t и а. Теперь, если в каком-то месте слова встречается подслово ta, мы заменяем его на подслово att, используя соотношение (4.12). Повторив эту операцию нужное число раз, получим W = аНтд. Допустим, т 2k+l и т ф 2к. Тогда т = 21 х (2р + 1), где I к} р 0. Из соотношения att — ta - (4.12), следует, что at2s = tsa. Тогда а1+Ц2 x(2p+i) tpatal. Таким образом, применяя ад = да соотношение (4.13), получаем aktm = ak l 4patgal. Учитывая atg = 0 - соотношение (4.7), получаем W = 0.
