Комбинаторика на бесконечных перестановках тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ НАУКИ ИНСТИТУТ МАТЕМАТИКИ им. С.Л. СОБОЛЕВА

005055160

Макаров Михаил Александрович

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

01.01.09 - дискретная математика и математическая кибернетика

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

перестановках

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 5 НОЯ 2012

Новосибирск - 2012

005055160

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте математики им. С.Л. Соболева Сибирского отделения Российской академии наук

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

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

кандидат физико-математических наук Августинович Сергей Владимирович кандидат физико-математических наук Глебов Алексей Николаевич, доктор физико-математических наук профессор Федорук Михаил Петрович Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Уральский федеральный университет имени первого Президента России Б.Н. Ельцина»

Защита состоится 21 ноября 2012 года в 15 часов на заседании диссертационного совета Д 003.015.01 при Федеральном государственном бюджетном учреждении науки Институте математики им. С.Л. Соболева Сибирского отделения Российской академии наук по адресу: 630090, г. Новосибирск, пр. Академика Коптюга, 4, ауд. 417.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук.

Автореферат разослан «ЛЁ.—» —-2012 г.

"Ученый секретарь диссертационного совета, д.ф.-м.н.

Шамардин Ю.В.

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

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

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

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

Слово Туэ-Морса ш = 0110100110010110... может быть задано ре-куррентно условиями «;(0) = 0, ш(2п) = ш(п), и){2п + 1) = 1 — ю(тг) при всех п ^ 0. Также слово Туэ-Морса можно определить как неподвижную точку морфизма. А именно, рассмотрим отображение <р: {0,1} —> {0,1}2, заданное равенствами <¿>(0) = 01 и <р(1) = 10. Для произвольного слова й = в(1)... й(п) е {0,1}" положим <р(.?) = </?(з(1))... <^(в(п)). Рассмотрим последовательность г/>0 = 0, и>\ = 01, и>2 — ОНО, г/;3 = 01101001, ..., где и'„+1 = 1р(у'п). Нетрудно доказать, что для любого п слово гип является префиксом слова и>п+\. Следовательно, существует бесконечное слово № = ш(0)ш(1)и>(2)... = 0110100110010110 ..., что юп = ги(0)... ги(2п - 1) для каждого п. Это слово и называется словом Туэ-Морса.

Слово удвоения периода ы = 010001010100... может быть задано рекуррентно условиями ы(2п — 1) = 0 и ги(2п) = 1 — ги(п) для всех п > 1. Также оно является неподвижной точкой морфизма <р: 0 н-> 0100,1

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

Примером слов Штурма является слово Фибоначчи. Определим последовательночть конечных слов рекуррентно: qo = 0, г^ = 01, <7„ = qn-lq„-2■ Поскольку каждый член последовательности является префиксом следующего члена, то существует такое бесконечное слово q —- 010010100100101001010..., что все члены последовательности qn являются его префиксами. Это слово q и называется словом Фибоначчи. Также его можно определить как неподвижную точку морфизма ¡р: Он 01,1 >-> 0. Известно, что слово Фибоначчи является словом Штурма с наклоном а — (3 — \/5)/2.

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

Есть и другие обобщения, аналоги результатов комбинаторики на словах. Среди них — исследование комбинаторных свойств бесконечных перестановок. Именно им и посвящена настоящая диссертация.

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

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

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

Нетрудно понять, что любую биекцию р\ {!,..., ri) -> {1,..., п} можно мыслить как линейный порядок на {1,...,п}. В самом деле, положим, что х <р у тогда и только тогда, когда р(х) < р(у). Легко проверяется, что это действительно линейный порядок. Обратно имея некоторый линейный порядок X на множестве {1,..., п}, можем построить по нему биекцию р, {1,..., „} {1,..., п} следующим образом: р( 1) положим равным минимальному элементу из множества {1,..., п) по линейному порядку далее р{2) положим равным второму'по величине элементу, и так далее, р(п) положим равным максимальному элементу по линейному порядку < Очевидно, что р - действительно биекцпя.

Тем самым, классическое определение конечных перестановок как биекций эквивалентно нашему определению через линейные порядки. Этим в частности, оправдывается такое название. Конечная перестановка тг со-отвествующая биекции р: {1,...,п} {!,...,„.},„ алгебре часто записывается в виде

