Проблема конечного базиса для полугрупп преобразований

0.1 Постановка проблемы конечного базиса.

Пусть? — счетный алфавит, через ?+ и ?* мы обозначим соответственно свободную полугруппу и свободный моноид над Е. Тождеством над алфавитом Е называется пара слов u, v е ?+, которая обозначается посредством формального равенства и = v. Полугруппа S удовлетворяет тождеству и = v, если для любого гомоморфизма <р: —> S выполняется и<�р = vcp. Если I — некоторое множество тождеств, то говорят, что тождество и = v следует из I, если любая полугруппа 5, удовлетворяющая всем тождествам из I, удовлетворяет также тождеству и = v. Полугруппа S называется конечно базируемой, если все тождества этой полугруппы следуют из некоторого конечного набора ее тождеств (базиса тождеств полугруппы 5') — в противном случае S называется бесконечно базируемой. Пусть М — некоторый класс конечных полугрупп. Проблема конечного базиса для класса Л4 состоит в том, чтобы определить, какие полугруппы из М являются конечно базируемыми и какие — бесконечно базируемыми.

Решение проблемы конечного базиса известно для класса всех конечных групп. А именно, в [26] доказано, что любая конечная группа является конечно базируемой. Для конечных полугрупп это условие может не выполняться. Первый пример бесконечно базируемой полугруппы был приведен в [28]. Им стал 6-элементный моноид Брандта В, который может быть представлен в виде полугруппы 2×2-матриц относительно обычного матричного умножения. Естественно возникает задача классификации конечных полугрупп с точки зрения конечной базируемо-сти их тождеств. За последние 40 лет в этом направлении проделана большая работа, результаты которой по состоянию на 1985 г. и 2000 г. систематизированы в обзорных статьях [9, глава II] и [39] соответственно. Представляется, однако, что эти исследования еще далеки от полного завершения. В частности, для ряда конкретных конечных полугрупп, важных для теории и приложений, все еще неизвестно, конечен ли их базис тождеств.

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

0 0 1 0.

0 0 0 1 эффективному описанию полугруппы S определял бы, является она конечно базируемой или нет. Такая формулировка проблемы конечного базиса была предложена А. Тарским в начале 60-х годов в более общем случае, а именно, для класса всех конечных алгебр [37]. Вопрос о существовании такого алгоритма для конечных полугрупп открыт до сих пор. Отметим, что для класса всех конечных группоидов проблема Тарского была решена Р. Мак-Кензи в работе [24], где было показано, что такого алгоритма не существует.

Известен алгоритм, определяющий, является ли конечная инверсная полугруппа S конечно базируемой. Алгоритм основан на том, что для конечной базируемости полугруппы S необходимо и достаточно, чтобы моноид Бран-дта В не принадлежал многообразию var5. Необходимость этого условия была доказана М. В. Волковым в [1], а достаточность является следствием результатов М. В. Сапира [6].

0.2 Полугруппы преобразований.

Полугруппы преобразований являются классическим объектом общей теории полугрупп и изучение их абстрактных свойств занимает важное место в современной алгебре. Этой тематике посвящено огромное число публикаций, в том числе и обобщающего характера. Текущее состояние теории полугрупп преобразований отражено в недавнем обзоре Р. Салливана [36].

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

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

• Тп — полугруппа всех преобразований n-элементного множества,.

• МТп — полугруппа всех многозначных преобразований п-элемеитного множества,.

• VTn ~~ полугруппа всех частичных преобразований n-элементного множества,.

• Вп — полугруппа всех частичных многозначных преобразований п-элементного множества,.

• СТп (К) — полугруппа всех линейных преобразований n-мерного линейного пространства над конечным полем К.

Отметим, что последние две полугруппы удобно мыслить себе как полугруппы матриц. А именно, полугруппа СТп{К) есть не что иное как полугруппа п х n-матриц над конечным полем К, а Вп — полугруппа булевых п х п-матриц, то есть матриц, элементы которых принимают значения 0 или 1 и подчинены следующим законам сложения и умножения:

0 + 0 = 0- 0 = 0−1 = 1- 0 = 0, 1−1 = 1 + 0 = 0 + 1 = 1 + 1 = 1.

Среди подполугрупп полугруппы СТп{К) особый интерес представляет полугруппа всех верхних треугольных матриц, которую мы обозначим через Тп{К). На языке преобразований Тп (К) может быть охарактеризована следующим образом. Пусть V — n-мерное линейное пространство над полем К, и векторы {ei, е2,., е&bdquo-} образуют базис V. Рассмотрим флаг подпространств Vi С .,. С Vn, в котором подпространство Vi порождается векторами еь ., е, для всех г = 1,., п. Нетрудно понять, что полугруппа Тп (К) состоит из всех таких преобразований, для которых подпространства Vi,., Vn являются инвариантными. В недавней статье Ж. Алмейды, С. Марголиса, Б. Стейнберга и М. В. Волкова [12] было показано, что полугруппы треугольных матриц над конечными полями играют важную роль с точки зрения теории представлений и ее связи с формальными языками.

Аналогично, можно рассмотреть полугруппу булевых треугольных п х п-матриц. Эту полугруппу будем обозначать через ТВп.

Еще одной важной серией полугрупп матриц являются полугруппы унит,-реуголъных матриц, то есть верхних треугольных матриц, на главной диагонали которых все элементы равны 1. Полугруппу унитреугольных п х п-матриц над полем К будем обозначать через ЫТп{К), булевых унитреугольных п х n-матриц — через ЫТВп.

Далее мы будем считать, что множество, на котором действуют рассматриваемые нами преобразования, линейно упорядочено, и мы будем отождествлять его с отрезком натурального ряда {1,.,??,}. Среди всех полугрупп преобразований этого множества мы выделим так называемый базисный каркас, состоящий из тех полугрупп, преобразования которых характеризуются некоторой комбинацией следующих четырех фундаментальных свойств:

• всюду определенность,.

• инъективность,.

• монотонность (частичное преобразование, а называется монотонным, если для всех i, j из области определения, а из i < j следует, что i. a < i-a),.

• направленность (частичное преобразование, а называется направленным, если г < г. а для каждого г из области определения а).

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

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

• 1п, моноид всех частичных инъективных преобразований, симметрический инверсный моноид,.

• VOn, моноид всех частичных монотонных преобразований,.

• V? n, моноид всех частичных направленных преобразований.

Каждая другая полугруппа из базисного каркаса получается как теоретико-множественное пересечение каких-то из только что указанных моноидов. Например, полугруппа Sn = Тп П Хп состоит из всех всюду определенных инъективных преобразований и, разумеется, есть не что иное как группа всех перестановок множества {1,., п} (симметрическая группа). Единицу этой группы обозначим через l{i,.,"}.

При п > 2 базисный каркас состоит из 13 полугрупп, изображенных на следующей диаграмме:

Рис. 1. Базисный каркас полугрупп преобразований п-элементного множества.

Нетривиальные полугруппы, представленные на рисунке 1, интенсивно исследовались с самых разных точек зрения. Много внимания уделялось, например, вопросам их характеризации в терминах образующих и определяющих соотношений, см. недавний обзор [18]. Псевдомногообразия, порождаемые этими полугруппами, оказались весьма важными с точки зрения приложений алгебры в теории формальных языков, см. обзор [19].

Так, например, серия моноидов 0£п порождает псевдомногообразие всех^{-тривиальных} полугрупп, которое, в свою очередь, порождается синтаксическими моноидами кусочно-тестируемых языков, то есть языков вида S*aiS*a2 • • • afcS*, где к > О, <ц € Е, i — 1,., к. В терминах соответствия Эйленберга между псевдмоногообразиями конечных моноидов и многообразиями формальных языков (см., например, [29]) последнее условие может быть сформулировано следующим образом: псевдомногообразию всех J-тривиальиых полугрупп соответствует многообразие кусочно-тестируемых языков. Каждая из серий £п, V? n и VO? n порождает псевдомногообразие 71-тривиальных полугрупп, которому соответствует многообразие языков, порожденное языками вида? gai?*a2 • • • аиЩ., где к > 0 и Е0, Ej С Е, a, € Е, щ Еi для % = 1,., к. И, наконец, каждая из серий V? ln и VO? Xn порождают псевдомногообразие всех^{-тривиальных} полугрупп с коммутирующими идемпотентами. Этому псевдомногообразию, в свою очередь, соответствует многообразие языков, порожденное языками вида? jijai?*a2 • • -afcE?, где к > 0 и Е0, Ej С ?, ^ е Е, щ Ej U Eji для г = 1,., к.

Рассмотрим еще две серии полугрупп преобразований. Пусть заданы два множества Хп = {1,2,., п} и Х’п = {1', 2',., п'}. Определим преобразования ej и e’j (j — 1,2., п) на множестве Xn+1 U Х’п+1 следующим образом:

Через £'п [и, соответственно, ?"] мы обозначим полугруппы преобразований на множестве Xn+i U Х’п [Xn+i U Х^+1], порожденные преобразованиями е’р где j = 1,2,.,., п [ej, e’j где j = 1,2,., п и преобразованием е^+1].

Полугруппы £'п и исследовались Э. Соломоном в работе [34], связанной с Эйленберговым описанием многообразий формальных языков, распознаваемых 7?.-тривиальными моноидами.

Данные полугруппы интересны еще и тем, что являются примерами конструкции, иногда называемой моноидом Катала, на некоторого графа G. Опишем эту конструкцию. Пусть G = (V, Е) — конечный ориентированный граф. Для каждого ребра (a, b) g Е определим преобразование f^) множества V следующим образом: если г = j, если г ф jесли г = j, если i ф j.

X-f (a, b) = b, если х — a, х, в противном случае.

Моноидом Каталана графа G называется моноид, порожденный всеми возможными преобразованиями /(aj (,). Исследованию моноидов Каталана и их свойств посвящена работа Э. Соломона [35]. Несложно проверить, что полугруппа 0?", о которой речь шла выше, является моноидом Каталана для графа, являющегося цепью:

1 2 п-1 п.

Ф—>——.

Из определения полугрупп £'п и немедленно следует, что эти полугруппы также являются моноидами Каталана. А именно, £'п является моноидом Каталана для графа.

1 2 п п+1.

1' 2' п1 а — для графа.

12 п п+1.

1' 2' п' (п + 1)'.

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

0.3 Дополнительные замечания о проблеме конечного базиса.

Кратко обсудим небольшую тонкость, возникающую при обсуждении проблемы конечного базиса. Поскольку мы рассматриваем тождества конечных полугрупп, то весьма естественно сузить определения, приведенные в начале введения, до класса J всех конечных полугрупп. А именно, мы можем сказать, что тождество и = v следует в классе $ из системы тождеств /, если любая конечная полугруппа S, удовлетворяющая всем тождествам из /, удовлетворяет также тождеству и = v. В этом случае можно преобразовать и определение конечно базируемой полугруппы, а именно, будем говорить, что полугруппа S называется конечно базируемой в если все тождества этой полугруппы следуют в $ из некоторого конечного набора ее тождеств. В общем случае для алгебр и даже для группоидов, вопрос о том, является ли свойство конечной базируемости в классе конечных алгебр эквивалентным этому свойству в обычном смысле, является открытым. К счастью, для полугрупп эти два понятия конечной базируемости («абсолютная» и в совпадают, что было показано М. В. Сапиром в работе [32]. Из этого тем не менее не следует, что понятие следствия из системы тождеств в «абсолютном» смысле эквивалентно его «конечному» варианту, соответствующий пример можно найти в работе Ж. Черчилль [17].

Аналогичное замечание можно сделать и относительно проблемы конечного базиса для конечного моноида М как алгебры типа (2,0) и как полугруппы: моноид М конечно базируем в классе всех моноидов тогда и только тогда, когда он конечно базируем в классе всех полугрупп. Как и выше, из этого не следует эквивалентность между определениями следования из системы тождеств для моноидов и полугрупп. Например, тождество ху = xz влечет у = z в любом моноиде, но не в классе всех полугрупп.

Класс всех конечно базируемых полугрупп в определенном смысле «нерегулярен»: за исключением единичных примеров он не замкнут относительно стандартных теоретико-групповых операций или конструкций. Приведем несколько примеров такого нерегулярного поведения. Существуют бесконечно базируемые полугруппы, являющиеся:

• прямым произведением двух конечно базируемых полугрупп (соответствующие примеры можно найти в работах [2, 33, 31, 21]),.

• подполугруппой или гомоморфным образом конечно базируемой полугруппы (это следует из примера конечно базируемой полугруппы, являющейся прямым произведением двух бесконечно базируемых полугрупп, см. [33]),.

• полупрямым произведением двух конечно базируемых полугрупп (см. [20, 10, 7]),.

• прямоугольной связкой конечно базируемых полугрупп (см. [23]),.

• моноидом S1 для некоторой конечно базируемой полугруппы S (соответствующий пример можно найти в [28]).

Довольно интересный результат был получен М. В. Волковым в работе [2]. А именно, для любой конечной полугруппы S можно указать конечно базируемую полугруппу, А и конечную группу G (которая, в свою очередь, тоже конечно базируема), что прямое произведение S х G х, А будет бесконечно базируемым. Таким образом, каждая конечная полугруппа является прямым сомножителем некоторой бесконечно базируемой конечной полугруппы.

За 40 лет исследований, посвященных проблеме конечного базиса, сформировался определенный багаж методов доказательства бесконечной базируемое&tradeполугрупп. Мы приведем здесь основные идеи трех наиболее часто используемых методовдва из них будут применены в данной диссертации.

1. Синтаксический метод. Данный метод основан на следующей теореме Биркгофа о полноте [13], дающей синтаксическое описание понятия выводимости из некоторой системы тождеств:

Теорема Биркгофа. Нетривиальное полугрупповое тождество u — v следует из системы mootcdecme I тогда и только тогда, когда найдутся слова wo, wL,., Wk 6 ?+, такие что и = Wq, v = Wk и для каждого i =.

0.1.к — 1 существуют ai, bi G Е* и гомоморфизм Q '¦ —> что Wi — ai (si (i)bi, Wi+i = ai (ti (i)bi и тождество Si = U принадлежит системе.

1.

Для того чтобы показать, что id S не имеет конечного базиса тождеств, достаточно указать некоторую бесконечную последовательность тождеств / С id S и проверить, что из-за особенностей полугруппы S «длинные» тождества последовательности I не могут быть формально выведены из «коротких» тождеств системы id 5.

2. Метод критических полугрупп. Пусть V = varS'. Для любого натурального числа п мы обозначим через V^ многообразие, определенное всеми тождествами не более чем от п переменных, выполненных в V. Другими словами V^ может быть определено как класс всех полугрупп, чьи подполугруппы, порожденные не более чем п элементами, лежат в V.

Очевидно, что для любого п выполняется V^ D V, и если V конечно базируемо, то V^ = V для некоторого п. С другой стороны, по теореме Биркгофа о конечной базируемости тождеств от конечного числа переменных [13], каждое из многообразий V^ конечно базируемо. Следовательно, равенство V^ = V является не только необходимым, но и достаточным условием конечной базируемости полугруппы S. Таким образом, чтобы показать, что S бесконечно базируема, нужно проверить, что для любого п включение V (n) Э V строгое, а значит, существует полугруппа Sn Е V^ V. Полугруппы Sn, обладающие таким свойством, называются критическими полугруппами по отношению к S.

Для того, чтобы построить последовательность критических полугрупп необходимы конструкции, которые были бы чувствительны к удалению порождающих элементов. В самом деле, требование Sn € V^ V означает, что хотя Sn не принадлежит многообразию V, все ее подполугруппы, содержащие не более п порождающих элементов, ему принадлежат. Всего известно буквально несколько конструкций, которые удовлетворяют этим требованиям, и что интересно, большинство из них используют одни и те же приемы. А именно, эти конструкции некоторым образом «кодируют» определенные графы, так что удаление порождающих элементов соответствует удалению ребер этого графа, до тех пор, пока не получится остовное дерево этого графа. Например, в качестве критических полугрупп часто используются полугруппы частичных преобразований некоторого конечного множества, или, другими словами, полугруппы преобразований неполного автомата, и в качестве графа, о котором говорилось выше, выступает граф этого автомата.

3. Существенно бесконечно базируемые полугруппы. В выдающейся работе [6] М. В. Сапир показал, что если все ниль-полугруппы конечно базируемого многообразия V локально конечны, то V удовлетворяет нетривиальному тождеству вида Zn = w, где {Zn} есть последовательность слов Зимина, определяемая по правилу.

Z = Х и Zn+1 = Znxn+iZn.

Поскольку в любом конечно порожденном многообразии все полугруппы локально конечны, то любая конечная полугруппа, не удовлетворяющая никакому нетривиальному тождеству Zn = w, не только является бесконечно базируемой, но и обладает значительно более сильным свойством. А именно, эта полугруппа не принадлежит никакому конечно базируемому локально конечному многообразию. Полугруппы, удовлетворяющие последнему условию, называются существенно бесконечно базируемыми.

В работе [5] М. В. Сапир дал структурное описание существенно бесконечно базируемых конечных полугрупп. Пользуясь этим описанием, можно построить алгоритм, который по полугруппе, заданной таблицей Кэли определял бы, является ли эта полугруппа существенно бесконечно базируемой. Отметим здесь, что в случае конечных группоидов алгоритма, распознающего свойство «быть существенно бесконечно базируемым» не существует, это было показано Р. Мак-Кензи в [24].

Неоднократно упоминавшийся выше моноид Брандта В является примером существенно бесконечно базируемой полугруппы. Более того, существенная бесконечная базируемость полугрупп очень часто доказывается именно путем отыскания моноида Брандта в соответствующем многообразии. Однако, существуют существенно бесконечно базируемые полугруппы, для которых это не так. В работе [5] М. В. Сапир построил пример существенно бесконечно базируемой полугруппы Т такой, что В var Т. М. Джексон в [21, 22] показал, что любая такая полугруппа Т должна состоять как минимум из 56 элементов и содержать как минимум 9 не нильпотентных подгрупп. Он описал все 56-элементные существенно бесконечно базируемые полугруппы Т, такие, что В $ var Т и все минимальные с точки зрения отношения делимости1 существенно бесконечно базируемые полугруппы. Поскольку любая существенно бесконечно базируемая полугруппа имеет хотя бы один минимальный существенно бесконечно базируемый делитель, то последний результат дает еще одну алгоритмически эффективную характеризацию существенно бесконечно базируемых конечных полугрупп.

Стоит отметить, что для доказательства конечной базируемости до сих пор не были обнаружены «индустриальные» методы наподобие описанных выше. Как правило, конечная базируемость полугрупп доказывается непосредственно путем проверки того, что все тождества данной полугруппы выводятся из заданного конечного набора ее тождеств. При исследовании полугрупп, содержащих малое число элементов может быть применен результат, полученный А. Н. Трахтманом в работе [38], А именно, он показал, что любая полугруппа, содержащая не более 5 элементов является конечно базируемой. Из этого результата, в частности, следует тот факт, что моноид В является минимальной по числу элементов бесконечно базируемой полугруппой.

В заключение отметим, что в последнее время к проблеме конечного базиса для класса конечных полугрупп возник интерес и со стороны компьютерных наук. При изучении таких объектов, как графы, конечные автоматы или формальные языки, важную роль играют полугруппы, связанные с ними. Примерами таких полугрупп могут являться полугруппы переходов конечных автоматов, синтаксические моноиды формальных языков, моноиды Каталана и т. д. Свойства этих полугрупп часто определяют свойства соответствующих им объектов. Одним из таких определяющих свойств является, например, принадлежность данной конечной полугруппы некоторому многообразию. Следовательно, интерес представляет проблема распознавания принадлежности многообразию, порожденному некоторой конечной полугруппой 5и, в частности, вычислительная сложность этой проблемы. Пусть Т — конечная полугруппа, для которой мы хотим выяснить, верно ли, что Т? var 5. В том случае, когда полугруппа S конечно базируема, легко указать алгоритм, решающий эту задачу, и сложность этого алгоритма будет полиномиально зависеть от размера полугруппы Т. В самом деле, если Т| = п, а в записи некоторого конечного базиса тождеств полугруппы S встречается не более m переменных, то можно перебрать все возможные наборы из m элементов полугруппы Т, подставить эти элементы в базис тожхНатгомним, что полугруппа S делит полугруппу Т, если S является гомоморфным образом некоторой подполугруппы Т. Очевидно, что отношение делимости на классе всех конечных полугрупп является отношением порядка. деств и таким образом установить, выполнены ли все тождества полугруппы S в полугруппе Т, или, другими словами, принадлежит ли Т многообразию, порожденному полугруппой S. Очевидно, что сложность такого алгоритма 0(пт). В случае, если полугруппа S бесконечно базируема, проблема принадлежности многообразию var S остается нетривиальной и может не иметь полиномиального алгоритма. Пример такой конечной полугруппы S, для которой данная проблема является NP-трудной, был найден Р. Мак-Кензи и М. Джексоном в работе [25].

0.4 Проблема конечного базиса для различных серий полугрупп преобразований.

В работе М. В. Волкова [2] было получено полное решение проблемы конечного базиса для серий полугрупп Тп, МТп, VTn, Вп и? Тп{К). А именно, было показано, что что полугруппа Тп бесконечно базируема тогда и только тогда, когда п > 3, а полугруппы МТп, VTn, Вп и? Тп (К) бесконечно базируемы тогда и только тогда, когда п > 2. Эти же результаты следуют из результатов М. В. Сапира [5].

Обратимся к проблеме конечного базиса для полугруппы Тп{К) всех верхних треугольных п х n-матриц над конечным полем К. Очевидно, что полугруппа Т{К) коммутативна, и, следовательно, базис ее тождеств конечен. Вопрос о конечной базируемости полугруппы Тп (К) при п > 2 был в явном виде поставлен в [9] и затем повторен в [39].

Ситуация аналогична и для полугруппы ТВп всех булевых треугольных п х n-матриц. Полугруппа ТВ содержит всего два элемента и, следовательно, имеет конечный базис тождеств, а при п > 2 проблема конечного базиса оставалось открытой.

Полугруппа ЫТп{К) унитреугольных п х n-матриц над конечным полем не представляет особого интереса с точки зрения проблемы конечного базиса: поскольку определитель любой унитреугольной матрицы равен 1, то эта полугруппа является группой и поэтому конечно базируема. Однако, аналогичный вывод не может быть сделан относительно полугруппы ЫТВп всех булевых унитреугольных п х n-матриц. Полугруппы UTBi и UTB2 конечно базируемы, поскольку содержат один и два элемента соответственно. Однако, для больших значений п очевидным образом результат получить не удается.

Перейдем к рассмотрению полугрупп базисного каркаса с точки зрения проблемы конечного базиса. Очевидно, что полугруппа Sn (являющаяся группой) и {l{i,., n}}> конечно базируемы. С другой стороны, выше уже упоминалось, что полугруппа Тп бесконечно базируема при п > 3, и можно показать, что VOn, Tjj, On и VOXn при n > 3 также бесконечно базируемы (более того, указанные полугруппы существенно бесконечно базируемы, поскольку каждая из них порождает многообразие, содержащее В). Проблема конечного базиса для 0£п была недавно решена в [40], где было показано, что эта полугруппа бесконечно базируема тогда и только тогда, когда п > 5. Вопрос о конечной базируемости оставшихся полугрупп был в явном виде сформулирован в [39].

Полугруппа ?[ содержит три элемента и поэтому конечно базируема. Для остальных полугрупп из серий £'п и аналогичным образом решить проблему конечного базиса не удается.

Целью данной диссертации является решение следующей задачи:

Задача. Решить проблему конечного базиса для серий полугрупп Тп{К), ТВп, ЫТВп, £п, V? n, VO? n, V? ln, VO? ln, ?'n и С.

0.5 Содержание диссертации.

Основные результаты диссертации решают проблему конечного базиса для серий полугрупп Тп{К), ТВ п 1 МТВп, £п, V? n, VO? n, V? ln, VO? ln, ?'n.

В главе 1 рассматриваются полугруппы треугольных п х n-матриц над конечными полями. В § 1.1 и § 1.2 доказываются некоторые свойства полугруппы Тп{К) и приводятся вспомогательные результаты, касающиеся существенно бесконечно базируемых полугрупп. В § 1.3 доказывается критерий существенной бесконечной базируемости для полугрупп треугольных матриц над конечными полями и таким образом решается проблема конечного базиса для серии полугрупп Тп (К).

Глава 2 посвящена изучению полугруппы булевых треугольных п х п-матриц ТВп. В § 2.1 исследуются свойства данных полугрупп, а в § 2.2 решается проблема конечного базиса для ТВп, а именно, доказывается критерий существенной бесконечной базируемости этой полугруппы. В § 2.3 приводится описание системы тождеств, выполненных в полугруппах всех булевых унитреугольных п х n-матриц и полностью решается проблема конечного базиса для этой серии полугрупп.

В главе 3 рассматриваются полугруппы преобразований из базисного каркаса, а также полугруппы £'п и Параграф 3.1 носит вспомогательный характер, в § 3.2 описываются системы тождеств, выполненные в данных полугруппах, а в § 3.3 решается проблема конечного базиса для этих полугрупп.

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

Нумерация теорем, лемм, предложений и следствий двойная. Первое число соответствует номеру главы, второе — номеру утверждения.

Основным результатом главы 1 является следующая теорема.

Теорема 1.1 Полугруппа Тп (К) всех верхних треугольных п х п-матриц над конечным полем К существенно бесконечно базируема тогда и только тогда, когда К > 2 и п > 4.

Мы отмечали выше, что существенная бесконечная базируемость полугрупп как правило доказывается путем отыскания моноида В в многообразии, порожденном исследуемой полугруппой. Мы показываем, что В не принадлежит многообразию, порожденному полугруппой Тп{К) ни при каких п и К, поэтому теорема 1.1 не может быть получена указанным методом. Можно сказать, что полугруппы верхних треугольных матриц над конечными полями составляют первый класс примеров существенно бесконечно базируемых полугрупп «естественного происхождения», не сводящихся к В.

Совокупность всех верхних треугольных п х n-матриц над полем является не только полугруппой, но и кольцом. М. В. Сапиром в [6, следствие 6.3] было доказано, что если мультипликативная полугруппа конечного кольца R имеет конечный базис тождеств, то факторкольцо кольца R по его радикалу — прямая сумма конечных полей. Мы видим теперь, что это утверждение нельзя обратить: факторкольцо кольца Тп{К) по его радикалу — прямая сумма п копий поля К, а полугруппа Тп{К) при К > 2 и п > 4 не конечно базируема. Насколько нам известно, в литературе такие примеры ранее не отмечались.

Первым основным результатом главы 2 является следующая теорема:

Теорема 2.1 Полугруппа ТВп существенно бесконечно базируема тогда и только тогда, когда п > 4.

Несмотря на кажущуюся схожесть рассматриваемых нами полугрупп треугольных матриц над конечными полями и булевых треугольных матриц, а также результатов относительно существенной бесконечной базируемости данных полугрупп, эти результаты имеют принципиально разную природу. А именно, для полугрупп ТВп при п > 4 существенная бесконечная базируемость доказывается стандартным в аналогичных ситуациях способом: в многообразии varT&i отыскивается моноид Брандта В.

Моноиды ТВп были подробно исследованы в работе Ж-Э. Пэна и X. Стра-убипга [30]. С использованием методов теории формальных языков они показали, что псевдомногообразие, порожденное серией этих моноидов совпадает с достаточно хорошо изученным псевдомногообразием PJ. Известно, что моноид Брандта В принадлежит псевдомногообразию PJ (см., например, [11, раздел 11.6]), следовательно, можно указать такое число т, что.

В € vaxTBm. Тогда, очевидно, для любых значений п > т полугруппа ТВп является существенно бесконечно базируемой. Теорема 2.1 определяет значение числа m с таким свойством, а именно, m = 4.

Прежде чем приступить к описанию второго основного результата главы 2, введем необходимые определения. Пусть v, w — слова над алфавитом Е. Будем говорить, что слово г/ является разбросанным подсловом слова w, если v = а—-ат, где ai,., am? Ни можно подобрать такие слова w0, wi,., wn-i, wn <Е Е*, что гу = ty0aiw/i • • • Шп-А^- (1) другими словами это означает, что буквы слова v входят в w в качестве подпоследовательности. Через Jj. мы обозначим семейство всех таких тождеств w = w', что для любого т < к множества разбросанных под слов длины m слов ии ад' совпадают. Нами было получено описание тождеств полугруппы булевых унитреугольных матриц:

Предложение 2.3 Для любого натурального п множество Jn совпадает с множеством всех тоэюдеств, выполненных в полугруппе UTBn+1.

Системы тождеств Jk были подобно изучены Ф. Бланш-Садри в работах [14, 15, 16]. В частности, она доказала, что данная система тождеств бесконечно базируема тогда и только тогда, когда к > 4. Из этого результата и из предложения 2.3 немедленно следует второй основной результат главы 2:

Теорема 2.2 Полугруппа ЫТВп бесконечно базируема тогда и только тогда, когда п > 5.

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

Таблица 1: Проблема конечного базиса для полугрупп п х п-матриц.

Основное множество: Тип матриц: произвольные треугольные унитреугольные конечное поле К бесконечно базируема для всех п> 2 бесконечно базируема при К>2 и п > 4 конечно базируема при п > 2 булево полукольцо бесконечно базируема при п > 2 бесконечно базируема при п > 4 бесконечно базируема тогда и только тогда, когда п> 5.

Для формулировки результатов главы 3 нам понадобится несколько дополнительных обозначений и определений. Обозначим через c (w) алфавит слова w, то есть множество всех букв, встречающихся в w. Пусть v — разбросанное подслово слова w. Представление (1) назовем первым вхоокдени-ем слова v в слово w, если flj ^ c (w^-i) для любого i = 1,., то. Подслова щ, ц}1,., wm слова w будем называть факторами первого вхождения слова v в w. Очевидно, что для любого разбросанного подслова можно единственным образом указать его первое вхождение. Если для слова w существует всего одно представление вида (1), то слово v назовем уникально разбросанным подсловом слова w.

Определим несколько систем тождеств. Через Rk [соответственно, R’k] мы обозначим набор всех таких тождеств w = w', что выполняются следующие два условия:

1) для любого т < к множества разбросанных подслов длины т слов w и и>' должны совпадать;

2) если представления w = WQCLiWi ¦ • • wm-iamwm и и> = Woa^-'-w'^amW^ являются первыми вхождениями разбросанного подслова v = % • • • ат длины т < к в слова w и w', то должны совпадать алфавиты факторов первых вхождений слова v в w н wc (wi) = c (w'i) для всех i = 0,., т [соответственно, для всех г = 0,., т — 1].

Через С к обозначим набор всех таких тождеств w — w', что выполняются следующие три условия:

1) c{w) = c (w');

2) для любого т < к множества уникально разбросанных подслов длины т слов w и и>' должны совпадать;

