Комбинаторика на бесконечных перестановках

Одним из разделов дискретной математики является комбинаторика на словах. Возникновение этого раздела восходит к работам Акселя Туэ в начале XX века [1], [2], [3]. Исторический очерк может быть найден, например, в статье [4]. Одними из основополагающих книг являются [5], [6].

Объектом исследования в комбинаторике на словах являются символьные последовательности над конечным алфавитом (или слова). Естественным образом определяется конкатенация конечных слов и операция взятия под-слов. Язык всех конечных подслов заданного бесконечного слова является факторным, то есть вместе с любым словом он содержит все его подслова. Среди исследуемых комбинаторных свойств бесконечных слов особенный интерес представляет функция комбинаторной сложности /ш (п), ставящая в соответствие каждому натуральному п количество различных подслов длины п бесконечного слова т. Обзор результатов по комбинаторной сложности слов дан в статье [7]. Классический результат Морса и Хедлунда [8] гласит, что для всякого бесконечного слова и>, являющегося существенно непериодическим (то есть никакой суффикс которого не является периодическим), выполнено /го (п) ^ П + 1.

Помимо исследования общих свойств бесконечных слов, выделяются конкретные классы бесконечных слов или даже отдельные бесконечные слова, которые изучаются более подробно. Таковыми являются слово Туэ-Морса [9], слово удвоения периода [10], слова Штурма [11], слово Фибоначчи [12], слова Роте [13], слово Серпинского, и другие. Приведём несколько определений.

Слово Туэ-Морса т = 110 100 110 010 110. может быть задано рекуррентно условиями ги (0) = 0, и>(2п) = и){п), и>(2п + 1) = 1 — и)(п) при всех п ^ 0. Также слово Туэ-Морса можно определить как неподвижную точку морфизма. А именно, рассмотрим отображение (р: {0,1} —>¦ {0,1}2, заданное равенствами (0) = 01 и (1) = 10. Для произвольного слова я = ?(1). з (п) 6 {0,1}п положим ^(й) = </?(з (1)). ^(¿-(п)). I.

Рассмотрим последовательностьшд = 0, уох = 01, и>2 = 0110, = 1 101 001, ., где и]п+1 = (р{и)п). Нетрудно доказать, что для любого п слово тп является префиксом слова иип+Следовательно, существует бесконечное слово т = 'ш (0)ъи (1)'ш{2). = 110 100 110 010 110., что иоп = -ш (0). т (2п — 1) для каждого п. Это слово и называется словом Туэ-Морса. Слово удвоения периода ы = 10 001 010 100. может быть задано рекуррентно условиями ио (2п— 1) = 0 и ги (2п) = 1 — т (п) для всех п ^ 1. Также оно является неподвижной точкой морфизма с^: 0 >— 0100,1^0101.

Есть несколько эквивалентных определений слов Штурма. Одно из них следующее. Зафиксируем иррациональное число, а Е (0,1) и действительное число ?3 Е К. Положим ио (п) = [а (п + 1) + /3} - [ап + ?3}.

Будем говорить, что и] = т (1)ъи (2). — слово Штурма с параметрами, а и /3, причём, а называется наклоном слова Штурма.

Примером слов Штурма является слово Фибоначчи. Определим последовательность конечных слов рекуррентно: до = 0, = 01, д&trade- — дп1дп-2. Поскольку каждый член последовательности является префиксом следующего члена, то существует такое бесконечное слово q = 10 010 100 100 101 001 216 что все члены последовательности являются его префиксами. Это слово д и называется словом Фибоначчи. Также его можно определить как неподвижную точку морфизма (р: 0 I—У 01, 1 ь->• 0. Известно, что слово Фибоначчи является словом Штурма с наклоном а. = (3 — л/5)/2.

Актуальным направлением является исследование возможных обобщений результатов комбинаторики на словах, получение аналогов этих результатов для других, схожих с бесконечными словами, объектов. Один из путей попытка исследовать комбинаторные свойства двумерных слов. В этом направлении одной из самых известных проблем является гипотеза Нива [14], утверждающая, что если существует пара чисел (то, щ), что для комбинаторной сложности двумерного слова ии выполнено неравенство ^(то^щ) ^ ШоПо, то слово и> имеет вектор периодичности.

Возможны и другие обобщения. Пусть задано некоторое множество Ы, его элементы будем называть обобщёнными словами, каждому элементу и Е Ы сопоставлено натуральное число £(и), которое мы будем называть длиной и. Пусть задана операция взятия подслова. А именно, пусть для каждого и ЕЫ и для каждых т, тч ^ Ни) определено обобщённое слово Е Ы.

Постулируем свойства:

• и[1,?(и)] = щ.

• ?(и[т, 1, т2}) =7712—7711 + 1;

• К¡-777,1, ^2] ?7¹⁵ т^] — и[т'1 + 777,1 — 1, 777,2 + — 1].

Если выполнено всё вышеизложенное, то структуру (Ы-[7771,7772]) будем называть обобщённым факторным языком. Через Ы{п) будем обозначать множество обобщённых слов длины п. Количество всех обобщённых слов фиксированной длины п обозначим через /(77) = Ы{п). Последовательность {Лп)}^=1 назовём комбинаторной сложностью языка Ы.

Под такое общее определение подпадают как обычные слова, так и ряд других объектов, в том числе бесконечные перестановки, которым и посвящена настоящая диссертация.

Бесконечные перестановки (в нашем смысле) были введены в 2005 году в [15], [16]. Однако некоторые проблемы, связанные с ними, исследовались ранее. Например, в статье [17] 1977 года рассматриваются перестановки, избегающие длинных монотонных арифметических паттернов. Краткий обзор результатов и направлений исследования по бесконечным перестановкам дан в статье [18].

