О комбинаторных свойствах бернсайдовых полугрупп тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи УДК 512.531

005006794

ПЛЮЩЕНКО Андрей Николаевич

О КОМБИНАТОРНЫХ СВОЙСТВАХ БЕРНСАЙДОВЫХ ПОЛУГРУПП

01.01.06 — Математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физика-математических наук

1 2 ПНВ2012

Екатеринбург 2011 г.

005006794

Работа выполнена на кафедре алгебры и дискретной математики Института математики и компьютерных наук Уральского федерального университета имени первого Президента России В. Н. Ельцина.

Научный руководитель:

доктор физико-математических наук А. М. Шур

Официальные оппоненты:

доктор физико-математических наук, профессор В. С. Губа

кандидат физико-математических наук И. А. Гольдберг

Ведущая организация:

Математический институт им. В. А. Стеклова Российской академии наук

Защита диссертации состоится «31» января 2012 года в 1200 на заседании диссертационного совета Д 004.006.03 в Институте математики и механики УрО РАН по адресу: 620990, г. Екатеринбург, ул. С. Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослан «26» декабря 2011 г.

Ученый секретарь диссертационного совета Д 004.006.03,

кандидат физ.-мат. наук И. Н. Белоусов

Общая характеристика работы

Актуальность темы. Полугруппы, удовлетворяющие тождеству вида ж" = хп+т для некоторых п, т ^ 1, образуют важный подкласс класса всех периодических полугрупп и представляют собой классический объект исследования. Такие полугруппы называют полугруппами бернсай-дова типа, или бернсайдовыми полугруппами. Проблематика бернсайдо-вых полугрупп естественным образом развивает аналогичную проблемаг тику для бернсайдовых групп, т. е. групп с тождеством хт = 1. Изучение последних было начато в 1902 году Бернсайдом [8], интересовавшимся, всякая ли конечно порожденная группа с ограниченным периодом конечна (так называемая ограниченная проблема Бернсайда).

Важное место в теории бернсайдовых полугрупп занимают свободные бернсайдовы полугруппы — полугруппы, свободные в многообразии уаг{ж" = хп+т} (для фиксированных п,т ^ 1), так как всякая полугруппа из уаг{х" = х"+т} есть гомоморфный образ подходящей свободной бернсайдовой полугруппы.

Свободные бернсайдовы полугруппы изучались многими исследоваг телями, начиная со второй половины XX века и по настоящее время. Выл разработан соответствующий инструментарий для изучения таких полугрупп, использующий как теоретико-групповые методы, так и методы теории формальных языков (в этом случае элементы свободной бернсайдовой полугруппы рассматриваются как классы эквивалентных слов над соответствующим алфавитом), методы общей комбинаторики и теории графов. Всплеск активности в этой области наблюдался в 1990-ые годы: благодаря целому ряду работ (Кадорек и Полак |19], де Лука и Варик-кио [9,10], Маккаммонд [21], до Лаго [12-14], В. С. Губа [17,18]), удалось установить немало важных свойств, проясняющих внутреннюю структуру таких полугрупп, а также решить ряд ключевых проблем для свободных бернсайдовых полугрупп. Более подробно с теорией бернсайдовых полугрупп можно ознакомиться, например, по обзорной статье [15], книгам по теории полугрупп [3,11] и др.

Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы. Тесным образом решение проблемы равенства слов связано с гипотезой о том, что любой элемент свободной бернсайдовой полугруппы является рациональным языком. Эта гипотеза, сформулированная Бжозовским в 1969 году для полугрупп с тождеством хп = хп+1, была затем расширена Маккаммондом на случай произвольных пит.

К настоящему времени удалось достаточно хорошо описать строение свободных бернсайдовых полугрупп произвольного ранга к и тождеством хп — хп+т (для таких полугрупп мы будем использовать обозначение В(к,п,п + т)) при п ^ 3. Так, например, в [13] показывается, что все максимальные подгруппы полугруппы В(к, п,п + т) при п ^ 3 циклические порядка т, а каждый элемент такой полугруппы, рассматриваемый как класс эквивалентных слов, содержит единственное слово минимальной длины. В 1990 году де Лука и Вариккио подтвердили гипотезу Бжозовского для полугрупп В(к,п,п + 1) сп^ 5 ([9]). Маккаммонд распространил эту гипотезу на случай полугруппы В(к, п, п+т) с произвольным т ^ 1 и независимо доказал ее справедливость при п ^ 6, т ^ 1 ([21], 1991). Позже до Лаго усовершенствовал метод де Луки и Вариккио и улучшил оценку до п ^ 4,т ^ 1 ([12], 1992). Наконец, В. С. Губа показал справедливость гипотезы для п ^ 3, т ^ 1 ([17,18], 1993).

Разрешимость проблемы равенства слов следует из справедливости гипотезы Бжозовского: так как всякий элемент полугруппы В(к, п, п+тп) является рациональным языком, мы можем по одному из двух данных слов построить автомат, распознающий его класс эквивалентности, и проверить, распознает ли этот автомат второе слово.

Несмотря на то, что в общем случае вопрос о разрешимости проблемы равенства слов для полугрупп В(к, 1,1 + тп) остается открытым, ответ на него определенным образом зависит от ответа на аналогичный вопрос для свободных бернсайдовых групп (см. [19]). В частности, проблема равенства слов разрешима при тп= 1,2,3,4,6, так как в этом случае свободная бернсайдова группа В(к,тп) (ранга к и с тождеством хт = 1) конечна для любого к. Более того, в серии работ [1,4-6] показывается разрешимость проблемы равенства слов для групп В (к, т) при любом к и нечетном т ^ 665 или кратном 16 значении тп ^ 8000. Следовательно, проблема равенства слов разрешима и для полугрупп В (к, 1,1 + т) при тех же значениях т. Во всех остальных случаях проблема равенства слов остается открытой. Что касается гипотезы Бжозовского, она, очевидно, справедлива для конечных полугрупп В(к, 1,1 + т). Опираясь на результаты работ [1,4-6], до Лаго показал ([14]), что гипотеза Бжозовского неверна для полугрупп В(к, 1,1 + тп), где к > 1, при т ^ 8000 и при нечетном т ^ 665. Для остальных значений тик вопрос остается открытым. Кроме того, получено достаточно хорошее описание структуры полугруппы В(к, 1,1 + тп) для любого т ^ 1, в частности, работа Грина и Риса ([16]) дает простое описание 23-классов такой полугруппы.