7Г — [ 1 2 ••■ «

Р(1) Р(2) ... р(п)

мы же будем записывать лишь нижнюю строку: тг = р(1)р(2). ..р(п). При этом число п мы будем называть длиной перестановки тг. Множество всех конечных перестановок длины п обозначаем через

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

Для каждой перестановки тг (конечной или бесконечной) их у € X х Ф У, определим символ 7,(.х, у) е {0,1} следующим образом:

Ъ(х,У)=1°' 6СЛН Я(Х) < Ж{У)'

[1, если тг(.т) > ж (у).

В статье [16] дано определение периодичности перестановок. Будем говорить, что бесконечная перестановка тг периодична с периодом I, если у) = (х + I,у + 1) для всех х, у. Будем говорить, что бесконечная перестановка тт существенно периодична с периодом t, если существует число N0, что 7*(ж, ?/) = 7„(х + г,у + *) при всех х ^ Ы0, у ^ N0, т.е., другими словами, если периодичен какой-то её суффикс. В статье [16] доказано, что периодические перестановки не могут быть представлены последовательностями из натуральных чисел.

Линейные порядки на X индуцируют линейные порядки на подмножествах X, следовательно естественным образом можно определить понятие подперестановки. Дадим формальное определение. Для перестановки 7г = (X, (конечной или бесконечной) и конечного набора Ух,...,Уп £ X, где 7/1 < ... < ?/„, обозначим через 7г{уь..., ?;„} перестановку на {1,..., п}, определённую равенством .....Уп}(г,Л = 1*Ы,У])

при 1 < г < п, 1 < < п, г ^ 3. Особенно интересен случай, когда уи ■ ■ ■, уп — последовательные целые числа (и соответственно когда X = N или X = {1,..., N}). Итак, пусть заданы числа т\ и т2, причём т\ < т2. Тогда перестановку тфгц, тх +1,..., т2} будем обозначать через 7г[т1, т2]. Иными словами, 7г[ть т2] — это такая перестановка длины т2 - т\ + 1, что при 1 ^ г ^ ш2 - ш 1 + 1 и 1 ^ з < тп,2 — тп\ + 1 выполнено 77г[т1,т2](^.7') = 77г(«11+г-1,т1+^'-1). Будем говорить, что конечная перестановка £€<!>„ является подперестансвкой конечной или бесконечной перестановки 7г, если £ = 7г[7пг,т2] для некоторых тг и т2. Аналогичное обозначение мы будем применять для слов над конечным алфавитом, то есть для слова и (конечного или бесконечного) запись и[?7?.1,т2] будет означать его подслово 1/(7721) • ■ • и(тп2).

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

Поскольку слов длины п над алфавитом {0,1} существует ровно 2™, а перестановок длины п существует ровно тг!, то для любого бесконеч-

ного слова w имеет место верхняя оценка fw(n) ^ 2", а для любой бесконечной перестановки тг имеет место верхняя оценка /ж(п) ^ п\. Несложно построить бесконечное слово и бесконечную перестановку, на которых эти верхние оценки достигаются.

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

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

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

Помимо комбинаторной сложности, при исследовании структуры конечных подслов бесконечного слова w иногда рассматривают последовательность графов (Gw(n)), называемых графами Рози [19], [20]. Для бесконечного слова w обозначим через Gw(n) граф, в котором fw(n) вершин, помеченных подсловами w длины п, и fw(n + 1) дуг, помеченных подсловами w длины п + 1. Каждому слову и длины п + 1, являющемуся подсловом in, соответствует дуга, помеченная словом и и ведущая из вершины, помеченной словом ы[1,п], в вершину, помеченную словом и[2, п + 1].

Можно ввести аналог графов Рози для бесконечных перестановок. Для бесконечной перестановки 7г и п > 2 обозначим через Gn(n) ориен-

тированный мультиграф, в котором f„(n) вершин, помеченных подпере-становками -к длины п, и /^(n + 1) дуг, помеченных подперестановками тг длины 77,+ 1. Каждой т/ е F„(n+ 1) соответствует дуга, помеченная т] и ведущая из вершины, помеченной т][1, п] в вершину, помеченную г][2, п + 1]. Граф Gn(n) будем называть графом Рози перестановки 7г порядка п.

В отличии от графов Рози для слов, графы Рози для перестановок могут иметь параллельные дуги. Например, вершины, помеченные перестановками 312 и 123, могут быть соединены двумя параллельными дугами, помеченными перестановками 4123 и 3124. Однако, несложно показать, что для каждой пары вершин vi, v2 количество дуг, ведущих из vi в «2, меньше либо равно 2.

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

