Комбинаторная сложность. Слова Штурма. Лемма о сбалансированном множестве и палиндроме.

Executive summary

В теории слов стандартная факторная сложность бесконечного слова \(w\) — это функция \(p*w(n)=|F*n(w)|\), где \(F*n(w)\) есть множество всех факторов длины \(n\). Для непериодических слов действует нижняя граница \(p*w(n)\ge n+1\); бинарные слова, достигающие этой границы при всех \(n\ge 1\), и есть слова Штурма. Эквивалентно, слово Штурма — это бинарное сбалансированное апериодическое слово; то же самое множество дают иррациональные механические слова. Для слов Штурма работают еще две важные эквивалентные характеристики: у каждого непустого фактора ровно два возвратных слова, а палиндромная сложность равна \(P(n)=1\) при чётных \(n\) и \(P(n)=2\) при нечётных \(n\). Для конечных слов точный аналог таков: конечное бинарное слово является конечным словом Штурма тогда и только тогда, когда оно сбалансировано.

Основной доказательный каркас темы состоит из трёх шагов. Сначала используется теорема Марстон Морс–Густав Хедлунд: у апериодического слова сложность не может опуститься ниже \(n+1\). Затем доказывается лемма о сбалансированном множестве факторов: язык бинарного сбалансированного слова имеет не более \(n+1\) факторов длины \(n\). Наконец, если слово со сложностью \(n+1\) предположить несбалансированным, минимальный контрпример имеет вид \(0W0\) и \(1W1\), причём \(W\) обязан быть палиндромом; это приводит к противоречию с минимальной сложностью.

Определения

Пусть \(A\) — конечный алфавит, \(A^\*\) — множество конечных слов, \(A^\omega\) — множество правосторонне-бесконечных слов. Для конечного слова \(u=u*0u_1\cdots u*{m-1}\) длина обозначается через \(|u|=m\), а разворот через \(\widetilde u=u*{m-1}\cdots u_1u_0\). Слово \(u\) называется палиндромом, если \(u=\widetilde u\). Для бесконечного слова \(w\) через \(F\*n(w)\) обозначают множество факторов длины \(n\), а через \(F(w)=\bigcup*{n\ge 0}F*n(w)\) — весь язык факторов. В русскоязычной литературе факторную сложность обозначают либо \(p*w(n)\), либо \(T_n(w)\); это одна и та же функция: число различных факторов длины \(n\).

Факторная сложность. Для бесконечного слова \(w\) над алфавитом \(A\) [ pw(n)=|Fn(w)|,\qquad n\ge 0. ] В контексте слов Штурма выражения комбинаторная сложность, подсловная сложность и факторная сложность* обычно используются как синонимы этой функции. Для двоичных слов \(p*w(1)=2\) означает, что в слове встречаются обе буквы.

Сбалансированность. Бесконечное бинарное слово \(w\) называется сбалансированным, если для любых двух факторов \(u,v\in F(w)\) одинаковой длины выполняется [ \bigl|\lvert u\rvert_1-\lvert v\rvert_1\bigr|\le 1, ] где \(\lvert u\rvert_1\) — число единиц в \(u\). Более общо, множество слов \(X\subseteq A^\*\) называется \(\ell\)-сбалансированным, если для любых \(x,y\in X\) одинаковой длины и любой буквы \(a\in A\) выполняется \(\bigl|\lvert x\rvert_a-\lvert y\rvert_a\bigr|\le \ell\). Для бинарных слов обычная сбалансированность — это именно \(1\)-сбалансированность.

Слова Штурма. Бесконечное бинарное слово \(w\) называется словом Штурма, если [ p*w(n)=n+1\quad\text{для всех }n\ge 1. ] Конечное слово называется конечным словом Штурма, если оно является фактором некоторого бесконечного слова Штурма. Для конечных бинарных слов эквивалентно: конечное слово Штурма — это просто конечное сбалансированное слово.

Правоспециальные и биспециальные факторы. Фактор \(u\in F(w)\) называется правоспециальным, если \(u0\) и \(u1\) оба принадлежат \(F(w)\). Аналогично, \(u\) левоспециальный, если \(0u\) и \(1u\) оба являются факторами. Фактор, который одновременно лево- и правоспециальный, называется биспециальным. Именно через такие факторы контролируется приращение сложности \(p*w(n+1)-p*w(n)\).