Наименее изученными остаются полугруппы с тождеством х2 = х2+т : проблема равенства слов в этом случае до сих пор не решена, а гипотеза Бжозовского при болыпйх значениях т оказывается неверной (см. [14]).

Структура полугрупп В (к, 2,2 + т) при гп ^ 2 оказывается сложнее структуры полугрупп В(к,п,п + т) при п ^ 3,ш ^ 1. Тал, например, известно ([14]), что полугруппа В(к, 2,2 + т.) при к > 1 и гп ^ 2 содержит максимальные подгруппы, не являющиеся циклическими группами, а также существуют элементы полугруппы, которые как классы эквивалентных слов содержат несколько слов минимальной длины. Случай гп = 1 остается единственным, при котором полугруппа В(к, 2,2 + гп) еще может иметь достаточно простую структуру. В связи с этим, особый интерес представляют полугруппы В{к, 2,3): интерес этот вызван и тем, что полутруппы вида В(к, п,п+ 1) составляют важный подкласс бернсайдовых полугрупп. Исторически теория бернсайдовых полугрупп (исключая бернсайдовы группы) начиналась с изучения именно таких полутрупп. Отметим, гипотеза Бжозовского была выдвинута для свободных бернсайдовых полугрупп с тождеством хп = хп+1 и еще в 1980 году была включена Вжозовским в список открытых проблем [7]; лишь позже Маккаммонд распространил эту гипотезу на любые бернсайдовы полугруппы. Среди свободных бернсайдовых полугрупп с тождеством хп = 1п+1 полугруппы В(к, 2,3) — единственные, для которых и проблема равенства слов, и гипотеза Бжозовского остаются открытыми.

Цель работы. Основной целью диссертации является исследование проблемы равенства слов и гипотезы Бжозовского для полугрупп В(к, 2,3): разработка новых методов и подходов к решению данных проблем. Часть полученных в диссертации результатов обобщается на полугруппы В(к, 2,2 +тп) для произвольного т.

Научная новизна. Все результаты являются новыми.

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

Апробация результатов работы. Результаты диссертации были представлены на XIV международной конференции студентов, аспирантов и молодых ученых «Ломоносов 2007», на свердловском областном конкурсе студенческих работ «0лимп-2007», на 6-й международной конференции по комбинаторике слов \VORDS2007 (Марсель, 2007), «Международной конференции по полугруппам, алгебре и приложениям ААА82» (Потсдам, 2011), 15-й международной конференции «Развитие теории языков» (Милан, 2011), международной конференции «Мальцевские чтения» (Новосибирск, 2011). Автор выступал с докладами по теме диссер-

тации на семинаре «Алгебраические системы» (УрГУ, рук. Л. Н. Шев-рин, 2007-2011), на алгебраическом семинаре института математики и механики УрО РАН (2011), на семинаре «Алгоритмические вопросы алгебры и логики» (МГУ, рук. С. И. Адян, 2011).

Публикации. По теме диссертации написано 7 работ: [23-29]. Из них статья [26] опубликована в издании из списка, рекомендованного ВАК, а статьи [28,29] — в зарубежных изданиях, удовлетворяющих достаточному условию ВАК. Работы [23,25] являются тезисами (в том числе электронная публикация [25]); статьи [27,28] опубликованы в сборниках трудов конференций; 3 работы ([27-29]) написаны совместно с А. М. Шуром, однако доказательства основных результатов принадлежат автору.

Структура и объем диссертации. Диссертация состоит из введения, трех глав и списка литературы. Объем диссертации составляет 108 страниц. Библиографический список содержит 39 наименований.

Краткое содержание работы

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

1. Пусть Ек = {1,...,&}, где к = 1,2,____ Свободная бернсайдова полугруппа ранга к и тождеством хп = хп+т для некоторых фиксированных чисел п, т ^ 1 с точностью до изоморфизма определяется как фактор-полугруппа

В{к, п, п + т) = Е£/ ~к,п,т

свободной полугруппы £¡2" по конгруэнции ~*,„,т> порожденной всеми парами вида (У", Уп+т), где У е Е£. Класс эквивалентности со-

