Избегание экспонент. Избегание экспоненты 2 над алфавитом размера 3.

Исполнительное резюме

Для трёхбуквенного алфавита экспонента \(2\) избегаема: существуют бесконечные слова без квадратов, то есть без факторов вида \(uu\), \(u\neq\varepsilon\). Это классический результат Аксель Туе. Одновременно точная граница повторяемости для трёхбуквенного алфавита равна [ RT(3)=\frac74, ] то есть существуют бесконечные слова, не содержащие факторов экспоненты \(>\frac74\), но никакое бесконечное трёхбуквенное слово не может избегать всех факторов экспоненты \(\ge \frac74\). Это результат Франсуаза Дежан; общая формула Дежан для всех размеров алфавита была окончательно доказана работами Джеймс Карри, Нарад Рамперсад и независимо Микаэль Рао. Для алфавита размера \(4\) порог равен \(7/5\), что доказал Жан-Жак Пансьо.

Для учебных задач по теме достаточно держать в голове четыре факта. Во-первых, квадратсвободность над \(\Sigma_3\) существует и задаётся явными морфическими и автоматными конструкциями. Во-вторых, квадратсвободность сильнее, чем «отсутствие экспоненты \(2\)», но слабее, чем \(7/4^+\)-свободность: квадратсвободное слово может содержать факторы экспоненты \(7/4\), \(9/5\), \(11/6\) и т. п., лишь бы не было экспоненты \(\ge 2\). В-третьих, для морфизмов над трёхбуквенным алфавитом есть эффективный критерий Максим Крошмор: морфизм квадратсвободен тогда и только тогда, когда он сохраняет квадратсвободность всех квадратсвободных слов длины \(5\). В-четвёртых, отсутствие квадратов в конечном слове проверяется алгоритмически вплоть до линейного времени.

Для трибуквенного алфавита полезно различать два типа конструкций. Первая — бесконечные квадратсвободные слова, например фиксированная точка морфизма [ 0\mapsto 012,\qquad 1\mapsto 02,\qquad 2\mapsto 1. ] Вторая — бесконечные \(7/4^+\)-свободные слова, например фиксированная точка 19-равномерного морфизма Дежан. Кроме того, известен более тонкий результат: для \(\Sigma_3\) конечный порог повторов совпадает с порогом Дежан, [ FRt(3)=RT(3)=\frac74, ] и существует бесконечное трёхбуквенное слово, у которого все факторы имеют экспоненту не более \(7/4\), а факторов экспоненты ровно \(7/4\) всего два, причём это минимально возможное число.

Базовые понятия

Пусть \(\Sigma\) — конечный алфавит, \(\Sigma^\ast\) — множество всех конечных слов над \(\Sigma\), \(\Sigma^\omega\) — множество бесконечных слов. Фактор слова \(x\) — это любой непрерывный блок символов, то есть слово \(v\), для которого \(x=uvz\) при некоторых словах \(u,z\). Периодом слова \(w=w[1..n]\) называется число \(p\ge 1\), для которого \(w[i]=w[i+p]\) при всех \(1\le i\le n-p\); наименьший период обозначают \(\operatorname{per}(w)\). Экспонента слова определяется формулой [ \exp(w)=\frac{|w|}{\operatorname{per}(w)}. ] Например, слово \(010\) имеет длину \(3\), период \(2\) и экспоненту \(3/2\). Критическая экспонента конечного или бесконечного слова \(x\) — это [ ce(x)=\sup{\exp(u): u \text{ — непустой конечный фактор }x}. ] Слово называется примитивным, если оно не является собственной степенью более короткого слова.

