Избегание экспонент. Теорема Дежан (без доказательства).

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

Предположение для этого пособия: речь идет о стандартной теореме Дежан в комбинаторике слов. Именно в этом контексте в литературе используются выражения «избегание экспонент», «избегаемые дробные степени», «порог повторов» и обозначение \(RT(k)\). Поэтому ниже экспонента означает экспоненту слова/повтора, а не экспоненту группы; перечисленные в запросе термины из теории групп \(p\)-группа, квазицентр, нормальная серия, класс нильпотентности и т. п. к стандартной теореме Дежан не относятся. Предполагаемый уровень — старший бакалавриат / магистратура; предполагаемый объём — компактное пособие примерно на 6–12 страниц эквивалента.

Главный результат темы таков: для алфавита мощности \(k\) точный порог повторов равен [ RT(k)= \begin{cases} 2,& k=2,\[2mm] \frac74,& k=3,\[2mm] \frac75,& k=4,\[2mm] \frac{k}{k-1},& k\ge 5. \end{cases} ] Эквивалентно: существует бесконечное слово над \(k\)-буквенным алфавитом, в котором нет факторов экспоненты строго больше \(RT(k)\), и ни для какого меньшего порога это уже невозможно. Это и есть современная формулировка теоремы Дежан.

Практическое применение почти всегда сводится к сравнению требуемого порога \(\beta\) с \(\tau=RT(k)\). Если \(\beta<\tau\), бесконечного \(\beta^+\)-свободного слова не существует. Если \(\beta>\tau\), существование бесконечного \(\beta\)-свободного слова гарантировано. Случай \(\beta=\tau\) требует аккуратности: теорема Дежан гарантирует \(\tau^+\)-свободность, но сама по себе не утверждает \(\tau\)-свободность. Эта тонкость реальна, а не формальна; именно поэтому в последующих работах отдельно изучается finite-repetition threshold. Завершающие доказательства бывшей гипотезы Дежан были получены независимо Дж. Карри с Н. Рамперсадом и М. Рао.

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

Пусть \(\Sigma_k=\{0,1,\dots,k-1\}\) — алфавит мощности \(k\ge2\). Слово — конечная или бесконечная последовательность символов из \(\Sigma_k\). Фактор слова — его непрерывное подслово. В задачах на теорему Дежан почти всегда рассматриваются именно бесконечные слова, а свойства проверяются по их конечным факторам.

Конечное непустое слово \(w\) имеет период \(p\), если \(w\) можно представить в виде \(w=x^n x'\), где \(x'\) — префикс слова \(x\), а \(p=|x|\). Наименьший такой период обозначают \(p(w)\) и считают основным периодом слова. Тогда экспонента слова определяется формулой [ \exp(w)=\frac{|w|}{p(w)}. ] Важно: одно и то же слово может иметь несколько периодов, но стандартная экспонента слова всегда считается по наименьшему периоду. Например, слово \(01010\) имеет основной период \(2\) и экспоненту \(5/2\).

Если \(\exp(w)=\alpha\), то говорят, что \(w\) — \(\alpha\)-степень или \(\alpha\)-power. В частности, квадрат — это \(2\)-степень, куб — \(3\)-степень. Слово называется \(\alpha\)-свободным (\(\alpha\)-free), если в нем нет факторов с экспонентой \(\ge \alpha\). Слово называется \(\alpha^+\)-свободным (\(\alpha^+\)-free), если в нем нет факторов с экспонентой \(>\alpha\). Это различие фундаментально: \(\alpha\)-free сильнее, чем \(\alpha^+\)-free.

Для бесконечного слова \(x\) его критическая экспонента \(E(x)\) — это супремум экспонент всех его конечных непустых факторов. При этом критическая экспонента может либо достигаться некоторым конечным фактором, либо быть только точной верхней гранью и не достигаться. Именно поэтому из равенства \(E(x)=\alpha\) нельзя автоматически заключить, что \(x\) не является \(\alpha\)-свободным; зато всегда верно, что \(E(x)\le \alpha\) эквивалентно \(\alpha^+\)-свободности.