держащий слово IV е Е£, обозначается через [И^п,™- При рассмотрении конкретной Полугруппы В(к, п,п + т) мы будем опускать индексы и писать просто ~ й [И7], где IV 6 Е£. Помимо свободной полугруппы мы рассматриваем также свободный моноид получающийся из полугруппы Е£ присоединением пустого слова А (слова длины 0), служащего единицей свободного моноида.

Договоримся длину слова IV (число букв в нем) обозначать через \ \У\, а г-ую букву слова IV — через \¥Щ. Понятия подслова, степени слова и

пр. вводятся естественным образом. Подслово Y слова W называется собственным, если У ф W.

Периодом слова W называется число р со свойством: W[i] = И^[г+р] для любого г = 1,..., |JV| — р. Экспонентной exp(W) слова W называется отношение длины слова W к его минимальному периоду, а локальной экспонентной lexp(W) — максимум из экспонент всех подслов слова W. Наконец, введем понятие сильно локальной экспоненты 1ехр<(5У) слова W как максимум из экспонент всех собственных подслов слова W.

Слово W называется ß-свободным, если lexp(W) < ß, и ß+ -свободным, если lexp(W) ^ ß. Аналогично, слово W мы назовем почти ß-свободным (почти ß+-свободным), если, соответственно, выполняется lexp<(VK) < ß и lexp<(W) < ß. [Почти] 3-свободные (2+-свободные) слова называют также [почти] бескубными (соответственно, сильно бескубными) словами.

Легко проверить, что слово V 6 Е£ [почти] является сильно бескуб-ным тогда и только тогда, когда оно не содержит [собственных] подслов вида XYXYX, где X 6 У 6

Пусть ß' < ß". Очевидно, что любое ß'- или /3'+-свободное слово является также и ß"- или, соответственно, /3"+-свободным. Аналогичное утверждение справедливо и для почти свободных слов. Однако слово W может быть почти ß'- или /3'+-свободным, но не являться ß"- или ß"+-свободным. Так, например, слово 111 почти сильно бескубно, но при этом оно является кубом.

2. Языком над алфавитом Е называется произвольное подмножество из Е*. Произведением языков С и К, называется язык

ОС = {UV | U е С, V € К),

а итерацией языка £ называется язык С = Ug0£l.

Язык называется рациональным, или регулярным, если он может быть записан при помощи регулярного выражения — выражения, содержащего одноэлементные языки и операции теоретико-множественного объединения, произведения и итерации языков. Согласно теореме Клини, рациональные языки — это в точности те языки, которые можно распознать при помощи детерминированных конечных автоматов (подробнее см., например, [3,20]).

Для любого языка С С Е* комбинаторная сложность есть функция рс(п): N0 —► N0) которая определяется как Рс(тг) — \С П Еп|, где Е" — множество всех слов длины п над алфавитом Е. Основным инструментом для оценки степени роста комбинаторной сложности языка служит индекс роста gr(L) = Нт«-^ p.c(n)1/".

Как показывают результаты, полученные различными авторами в ходе исследования свободных бернсайдовых полугрупп, структура таких полутрупп зависит в основном от параметров пит (от п в большей степени и от т — в меньшей). Что касается параметра к, то при к = 1 свободные бернсайдовы полугруппы суть конечные циклические полугруппы. При к > 1 полугруппы В{к, п,п + т) имеют весьма схожую структуру (при фиксированных пит).

