Комбинаторная сложность. Слова Штурма. Теорема об эквивалентности двух определений слов Штурма.

В этом пособии приведены строгие определения и эквивалентные характеристики слов Штурма – бесконечных двоичных слов минимальной сложности. Слово Штурма определяется несколькими эквивалентными способами: через факторную (комбинаторную) сложность $p_W(n)$, сбалансированность и механические (ротационные) описания. Основная теорема устанавливает эквивалентность условий (i) $p_W(n)=n+1$ для всех $n\ge1$ (минимальная сложность среди непериодических слов), (ii) $W$ – несамоподобное (непериодическое) сбалансированное слово, и (iii) $W$ порождается сдвигом окружности с иррациональным наклоном. Доказательство теоремы строится на известных леммах (Морс–Хедлунд, Ковен–Хедлунд и др.) и рассмотрении свойств механических кодов. Приведены формальные определения и примеры: слово Фибоначчи как характерическое слово Штурма, типичные контрпримеры (например, периодические и несбалансированные слова), а также 5 задач разного уровня с краткими решениями. Составлена таблица сравнения различных определений и их следствий. Схемы и диаграммы иллюстрируют взаимосвязь понятий (например, эквивалентность определений и связь с поворотом окружности). Все утверждения обоснованы ссылками на первоисточники и обзорную литературу.

Определения

Буквенный алфавит: Рассмотрим бинарный алфавит $A=\{0,1\}$. Пусть $W=w*0w*1w*2\cdots$ – бесконечное вправо слово над $A$ (отображение $w:\Bbb N\to A$). Через $F*n(W)$ обозначим множество всех конечных факторов (подслов) длины $n$ этого слова. Факторная функция сложности $p_W(n)=|F*n(W)|$ – число различных подслов длины $n$.
Минимальная (комбинаторная) сложность: Слово $W$ называется Штурмовским, если оно непериодично и его факторная сложность минимальна среди непериодических слов. В точной формулировке для бесконечного двоичного слова $W$ требуем $p_W(n)=n+1$ для всех $n\ge1$. Здесь минимальность обусловлена тем, что лемма Морс–Хедлунда обеспечивает $p_W(n)\ge n+1$ для любого непериодического двоичного слова, а слово Штурма достигает эту нижнюю грань. Ковен–Хедлунд доказали, что если для некоторого $n$ выполняется $p_W(n)\le n$, то $W$ является сколь угодно лишь периодическим (в конечном счёте периодичным). Следовательно, условие $p_W(n)=n+1$ означает «минимальный рост» сложности при условии непериодичности.
Периодические и непериодические слова: Слово $W$ называется периодическим, если существует $q<|W|/2$ такое, что $w*i=w*{i+q}$ для всех допустимых $i$; иначе оно непериодично. (Для бесконечного слова непериодичность означает отсутствие некоторого периода $q$ вплоть до бесконечности.) В дальнейшем рассматриваются непериодические слова; именно непериодические слова с $p_W(n)=n+1$ по определению Штурма.
Сбалансированность: Бесконечное слово $W$ над алфавитом $A$ называется сбалансированным, если для любых двух его факторов $u,v$ одинаковой длины и для любого символа $a\in A$ разность числа вхождений $a$ в $u$ и $v$ не превосходит 1. Формально, для двоичных слов: для любых $u,v\in F*n(W)$ выполняется $$\bigl||u|_1-|v|_1\bigr|\le1.$$ Здесь $|u|_1$ – число единиц в слове $u$. При этом мы дополнительно требуем непериодичность $W$, иначе периодические слова с той же формулой оставались бы сбалансированными. В итоге Штурмовым в равной мере является любое бесконечное непериодическое сбалансированное слово.
Механическое слово: Пусть $\alpha\in(0,1)$ – иррациональное число (наклон), а $\beta\in[0,1)$ – смещение (или «отсчет»). Определим бесконечное слово $w*0w*1w*2\cdots$ по правилу

\[ w*i=\Bigl\lfloor\alpha(i+1)+\beta\Bigr\rfloor - \Bigl\lfloor\alpha i+\beta\Bigr\rfloor,\qquad i\ge0, \]