3) если для уникально разбросанного подслова v = а • ¦ • ат длины т < к имеют место представления w = w0aiwi • • • wm-iamwm и w = w'0a1w'1—-w'm1amw'm, то должны совпадать алфавиты соответствующих факторов первых вхождений: c (wi) = с (ю'{) для всех г = 0,., т.

Доказательству следующего результата посвящен § 3.2:

Предложение 3.2 Для любого натурального числа п справедливы следующие утверждения:

1) множество Rn совпадает с множеством, всех тождеств, выполненных в полугруппах £п+2, V? n+i, 'РО?п+i и ?

2) множество R’n совпадает с множеством всех тождеств, выполненных в полугруппе £'п;

3) множество Сп совпадает с множеством всех тождеств, выполненных в полугруппах V? Tn+ и VO? Xn+i.

С использованием описаний тождеств, полученных в предложении 3.2, была решена проблема конечного базиса для полугрупп базисного каркаса и полугрупп £'п и ?%¦ Основным результатом главы 3 является следующая теорема:

Теорема 3.1 Для любого натурального числа п > 3 полугруппы £п+2, V? n+i, VO? n+i, £'п, V? ln+i и VO? ln+i не имеют конечного базиса тождеств.

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

0.6 Апробация результатов.

Основные результаты диссертации докладывались на XXIV Конференции молодых ученых механико-математического факультета МГУ (Москва, 2002), 57-х Герценовских чтениях (Санкт-Петербург, 2003), Международной алгебраической конференции, посвященной 250-летию Московского университета и 75-летию кафедры высшей алгебры (Москва, 2004), Международной конференции по полугруппам и языкам CSL'2005 (Лиссабон, Португалия, 2005), Международной алгебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина (Екатеринбург, 2005), заседании семинара кафедры высшей алгебры МГУ (2002), заседаниях семинара «Алгебраические системы» (УрГУ).