Под перестановкой мы понимаем линейный порядок -<ж на некотором множестве X (обычно на конечном множестве {1,., п}, на множестве натуральных чисел N = {1,2,3,4,.} или на множестве целых неотрицательных чисел Ми {0}) по отношению к «обычному» линейному порядку ^ на X. Более точно, каждая перестановка — это упорядоченная тройка 7 Г = (X, ^т,.), где ^ и^тг — линейные порядки на X. Вместо записи х у для х, у 6 X мы используем более удобную запись к{х) ^ 7 Г (у). Множество X мы будем называть носителем перестановки, а его элементы по отношению к перестановке 7 Г мы будем называть вершинами перестановки, через 7 г (ж) будем обозначать вершину перестановки 7 Г, соответствующую элементу X € X.

Нетрудно понять, что любую биекцию р: {1,., п} —> {1,., п} можно мыслить как линейный порядок^р на {1,., п}. В самом деле, положим, что х у тогда и только тогда, когда р (х) ^ р (у) — Легко проверяется, что это действительно линейный порядок. Обратно, имея некоторый линейный порядок ^ на множестве {1,., п}, можем построить по нему биекцию р: {1,., п} —>• {1,., п} следующим образом: р (1) положим равным минимальному элементу из множества {1,., п} по линейному порядку далее р (2) положим равным второму по величине элементу, и так далее, р (п) положим равным максимальному элементу по линейному порядку Очевидно, что р — действительно биекция.

Тем самым, классическое определение конечных перестановок как би-екций эквивалентно нашему определению через линейные порядки. Этим, в частности, оправдывается такое название. Конечная перестановка 7 Г, соотвест-вующая биекции р: {1,., п} —> {1,., п}, в алгебре часто записывается в виде / 1 2. п * р (2). р (п))> мы же будем записывать лишь нижнюю строку: тг =р (1)р (2). .р (та).

При этом число п мы будем называть длиной перестановки 7 Г. Множество всех конечных перестановок длины п обозначаем через <5П.

Отметим, что в отличие от конечного случая, для бесконечного множества X наше определение бесконечной перестановки через пару линейных порядков на X вовсе не эквивалентно существованию соответствующей биекции X на себя. В самом деле, приведём пример бесконечной перестановки на N, которой не соответствует никакая биекция N на себя. Положим 7 г (гс) > 7 г (у) при любом чётном х и нечётном у, а также положим 7 г (1) < 7 г (3) < 7 г (5) <. и 7 г (2) > 7 г (4) > 7 г (6) >Если допустить, что найдётся биекция р: N N такая, что р (х) ^ р (у) тогда и только тогда, когда тт (х) ^ к (у), то тогда мы бы имели строго возрастающую бесконечную последовательность натуральных чисел р (1) < р (3) < р (5) < ., ограниченную сверху (например числом р (2)), что невозможно.

Вместо биекций X на себя бесконечным перестановкам соответствуют классы эквивалентности отображений из X в У, где У ЭХ. Эквивалентность определим следующим образом. Будем считать, что отображения /: X —> Y и д: X ^ Y эквивалентны, если для всех х, у € X выполнено f{x) ^ f (y) тогда и только тогда, когда д{х) ^ д (у) — Легко проверить, что таким образом определённая эквивалентность отображений рефлексивна, симметрична и транзитивна, то есть в самом деле является отношением эквивалентности. Каждый класс эквивалентности задаёт перестановку 7 Г на X такую, что 7 г (ж) ^ 7Г{у) тогда и только тогда, когда f (x) ^ /(у), где отображение / — представитель нашего класса эквивалентности. Обратно, всегда ли перестановке будет соответствовать какой-то класс эквивалентности отображений — зависит от выбора Y.

Нетрудно понять, что для X = N всегда можно взять Y = К, то есть любой перестановке на N соответствует класс эквивалентности последовательностей действительных чисел. При этом, как мы видели выше, Y = N можно взять не всегда, то есть далеко не всякая перестановка может быть реализована как биекция N на себя. Соответственно, возникает интересная задача: для заданной перестановки (или класса перестановок) определить, какие множества Y для неё годятся. В частности, интересно исследовать случаи Y = N и Y = Z.

В статье [17] рассматривается как раз задача такого типа. Там исследуются перестановки, избегающие монотонных подпоследовательностей вершин с номерами, образующими арифметическую прогрессию. Более точно, для заданного к ^ 3 рассматриваются перестановки 7 г для которых не существует такой арифметической прогрессии т^ ., т^, что 1 г (т) <. < 7 г (т^) или 7 г (т1) >. > 7 г (т^). В статье [17] показано, что такие перестановки существуют для к ^ 3, а также что при к = 5 существует такая перестановка, реализующаяся последовательностью натуральных чисел (то есть что для неё годится У = М), а при к = 4 существует такая перестановка, которая реализуется последовательностью целых чисел (то есть годится У = Z). До сих пор нерешённым остаётся вопрос, существует ли при к = 4 такая перестановка, реализующаяся последовательностью натуральных чисел. В недавней статье [19] сделано частичное продвижение: там построен пример такой перестановки для к = 4, реализующейся последовательностью натуральных чисел, но где требование избегаемости монотонных подпоследовательностей вершин с номерами, образующими арифметическую прогрессию, ослаблено до требования избегаемости монотонных подпоследовательностей вершин с номерами, образующими арифметическую прогрессию с нечётной разностью.

Ещё одно обобщение результатов статьи [17] рассмотрено в другой недавней статье [20]. Там исследуются линейные порядки на множестве рациональных чисел и на множестве действительных чисел, избегающие монотонных арифметических прогрессиий.

Для каждой перестановки 7 г (конечной или бесконечной) и х, у? X, X у, определим СИМВОЛ 7ж (х, у)? {0,1} (или просто 7(х, у), если ясно, о какой перестановке идёт речь) следующим образом:

Ясно, что перестановка 7 г полностью определяется символами^уп (х, у). В частности, если щ и 7Г2 — перестановки на одном и том же носителе X, то 7Г1 = 7Г2 тогда и только тогда, когда 77Т1(х^у) = «уП2(х, у) при всех х, у 6 X, х^у.

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

0, если 7 г (х) < 7 г (г/),.