Для рационального \(\alpha>1\) слово \(w\) называется \(\alpha\)-степенью или \(\alpha\)-повтором, если [ w=x^m x', ] где \(x'\) — префикс слова \(x\), а \(|w|=\alpha|x|\). Если \(\alpha=2\), получаем квадрат \(xx\); если \(\alpha=3\), получаем куб \(xxx\); если \(\alpha\notin \mathbb Z\), говорят о дробной экспоненте. В стандартной нотации слово называется \(\alpha\)-свободным, если оно не содержит факторов экспоненты \(\ge \alpha\), и \(\alpha^+\)-свободным, если оно не содержит факторов экспоненты \(> \alpha\). Соответственно, квадратсвободность — это \(2\)-свободность.

Ниже — компактная таблица терминов.

Из определений немедленно следует полезная для задач лемма.

Лемма. Если слово квадратсвободно, то every его фактор тоже квадратсвободен; кроме того, любой его фактор имеет экспоненту \(<2\).

Доказательство. Если фактор \(v\) квадратсвободного слова содержит квадрат \(uu\), то тот же квадрат содержится и в исходном слове; противоречие. Теперь пусть фактор \(y\) имеет период \(p\) и \(|y|/p\ge 2\). Тогда первые \(2p\) символов слова \(y\) образуют квадрат \(zz\), где \(|z|=p\), что невозможно. Следовательно, \(\exp(y)<2\). \(\square\)

Эта лемма объясняет, почему квадратсвободность автоматически означает отсутствие экспоненты \(2\), но не означает отсутствие экспонент \(<2\). Например, квадратсвободное слово может содержать \(7/4\)-степени.

Теоремы и сравнительная картина

Теорема Туе. Над трёхбуквенным алфавитом существует бесконечное квадратсвободное слово. Эквивалентно: экспонента \(2\) избегаема над \(\Sigma_3\). Одновременно над двубуквенным алфавитом квадратсвободного бесконечного слова нет; в двоичном случае оптимальный порог равен \(RT(2)=2\), а бесконечные \(2^+\)-свободные слова существуют.

Теорема Дежан для трёх букв. [ RT(3)=\frac74. ] Точная формулировка: существует бесконечное трёхбуквенное слово, не содержащее факторов экспоненты \(>7/4\); но каждое бесконечное трёхбуквенное слово содержит фактор экспоненты \(\ge 7/4\). Следовательно, квадратсвободность возможна, но \(7/4\)-свободность для бесконечных трёхбуквенных слов невозможна.

Теорема Пансьо для четырёх букв. [ RT(4)=\frac75. ] В формулировке из аннотации статьи Пансьо: для четырёхбуквенного алфавита «наибольшие неизбежные повторения» в сколь угодно длинных словах имеют вид \(uvu\), где \(|uvu|=\frac75|uv|\). Это и есть точная граница \(7/5\).

Полная теорема Дежан. [ RT(n)= \begin{cases} 7/4,& n=3,\[2mm] 7/5,& n=4,\[2mm] n/(n-1),& n\neq 3,4. \end{cases} ] Значения \(RT(2),RT(3),RT(4)\) установлены работами Туе, Дежан и Пансьо соответственно; случаи \(5\le n\le 11\) доказал Jean Moulin Ollagnier, случаи \(12\le n\le 14\) — Mohammad-Noori и Currie, случаи \(n\ge 33\) — Arturo Carpi, \(n\ge 27\) — Currie и Rampersad, последние открытые случаи \(15\le n\le 26\) — Currie и Rampersad, независимо закрытые также Rao.

Теорема Бадкобех–Крошмора о конечном пороге повторов для \(\Sigma_3\). [ FRt(3)=RT(3)=\frac74. ] Более точно: существует бесконечное трёхбуквенное слово, все факторы которого имеют экспоненту \(\le 7/4\), причём факторов экспоненты ровно \(7/4\) только два; это минимально возможное число. Конструкция основана на 160-равномерном морфизме, переводящем четырёхбуквенное слово Дежан в трёхбуквенное.

Теорема Ошема. Существует экспоненциально много трёхбуквенных \(7/4^+\)-свободных слов конечной длины; это усиливает простое утверждение о существовании и показывает, что язык \(7/4^+\)-свободных слов над \(\Sigma_3\) очень велик.