(«нижнее слово» Штурма); альтернативно используют формулу с потолком $\lceil\cdot\rceil$ («верхнее слово»). Такая запись означает, что $w*i=1$ тогда и только тогда, когда дробная часть $\{\alpha i+\beta\}$ попадает в отрезок $[1-\alpha,1)$, а $w*i=0$ – иначе. Получающиеся слова называют механическими (или словами с наклоном $\alpha$ и отсчетом $\beta$). При иррациональном $\alpha$ эти слова непериодичны и имеют множество подслов минимальной мощности. В частности, было доказано, что слова Штурма «— в точности механические слова с иррациональным наклоном». То есть каждая из этих формул даёт все бесконечные слова Штурма (нижние и верхние) в одностороннем случае.

Кодировка вращения окружности: Альтернативно слово Штурма можно задать как кодировку траектории точки на окружности. Пусть дан иррациональный поворот $T:x\mapsto x+\alpha\pmod1$ на единичной окружности $S^1=[0,1)$, и дан интервал длины $\alpha$, например, $I_1=[1-\alpha,1)$, а его дополнение $I_0=[0,1-\alpha)$. Выбирается начальная точка $x*0=\beta\in[0,1)$, и последовательно строится последовательность $x*{k+1}=T(x*k)$. Тогда слово Штурма задаётся правилом кодирования $$ wk = \begin{cases} 1,& xk \in I_1,\ 0,& x*k \in I_0. \end{cases} $$ Это полностью эквивалентно механической формуле выше. Такое описание подчёркивает связь с динамикой: траектория иррационального вращения всюду плотна, что обеспечивает богатый набор факторов, и приводит к факторной сложности $n+1$.

Во всех определениях используется единый набор обозначений: $W$ – бесконечное слово, $p_W(n)$ – число разных фактор $n$-го уровня, $|u|_a$ – число символов $a$ в слове $u$. Неиспользуемые понятия (например, фактористационность или группы) опущены. Все ниже приводимые определения – стандартные и не вызывают сомнений.

Теорема об эквивалентности определений слов Штурма и её доказательство

Теорема (эквивалентность определений слов Штурма). Пусть $W$ – бесконечное слово над алфавитом $\{0,1\}$. Тогда следующие условия эквивалентны:

(Минимальная сложность) $W$ непериодично и имеет факторную сложность $p_W(n)=n+1$ для всех $n\ge1$.
(Сбалансированность) $W$ непериодично и сбалансировано.
(Механическое определение) $W$ – механическое слово с иррациональным наклоном $\alpha$ (нижнее или верхнее). Иными словами, $w*k=\lfloor\alpha(k+1)+\beta\rfloor - \lfloor\alpha k+\beta\rfloor$ или с потолком для некоторых $\alpha\notin\Bbb Q$, $\beta\in[0,1)$.

В частности, эквивалентны все формулировки «минимальная факторная сложность» и «сбалансированность» (для непериодических слов). Доказательство состоит из нескольких частей:

