Содержание к диссертации
Введение
1 Тождества полугрупп треугольных матриц над конечными полями 20
1.1 Некоторые свойства полугруппы Тп(К) 20
1.2 Вспомогательные результаты о существенно бесконечно базируемых полугруппах 23
1.3 Доказательство теоремы 1.1 24
1.4 Обсуждение результатов главы 1 31
2 Тождества полугрупп треугольных булевых матриц 33
2.1 Вспомогательные результаты о полугруппах ТВп и UTBn . 33
2.2 Доказательство теоремы 2.1 36
2.3 Доказательство теоремы 2.2 37
2.4 Обсуждение результатов главы 2 40
3 Тождества полугрупп базисного каркаса и полугрупп 'п, 41
3.1 Определения и вспомогательные результаты 41
3.2 Описания тождеств 43
3.3 Доказательство теоремы 3.1 51
3.4 Обсуждение результатов главы 3 62
Список литературы 63
- Вспомогательные результаты о существенно бесконечно базируемых полугруппах
- Доказательство теоремы 2.1
- Доказательство теоремы 2.2
- Описания тождеств
Введение к работе
0.1 Постановка проблемы конечного базиса
Пусть — счетный алфавит, через "'" и * мы обозначим соответственно свободную полугруппу и свободный моноид над Е. Тооїсдеством над алфавитом 2 называется пара слов u,v Є S+, которая обозначается посредством формального равенства и — и. Полугруппа S удовлетворяет тождеству и = w. если для любого гомоморфизма <р : S4" —> ,? выполняется и<р — к<р. Если I — некоторое множество тождеств, то говорят, что тождество и = V следует из 1". если любая полугруппа 5, удовлетворяющая всем тождествам из I, удовлетворяет также тождеству и — v. Полугруппа S называется конечно базируемой, если все тождества этой полугруппы следуют из некоторого конечного набора се тождеств (базиса тождеств полугруппы S); в противном случае S называется бесконечно базируемой. Пусть М. ~ некоторый класс конечных полугрупп. Проблема конечного базиса для класса М состоит в том, чтобы определить, какие полугруппы из М являются конечно базируемыми и какие — бесконечно базируемыми.
Решение проблемы конечного базиса известно для класса всех конечных групп. А именно, в [26] доказано, что любая конечная группа является конечно базируемой. Для конечных полугрупп это условие может не выполняться. Первый пример бесконечно базируемой полугруппы был приведен в [28]. Им стал б-элемеитный моноид Брандта В\ , который может быть представлен в виде полугруппы 2 х 2-матриц
/О 0\ /1 0\ /1 0\ /0 1\ /о о\ /о 0\
[о о J' \о у' V0 /' 1 V' Vі У' 1 і/
относительно обычного матричного умножения. Естественно возникает задача классификации конечных полугрупп с точки зрения конечной базируемо-сти их тождеств. За последние 40 лет в этом направлении проделана большая работа, результаты которой по состоянию на 1985 г. и 2000 г. систематизированы в обзорных статьях [9, глава II] и [39] соответственно. Представляется, однако, что эти исследования еще далеки от полного завершения. В частности, для ряда конкретных конечных полугрупп, важных для теории и приложений, все еще неизвестно, конечен ли их базис тождеств.
"Идеальным" решением проблемы конечного базиса для класса всех конечных полугрупп может стать появление метода, который бы позволил различить конечно базируемые и бесконечно базируемые полугруппы. Поясним эту мысль более подробно. Поскольку любая конечная полугруппа может быть описана конструктивно (например, таблицей умножения), то имеет смысл ставить вопрос о существовании алгоритма, который по некоторому
эффективному описанию полугруппы S определял бы, является она конечно базируемой или нет. Такая формулировка проблемы конечного базиса была предложена А. Тарским в начале 60-х годов в более общем случае, а именно, для класса всех конечных алгебр [37]. Вопрос о существовании такого алгоритма для конечных полугрупп открыт до сих пор. Отметим, что для класса всех конечных группоидов проблема Тарского была решена Р. Мак-Кеизи в работе [24], где было показано, что такого алгоритма не существует.
известен алгоритм, определяющий, является ли конечная инверсная полугруппа. S конечно базируемой. Алгоритм основан на том, что для конечной базируемое полугруппы S необходимо и достаточно, чтобы моноид Бран-дта В\ не принадлежал многообразию varS. Необходимость этого условия была доказана М. В. Волковым в [1], а достаточность является следствием результатов М. В. Сапира [6].
0.2 Полугруппы преобразований
Полугруппы преобразований являются классическим объектом общей теории полугрупп и изучение их абстрактных свойств занимает важное место в современной алгебре. Этой тематике посвящено огромное число публикаций, в том числе и обобщающего характера. Текущее состояние теории полугрупп преобразований отражено в недавнем обзоре Р. Салливана [36].
В литературе, как правило, рассматриваются серии полугрупп преобразований, индексируемые одним или несколькими естественными параметрами. Например, при исследовании полугрупп преобразований некоторого конечного множества таким параметром может служить количество элементов этого множества; при исследовании линейных преобразований линейного пространства над конечным полем параметрами могут выступать размерность пространства и само конечное поле, и т.п.
Приведем несколько примеров важных серий полугрупп преобразований. Пусть п — натуральное число. Будем пользоваться следующими обозначениями:
%i~ полугруппа всех преобразований n-элементного множества,
МТп - полугруппа всех многозначных преобразований тг-элементиого множества,
VTn — полугруппа всех частичных преобразований п-элементного множества,
Вп — полугруппа всех частичных многозначных преобразований п-эле-ментпого множества,
CT„(K) — полугруппа всех линейных преобразований n-мерного ли
нейного пространства над конечным полем К.
Отметим, что последние две полугруппы удобно мыслить себе как полугруппы матриц. А именно, полугруппа CTjK) есть не что иное как полугруппа п х n-матриц над конечным полем А', а Вп — полугруппа булевых п х п-матриц, то есть матриц, элементы которых принимают значения 0 или 1 и подчинены следующим закотам сложения и умножения:
0 + 0 = 0-0 = 0-1 = 1-0 = 0, 1-1 = 1 + 0-0 + 1 = 1 + 1-1.
Среди подполугрупп полугруппы СТп{К) особый интерес представляет полугруппа, всех верхних треугольных матриц, которую мы обозначим через %,{К). На языке преобразований Тп(К) может быть охарактеризована следующим образом. Пусть V — n-мериое линейное пространство над полем К, и векторы {ei, е3,,.. ,e,J образуют базис V. Рассмотрим флаг подпространств VI С .,. С V„, в котором подпространство У; порождается векторами Є[,... ,Єі для всех і = 1,.... га. Нетрудно понять, что полугруппа Тп{К) состоит из всех таких преобразований, для которых подпространства 1д, , К являются инвариантными. В недавней статье Ж. Алмейды, С. Марголиса, Б. Стейнберга и М. В. Волкова [12] было показано, что полутруппы треугольных матриц над конечными полями играют важную роль с точки зрения теории представлений и ее связи с формальными языками.
Аналогично, можно рассмотреть полугруппу булевых треугольных п х п-матриц. Эту полугруппу будем обозначать через ТВп
Еще одной важной серией полугрупп матриц являются полугруппы уиита-реуголъиых матриц, то есть верхних треугольных матриц, на главной диагонали которых все элементы равны 1. Полугруппу унитреутольных п х п-матриц над полем К будем обозначать через ЫТп{К), булевых унитреугольных її х n-матриц — через ЫТВп.
Далее мы будем считать, что множество, на котором действуют рассматриваемые нами преобразования, линейно упорядочено, и мы будем отождествлять его с отрезком натурального ряда {1,... ,п}. Среди всех полугрупп преобразований этого множества мы выделим так называемый базисный каркас, состоящий из тех иолугрз'пп, преобразования которых характеризуются некоторой комбинацией следующих четырех фундаментальных свойств:
всюду определенность,
инъектиБность,
монотонность (частичное преобразование а называется монотонным, если для всех i,j из области определения а из і < j следует, что і.а < 3-а),
направленность (частичное преобразование а называется направлен
ным, если і < г.а для каждого і из области определения а).
Перечислим полугруппы преобразований множества {1,... ,п}, которые характеризуются каждым из названных свойств по отдельности:
%t, уже упоминавшийся выше моноид всех всюду определенных преобразований, симметрический моноид,
1п, моноид всех частичных инъективиых преобразований, симметрический инверсный моноид,
VQn, моноид всех частичных монотонных преобразований,
Vn, моноид всех частичных направленных преобразований.
Каждая другая полугруппа из базисного каркаса получается как теоретико-мяожествеш-юе пересечение каких-то из только что указанных моноидов. Например, полугруппа Sn ~ Тп П Хп состоит из всех всюду определенных инъективиых преобразований и, разумеется, есть не что иное как группа всех перестановок множества {1,...,п} (симметрическая группа). Единицу этой группы обозначим через 1(1,...,^)-
Рис. 1. Базисный каркас полугрупп преобразований п-элемеитного
множества
При п > 2 базисный каркас состоит из 13 полугрупп, изображенных на следующей диаграмме;
Нетривиальные полугруппы, представленные на рисунке 1, интенсивно исследовались с самых разных точек зрения. Много внимания уделялось, например, вопросам их характеризации в терминах образующих и определяющих соотношений, см. недавний обзор [18]. Псевдомногообразия, порождаемые этими полугруппами, оказались весьма важными с точки зрения приложений алгебры в теории формальных языков, см. обзор [19].
Так, например, серия моноидов 0п порождает псевдомпогообразие всех (J-тривиальных полугрупп, которое, в свою очередь, порождается синтаксическими моноидами кусочно-тестируемых языков, то есть языков вида Б*а-і*а2''ffijfcE*. где k > 0, а; Є Е, г = 1...., ft. В терминах соответствия Эйленберга между пеевдмоногообразиями конечных моноидов и многообразиями формальных языков (см., например, [29]) последнее условие может быть сформулировано следующим образом: псевдомгюгообразию всех J-тривиалышх полугрупп соответствует многообразие кусочно-тестируемых языков. Каждая из серий п, Рп и ТОп порождает псевдомпогообразие Я-тривиальных полугрупп, которому соответствует многообразие языков, порожденное языками вида Е^Е^ аиЩ, где к > 0 и Е0, S; С Е, ( є Е, щ Ej для і = 1,..., ft. И, наконец, каждая из серий ТХп и VOln порождают псевдомногообразие всех (/-тривиальных полугрупп с коммутирующими идемпотеитами. Этому псевдомногообразию, в свою очередь, соответствует многообразие языков, порожденное языками вида Е^Е^ '«jjEfc, где к > 0 и Е0, Ej С Е, щ 6 Е, щ Ej U E*_i для і = 1,..., ft.
Рассмотрим еще две серии полугрупп преобразований. Пусть заданы два множества Хп = {1,2,..,, п} и Х'п = [V, 2',..., п'}. Определим преобразования ej и єj- (j = 1,2..., п) на множестве Хп+1 U Х'п+1 следующим образом:
__/?' + 1, если і = j, . і _ Г г', если г = j,
3 \ г, если іф у, і \ г, если і ф j.
Через 'п [и, соответственно, %] мы обозначим полугруппы преобразований па множестве Xn+i UX^ \Xn+i U X!n+l\, порожденные преобразованиями ej, e'p где j - 1,2,.,.,n [ej, e'j где j = 1,2,,,., n и преобразованием e'n+]].
Полугруппы !n и исследовались Э. Соломоном в работе [34], связанной с Эйленберговым описанием многообразий формальных языков, распознаваемых %-тривиальными моноидами.
Данные полугруппы интересны еще и тем, что являются примерами конструкции, иногда, называемой моноидом Катпалаш некоторого графа G. Опишем эту конструкцию. Пусть G = (V, Е) — конечный ориентированный граф. Для каждого ребра (а, Ь) Є Е определим преобразование f^^ множества V следующим образом:
, Ґ Ь, если 1-а.
ж. Лп ь) — і
' ' [ х, в противном случае.
Моноидом Каталана графа G называется моноид, порожденный всеми возможными преобразованиями /{„.,&) Исследованию моноидов Каталана и их свойств посвящена работа Э, Соломона [35]. Несложно проверить, что полугруппа 0„, о которой речь шла выше, является моноидом Каталана для графа, являющегося цепью:
Из определения полугрупп 'п и " немедленно следует, что эти полугруппы также являются моноидами Каталана. А именно, 'п является моноидом Каталана для графа
І 2 п п+1
2'
а ~ Для графа.
п + 1
*
Iі 2' п' (п + 1)'
Таким образом, среди моноидов Каталана встречаются полугруппы, представляющие интерес с различных точек зрения. Поэтому весьма вероятно, что изучение свойств моноидов такого сорта может составить тему для дальнейших исследований.
0.3 Дополнительные замечания о проблеме конечного
базиса
Кратко обсудим небольшую тонкость, возникающую при обсуждении проблемы конечного базиса. Поскольку мы рассматриваем тождества конечных полугрупп, то весьма естественно сузить определения, приведенные в начале введения, до класса # всех конечных полугрупп. А именно, мы можем сказать, что тождество u = v следует в классе J? из системы тождеств /, если любая конечная полугруппа S, удовлетворяющая всем тождествам из I,
удовлетворяет также тождеству и = v.B этом случае можно преобразовать и определение конечно базируемой полугруппы, а именно, будем говорить, что полугруппа S называется конечно базируемой в $, если все тождества этой полугруппы следуют в из некоторого конечного набора ее тождеств. В общем случае для алгебр и даже для группоидов, вопрос о том, является ли свойство конечной базируемое в классе конечных алгебр эквивалентным этому свойству в обычном смысле, является открытым. К счастью, для полугрупп эти два понятия конечной базируемое. ("абсолютная" и в $) совпадают, что было показано М, В. Сапиром в работе [32]. Из этого тем не менее не следует, что понятие следствия из системы тождеств в "абсолютном" смысле эквивалентно его "конечному" варианту, соответствующий пример можно найти в работе Ж. Черчилль [17].
Аналогичное замечание можно сделать и относительно проблемы конечного базиса для конечного моноида М как алгебры типа {2.0} и как полугруппы; моноид М конечно базируем в классе всех моноидов тогда и только тогда, когда ош конечно базируем б классе всех полугрупп. Как и выше, из этого не следует эквивалентность между определениями следования из системы тождеств для моноидов и полутрупп. Например, тождество ху = XZ влечет у — z в любом моноиде., но не в классе всех полугрупп.
Класс всех конечно базируемых полугрупп в определенном смысле "нерегулярен": за исключением единичных примеров он не замкнут относительно стандартных теоретико-групповых операций или конструкций. Приведем несколько примеров такого нерегулярного поведения. Существуют бесконечно базируемые полугруппы, являющиеся:
прямым произведением двух конечно базируемых полугрупп (соответствующие примеры можно найти в работах [2, 33, 31, 21]),
подполугруппой или гомоморфным образом конечно базируемой полугруппы (это следует из примера конечно базируемой полугруппы, являющейся прямым произведением двух бесконечно базируемых полугрупп, СМ. [33]);
полупрямым произведением двух конечно базируемых полугрупп (см, [20,10,7]),
прямоугольной связкой конечно базируемых полугрупп (см. [23]),
моноидом S1 для некоторой конечно базируемой полугруппы S (соответствующий пример можно найти в [28]).
Довольно интересный результат был получен М. В. Волковым в работе [2], А именно, для любой конечной полугруппы S можно указать конечно базируемую полугруппу А и конечную группу G (которая, б свою очередь, тоже
конечно базируема), что прямое произведение 5 х G х А будет бесконечно базируемым. Таким образом, каждая конечная полугруппа является прямым сомножителем некоторой бесконечно базируемой конечной полугруппы.
За 40 лет исследований, посвященных проблеме конечного базиса, сформировался определенный багаж методов доказательства бесконечной бази-руемости полугрупп. Мы приведем здесь основные идеи трех наиболее часто используемых методов; два из них будут применены в данной диссертации.
1. Синтаксический метод. Данный метод основан на следующей теореме
Биркгофа о полноте [13], дающей синтаксическое описание понятия выводи
мости из некоторой системы тождеств:
Теорема Биркгофа. Нетривиальное полугрупповое тождество u = v следует из системы тождеств I тогда и только тогда, когда найдутся сло-ва i% wi>... .,Wk Є *, такие что и = Wg, v = w^ и для каждого і — ОД,...,к — 1 существуют щ,Ь{ Є 2* и гомоморфизм Q : 2+ —у Ен", что іі'і =
Для того чтобы показать, что id 3 не имеет конечного базиса тождеств, достаточно указать некоторую бесконечную последовательность тождеств / С id S и проверить, что из-за особенностей полугруппы 3 "длинные" тождества последовательности I не могут быть формально выведены из "коротких" тождеств системы idS.
2. Метод критических полугрупп. Пусть V = v&rS. Для любого на
турального числа п мы обозначим через V^ многообразие, определенное
Есеми тождествами не более чем от п переменных, выполненных в V. Дру
гими словами У^ может быть определено как класс всех полугрупп, чьи
подполугруппы, порожденные не более чем п элементами, лежат в V-
Очевидно, что для любого п выполняется V'"' 2 V, и если V конечно базируемо, то V^ — V для некоторого п. С другой стороны, по теореме Биркгофа о конечной базируемое тождеств от конечного числа переменных [13]. каждое из многообразий V^ конечно базируемо. Следовательно, равенство V
Для того, чтобы построить последовательность критических полугрупп необходимы конструкции, которые были бы чувствительны к удалению порождающих элементов. В самом деле, требование Sn V \ V означает, что
хотя Sn не принадлежит многообразию V, все ее подполугруппы, содержащие не более п порождающих элементов, ему принадлежат. Всего известно буквально несколько конструкций, которые удовлетворяют этим требованиям, и что интересно, большинство из них используют одни и те же приемы. А именно, эти конструкции некоторым образом "кодируют" определенные графы, так что удаление порождающих элементов соответствует удалению ребер этого графа, до тех пор, пока не получится остовное дерево этого графа. Например, в качестве критических полугрупп часто используются полугруппы частичных преобразований некоторого конечного множества, или, другими словами, полугруппы преобразований неполного автомата, и в качестве графа, о котором говорилось выше, выступает граф этого автомата.
3, Существенно бесконечно базируемые полугруппы, В выдающейся работе [6] М. В. Сапир показал, что если все пыль-полугруппы конечно базируемого многообразия V локально конечны, то V удовлетворяет нетривиальному тождеству вида Zn — w, где {Zn} есть последовательность слов Зилтна, определяемая по правилу
Z\ = Х[ и Zn+i = Znxn+iZn.
Поскольку в любом конечно порожденном многообразии все полугруппы локально конечны, то любая конечная полугруппа, не удовлетворяющая никакому нетривиальному тождеству Zn = w, не только является бесконечно базируемой, но и обладает значительно более сильным свойством. А именно, эта полугруппа не принадлежит никакому конечно базируемому локально конечному многообразию. Полугруппы, удовлетворяющие последнему условию, называются существенно бесконечно базируемыми.
В работе [5| М. В, Сапир дал структурное описание существенно бесконечно базируемых конечных полугрупп. Пользуясь этим описанием, можно построить алгоритм, который по полугруппе, заданной таблицей Кэли определял бы, является ли эта полугруппа существенно бесконечно базируемой. Отметим здесь, что в случае конечных группоидов алгоритма, распознающего свойство "быть существенно бесконечно базируемым" не существует, это было показано Р. Мак-Кепзи в [24].
Неоднократно упоминавшийся выше моноид Брандта В\ является примером существенно бесконечно базируемой полугруппы. Более того, существенная бесконечная базируемость полугрупп очень часто доказывается именно путем отыскания моноида Брандта в соответствующем многообразии. Однако, существуют существенно бесконечно базируемые полугруппы, для которых это не так. В работе [5] М. В. Сапир построил пример существенно бесконечно базируемой полугруппы Т такой, что В\ $ varT. М. Джексон в [21, 22] показал, что любая такая полугруппа Т должна состоять как минимум из 56
элементов и содержать как минимум 9 не нильпотентных подгрупп. Он описал все 56-элементные существенно бесконечно базируемые полугруппы Т, такие, что В\ varT и все минимальные с точки зрения отношения делимости1 существенно бесконечно базируемые полугруппы. Поскольку любая существенно бесконечно базируемая полугруппа имеет хотя бы один минимальный существенно бесконечно базируемый делитель, то последний результат дает еще одну алгоритмически эффективную характеризацию существенно бесконечно базируемых конечных полугрупп.
Стоит отметить, что для доказательства конечной базируемое до сих пор не были обнаружены "индустриальные" методы наподобие описанных выше. Как правило, конечная базируемость полугрупп доказывается непосредственно путем проверки того, что все тождества данной полугруппы выводятся из заданного конечного набора ее тождеств. При исследовании полугрупп, содержащих малое число элементов может быть применен результат, полученный А. Н. Трахтманом в работе [38]. А именно, он показал, что любая полугруппа, содержащая не более 5 элементов является конечно базируемой. Из этого результата, в частности, следует тот факт, что моноид В\ является минимальной по числу элементов бесконечно базируемой полугруппой.
В заключение отметим, что в последнее время к проблеме конечного базиса, для класса конечных полугрупп возник интерес и со стороны компьютерных наук. При изучении таких объектов, как графы, конечные автоматы или формальные языки, важную роль играют полугруппы, связанные с ними. Примерами таких полугрупп могут являться полугруппы переходов конечных автоматов, синтаксические моноиды формальных языков, моноиды Каталапа и т.д. Свойства этих полугрупп часто определяют свойства соответствующих им объектов. Одним из таких определяющих свойств является, например, принадлежность данной конечной полугруппы некоторому многообразию. Следовательно, интерес представляет проблема распознавания принадлежности многообразию, порожденному некоторой конечной полугруппой S и, в частности, вычислительная сложность этой проблемы. Пусть Т — конечная полугруппа, для которой мы хотим выяснить, верно ли, что Т є varS*. В том случае, когда полугруппа S конечно базируема, легко указать алгоритм, решающий эту задачу, и сложность этого алгоритма, будет полиномиально зависеть от размера полугруппы Т. В самом деле, если ]Г| - п, а в записи некоторого конечного базиса тождеств полугруппы S встречается не более m переменных, то можно перебрать все возможные наборы из m элементов полугруппы Т. подставить эти элементы в базис тож-
1 Напомним, что полугруппа S делит полугруппу Т, если S является гомоморфным образом некоторой подполугруппы Т. Очевидно, что отношение делимости па классе всех конечных полугрупп является отношением порядка.
деств и таким образом установить, выполнены ли все тождества, полугруппы S в полугруппе Xі, или, другими словами, принадлежит ли Т многообразию, порожденному полугруппой S. Очевидно, что сложность такого алгоритма 0(пт). В случае, если полугруппа S бесконечно базируема, проблема принадлежности многообразию var S остается нетривиальной и может не иметь полиномиального алгоритма. Пример такой конечной полугруппы S, для которой данная проблема является NP-трудной, был найден Р. Мак-Кензи и М. Джексоном в работе [25].
0.4 Проблема конечного базиса для различных серий полугрупп преобразований
В работе М. В. Волкова [2] было получено полное решение проблемы конечного базиса для серий полугрупп Тп, МТп, "РТ„, В„ и ТП(Л"). ^- именно, было показано, что что полугруппа Тп бесконечно базируема тогда и только тогда, когда п > 3, а полугруппы МТп, VTn; Вп и Тп(К) бесконечно базируемы тогда и только тогда, когда п > 2. Эти же результаты следуют из результатов М. В. Сапира [5].
Обратимся к проблеме конечного базиса для полугруппы Т„ (К) всех верхних треугольных п х п-матриц над конечным полем К. Очевидно, что полугруппа %{К) коммутативна, и, следовательно, базис ее тождеств конечен. Вопрос о конечной базируемости полугруппы Тп{К) при п > 2 был в явном виде поставлен в [9] и затем повторен в [39].
Ситуация аналогична и для полугруппы ТВп всех булевых треугольных п х п-матриц. Полугруппа ТВ\ содержит всего два элемента и, следовательно, имеет конечный базис тождеств, а при п > 2 проблема конечного базиса оставалось открытой.
Полугруппа UTJK) унитреугольных п х n-матриц над конечным полем не представляет особого интереса с точки зрения проблемы конечного базиса: поскольку определитель любой уиитреуголы-юй матрицы равен 1, то эта полугруппа является группой и поэтому конечно базируема. Однако, аналогичный вывод не мол-сет быть сделан относительно полугруппы UTBn всех булевых унитреугольных п х n-матриц. Полугруппы UTB-l и UTB2 конечно базируемы, поскольку содержат один и два. элемента соответственно. Однако, для больших значений п очевидным образом результат получить не удается.
Перейдем к рассмотрению полугрупп базисного каркаса с точки зрения проблемы конечного базиса. Очевидно, что полугруппа S„ (являющаяся группой) и {l{i,,..,n}}, конечно базируемы. С другой стороны, выше уже упоминалось, что полугруппа % бесконечно базируема при її > 3, и можно показать,
что VQn, Zn, On и VOZn при n > 3 также бесконечно базируемы (более того, указанные полугруппы существенно бесконечно базируемы, поскольку каждая из них порождает многообразие, содержащее В\). Проблема конечного базиса для 0п была недавно решена в [40], где было показано, что эта полугруппа бесконечно базируема тогда и только тогда, когда п > 5. Вопрос о конечной базируемости оставшихся полугрупп был в явном виде сформулирован в [39].
Полугруппа [ содержит три элемента и поэтому конечно базируема. Для остальных полугрупп из серий 'п и '1 аналогичным образом решить проблему конечного базиса не удается.
Целью данной диссертации является решение следующей задачи:
Задача. Решить проблему -конечного базиса для серий полугрупп Тп(К), ТВп, ЫТВп> п, Vn, VOn, VXn> VOln, 'n и С
0.5 Содержание диссертации
Основные результаты диссертации решают проблему конечного базиса для серий полугрупп Тп[К), ТВП) ЫТВп, п, Тп> VOnt VTn, VOln, 'п
и '.;,
В главе 1 рассматриваются полугруппы треугольных п х тг-матриц над конечными полями, В 1,1 и 1.2 доказываются некоторые свойства полугруппы %(К) и приводятся вспомогательные результаты, касающиеся существенно бесконечно базируемых полугрупп. В 1,3 доказывается критерий существенной бесконечной базируемосги для полугрупп треугольных матриц над конечными полями и таким образом решается проблема конечного базиса, для серии полугрупп TJK).
Вспомогательные результаты о существенно бесконечно базируемых полугруппах
Доказательство, Проверим, что полугруппа %[К) удовлетворяет условию (в) леммы 1.3. Пусть є — идемпотентная матрица из %(К) и а,Ь Тп(К) делят е. Тогда по лемме 1.1 Д(е) С А(а) и Д(е) С А(Ь), откуда Д(е) С Д(а)П Д(6) = А(аЬ), Снова применяя лемму 1.1, заключаем, что произведение ab делит е. Из леммы 1.3 и следствия 1.2 вытекает, в частности, упомянутый во введении факт, что полугруппа В\ не принадлежит многообразию у&х%,{К) ни при каких пк К. В завершение этого параграфа сформулируем результат из упомянутой выше работы [27, раздел 3.2, пример 2], описывающий 2?-строение полугруппы %(К) над произвольным полем К. Предложение 1.1. В полугруппе Тп(К) каждый V-класс состоит из всех матриц ранга j (0 j п) с одинаковым расположением нулевых элементов па главной диагонали и имеющих на ней ровно j ненулевых элементов. Каждый регулярный V-класс образует подполугруппу, и следовательно является объединением своих максимальных подгрупп. Каждая максимальная подгруппа V-класса, содержащего матрицы ранга j изоморфна группе всех обратимых треугольных j х j-матриц над полем К. 1.2 Вспомогательные результаты о существенно бесконечно базируемых полугруппах Напомним, что конечная полугруппа S называется существенно бесконечно базируемой, если S не принадлежит никакому конечно базируемому локально конечному многообразию. Нам понадобится два критерия существенной бесконечной базируемости из [6].
Перед тем, как сформулировать их, напомним, что период d{S) конечной полугруппы S — это наименьшее общее кратное периодов ее подгрупп, а верхним гиперцентром, T(G) конечной группы G называется подгруппа, на которой стабилизируется верхний центральный ряд G. Предложение 1.2. Конечная полугруппа S с единицей существенно бес конечно базируема, тогда и только тогда, когда найдутся элемент а Є S и идемпотент є Є S такие, что а делит е и элементы еае и ead( +1е не принадлежат одному смежному классу подгруппы И по ее верхнему ги перцентру, и Предложение 1.3. Если все подгруппы конечной группы S нилъпотентпы, то S существенно бесконечно базируема тогда и только тогда, когда В\ Е var S. ш Если элементы а, е. є S обладают свойством из формулировки предложения 1.2, то будем называть пару (а. е) критической. Отметим, что бывают ситуации, когда это свойство удовлетворяется, так сказать, тривиальным образом просто в виду того, что элементы еае и ead +le ие попадают в подгруппу Не. Именно так, например, обстоит дело для полугруппы В\, в которой критической является пара матриц а = [ п л }, е = ( л n ) (Дей например, для полугрупп %і{К) мы выше показали, что если некоторая матрица а Є Тп{К) делит идемпотент є Є %і{К)} то eake Є Не для всех к, а стало быть, существенная бесконечная базируемость, если она имеется, должна проявляться нетривиальным образом. Далее нам будет полезен следующий факт, полученный в [22]: Предложение 1.4. Пусть S — такая существенно бесконечно базируемая полугруппа, что В\ var S, и (а,е) — произвольная критическая пара в S. Тогда D-класс идемпотепта е содержит по крайней мере три С-класса и по крайней мере три Л-класса. ш Существенная бесконечная базируемость полугруппы Тп[К) вытекает из предложения 1.2 и из следующего факта: Предложение 1.5.
Матрицы а ие образуют критическую пару в %t(K). Доказательство. Несложно подсчитать, что е - идемпотент. Отсюда в силу леммы 1-1 вытекает, что а делит е. Так же непосредственно можно убедиться, что Отсюда ак = а2 и тке — е для любого к 1. В частности, если d - период полугруппы Та(К), то матрица ead+1e е принадлежит верхнему гиперцентру Г(Не) подгруппы Не. Итак, для того, чтобы доказать, что элементы еае и ead+1e не принадлежат одному смежному классу по Г(#е), остается проверить, что Пусть {е} = 2о С Z\ С 2 С - С Zm = Т(Не) — верхний центральный ряд группы Не. Если д Є Г(#е), h є Не, то коммутатор [д, k\ принадлежит уже Дп-ъ повторньїіі коммутатор [[д, h],h] попадает в Zm-2, и т.д.; наконец, т-кратнос коммутирование с h дает е. Поэтому для того, чтобы показать, что еае ф Г(#с), достаточно найти такую матрицу h Є Яе, что ни при каком натуральном т. Пусть /3 — элемент поля К, отличный от 0 и 1 (такой элемент существует, так как \К\ 2). Убедимся, что в качестве h можно взять матрицу
Доказательство теоремы 2.1
Прежде всего отметим, что для каждого п 4 полугруппа ТВп содержит подполугруппу, изоморфную ТВ,\. Следовательно, для доказательства существенной бесконечной базируемое ТВп при п 4 достаточно проверить, что полугруппа Брандта В\ принадлежит многообразию тгжТБ - Рассмотрим подполугруппу В в ТВІ, порожденную следующими матрицами: Поскольку каждая матрица (7 ) Є удовлетворяет условию 7п = 744 = 1; то множество / всех матриц () Є Л, таких, что Л і4 = 1 образует идеал в В. Непосредственные вычисления показывают, что кроме а, 6, единичной матрицы е, только две мартицы принадлежат В \ I. Рассмотрим следующую биекцию между В\1 и множеством ненулевых матриц в В\: Легко проверить, что данная биекция продолжается до изоморфизма между факторполугруппой Риса В/1 и полугруппой В\. Таким образом, В\ является гомоморфным образом некоторой подполугруппы в ТВц и, следовательно, В\ принадлежит многообразию, порожденному ТВІ Осталось проверить, что полугруппы ТВ2 и Т% не являются существенно бесконечно базируемыми.
Поскольку 7 вкладывается в ТВз, достаточно рассмотреть только 7-. Мы непосредственно проверили (при помощи компьютерной программы). что ТВ-& удовлетворяет тождеству которое нарушается в полугруппе В при подстановке 1 о о вместо х и Следовательно, В не принадлежит многообразию var7%, и по предложению 2.1 полугруппа. ТБ3 не содержит нетривиальных подгрупп. Из последнего условия следует, что все подгруппы полугруппы 7% нильпотентны и тогда, применив предложение 1.3 мы заключаем, что 7 не является существенно бесконечно базируемой. Теорема 2.1 доказана. 2.3 Доказательство теоремы 2.2 Следующее предложение устанавливает связь между системой тождеств Jk и полугруппой иТВп Предложение 2.3. Для любого натурального п мноотество Jn совпадает с множеством всех тождеств, выполненных в полугруппе U1 В„+1. Доказательство. Обозначим через 1п множество всех тождеств, выполненных в полугруппе UTBn+i. Сначала покажем, что /„ С ./„. Пусть задано слово w = Xi xm, где Xi,..., xm Є и m п. Определим гомоморфизм ipw : — UTBn+x следующим образом: Лемма 2.1. Для любого слова v Т. слово w является разбросанным подсловом слова v тогда и только тогда, когда (vtp-a,), , 1 Доказательство. Пусть v = y-r--yk, где yh...,yk Є , и ys(pw = (a\f). Тогда, используя k - 1 раз правило умножения матриц, получаем следующее выражение для элемента {inpw)l : Если w = жт является разбросанным подсловом и, то найдется последовательность 1 si sm А\ такая, что х = ys. для каждого г = 1,..., т. Тогда все множители в произведении равны І, следовательно и само произведение равно 1, а значит и сумма в правой части выражения (12), в которую данное произведение входит в качестве одного из слагаемых, тоже равна 1. Таким образом, (vipvl) = 1. Обратно, если (yipw] = 1, то как минимум одно из слагаемых в правой части выражения (12) равно 1. Пусть По определению отображения (pw, имеем of- = 0, если і ф j,j + 1. Сле довательно, возрастающая последовательность jo = 1 j] - jjb_5 ті + l=ji содержит ровно m "скачков" вида j,- j,.+i Л + 1- Через su где г = 1,...,т, мы обозначим позицию г-го такого скачка. Тогда произведе ние Giji«j-jL "ajJ_im-i может быть записано в виде (13). и поскольку все множители af/li равны "I, то из (11) следует, что ун — :щ для всех г. По этому w — %\ хт в самом деле является разбросанным подсловом слова Теперь, чтобы доказать, что 1п С Jn, возьмем произвольное тождество и = v, выполненное в полугруппе UTBn+i. Тогда шр = щ для любого гомоморфизма (р : 2 — UTBn±\. В частности, u = t1 , для любого слова w Є длины m ЇЇ, следовательно ( "- ш и1 = (v )im+i лемме 2-1 это условие означает, что w является разбросанным подсловом и тогда и только тогда, когда w является и разбросанным подсловом слова v.
Поэтому тождество и = v принадлежит множеству Зп. Чтобы доказать обратное включение Jn С 1п, необходимо проверить, что для любого тождества и — v из Jn и для каждого гомоморфизма tp : - UTBn+i условие выполняется при всех значениях I тп. Из соображений симметрия достаточно проверить, что (и р), — 1, если (v(pj. = 1. Пусть v — уі---уіс для некоторых Уі;-.-,Ук Є , и пусть г/ь(р — ( ). Тогда и, поскольку сумма в правой части выражения равна. 1, го хотя бы одно из ее слагаемых должно быть равно 1. Пусть crJ m !-г - m _ m = 1. Через р мы обозначим количество "скачков" вида }.,. j,.+i в неубывающей последовательности jo = I ji jt-[ in = jj.. Легко понять, что р не превосходит та - t (n+ 1) — 1 = я. Для каждого г = 1,... ,/j мы обозначим позицию г-го по порядку скачка через 5, и размер этого скачка jT+i -jr через dj. Тогда слагаемое ЩІо/ \г -ajJ_im можно записать следующим образом:
Доказательство теоремы 2.2
Из теоремы 2.1 следует, что "практически все" полугруппы из серии ТВп являются бесконечно базируемыми. Исключение могут составить лишь полугруппы матриц малой размерности 7 и ТВ?,. Поскольку данные полугруппы содержат более 5 элементов (наименьшая по количеству элементов из этих полугрупп, ТВ2 содержит 23 = 8 элементов), то вопрос о конечной базируемое для них остается нетривиальным. Поэтому интерес представляет следующая задача: Проблема 3. Решить проблему конечного базиса для полугрупп ТВ% и Т$з Отметим, что для серии полугрупп булевых унитреуголышх матриц нами получено полное решение проблемы конечного базиса: теорема 2.2 дает необходимое ш достаточное условие для бесконечной базируемое этих полугрупп. Предложение 2.3 представляет интерес и с точки зрения компьютерных наук. Благодаря описанию тождеств, полученному в этом предложении, можно сделать вывод, что задача проверки тождеств в полугруппе UTBn решается за полиномиальное время от длины тождества. В самом деле, чтобы проверить, выполняется ли тождество w = w в этой полугруппе, достаточно сравнить множества разбросанных ПОДСЛОЕ длины, не превосходящей п - 1, для слов w и и/. Известно, что задача построения множества всех разбросанных подслов фиксированной длины для некоторого слова w может быть решена за полиномиальное время от длины этого слова. Таким образом, задача проверки тождеств в полугруппе иТВп является "легкой" с точки зрения теории вычислительной сложности. Для удобства читателя напомним определения, которые нам потребуются в данной главе. Пусть v,w — слова над алфавитом Б, Будем говорить, что слово v является разбросанным подсловом слова w, если v = а,\ ат, где йі,...,йт Є 2, и можно подобрать такие слова wo, Wi,.. .,wm i,wm Є , что другими словами это означает, что буквы слова v входят в w в качестве подпоследовательности. Очевидно, что если v является разбросанным подсловом слова w. то w .может иметь несколько представлений в виде (15). Представление (15), для которого справедливы условия ( c(tt;;_i), гДе і — 1,..., m, будем называть первым, вхождением слова v в слово w} а факторы WQ, -Ш],..., ifm, участвующие в этом представлении, — факторами первых вхождений v в w. Если для слова w существует всего одно представление вида (15), то слово v назовем уникально разбросанным подсловом слова w. Следующее свойство уникально разбросанных подслов будет полезно нам в дальнейших рассуждениях. Предложение 3.1.
Пусть v — разбросанное подслово слова w и представление (15) является первым вхождением слова v ew. Для того чтобы, слово v являлось уникально разбросанным подсловом слова w, необходима и достаточно, чтобы, выполнялись условия щ $ C(WJ) для всех і = 1,..., т. Доказательство. Необходимость данного условия практически очевидна. Действительно, пусть найдется такое значение го, что щ0 Є с(иц). Следовательно, слово и г0 можно представить в виде ш;0 — 5 для некоторых слов Ui0.u io Є . Обозначим через w iu_l слово Wi0-\Cii0UiQ. Тогда слово w может быть представлено в виде что противоречит тому, что v является уникально разбросанным подсловом слоь-а w. Предположим теперь, что для всех значений г = 1,...,т выполняются условия щ $ с{ Ші). Покажем, что v является уникально разбросанным подсловом w. Предположим противное, т.е. пусть существует еще одно представление слова w в виде Обозначим через кі її к[ номера позиций букв щ в представлениях (15) и (16) соответственно. Поскольку (15) является первым вхождением слова V В W, то, очевидно, выполняются неравенства fc; к[ для всех і = 1,,,., т. Следуя нашему предположению, найдется такое число ц, что кіа к ,. Поскольку буква йі0 не содержится в слове v;iu. то /i:io+i k io, откуда kio+y fcjD+1. Индуктивно продолжая эти рассуждения, мы получим, что кт к т; следо вательно, ат Є c(wm), что противоречит условию предложения. Определим несколько систем тождеств. Через . [соответственно Я;.] мы обозначим набор всех таких тождеств w — w , что выполняются следующие два условия: 1) для любого т к множества разбросанных ПОДСЛОБ длины m слов w и w должны совпадать; 2) если представления являются первыми вхождениями разбросанного подслова v = а і ат длины т к в слова w и и , то должны совпадать алфавиты факторов первых вхождений слова v в w и w \ c(wi) — c(uij) для всех і 0,..,, т [соответственно для всех г — 0,..., т — 1]. Через 6 обозначим набор всех таких тождеств w = w , что выполняются следующие три условия: 1) c(w)=c{w ); 2) для любого т к множества уникально разбросанных полслов длины т слов w и w должны совпадать; 3) если для уникально разбросанного подслова v = ay ат длины т к имеют место представления и то должны совпадать алфавиты соответствующих факторов первых вхождений: с( Ші) = c{v][) для всех І = 0,...,771.
Описания тождеств
Очевидно, что определенное таким образом преобразование лежит в полугруппе п+2- По построению l.(w ) = т+ 1, следовательно 1,(и/ ) = то+ 1. Легко проверить, что данное условие может быть выполнено ТОЛЬКО в том случае, если v является разбросанным подсловом w и для первого вхождения v в ID справедливы включения c{ w ) С c(Wi), где г = 0,1,.... т. Обратные включения получаются из симметричных рассуждений. Теперь предположим, что тождество w = w содержится в множестве В,п. Покажем, что для любого гомоморфизма tp : 2 -4- пЛ.2 и любого натурального числа к = 1,... ,п + 2 выполняется k.(w p) = k.(w p). Без ограничения общности мы будем считать, что k.(w p) k.(w p). Построим разбросапгюе поделово v = а\- -ат слова w, удовлетворяющее следующим свойствам: Очевидно, что длина построенного слова v не превосходит п + 1, а представление есть первое вхождение слова v в w. Предположим, что m п. Тогда слово v является также разбросанным подсловом слова w . При этом первое вхождение слова v в w удовлетворяет условиям с(шо) — C(WQ), С(Щ) = c(w[),... ,c(wm) c(w m). Очевидно, что Случай Vn+\. Результат предложения для полугруппы V-a+\ немедленно получается из предыдущего случая и следующего утверждения: Лемма 3.1. ДЛЯ любого натурального числа т, полугруппа Vm изо-м,орфна полугруппе Ет+\_. Доказательство. Построим отображение р : Тт - т+\ следующим образом: для любого преобразования х Є Vm и каждого і 1,..,, т + 1 определим
Определенное таким образом преобразование х р, очевидно, является направленным, так как таковым является х. Проверим, что р — изоморфизм. Всю-дуопределенность и однозначность р очевидны из определения. Для любого направленного преобразования у m+i его прообразом является такое частичное направленное преобразование х Є Vm, что следовательно ц является сюрьекцией. Иньективность ір также очевидна: если zip = zip для некоторых х, z Є Vm, то преобразования х и z совпадают на общей области определения (это следует из первой строки определения преобразования х р выше) и их области определения совпадают (из второй строки определения). Итак, р — взаимно однозначное отображение Vm — Покажем теперь, что для любых х, у Є Рт выполняется равенство (ху) р — [xsp)(ytp). Зафиксируем произвольное число і = 1,..., т. Случай 1. Если і.х и і.(.ту) — (г.х).у определены, то Случай 2. Если хотя бы одно из выражений і.х или і.(ху) = {і.х).у не определено, то г.((ху) р) — т+ 1 и i.(xtp)(yip) = т + 1. Следовательно, tp — изоморфизм. а Случай POn+i. Предположим, что тождество ад = «/ выполняется в полугруппе VOn+i и слово v = Oi---ara (m п) является разбросанным подсловом слова w. Как и выше, мы рассмотрим первое вхождение (15) слова ившя построим гомоморфизм р : Е — TOn+i. Пусть а є Е, положим и j.(aip) j для ; — m + 2,..., п + 1. Очевидно, что определенное таким образом преобразование лежит в полугруппе Рп+\_. По построению l.(w p) = т + 1, следовательно l.(w ip) = т + 1. Легко проверить, что данное условие может быть выполнено только в том случае, если v является разбросанным ПОДСЛОВОМ W1 И ДЛЯ ПерВОГО ВХОЖДеНИЯ V В W1 Справедливы ВКЛЮЧеНИЯ е( Ш ) С с{щ), где г = О,1,..., т. Обратные включения получаются из симметричных рассуждений. Пусть теперь тождество w — w1 содержится в множестве Д„. Нам необходимо проверить, что для любого гомоморфизма (р : Е — VOn+i и любого к — 1,...,71+1 значения k.(wtp) и k.(v/tp) либо одновременно не определены, либо одновременно определены и равны. Предположим, что значение k.(wtp) определено.
Построим разбросанное подслово v = а\- ат слова w, удовлетворяющее следующим свойствам: Очевидно, что длина построенного слова v не превосходит п, а представление есть первое вхождение слова v в w. Тогда слово v является также разбросанным подсловом слова к/. При этом первое вхождение слова v в и/ удовлетворяет условиям c(u o) = с(гО[ )), с (го і) = c(w[),... ,c(wn) = c{w m). Очевидно, что Таким образом, мы показали, что значение k.(w (p) определено и k.(wip) = k.{w!tp), что и требовалось. Случай пЛ. Пусть тождество иг = -ш выполнено в " и v = аій2 ami где m гг, — разбросанное подслово слова ш. Рассмотрим первое вхождение (15) слова v в w и определим гомоморфизм р : Е —» по следующему правилу: пусть aeS, для і — 1,..., m положим