В связи с вышесказанным, изучение проблемы равенства слов и гипотезы Бжозовского для полугрупп В (к, 2,3) представляется разумным проводить в два этапа: на первом этапе доказать сводимость рассматриваемых проблем для полугрупп В(к, 2,3) произвольного ранга к к соответствующим проблемам для какой-то полугруппы В(к', 2,3) фиксированного ранга к!, после чего работать только с этой полугруппой. Наиболее перспективной в этом плане является полугруппа 5(2,2,3): во-первых, для исследования слов и языков над бинарным алфавитом разработан достаточно большой и разнообразный инструментарий, во-вторых, случай к = 2 представляется наиболее простым, в-третьих, для полугруппы В(2,2,3) уже получен ряд результатов. В частности, в диссертации существенно развивается техника, изложенная в [2].

Первая глава диссертации полностью реализует первый этап нашего исследования. Основными результатами этой главы являются следующие две теоремы.

Теорема 1. Проблема равенства слов для полугруппы В(к, 2,3) произвольного ранга к ^ 2 разрешима тогда и только тогда, когда проблема равенства слов разрешима для полугруппы В(2,2,3).

Теорема 2. Гипотеза Бжозовского для полугруппы В(к, 2,3) при к ^ 2 справедлива тогда и только тогда, когда эта гипотеза справедлива для полугруппы В(2,2,3).

Для доказательства теорем 1 и 2 в диссертации вводится операция склейки слов по фиксированному слову, обобщающая операцию произведения слов, и строится функция а: —» сохраняющая операцию склейки и такая, что для любых слов и,У € условие V V

выполняется тогда и только тогда, когда а(11) ~2,2,1

В конце первой главы теоремы 1 и 2 обобщаются на полугруппы В{к, 2,2 + т) с произвольными т ^ 1 и к ^ 2.

Центральное место в диссертации отводится главе 2, в которой исследуется проблема равенства слов для полугруппы В{2,2,3). Один из возможных путей решения проблемы равенства слов в полугруппе В(2,2,3)

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

12122121 ~ 121212 212121 ~ 121212 21212 212121 ~ 1212212122121 .

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

Таким образом, круг «кандидатов» в канонические представители необходимо сузить. Разумно в качестве канонического представителя в каждом классе эквивалентности выбрать минимальное по длине слово, однако неясно, как находить такое слово в произвольном классе эквивалентности. К тому же до сих пор не известно, в каждом ли классе конгруэнции ~2,2,i слово минимальной длины единственно (см. [14]).

В связи с изложенным выше, интересным представляется вопрос, как по классам эквивалентности распределены сильно бескубные и почти сильно бескубные слова. Е. В. Сухановым была выдвинута гипотеза, что каждый класс эквивалентности содержит не более одного сильно бескубного слова. Косвенно эта гипотеза подтверждается результатами работ [2] и [22]: в [2] доказывается, что всякий класс эквивалентности содержит не более одного слова Туэ-Морса, а согласно [22], произвольное сильно бескубное слово в некотором смысле очень похоже на подходящее слово Туэ-Морса.

В диссертации доказывается несколько более сильное утверждение.

Теорема 3. Всякий класс конгруэнции ~2,2,ъ за исключением классов [11] и [22], содержит не более одного почти сильно бескубного слова. Каждый из классов [11], [22] содержит в точности два почти сильно бескубных слова.

Класс [11] (класс [22]) содержит два почти сильно бескубных слова 11 и 111 (соответственно, 22 и 222), из которых только одно слово является сильно бескубным. Таким образом, из теоремы 3 непосредственно вытекает справедливость сформулированной выше гипотезы Суханова.

Следствие. Всякий класс конгруэнции ~2,2,i содержит не более одного сильно бескубного слова.

Для решения проблемы равенства слов недостаточно выбрать в каждом классе эквивалентности элемент, служащий его каноническим представителем. Необходимо уметь находить такой элемент в классе [С/] для произвольного слова II. Эту задачу решает построенный в диссертации алгоритм Е^АОР, который за линейное от |[/| время по данному слову и находит почти сильно бескубное слово V, эквивалентное С/, или сообщает, что таких слов нет. Таким образом, алгоритм ЕяАОР позволяет получить частичное решение проблемы равенства слов для полугруппы 5(2,2,3).

Теорема 4. В полугруппе В(2,2,3) проблема равенства слов разрешима за время 0(тах{|£/|, |У|}) для всех пар (II, V), в которых по крайней мере одно из слов эквивалентно почти сильно бескубному слову.

Построение и доказательство корректности алгоритма EqAOF является наиболее технически сложной частью диссертации. Сам алгоритм состоит из двух больших шагов: на первом шаге входное слово и сжимается до константной длины с сохранением логарифмического объема информации о ходе сжатия; если такое сжатие невозможно, слово С/ не эквивалентно никакому почти сильно бескубному сЛову. На втором шаге результаты первого шага используются для построения «канонического» слова, эквивалентного II. Если это слово оказывается почти сильно бескубным, то оно является искомым; в противном случае слово и не эквивалентно никакому почти сильно бескубному слову. При построении первого шага использованы, в частности, некоторые идеи из [2,22].

К сожалению, существуют классы, не содержащие почти сильно бес-кубных слов, например, класс [121211]. Поэтому полученное нами решение проблемы равенства слов для полугруппы В(2,2,3) является частичным.

Наконец, третья глава посвящена применению алгоритма EqAOF для исследования полугруппы 5(2, 2,3). Важнейшим результатом глаг вы 3 является подтверждение гипотезы Бжозовского для полугруппы В(2,2,3) в частном случае, когда класс конгруэнции ~2,2д содержит почти сильно бескубное слово.

Теорема 5. Для любого почти сильно бескубного слова V класс [V]2,2,1 является рациональным языком.

При помощи алгоритма ЕчАОР устанавливается также следующее важное свойство классов экивалентности, содержащих почти сильно бес-кубные слова.

Теорема 6. Если слово V почти сильно бескубно и V {111,222}, то V — единственное слово минимальной длины в классе [¥¡2,2,1 ■

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

Теорема 7. Пусть V — почти сильно бескубное слово и |У| > 50. Тогда 8г([У]2.2д) > <р, где <р = (1 + \/5)/2 _ золотое сечение.

Через [7]<3 обозначим язык всех бескубных слов из класса [V] 2,2,1, где V € произвольное слово. Напомним, что сильно бескубными являются, в частности, слова Туэ-Морса <;„ = б"(1), где п > 0, а в — эндоморфизм свободного моноида Е^, задаваемый равенствами 9(1) = 12 и 6(2) = 21.

Теорема 8. 6гС^„]<3) > ¡р1'74 для любого п > 11.

Из теоремы 8 следует, что в классе конгруэнции ~г,2,1 может быть бесконечно много 3-свободных слов. С другой стороны, теорема 3 говорит, что в каждом классе не может быть больше одного 2+-свободного слова и, исключая классы [11] и [22], больше одного почти 2+-свободного слова. В связи с этим, интересным представляется вопрос, как распределяются по классам эквивалентности (почти) /?-(или /3+)-свободпые слова при изменении /? в промежутке [2,3]. В частности, интересно найти «границу единственности» — число

вир{Р [ класс [ 1^)2,2,1 содержит не более одного

/З-свободного слова для любого V € Е*} .

В диссертации путем обобщения теорем 3 и 4 показывается, что эта граница по крайней мере не меньше 7/3.

Теорема 9. Всякий -класс конгруэнции ~2,2,ъ за исключением классов [11] и [22], содержит не более одного почти 7/Ъ-свободного слова. Каждый из классов [11], [22] содержит в точности два почти 7/3-свободных слова.

Теорема 10. В полугруппе В(2,2,3) проблема равенства слов для разрешима за время 0(тах{|£/|, |У|}) для всех пар (и, V), в которых по крайней мере одно из слов эквивалентно почти 7/"¿-свободному слову.

Основные результаты диссертации

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

- Теорема 1 об эквивалентности разрешимости проблемы равенства слов в полугруппе В(к, 2,3) произвольного ранга к > 2 и разрешимости этой же проблемы для полугруппы В(2,2,3), и аналогичная ей по формулировке теорема 2 о справедливости гипотезы Бжозов-ского.

- Теорема 3 о единственности почти сильно бескубного слова в классах конгруэнции ~2,2,1-

- Линейный по времени работы алгоритм ЕчАОР, который находит почти сильно бескубное слово, ~2,2,¡-эквивалентное заданному слову, или сообщает, что таких почти сильно бескубных слов нет, и вытекающая из этого алгоритма теорема 4 о разрешимости в полугруппе В(2,2,3) проблемы равенства для любой пары слов, в которой хотя бы одно из слов эквивалентно почти сильно бескубному слову.

- Теорема 5, подтверждающая гипотезу Бжозовского для полугруппы В(2,2,3) в частном случае, а именно, доказывающая рациональность всех классов конгруэнции ~2,2д, содержащих почти сильно бескубное слово.

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

- Теорема об эквивалентности разрешимости проблемы равенства слов в полугруппе В (к, 2,2 + т) произвольного ранга к > 2 при фиксированном значении разрешимости этой же проблемы для полугруппы В(2,2,2 4- т), и аналогичная ей по формулировке теорема о справедливости гипотезы Бжозовского. Эти теоремы, являющиеся аналогами теорем 1 и 2, могут служить отправной точкой для применения разработанной в диссертации техники к произвольным полугруппам В(к, 2,2 + т).

- Теорема 6 гласит, что почти сильно бескубное слово является единственным словом минимальной длины в своем классе и тем самым обнаруживает в полугруппе В(2,2,3) свойство, характерное для бернсайдовых полугрупп сп^З.

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

- Теоремы 9 и 10 являются аналогами теорем 3 и 4, с заменой почти сильно бескубных слов на почти 7/3-свободные, и демонстрируют границы применимости разработанной в диссертации комбинаторной техники.

Список литературы

[1] С. И. Адян. Проблема Бернсайда и тождества в группах. М.: Наука, 1975. 335с.

[2| М. Ф. Бакиров, Е. В. Суханов. Слова Туэ-Морса и V-строение свободной бернсайдовой полугруппы // Изв. Уральского государственного университета. Серия «Математика и механика». 2000. Т. 18 (выпуск 3). С. 5-19.

[3] Ж. Лаллеман. Полугруппы и комбинаторные приложения. М.: «Мир», 1985. 440с.

[4] И. Г. Лысенок. Бесконечность бернсайдовых групп периода 2к при к ^ 13 // Успехи мат. наук. 1992. Т. 47: 2(284). С. 201-202.

[5] П. С. Новиков, С. И. Адян. Бесконечные периодические группы. I// Изв. АН СССР. Сер. «Математика». 1968. Т. 32. С. 212-244.

[6] П. С. Новиков, С. И. Адян. Бесконечные периодические группы. IIЦ Изв. АН СССР. Сер. «Математика». 1968. Т. 32. С. 251-524.

[7] J. Brzozowski. Open problems about regular languages // Formal language theory: perspectives and open problems. R. Book. Ed. Academic Press, New York, 1980. P. 23-47.

[8] W. Burnside. On an unsettled question in the theory of discontinuous groups // Quart. J. Pure Appl. Math. 1902. Vol. 33. P. 230-238.

[9] A. de Luca, S. Varricchio. On non-counting regular classes // Proc. ICALP'90. Berlin: Springer, 1990. P. 74-87. (LNCS Vol. 443).

10] A. de Luca, S. Varricchio. On non-counting regular classes // Theoret. Comput. Sci. 1992. Vol. 100(1). P. 67-104.

11] A. de Luca, S. Varricchio. Finiteness and regularity in semigroups and formal languages. Berlin: Springer, 1999. 240p.

12] A. P. do Lago. On the Burnside semigroups xn = xn+m // Proc. LATIN'92. Berlin: Springer, 1992. P. 329-343. (LNCS Vol. 583).