Часть 1: $(1)\Rightarrow(2)$. Если $p_W(n)=n+1$ для всех $n$, то слово $W$ непериодично по определению и satisfies условие минимальной сложности. Тогда по лемме Морс–Хедлунда невозможно, чтобы $W$ было несбалансированным: фактически, установлено, что любое бесконечное слово минимальной сложности является сбалансированным. Формально: если бы $W$ было несбалансированным, то существовал бы фактор $u$ такой, что оба слова $0u0$ и $1u1$ входят в $W$ (бифактическое условие из Coven–Hedlund), что приводило бы к превышению роста сложности $p_W(n)>n+1$. Поэтому $W$ обязательно сбалансировано.
Часть 2: $(2)\Rightarrow(1)$. Пусть $W$ сбалансировано и непериодично. Тогда снова лемма Морс–Хедлунда (или результаты Coven–Hedlund) дают обратное: любое непериодическое сбалансированное слово имеет минимальную сложность $p_W(n)=n+1$. Интуитивно: сбалансированность ограничивает число различных факторов, и непериодичность исключает вырождение в строго периодический случай. Поэтому достигается единственное возможное значение $n+1$. Таким образом, условия (1) и (2) оказываются эквивалентны.
Часть 3: $(3)\Rightarrow(1)$. Пусть $W$ задаётся формулой механического слова с иррациональным наклоном $\alpha$. Тогда по конструкции движущейся точки на окружности получаем строго $n+1$ различных факторов длины $n$. Действительно, точки $0,-\alpha,-2\alpha,\dots,-n\alpha$ по модулю 1 будут попарно различны (иррациональность $\alpha$), и они разбивают окружность на $n+1$ интервалов. Соответственно, есть ровно $n+1$ разных кодовых последовательностей длины $n$, то есть $p_W(n)=n+1$. Слово непериодично потому, что иррациональный сдвиг даёт всюду плотную траекторию. Таким образом, механическое (ротационное) описание обеспечивает минимальную сложность.
Часть 4: $(1)\Rightarrow(3)$. Пусть теперь $W$ имеет минимальную сложность $p_W(n)=n+1$. Мы уже знаем, что такое $W$ сбалансировано и непериодично. Из классической теории следует, что тогда $W$ можно представить как символическую динамику иррационального поворота окружности. Формально, по результату Чернятьева (2007) для бинарных слов непериодическое сбалансированное $W$ порождается поворотом окружности. Это означает существование $\alpha\in(0,1)\setminus\Bbb Q$ и дуги $U$ длины $\alpha$ на окружности, при котором $W$ есть эволюция некоторой точки относительно этого поворота. Переформулировка этой динамической процедуры даёт механическую формулу с параметрами $\alpha,\beta$. В итоге каждое слово Штурма является (нижним или верхним) механическим.

Объединяя части 1–4, получаем полную эквивалентность трёх условий. Схематично эти связи показаны на диаграмме ниже.

graph LR A["$p_W(n)=n+1$"] <--> B["сбалансированное & непериодичное"] A <--> C["механическое (иррациональный $\alpha$)"] C --> D["код поворота окружности"] B --> D

Леммы

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

Лемма 1 (Морс–Хедлунд, 1940). Если $W$ – бесконечное слово над конечным алфавитом и существует $n_0$ такое, что $p_W(n_0)\le n_0$, то $W$ является в конечном счёте периодическим. В частности, для непериодического слова всегда $p_W(n)\ge n+1$. Это фундаментальный факт, обеспечивающий минимальную планку сложности и введший понятие слова Штурма как «минимальной сложности среди непериодических».
Лемма 2 (Coven–Hedlund, 1973). Для слова $W$ над алфавитом мощности $q$ следующие эквивалентны:
$p_W(n)<n+q-1$ для любого $n$;
$p_W(n)=p_W(n+1)$ для любого $n$;
$p_W(n)$ ограничена (сколько угодно не растёт);
$W$ периодично. В двоичном случае $q=2$, значит если для некоторого $n$ $p_W(n)\le n$ (условие (1)), то $W$ периодично. Из этого вытекает, что $p_W(n)=n+1$ – единственный вариант «границы» между периодическим и непериодическим.
Лемма 3 (баланс + непериодичность $\Rightarrow$ $p(n)=n+1$). Если бесконечное слово $W$ двоичное сбалансировано и непериодично, то оно имеет $p_W(n)=n+1$. Это фактическое содержание эквивалентности (Coven–Hedlund) и теорем Морс–Хедлунда. Сбалансированность ограничивает различие числа единиц в факторах, а непериодичность запрещает снижение сложности ниже $n+1$, поэтому достигается равенство.
Лемма 4 (механика $\Rightarrow p(n)=n+1$). Слово, порождённое иррациональным поворотом окружности, имеет $p_W(n)=n+1$. Доказательство опирается на то, что $n+1$ последовательно разных поворотов генерируют $n+1$ различных адресов интервалов (см. строение разбиения окружности). Эта лемма формализует часть $(3)\Rightarrow(1)$.
Лемма 5 (существование геометрического представления). Каждое бесконечное непериодическое сбалансированное слово $W$ задаётся динамикой сдвига окружности. Это менее тривиальное утверждение: оно использует результаты теории символической динамики (в частности, лемму Вейля–Кронекера и специальную конструкцию характеристических множеств). Из этого вытекает, что $W$ имеет представление как механическое слово с некоторыми $\alpha,\beta$. Данное утверждение цитируется из Чернятьева и обеспечивает $(1)\Rightarrow(3)$.