Основные результаты диссертации опубликованы в работах [41]-[50]. Автор выражает глубокую благодарность своему научному руководителю профессору М. В. Волкову за постановки задач и постоянное внимание к работе, а также профессору Л. Н. Шеврину за ценные обсуждения текста диссертации.

0.7 Список обозначений var S1 — многообразие, порожденное полугруппой S. id S — множество тождеств, выполненных в полугруппе S. — свободная полугруппа над алфавитом ?.

Е* — свободный моноид над алфавитом Е. г. х — образ элемента г при преобразовании х. wip — образ элемента w при гомоморфизме ц>.

Запись w = w' означает равенство слов шию’в свободном моноиде ?*. w = w' — тождество, частями которого являются слова w и w'. it — слово хх ¦ ¦ -хт, где ., хт € ?. V — слово хт ¦ ¦ ¦ xi, где хт Е ?.

GF{2) — поле, состоящее из двух элементов.

1. Волков М. В. О базисах тождеств полугрупп Брандта/ В сб. Исследов. алгебраическ. систем по свойствам их подсистем. Свердловск, 1985. С.38−42.

2. Волков М. В. О конечной базируемости многообразий полугрупп// Ма-тем. заметки. 1989. Т.45, № 3. С.12−23.

3. Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Наука, 1972.

4. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. Т 1, 2. М.: Мир, 1972.

5. Сапир М. В. Проблемы бернсайдовского типа и конечная базируемостъ в многообразиях полугрупп// Изв. Акад. Наук СССР, Сер. Мат, 51. С.319−340.

6. Сапир М. В. Существенно бесконечно базируемые конечные полугруппы// Матем. сб. 1987. Т.133. № 2. С. 154−166.

7. Тищенко А. В. Сплетения многообразий и полуархимедовы многообразия полугрупп// Труды ММО. 1996. Т.57. С.318−338.

8. Шеврин Л. Н. К теории эпигрупп. /// Матем. сб. 1994. Т.185. № 8. С.129−160.

9. Шеврин Л. Н., Волков М. В. Тождества полугрупп// Изв. вузов. Математика. 1985. № 11. С.3−47.

10. Almeida J. On iterated semidirect products of finite semilatticies// J. Algebra, 142, 1991. P.239−254.

11. Almeida J. Finite Semigroups and Universal Algebra, World Scientific, Singapore, 1995.

12. Birkhoff G. On the structure of abstract algebras// Proc. Cambridge Philos. Soc. 31, 1935. P.433−454.

13. Blanchet-Sadri F. Games, equations and the dot-depth hierarchy// Comput. Math. Appl. 18, 1989. P.809−822.