13] A. P. do Lago. On the Burnside semigroups xn = xn+m // Internat. J. Algebra Comput. 1996. Vol. 6(2). P. 179-227.

14] A. P. do Lago. Maximal groups in free Burnside semigroups // Proc. LATIN'98. Heidelberg: Springer, 1998. P. 65-75. (LNCS Vol. 1380).

15] A. P. do Lago, I. Simon. Free Burnside Semigroups // Theoret. Inform. Appl. 2001. Vol. 35(6). P. 579-595.

16] J. A. Green, D. Rees. On semigroups in which xr = x // Proc. Cambridge Philos. Soc. 1952. Vol. 48. P. 35-40.

17] V.S. Guba. The word problem for the relatively free semigroups satisfying tm - tm+n with m ^ 4 or m > 3, n = 1 I I Internat. J. Algebra Comput. 1993. Vol. 3(2). P. 125-140.

18] V.S. Guba. The word problem for the relatively free semigroups satisfying tm = tm+n with m Js 3 // Internat. J. Algebra Comput. 1993. Vol. 3(3). P. 335-348.

19] L. Kaclourek, J. Polak. On free semigroups satisfying Simon Stevin. 1990. Vol. 64(1). P. 3-19.

20] M. Lothaire. Combinatorics on words. Reading, MA: Addison-Wesley, 1983. 262p.

21] J. McCammond. The solution to the word problem for the relatively free semigroups satisfying i° = ta+b with a Js 6 // Internat. J. Algebra Comput. 1991. Vol. 1. P. 1-32.

22] A.M. Shur. Overlap-free words and Thue-Morse sequences // Internat. J. Algebra Comput. 1996. Vol. 6(3). P. 353-367.

Работы автора по теме диссертации

[23] А. Н. Плющенко. Сильно бескубные слова и свободная бернсайдова полугруппа с тождеством х2 = х3 // Материалы XIV международной научной конференции «Ломоносов-2007». Москва: Мысль, 2007. С. 92.

[24] А. Н. Плющенко. Сильно бескубные слова и свободная бернсайдова полугруппа с тождеством х2 = х3 и двумя образующими // Сибирские Эл. Мат. Изв. 2009. Т. 6. С. 166-181.

[25] А. Н. Плющенко. О проблеме равенства слов для свободных бернсайдовых полугрупп с тождестволь х2 = хг // Тезисы докладов международной конференции «Мальцевские чтения 2011». Новосибирск, 2011. С. 51. Электронный ресурс: http://www.math.nsc.ru/conference/nialmeet/ll/malmeet2011.pdf

[26] А. Н. Плющенко. О проблеме равенства слов для свободных бернсайдовых полугрупп с тождеством х2 = х3 // Известия вузов. Математика. 2011. №11. С. 89-93.

[27] А.N. Plyushchenko, A.M. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x2 ~ x3 // Proc.WORDS 2007. Marseille, France, 2007. P. 245-253.

[28] A.N. Plyushchenko, A.M. Shur. On Brzozowski's conjecture for the free Burnside semigroup satisfying x2 = x3 // Proc. DLT 2011. Berlin: Springer, 2011. P. 362-373. (LNCS Vol. 6795).

[29] A. N. Plyushchenko, A. M. Shur. Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x2 = x3 // Internat. J. Algebra Comput. 2011. Vol. 21. P. 973-1006.

Подписано в печать 19.11.2011. Формат 60x84 1/16 Бумага офсетная. Усл. печ. л. 1,0 Тираж 100 экз. Заказ №

Отпечатано в типографии ИПЦ УрФУ 620000, Екатеринбург, ул. Тургенева, 4

61 12-1/393

ФГАОУ ВПО Уральский федеральный университет имени первого Президента России Б. Н. Ельцина

На правах рукописи

ПЛЮЩЕНКО Андрей Николаевич

УДК 512.531