1, если 7 г (х) > 7 т (у). линейному порядку Имеется в виду, что если, например, X < у и 1 г (х) > 7 г (у), то точка, соответствующая вершине 7 г (х), на диаграмме должна находится левее и одновременно выше, чем точка, соответствующая вершине 7 т (у). Соседние по горизонтали точки соединяются отрезками (для красоты).

Пример 1. Конечная перестановка 7 Г = 2431 длины 4 изображена на рисунке 1. Имеем 7.(1,2) = 0, 7.(2,3) = 1, 7.(3,4) = 1, 7.(1,3) = 0, 7.(2,4) = 1, 7.(1,4) = !.

Пример 2. На рисунке 2 изображён начальный кусок бесконечной перестановки 7 Г, заданной равенствами 7п (х, у) = 0 для всех нечётных х и чётных у, а также 7^(24, ?2) — 0 при всех нечётных Х2, Х < Х2, и 7^(2/1,2/2) = 1 при всех чётных 2/1, 2/2, У < У2• Выше мы использовали эту перестановку в качестве примера бесконечной перестановки, для которой не существует соответствующей биекции N на себя.

В статье [16] дано определение периодичности перестановок. Будем говорить, что бесконечная перестановка 7 г периодична с периодом если 7. (х, у) = 7.(х + + ?) для всех х. у. Будем говорить, что бесконечная перестановка 7 г существенно периодична с периодом t, если существует число N0, что 7.(а, 2/) = 7тг (ж + + ПРИ всех х ^ Мь У ^ ЛЬ, то есть, другими словами, если периодичен какой-то её суффикс. Заметим, что перестановка из примера 2 является периодической с периодом 2. В статье [16] доказано, что.

Рис. 1. тг = 2431.

Рис. 2 периодические перестановки не могут быть представлены последовательностями из натуральных чисел.

Линейные порядки на X индуцируют линейные порядки на подмножествах X, следовательно естественным образом можно определить понятие подперестановки. Дадим формальное определение. Для перестановки 7 Г = (ЛГ, ^тг) (конечной или бесконечной) и конечного набора у1,., уп Е X, где у <. < уп, обозначим через тг{у,., уп} перестановку на {1,., п}, определённую равенством Ъ{У1,., Уп}(ь з) = 1ж{уь Уз) при 1 ^ г ^ п, 1 ^ з ^ п, ъф 3- Особенно интересен случай, когда ., уп — последовательные целые числа (и соответственно когда X = N или X = {1,., А/" }). Итак, пусть заданы числа 777,1 И Ш2, причём 777,1 < 777,2- Тогда перестановку 7г{777,1, 7721 + 1, • • • ,™>2} будем обозначать через 7г[777,1,777,2]. Иными словами, 7г[777,1, ^2] ~ это такая перестановка длины 7772—777,1 + 1, ЧТО При 1 ^ % ^ 7772 — 777,1 + 1 И 1 ^ ] ^ 7772—7771 + 1 выполнено 77Г[тьТО2)(г, 3) = + г — 1, т1 + 3 — 1). Будем говорить, что конечная перестановка? € ¿->п является подперестановкой конечной или бесконечной перестановки 7 Г, если? = 7г[7771,7772] ДЛЯ некоторых 7771 И 7772- Для каждой бесконечной перестановки 7 г и конечной перестановки? € с>п определим множество = = 7г[т + 1, т + п]}.

Пример 3. Перестановка 321 является подперестановкой перестановки 7 г = 2431, так как 7г[2,4] = 321. А для бесконечной перестановки тг из примера 2 имеем тг[1, 8] = 18 273 645 и ?"(18 273 645) = {0, 2,4, 6,.}.

Аналогичное обозначение мы будем применять для слов над конечным алфавитом, то есть для слова и (конечного или бесконечного) запись и[т1,7772] будет означать его подслово и[гп). 7/(7772).

Через Л будем обозначать пустое слово.

Пусть у нас имеется бесконечная перестановка 7 Г. Множество всех её под-перестановок обозначим через Тж и будем называть языком всех подпереста-новок перестановки 7 г. Легко видеть, что этот язык является факторным, то есть вместе с любой перестановкой содержит все её подперестановки. Множество перестановок из Т^ длины п обозначим через ^(п) = П ¿->п, а его мощность обозначим через ^(п) = Другими словами, /&bdquo-(п) — это количество различных подперестановок длины п в бесконечной перестановке 7 Г. Последовательность называется комбинаторной сложностью бесконечной перестановки 7 г (и самого языка Комбинаторная сложность бесконечных перестановок (/тг (^))п>2 является аналогом комбинаторной сложности бесконечных слов которая активно исследовалась ранее (см. например обзорную статью [7]).

Пример 4. Для перестановки 7 г из примера 2 имеем /ж (п) = 2 при всех тг ^ 2, так как.

Поскольку перестановок длины п существует ровно 77,!, то для любой бесконечной перестановки 7 Г имеет место верхняя оценка /" (п) ^ 77,!. Покажем, что она может достигаться. Сделаем это по аналогии с примером бесконечного слова над двухсимвольным алфавитом с комбинаторной сложностью 2П, который строится выписыванием (для определённости, в лексикографическом порядке) всех слов длины 1, потом в лексикографическом порядке — слов длины 2, потом — длины 3, и так далее. По аналогии, построим такую бесконечную перестановку 7Го, что 7Го[1, 2] = 12 и 7Го[3,4] = 21, то есть что перестановки 7Го[1, 2], 7Го[3,4] — это все перестановки длины 2, далее 7Го[5, 7] = 123, тг0[8,10] = 132, тг0[11,13] = 213, тг0[14,16] = 231, тг0[17,19] = 312, тг0[20, 22] = 321, то есть по порядку все перестановки длины 3 (в порядке, соответствующем лексикографическому порядку слов над алфавитом {1, 2, 3}, представляющих эти перестановки), далее проделываем то же с перестановками длины 4, и так далее. Указанные условия ещё не задают полностью бесконечную перестановку 7Го, ведь конкатенация для перестановок не определена однозначно, но они задают символы 7тг0(ж, у), когда вершины к (х) и 7 г (у) попадают в один и тот же блок (то есть когда х и у попадают в одно и то же множество из.

1, 2}, {3, 4}, {5, 6, 7}, {8, 9,10}, {И, 12,13}, и т. д.). В остальных случаях, то есть когда 7 г (х) и тг (у) попадают в разные блоки, положим 7⁰{х, у) — 0 для х < у, и тПо (х, у) = 1 для х > у. Нетрудно убедиться, что такое определение.

7Г[1, 77,] При чеТНЫХ 777,;

7Г[2, 72 + 1] При НечётНЫХ 777. корректно. Префикс ДЛИНЫ 34 получившейся бесконечной перестановки 7Го изображён на рисунке 3.

Таким образом, верхние оценки для комбинаторной сложности бесконечных слов и бесконечных перестановок аналогичны. По-иному обстоят дела с нижними оценками. Напомним, что для бесконечных слов имеется следующий известный результат [8]: комбинаторная сложность существенно периодического слова ограничена, а для всякого бесконечного слова являющегося существенно непериодическим, выполнено /ш (п) ^ п + 1, причём эта нижняя оценка достигается на словах Штурма. Отметим, что этот результат верен не только для случая бесконечных вправо слов, но и для случая бесконечных в обе стороны слов. Аналогичный вопрос о низкой комбинаторной сложности бесконечных перестановок исследовался в статье [16]. Оказывается, случаи перестановок на N и перестановок на Ъ различаются. А именно, в статье [16] доказано следующее:

• комбинаторная сложность перестановки на N ограничена тогда и только тогда, когда эта перестановка существенно периодична, а комбинаторная сложность существенно непериодичных перестановок на N может.

Рис. 3. Префикс перестановки с комбинаторной сложностью п! расти сколь угодно медленно;

• комбинаторная сложность перестановки на Z ограничена тогла и только тогда, когда эта перестановка периодична, а для комбинаторной сложности непериодичной перестановки 7 Г на Z выполнена нижняя оценка fn (ri) ^ п — С, где С — некоторая константа (которая не зависит от п, но зависит от 7 Г и может быть произвольно большой), причём эта нижняя оценка неуточняемая.

Кроме того, отметим, что комбинаторная сложность некоторых бесконечных перестановок исследовалась в статьях [21], [22], [23].

При исследовании структуры конечных подслов бесконечного слова w иногда рассматривают последовательность графов (Gw (n)): называемых графами Рози [24], [25]. Для бесконечного слова w обозначим через Gw (n) граф,.

В КОТОРОМ fw (n) ВерШИН, Помеченных ПОДСЛОВамИ W ДЛИНЫ П, И /ur (7l-f-l) дуг, помеченных подсловами w длины 71+1. Каждому слову и длины п + 1, являющемуся подсловом w, соответствует дуга, помеченная словом и и ведущая из вершины, помеченной словом w[l, n], в вершину, помеченную словом и[2,п+1].

Мы предлагаем ввести аналог графов Рози для бесконечных перестановок. Для бесконечной перестановки тт и п ^ 2 обозначим через Gn (n) ориентированный мультиграф, в котором fn (n) вершин, помеченных подпереста-новками 7 Г ДЛИНЫ 71, И /л-(п ± 1) дуг, помеченных подперестановками 7 Г длины п + 1. Каждой г/ G Fn (n + 1) соответствует дуга, помеченная г] и ведущая из вершины, помеченной 7/[1,п] в вершину, помеченную ту[2,п+ 1]. Граф Стг (п) будем называть графом Рози перестановки 7 г порядка п.

В отличии от графов Рози для слов, графы Рози для перестановок могут иметь параллельные дуги. Например, вершины, помеченные перестановками 312 и 123, могут быть соединены двумя параллельными дугами, помеченными перестановками 4123 и 3124. Однако, покажем, что для каждой пары вершин г>1, г>2 количество дуг, ведущих из v в г>2, меньше либо равно 2. В самом деле, допустим, что существует три попарно различных перестановки Т?1,772, 77з е Sn+l, ЧТО 7? i[l, n] = 772(1, та] = 7?3[l, n] И 771 [2, n+ 1] = 772 [2, п + 1] =.

77з[2,п+ 1]. Тогда имеем 7 т (г^) = 7%(г,]) = 7 т? з (м) Для {^Л Ф {1,п + 1};

И ТОЛЬКО ЛИШЬ СИМВОЛЫ 7^(1,77, + 1), 7^(1,71 + 1), 7^(1,77, + 1) могут быть разными. По принципу Дирихле среди этих трёх символов найдутся два одинаковых: 7^(1, п + 1) = 7^(1, п + 1) для некоторых? {1,2,3}, р ф д. Тогда г) р = щ, противоречие.

