Комбинаторная сложность. Теорема о сложности периодических (с предпериодом) слов.

Executive summary

Для одностороннего бесконечного слова \(x\) над конечным алфавитом заключительная периодичность \(x=uv^\omega\) эквивалентна каждому из следующих условий: факторная сложность \(p_x(n)\) ограничена; существует \(n\), для которого \(p_x(n)\le n\); существует \(n\), для которого \(p_x(n+1)=p_x(n)\). Если же слово не является заключительно периодическим, то \(p_x(n+1)>p_x(n)\) для всех \(n\), а значит, \(p_x(n)\ge n+1\) для всех \(n\ge 0\). Исторически исходная двусторонняя форма принадлежит теореме Морса–Хедлунда 1938 года; односторонняя форма «с предпериодом» и критерий через равенство \(p(n+1)=p(n)\) закрепились в последующих работах и учебной литературе, в частности у Ковена–Хедлунда.

Ключевой технический инструмент — правые специальные факторы. Если \(F*n(x)\) обозначает множество факторов длины \(n\), а \(r_x(u)\) — число различных правых продолжений фактора \(u\in F*n(x)\), то [ p_x(n+1)-p_x(n)=\sum{u\in Fn(x)}(r_x(u)-1). ] Отсюда \(p_x(n+1)=p_x(n)\) тогда и только тогда, когда факторов длины \(n\) с двумя различными правыми продолжениями нет. Именно это делает поведение слова после некоторого места детерминированным и приводит к периодичности.

Для слова \(x=uv^\omega\) с наименьшим предпериодом \(m=|u|\) и наименьшим периодом \(q=|v|\) доказуем более точный факт: начиная с некоторой длины \(N\), выполняется [ p_x(n)=m+q. ] В частном случае чисто периодического слова \(x=v^\omega\) имеем \(m=0\), поэтому \(p_x(n)\) в конце концов равно точному периоду \(q\); более того, уже при \(n\ge q\) выполняется \(p_x(n)=q\). Это и есть практическая «теорема о сложности периодических слов», наиболее удобная для решения задач.

Определения и нотация

Работаем с односторонними бесконечными словами над конечным алфавитом \(A\). Стандартные определения конечного слова, длины, фактора, префикса, суффикса, бесконечного слова, чисто периодического и заключительно периодического слова, а также терминов «предпериод» и «период», зафиксированы в современных учебниках и обзорах именно в таком виде.

В этом пособии используются следующие обозначения.

Далее мы принимаем соглашение \(F\*0(x)=\{\varepsilon\}\), поэтому \(p_x(0)=1\). Если в вашем курсе \(p_x(n)\) определена только для \(n\ge1\), то это меняет лишь запись стартового шага; все ключевые критерии остаются теми же.

Слово \(x\in A^\omega\) называется чисто периодическим, если \(x=v^\omega\) для некоторого непустого \(v\in A^+\). Оно называется заключительно периодическим или периодическим с предпериодом, если [ x=uv^\omega ] для некоторых \(u\in A^\*\), \(v\in A^+\). Если \(|u|\) и \(|v|\) выбраны минимально, то \(|u|\) называется наименьшим предпериодом, а \(|v|\) — наименьшим периодом. Слово, не являющееся заключительно периодическим, называется апериодическим.

Элементарные свойства факторной сложности

Монотонность

Для любого бесконечного слова \(x\) функция \(p_x(n)\) неубывает: [ p_x(n+1)\ge p_x(n)\qquad (n\ge0). ]

Доказательство. Рассмотрим отображение, удаляющее последнюю букву, [ \pi:F{n+1}(x)\to Fn(x),\qquad \pi(wa)=w. ] Оно сюръективно, потому что любой фактор длины \(n\) в бесконечном слове продолжается вправо хотя бы одной буквой. Следовательно, [ |F{n+1}(x)|\ge |Fn(x)|, ] то есть \(p_x(n+1)\ge p_x(n)\). ∎

Правые специальные факторы

Фактор \(u\in F\*n(x)\) называется правым специальным, если у него не менее двух различных правых продолжений, то есть \(r_x(u)\ge2\). Это стандартный язык для описания первых разностей функции сложности.

Лемма о первой разности. Для любого \(n\ge0\) [ p_x(n+1)-p_x(n)=\sum{u\in Fn(x)}(r_x(u)-1). ]