Сравнение алфавитов размеров \(2,3,4\) удобно держать в виде таблицы.

Источники таблицы: общая формула и история доказательств — Currie–Rampersad и Rao; случай \(k=4\) — Pansiot; случай \(k=3\) — Dejean; случай квадратсвободности при \(k=3\) — Thue.

Ключевой логический вывод для темы «избегание экспоненты \(2\) над \(\Sigma_3\)» такой: факт существования бесконечных квадратсвободных слов решает задачу избегания ровно экспоненты \(2\), а факт \(RT(3)=7/4\) описывает уже более тонкую границу для всех дробных экспонент. Поэтому ответ на вопрос «избегается ли \(2\)?» — да, а ответ на вопрос «какова точная минимальная неизбежная экспонента?» — \(7/4\).

Конструкции слов над трёхбуквенным алфавитом

Классическая квадратсвободная конструкция — фиксированная точка морфизма [ h(0)=012,\qquad h(1)=02,\qquad h(2)=1. ] Её фиксированная точка [ H=h^\omega(0)=012021012102012021020121\cdots ] называется словом Туе над тремя буквами; в литературе встречается также обозначение \(vtm\), и это слово квадратсвободно. В эквивалентной переобозначенной форме встречается также [ 2102012101202102012021\cdots, ] получаемое из \(H\) перестановкой букв; показано, что этот же объект задаётся конечным автоматом по двоичной записи индекса, то есть конструкция одновременно морфическая и автоматная.

Первые итерации морфизма \(h\) выглядят так: [ 0,\quad 012,\quad 012021,\quad 012021012102,\quad 012021012102012021020121,\ldots ] Каждый префикс этого бесконечного слова квадратсвободен; следовательно, для каждой длины \(n\ge 0\) существует конечное трёхбуквенное квадратсвободное слово длины \(n\). Это сразу решает типовые задачи на конструкцию конечных примеров.

Стандартный короткий способ доказать квадратсвободность этой конструкции опирается на критерий Крошмора: морфизм \(\alpha:\Sigma_3^\ast\to\Delta^\ast\) квадратсвободен тогда и только тогда, когда образы всех квадратсвободных слов длины \(5\) квадратсвободны. Для морфизма \(h\) это конечная проверка по всем квадратсвободным словам длины \(5\); после неё следует, что \(h\) — квадратсвободный морфизм, а потому все итераты \(h^n(0)\) квадратсвободны, и их предел \(H\) тоже квадратсвободен.

Для точного порога \(RT(3)=7/4\) нужна более сильная конструкция. Дежан использует 19-равномерный морфизм [ \delta(a)=abcacbcabcbacbcacba, ] [ \delta(b)=bcabacabcacbacabacb, ] [ \delta(c)=cabcbabcabacbabcbac. ] Фиксированная точка \(\delta^\omega(a)\) является \(7/4^+\)-свободной. Это даёт верхнюю оценку \(RT(3)\le 7/4\); нижняя оценка \(RT(3)\ge 7/4\) доказывается отдельным аргументом Дежан, и вместе они дают точное равенство \(RT(3)=7/4\). Морфизм удобен для задач на построение \(7/4^+\)-свободных примеров: любой длинный префикс \(\delta^\omega(a)\) годится.

Чтобы не путать два уровня утверждений, полезен конкретный контрпример к неверной импликации «квадратсвободность \(\Rightarrow 7/4^+\)-свободность». В квадратсвободном слове \(H\) встречается фактор \(2101210\), у которого длина \(7\), период \(4\), а значит экспонента равна \(7/4\). Следовательно, квадратсвободное слово может содержать предельные повторы экспоненты \(7/4\), хотя квадратов в нём нет. Это именно та причина, по которой факт существования квадратсвободных слов не противоречит равенству \(RT(3)=7/4\).

Схема доказательства равенства \(RT(3)=7/4\) выглядит так.

Полные доказательства обеих половин теоремы Дежан занимают статью; для учебных задач обычно достаточно знать именно эту декомпозицию: верхняя оценка идёт от явного морфизма, нижняя — от неизбежности \(7/4\)-степеней.