Максимальная шаблонная сложность для слов была введена в статье [21] и далее исследовалась в статьях [22], [23], [24], [25], [26], [27], [28]. Последовательность целых положительных чисел d = (di,... ,rf„_i) условимся называть okhoai длины п с дистанциями d.\, ..., . Будем говорить, что конечное слово и длины п встречается в бесконечном слове w по окну d = (db...,rfn_i), если существует такое т, что и = w(m, + D0) • ■ ■ w(m + Аi-i)> то есть что "(*) = ™(m + Di-1) при всех г € {1,..., п}, где D0 = 0, Dk = dj при 1 < k < п - 1. Количество

слов, встречающихся в w по окну d, обозначим через fw(d). В частности, если d — окно с дистанциями г'\ = ... = dn-{ = 1, то получаем комбинаторную сложность: fw(d) = fw(n). Обозначим kw(n) = supd fw(d), где супремум берётся по всем окнам d. длины п. Последовательность (k,w(n)) будем называть максимальной шаблонной сложностью (или сложностью Камаз) бесконечного слова w.

Аналогичным образом максимальную шаблонную сложность можно определить и для бесконечных перестановок. Будем говорить, что конечная перестановка £ длины п встречается в бесконечной перестановке 7г по окну d — (di,... ,dn-i), если существует такое ш, что £ = тт{т + Do, ...,т+ Dn_i}, то есть что -у = + А-ь т + ^j-i) при всех г, j е {1,..., г?,}, г ^ j, где D0 = 0, Dk = di ПРИ 1 О < га-1. Количество перестановок, встречающихся в -к по окну d обозначим через (ei). В частности, если d. — окно с дистанциями d,\ — ... = dn-1 = 1, то получаем комбинаторную сложность: f„(d) = U(n). Обозначим К(п) = supdf„(d.), где супремум берётся по всем окнам d. длины п. Последовательность (fcw(n))n^2 будем называть максимальной шаблонной сложностью (или

сложностью Камаэ) перестановки тг.

Ясно, что максимальная шаблонная сложность всегда не меньше, чем комбинаторная сложность (как для бесконечных слов, так и для бесконечных перестановок), то есть kw(n) > fw(n) и kn(n) > f^(n). По аналогии с комбинаторной сложностью, интересен вопрос о том, насколько медленно может расти максимальная шаблонная сложность. Для существенно непериодических бесконечных слов в статье [21] доказана нижняя оценка kw(n,) > 2п. В статье [29] доказано, что kv{ri) ^ п для любой существенно непериодической перестановки тт.

Арифметическая сложность для бесконечных слов была введена в работе [30] и далее исследовалась в статьях [31], [32], [33], [34], [35], [36], [37]. Будем говорить, что слово и длины п встречается в бесконечном слове и> по арифметической прогрессии, если существует такие числа т. и d, что и, = w{m+d)w{m.-\-2d) ... w(m + nd), то есть u(i) = w(m + id), 1 ^ i si п. Обозначим через a.w(n) количество слов длины п, встречающихся в бесконечном слове w по арифметической прогрессии. Последовательность (aw(n)) называется арифметической сложностью бесконечного слова w.