Порог повторов \(RT(k)\) — это наименьшее вещественное \(\alpha>1\), для которого существует бесконечное слово над \(k\)-буквенным алфавитом, избегающее всех повторов экспоненты строго выше \(\alpha\). В литературе встречаются и обозначения \(\alpha(k)\), и формулировка через infimum; по содержанию это одно и то же понятие.

Связи между основными понятиями удобно держать в голове так.

Теорема Дежан и варианты формулировки

Стандартная «формула порога» имеет вид [ RT(k)=\frac{k}{k-1}\quad\text{для всех }k\ge2,\ k\ne3,4, ] с двумя исключениями [ RT(3)=\frac74,\qquad RT(4)=\frac75. ] Эквивалентно можно писать просто полную покомпонентную формулу, приведенную в резюме.

Для практики полезно держать рядом три эквивалентные формулировки.

Таблица выше непосредственно следует из определения порога повторов, различия между \(\alpha\)-free и \(\alpha^+\)-free, а также из окончательной формулы теоремы Дежан.

Исторически тема начинается с работ Аксель Туэ о бесконечных квадрат-свободных и overlap-free словах. Случай \(k=3\) установила Франсуаза Дежан в 1972 году, случай \(k=4\) — Жан-Жак Пансьо в 1984 году. Последние открытые случаи были независимо закрыты Джеймс Д. Карри вместе с Нарад Рамперсад и отдельно Микаэль Рао. В русскоязычных курсах по комбинаторике слов эту тему нередко называют также граничной теоремой.

Полезные факты и критерии применения

Для задач, где по двум периодам нужно быстро вычислить более короткий период, используется теорема Файна–Вильфа: если слово имеет периоды \(p\) и \(q\), а его длина не меньше \(p+q-\gcd(p,q)\), то \(\gcd(p,q)\) тоже является периодом. Это — основной инструмент для «схлопывания» двух периодов в один меньший.

Нужны и несколько простых, но важных следствий. Если фактор имеет экспоненту \(>1\), то он начинается и заканчивается одним и тем же непустым куском, то есть является bordered. Если слово \(\alpha\)-free, то оно автоматически \(\beta\)-free для любого \(\beta\ge\alpha\). Если слово \(\alpha^+\)-free, то оно автоматически \(\beta^+\)-free для любого \(\beta\ge\alpha\), а также \(\beta\)-free для любого \(\beta>\alpha\). Поэтому сравнение с \(RT(k)\) действительно полностью решает большинство вопросов вида «можно ли избежать экспоненты \(\beta\) на \(k\) буквах».

Самые полезные критерии применения таковы. Пусть \(\tau=RT(k)\). Тогда бесконечное \(\beta^+\)-свободное \(k\)-арное слово существует тогда и только тогда, когда \(\beta\ge\tau\). Для \(\beta\)-свободности ситуация чуть тоньше: при \(\beta<\tau\) такого слова нет, при \(\beta>\tau\) оно существует, а при \(\beta=\tau\) одной теоремы Дежан уже недостаточно. Эта оговорка не декоративна: последующие работы по finite-repetition threshold специально изучают, сколько раз в «пороговом» слове могут появляться факторы экспоненты ровно \(RT(k)\); например, для тернарного случая известно, что можно построить бесконечное слово, у которого таких факторов лишь конечное число.

Для критической экспоненты полезно помнить следующую схему. Если \(E(x)\le\beta\), то бесконечное слово \(x\) обязательно \(\beta^+\)-свободно. Если \(E(x)<\beta\), то \(x\) точно \(\beta\)-свободно. Но при \(E(x)=\beta\) надо отдельно проверять, достигается ли экспонента \(\beta\) фактором; Шаллит прямо отмечает, что рациональная критическая экспонента может быть как достигаемой, так и недостижимой.

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

Задача A. Найти наименьший период и экспоненту слова \(u=\texttt{abcabcab}\).

Решение. Слово записывается как \((\texttt{abc})^2\texttt{ab}\), значит, период \(3\) есть. Период \(1\) невозможен, потому что буквы не одинаковы. Период \(2\) тоже невозможен: уже префикс \(\texttt{abca}\) не согласуется с двухбуквенной периодичностью. Следовательно, наименьший период равен \(3\), а экспонента [ \exp(u)=\frac{|u|}{p(u)}=\frac{8}{3}. ] Итак, \(u\) — \(8/3\)-степень.