Пример 5. На рисунке 4 показаны графы Рози 6^(2) (слева) и С7Г (3) (справа) для периодической перестановки тг из примера 2. Все графы Рози Сп (п) для этой перестановки изоморфны между собой.

132 1423.

Рис. 4. Графы Рози ??>(2) и ??>(3) периодической перестановки тс.

На рисунке 5 представлен граф Рози 6^(3) для перестановки щ с комбинаторной сложностью п, которую мы описывали выше и префикс которой был показан на рисунке 3. В графе 0^(3) присутствуют параллельные дуги.

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

Максимальная шаблонная сложность для слов была введена в статье [26] и далее исследовалась в статьях [27], [28], [29], [30], [31], [32], [33]. Последовательность целых положительных чисел (I = (.

1 ^ к ^ п — 1. Количество слов, встречающихся в и) по окну й обозначим через /ш (сГ). в частности, если (1 — ОКНО С дистанциями =. .. = = 1, то получаем комбинаторную сложность: /^(сГ) = 1ги (п). Обозначим к^п) = йир^ где супремум берётся по всем окнам (1 длины п. Последовательность (/чу (п)) будем называть максимальной шаблонной сложностью (или максимальной оконной сложностью, или сложностью Камаэ) бесконечного слова ио.

Аналогичным образом максимальную шаблонную сложность можно определить и для бесконечных перестановок. Будем говорить, что конечная перестановка? длины п встречается в бесконечной перестановке 7 Г по окну (I = ((?1,. .. , Йпх), если существует такое 772, ЧТО? = 7г{тп +Д,. .. , 777 +Дх}, то есть что = 7^(777, + Дх, т + Д-х) при всех г,, 7? {1,., п}, г ф где Д = О, Д = ^ ПРИ 1 ^ ^ ^ ^ — 1- Количество перестановок, встречающихся В 7 Г ПО окну (1 обозначим через /тг (^). В частности, если д, — окно с дистанциями =. = (¿-пх = 1, то получаем комбинаторную сложность: /тг (^) = /ж{п). Обозначим кж (п) = эир^ /^(с?), где супремум берётся по всем окнам (1 длины п. Последовательность {кж{п))п² будем называть максимальной шаблонной сложностью (или максимальной оконной сложностью, или сложностью Камаэ) перестановки 7 г.

Ясно, что максимальная шаблонная сложность всегда не меньше, чем комбинаторная сложность (как для бесконечных слов, так и для бесконечных перестановок), то есть кт (п) ^ 1и){п) и ^(п) ^ /-п-(п). По аналогии с комбинаторной сложностью, интересен вопрос о том, насколько медленно может расти максимальная шаблонная сложность. Для существенно непериодических бесконечных слов в статье [26] доказана нижняя оценка кш{п) ^ 2п. В статье [34] доказано, что кж (п) ^ п для любой существенно непериодической перестановки 7 г.

Пример 6. Нетрудно видеть, что для периодической перестановки 7 г из примера 2 имеем кж (п) = 2 при всех п ^ 2. Кроме того, для перестановки 7Го с комбинаторной сложностью п, которую мы описывали выше и префикс которой изображён на рисунке 3, имеем кЖо (п) = п.

Арифметическая сложность для бесконечных слов была введена в работе [35] и далее исследовалась в статьях [36], [37], [38], [39], [40], [41], [42]. Будем говорить, что слово и длины п встречается в бесконечном слове ии по арифметической прогрессии, если существует такие числа т и что и = ъи (т+с1)и1(т + 2с1). и>(т+пеГ), то есть и (г) = w (m+id), 1 ^ г ^ п. Обозначим через количество слов длины п встречающихся в бесконечном слове %и по арифметической прогрессии. Последовательность (а^п)) называется арифметической сложностью бесконечного слова и).

Аналогичным образом можно определить арифметическую сложность для бесконечных перестановок. Будем говорить, что перестановка? длины п встречается в бесконечной перестановке 7 Г по арифметической прогрессии, если существуют такие числа т и с/, что? = тг{т + (1,т— 2с£,., га + п (1}. Обозначим через аж (п) количество перестановок длины п, встречающихся в бесконечной перестановке 7 г по арифметическим прогрессиям. Последовательность (аж (п))п² будем называть арифметической сложность бесконечной перестановки 7 г. Ясно, что арифметическая сложность всегда не меньше, чем комбинаторная сложность (как для бесконечных слов, так и для бесконечных перестановок), то есть аю (п) ^ /ш (п) и аж (п) ^ /тг (п).

Кроме того, через аж (га, д) будем обозначать бесконечную перестановку, соответствующую линейному порядку, индуцированному -<ж на арифметической прогрессии {га + с1, га + 2 т + Зс£,.}. А именно,.

В частности, при т = 0 и с! = 1 получаем аДО, 1) = 7 Г. Кроме того, обозначим через Аж{п) множество перестановок длины п, встречающихся в 7 г по арифметическим прогрессиям: з) = ъ{т + id, m + 3 п.

Имеем аж (п) = Аж (п).

Пример Т. Нетрудно видеть, что для периодической перестановки 7 Г из примера 2 имеем аж (п) — 4 при всех п ^ 3. Кроме того, для перестановки 7Го с комбинаторной сложностью п!, которую мы описывали выше и префикс которой изображён на рисунке 3, имеем аж0(п) = п.

Ещё одним направлением исследований являются автоматные перестановки [43] (по аналогии с автоматными словами [44]). Бесконечное слово т над алфавитом ?9 называется к-автоматным, если существует детерминированный конечный автомат, состояния которого помечены символами алфавита Ед и для каждого г символ т (г) совпадает с символом, которым помечено состояние, где автомат остановится, после того как на вход было подано /с-ичное представление (г)^ числа г. Известно, например, что слово Туэ-Морса является 2-автоматным.

По аналогии, бесконечная перестановка 7 г называется А-/с-автоматной, если существует детерминированный конечный автомат (ф, ()2,5, б/о, {<, >, =}, т) с функцией перехода 6: С} х Е| —> (и её естественным расширением до функции 5: х (?|)* —> С}) и пометкой состояний автомата г: —> {<, >, такой, что т (6(д0,^)к х и) к)) = < если 7 г (г) < >, если 7 г (г) > 7 г (7') — =, если % = у. то есть после того как на вход автомата подаётся к-ичное представление пары чисел г и автомат должен выдавать символ В статье [43], помимо прочего, показано, что перестановка Туэ-Морса, о которой годробно будет идти речь в главе 4 данной диссертации, является А-2-автоматной.

В целях сравнения свойств бесконечных слов и бесконечных перестановок, представляло бы интерес иметь некую схему, которая каждому бесконечному слову сопоставляла бы бесконечную перестановку с похожими свойствами. Одна из таких схем следующая. Для заданного бесконечного слова ъи над алфавитом {0,1} определим бесконечную перестановку 7 г, положив.

7тг (ж, у) = 0, если (ги (ж) = 0 и го (у) = 1) или (у)(х) = и)(у) = 0 и х < у) или (ги (ж) = у)(у) = 1 и х > у) — а также 7^(2, у) = 1, если (т (х) = 1 и т (у) = 0) или (ъи (х) = и){у) = 1 и х < у) или (гу (ат) = т (у) — 0 и х > у). Несложно проверить, что такое определение корректно. Заметим, что для случая х < у всегда выполнено 7ж (х, у) = т (х).

