1.3. Решение проблемы сильной бескубности

Рассмотрим DOL-систему G =({a, b}, h, a), где морфизм h определяется следующим образом: h(a) = ab, h(b) = ba. Тогда последовательность S(G) начинается словами

Вообще, для всех i≥1 (i+1)-е слово w_i+1 последовательности S(G) удовлетворяет равенству

где через x' обозначается слово, которое получается из слова x заменой всех a и b и наоборот.

Докажем равенство (1.5) по индукции. При i=1 оно очевидно. Переход от i к i+1 выглядит так:

где последнее равенство выполняется, так как h(x') = (h(x))' для всех x по определению h.

Пусть теперь α есть ω-слово, порожденное DOL-системой G. Мы хотим доказать, что а является сильно бескубным. Заметим, что равенство (1.5) дает удобный способ написания произвольно длинного начала ω-слова α. Используя группировку, представленную в (1.5) получаем сверхслово

Таким образом, (1.6) - это некоторое начало ω-слова α. Пробелы использованы только для того, чтобы было ясно, где приписывается новое w_i'.

Для доказательства основной теоремы нам понадобятся некоторые свойства ω-слова α. Будет полезно записывать α также в виде

где каждое c_j - либо a, либо b.

Лемма 1.3. Ни a³, ни b³ не входят в качестве подслова в α. Ни ababa, ни babab не входят в качестве подслова в α. Следовательно, любое подслово x ω-слова α, такое, что |x| = 5, содержит в качестве подслова либо a², либо b².

Доказательство. Докажем первое утверждение. Если слово a³ или b³ входит в качестве подслова в α, то оно входит в качестве подслова в некоторое w_i. Но это невозможно, так как w_i = h(w_i-1) и, следовательно, w_i получено приписыванием слов ab и ba в некотором порядке.

Докажем второе утверждение. Предположим, что ababa входит в качестве подслова в ω-слово α, начиная с j-й его буквы. Тогда, используя обозначения (1.7), запишем

Выберем настолько большое i, что |w_i|≥j+4. Тогда вхождение (1.8) целиком лежит в w_i. Еще раз используя соотношение w_i = h(w_i-1), заключаем, что в w_i-1 в качестве подслова входит либо a³, либо b³ в зависимости от того, является ли j в (1.8) нечетным или четным. Но это невозможно в силу доказанного выше первого утверждения леммы. Таким же способом (или воспользовавшись соображениями симметрии) можно убедиться в том, что babab не входит в α.

Наконец, последнее утверждение является следствием второго, так как, за исключением слов ababa и babab, любое слово длины 5 над {a, b} содержит в качестве подслова a² или b².▫

Лемма 1.4. Предположим, что a² или b² входит в качестве подслова в α, начиная с j-й буквы; тогда j четно.

Доказательство. Используя обозначения (1.7), предположим, что c_jc_j+1 есть a² или b². Вновь выбираем такое i, что |w_i|≥j+1, и применяем соотношение w_i = h(w_i-1). В силу этого соотношения, если j нечетно, то c_jc_j+1 есть либо h(a), либо h(b). Так как ни h(a), ни h(b) не есть a² или b², лемма доказана.▫

Теперь мы можем доказать основную теорему.

Теорема 1.5. ω-слово а является сильно бескубным.

Доказательство. Вновь рассуждая от противного, предположим, что xxc, где c - первая буква x, есть подслово слова а и что никакое слово yyd, где d - первая буква y и |y|<|x|, не является полсловом слова α. (Иначе говоря, ххс - кратчайший возможный контрпример к теореме 1.5.) Если |x| = 1 или |x| = 2, то одно из слов a³, b³, ababa, babab входит в качестве подслова в α. Так как в силу леммы 1.3 это невозможно, заключаем, что

Предположим, что рассматриваемое вхождение xxc начинается с j-й буквы α. Тогда в обозначениях (1.7) имеем

По лемме 1.3 и (1.9) или a², или b² входит в качестве подслова в xx. Из этого следует, что или a², или b²дважды входит в качестве подслова в xxc. Действительно, a² или b² должно входить в качестве подслова или в x, или в xc. В обоих случаях оно дважды входит в xxc. Теперь из леммы 1.4 можно вывести, что |x|=t является четным числом. Действительно, если бы t было нечетным, то хотя бы одно из вхождений a² или b² в xxc должно было бы начинаться с k-й буквы α при некотором нечетном k. Но это невозможно в силу леммы 1.4.

Следовательно, t = 2u для некоторого натурального числа u. Предположим сначала, что j в (1.10) четно и, следовательно, j≥2. Применяя наш обычный прием, т. е. выбирая достаточно большое число i (такое, что |w_i|≥j+2t) и используя соотношение w_i = h(w_i-1), получаем, что

Поскольку j+t четно, отсюда следует, что

Согласно (1.10) c_j = c_j+t. Из последнего равенства и равенств (1.11), (1.12) вытекает, что c_j-1 = c_j-1+t. Следовательно,

Для 0≤n≤1 слово c_j-1+2nc_j+2n есть либо h(a), либо h(b). Это следует из соотношения w_i = h(w_i-1) и нечетности числа j-1.

Теперь в силу (1.13) заключаем, что w_i-1 содержит подслово yyd, где d - первая буква слова y и |y| = t/2 = u. Следовательно, α содержит yyd в качестве подслова. Но это противоречит выбору x. Нам осталось рассмотреть случай, когда j в (1.10) до буквы c_j+2t+1 вместо c_j-1. Так как числа j+t и j+2t нечетны, слова c_j+tc_j+t+1 и c_j+2tc_j+2t+1 имеют вид либо h(a), либо h(b), как это было в (1.11) и (1.12). Следовательно, из равенства c_j+t = c_j+2t вытекает равенство c_j+t+1 = c_j+2t+1. Значит,

Так же как и в предыдущем случае, отсюда следует, что α содержит подслово yyd, где d - первая буква слова y и |y| = u, что снова противоречит выбору x. Мы показали, что α является сильно бескубным ω-словом над алфавитом {a, b}, и тем самым завершили доказательство теоремы 1.5.▫