14. Blanchet-Sadri F. Equations and dot-depth one// Semigroup Forum 47, 1993. P.305−317.

15. Blanchet-Sadri F. Equations and monoid varieties of dot-depth one and two// Theor. Сотр. Sci. 123, 1994 P.239−258.

16. Churchill G. Almeida’s generalized variety problem// J. Algebra, № 196, 1997. P.499−519.

17. Fernandes V. H, Presentations for some monoids of partial transformations on a finite chain: A survey/ В кн. Gracinda M. S. Gomes, J. Pin, S. V. Sil-va, Semigroups, Algorithms, Automata and Languages. World Scientific, Singapore, 2002. P. 363−378.

18. Irastroza C. Base поп finie de varietes/ В кн. К. Mehlhorn (ed.) Theor. Aspects Comput. Sci. 2nd ann. Symp., Saarbriichen/Germany, 1985 Lect Notes Comput. Sci. 182], Springer-Verlag, Berlin-Hiedelberg-N.Y., 1985. P.180−186.

19. Jackson M. Small Semigroup Related Structures with Infinite Properties. Ph.D. thesis, Univ. of Tasmania, Hobart. 1999.

20. Jackson M. Small inherently nonfinitely based finite semigroups. Semigroup Forum. 2002. V. 64 № 2. P.297−324.

