Введение 1
1 Определения и обозначения 3
2 Вспомогательные результаты 4
2.1 О словах Линдона 4
2.2 О словах Штурма 5
2.3 Об абелевых бордюрах 6
2.4 О рекурсивном задании слов 7
3 Морфизмы длины 3 8
4 Морфизмы длины 4 8
4.1 Морфизмы длины 4, неподвижные точки которых не являются самошаффлящимися 9
4.2 Морфизмы длины 4, неподвижные точки которых являются самошаффлящимися 9
5 Морфизмы длины 5 10
5.1 Морфизмы длины 5, неподвижные точки которых не являются самошаффлящимися 11
5.2 Морфизмы длины 5, неподвижная точка которых является самошаффлящейся 13
5.3 О четырёх оставшихся морфизмах 18
Заключение 21
Список литературы 22
Данная работа относится к такому разделу математики как комбинаторика
слов. Основными объектами работы будут слова (конечные и бесконечные)
над конечным (в основном – бинарным) алфавитом, и морфизмы (отоб-
ражения, сохраняющие операцию конкатенации) на множествах этих слов.
Некоторые морфизмы естественным образом порождают свою неподвиж-
ную точку (то есть слово, которое данный морфизм переводит в себя), а
именно, как предел итераций f n(0), где f – наш морфизм (от него требу-
ется выполнение некторого условия), а 0 – подходящая буква. Именно о
полученных таким образом словах – их мы будем назвать морфичными –
мы будем говорить. Свойство таких слов, которое мы будем изучать, на-
зыватеся самошаффлуемость (от английского self-shuffling). Бесконечное
слово v называется самошаффлящимся, если выполнено:
v = ∞∏ i=1 UiVi = ∞∏ i=1 Ui = ∞∏ i=1 Vi;
где для всех i слова Ui, Vi – конечные и непустые. То есть, неформально
говоря, v можно получить, смешав две копии v с сохранением порядка букв.
Некоторые известные бесконечные слова являются самошаффлящими-
ся, к примеру, в [1] представленно конструктивное доказательство того,
что слово Туэ-Морса, задающееся, например, как неподвижная точка s =
lim n→∞ f n(0) морфизма
{
0 −→ 01
1 −→ 10
– самошаффлящееся; и в [3] показано, что представленный шаффл является
в нектором смысле оптимальным. Доказать, что слово Туэ-Морса являет-
ся самошаффлящимся оказалось более сложной задачей, чем можно было
ожидать, что говорит о том, что для некоторых морфичных слов проверить,
являются ли они самошаффлящимися – потенциально непростая задача.
Свойство самошаффлуемости изучалось для многих важных классов
бесконечных слов. Так, в [1] доказывается, что никакое бесконечное слово
Линдона (слово, лексикографически меньшее любого своего собственного
суффикса относительно некоторого порядка на его алфавите) не является
самошаффлящимся. Там же дана характеризация самошаффлящихся слов Штурма.
О шаффлах бесконечных слов ставились самые разные задачи. В [4] най-
дено бесквадратное бесконечное слово над алфавитом размера 3, шаффля
которое с самим собой, можно получить также бесквадратное (но другое)
слово. Уже позже в [6] получены примеры бесквадратных самошаффля-
щихся слов над алфавитами размера 3 и 4. В той же работе представлено
такое бесконечное слово, что ни одно слово из замыкания его орбиты не
является самошаффлящимся.
Свойство самошаффлуемости позволяет доказывать некоторые на пер-
вый взгляд напрямую не связанные с ним вещи. Например, с помощью
этого понятия было найдено короткое доказательство теоремы Ясутоми, а
именно, охарактеризованы морфичные слова в орбите характеристического
слова Штурма [1].
Данная дипломная работа посвящена изучению самошаффлуемости мор-
фичных слов. Мы будем работать с бинарным алфавитом и морфизмами вида
f = {
0 −→ 0u
1 −→ v
где u, v – некоторые непустые слова из {0, 1}∗. В этом случае в пределе
s = lim
n→∞ f n(0) получается бесконечное слово, являющееся неподвижной
точкой морфизма f . Именно такие неподвижные точки мы и будем пы-
таться шаффлить.
В параграфе 2 данной работы (раздел 2.4) представлен новый метод до-
казательства самошаффлуемости для морфических слов и некоторых сход-
ных с ними классов слов. Многие морфические слова можно представить
рекурсивным образом, а для ряда рекурсий удается доказать, что любое
слово, задающееся такими рекурсиями, является самошаффлящимся, неза-
висимо от начальных данных. Для удобства такие рекурсии тоже будем
называть самошаффлящимися; и они, очевидно, порождают бесконечное
число самошаффлящихся слов.
В последующих параграфах представлена характеризация (при помощи
старых и новых методов) по свойству самошаффлуемости неподвижных
точек морфизмов длины не превосходящей 5 (длиной морфизма f мы на-
зываем сумму длин образов под действием f всех букв рассматриваемого алфавита).
Так, в параграфе 3 разобраны морфизмы длины 3, в параграфе 4 –
морфизмы длины 4, в параграфе 5 – длины 5.
Многие результаты дипломной работы, касающиеся достаточных или
необходимых условий самошафлуемости неподвижных точек морфизмов,
носят довольно общий характер, и их применимость не ограничевается мор-
физмами с маленькими длиными. В частности, это относится к результатам
о самошафлумости, полученным с помощью рекурсий: зачастую они позво-
ляют установить самошаффлуемость и для ряда морфизмов больших длин.
Общая задача, которая скорее всего сложная, - это дать характеризацию морфизмов, неподвижные точки которых являются самошаффлящимися словами. В данной работе разобраны короткие морфизмы и представлены удобные методы доказательства самошаффлуемости и несамошаффлуемости для некоторых классов морфичных (и не только) слов.