Покажем, что при таком определении 7г{гг1,., хп, хп+1} = тг{у1?., уп, уп+1} тогда и только тогда, когда и/^х) = у){у), ., го (жп) = Уо (уп). В самом деле, если 7г{ж1, ., хт жп+1} = 7г{у1,., уп, Уп+1}, ТО при каждом 3, 1 ^ 3 ^ п5 имеем = ^^{х^.х^^х) = = Обратно, если ш (х 1) = IV (У1),. .. , ъи^п) = IV (уп), то при любых i, 1 ^ г < j ^ п + 1, имеем = Ъи (Хг) = Уо (Уг) = ОТКуда 7г{х1,. .. , Хп, Хп+1} =.

Как частный случай доказанного свойства, мы получаем, что i: mi + 1, 7П + п + 1] = 7г[т2 + 1, 777,2 + П + 1] ТОГДа И ТОЛЬКО ТОГДа, когда т[гП1 + 1, 777,1 + п) = т[гП2 + 1, 7712 + п].

Доказанное свойство означает, что слово и> и перестановка 7 Г изоморфны в том смысле, что между подпоследовательностями СИМВОЛОВ ДЛИНЫ 77 слова IV и подпоследовательностями вершин длины 77 + 1 перестановки 7 Г существует взаимно-однозначное соответствие. Из этого вытекает, что все свойства слова ги, определяемые через подпоследовательности символов, могут быть перенесены на перестановку 7 г (с увеличением длины подпоследовательности на единицу). В частности, все свойства слова го, определяемые через операцию взятия подслова, могут быть перенесены на перестановку 7 Г. Таковыми свойствами являются, в том числе, комбинаторная сложность и графы Ро-зи (а также ещё ряд свойств, в том числе, частоты подслов и функции рекуррентности, определения которых мы здесь не приводим), то есть имеем /ш (п) = /тг (77 + 1) и = Сж (п + 1). Больше того, то же верно для максимальной шаблонной сложности и для арифметической сложности, то есть кт{п) = кж (п + 1) и аю (п) = аж{п + 1).