21. Mashevitzky G. I. On bases of completely simple semigroups identities// Semigroup Forum, 30, 1984, P.67−76.

22. McKenzie R. Tarski’s finite basis problem is undecidable// Int. J. Algebra abd Computation, 1996, № 6, P.49−104.

23. Jackson M., McKenzie R. Interpreting graph colorability in finite semigroups// Int. J. Algebra and Computation. 2006. V. 16, № 1. P.119−140.

24. Oates S., Powell M. B. Identical relations in finite groups// J. Algebra 1964. V.l. № 1. P. 11−39.

25. Okninski J. Semigroup of Matrices. World Scientific, 1998.

26. Perkins, P. Bases for equational theories of semigroups// J. Algebra 1969. V.ll. № 2. P.298−314.

27. Pin J-E. Varieties of Formal Languages. North Oxford Academic, 1986.

28. Sapir 0. Identities of Finite Semigroups and Related Questions. Ph.D. thesis, Univ. of Nebraska, Lincoln. 1997.

29. Sapir M. V. Sur la propriete de base finie pour les pseudovarietes de semi-groupes finis// C. R. Acad. Sci. Paris (Ser. I) № 306, P.795−797.

30. Sapir M. V. On Cross semigroup varieties and related questions// Semigroup Forum, 42, 1991. P.345−364.