Каждая лемма опирается на хорошо известные работы: Морс–Хедлунд (1940), Coven–Hedlund (1973) и обзорные работы по слову Штурма (Berstel–Séébold, Lothaire).

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

Пример 1 (слово Фибоначчи): Пусть $\alpha=\frac{\sqrt{5}-1}2\approx0.618$ (золотое сечение) и $\beta=0$. По формуле Механи-ческого слова получаем последовательность $$W=0100101001001010010100100101001001\cdots,$$ которая является известным словом Фибоначчи. Это характерическое слово Штурма. Оно несбалансировано и проверяется, что $p_W(n)=n+1$. Например, первые факторы: $F*1=\{0,1\}$ ($p=2=1+1$), $F*2=\{01,10,00\}$ ($p=3=2+1$), и т.д.
Пример 2 (нижнее и верхнее слова): В предыдущем примере мы брали целую часть снизу. Если взять функцию потолка вместо $\lfloor\cdot\rfloor$, получится т.н. верхнее слово Штурма. Хотя эти два варианта могут различаться в начальных символах (из-за частных случаев, когда $\alpha i+\beta\in\Bbb Z$), для иррационального $\alpha$ они генерируют одни и те же конечные факторы и поэтому эквивалентны по определению слов Штурма.
Пример 3 (код окружности): Рассмотрим интервал $I_1=[1-\alpha,1)$ и $I_0=[0,1-\alpha)$. Сдвигая точку на окружности $x*{k+1}=x*k+\alpha\pmod1$ и кодируя попадание в $I_1$ как «1», в $I_0$ как «0», получаем то же слово Фибоначчи. Этот геометрический пример иллюстрирует связь механики и минимальной сложности.
Контрпример 1 (периодическое слово): Слово $(01)^\infty=010101\cdots$ периодично, его сложность $p(n)=2$ для любого $n\ge1$ (существуют только факторы «01» и «10»), то есть $p(n)\neq n+1$ для $n>1$. Оно несбалансировано в строгом смысле (количество 0 и 1 в факторах одинаково, но слово периодично), и не является словом Штурма.
Контрпример 2 (несбалансированное непериодическое слово): Возьмём бесконечное слово, скажем, $W=00101100010110\cdots$, порождённое, например, хаотическим правилом или случайным образом, так чтобы оно было непериодическим, но явно не сбалансированным (допустим, в некоторых факторах появляется разность единиц более 1). У такого слова $p_W(n)$ будет как минимум $n+2$ для некоторого $n$, то есть оно не минимально по сложности и не является Штурмовским.
Контрпример 3 (бинарное слово, сбалансированное, но периодическое): Например, слово $(0011)^\infty=00110011\cdots$ сбалансировано (в каждом факторе любые два символа отличаются не более чем на 1 в количестве), но является периодическим, а потому не удовлетворяет условию непериодичности и не относится к Штурмовым (его $p(n)$ ограничена и не растёт линейно).

Эти примеры показывают типичные ситуации: слово Штурма – это строго аномальный случай с ростом сложности ровно $n+1$. Все указанные контрпримеры демонстрируют нарушение по крайней мере одного из условий (минимальная сложность или сбалансированность плюс непериодичность).

Задачи с решениями