Таким образом, бесконечные перестановки действительно являются в некотором смысле обобщением бесконечных слов, ведь каждому бесконечному слову соответствует некоторая изоморфная ему бесконечная перестановка, то есть с точностью до такого изоморфизма множество бесконечных слов является подмножеством множества бесконечных перестановок. На рисунке 6 приведён префикс бесконечной перестановки, изоморфной слову Туэ-Морса.

В настоящей диссертации рассматривается ещё одна, другая, схема, сопоставляющая каждому бесконечному слову над алфавитом {0,1} бесконечную перестановку. Первоначально она возникла в связи с практическими задачами поиска подслова в слове и, в частности, с так называемыми суффиксными массивами. Так, в статье [45] в качестве открытого вопроса сформулирована проблема комбинаторной характеризации перестановок, соответствующих суффиксным массивам. Эта проблема была решена в работе [46]. Однако в обоих указанных статьях, во-первых, рассматривались конечные перестановки, которые порождались конечными словами (которые притом заканчивались на особый символ, отличный от 0 и 1, то есть по существу, там бесконечное слово обрывалось особым символом), что существенно упрощает задачу, а, во-вторых, в них акцент сделан прежде всего на поиск оптимальных алгоритмов определения принадлежности перестановки рассматриваему классу и другие практические задачи. А чисто комбинаторные свойства остались практически неисследованными.

Итак, пусть w = w (l)w (2). w (n). — произвольное существенно непериодическое (никакой суффикс которого не является периодическим) бесконечное вправо слово над алфавитом {0,1}. Каждому п G N может быть сопоставлено действительное число в двоичной системе счисления.

Rw{n) = 0, w (n)w (n + l) w{n + 2). =^2w (n + k)2~{к+1). к^О.

В силу непериодичности суффиксов слова w все эти действительные числа будут различны. Поэтому эти числа порождают некоторую бесконечную перестановку 7Гц, такую, что для любых г, j, г j, неравенство itw{i) < 7t№(j) выполнено тогда и только тогда, когда выполнено неравенство Rw{%) < Rw (j). Другими словами, перестановка irw определяется лексикографическим порядком на суффиксах слова u>, то есть irw = (N, где ;

Пример 8. Для слова Туэ-Морса w = 1 101 001. имеем Rui 1) = 0,1 101 001., Ящ (2) = 0,1 101 001.Я№(3) = 0,101 001.Яад (4) = 0,1 001. Ясно, что Яш (4) < Rw (l) < Яад (З) < Rw{2). Поэтому слово w порождает перестановку irw такую, что 7Пш[1,4] = 2431, первые четыре вершины которой 7Пш[1,4] = 2431 схематично изображены на рис. 7 слева. Л.

2431 2134.

Рис. 7. Допустимая и недопустимая перестановки.

Оказывается, что не все конечные перестановки могут быть получены аналогичным образом из некоторого бесконечного слова над алфавитом {0,1}. Например, для перестановки т = 2134 не существует слова w такого, что ^[1,4] = г. В самом деле, если бы такое слово w существовало, то из леммы 2 (которая утверждает, что если w (j) = 0, то irw (j) < 7rw (j + l), и которую мы докажем в главе 1) вытекает, что первый его символ был бы 1, ибо иначе мы бы имели 7гад (1) < 71^(2), что противоречило бы тому, что т (1) > т (2). Аналогично получаем, что и>(3) = 0. Но тогда Ии}(1) > Иш{3), однако т (1) < т (3), противоречие.

Итак, конечную перестановку назовём лексикографически ъи-допустимой (или, для краткости, просто т-допустимой), если она является подпереста-новкой перестановки 7ГЮ. Конечную перестановку назовём лексикографически допустимой (или допустимой), если она лексикографически ии-допустима для какого-нибудь слова т. Из предыдущих примеров следует, что перестановка 2431 лексикографически допустима, а перестановка 2134 — нет.

