Введение 1
1 Определения и обозначения 3
2 О морфизмах, порождающих слова Линдон 5
2.1 Известный результат для бинарного алфавита 5
2.2 Избыточность условий в оригинальной теореме 6
2.3 Гипотеза о критерии линдоновости неподвижной точки морфизма над произвольным алфавитом 8
2.4 Короткие морфизмы
3 Об абелевой периодичности морфических слов 10
3.1 Абелева периодичность неподвижных точек коротких морфизмов 10
3.1.1 Морфизм длины 3 12
3.1.2 Морфизмы длины 4 12
3.1.3 Морфизмы длины 5 13
3.1.4 Морфизмы длины 6 13
3.2 Необходимое условие абелевой периодичности и его недостаточность 16
3.3 Достаточное условие абелевой периодичности морфического слова и гипотеза о его необходимости 22
Заключение 23
Список литературы 23
Данная работа посвящена некоторым гипотезам из такого раздела математики как комбинатора слов. Основными объектами изучения будут слова (конечные или бесконечные) над конечным алфавитом, а также морфизмы, то есть гомоморфизмы моноида слов. Любой морфизм естественным образом продлевается до определённого на множестве бесконечных слов. В работе изучаются так называемые морфические слова, то есть бесконечные слова, полученные как предел последовательности конечных слов а, f (а), f2 (а), • • •, где a- буква рассматриваемого алфавита, а f - морфизм, такой, что f (а) = аи, где и - непустое слово. Тогда в последовательности a, f(а), f2(а),... каждое предыдущее слово является собственным префиксом следующего, и, таким образом, эта последовательность определяет некоторое бесконечное слово, которое притом будет являться неподвижной точкой морфизма f.
Построение бесконечных слов в виде неподвижных точек морфизмов является одним из основных способов в комбинаторике слов. Одним из его преимуществ является возможность порождать слова быстро. Несмотря на то, что не каждое бесконечное слово является морфическим, очень часто свойства бесконечных слов, например, свойства периодичности (обыкновенной [3], [4], абелевой, слабой абелевой [2]), свойства избегаемости (см., например, [15],[16]) изучаются именно на морфических словах.
Активно изучается вопрос комбинаторной сложности (или просто сложности) морфических слов. Сложность бесконечного слова и - это функция, сопоставляющая каждому натуральному числу n число различных подслов длины n в слове и. Абелева сложность - то же, но подсчёт ведется с точностью до абелевой эквивалентности подслов (два конечных слова называются абелево эквивалентными, если одно можно получить из другого перестановкой букв, иначе говоря, если для каждой буквы алфавита верно, что число её вхождений в одно и в другое слово совпадают). Оказывается, что задача об абелевой сложности морфических слов трудная, она активно изучалась и есть много частичных результатов (к примеру, [6]), однако об абелевой сложности морфических слов всё ещё известно мало. В настоящей работе, в разделе 3, мы будем говорить о таком связанном с абелевой сложностью свойстве морфических слов как абелева периодичность.
В настоящей работе изучаются два вопроса: когда морфическое слово является словом Линдона, и когда морфическое слово является абелево периодическим.
Ответ на первый вопрос в случае, когда алфавит состоит из двух букв, был дан в [1]. Однако характеризация, полученная там для бинарного алфавита, не может быть сразу обобщена для случая алфавитов больших размеров. В разделе 2 настоящей работы показано, что условия критерия линдоновости неподвижной точки бинарного морфизма, полученные в [1], образуют избыточную систему. При этом при избавлении от одного из избыточных условий получается сформулировать уже жизнеспособную гипотезу о критерии линдоновости неподвижной точки морфизма над алфавитами размера 3 и более. Слова Линдона, конечные и бесконечные, оказываются важными даже в на первый взгляд не связанных с ними задачах. Так, свойство линдоновости сыграло важную роль в доказательстве «runs conjecture» [11], которую до этого не удавалось доказать на протяжении 15 лет. В свою очередь свойство линдоновости для бесконечных слов связано с некоторыми другими изучаемыми свойствами бесконечных слов. Например, линдо- новость для бесконечного слова является достаточным условием отсутствия самошаффлуемости [12].
В разделе 3 настоящей работы мы говорим об абелевой периодичности морфических слов. Об этом свойстве известно мало, в то время как известна разрешимость, в случае бинарного алфавита, задачи о более слабом свойстве морфических слов, а именно: о слабой абелевой периодичности [2]...
В настоящей работе были рассмотрены две задачи о морфических словах: об их линдоновости и абелевой периодичности. Доказано, что в результате Ришомма и Зеболда [1] система условий, составляющих критерий линдоно- вости морфического слова над бинарным алфавитом, является избыточной. Это дало новую формулировку критерия для бинарных слов, на основе которого сформирована гипотеза о критерии линдоновости морфических слов над алфавитами размера 3 и более. Отметим, что исходная формулировка Ришомма и Зееболда не допускала естественного обобщения на алфавиты больших размерностей, что авторы отмечают в заключении статьи [1]. Кроме того, была предоставлена классификация коротких морфизмов по свойству абелевой периодичности их неподвижной точки. Приведены некоторые необходимые и некоторые достаточные условия абелевой периодичности в общем случае, а также сформулирована гипотеза о необходимом и достаточном условии абелевой периодичности морфических слов. Обе гипотезы были проверены на коротких морфизмах.