Проверка отсутствия экспоненты 2 и алгоритмические методы

Для конечного слова \(w\) длины \(n\) проверка квадратсвободности сводится к поиску индексов \(i\) и длины \(p\ge 1\), для которых [ w[i..i+p-1]=w[i+p..i+2p-1]. ] Самый прямой перебор всех \(i,p\) с посимвольным сравнением двух блоков работает за \(O(n^3)\). Если сравнение блоков ускорять хешами, \(Z\)-функцией, LCP-структурами или суффиксным массивом, то естественный перебор пар \((i,p)\) снижает время до \(O(n^2)\). Это хороший практический подход для ручных и небольших вычислений.

Для теоретически оптимальных оценок используются классические алгоритмы репетиций. Крошмор дал линейный алгоритм для поиска квадрата в слове; значит, решение задачи «есть квадрат / нет квадрата» возможно за \(O(n)\). Main–Lorentz дали алгоритм поиска всех повторов за \(O(n\log n)\). Позднее были получены линейные алгоритмы для всех tandem repeats (то есть квадратов) через суффиксные деревья и связанные структуры. Следовательно, квадратсвободность конечного слова проверяется в \(O(n)\) в стандартных строковых моделях вычислений.

Для морфических конструкций важен отдельный метод. Если слово задано как фиксированная точка морфизма, то часто не нужно искать квадраты во всё более длинных префиксах. Вместо этого проверяют сам морфизм. Над \(\Sigma_3\) действует точная теорема Крошмора: морфизм квадратсвободен тогда и только тогда, когда образы всех квадратсвободных слов длины \(5\) квадратсвободны. Поэтому доказательства квадратсвободности морфических слов обычно строятся именно так: конечный тест на ограниченном наборе образцов \(\Rightarrow\) квадратсвободность морфизма \(\Rightarrow\) квадратсвободность фиксированной точки.

Для задач на дробные экспоненты вместо проверки только квадратов используют тот же общий принцип, но отслеживают слова с \(\exp(w)>\beta\). В статье Ошема введена удобная нотация \((\beta^+,n)\)-свободности и доказана общая лемма, позволяющая проверять \(\beta^+\)-свободность образов длинных слов через конечный набор коротких \(\alpha^+\)-свободных тестов. Именно такие результаты делают возможными компьютерно-проверяемые морфические доказательства для порогов типа \(7/4\) и \(7/5\).

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

Источники для последних двух строк — Crochemore, Main–Lorentz и последующие алгоритмы tandem repeats.

Типовые задачи и упражнения с решениями

Типовые задачи

Задача. Каков минимальный размер алфавита, над которым существует бесконечное слово без экспоненты \(2\)?

Решение. Это число равно \(3\). Для \(2\) букв квадратсвободное бесконечное слово невозможно, поскольку \(RT(2)=2\). Для \(3\) букв бесконечное квадратсвободное слово существует по теореме Туе. Значит, минимальный размер алфавита — ровно \(3\).

Задача. Построить квадратсвободное трёхбуквенное слово длины \(n\).

Решение. Достаточно взять префикс длины \(n\) слова [ H=012021012102012021020121\cdots=h^\omega(0), \quad h(0)=012,\ h(1)=02,\ h(2)=1. ] Поскольку \(H\) квадратсвободно, любой его префикс квадратсвободен. Например, для \(n=12\) получаем [ 012021012102. ] Для \(n=24\) получаем [ 012021012102012021020121. ]

Задача. Объяснить, почему существование бесконечного квадратсвободного слова над \(\Sigma_3\) не противоречит равенству \(RT(3)=7/4\).

Решение. Квадратсвободность запрещает только факторы экспоненты \(\ge 2\). Порог \(RT(3)=7/4\) говорит о невозможности избежать всех факторов экспоненты \(\ge 7/4\). Эти утверждения совместимы, потому что в квадратсвободном слове могут появляться факторы с экспонентой между \(7/4\) и \(2\). Например, в слове \(H\) встречается фактор \(2101210\) экспоненты \(7/4\), но квадратов в \(H\) нет.