Доказательство. Для каждого \(u\in F*n(x)\) число прообразов \(u\) при \(\pi:F*{n+1}(x)\to F*n(x)\) равно \(r_x(u)\): прообразами являются ровно слова \(ua\), где \(a\in R_x(u)\). Поэтому [ p_x(n+1)=\sum{u\in Fn(x)}r_x(u) =\sum{u\in Fn(x)}\bigl(1+(r_x(u)-1)\bigr) =p_x(n)+\sum*{u\in F*n(x)}(r_x(u)-1). ] ∎

Следствие. Равенство \(p_x(n+1)=p_x(n)\) эквивалентно отсутствию правых специальных факторов длины \(n\). Действительно, все слагаемые \(r_x(u)-1\) неотрицательны, и их сумма равна нулю тогда и только тогда, когда каждое из них равно нулю, то есть \(r_x(u)=1\) для всех \(u\in F\*n(x)\).

Почему равенство на одном уровне замораживает сложность навсегда

Если \(p_x(n+1)=p_x(n)\), то каждый фактор длины \(n\) имеет единственное правое продолжение. Тогда любой фактор длины \(\ell\ge n\) тоже имеет единственное правое продолжение: оно определяется последними \(n\) символами этого фактора. Следовательно, [ p_x(\ell+1)=p_x(\ell)\qquad\text{для всех }\ell\ge n, ] то есть после первого равенства функция сложности становится постоянной. Это и есть форма «strictly increasing, then constant», часто встречающаяся в литературе.

Для примера рассмотрим слово \(x=0(01)^\omega=0010101\ldots\). На уровне \(n=2\) его факторы равны \(00,01,10\), и каждый имеет единственное правое продолжение. Соответствующий граф переходов таков.

Здесь путь входит в цикл \(01\to10\to01\), что визуально даёт предпериод длины \(1\) и период длины \(2\).

Теорема Морса–Хедлунда–Ковена

Исторически полезно различать две формы результата. В оригинальной двусторонней версии 1938 года для би-бесконечного слова периодичность эквивалентна тому, что функция сложности сначала строго возрастает, а затем становится постоянной; супремум сложности равен точному периоду. Для односторонних слов естественная замена «периодичности» — заключительная периодичность, то есть наличие предпериода. Именно эта форма используется в задачах по комбинаторике слов.

Формулировка

Пусть \(x\in A^\omega\). Тогда эквивалентны следующие условия:

1. \(x\) заключительно периодично.
2. \(p_x(n)\) ограничена.
3. \(p_x(n)\) начиная с некоторого места постоянна.
4. Существует \(n\ge0\), для которого [ p_x(n+1)=p_x(n). ]
5. Существует \(n\ge1\), для которого [ p_x(n)\le n. ]

Эквивалентная отрицательная форма:

1. \(x\) апериодично.
2. Для всех \(n\ge0\) [ p_x(n+1)>p_x(n). ]
3. Для всех \(n\ge0\) [ p_x(n)\ge n+1. ]

Кроме того, если \(p_x(n+1)=p_x(n)\), то у слова есть представление с периодом не больше \(p_x(n)\), а предпериод можно выбрать меньше \(p_x(n)\).

Доказательство импликации \(p_x(n+1)=p_x(n)\Rightarrow x\) заключительно периодично

Пусть [ p_x(n+1)=p_x(n). ] По предыдущему следствию всякий фактор длины \(n\) имеет единственное правое продолжение.

Определим отображение [ T:Fn(x)\to Fn(x) ] так: если у фактора \(u=a*1a_2\cdots a_n\) единственное правое продолжение \(ua\), то [ T(u)=a_2a_3\cdots a_na. ] Теперь рассмотрим последовательность \(n\)-факторов слова \(x\): [ u_i=x[i..i+n-1],\qquad i\ge0. ] Тогда по построению [ u*{i+1}=T(u_i)\qquad(i\ge0). ]