Аналогичным образом можно определить арифметическую сложность для бесконечных перестановок. Будем говорить, что перестановка £ длины п встречается в бесконечной перестановке тт по арифметической прогрессии, если существуют такие числа m и d, что £ = тт{т + d,m + 2d,... ,т 4- nd.}. Обозначим через (^(п) количество перестановок длины п, встречающихся в бесконечной перестановке тг по арифметическим прогрессиям. Последовательность (пл("))п>2 будем называть арифметической сложность бесконечной перестановки 7г. Ясно, что арифметическая сложность всегда не меньше, чем комбинаторная сложность (как для бесконечных слов, так и для бесконечных перестановок), то есть ow(n) ^ fw(n) и аж(п) ^ fn(n).

Из изложенного выше о комбинаторной сложности становится понятным, что свойства бесконечных слов и бесконечных перестановок в чём-то сходны, а в чём-то различны. Соответственно, актуальной темой является сравнение свойств бесконечных слов и бесконечных перестановок. В целях такого сравнения, представляло бы интерес иметь некую схем}', которая каждому бесконечному слову сопоставляла бы бесконечную перестановку с похожими свойствами. Одна из таких схем следующая. Для заданного бесконечного слова и> над алфавитом {0,1} определим бесконечную перестановку п, положив 7„(х,у) = 0, если (и>(х) = 0 и w(y) = 1) или (w(x) = w(y) = 0 и х < у) или (w(x) = w(y) = 1 и х > у); а также 7т,(х,у) = 1, если (iu(x) = 1 и w(y) = 0) или (w(x) = w(y) = 1 и х < у) или (w(x) = w(y) = 0 и х > у). Несложно проверить, что такое

определение корректно. Заметим, что для случая х < у всегда выполнено 1* (х,у) = ы(х).

Можно доказать, что при таком определении щтх +1, шх + п+1] -7г[т2 + 1, ш2 + п + 1] тогда и только тогда, когда ги[гп1 + п, тг + п] = ■ш{т2 + 1 ,т2 + п]. Это свойство означает, что слово и; и перестановка 7Г изоморфны в том смысле, что между подсловами длины п слова иг и подперестановками длины п +1 перестановки тг существует взаимно-однозначное соответствие. В частности, из этого вытекает, что все свойства слова и>, определяемые через операцию взятия нодслова, могут быть перенесены на перестановку 7г. Таковым свойством является, в том числе, комбинаторная сложность (а также ещё ряд свойств, в том числе, графы Рози, частоты подслов и функции рекуррентности, определения которых мы здесь не приводим), то есть имеем /и,(п) = /„(п + 1). Больше того, несложно показать, что то лее верно для максимальной шаблонной сложности и для арифметической сложности, то есть ку:(п) = к- (п + 1) и

аь,(п)^-а.7Т{ п+ 1).

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

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

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

быть сопоставлено действительное число в двоичной системе счисления Лш(п) = 0,и>(п)ь>(п + 1)?/|(тг + 2)... = и)(п Н- к)Т{к+1).

к^О

В силу непериодичности суффиксов слова ги все эти действительные числа будут различны. Поэтому эти числа порождают некоторую бесконечную перестановку ?ги, такую, что для любых г.] 6 {1 ,...,п} неравенство 7гг„(г) < 7ги, (-]) выполнено тогда и только тогда, когда выполнено неравенство /?ш(г) < Пь,(]). Другими словами, перестановка 7ГШ определяется лексикографисеким порядком на суффиксах слова -ш, то есть 7Т.Ш = (М, !<„,), где — лексикографический порядок на суффиксах

Например, для слова Туэ-Морса и> — 01101001... имеем 1) = 0,01101001..., Лю{2) = 0,1101001..., Ли,(3) = 0,101001..., Лю(4) = 0,01001 Ясно, что Ли,(4) < Ли>( 1) < Л.и!(3) < /?ш(2). Поэтому слово т порождает перестановку такую, что 7гш[1,4] = 2431. Оказывается, что не все конечные перестановки могут быть получены аналогичным образом из некоторого бесконечного слова над алфавитом {0,1}. Например, можно доказать, что для перестановки 2134 не существует слова и> такого, что 7гш[1,4] = 2134.

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

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

Цель работы состоит в исследовании комбинаторных свойств бесконечных перестановок.

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

Практическая значимость. Работа носит теоретический характер.

На защиту выносятся следующие основные результаты диссертации:

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

2. а. Для класса бесконечных перестановок, порождённых лексико-

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

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

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

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

Апробация работы. Результаты диссертации докладывались на XLIV международной научной студенческой конференции «Студент и научно-технический прогресс» (Новосибирск, 2006), а также на семинаре «Факторные языки» (ИМ СО РАН).

Публикации. Результаты диссертации опубликованы в статьях [40], [41], [42], [43], [44].

Личный вклад автора. Все результаты диссертации получены лично автором.

Структура и объём диссертации. Диссертация состоит из введения, пяти глав и списка литературы. Объём диссертации составляет 111 страниц.

Содержание работы

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

Лемма. Пусть 7г„[1,п] = 7г„[1,п]. Тогда i/,[l,n - 1] = и[1,тг - 1].

Перестановка тг' длины п + 1 называется продолжением влево перестановки 7Г длины п, если тг'[2, п+ 1] = тт. Перестановка п' длины n-f 1 называется продолжением вправо перестановки 7Г длины п, если 7г'[1, га] = -к.

