1.4. Решение проблемы бесквадратности

Теперь обратимся к проблеме построения бесквадратного ω-слова над алфавитом из трех букв. Фактически мы можем вывести основное утверждение из уже доказанной теоремы 1.5. Это оказывается возможным благодаря применению одного полезного и весьма распространенного в теории формальных языков приема, состоящего в группировке нескольких букв в одну. С помощью этого приема прежде всего докажем следующую лемму.

Лемма 1.6. Существует бесквадратное ω-слово β над алфавитом из четырех символов.

Доказательство. Рассмотрим ω-слово α из теоремы 1.5. Определим новый алфавит ∑₁ следующим образом;

Используя выражение (1.7) для α, определим над алфавитом ∑₁ ω-слово

полагая

Предположим, что y² входит в качестве подслова в β, т. е.

Следовательно,

Это означает, что c_j+1 = c_j+t+1 = c_j+2t+1 и c_j+n = c_j+t+n для 1≤n≤t. Значит, (c_j+1 ... c_j+t)²c_j+1 входит в качестве подслова в α, что противоречит теореме 1.5. Следовательно, β бесквадратно. ▫

Усилим лемму 1.6 до желаемого результата. Для этого удобно ввести новые обозначения для элементов ∑₁, положив

Теперь начало β примет вид

(сравните с (1.6)). По определению β перед символом 1 должен стоять символ 1 или 3. Однако если перед символом 1 стоит он же, то a³ входит в качестве подслова в α, что невозможно в силу леммы 1.3. Значит, в β перед символом 1 всегда стоит символ 3. Точно так же выводятся остальные утверждения следующей леммы.

Лемма 1.7. В β символу 1 всегда предшествует символ 3, а за символом 1 всегда следует символ 2. Символу 4 всегда предшествует символ 2, а за символом 4 всегда следует символ 3.

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

Теорема 1.8. Существует бесквадратное ω-слово γ над алфавитом из трех символов.

Доказательство. Рассмотрим алфавит ∑₂ = {1,2,3}. Определим ω-слово у как результат замены в β всех вхождений символа 4 символом 1. Таким образом, начало γ будет иметь вид

Покажем, что γ является бесквадратным.

Предположим противное: пусть xx входит в качестве подслова в γ, причем x непусто. Отсюда следует, что β содержит подслово y₁y₂, такое, что |y₁| = |y₂| = |x| = t, и, кроме того, y₁ и y₂ совпадут, если заменить в них все вхождения символа 4 символом 1.

Прежде всего заметим, что t≥2, так как в силу леммы 1.7 ни одно из слов 11, 14, 41, 44 не входит в качестве подслова в β.

Пусть в обозначениях (1.14)

Тогда для любого n, удовлетворяющего неравенствам 1≤n≤t, имеем d_j+n = d_j+n+t, за исключением случая, когда один из символов d_j+n и d_j+n+t есть 1, а другой 4. Мы докажем, что этот исключительный случай в действительности невозможен.

Рассмотрим сначала фиксированное значение n, удовлетворяющее неравенствам 1≤n<t. Если d_j+n есть 1 (соответственно 4), то в силу леммы 1.7 d_j+n+1 есть 2 (соответственно 3). Следовательно, по нашему допущению относительно y₁ и y₂, d_j+n+1+t тоже есть 2 (соответственно 3). Далее, еще раз применив лемму 1.7, получим

Обратимся теперь к символам d_j+t и d_j+2t и в нашем доказательстве, основанном на лемме 1.7, вместо последующих символов будем рассматривать предыдущие. Если d_j+t есть 1 (соответственно 4), то d_j+t-1 есть 3 (соответственно 2). Значит, d_j+t = d_j+2t. Из последнего равенства и (1.15) следует, что (d_j+1 ... d_j+t)² входит в качестве о том, что xx входит в γ в качестве подслова, неверно, и тем самым теорема 1.8 доказана.▫

Подведем итог полному решению проблемы Туэ в следующей теореме.

Теорема 1.9. Если ∑ состоит не менее чем из трех символов, то над ∑ существует бесквадратное ω-слово. Если ∑ состоит из двух символов, то над ∑ существует сильно бескубное ω-слово, но не существует бесквадратных слов, имеющих длину более 3.

Мы хотим подчеркнуть, что в формулировке предыдущей теоремы выражение "существует" фактически означает, что искомое ω-слово может быть эффективно построено: используя (1.5), мы можем вычислить любой символ в α, β, γ. За немногими исключениями,и другие доказательства теории формальных языков дают метод построения искомых объектов.