О КОМБИНАТОРНЫХ СВОЙСТВАХ БЕРНСАЙДОВЫХ ПОЛУГРУПП

01.01.06 — Математическая логика, алгебра и теория чисел

Диссертация на соискание ученой степени кандидата физика-математических наук

Научный руководитель: доктор физико-математических наук Шур Арсений Михайлович

Екатеринбург 2011 г.

Оглавление

Введение 4

1° Предварительные сведения........................................................5

1°.1 Слова..........................................................................5

1°.2 Языки и автоматы............................................................7

1°.3 Свободные бернсайдовы полугруппы, моноиды, группы................8

2° Обзор исследований в предметной области......................................9

2°.1 Общие методы и результаты................................................10

2°.2 Случай п = 1..................................................................11

2°.3 Случай та ^ 3..................................................................13

2°.4 Случай та = 2..................................................................14

3° Обзор диссертации..................................................................15

3°.1 Цели диссертации. Основные проблемы ..................................15

3°.2 Основные результаты........................................................16

3°.3 Основные методы............................................................17

3°.4 Структура диссертации и организация текста............................17

3°.5 Апробация и публикации....................................................18

Глава 1. Полугруппы В(к, 2,3) 19

§ 1.1 Введение и формулировка результатов ..........................................19

§1.2 Основная техника, используемая в диссертации................................20

§ 1.3 Построение отображения а........................................................25

§ 1.4 Доказательство основных результатов............................................32

§ 1.5 Обобщение результатов на полугруппы В(к, 2,2 + га)..........................35

Глава 2. Проблема равенства слов для полугруппы В(2,2,3) 39

§2.1 Введение и формулировка результатов ..........................................39

§ 2.2 Свойства г-редукции................................................................40

2.2.1 Нередуцируемые хвосты. Свойство г (II) ~ II ............................41

2.2.2 Регулярные соседние слова и квазисоседние слова ......................44

§ 2.3 Нерегулярные почти сильно бескубные слова. Хвосты первого рода..........47

2.3.1 Нерегулярные почти сильно бескубные слова............................47

2.3.2 Хвосты первого рода. Операция гт........................................50

2.3.3 Классы [112112211211]Г1 и [221221122122]Г1................................54

§ 2.4 Функции £ и г]........................................................................57

§2.5 Доказательство теоремы 2.1........................................................61

§ 2.6 Главные и нормальные ряды......................................................62

2.6.1 Процедура Ancestor. Главные ряды........................................62

2.6.2 Нормальные ряды............................................................65

2.6.3 Обработка плохих пар........................................................70

§ 2.7 Алгоритм EqAOF. Доказательство теоремы 2.2 ................................82

Глава 3. Приложения алгоритма EqAOF и обобщение результатов 86

§3.1 Гипотеза Бжозовского и другие приложения....................................86

3.1.1 Описание класса эквивалентности произвольного почти сильно бес-кубного слова ................................ 86

3.1.2 Гипотеза Бжозовского............................ 90

3.1.3 Слова минимальной длины..................................................94

§ 3.2 Индекс роста классов эквивалентности..........................................95

§3.3 Обобщение результатов на почти 7/3-свободные слова ............100

Список литературы

106

Введение

Теория бернсайдовых полугрупп, или полугрупп с тождеством хп = хп+т для некоторых п, m ^ 1 занимает важное место в теории периодических полугрупп. Бернсайдовы полугруппы возникают при рассмотрении полугрупп с ограниченным периодом. Проблематика бернсайдовых полугрупп естественным образом развивает аналогичную проблематику для бернсайдовых групп, т. е. групп с тождеством хт = 1. Изучение последних было начато в 1902 году Бернсайдом, интересовавшимся, всякая ли конечно порожденная группа с ограниченным периодом конечна (так называемая ограниченная проблема Бернсайда).

Важнейшими объектами для исследования, несомненно, являются свободные бернсайдовы полугруппы, то есть полугруппы, свободные в многообразии var{x™ = хп+т} (для фиксированных п,т ^ 1), поскольку всякая полугруппа из var{a;n = хп+т} есть гомоморфный образ подходящей свободной бернсайдовой полугруппы.

Свободным бернсайдовым полугруппам посвящено немало исследований, проясняющих многие особенности их внутренней структуры. Был разработан соответствующий инструментарий для изучения таких полугрупп, использующий как теоретико-групповые методы, так и методы теории формальных языков (в этом случае элементы свободной бернсайдовой полугруппы рассматриваются как классы эквивалентных слов над соответствующим алфавитом), методы общей комбинаторики и теории графов. Краткий обзор результатов приводится ниже в § 2°. Более подробно с теорией бернсайдовых полугрупп можно ознакомиться, например, по обзорной статье [20], немало интересных сведений можно почерпнуть из книг по теории полугрупп [3,15] и др.

Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы. Тесным образом решение проблемы равенства слов связано с гипотезой о том, что любой элемент свободной бернсайдовой полугруппы является рациональным языком. Эта гипотеза, сформулированная Бжозовским в 1969 году для полугрупп с тождеством хп = жта+1, была затем расширена Маккаммондом на случай произвольных пит. Заметим, что из справедливости (обобщенной) гипотезы Бжозовского вытекает разрешимость проблемы равенства слов в рассматриваемой полугруппе.

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

благодаря целому ряду работ, удалось подтвердить гипотезу Бжозовского и, как следствие, решить проблему равенства слов для случая п ^ 3. Значимые результаты получены и для полугрупп с п = 1 (см. § 2°). Наименее изученными остаются полугруппы с тождеством х2 = х2+т: проблема равенства слов в этом случае до сих пор не решена, а гипотеза Бжозовского при болыпйх значениях т оказывается неверной. В данной работе рассматриваются полугруппы с тождеством х2 = х3, для которых обе исследуемые проблемы остаются открытыми. Часть полученных в диссертации результатов обобщается на случай п = 2 и произвольного т.

1° Предварительные сведения

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

1°.1 Слова