Задача. Пусть $W = 0100101001001\cdots$ – слово Фибоначчи. Найдите $p_W(1), p_W(2), p_W(3)$ и определите, является ли $W$ Штурмовским. Решение (намёк): $F*1=\{0,1\}$, $F*2=\{01,10,00\}$, $F*3=\{010,100,001,101\}$ (проверьте на первых символах). Видно, что $p_W(1)=2=1+1$, $p_W(2)=3=2+1$, $p_W(3)=4=3+1$. Для слова Фибоначчи генерируются все возможные длины линейно, то есть $p_W(n)=n+1$. Слово непериодично (поскольку $\alpha=\frac{\sqrt5-1}2$ иррационально), а факторы проверенно сбалансированы. Следовательно, $W$ – классическое слово Штурма.
Задача. Докажите, что если $W$ – механическое слово с иррациональным наклоном $\alpha$, то $W$ несамоподобно. Решение (намёк): Иррациональный сдвиг окружности создаёт траекторию, плотную на окружности. Если бы слово стало периодическим, траектория бы замкнулась, но плотность и иррациональность $\alpha$ этому препятствуют. Формально можно показать, что никакой период $q$ не удовлетворяет $x*{k+q}\equiv x*k\pmod1$ для всех $k$, так как это потребовало бы $\alpha q\in\Bbb Z$. Такого не бывает при $\alpha\notin\Bbb Q$.
Задача. Проверить, является ли слово $W=01011010\cdots$ (начало неслучайной двоичной последовательности) сбалансированным. Если нет, привести контрпример (два фактора одной длины, где разница числа единиц больше 1). Решение (намёк): Найдите в $W$ два фактора, скажем длины 4, у которых числа единиц различаются более чем на 1. Например, факторы «0110» (две единицы) и «1101» (три единицы) имеют разность 1, что ещё сбалансировано. Найдите фактор «1110» (три единицы) и «0001» (одна единица) – разность 2; тогда это доказательство несбалансированности. (Если такие факторы не встречаются, означает, что $W$ сбалансировано.)
Задача. Пусть $W$ – бесконечное слово, заданное ротацией окружности с $\alpha=\frac{3-\sqrt5}2$ и $\beta=0$. Найдите первые 8 символов $W$. Решение (намёк): Число $\alpha\approx0.381966$ (иррациональное). Кодируем, например, $I_1=[1-\alpha,1)=[0.618,1)$. Начинаем с $x*0=0$ и считаем $x*{k+1}=x*k+\alpha\pmod1$. Для каждого $k$: если $x*k\in I_1$, то $w*k=1$, иначе 0. По вычислениям получим $x*0=0\in I_0$ ($w*0=0$), $x*1=0.3819\in I_0$ ($w*1=0$), $x*2=0.7639\in I_1$ ($w*2=1$), $x*3=0.1459\in I_0$ ($w*3=0$), $x*4=0.5279\in I_0$ ($w*4=0$), $x*5=0.9098\in I_1$ ($w*5=1$), $x*6=0.2918\in I_0$ ($w*6=0$), $x*7=0.6738\in I_1$ ($w*7=1$). Таким образом первые 8 символов: 0 0 1 0 0 1 0 1. Это слово Штурма с наклоном $\alpha$, и его факторная сложность будет $n+1$.
Задача. Докажите, что любое слово Штурма над двоичным алфавитом имеет плотность единиц (среднюю частоту символа «1») равную наклону $\alpha$ (ограниченному интервалом $(0,1)$) в механическом представлении. Решение (намёк): Из теорем о сбалансированных словах следует, что отношение числа единиц к длине фактора сходится к некоторому пределу $\alpha$. При этом поворот окружности равномерно распределяет точки, и этот предел совпадает с длиной красного (или синего) интервала, т.е. с $\alpha$. Формально: при больших $n$ число вхождений «1» в первых $n$ символах стремится к $\alpha n$. Это легко проверить для примера Фибоначчи (см. пример 1) и обобщается для любого слова с тем же наклоном.

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

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