Задача B. У слова \(u=\texttt{aabcaabcaa}\) указать несколько периодов и найти стандартную экспоненту.

Решение. Имеем [ u=(\texttt{aabc})^2\texttt{aa}, ] поэтому \(4\) — период. Также \(u=\texttt{aabcaabc}\cdot\texttt{aa}\), так что \(8\) — тоже период; аналогично можно рассматривать и период \(9\). Но стандартная экспонента слова считается по наименьшему периоду. Следовательно, [ p(u)=4,\qquad \exp(u)=\frac{10}{4}=\frac52. ] Здесь важно видеть, что «пара период–экспонента» не уникальна, а вот стандартная экспонента определяется по кратчайшему периоду.

Задача C. Найти \(RT(2)\), \(RT(4)\) и \(RT(8)\).

Решение. По теореме Дежан: [ RT(2)=2,\qquad RT(4)=\frac75,\qquad RT(8)=\frac87. ] Последнее берется из общей формулы \(RT(k)=k/(k-1)\) для \(k\ge5\).

Задача D. Существует ли бесконечное бинарное квадрат-свободное слово? Существует ли бесконечное бинарное \(2^+\)-свободное слово?

Решение. Квадрат-свободность — это \(2\)-свободность. Поскольку \(RT(2)=2\), бесконечное бинарное \(2\)-свободное слово не существует. Но бесконечное бинарное \(2^+\)-свободное слово существует; классический пример дает слово Туэ–Морса, у которого критическая экспонента равна \(2\). Значит, в бинарном случае равенство порогу принципиально отделяет \(2\)-free от \(2^+\)-free.

Задача E. Существует ли бесконечное тернарное \(9/5\)-свободное слово?

Решение. Да. Здесь [ RT(3)=\frac74=1.75,\qquad \frac95=1.8. ] Теорема Дежан гарантирует существование бесконечного тернарного \(7/4^+\)-свободного слова. Но если в слове нет факторов экспоненты \(>7/4\), то тем более в нем нет факторов экспоненты \(\ge 9/5\), потому что \(9/5>7/4\). Следовательно, бесконечное \(9/5\)-свободное тернарное слово существует.

Задача F. Существует ли бесконечное тернарное \(17/10^+\)-свободное слово?

Решение. Нет. Здесь [ \frac{17}{10}=1.7<\frac74=1.75=RT(3). ] По критерию применения теоремы Дежан \(\beta^+\)-свободное бесконечное \(k\)-арное слово существует тогда и только тогда, когда \(\beta\ge RT(k)\). Поскольку \(17/10<RT(3)\), бесконечного тернарного \(17/10^+\)-свободного слова не существует.

Задача G. Что именно следует из теоремы Дежан о существовании бесконечного слова на \(5\) буквах при пороге \(5/4\)?

Решение. Так как [ RT(5)=\frac54, ] из теоремы Дежан следует существование бесконечного \(5/4^+\)-свободного слова на \(5\) буквах. Но из одной только теоремы не следует существование бесконечного \(5/4\)-свободного слова. Ровно на равенстве порогу требуется более тонкий анализ. Значит, правильный вывод: «\(5/4^+\)-free — да; \(5/4\)-free — не определяется одной лишь теоремой Дежан».

Задача H. Пусть бесконечное слово \(x\) над \(6\)-буквенным алфавитом имеет критическую экспоненту \(E(x)=6/5\). Что можно заключить?

Решение. По определению критической экспоненты все факторы слова \(x\) имеют экспоненту \(\le 6/5\). Следовательно, \(x\) является \(6/5^+\)-свободным. Так как по теореме Дежан [ RT(6)=\frac65, ] слово \(x\) реализует пороговый случай для шестибуквенного алфавита. Однако из равенства \(E(x)=6/5\) еще не следует автоматически, что \(x\) не является \(6/5\)-свободным: нужно знать, достигается ли экспонента \(6/5\) некоторым фактором.