В настоящей диссертации исследуются свойства конечных допустимых и и]-допустимых перестановок, а также бесконечных перестановок 71″^, полученных описанным выше способом как лексикографический порядок на суффиксах бесконечного слова, для слов Штурма, слова удвоения периода, слова Туэ-Морса.

Отметим, что лексикографический порядок на подсловах возникает в другой задаче (которая, однако, прямого отношения к нашим результатам не имеет), а именно в задаче факторизации бесконечных слов в конкатенацию слов Линдона [47], [48], [49], [50]. Такой факторизации соответствует убывающая последовательность вершин перестановки, порождённой лексикографическим порядком на суффиксах данного бесконечного слова.

Отметим, что наше определение перестановок допускает следующее обобщение. Зафиксируем натуральное число к ^ 2. Набор 7 г = (X, ., будем называть обобщённой перестановкой порядка к, если:

• ^ — линейный порядок на X;

• Гп, • • •?^к ~ частичные порядки на X, что для любых х, у? X, х Ф у, выполнено ровно одно из к условий: х гп У, ¦ ¦ •, х У (то единственное ]. для которого х у обозначаем ] = '^{х. у)).

Заметим, что при к — 2 определение эквивалентно определению перестановок, данному выше, так как в этом случае частичные порядки ^ и -<2 являются линейными и обратными друг другу (то есть достаточно задать лишь один из них). Для заданной обобщённой перестановки частичные порядки на X индуцируют частичные порядки на подмножествах X, поэтому понятие подперестановки определяется естественным образом. Следовательно, можно определить комбинаторную сложность. Задачи, связанные с комбинаторной сложностью обобщённых перестановок и другими их комбинаторными характеристиками, представляют одно из возможных направлений для дальнейших исследований.

Опишем кратко структуру настоящей диссертации.

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

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

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

В главе 4 определяется и исследуется перестановка Туэ-Морса. В частности, результатом этой главы является доказательство эквивалентности двух существенно разных определений перестановки Туэ-Морса.

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

Результаты диссертации опубликованы в статьях [51], [52], [53], [54], [55].

1. Thue A. Uber unendliche Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. 1. Mat.-Nat. Kl. Christiana, 1906. pp. 1−22.

2. Thue A. Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. Christiana, 1912. pp. 1−67.

3. Thue A. Probleme uber Veranderungen von Zeichenreihen nach gegebenen Regeln // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. Christiana, 1914. pp. 1−34.

4. Berstel J., Perrin D. The origins of combinatorics on words // European Journal of Combinatorics. 2007. Vol. 28. pp. 996−1022.

5. Lothaire M. Combinatorics on Words. Vol. 17 of Encyclopedia of Mathematics and Its Applications. Addison-Wesley, 1983.

6. Lothaire M. Algebraic Combinatorics on Words. Cambridge University Press, 2002.

7. Ferenczi S. Complexity of sequences and dynamical systems // Discrete Mathematics. 1999. Vol. 206. pp. 145−154.

8. Morse M., Hedlund G.A. Symbolic dynamics II: Sturmian trajectories // Amer. J. Math. 1940. Vol. 61. pp. 1−42.

9. Allouche J.-P., Shallit J. The ubiquitous Prouhet-Thue-Morse sequence // Proceedings of SETA'98 (Sequences and their Applications), DMTCS / Ed. by C. Ding, T. Helleseth, H. Niederreiter. Springer, 1999. pp. 1−16.

10. Damanik D. Local symmetries in the period doubling sequence // Discrete Applied Mathematics. 2000. Vol. 100. pp. 115−121.

11. Berstel J. Recent results on Sturmian words // Developments in language theory II. Magdeburg, 1995. pp. 13−24.12. de Luca A. A Combinatorial Property of the Fibonacci Words // Information Processing Letters. 1981. Vol. 12, no. 4. pp. 193−195.

12. Rote G. Sequences with subword complexity 2n // Journal of Number Theory. 1994. Vol. 46. pp. 196−213.

13. Epifanio C., Koskas M., Mignosi F. On a conjecture on bidimensional words // Theoretical Computer Science. 2003. Vol. 299. pp. 123−150.

14. Fon-Der-Flaass D., Frid A. On periodicity and low complexity of infinite permutations // European Journal of Combinatorics. 2007. Vol. 28, no. 8. pp. 2106−2114.

15. Davis J., Entringer R., Graham R., Simmons G. On permutations containing no long arithmetic progressions // Acta Arithmetica. 1977. Vol. 34. pp. 81−90.

16. Frid A. Infinite permutations vs. infinite words // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 13−19.

17. LeSaulnier T., Vijay S. On permutations avoiding arithmetic progressions // Discrete Mathematics. 2011. Vol. 311. pp. 205−207.

18. Ardai H., Brown T., Jungic V. Chaotic Orderings of the Rationals and Reals // The American Mathematical Monthly. 2011. Vol. 118, no. 10. pp. 921−925.

19. Widmer S. Permutation complexity of the Thue-Morse word // Advances in Applied Mathematics. 2011. Vol. 47, no. 2. pp. 309−329.

20. Widmer S. Permutation complexity related to the letter doubling map // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 265−276.

21. Valyuzhenich A. Permutation complexity of the fixed points of some uniform binary morphisms // Electronic Proceedings in Theoretical Computer Science. 2011. Vol. 63. pp. 257−264.

22. Rauzy G. Suites a termes dans un alphabet fini // Seminaire de Theorie des nombres de Bordeaux, expose 25. 1983. pp. 2501−2516.

23. Cassaigne J. On a conjecture of J. Shallit // Proceedings of the 24th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science. Vol. 1256. Bologna, Springer, 1997. pp. 693−784.

24. Kamae T., Zamboni L. Sequence entropy and the maximal pattern complexity of infinite words // Ergodic Theory and Dynamical Systems. 2002. Vol. 22, no. 4. pp. 1191−1199.