Задача. Доказать, что если морфизм \(h:\Sigma_3^\ast\to\Sigma_3^\ast\) квадратсвободен и \(a\in\Sigma_3\), то каждая итерация \(h^m(a)\) квадратсвободна.

Решение. По определению квадратсвободного морфизма образ любого квадратсвободного слова квадратсвободен. Буква \(a\) квадратсвободна. Значит, \(h(a)\) квадратсвободно. Далее по индукции: если \(h^m(a)\) квадратсвободно, то \(h^{m+1}(a)=h(h^m(a))\) тоже квадратсвободно. \(\square\)

Задача. Как теоретически проверять квадратсвободность очень длинного конечного слова?

Решение. Теоретически оптимальный ответ: использовать линейный алгоритм поиска квадратов или линейный алгоритм перечисления tandem repeats. Альтернатива — Main–Lorentz за \(O(n\log n)\), если нужен весь набор повторов. Для морфически заданных слов проще проверять не готовый префикс, а сам морфизм по критерию Крошмора.

Упражнения с решениями

Упражнение. Найти экспоненту слова \(2101210\).

Решение. У слова длина \(7\). Оно \(4\)-периодично, потому что [ 2101210 = 2101\cdot 210, ] и префикс длины \(3\) дописывает период \(2101\). Наименьший период равен \(4\), следовательно, [ \exp(2101210)=\frac74. ]

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

Решение. Если фактор содержит квадрат \(uu\), то тот же квадрат содержится и в исходном слове. Противоречие. \(\square\)

Упражнение. Верно ли, что всякое квадратсвободное слово является \(7/4^+\)-свободным?

Решение. Нет. Квадратсвободность запрещает только экспоненты \(\ge 2\). Фактор \(2101210\) показывает, что экспонента \(7/4\) может встречаться в квадратсвободном слове.

Упражнение. Почему из существования бесконечного квадратсвободного слова следует существование квадратсвободных слов любой конечной длины?

Решение. Любой префикс бесконечного квадратсвободного слова квадратсвободен. Для заданной длины \(n\) берём префикс длины \(n\). \(\square\)

Упражнение. Сколько букв нужно проверить в теореме Крошмора для морфизма над \(\Sigma_3\)?

Решение. Не длину образов, а длину тестовых входных слов: достаточно проверить все квадратсвободные слова длины \(5\). Это и есть точная формулировка критерия Крошмора.

Упражнение. Чем отличаются \(2\)-свободность и \(2^+\)-свободность?

Решение. \(2\)-свободность запрещает все факторы экспоненты \(\ge 2\), то есть в частности квадраты. \(2^+\)-свободность запрещает только экспоненты \(>2\); квадратов экспоненты ровно \(2\) она не исключает. Поэтому двоичное перекрытие-свободное слово может быть \(2^+\)-свободным, но не квадратсвободным.

Упражнение. Какой морфизм удобно использовать для построения \(7/4^+\)-свободных слов над \(\Sigma_3\)?

Решение. Морфизм Дежан [ a\mapsto abcacbcabcbacbcacba,\quad b\mapsto bcabacabcacbacabacb,\quad c\mapsto cabcbabcabacbabcbac. ] Его фиксированная точка \(7/4^+\)-свободна.

Самая важная практическая связка для решения задач такова. Если задача требует лишь «избежать экспоненты \(2\)», достаточно строить квадратсвободное слово Туе \(H=h^\omega(0)\). Если задача требует работать на границе Дежан, нужно переходить к \(7/4^+\)-свободным конструкциям. Если задача алгоритмическая, квадратсвободность конечного слова проверяется поиском квадратов, а квадратсвободность морфической конструкции — конечным тестом на уровне морфизма. Это покрывает подавляющее большинство учебных задач по теме.