Контрольные упражнения

Ниже — короткий набор упражнений для самопроверки. Подсказки опираются только на определения, формулу \(RT(k)\) и теорему Файна–Вильфа.

Упражнение A. Найдите наименьший период и экспоненту слова \(\texttt{ababa}\). Подсказка: представьте его как \((\texttt{ab})^2\texttt{a}\).

Упражнение B. Найдите \(RT(12)\). Подсказка: для \(k\ge5\) действует общая формула.

Упражнение C. Существует ли бесконечное \(4\)-буквенное \(3/2\)-свободное слово? Подсказка: сравните \(3/2\) и \(RT(4)=7/5\).

Упражнение D. Существует ли бесконечное \(4\)-буквенное \(7/5^+\)-свободное слово? Подсказка: это случай точного равенства порогу.

Упражнение E. Что одна только теорема Дежан говорит об \(7/5\)-свободном бесконечном слове на \(4\) буквах? Подсказка: различайте \(\alpha\)-free и \(\alpha^+\)-free.

Упражнение F. У слова длины \(18\) известны периоды \(8\) и \(12\). Какой еще период гарантирован? Подсказка: проверьте неравенство \(18\ge8+12-\gcd(8,12)\).

Упражнение G. Если \(E(x)=2\), а экспонента \(2\) не достигается ни одним фактором, то является ли \(x\) \(2\)-свободным? Подсказка: здесь важна недостижимость супремума.

Упражнение H. Сравните \(RT(5)\), \(RT(6)\), \(RT(10)\) и найдите предел \(RT(k)\) при \(k\to\infty\). Подсказка: используйте форму \(RT(k)=1+\frac{1}{k-1}\) для \(k\ge5\).

Краткая справка и источники

Ниже собраны быстрые таблицы, которые удобно держать рядом при решении задач.

Эта таблица — самое компактное «правило применения» теоремы Дежан в задачах.

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

Русскоязычные материалы, с которых удобно начинать:

• Лекция Анна Фрид «Слова и избегаемость» — компактный русскоязычный вводный материал: квадраты, кубы, избегаемые экспоненты, \(RT(n)\), краткая история гипотезы Дежан.
• Курс Арсений Шур «Комбинаторика слов и ее приложения» — русскоязычный спецкурс; в программе явно есть теорема Файна–Вильфа, слова Аршона, избегаемые экспоненты и граничная теорема. Подходит для расширения после этого пособия.

Классические и основные источники:

• F. Dejean, Sur un théorème de Thue — оригинальная статья 1972 года: установлен случай \(k=3\) и сформулирована общая гипотеза.
• J.-J. Pansiot, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots — классический источник по случаю \(k=4\).
• J. D. Currie, N. Rampersad, A Proof of Dejean’s Conjecture — один из завершающих источников полного доказательства; особенно полезен для точной формулы \(RT(k)\).
• M. Rao, Last cases of Dejean’s conjecture — независимая завершающая линия доказательства последних случаев.
• L. Ilie, P. Ochem, J. Shallit, A Generalization of Repetition Threshold — очень полезный источник для точных определений \(\alpha\)-free, \(\alpha^+\)-free и для аккуратного понимания «что именно минимизируется» в \(RT(k)\).
• Combinatorics on Words — классический фундаментальный справочник по комбинаторике слов; хорош для базовой теории периодичности и повторов.
• Algebraic Combinatorics on Words — продвинутый референс по современной комбинаторике слов; полезен как следующий шаг после усвоения базовых определений и теорем.
• J. Shallit, The Critical Exponent is Computable for Automatic Sequences — удобный источник именно для определения критической экспоненты и важной оговорки о том, что супремум может достигаться, а может и не достигаться.

Итоговый учебный минимум для решения типовых задач по теме можно сформулировать так: нужно уверенно различать период, наименьший период, экспоненту, \(\alpha\)-free, \(\alpha^+\)-free, критическую экспоненту и знать точные значения \(RT(k)\). После этого почти все стандартные задачи решаются простым и строгим сравнением требуемого порога с \(RT(k)\), с обязательной проверкой тонкого случая равенства.