25. Kamae T., Zamboni L. Maximal pattern complexity for discrete systems // Ergodic Theory and Dynamical Systems. 2002. Vol. 22. pp. 1201−1214.

26. Kamae T., Rao H., Tan Bo, Xue Yu-Mei. Language structure of pattern Sturmian word // Discrete Mathematics. 2006. Vol. 306. pp. 1651−1668.

27. Kamae T., Rao H., Xue Yu-Mei. Maximal pattern complexity of two-dimensional words // Theoretical Computer Science. 2006. Vol., 359. pp. 15−27.

28. Gjini N., Kamae T., Tan Bo, Xue Yu-Mei. Maximal pattern complexity for Toeplitz words // Ergodic Theory and Dynamical Systems. 2006. Vol. 26. pp. 1073−1086.

29. Kamae T., Rao H. Maximal pattern complexity of words over? letters // European Journal of Combinatorics. 2006. Vol. 27, no. 1. pp. 125−137.

30. Kamae Т., Salimov P. On maximal pattern complexity of some automatic words // Ergodic Theory and Dynamical Systems. 2011. Vol. 31, no. 5. pp. 1463−1470.

31. Kamae T. Behavior of various complexity functions // Theoretical Computer Science. 2012. Vol. 420. pp. 36−47.

32. Avgustinovich S., Frid A., Kamae Т., Salimov P. Infinite permutations of lowest maximal pattern complexity // Theoretical Computer Science. 2011. Vol. 412. pp. 2911−2921.

33. Avgustinovich S., Fon-Der-Flaass D., Frid A. Arithmetical complexity of infinite words // Words, Languages & Combinatorics III / Ed. by M., Ito, T. Imaoka. World Scientific Publishing, 2003. pp. 51−62.

34. Frid A. Arithmetical complexity of symmetric D0L words // Theoretical Computer Science. 2003. Vol. 306. pp. 535−542.

35. Frid A. Sequences of linear arithmetical complexity // Theoretical Computer Science. 2005. Vol. 309. pp. 68−87.

36. Frid A. On possible growths of arithmetical complexity // Theoretical Informatics and Applications. 2006. Vol. 40, no. 3. pp. 443−458.

37. Avgustinovich S., Cassaigne J., Frid A. Sequences of low arithmetical complexity // Theoretical Informatics and Applications. 2006. Vol. 40, no. 4. pp. 569−582.

38. Фрид А. Нижняя оценка на арифметическую сложность слов Штурма // Сибирские электронные математические известия. 2005. Т. 2. С. 14−22.

39. Cassaigne J., Frid A. On arithmetical complexity of Sturmian words // Theoretical Computer Science. 2007. Vol. 380. pp. 304−316.

40. Salimov P. Constructing infinite words of intermediate arithmetical complexity // Language and Automata Theory and Applications, Lecture Notes in Computer Science. Vol. 5457. Springer, Berlin, 2009. pp. 696−701.

41. Frid A., Zamboni L. On automatic infinite permutations // RAIRO Theoretical Informatics and Applications. 2012. Vol. 46, no. 1. pp. 77−85.

42. Allouche J.-P., Shallit J. Automatic sequences — theory, applications, generalizations. Cambridge University Press, 2003.

43. Grossi R., Vitter J. Compressed suffix arrays and suffix trees with applications to text indexing and string matching // Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. 2000. pp. 397−406.

44. He M., Munro J., Rao S. A categorization theorem on suffix arrays with applications to space efficient text indexes // Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 2005. pp. 23−32.

45. Siromoney R., Matthew L., Dare V., Subramanian K. Infinite Lyndon words // Information Processing Letters. 1994. Vol. 50, no. 2. pp. 101−104.

46. Melancon G. Lyndon factorization of infinite words // STACS'96, 13th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 1046 / Ed. by C. Puech, R. Reischuk. SpringerVerlag, 1996. pp. 147−154.

47. Melancon G. Lyndon factorization of sturmian words // Discrete Mathematics. 2000. Vol. 210. pp. 137−149.

48. Seebold P. Lyndon factorization of the Prouhet words // Theoretical Computer Science. 2003. Vol. 307. pp. 179−197.

49. Макаров M. О перестановках, порождённых бесконечными бинарными словами // Сибирские электронные математические известия. 2006. Т. 3. С. 304−311.

50. Макаров М. О перестановках, порождённых словами Штурма // Сибирский математический журнал. 2009. Т. 50, № 4. С. 850−857.

51. Makarov М. On the infinite permutation generated by the period doubling word // European Journal of Combinatorics. 2010. Vol. 31, no. 1. pp. 368−378.

52. Makarov M. On an infinite permutation similar to the Thue-Morse word // Discrete Mathematics. 2009. Vol. 309. pp. 6641−6643.

53. Макаров M. Антимонотонные перестановки // Сибирские электронные математические известия. 2012. Т. 9. С. 346−359.

54. Elizalde S. The number of permutations realized by a shift // SI AM Journal of Discrete Mathematics. 2009. Vol. 23. pp. 765−786.

55. Domaratzki M., Kisman D., Shallit J. On the number of distinct languages accepted by finite automata with n states //J. Autom. Lang. Comb. 2002. Vol. 7. pp. 469−486.

56. Seebold P. Fibonacci morphisms and sturmian words // Theoretical Computer Science. 1991. Vol. 88. pp. 365−384.

57. Fraenkel A., Simpson J. The exact number of squares in Fibonacci words // Theoretical Computer Science. 1999. Vol. 218. pp. 95−106.

58. Berstel J., Pocchiola M. A geometric proof of the enumeration formula for Sturmian words // Internat. J. Algebra Comput. 1993. Vol. 3. pp. 349−355.

59. Cassaigne J. Complexite et facteurs speciaux // Bulletin of the Belgian Mathematical Society. 1997. Vol. 4, no. 1. pp. 67−88.

60. Августинович С. Число различных подслов заданной длины в последовательности Морса-Хедлунда // Сибирский журнал исследования операций. 1994. Т. 1, № 2. С. 3−7.