1. Алфавит £ — это непустое множество, элементы которого называются буквами или символами. В данной работе рассматриваются только конечные алфавиты. В дальнейшем, Е^ = {1,..., к}, где к = 1,2,.... Для обозначения некоторой (неизвестной) буквы в слове используются строчные латинские буквы из начала алфавита.

Словом называется произвольная конечная последовательность букв: \¥ = а\а2 ... ап. Число п называется длиной слова Ж. Длина слова IV обозначается через а его

г-ая буква — через Ж [г]. Таким образом, Ш = И^[1]1У[2]... или просто Ш =

Ж[1... \ \¥\]. Символ А обозначает пустое слово, имеющее длину 0. Для обозначения слов используются заглавные латинские буквы из второй половины алфавита.

2. Обозначения Е*, £+, Е™ используются, соответственно, для множества всех слов, всех непустых слов, слов длины п над алфавитом Е. Множества Е+ и Е* образуют, соответственно, свободную полугруппу и свободный моноид относительно операции конкатенации (приписывания). Конкатенация слов V и V записывается как [/V. Положим

ип = и и... и.

1 ч/

п

для обозначения п-ой степени слова II; по определению, {7° = А.

Слово У называется подсловом слова (7 (обозначается У ^ [/), если существуют такие слова X, Ъ Е £*, что II — ХУЕ. Слово У называется собственным подсловом слова и (обозн. У < и), если У ^ 17 и У ф II. Наконец, слово У будем называть внутренним подсловом слова и (обозначается У -С и), если существуют такие слова X, Z € Е+, что и = ХУ2. Таким образом, внутреннее подслово У начинается не раньше второй

буквы в слове U и заканчивается не позже предпоследней буквы, то есть содержится целиком внутри U. Слово Y называется префиксом (суффиксом) слова U, если существует слово Z € Е* такое, что U = YZ (соответственно, U = ZY). Если при этом слово Z непустое, У называется собственным префиксом (соответственно, собственным суффиксом) слова U.

Подслово Y может входить в слово U несколькими способами; каждое такое вхождение Y в U однозначно определяется позицией первой буквы слова Y в U. Расстояние между вхождениями — это разность соответствующих позиций. В дальнейшем под термином «подслово» часто понимается конкретное вхождение какого-то подслова: из контекста будет понятно, идет ли речь о подслове или о его вхождении.

3. Периодом слова W называется число р со свойством: W[i] = W[i+p] для любого г = 1,..., \ W\-p. Экспонент,ой ехр(И/) слова W называется отношение длины слова W к его минимальному периоду, а локальной экспонентой lexp(PF) — максимум из экспонент всех подслов слова W. Наконец, введем понятие сильно локальной экспоненты 1ехр<(Ж) слова W как максимум из экспонент всех собственных подслов слова W.

Проиллюстрируем введенные в предыдущем абзаце определения примерами. W = 123123 имеет период 3; \W\ = 6, exp(W) = lexp(W) = 2, lexp<(W) = 5/3;

W = 1211121 имеет периоды 4 и 6; \W\ = 7, exp(W) = 7/4, 1ехр(Ж) = 3, \exP<(W) = 3; W = 111 имеет периоды 1 и 2; \W\ = 3, exp(W) = 3, lexp(WK) = 3, 1ехР<(Ж) = 2.

Слово W называется (З-свободным, если lexp(Wr) < (3, и называется ¡3+ -свободным, если lexp(W) ^ (3. Аналогично, слово W мы назовем почти [З-свободным (почти (3+-свободным), если, соответственно, 1ехр<(1У) < ¡3 и 1ехр<(И/) ^ (3. [Почти] 2-свободные, (3-свободные, 2+-свободные) слова называют также [почти] бесквадратными (соответственно, бескубными, сильно бескубными) словами.

Пусть /3' < (3". Очевидно, что любое /?'- или /3'+-свободное слово является также и /?"-или, соответственно, /3"+-свободным. Аналогичное утверждение справедливо и для почти свободных слов. Однако слово W может быть почти (3'- или /?/+-свободным, но не являться /3"- или |5//+-свободным. Так, например, слово 111 почти сильно бескубно, но при этом оно является кубом.

4. Морфизмом называется гомоморфизм свободных моноидов. Единственный нетривиальный автоморфизм свободного моноида Eij называется операцией инвертирования и обозначается . Таким образом, операция инвертирования переобозначает буквы в слове: 1 = 2, 2 = 1.

Морфизм Туэ-Морса 0: £ij —> Ei; задается равенствами 0(1) = 12 и 0(2) = 21. Обозначим tn = 0П(1), тогда t„ = 0™(2). Слова tn и tn называются словами Туэ-Морса.

Очевидно, морфизм Туэ-Морса инъективен. Обратное отображение из 0(Е^) в свободный моноид EJ обозначается через в"1.

1°.2 Языки и автоматы

1. Языком над алфавитом £ называют произвольное подмножество свободного моноида Е*. Напомним определения основных операций над языками. Под объединением языков С и 1С (обозначается Си 1С или £ + 1С) понимают их теоретико-множественное объединение, произведением С и К называется язык

СК = {иу I и € £, V € /С},

левое 1С~гС и правое СК-1 частные языков С и 1С определяются как

1С'1 С = {и | ЗУ е К(уи е £)} и ОС'1 = {и | ЗУ е ЦИУ е £)}

соответственно. Положим £* = = и^х£г (операция * называется итерацией).

При записи одноэлементных языков вида {ТУ}, где ТУ 6 £*, фигурные скобки опускаются. Например, вместо /С{ТУ}-1 и {ТУ}* мы пишем просто /СТУ-1 и ТУ*.

Естественным образом на языки распространяются операции взятия образа и прообраза:

ВД = {к(и) | и € /С}, /Гх(£) = {{/ | ВД е £}

для произвольного отображения /г: Д* —> £* и языков £ С £*, /С С Д*.

Язык называется рациональным, или регулярным, если он может быть записан при помощи регулярного выражения — выражения, содержащего одноэлементные языки и операции объединения, произведения и итерации языков.

Класс рациональных языков замкнут относительно взятия частного и прообраза любого морфизма. Таким образом, для произвольных языков £, К С Е* и любого морфизма Л: Д* —> £*, если язык £ рациональный, то и языки СК,'1 и /г~1(£) оказываются рациональными.

В дальнейшем, при рассмотрении регулярных выражений мы будем часто употреблять фразу «слово имеет вид»: слово ТУ имеет вид (12)* 1, слово ТУ вида (12 + 21)* и т. п., подразумевая, что слово ТУ принадлежит языку, задаваемому соответствующим регулярным выражением.

2. Детерминированным конечным автоматом (ДКА) называется пятерка Е, 6, в, Т), состоящая из конечного множества состояний (вершин) <5, алфавита Е, функции перехода 5: х Е —(3, начального состояния в £ и множества конечных (терминальных) состояний Т С <5- Конечный автомат удобно отождествлять с орграфом с множеством вершин (5 (и метками, указывающими, является ли вершина начальной и/или конечной) и множеством дуг вида q А д', определяемых условиями а) = д'. Операция 6 естественным образом распространяется на слова:

6(д, ТУ) = *(... (<%, ТУ[1]), ТУ[2]) • • • , ТУ[|ТУ|]) .

Каждый маршрут в автомате помечен словом над алфавитом Е. ДКА распознает (принимает) слово ТУ, если существует хотя бы один маршрут из начальной вершины в

какую-либо из конечных, помеченный словом Щ. Язык всех распознаваемых ДКА А слов обозначается через С(Л). Говорят, что ДКА Л распознает язык С(Л).

Недетерминированный конечный автомат (НКА) получается из понятия ДКА путем двух обобщений: начальное состояние в заменяется множеством начальных состояний I, а функция перехода 5: СЦ х £ —» заменяется на тернарное отношение 6 С С} х £ х (¡). Представление орграфом, распознаваемый язык определяются так же, как и для ДКА. Согласно теоремам Рабина-Скотта и Клини, классы языков, распознаваемых ДКА и НКА, совпадают с классом рациональных языков (см., например, [3]).

3. Для любого языка £ С £* комбинаторная сложность есть функция рг(п): N0 —► М0, которая определяется как рс(п) = |£П£П|. В дальнейшем термин «сложность» применительно к языку означает комбинаторную сложность.

Основным инструментом для оценки степени роста комбинаторной сложности языка служит индекс роста gr(L) = Ншп-^оо Р

1°.3 Свободные бернсайдовы полугруппы, моноиды, группы

1. Свободный бернсайдов моноид ранга к и тождеством хп = хп+т для некоторых фиксированных чисел п ^ 0,т ^ 1 с точностью до изоморфизма определяется как фактор-моноид

В (к, п,п + т) = ££/ ~к,п,т

свободного моноида ££ по конгруэнции ~к,п,т> порожденной всеми парами вида (У™, уп+т), где У 6 А^оноиды В(к,0,т) являются группами, которые называются свободными бернсайдовыми группами и обозначаются В(к,т). Свободная бернсайдова полугруппа В(к,п,п + т), где п,т ^ 1, получается из моноида В(к,п,п + т) удалением единицы (нейтрального элемента) — класса эквивалентности, состоящего из пустого слова. Того же результата можно достичь, заменив ££ на £¡1" и слово «моноид» на слово «полугруппа» в определении свободного бернсайдова моноида В(к,п,п + т). Класс эквивалентности содержащий слово 1¥, обозначается через \У/\к,п,т-Все результаты диссертации формулируются для свободных бернсайдовых полугрупп, однако те же результаты справедливы и для соответствующих этим полугруппам свободных бернсайдовых моноидов. Более того, в дальнейшем мы часто будем иметь дело именно с моноидами, рассматривая пустое слово Л и класс [А]^^ везде, где это необходимо.

2. Для работы с конгруэнцией ~к,п,т удобно ввести отношения соседства Пк,п,т:

Кк,п,т = {(у, у), (хупг,хуп+тг), (хуп+тг, хупг) \ х, г е Е*к, у е .

Слова 11 и V мы называем соседними, если (£/, V) € пк,щт (при фиксированных параметрах п, т и к). Легко проверить, что ,т~ тгкпт' то есть конгруэнция ~к,п,т является транзитивным замыканием отношения соседства тгк,п,т-

Ввиду вложенности множеств £1 С £2 С £3 С ..полугруппа В(к, п,п + т) является подполугруппой полугруппы В (к', п,п + т), а моноид В (к, п,п + т) — подмоноидом моноида В(к',п,п + т), если к < к'. Это позволяет нам опускать индекс к в обозначениях

Пк,п,т, ~к,п,т И \У/)к,п,т, ГДв \¥ £ £*.

2° Обзор исследований в предметной области

В данном параграфе приводится краткий обзор исследований и основных результатов других авторов в теории бернсайдовых полугрупп. Более подробно с проблематикой и историей развития данной предметной области можно ознакомиться, например, по обзорной статье [20]; немало интересной информации о бернсайдовых полугруппах можно почерпнуть из книг по общей теории полугрупп, таких как [3,15], и др.

Основные затрагиваемые здесь проблемы следующие:

Проблема конечности (ограниченная проблема Бернсайда): при каких п, т и к полугруппа В (к, п,п + т) бесконечна? Эта проблема была впервые сформулирована Бернсайдом в 1902 году для бернсайдовых групп. Позже она была распространена на случай произвольной бернсайдовой полугруппы.

(Обобщенная) гипотеза Бжозовского: всякий элемент свободной бернсайдовой полугруппы является рациональным языком над соответствующим алфавитом. Гипотеза была сформулирована Бжозовским в 1969 году для полугрупп В(к,п,п + 1), позже Маккаммонд распространил ее на случай произвольной свободной бернсайдовой полугруппы.

Проблема равенства слов: По произвольно заданным словам II иУ определит