Теорема. Каждую допустимую перестановку длины п ^ 2 можно продолжить влево до допустимой перестановки длины п+1 либо двумя, либо тремя способами. причём перестановок второго т,ипа существует, в точности гр(п) = ]Гф( где ¡i, - функция Мёбиуса.

Теорема. Допустимых перестановок длины п+1 существует в

точности Р(п + 1) — V . 2n-t.

t=i

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

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

п + 1 < fu(n) ^ Л,,(га + 1) < Р(п + 1) = 2П(п -а + 0(п2~п'2)), (*)

В главе 2 определяются и исследуются перестановки Штурма. Зафиксируем иррациональное число а е (0,1) и действительное число /3 g R. Пусть w — слово Штурма с параметрами а и /3. Перестановкой Штурма будем называть перестановку а = тги,, порождённую из слова Штурма w лексикографическим порядком на суффиксах. Рассмотрим кроме того последовательность действительных чисел (,чп), определённую соотношением sn = an + /3 - [an + р\. Обозначим через а' перестановку, порождённую последовательностью (.sn), то есть такую перестановку гт', что сг'(г) < <r'(j) тогда и только тогда, когда s¿ < sj.

Лемма. Выполнено а = а'.

Лемма. Имеем <т[тЛ + 1,тЛ + п + 1] = <т[т2 + 1,т2 + п + 1] тогда и только тогда, когда w\m,i + 1, тЛ + га] = w[m2 + 1, т2 + га].

Теорема. Комбинаторная сложность перестановки Штурма а не зависит ни от а, ни от ¡3, и равна fa(n) = fw(n -I) — п. В частности, на перестановках Штурма достигается нижняя оценка (*). Кроме того, граф Рози Ga{n) изоморфен графу Рози Gw(n - 1).

Теорема. Максимальная шаблонная сложность перестановки Штурма а не зависит ни от а, ни от в, и равна ка(п) = п.

Теорема. Арифметическая сложность перестановки Штурма а не зависит ни от а, ни от ¡3, и равна

п

аст(п +1) = (п + 1)

Р=1

где — функция Эйлера (то есть <р[р) — это количество чисел из множества {1,... ,р — 1}, взаимно простых с р).

Таким образом, для перестановок Штурма, мы исследовали некоторые комбинаторные свойства. Среди этих свойств отдельно можно выделить те, которые определяются только через операцию взятия подпе-рестановки. В частности, это комбинаторная сложность (а также графы Рози, частоты подперестановок, функции рекуррентности, определения которых мы здесь не приводим). Мы показали, что такие свойства могут быть непосредственно перенесены с аналогичных свойств слов Штурма. Напротив, такие свойства, как арифметическая сложность и максимальная шаблонная сложность, существенно отличаются от соответствующих свойств слов Штурма. Так, например, мы показали, что ка(п) = п, в то время как максимальная шаблонная сложность слов Штурма равна 2п. Для арифметической сложности ситуация вообще удивительна: мы нашли точную формулу для аа(п) (и она не зависит от параметров а и /?), в то время, как арифметическая сложность слов Штурма зависит от а и до сих пор не найдена, для неё известны лишь нижняя [35] и верхняя [36] оценки.

В главе 3 определяется и исследуется перестановка удвоения периода. £ = 7гш, порождённая лексикографическим порядком на слове удвоения периода и> = 010001010100 ....

Мы сводим задачу о нахождении комбинаторной сложности к двум независимым более простым задачам о продолжаемости перестановок влево. Для каждого п мы рассматриваем два множества перестановок длины п: Вп и 5П. Они определяются следующим образом.

Перестановка 7г принадлежит Вп, если существует пара чисел (ть т2), что выполнены следующие свойства:

• 7Г = 7Г№[Ш1 + 1, 777! + 77,] = 7ГШ [т2 + 1, ГП2 + 77.];

• ^[Шь 771! +П]ф 7Гш[т2, 7772 + "■];

• 1л(т,1) ф и){т2).

Перестановка 7г принадлежит 5П, если существует пара чисел {тл, т2), что выполнены следующие свойства:

• 7Г = 7ГШ[?П1 + 1, ТОХ + 77,] = 7Г,„[га2 + 1, ТП2 + 77,];

• 7ГШ[777.1 , »щ + п] ф 7гш[т2, т2 + п];

• 7х;(т1) = 'ш(т2).

Теорема. Справедлива рекуррентная формула для колгбипаторной слоэ/с-ности:

Л("+1)-/е(п) = |Д,| +15,11-

Итак, мы свели проблему нахождения /с(н) к проблеме нахождения |£? п| и I■ Подчеркнём, что множества 13п и . вообще говоря, могут пересекаться (и для случая перестановки удвоения периода при некоторых п они действительно пересекаются). В следующих двух теоремах находятся Ьп — \Вп\ и яп = |5„| для случая перестановки удвоения периода,.

Теорема. Для Ьп = \Вп\ имеем: Ь2 = 1, Ь3 = 2, Ь4 = 2, Ь5 — 2, Ьп = 1 для 5 • 2« 4-1 < п < 6 • 2\ Ьп = 2 Лы 6 ■ 2( + 1 «С п ^ 5 • 2г+1.

Теорема. Для 5„ = |5„| ыл«еел« л3 = 2; я„ = 21 при п = 3-2', * > 1; .«„ = О при п ф 3 ■ 2Ь.

Теорема. Имеем Д(2) = 2, Д(3) = 3, Д(4) = 7, Д(5) = 9, /£(6) = 11. При имеем,

[ _ | " + 6 • 24 - 1, если 5 • 2( < п < б ■ 2г для некоторого I > 1;

[ 2п + 2 • 21 - 2, если 6 • 21 < п < 10 • 2г для некоторого I > 0.

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

Первое определение — это порождение бесконечной перестановки 7Гц, с помощью лексикографического линейного порядка на суффиксах слова Туэ-Морса т = 0110100110010110 .... Напомним, что для каждого п € Ки{0} мы рассматриваем число В.и,{п) в двоичной системе счисления:

Яги(п) = 0,ы(п)и>(п + 1 )и>(п + 2) ... = ]Г г„(п + /с)2~(А:+1).

к^ О

Определение 1. Мы определяем перестановку Туэ-Морса г — (NU{0},< , dr), где х ^т у тогда и только тогда, когда Rw(x) < Rw{y)-

Для второго определения мы вводим морфизм на действительных числах. Напомним, что слово Туэ-Морса порождается морфизмом 0 i--» 01,1 i-» Ю. По аналогии, мы конструируем последовательность действительных чисел, порождённую итерированием морфизма.

Если х = (хь...,.тп) е К" ну— {у!,...,ук) 6 то определим x\\y = (xl,...,xn,yl,...,yk)€Rn+k.

Рассмотрим отображение ip-. К. R2, определённое так:

ы [(!>! +1). если х SC 0;

\(|,|-1), если х > 0.

Теперь определим <р((жь..., хп)) = (р(хг) || ... || <р(хп). Заметим, что для любых х € К" и у 6 Rk мы имеем ip(x || у) = ip(x) || <р(у).

Начнём с Т'(0) = 0. Рассмотрим последовательность i0 = Т{0) = 0,

h = f(.to), t-2 = <p(h), t3 = ¡p(t2),____Легко видеть, что каждый элемент

этой последовательности имеет в качестве префикса предыдущий элемент. Следовательно, существует последовательность действительных чисел (Т(п))„^0 такая, что для всех п выполнено tn = (Т(0),..., Т(2™ — 1)).

Приведём здесь несколько первых членов этой последовательности: Т(0) = 0, Т(1) = 1, Т(2) = i Т(3) = -¿, Т(4) = i Т(5) = , Т(6) = Г(7) = Т(8) = i Т(9) = -I, Т(10) = Г(11) = |, Т( 12) = Т(13) = 1, Т( 14) = Т(15) = -§, т(16) = i, ....

Определение 2. Определяем перестановку Туэ-Морса т = (N U {0}, ^ , где х <т у тогда и только тогда, когда Т(х) ^ Т(у).

Теорема. Неравенства T(i) < T(j) и Rw{i) < Rw{j) выполнены или не выполнены одновременно. В частности, определения 1 и 2 эквивалентны.

В главе 5 исследуются антимонотонные перестановки.

Идея конструкции состоит в следующем. При определении антимонотонной перестановки (NU {0}, <, d) будем мыслить себе, что на первом шаге все целые неотрицательные числа делятся на два множества по чётности. Договоримся, что наше отношение линейного порядка ■< между числами из разных множеств не зависит от выбора этих чисел, то есть -у(х, у) = у(:г,', у') при любых чётных х и х' и нечётных у и у', то есть либо все чётные числа больше (по линейному порядку всех нечётных, либо

наоборот — все нечётные числа больше всех чётных. Выберем какой-то из этих двух вариантов. На следующем шаге каждое из множеств аналогично разделим ещё на два и договоримся, что отношение линейного порядка < между числами из разных множеств зависит только от этих множеств, но не от выбранных элементов. И так далее. В конечном счёте, каждые два числа рано или поздно окажутся в разных множествах, и потому отношение между ними будет определено. Бесконечную перестановку, соответствующую построенному таким образом линейному порядку будем называть антимонотопной.

Перейдём к формальному определению.

Для целого неотрицательного числа х будем обозначать через (х)2 бесконечное слово над алфавитом {0,1}, соответствующее двоичному разложению числа х, записанному в обратном порядке. Другими словами,

х = Тл=о(хЫк) гДе (хЫк) <Е {0,1} - цифры двоичного разложения (причём понятно, что (х)2(к) = 0 для к > х).

Пусть задана произвольная функция I: {0,1}* -> {0,1}. По ней определим перестановку тгг на Ми {0}. Зафиксируем произвольные целые неотрицательные х и у, х ф у. Поскольку х ф у, то существует такое р, что (х)2[0,р - 1] = (у)2[0,Р - 1] и (х)2(р) ф (у)2(р). Положим

7ггг(х,у) = (х)2(р) © *((а02[О,р- 1]),

где © означает сложение по модулю 2. (Подразумевается, что при р - 0 под í стоит пустое слово А.)

Несложно доказать, что такое определение 7Х,(х,у) корректно задаёт перестановку 7г4.

Перестановку п будем называть антимонотонной, если существует такая функция что п = щ.

Одно из свойств антимонотонных перестановок состоит в том, что три числа х, у, г, образующие нетривиальную арифметическую прогрессию, не могут быть упорядочены в антимонотонной перестановке монотонно, то есть не может быть щ(х) < щ{у) < щ(2) и не может быть щ(х) > щ(у) > Это свойство рассматривалось в статье [17].

Теорема. Комбинаторная сложность антимонотонной перестановки 7Г( не зависит от I и равна

.ЛгДп) =

Больше того, последовательность графов Рози , (?/.) также не зависит от I и имеет следующий вид. Если п не является степенью двойки, то <7* (га) - цикл длины г^"!. Если же п = 2\ то в^п)

— цикл длины 2'\ в котором каждые две последовательные вершины, соединены двумя параллельными дугами.

Теорема. Максимальная шаблонная сложность антимонотонной перестановки не зависит от I и равна

Помимо арифметической сложности, рассмотрим ещё арифметическую сложность по нечётным разностям. Будем говорить, что перестановка £ длины п встречается в бесконечной перестановке 7г по ариметической прогрессии с нечётной разностью, если существует такое тп и такое нечётное ё, что £ = 1г{т + <1, т + 'Ы,..., т + пй}. Через а!ж (п) обозначим количество перестановок длины п, встречающихся в тг по арифметическим прогрессиям с нечётными разностями. Последовательность (о4(п))п^2 будем называть арифметической сложностью по нечётным разностям бесконечной перестановки п.

Теорема. Арифметическая сложность по нечётным разностям антимонотонной перестановки щ не зависит от f и равна

Теорема. Для арифметической сложности антимонотонных перестановок выполнены нижняя и верхняя оценки

где «4 (п) вычислено в предыдущей теореме. Причём обе оценки достигаются при некоторых t, то есть существует to, что a.nto(n) = a4t(n) при всех п > 2, и существует t-i, что аЖч (n) = 2п~1 при всех п > 2.

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

1. Thue А. Über unendliche Zeichenreihen // Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl. Christiana, 1906. pp. 1-22.

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

knt(n) = 2n'\

22h, если n = 2h + 1; 22h+1, если 2h + 2 ^ n ^ 2h+l;

OK а*» ^ 2"-\

3. Thue A. Probleme über Veränderungen 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.

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

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

15. Fon-Der-Fla,ass D., Frid A. On periodicity and low complexity of infinite permutations // in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb'05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings volume AE pp. 267-272.

16. 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.

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

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

19. Rauzy G. Suites à termes dans un alphabet fini // Séminaire de Théorie des nombres de Bordeaux, exposé 25. 1983. pp. 2501-2516.

20. 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.

21. 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.

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

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

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

25. 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.

26. Kamae T., Rao H. Maximal pattern complexity of words over I letters 11 European Journal of Combinatorics. 2006. Vol. 27, no. 1. pp. 125-137.

27. Kamae T., Salimov P. On maximal pattern complexity of some automatic words // Ergodic Theory and Dynamical Systems. 2031. Vol. 31, no. 5. pp. 1463-1470.

28. Kamae Т. Behavior of various complexity functions // Theoretical Computer Science. 2012. Vol. 420. pp. 36-47.

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

30. 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.

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

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

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

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

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

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

37. 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.

38. 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.

39. 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.

Публикации автора по теме диссертации

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

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

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

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

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

Макаров Михаил Александрович

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

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

Подписано в печать 17.09.2012. Формат 60x84 1/16. Усл. печ. л. 1,2. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ № 148.

Отпечатано в ООО «Омега Принт» 630090 Новосибирск, пр. Лаврентьева, 6

Введение

Глава 1. Перестановки, порождённые лексикографическим порядком на суффиксах слов

1.1. Конечные лексикографически допустимые перестановки

1.2. Биекция между допустимыми перестановками и регулярными языками

1.3. Бесконечные перестановки, порождённые универсальными словами

Глава 2. Перестановки Штурма

2.1. Определения и предварительные замечания

2.2. Комбинаторная сложность

2.3. Максимальная шаблонная сложность.

2.4. Обобщение на двумерный случай

2.5. Арифметическая сложность

2.6. Заключительные замечания

Глава 3. Перестановка удвоения периода

3.1. Предварительные определения.

3.2. Знаки и типы вершин.

3.3. Классификация к;-допустимых перестановок.

3.4. Бинарные влево перестановки

3.5. Странные перестановки.

3.6. Комбинаторная сложность

3.7. Технические леммы о «;-допустимых перестановках маленькой длины.

Глава 4. Перестановка Туэ-Морса.

4.1. Два определения.

4.2. Эквивалентность двух определений

4.3. Замечание о последовательностях Т(п) и #щ(п).

Глава 5. Антимонотонные перестановки.

5.1. Определение

5.2. Комбинаторная сложность и графы Рози.

5.3. Максимальная шаблонная сложность.

5.4. Арифметическая сложность

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

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

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

Слово Туэ-Морса т = 0110100110010110. может быть задано рекуррентно условиями ги(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, = 01101001, ., где и]п+1 = (р{и)п). Нетрудно доказать, что для любого п слово тп является префиксом слова иип+Следовательно, существует бесконечное слово т = 'ш(0)ъи(1)'ш{2). = 0110100110010110., что иоп = -ш(0). т(2п - 1) для каждого п. Это слово и называется словом Туэ-Морса. Слово удвоения периода ы = 010001010100. может быть задано рекуррентно условиями ио(2п— 1) = 0 и ги(2п) = 1 — т(п) для всех п ^ 1. Также оно является неподвижной точкой морфизма с^: 0 >— 0100,1^0101.

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

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

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

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

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

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

• и[1,£(и)] = щ

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

• К¡777,1, ^2] ¡7^15 т^] — и[т'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] = 18273645 и £„(18273645) = {0, 2,4, 6,.}.

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

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

Пусть у нас имеется бесконечная перестановка 7Г. Множество всех её под-перестановок обозначим через Тж и будем называть языком всех подпереста-новок перестановки 7г. Легко видеть, что этот язык является факторным, то есть вместе с любой перестановкой содержит все её подперестановки. Множество перестановок из Т^ длины п обозначим через ^(п) = П ¿>п, а его мощность обозначим через ^(п) = Другими словами, /„(п) — это количество различных подперестановок длины п в бесконечной перестановке 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{х,у) — 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) условимся называть окном длины п с дистанциями ., с£пх- Будем говорить, что конечное слово и длины п встречается в бесконечном слове ги по окну б, = (¿¿х,., с£пх), если существует такое ттг, что и = ъи(т 4- Д). .ги(т + Д-х), то есть что и{г) = и){т + Дх) при всех г € {1,., п}, где Д = О, Д = при

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

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

Пример 8. Для слова Туэ-Морса w = 01101001. имеем Rui 1) = 0,01101001., Ящ(2) = 0,1101001.Я№(3) = 0,101001.Яад(4) = 0,01001. Ясно, что Яш(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. Über 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 über Veränderungen 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 à termes dans un alphabet fini // Séminaire de Théorie des nombres de Bordeaux, exposé 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. Complexité et facteurs spéciaux // Bulletin of the Belgian Mathematical Society. 1997. Vol. 4, no. 1. pp. 67-88.

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