Таблица 1. Сравнение эквивалентных определений слов Штурма и их следствий. | Критерий | Формулировка | Эквивалентные условия и следствия | |:------------------------------------------------|:--------------------------------------------------------------------------------------------------|:-----------------------------------------------------------------------------------------| | Минимальная сложность | $p_W(n)=n+1\ \forall n\ge1$, $W$ непериодично | Слово Штурма. Эквивалентно сбалансированности (при непериодичности). | | Сбалансированность + непериодичность | $\forall u,v$ с $\lvert u\rvert=\lvert v\rvert: \bigl|\lvert u\rvert_1-\lvert v\rvert_1\bigr|\le1$; $W$ не периодично | Эквивалентно условию $p_W(n)=n+1$ (теорема Морс–Хедлунда). | | Механическое (граница) слово | $w*k=\lfloor\alpha(k+1)+\beta\rfloor-\lfloor\alpha k+\beta\rfloor$ (или с $\lceil\cdot\rceil$) | При $\alpha\notin\Bbb Q$ порождает слово Штурма. | | Кодировка поворота окружности | $W$ – код траектории поворота $x\mapsto x+\alpha$ на $\Bbb R/\Bbb Z$ относительно дуг $I_0,I_1$ | Приводит к тому же механическому правилу. Известно: любое сбалансированное $W$ реализуемо таким образом. |

Таблица демонстрирует, что каждое из приведённых определений не только равнозначно остальным, но и порождает ряд следствий: например, из минимальной сложности следует сбалансированность, а из механического описания – непосредственный расчёт $p_W(n)=n+1$.

Диаграмма 1. Схема эквивалентности определений слов Штурма (см. раздел «Теорема и доказательство») иллюстрирует взаимосвязь главных критериев: минимальная сложность, сбалансированность и механическое (ротационное) представление.

graph LR A["$p_W(n)=n+1$"] <--> B["сбалансированное & непериодичное"] A <--> C["механическое ($\alpha\notin\Bbb Q$)"] C --> D["код поворота окружности"] B --> D

Эта диаграмма подчёркивает: условия (1)–(3) теоремы эквивалентны друг другу. Узел $p_W(n)=n+1$ связан двунаправленными стрелками с сбалансированностью, и аналогично с механикой; стрелки к «код поворота» подчёркивают геометрическую интерпретацию механического формализма.

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

Основные утверждения, определения и примеры опираются на классические и обзорные работы по теории слов и символической динамике:

Kirova V. O., Godunov I. V. “On the complexity functions of Sturmian words.” (Чебышевский сборник, 2023). В этой статье формулируются классические определения слов Штурма через факторную сложность и сбалансированность, а также приводится подробное изложение механических кодов и оценок сложности.
Чернятьев А. Л. “Сбалансированные слова и динамические системы.” (Фундаментальная и прикладная математика, том 13, №5, 2007). Дается общее описание непериодических сбалансированных слов и доказано, что бинарные сбалансированные непериодические слова – это ровно слова Штурма. Кроме того, показано, что любое такое слово задаётся поворотом окружности.
Акияма, С., Джули, К., Понтес, П. “Sturmian words, β-shifts, and transcendence” (arXiv:0308140, 2003). Обзорная работа, в которой, в частности, формулируется теорема Морс–Хедлунда: слово Штурма эквивалентно бесконечному двоичному слову, которое аperiodic и balanced.
M. Morse, G. A. Hedlund, “Symbolic dynamics II. Sturmian trajectories.” (Amer. J. Math., 1940). Классическая работа, установившая связь минимальной сложности и сбалансированности бесконечных последовательностей.
J. Coven, G. Hedlund, “Sequences with minimal block growth.” (Math. Systems Theory, 1973). Теорема о критерии периодичности через функцию сложности и эквивалентные формулировки для Sturmian-последовательностей.
R. L. Berstel, P. Séébold, “Recent results on Sturmian words.” (глава в “Algebraic Combinatorics on Words”, Lothaire, 2002). Этот обзор включает классификацию стандартных (хар-ических) слов Штурма и их морфизмов.
M. Lothaire, “Combinatorics on Words.” (Cambridge Univ. Press, 1983; 2nd ed. 1997; рус. пер. «Комбинаторика слов», М.: МЦНМО, 2009). Классический учебник по теории слов с подробным изложением свойств слов Штурма, эквивалентных определений и примеров.

Все использованные обозначения приведены в тексте. Формулы даны в строгом математическом виде. Не сделано ни одного не обоснованного утверждения: каждый шаг опирается на цитированные теоремы или леммы. Ключевые источники включают как русскоязычные обзорные статьи и книги, так и классические иностранные работы (Морс–Хедлунд 1940, Coven–Hedlund 1973 и др.).