Групповая сложность бесконечных слов

Перейдем к результатам работы. Следующая теорема говорит о том, что действительно существуют слова, для которых можно для любой длины получить все значения между абелевой сложностью и факторной сложностью, и примером слов, удовлетворяющих это­му свойству, являются слова Штурма.
Теорема 1. Для любого слова Штурма, для любой длины n 2 N для любого t, 2 6 t 6 n + 1, можно подобрать такую подгруппу G группы перестановок Sn, что pG(n) = t.
Доказательство. Рассмотрим слово Штурма и и произвольное натуральное число n 2 N. Выпишем все факторы длины n в лексикографическом порядке. Как было написано в предыдущем разделе, последовательные факторы v,v' могут иметь только вид либо v = А01ц, v' = А10ц для каких-то, возможно, пустых, А,ц, либо v = X0,v' = А1.
Возьмем m :0 6 m < n — 1. Рассмотрим группу G, которая оставляет на месте первые m букв и полностью переставляет остальные буквы. Эта группа будет порождаться пере­становками ((1)... (m)(m + 1 m + 2), (1)... (m)(m + 1 m + 2 ... n)). Действительно, группа Sk порождается перестановками ((12), (12 ...k)), потому что (12 ... k)z (12)(12 ... k)-i = (i + 1, i + 2), а транспозициями такого вида можно породить S/,..
Рассмотрим префиксы факторов слова и. Мы знаем, что среди префиксов длины m ровно m + 1 различных. Значит, pG(n) > m + 1. Покажем индукцией по m, что она равна m + 2.
Для m = 0 это действительно так — мы получаем просто действие Sn . Сложность относительно Sn — это абелева сложность. Для слов Штурма она равна 2, это как раз m + 2 при m = 0. Посмотрим, что происходит при переходе от длины префикса m к длине m +1. Рассмотрим два случая.
В первом случае у двух последовательных (по лексикографическому порядку) факто­ров v,v' префиксы остается одинаковыми, v = uw,v' = uw'. Тогда они разделяются на два класса только в случае, когда v = А0, v' = А1, причем такое разделение происходило и при длине m и на увеличение количества классов при переходе с одной длины на другую не влияет. Иначе в их суффиксах одинаковое количество нулей и единиц, потому что они представимы в виде v = uA01^,v' = иА10ц, а группа G полностью переставляет буквы в суффиксе и поэтому на количество классов, которые могут получиться под её действием, влияет только количество нулей.
Во втором случае v = Л01д, v0 = Л10д, |Л| = т. Тогда при переходе от т к т+1 у слова v префикс длины т будет иметь на одну единицу меньше, чем префикс слова v0, и поэтому слова v, v0 попадают в два разных класса под действием G. Такое происходит ровно для одной пары слов, поэтому количество классов увеличивается на один и становится m + 3 = (m + 1) + 2.
Таким образом, для любого t : 2 6 t 6 п + 1 можно найти группу G, для которой pG(n) = t. □
Следующая теорема, наоборот, говорит о том, что существуют слова, для которых нель­зя получить все значения между абелевой сложностью и факторной сложностью для бесконечного числа длин.
Теорема 2. Пусть слово x замкнуто относительно инверсии. Тогда p!(п) может при­нимать только четные значения для любых ! при нечетных значениях п.
Доказательство. Пусть x — слово, замкнутое относительно инверсии. Зафиксируем неко­торое нечетное число п и некоторую группу Gn.
Во-первых, заметим, что у слова x будет четная факторная сложность. Можно за­метить, что факторы x разбиваются на два класса — бедные, число единиц в которых меньше П, и богатые, число единиц в которых больше П• Так как п нечетно, факторов с ПП единиц не будет. Обозначим бедные классы как Pn (от англ. poor), а богатые как Rn (от англ. rich). Так как слово x замкнуто относительно инверсии, а п — нечетное, то для каждого и из Pn слово и тоже будет фактором x, при этом оно будет лежать в множестве Rn. Аналогично для любого v из Rn — v лежит в Pn. Мы построили биекцию между Pn и Rn, а других факторов длины п в x нет, так как п нечетное. Значит, pn(x) — четное при нечетном п.
Аналогичное рассуждение можно применить для групповой сложности. Рассмотрим классы эквивалентности факторов слова x относительно Gn. Понятно, что для любых и 2 Pn и v 2 Rn слово и не эквивалентно слову v относительно Gn — в них заведомо разное число нулей и единиц, и никакая перестановка не может их приравнять. Пусть теперь u,v 2 Pn, и пусть для какого-то g 2 Gn выполняется g(u) = v. Тогда и g(u) = v, причем u, v 2 Rn — понятно, что после инверсии эта перестановка так же переводит одно слово в другое. Значит, каждому классу эквивалентности из Pn соответветствует класс эквивалентности из Rn и наоборот, а других классов нет в силу нечетности п. □
Слов и классов слов, удовлетворяющих такому свойству, довольно много. Из известных слов, например, таким свойством обладает слово Туэ-Морса. Как уже было доказано выше, оно замкнуто относительно инверсии.
Следствие 1. Групповая сложность слова Туэ-Морса принимает только четные зна­чения при нечетных п.

Купить