Механические слова. При \(0<\alpha<1\) и \(0\le \rho\le 1\) нижнее механическое слово задаётся формулой [ s{\alpha,\rho}(n)=\lfloor (n+1)\alpha+\rho\rfloor-\lfloor n\alpha+\rho\rfloor,\qquad n\ge 0, ] а верхнее — [ s'(n)=\lceil (n+1)\alpha+\rho\rceil-\lceil n\alpha+\rho\rceil. ] Это бинарные слова из \(\{0,1\}\); при замене \(0\mapsto a\), \(1\mapsto b\) получаются эквивалентные формулы над \(\{a,b\}\). Если \(\alpha\) иррационально, механические слова в точности являются словами Штурма; если \(\alpha\) рационально, они периодичны. При \(\rho=\alpha\) нижнее и верхнее механические слова совпадают; это характеристическое слово наклона \(\alpha\).

Характеристическое слово и цепная дробь. Если [ \alpha=[0,m1+1,m2,m3,\dots], ] то характеристическое слово \(c*\alpha\) строится как предел стандартной последовательности [ s=1,\qquad s0=0,\qquad s_n=s\quad (n\ge 1). ] Каждое }^{\,m*n}s*{n-2\(s_n\) является префиксом \(s*{n+1}\), поэтому предел существует. Этот рекурсивный способ — основной алгоритмический вход в задачах на конкретные слова Штурма.

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

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

Утверждение. Если для бесконечного слова \(w\) существует \(n\ge 0\) такое, что \(p*w(n+1)=p*w(n)\), то \(w\) в одностороннем случае является в конечном счёте периодическим. Следовательно, если \(w\) апериодично, то \(p\*w(n)\ge n+1\) для всех \(n\ge 1\). В бинарном случае минимально возможная сложность апериодического слова равна \(n+1\).

Доказательство. Рассмотрим граф Рози \(R_n(w)\): его вершины — факторы длины \(n\), а рёбра — факторы длины \(n+1\); ребро \(x*0x*1\cdots x*n\) идёт из вершины \(x*0\cdots x*{n-1}\) в вершину \(x*1\cdots x*n\). У каждой вершины исходящая степень хотя бы \(1\), потому что каждый наблюдаемый фактор длины \(n\) продолжается вправо следующим символом в самом слове. Если \(|E|=|V|\), то сумма исходящих степеней равна числу вершин, значит, каждая вершина имеет исходящую степень ровно \(1\). Поэтому, двигаясь по слову начиная с некоторой позиции, мы каждый раз однозначно переходим к следующей вершине длины \(n\); в конечном графе такая траектория обязательно заходит в цикл и далее уже не может его покинуть. Значит, хвост слова периодичен. Теперь, если слово апериодично, равенство \(p*w(n+1)=p*w(n)\) невозможно ни при каком \(n\); следовательно, \(p*w(n+1)\ge p*w(n)+1\) для всех \(n\). Так как \(p*w(1)\ge 2\), получаем по индукции \(p\*w(n)\ge n+1\).

Лемма о сбалансированном множестве факторов

Ниже под сбалансированным множеством понимается язык \(F(w)\) факторов некоторого бесконечного бинарного слова \(w\), причём слово \(w\) сбалансировано.

Лемма. Для каждого \(n\ge 0\) число факторов длины \(n\) в языке сбалансированного бинарного слова не превосходит \(n+1\): [ p*w(n)\le n+1. ] Эквивалентно, для каждого \(n\) существует не более одного правоспециального фактора длины \(n\).

Доказательство. Предположим, что существуют два различных правоспециальных фактора длины \(n\), скажем \(u\) и \(v\). Возьмём их наибольший общий суффикс \(x\). Тогда \(u=0x\) и \(v=1x\) для некоторого слова \(x\). Так как \(u\) и \(v\) правоспециальны, все четыре слова \(0x0\), \(0x1\), \(1x0\), \(1x1\) являются факторами. Но слова \(0x0\) и \(1x1\) имеют одинаковую длину и отличаются по числу единиц на \(2\), что противоречит сбалансированности. Значит, двух различных правоспециальных факторов одной длины быть не может. Теперь [ pw(n+1)-pw(n)=\sum{u\in Fn(w)}(\deg^+(u)-1), ] где \(\deg^+(u)\) — число правых продолжений фактора \(u\). В бинарном слове \(\deg^+(u)\in\{1,2\}\), и только один фактор может иметь \(\deg^+(u)=2\). Поэтому \(p*w(n+1)-p*w(n)\le 1\). Так как \(p*w(1)\le 2\), по индукции получаем \(p*w(n)\le n+1\).

Эта лемма — верхняя оценка на сложность в сбалансированном случае. В сочетании с нижней оценкой Морса–Хедлунда она сразу даёт одну из главных эквивалентностей темы.

Лемма о небалансности и палиндромная лемма

Лемма о небалансности. Если бинарное слово \(w\) не сбалансировано, то существует слово \(W\) (возможно пустое) такое, что оба слова \(0W0\) и \(1W1\) являются факторами \(w\).

Доказательство. Возьмём два фактора \(A,B\) одинаковой длины с \(|\,|A|_1-|B|1\,|>1\). Рассмотрим разности числа единиц в суффиксах одинаковой длины: [ d_k=|A_k|1-|B_k|1,\qquad d_0=0. ] При увеличении \(k\) на \(1\) величина \(d_k\) меняется не более чем на \(1\), а \(d_s_{|A|}\) по модулю больше \(1\); значит, для некоторого \(k\) имеем \(|d_k|=2\). Выберем такую пару минимальной длины; тогда неизбежно [ A=1W1,\qquad B=0W0. ] Иначе можно было бы убрать общий первый или общий последний символ и получить более короткий контрпример. Лемма доказана.

Палиндромная лемма. Пусть \(w\) — слово Штурма. Если выбрать слово \(W\) минимальной длины так, что \(0W0\) и \(1W1\) являются факторами \(w\), то \(W\) — палиндром.

Доказательство. В слове Штурма ровно одно из слов \(00\), \(11\) встречается как фактор длины \(2\), так как \(p*w(2)=3\) и факторы \(01\), \(10\) обязаны присутствовать. Следовательно, \(W\) не пусто, а его первый и последний символы совпадают: иначе одновременно встретились бы и \(00\), и \(11\). Предположим теперь, что \(W=w*0w*1\cdots w*n\) не палиндром. Возьмём наименьший индекс \(k\), для которого \(w*k\ne w*{n-k}\); без ограничения общности \(w*k=0\), \(w*{n-k}=1\). Тогда из наличия факторов \(0W0\) и \(1W1\) получаются более короткие факторы \(0w*0\cdots w*{k-1}0\) и \(1w*{n-k+1}\cdots w*n1\), снова нарушающие баланс. Это противоречит минимальности выбора \(W\). Следовательно, \(W=\widetilde W\).

Теорема о характеризации слов Штурма через баланс

Теорема. Для бесконечного бинарного слова \(w\) следующие условия эквивалентны:

Это классическая характеристика слов Штурма.

Доказательство, направление “сбалансировано и апериодично \(\Rightarrow\) Штурм”. По лемме о сбалансированном множестве факторов имеем \(p*w(n)\le n+1\) для всех \(n\). По теореме Морса–Хедлунда для апериодического слова \(p*w(n)\ge n+1\). Значит, \(p\*w(n)=n+1\) для всех \(n\ge 1\), то есть \(w\) — слово Штурма.

Доказательство, направление “Штурм \(\Rightarrow\) сбалансировано”. Пусть \(w\) — слово Штурма и, вопреки утверждению, не сбалансировано. По предыдущей лемме существует минимальное \(W\), для которого \(0W0\) и \(1W1\) являются факторами \(w\), а по палиндромной лемме это \(W\) — палиндром. Слова \(0W0\) и \(1W1\) показывают, что \(W\) биспециально. Но при сложности \(p\*w(n)=n+1\) на каждой длине имеется ровно один правоспециальный фактор и ровно один левоспециальный фактор; следовательно, биспециальный фактор данной длины единственен. Далее, ровно одно из слов \(0W\), \(1W\) может быть правоспециальным. Без ограничения общности пусть это \(0W\). Тогда факторы \(0W0\), \(0W1\), \(1W1\) принадлежат языку, а \(1W0\) не принадлежит ему. Зафиксируем вхождение \(1W1\). Из палиндромности \(W\) следует, что никакое вхождение \(0W\) не может начинаться внутри соответствующего блока длины \(2|W|+4\): иначе возникло бы несовместимое перекрытие с разными симметричными символами. Поэтому внутри этого блока имеется \(n+3\) факторов длины \(|W|+2\), но ни один из них не равен \(0W\). Так как общее число факторов этой длины в слове Штурма тоже равно \(n+3\), какой-то фактор повторяется внутри блока. Однако все факторы этой длины, кроме \(0W\), имеют единственное правое продолжение; повтор такого фактора влечёт периодичность хвоста слова, что противоречит апериодичности слова Штурма. Противоречие показывает, что \(w\) сбалансировано.

Следствие. Конечное бинарное слово является конечным словом Штурма тогда и только тогда, когда оно сбалансировано. Это конечная версия предыдущей теоремы.

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

Для бесконечного бинарного слова \(w\) стандартный список эквивалентных или характеристических критериев таков. Если \(w\) задано как механическое слово с иррациональным наклоном \(\alpha\), то оно штурмово; если \(\alpha\) рационально, слово периодично. Два слова Штурма одного и того же наклона имеют один и тот же язык факторов. Характеристическое слово наклона \(\alpha\) можно строить либо через вращение окружности, либо через рекурсию из цепной дроби наклона.

Критерий возвратных слов: бесконечное слово является словом Штурма тогда и только тогда, когда для каждого непустого фактора множество его возвратных слов состоит ровно из двух элементов. Это один из самых удобных критериев в задачах на динамическую реконструкцию языка.

Критерий палиндромной сложности: бесконечное слово является словом Штурма тогда и только тогда, когда число палиндромных факторов длины \(n\) равно \(1\) для чётных \(n\) и \(2\) для нечётных \(n\); эквивалентная запись — [ P(n)+P(n+1)=3. ] В деталях доказательства этого критерия проявляется ещё одно характерное свойство: каждый палиндромный фактор слова Штурма имеет единственное палиндромное продолжение \(apa\).

Для конечных палиндромов полезны два дополнительных факта. Во-первых, конечный бинарный палиндром является штурмовым палиндромом тогда и только тогда, когда он является медианным фактором центрального слова. Во-вторых, конечное центральное слово эквивалентно палиндромному префиксу характеристического слова; его также можно распознать по наличию двух взаимно простых периодов \(p,q\) с длиной \(p+q-2\).

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

Ниже все процедуры рассчитаны на конечный вход. Для бесконечных слов точная проверка “слово Штурма / не слово Штурма” должна опираться на структурное задание слова: механическая формула, цепная дробь наклона, морфизм, возвратные слова или полное описание языка факторов. Для конечных слов достаточно критерия “сбалансированное \(\Longleftrightarrow\) конечное Sturmian”.

Вычисление факторной сложности конечного слова

procedure FactorComplexity(w):
 n:= |w|
 p[0]:= 1 // пустое слово
 for k from 1 to n:
 S:= empty set
 for i from 0 to n-k:
 S.add( w[i.. i+k-1] )
 p[k]:= |S|
 return p

Для ровно такого псевдокода время работы равно \(O(n^2)\) вставок в множество. Если подстроки копируются целиком, стандартная реализация даёт \(O(n^3)\) по байтовой стоимости; с роллинг-хешем или суффиксным автоматом — \(O(n^2)\) по времени и \(O(n^2)\) или лучше по памяти в зависимости от структуры данных. Корректность следует напрямую из определения \(p*w(k)=|F*k(w)|\).

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

procedure IsBalancedBinary(w):
 if alphabet(w) is not subset of s_{0,1}:
 return (False, "не бинарное слово")

 n:= |w|
 pref[0]:= 0
 for i from 0 to n-1:
 pref[i+1]:= pref[i] + (w[i] == '1' ? 1: 0)

 for k from 1 to n:
 minOnes:= +infinity
 maxOnes:= -infinity
 minPos:= -1
 maxPos:= -1

 for i from 0 to n-k:
 ones:= pref[i+k] - pref[i]
 if ones < minOnes:
 minOnes:= ones
 minPos:= i
 if ones > maxOnes:
 maxOnes:= ones
 maxPos:= i

 if maxOnes - minOnes > 1:
 u:= w[minPos.. minPos+k-1]
 v:= w[maxPos.. maxPos+k-1]
 return (False, k, u, v)

 return (True)

Проверка опирается на определение сбалансированности: для каждой длины \(k\) достаточно сравнить минимум и максимум числа единиц среди всех факторов длины \(k\). Время работы — \(O(n^2)\), память — \(O(n)\). Если слово не сбалансировано, процедура сразу возвращает свидетельство \(u,v\) одинаковой длины.

Проверка свойства “конечное слово Штурма”

procedure IsFiniteSturmian(w):
 if alphabet(w) is not subset of s_{0,1}:
 return False
 return IsBalancedBinary(w)

Корректность этой процедуры — прямое следствие теоремы: конечное бинарное слово является конечным словом Штурма тогда и только тогда, когда оно сбалансировано. В задачах это основной практически полезный критерий.

Проверка палиндромичности

procedure IsPalindrome(w):
 i:= 0
 j:= |w|-1
 while i < j:
 if w[i] != w[j]:
 return False
 i:= i + 1
 j:= j - 1
 return True

Эта процедура работает за \(O(|w|)\). Если нужны все палиндромные подслова конечного слова, стандартная линейная процедура — алгоритм Манакера; если задача требует только проверить отдельные кандидаты в стиле “является ли \(W\) палиндромом?”, двух указателей достаточно. В теории Sturmian-палиндромов важно помнить, что у бесконечного слова Штурма палиндромная сложность предписана формулой \(P(n)=1\) для чётных \(n\) и \(P(n)=2\) для нечётных \(n\).

Генерация характеристического слова по цепной дроби

procedure CharacteristicPrefix(m[1..r], L):
 s_minus_1:= "1"
 s_0:= "0"

 if L <= 1:
 return prefix(s_0, L)

 s_prev2:= s_minus_1
 s_prev1:= s_0

 for n from 1 to r:
 s_n:= (s_prev1 repeated m[n] times) + s_prev2
 if |s_n| >= L:
 return prefix(s_n, L)
 s_prev2:= s_prev1
 s_prev1:= s_n

 return prefix(s_prev1, min(L, |s_prev1|))

Если коэффициенты цепной дроби продолжаются бесконечно, цикл просто продолжают, пока текущего слова не хватит для нужного префикса. Корректность следует из рекурсии [ s{-1}=1,\quad s_0=0,\quad s_n=s, ] задающей характеристическое слово }^{m*n}s_{n-2\(c\alpha\) как предел этих префиксов.

Генерация механического слова

procedure LowerMechanical(alpha, rho, N):
 for n from 0 to N-1:
 x[n]:= floor((n+1)*alpha + rho) - floor(n_alpha + rho)
 return x

Если \(\alpha\) рационально, полученное слово периодично; если \(\alpha\) иррационально, это слово Штурма. Аналогично строится верхнее механическое слово с потолками вместо полов.

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

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

Слово Фибоначчи [ f=0100101001001010010\cdots ] соответствует наклону \([0;2,1,1,1,\dots]\). Для первых длин получаем: [ p*f(1)=2,\quad p_f(2)=3,\quad p_f(3)=4,\quad p_f(4)=5, ] а палиндромная сложность начинается так: [ P_f(0)=1,\ P_f(1)=2,\ P_f(2)=1,\ P_f(3)=2,\ P_f(4)=1. ] Это канонический пример слова Штурма. Его стандартные префиксы строятся рекурсией \(s_n=s*{n-1}s\_{n-2}\).

Периодическое, но сбалансированное слово [ u=(01)^\omega = 0101010101\cdots ] сбалансировано, потому что любые два фактора одинаковой длины отличаются по числу единиц не более чем на \(1\). Но оно не является словом Штурма, потому что периодично: для каждого \(n\ge 1\) существуют только два фактора длины \(n\), начинающиеся с \(0\) и с \(1\), значит \(p_u(n)=2\), а не \(n+1\). Это точный контрпример к ложному утверждению “сбалансированность сама по себе уже означает Sturmian”. Отсюда видно, почему в теореме нужно добавлять апериодичность.

*_Конечное сбалансированное слово, которое не является strongly balanced__ Слово \(0110\) сбалансировано, следовательно, это конечное слово Штурма. Но квадрат [ 0110\,0110 ] содержит оба фактора \(00\) и \(11\) длины \(2\), поэтому оно не strongly balanced. Это показывает, что “сбалансированное” и “strongly balanced” — разные свойства.

Sturmian-палиндром, который не является центральным словом Слово \(baab\) является штурмовым палиндромом, но не является центральным. Это стандартный контрпример к обратному утверждению “каждый Sturmian-палиндром центральный”.

Типовая задача

Задача. Вычислить факторную сложность слова \(u=(01)^\omega\) и решить, является ли оно словом Штурма.

Метод. Прямой подсчёт факторов фиксированной длины; затем критерий “сбалансированное и апериодическое”.

Решение. Для любой длины \(n\) существует ровно два фактора: [ 0101\cdots \text{ длины }n,\qquad 1010\cdots \text{ длины }n. ] Других быть не может, потому что слово строго чередуется. Значит, [ p_u(n)=2\quad\text{для всех }n\ge 1. ] Слово сбалансировано: у факторов длины \(n\) число единиц равно либо \(\lfloor n/2\rfloor\), либо \(\lceil n/2\rceil\). Но слово периодично с периодом \(2\), поэтому словом Штурма оно не является. Эквивалентно: уже \(p_u(2)=2<3\), что несовместимо с формулой \(p(n)=n+1\).

Типовая задача

Задача. Проверить, является ли конечное слово [ w=0100101001 ] конечным словом Штурма.

Метод. Критерий “конечное бинарное слово Sturmian \(\Longleftrightarrow\) сбалансировано”; проверка через минимум и максимум числа единиц среди факторов каждой длины.

Решение. Достаточно показать, что для каждой длины \(k\) числа единиц во всех факторах длины \(k\) различаются не более чем на \(1\). Для данного слова получаем следующую таблицу:

Во всех случаях максимум минус минимум не превышает \(1\). Значит, слово сбалансировано. Так как оно бинарно, по критерию конечных слов Штурма это и есть конечное Sturmian-слово. Заметим, что его сложность имеет типичный “трапецеидальный” профиль конечного штурмова слова: [ 2,3,4,5,5,5,4,3,2,1. ] Последняя последовательность уже не является определением, но хорошо служит быстрой самопроверкой после решения.

Типовая задача

Задача. Построить префиксы характеристического слова для наклона [ \alpha=[0;2,1,1,1,\dots]. ]

Метод. Рекурсия стандартных слов по коэффициентам цепной дроби.

Решение. В записи [ \alpha=[0,m1+1,m2,m3,\dots] ] имеем \(m*1=1\), \(m*2=m\*3=\cdots=1\). Поэтому [ s. ] Вычисляем: [ s_1=01,\qquad s_2=010,\qquad s_3=01001,\qquad s_4=01001010,\qquad s_5=0100101001001. ] Каждое слово является префиксом следующего, поэтому предел существует: [ c*\alpha=0100101001001010010\cdots ] Это и есть характеристическое слово Фибоначчи. Так как оно построено из цепной дроби наклона, оно штурмово.}=1,\qquad s_0=0,\qquad s_n=s*{n-1}s_{n-2

Типовая задача

Задача. Доказать, что в слове Штурма ровно одно из слов \(00\) и \(11\) встречается как фактор. Показать, что \(0011\) не может быть конечным словом Штурма.

Метод. Использовать равенство \(p\*w(2)=3\) и рекуррентность.

Решение. У слова Штурма \(p\*w(2)=3\), то есть существует ровно три различных фактора длины \(2\). Так как обе буквы встречаются бесконечно много раз, факторы \(01\) и \(10\) обязательно присутствуют. Остаётся ровно одно место для одного из слов \(00\) и \(11\). Следовательно, одновременно встречаться они не могут. Теперь рассмотрим конечное слово \(0011\). Среди его факторов длины \(2\) уже есть и \(00\), и \(11\). Поэтому \(0011\) не может быть фактором никакого бесконечного слова Штурма, а значит, не является конечным словом Штурма.

Типовая задача

Задача. Найти палиндромную сложность слова Штурма.

Метод. Применить палиндромный критерий.

Решение. Для любого бесконечного слова Штурма [ P(n)= \begin{cases} 1,& n\ \text{чётно},\[2mm] 2,& n\ \text{нечётно}. \end{cases} ] Отсюда сразу: [ P(0)=1,\quad P(1)=2,\quad P(2)=1,\quad P(3)=2,\quad\dots ] Например, для слова Фибоначчи палиндромы малых длин таковы: [ n=2:\ 00;\qquad n=3:\ 010,\ 101;\qquad n=4:\ 1001. ] Эта формула является не просто свойством, а полным критерием штурмовости в бинарном случае.

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

Следующие таблицы суммируют наиболее употребительные критерии и различия между близкими понятиями.

| Понятие | Формальное условие | Что гарантирует | Что не гарантирует | Опорный источник | | ------------------------------------------- | ----------------------------------------------------------- | ---------------------------------------------- | ----------------------------------------------- | ---------------- | ------------------------------ | --- | | Сбалансированное бесконечное бинарное слово | \(\bigl | \lvert u\rvert_1-\lvert v\rvert_1\bigr | \le 1\) для любых равнодлинных факторов \(u,v\) | \(p(n)\le n+1\) | Штурмовость без апериодичности | | | Слово Штурма | \(p(n)=n+1\) для всех \(n\ge 1\) | бинарность, сбалансированность, апериодичность | рациональный наклон | | | Конечное слово Штурма | фактор бесконечного слова Штурма | конечную сбалансированность | strongly balanced | | | Механическое слово | формулы с \(\lfloor\cdot\rfloor\) или \(\lceil\cdot\rceil\) | при иррациональном \(\alpha\): штурмовость | при рациональном \(\alpha\): апериодичность | | | Критерий возвратных слов | у каждого непустого фактора ровно 2 возвратных слова | штурмовость | не применим напрямую к конечному слову | | | Палиндромная сложность | \(P(n)=1\) при чётных \(n\), \(P(n)=2\) при нечётных \(n\) | штурмовость | центральность каждого палиндрома | |

Связи между основными критериями можно держать в памяти в виде следующей схемы.

Структура доказательства направления “минимальная сложность \(\Rightarrow\) баланс” сводится к одной короткой цепочке.

Конструкция характеристического слова по цепной дроби наклона выглядит так.

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

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

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

• Symbolic Dynamics (1938) и Symbolic Dynamics II: Sturmian Trajectories (1940) — исходные статьи по теореме Морса–Хедлунда и по Sturmian trajectories.
• Sequences with Minimal Block Growth (1973) — классическая работа о минимальном росте блочной сложности.
• Sturmian words: structure, combinatorics, and their arithmetics (1997) — центральные и стандартные слова, палиндромная левозамыкаемость, связь с числами Фарея.
• Palindromes and Sturmian words (1999) — палиндромная сложность и палиндромные расширения в бинарном штурмовом случае.
• A Characterization of Sturmian Words by Return Words (2001) — точный критерий через возвратные слова.
• Balanced words (2003) — обзор по сбалансированным словам как самостоятельному объекту.

Учебники, обзоры и русскоязычные материалы

• *_Combinatorics on Words__ — классический базовый учебник по комбинаторике слов.
• *_Algebraic Combinatorics on Words_ — особенно глава _Sturmian Words, где собраны базовые эквивалентные определения и конструкции.
• *_Substitutions in Dynamics, Arithmetics and Combinatorics__ — стандартный источник по подстановкам, динамике и связанным классам бесконечных слов.
• Sturmian and Episturmian Words — компактный современный обзор с удобными формулировками критериев для конечных и бесконечных слов.
• Русскоязычная лекция Слова Штурма — удобна для стандартной последовательности, цепных дробей и примера слова Фибоначчи.
• Русскоязычный обзор Комбинаторика слов, фактординамика и нормальные формы — удобен для обозначений \(T_n(w)\), формулировки теоремы “Штурм \(\Leftrightarrow\) сбалансированность + непериодичность” и связи с графами Рози.