Множество \(F*n(x)\) конечно и имеет размер \(p*x(n)\). Поэтому орбита [ u_0,u_1,u_2,\ldots ] в конечном множестве при отображении \(T\) неизбежно входит в цикл: существуют \(r\ge0\) и \(s\ge1\), такие что [ u{r+s}=ur. ] Так как продолжение справа у состояния \(u_r\) единственно, равенство \(u*{r+s}=u*r\) влечёт совпадение всех последующих состояний: [ u{r+s+t}=u_{r+t}\qquad(t\ge0). ] Следовательно, начиная с позиции \(r\) слово повторяется с периодом \(s\): [ x\qquad(t\ge0). ] Значит, }=x_{r+s+t\(x\) заключительно периодично.

Поскольку повтор в конечной орбите возникает не позже, чем через \(p_x(n)+1\) шагов, можно выбрать \(r<p_x(n)\) и \(s\le p_x(n)\). Тем самым период не превосходит \(p_x(n)\), а предпериод — меньше \(p_x(n)\). ∎

Доказательство остальных импликаций

Импликация \(1\Rightarrow2\). Пусть [ x=uv^\omega,\qquad |u|=m,\quad |v|=q. ] Рассмотрим фактор длины \(n\). Если он начинается в одной из позиций \(0,1,\ldots,m-1\), то таких факторов не более \(m\). Если он начинается не раньше позиции \(m\), то целиком лежит в периодическом хвосте и определяется только классом стартовой позиции по модулю \(q\), значит, таких факторов не более \(q\). Следовательно, [ p_x(n)\le m+q\qquad\text{для всех }n\ge0. ] Итак, \(p_x\) ограничена. ∎

Импликация \(2\Rightarrow3\). По лемме о монотонности \(p_x(n)\) не убывает. Любая ограниченная неубывающая последовательность целых чисел начиная с некоторого места постоянна. ∎

Импликация \(3\Rightarrow4\). Очевидна: если \(p_x\) начиная с некоторого места постоянна, то на этом месте уже есть равенство \(p_x(n+1)=p_x(n)\). ∎

Импликация \(4\Rightarrow1\). Доказана выше. ∎

Импликация \(5\Rightarrow4\). Предположим, что \(p_x(n)\le n\) для некоторого \(n\ge1\). Если бы для всех \(k=0,1,\ldots,n-1\) выполнялось строгое неравенство \(p_x(k+1)>p_x(k)\), то, начиная с \(p_x(0)=1\), получили бы [ p_x(n)\ge n+1, ] что противоречит \(p_x(n)\le n\). Значит, для некоторого \(k<n\) имеем [ p_x(k+1)=p_x(k). ] То есть выполнено условие 4. ∎

Импликация \(2\Rightarrow5\). Если \(p_x(n)\le C\) для всех \(n\), то при любом \(n\ge C\) имеем \(p_x(n)\le n\). ∎

Тем самым доказана эквивалентность 1–5. Отрицательная форма 6–8 получается отрицанием этих условий и уже доказанной монотонностью: если равенства \(p_x(n+1)=p_x(n)\) нигде нет, то разности всегда положительны, а значит, [ p_x(n)\ge p_x(0)+n=1+n. ] ∎

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

Немедленное следствие: слова Штурма — это в точности апериодические слова минимально возможной сложности, [ p_x(n)=n+1\qquad(n\ge0 \text{ или } n\ge1,\ \text{в зависимости от соглашения}). ] Именно поэтому они играют роль «крайних» непериодических примеров.

Точная структура сложности заключительно периодических слов

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

Точный предел

Теорема. Пусть [ x=uv^\omega, ] где \(|u|=m\) — наименьший предпериод, а \(|v|=q\) — наименьший период. Тогда существует \(N\), такое что [ p_x(n)=m+q\qquad\text{для всех }n\ge N. ]

Доказательство. Рассмотрим первые \(m+q\) суффиксов слова: [ s_i=xi x\cdots,\qquad 0\le i<m+q. ]}x_{i+2

Сначала покажем, что они попарно различны. Предположим противное: \(s_i=s_j\) при \(0\le i<j<m+q\). Тогда начиная с позиции \(i\) слово периодично с периодом \(d=j-i\), поскольку совпадают все символы на расстоянии \(d\): [ x{i+t}=x\qquad(t\ge0). ]}=x*{i+d+t

Если \(i<m\), то это означает, что периодичность начинается раньше наименьшего предпериода \(m\), противоречие.

Если \(i\ge m\), то оба суффикса лежат уже в чисто периодическом хвосте \(v^\omega\), а число \(d=j-i\) удовлетворяет \(1\le d<q\). Значит, хвост имеет период меньше \(q\), что противоречит минимальности периода \(q\).

Итак, суффиксы \(s*0,\ldots,s*{m+q-1}\) попарно различны.

Для каждой пары \(i<j\) длина их общего префикса конечна; обозначим её через \(\ell*{ij}\). Положим [ N=1+\max*{0\le i<j<m+q}\ell*{ij}. ] Тогда для всякого \(n\ge N\) первые \(n\) символов суффиксов \(s*0,\ldots,s*{m+q-1}\) попарно различны. Иначе говоря, факторы длины \(n\), начинающиеся в позициях \(0,1,\ldots,m+q-1\), попарно различны.

С другой стороны, любой фактор длины \(n\), начинающийся в позиции \(t\ge m\), совпадает с фактором, начинающимся в позиции [ m+((t-m)\bmod q), ] потому что хвост \(v^\omega\) \(q\)-периодичен. Значит, всех факторов длины \(n\) не больше \(m+q\).

Мы нашли \(m+q\) попарно различных факторов длины \(n\) и одновременно доказали верхнюю оценку \(m+q\). Следовательно, [ p_x(n)=m+q\qquad(n\ge N). ] ∎

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

Чисто периодический случай

Если \(m=0\), то получаем:

Следствие. Если \(x=v^\omega\) и \(q\) — наименьший период, то \(p_x(n)\) начиная с некоторого места равно \(q\). Более точно, [ p_x(n)\le q\quad\text{для всех }n,\qquad p_x(n)=q\quad\text{для всех }n\ge q. ]

Доказательство. Верхняя оценка \(p_x(n)\le q\) очевидна: фактор длины \(n\) определяется стартовой позицией по модулю \(q\). Для \(n=q\) факторы, начинающиеся в \(q\) разных позициях одного периода, являются \(q\) циклическими сдвигами слова \(v\). Они попарно различны: если два таких сдвига совпали бы, то \(v\) имело бы меньший период. Значит, [ p_x(q)=q. ] По монотонности и верхней оценке получаем \(p_x(n)=q\) для всех \(n\ge q\). ∎

В двусторонней формулировке это ровно соответствует классической записи: супремум функции сложности равен точному периоду.

Что важно не перепутать

Формула [ p_x(n)\equiv m+q \quad\text{для больших }n ] верна именно для наименьшего предпериода и наименьшего периода. Для произвольного разложения \(x=uv^\omega\) она может дать неверное число.

Контрпример: [ (ab)^\omega = a(ba)^\omega. ] Во втором разложении \(|u|+|v|=3\), но реальная сложность для больших \(n\) равна \(2\), потому что наименьший предпериод равен \(0\), а наименьший период равен \(2\).

Примеры и контрпримеры

Следующая таблица иллюстрирует все основные режимы поведения. Последняя строка — классический факт о словах Штурма.

Разберём две самые показательные ситуации.

Чисто периодический пример \((aab)^\omega\). Для \(n=2\) имеем факторы [ aa,\ ab,\ ba, ] поэтому \(p(2)=3\). С другой стороны, точный период равен \(3\), так что по доказанному следствию \(p(n)\le3\) при всех \(n\), а из монотонности немедленно следует \(p(n)=3\) для всех \(n\ge2\).

Пример с предпериодом \(0(01)^\omega\). Здесь период хвоста равен \(2\), но асимптотическая константа сложности равна \(3\), а не \(2\). Это важный контрпример к неверному утверждению «у заключительно периодического слова предел сложности равен периоду хвоста». Правильная формула — \(m+q\), то есть \(1+2=3\).

Отсюда получаются три стандартных контрпримера.

• Ограниченная сложность не означает чистую периодичность: \(0(01)^\omega\) ограничено по сложности, но имеет ненулевой предпериод.
• Для слов с предпериодом утверждение \(p_x(n)\le q\) ложно: у \(0(01)^\omega\) имеем \(q=2\), но \(p_x(2)=3\).
• Формула \(m+q\) требует минимального выбора \((m,q)\): запись \(a(ba)^\omega\) для слова \((ab)^\omega\) не является канонической.

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

Задача

Найти \(p_x(n)\) для слова [ x=(aab)^\omega. ]

Решение

Любой фактор длины \(n\) задаётся стартовой позицией по модулю \(3\), поэтому [ p_x(n)\le3. ] Для \(n=1\) факторы — это \(a,b\), значит \(p_x(1)=2\). Для \(n=2\) факторы равны [ aa,\ ab,\ ba, ] поэтому \(p_x(2)=3\). По монотонности и верхней оценке \(3\) получаем [ p_x(n)=3\qquad(n\ge2). ]

Итог: [ p_x(1)=2,\qquad p_x(n)=3\ \text{при }n\ge2. ]

Задача

Найти \(p_x(n)\) для слова [ x=0(01)^\omega=0010101\ldots ]

Решение

При \(n=1\) имеем факторы \(0,1\), следовательно, [ p_x(1)=2. ]

Пусть теперь \(n\ge2\). Тогда фактор длины \(n\) либо начинается в позиции \(0\), либо целиком начинается уже в периодическом хвосте.

• Старт в позиции \(0\) даёт один специальный «пограничный» фактор.
• В хвосте \( (01)^\omega \) возможны ровно два фактора длины \(n\), соответствующие двум классам стартовой позиции по модулю \(2\).

Итак, всего не более трёх факторов. Они действительно различны: пограничный фактор начинается с \(00\), а два хвостовых начинаются с \(01\) и \(10\). Следовательно, [ p_x(n)=3\qquad(n\ge2). ]

Итог: [ p_x(1)=2,\qquad p_x(n)=3\ \text{при }n\ge2. ]

Задача

Пусть для бесконечного слова \(x\) известно, что [ p_x(6)\le6. ] Доказать, что \(x\) заключительно периодично, и получить оценку на период.

Решение

По теореме Морса–Хедлунда–Ковена условие \(p_x(6)\le6\) уже достаточно для заключительной периодичности. Действительно, из него следует, что существует \(k<6\) такое, что [ p_x(k+1)=p_x(k). ] Тогда на уровне \(k\) каждый фактор имеет единственное правое продолжение, а детерминированный переход по конечному множеству \(F\*k(x)\) приводит к циклу. Поэтому слово заключительно периодично.

Для оценки периода используем ту же конструкцию: длина цикла не превосходит числа состояний, то есть [ \text{период}\le |F*k(x)|=p_x(k)\le p_x(6)\le6. ] Аналогично предпериод можно выбрать меньше \(p_x(k)\), следовательно, тоже не больше \(5\).

Итак, \(x\) заключительно периодично; один из допустимых периодов имеет длину не больше \(6\).

Задача

Пусть известно, что множество факторов длины \(2\) равно [ F*2(x)={00,01,10}, ] и правые продолжения единственны: [ 00\mapsto1,\qquad 01\mapsto0,\qquad 10\mapsto1. ] Восстановить слово \(x\), если оно начинается с \(00\).

Решение

Начальный фактор — \(00\). По условию он продолжается только буквой \(1\), поэтому слово начинается как [ 001. ] Тогда следующий двухбуквенный фактор — \(01\), а он продолжается только буквой \(0\): [ 0010. ] Теперь следующий фактор — \(10\), и он продолжается только буквой \(1\): [ 00101. ] Дальше снова появляется \(01\), затем \(10\), и процесс зацикливается: [ 00\to01\to10\to01\to10\to\cdots ] Следовательно, [ x=0(01)^\omega. ]

Это типичный способ «считать период» по уникальным продолжениям факторов.

Справочные таблицы и первоисточники

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

Основные источники, на которые опирается это пособие:

• Оригинальные статьи Marston Morse_* и Gustav A. Hedlund*: _Symbolic Dynamics (1938) и Symbolic Dynamics II. Sturmian Trajectories (1940). Это исторический первоисточник теоремы и всей линии «минимальной непериодической сложности».

• Статьи *_Ethan M. Coven_: _Sequences with minimal block growth (1973) и Sequences with minimal block growth II (1974). В учебной практике именно с ними обычно связывают односторонний вариант критерия для слов с предпериодом и формулировку через \(p(n+1)=p(n)\).

• Авторитетные монографии Combinatorics on Words_*, Algebraic Combinatorics on Words* и **Combinatorics, Words and Symbolic Dynamics*. Они удобны для систематической нотации, терминов «special factor», «Sturmian», языка факторов и связанных доказательств.

• Русскоязычный обзор 2009 года «Последовательности, близкие к периодическим» / Sequences close to periodic полезен как компактный мост между первоисточниками и учебным изложением: он содержит формулировку Proposition 6.1.1, краткое доказательство критерия \(p_x(n)\le n\), большую библиографию и русскую терминологию.