31. Solomon A. Stratifications of the variety of %-trivial monoids// Research Report 94−40, School of Mathematics and Statistics, Univ. of Sydney, 1994.

32. Solomon A. Catalan monoids, monoids of local endomorphisms, and their presentations// Semigroup Forum, 53, 1996. P.351−368.

33. Sullivan R. P. Transformation semigroups: past, present and future/ В кн. P. Smith, E. Giraldes, P. Martins (eds.) Proceedings of the international conference on semigroups, Braga, 1999, World Scientific, Singapore, 2000, P. 191−243.

34. Trahtman A. N. The finite basis problem for semigroups of order less than six// Semigroup Forum, 1983, 27. P.387−389.

35. Volkov M. V. The finite basis problem for finite semigroups// Mathematica Japonica. 2001. V.53. № 1. P.171−199.

36. Volkov M. V. Reflexive relations, extensive transformations and piecewise testable languages of a given height// Int. J. Algebra and Computation. V. 14, № 5−6. 2004. P.817−827.

37. Гольдберг И. А. Тождества полугрупп треугольных матриц над конечными полями// Тезисы студенческих научных работ: Направление «Естественные науки». Екатеринбург: Изд-во Уральского университета, 2002. С. 15.

38. Гольдберг И. А. Тождества полугрупп треугольных матриц над конечными полями// Тезисы докладов конф. молодых ученых, Изд-во МГУ, 2002. С. 53.

39. Волков M. В., Гольдберг И. А. Тождества полугрупп треугольных матриц над конечными полями// Матем. заметки. Т.73, № 4, 2003. С.502−510.

40. Goldberg I. A. Identities of some monoids of transformations of a finite chain// Международная алгебраическая конф., посвященная 250-летию Московского университета. Тезисы докладов. Изд-во МГУ, 2004. С. 195 197.

41. Goldberg I. A., Volkov M.V. On the finite basis problem for semigroups of boolean triangular matrices// Международная алгебраическая конф., посвященная 250-летию Московского университета. Тезисы докладов. Изд-во МГУ, 2004. С. 197−198.

42. Goldberg I. A. On the finite basis problem for certain transformation monoids// Int. conf. «Semigroups and Languages». Lisbon. Univ. of Lisbon. 2005. P.14−15.

43. Goldberg I. A. On the finite basis problem for certain transformation monoids// Международная алгебраическая конф. Тезисы докладов. Екатеринбург. 2005. С.19−21.

44. Гольдберг И. А. Проблема конечного базиса для моноидов направленных преобразований// Уральский государственный университет, Екатеринбург. 2006. Деп. в ВИНИТИ 20.04.2006 № 517 В2006. 21 с.