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

Краткое резюме. В стандартной терминологии комбинаторики слов запись \(2^+\) означает любой показатель строго больше 2. Для бинарного алфавита это принципиально важно: бесконечные бинарные слова, избегающие всех показателей \(>2\), существуют; классический пример — слово Thue–Morse. Но бесконечных бинарных слов, избегающих показателя \(2\) как такового, не существует: квадратсвободное бинарное слово не может иметь длину \(\ge 4\). Следовательно, над алфавитом размера \(2\) возможно избегать \(>2\), но невозможно избегать \(\ge 2\).

Для порогов повторяемости точные значения таковы: \(RT(2)=2\), \(RT(3)=7/4\), \(RT(4)=7/5\), а по теореме Dejean для всех \(k\ge 5\) выполнено \(RT(k)=k/(k-1)\). Критический показатель слова Thue–Morse равен \(2\): в нём есть квадраты, но нет факторов с показателем \(>2\). Это и есть оптимум для бинарных бесконечных слов.

Определения

Пусть \(w\) — непустое конечное слово. Число \(p\ge 1\) называется периодом слова \(w\), если для всех допустимых \(i\) выполнено \(w*i=w*{i+p}\). Наименьший период обозначим \(p(w)\). Тогда показатель (exponent) слова \(w\) определяется формулой [ \exp(w)=\frac{|w|}{p(w)}. ] Эквивалентно, \(w\) можно записать в виде \(w=x^n x'\), где \(x'\) — префикс слова \(x\), и тогда [ \exp(w)=n+\frac{|x'|}{|x|}. ] Поскольку \(|w|\) и \(p(w)\) целые, показатели конечных слов всегда рациональны.

Слово называется степенным или \(\alpha\)-степенью (\(\alpha\)-power), если его показатель равен \(\alpha\). Например, [ 01010=(01)^{5/2},\qquad \exp(01010)=\frac52. ] Стандартные специальные случаи: показатель \(2\) — квадрат, показатель \(3\) — куб. Для вещественного \(\alpha>1\) слово называется \(\alpha\)-повтором, если содержит фактор показателя \(\ge \alpha\), и \(\alpha^+\)-повтором, если содержит фактор показателя \(>\alpha\). Соответственно, слово называется \(\alpha\)-свободным (\(\alpha\)-free), если не содержит факторов показателя \(\ge \alpha\), и \(\alpha^+\)-свободным (\(\alpha^+\)-free), если не содержит факторов показателя \(>\alpha\). В этом пособии именно это соглашение используется всюду.

Наложением (overlap) называется слово вида \(axaxa\), где \(a\) — буква, \(x\) — произвольное слово, возможно пустое. Его показатель равен [ \frac{2|x|+3}{|x|+1}=2+\frac{1}{|x|+1}>2. ] Поэтому каждое наложение есть \(2^+\)-повтор. Обратно, если слово имеет показатель \(>2\), то оно имеет вид \(yyz\), где \(z\) — непустой префикс \(y\); если записать \(y=au\), то префикс длины \(2|y|+1\) равен \(auaua\), то есть содержит наложение. Следовательно, [ \text{overlap-free}\iff 2^+\text{-free}. ] Это основной факт для бинарного случая.

Пусть \(F\) — семейство запрещённых факторов или паттернов. Говорят, что \(F\) \(k\)-избегаемо, если существует бесконечное слово над \(k\)-буквенным алфавитом, не содержащее ни одного элемента из \(F\). Для повторов это приводит к понятию порога повторяемости [ RT(k)=\inf{\alpha>1:\ \exists\ \text{бесконечное }k\text{-арное слово, являющееся }\alpha^+\text{-free}}. ] Иначе говоря, \(RT(k)\) — наименьший достижимый сверху порог избегания строгих показателей.

Для бесконечного слова \(u\) его критический показатель определяется как [ E(u)=\sup{\exp(v):\ v\text{ — фактор }u}. ] Равносильно, [ E(u)=\inf{\beta:\ u\text{ является }\beta^+\text{-free}}. ] Из определений сразу следует [ RT(k)=\inf{E(u):\ u\in \Sigma_k^{\mathbb N}}. ] То есть порог Dejean — это минимально возможный критический показатель бесконечного слова над данным алфавитом.

Теоремы и доказательства

Бинарные квадраты неизбежны

Теорема. Бесконечного бинарного \(2\)-free слова не существует. Более того, любое бинарное квадратсвободное слово имеет длину не больше \(3\).

Доказательство. Пусть \(w=w*1w*2w*3w*4\) — бинарное слово длины \(4\), не содержащее квадратов. Тогда, в частности, в нём нет факторов \(00\) и \(11\), значит соседние буквы обязаны чередоваться. Следовательно, \(w\) равно либо \(0101\), либо \(1010\). Но это квадрат слова длины \(2\). Противоречие. Значит, бинарного квадратсвободного слова длины \(4\) нет, следовательно, бесконечного тоже нет. ∎

Эта теорема отвечает на часть пользовательского уточнения: избегание показателя ровно \(2\) на бинарном алфавите невозможно. Следовательно, невозможно и избегание всех показателей \(\ge 2\).

Теорема Thue для бинарного алфавита

Пусть \(\mu\) — морфизм Thue–Morse: [ \mu(0)=01,\qquad \mu(1)=10. ] Его неподвижная точка [ t=\mu^\omega(0)=0110100110010110\cdots ] называется словом Thue–Morse. Thue доказал, что \(t\) не содержит наложений, то есть является overlap-free; по лемме выше это эквивалентно \(2^+\)-free.

Схема доказательства. База: слово \(0\) наложений не содержит. Ключевая лемма: если \(\mu(w)\) содержит наложение, то после «декодирования» блоков \(01\mapsto 0\), \(10\mapsto 1\) получается наложение уже в \(w\). Причина в том, что все образы букв имеют длину \(2\), а паритет начала и периода наложения вынуждает его границы совпадать с границами блоков \(\mu(a)\). Значит, \(\mu\) сохраняет overlap-freeness. Отсюда по индукции каждое \(\mu^n(0)\) overlap-free, а значит и предел \(t\) overlap-free. ∎

Следствие для порога \(2^+\)

Из предыдущих двух теорем получаем точную бинарную дихотомию:

• бесконечные бинарные \(2\)-free слова не существуют;
• бесконечные бинарные \(2^+\)-free слова существуют.

Следовательно, [ RT(2)=2. ] Это точная бинарная форма теоремы Thue–Dejean. Именно это значение требуется понимать под «избеганием экспоненты \(2^+\) над алфавитом размера \(2\)».

Критический показатель слова Thue–Morse

Слово \(t\) содержит квадраты, например \(00\). Так как \(t=\mu(t)\), из любого фактора \(v\) слова \(t\) следует фактор \(\mu^n(v)\) для любого \(n\). Поэтому из фактора \(00\) получаем бесконечно много квадратов \(\mu^n(00)\) возрастающих длин. С другой стороны, \(t\) overlap-free, то есть не имеет факторов показателя \(>2\). Значит, [ E(t)=2. ] Это не только вычисление критического показателя \(t\), но и конструктивное доказательство оптимальности бинарного порога \(RT(2)=2\).

Более сильный факт: все квадраты в \(t\) описаны точно. Они ровно равны словам вида [ \mu^k(00),\ \mu^k(11),\ \mu^k(010010),\ \mu^k(101101)\qquad (k\ge 0). ] Это описание удобно для задач на распознавание квадратов в слове Thue–Morse.

Теорема Dejean

Теорема Dejean. [ RT(2)=2,\qquad RT(3)=\frac74,\qquad RT(4)=\frac75,\qquad RT(k)=\frac{k}{k-1}\ \text{для }k\ge 5. ] Значения для \(k=2,3,4\) были установлены соответственно Thue, Dejean и Pansiot; общий случай был завершён работами по большим алфавитам и последним оставшимся диапазонам \(k\).

Что именно доказано для малых алфавитов. Для \(k=3\) Dejean построила бесконечное слово критического показателя \(7/4\) и доказала, что меньший порог невозможен. Для \(k=4\) Pansiot доказал точное значение \(7/5\). Для \(k\ge 5\) современная схема доказательства основана на кодировании Pansiot, редукции к конечной проверке специальных «kernel repetitions» и компьютерной верификации конечного числа случаев; крупные диапазоны закрыл Carpi, затем оставшиеся диапазоны — работы 2009–2011 годов.

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

Конструкции

Морфизмы и морфические слова

Морфизмом называется отображение \(h:A^\*\to B^\*\), сохраняющее конкатенацию: \(h(uv)=h(u)h(v)\). Морфизм называется равномерным, если все \(|h(a)|\) одинаковы. Если \(h(a)=ax\) для некоторой буквы \(a\), то существует неподвижная точка [ h^\omega(a)=a\,x\,h(x)\,h^2(x)\cdots, ] называемая морфическим словом или словом, заданным итерацией морфизма. Это основной конструктивный механизм во всей теории избегания повторов.

Бинарная конструкция Thue–Morse

Основная конструкция для темы \(2^+\) над бинарным алфавитом: [ \mu(0)=01,\qquad \mu(1)=10,\qquad t=\mu^\omega(0). ] Первые итерации: [ 0,\quad 01,\quad 0110,\quad 01101001,\quad 0110100110010110. ] Предел \(t\) бинарен, \(2\)-автоматичен, морфичен, \(2^+\)-free и имеет критический показатель \(2\). Его дополнение \(\overline t=\mu^\omega(1)\) обладает теми же свойствами. Любой суффикс \(t[n..]\) и \(\overline t[n..]\) также является \(2^+\)-free, так как свойство избегания определяется по факторам.

Для задач полезно помнить ещё два точных свойства слова \(t\). Во-первых, оно содержит бесконечно много квадратов всех длин из семейства \(2^{m+1}\) и \(6\cdot 2^m\), поскольку \(00\) и \(010010\) встречаются в \(t\), а применение \(\mu^m\) к фактору сохраняет факторность в неподвижной точке. Во-вторых, все квадраты в \(t\) описываются ровно четырьмя морфическими семействами, указанными выше.

Полное описание всех бинарных overlap-free слов

Существует конечный автомат, который даёт полное описание всех бесконечных бинарных overlap-free слов. Иначе говоря, бинарные \(2^+\)-free слова не только существуют, но и образуют класс, допускающий конечное автоматное параметрическое описание. Для учебных задач это означает, что вопрос «какие вообще существуют бесконечные бинарные \(2^+\)-free слова?» имеет конечное алгоритмическое решение, а Thue–Morse — лишь центральный, но не единственный пример.

С более сильной стороны верно и обратное ограничение: среди бесконечных бинарных слов, получаемых именно как неподвижные точки итерации морфизма, overlap-free фиксированных точек по существу только две — \(t\) и \(\overline t\). Это объясняет, почему в бинарной теме конструкция Thue–Morse появляется практически во всех точных утверждениях.

Полезные небинарные ориентиры

Хотя тема пособия бинарная, для понимания таблиц \(k=2,3,4\) нужны ещё две классические конструкции.

Тернарное квадратсвободное слово можно получить как неподвижную точку морфизма [ h(0)=012,\qquad h(1)=02,\qquad h(2)=1. ] Это классическая квадратсвободная конструкция Thue–Hall.

Для точного тернарного порога \(7/4\) Dejean использовала 19-равномерный морфизм; в одной из стандартных учебных форм он задаётся так: [ \varphi(0)=0120212012102120210, ] [ \varphi(1)=1201020120210201021, ] [ \varphi(2)=2012101201021012102. ] Его неподвижная точка имеет критический показатель \(7/4\). Для \(k=4\) точное значение \(7/5\) достигается в конструкции Pansiot, но она уже существенно менее элементарна, чем морфизм Thue–Morse.

Алгоритмы проверки

Проверка конечного слова

Для конечного слова \(w\) проверка на наличие фактора показателя \(>\alpha\) при \(\alpha\ge 2\) естественно сводится к поиску максимальных повторов (runs). Run — это максимальный по включению периодический отрезок с периодом \(p\) и длиной не меньше \(2p\). Любой фактор показателя \(\ge 2\) можно расширить с сохранением периода до некоторого run, поэтому для проверки \(\alpha^+\)-свободы достаточно перебрать все runs и посчитать их показатели.

Современный базовый результат: все runs в слове длины \(n\) можно перечислить за линейное время, а их число строго меньше \(n\). Это даёт линейный алгоритм проверки \(\alpha^+\)-свободы конечного слова при \(\alpha\ge 2\). В частном случае \(\alpha=2\) это линейная проверка квадратсвободы; в случае \(\alpha=2^+\) — линейная проверка overlap-freeness.

Практическая схема:

Input: word w, threshold α ≥ 2
1. Enumerate all runs r=(l, r, p) in w
2. For each run compute exponent e = (r-l+1)/p
3. If some run has e > α, return "not α+-free"
4. Otherwise return "α+-free"

Корректность следует из того, что любой фактор показателя \(> \alpha \ge 2\) лежит внутри некоторого run того же периода.

Специализированные алгоритмы для overlap-free слов

Для overlap-free слов существуют и более тонкие процедуры. Известен линейный алгоритм, вычисляющий максимальный показатель всех факторов overlap-free слова. Это особенно полезно, когда вход гарантированно принадлежит классу \(2^+\)-free, а требуется анализировать допустимые квадраты и близкие к порогу факторы.

Проверка морфизмов по конечному тесту

Для конструктивных доказательств часто нужно проверить, что морфизм сохраняет бесквадратность или другой класс избегания. Классический критерий Crochemore таков: если морфизм равномерный, то для квадратсвободы достаточно проверить образы всех квадратсвободных слов длины \(3\); на трёхбуквенном алфавите в общем случае достаточно длины \(5\). Это превращает бесконечную проверку «морфизм сохраняет свойство» в конечный вычислимый тест.

Автоматные и логические методы для бесконечных слов

Если бесконечное слово автоматически задано, как слово Thue–Morse, то критический показатель можно вычислить алгоритмически. Для \(k\)-автоматических слов он всегда либо рационален, либо бесконечен, и его значение вычислимо. Это даёт общий алгоритмический путь к сертификатам вида \(E(t)=2\).

Ещё сильнее: первая порядковая теория класса бинарных overlap-free слов разрешима; более общо, разрешима теория \(\alpha\)-free слов для рациональных \(2<\alpha\le 7/3\). Практический вывод: много утверждений о бинарном \(2^+\)-избегании можно доказывать автоматически как задачи решаемой логики. Именно так сегодня часто проверяют ограничения на факторы, допустимые показатели и существование морфизмов в системах типа Walnut.

Примеры и задачи с решениями

Задача с показателем

Найти показатель слова \(01010\) и определить, является ли оно квадратом, кубом или \(2^+\)-повтором.

Решение. Наименьший период равен \(2\): слово есть префикс бесконечного \((01)^\omega\). Поэтому [ \exp(01010)=\frac{5}{2}. ] Это не квадрат и не куб, но это \(2^+\)-повтор. Более того, \(01010=0\,1\,0\,1\,0=axaxa\) при \(a=0\), \(x=1\), то есть это наложение.

Задача о связи \(2^+\)-повторов и наложений

Доказать, что каждое слово показателя \(>2\) содержит наложение.

Решение. Пусть \(w=yyz\), где \(z\) — непустой префикс \(y\). Запишем \(y=au\), тогда \(z\) начинается с буквы \(a\). Следовательно, префикс слова \(w\) длины \(2|y|+1\) имеет вид [ au\,au\,a=axaxa. ] Значит, \(w\) содержит наложение. Отсюда сразу: [ 2^+\text{-free}\iff \text{overlap-free}. ]

Задача о невозможности квадратсвободы

Найти максимальную длину бинарного квадратсвободного слова.

Решение. Длина \(3\) достижима: подходят \(010\) и \(101\). Длина \(4\) невозможна: если избегать \(00\) и \(11\), то буквы обязаны чередоваться, а тогда получается \(0101\) или \(1010\), то есть квадрат. Следовательно, максимум равен \(3\).

Задача о больших квадратах в слове Thue–Morse

Пусть \(t=\mu^\omega(0)\), \(\mu(0)=01\), \(\mu(1)=10\). Доказать, что \(t\) содержит бесконечно много квадратов.

Решение. Фактор \(00\) встречается в \(t\). Так как \(t=\mu(t)\), то если фактор \(v\) встречается в \(t\), то и \(\mu^n(v)\) встречается в \(t\) для любого \(n\). Но [ \mu^n(00)=\mu^n(0)\mu^n(0), ] то есть квадрат длины \(2^{n+1}\). Следовательно, в \(t\) есть квадраты сколь угодно больших длин.

Задача о критическом показателе слова Thue–Morse

Найти \(E(t)\).

Решение. По предыдущей задаче в \(t\) есть квадраты, следовательно, \(E(t)\ge 2\). По теореме Thue слово \(t\) overlap-free, а значит \(2^+\)-free, следовательно, никакого фактора с показателем \(>2\) в нём нет. Итак, [ E(t)=2. ]

Задача о бинарном пороге Dejean

Доказать, что \(RT(2)=2\).

Решение. Нижняя оценка: бесконечного бинарного \(2\)-free слова нет. Верхняя оценка: слово Thue–Morse бесконечно и \(2^+\)-free. Значит, точное значение порога равно \(2\).

Задача на run-проверку

Проверить, является ли слово \(001100110\) \(2^+\)-free.

Решение. Наименьший период слова равен \(4\): блок \(0011\) повторяется дважды и ещё берётся префикс длины \(1\). Поэтому [ \exp(001100110)=\frac{9}{4}>2. ] Значит, слово не является \(2^+\)-free. В run-терминах это один максимальный повтор с периодом \(4\) и показателем \(9/4\).

Упражнения

Без решений.

1. Доказать, что слово \(axaxa\) имеет показатель \(2+\frac{1}{|x|+1}\).
2. Проверить, что единственные бинарные квадратсвободные слова максимальной длины — \(010\) и \(101\).
3. Построить первые \(32\) символа слова \(t=\mu^\omega(0)\).
4. Доказать, что любой суффикс overlap-free слова снова overlap-free.
5. Найти показатель слова \(0010010\).
6. Вывести из теоремы Dejean, можно ли на тернарном алфавите избегать всех показателей \(>5/3\).
7. Показать, что \(2^+\)-free слово обязательно кубсвободно.
8. Используя описание квадратов в \(t\), выписать первые пять различных квадратов, встречающихся в слове Thue–Morse.
9. Проверить по критерию Crochemore, является ли данный равномерный морфизм квадратсохраняющим.
10. Сформулировать в логике первого порядка свойство «в слове существует квадрат периода \(p\)».

Таблицы и диаграммы

Сравнение результатов для алфавитов размеров \(2,3,4\)

Эта таблица сводит точные результаты Thue, Dejean и Pansiot для малых алфавитов и общий смысл порога повторяемости. Для бинарного случая особенно важно различать «\(2\)-free» и «\(2^+\)-free»: в первой колонке ответ отрицательный, во второй — положительный.

Таблица ключевых конструкций и свойств

Сводка опирается на классические конструкции и на полное автоматное описание бинарного overlap-free класса. Для языка задач центральной является первая строка: именно \(t\) даёт конструктивное бинарное \(2^+\)-избегание.

Диаграмма связей между понятиями

Диаграмма отражает стандартную логическую цепочку: период \(\to\) показатель \(\to\) запрещённые степени \(\to\) критический показатель \(\to\) порог повторяемости. В бинарном случае узел \(2^+\)-free совпадает с overlap-free.

Временная шкала основных результатов

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

Ссылки

Первоисточники

• Über unendliche Zeichenreihen (1906) — исходная работа, где появляются бесконечные слова без квадратов.
• Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen (1912) — исходная работа по бинарным overlap-free словам.
• Sur un théorème de Thue (1972) — первоисточник точного значения \(RT(3)=7/4\) и общей гипотезы Dejean.
• À propos d'une conjecture de F. Dejean sur les répétitions dans les mots (1984) — первоисточник точного значения \(RT(4)=7/5\).
• Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters (1992) — закрытие диапазона \(5\le k\le 11\).
• On Dejean's conjecture over large alphabets (2007) — крупный шаг: все \(k\ge 33\).
• Dejean's conjecture holds for \(N\ge 27\) (2009) — следующий крупный диапазон.
• A proof of Dejean's conjecture (2009/2011) — закрытие последних случаев \(15\le n\le 26\).
• Last cases of Dejean's conjecture (2011) — окончательное завершение оставшихся случаев.
• Squares and overlaps in the Thue-Morse sequence and some variants (2006) — точные сведения о квадратах в слове Thue–Morse.
• The “Runs” Theorem (2015/2017) — основной современный источник по линейному перечислению runs.
• The Critical Exponent is Computable for Automatic Sequences (2011) — вычислимость критического показателя для автоматических слов.
• The First-Order Theory of Binary Overlap-Free Words is Decidable (2022) — разрешимость логической теории бинарных overlap-free слов.

Обзорные и учебные материалы

• The origins of combinatorics on words (2007) — краткий исторический обзор возникновения дисциплины.
• Overlap-Free Words and Generalizations (2007) — подробное англоязычное изложение бинарной overlap-free и \(7/3\)-free тематики.
• Русскоязычное учебное пособие Комбинаторика слов (2003) — компактный вводный курс по терминологии и базовым техникам.
• Русскоязычный открытый курс Комбинаторика слов и её приложения — серия лекций, в том числе по повторам, overlap-free и алгоритмам.