Двоичные слова низкой сложности, избегающие $(5/2)^+$-степеней

Основная информация

• ID статьи: 2506.19050
• Название: Low complexity binary words avoiding $(5/2)^+$-powers
• Авторы: James Currie, Narad Rampersad
• Классификация: math.CO (комбинаторика), cs.FL (формальные языки)
• Дата публикации: 13 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2506.19050

Аннотация

Последовательности Роте — это бесконечные последовательности, содержащие ровно $2n$ факторов длины $n$ для каждого $n \geq 1$. Шаллит и Шур, а также Олингер и Шаллит доказали существование последовательностей Роте, избегающих $(5/2)^+$-степеней, и что это оптимально. В данной работе приводится структурная теорема для последовательностей Роте, избегающих $(5/2)^+$-степеней, подтверждающая гипотезу Олингера и Шаллита.

Исследовательский контекст и мотивация

Основная проблема

Исследование сосредоточено на двух фундаментальных концепциях теории комбинаторных слов: избегании степеней и факторной сложности. Конкретно решается задача: охарактеризовать все двоичные бесконечные последовательности, избегающие $(5/2)^+$-степеней и обладающие минимальной сложностью ($2n$).

Значимость проблемы

1. Теоретическое значение: Избегание степеней и факторная сложность являются фундаментальными концепциями теории комбинаторных слов, их взаимосвязь — центральное направление исследований в этой области
2. Структурная теория: Подобно классической структурной теореме Рестиво-Салеми о словах без перекрытий, данное исследование устанавливает новую структурную теорему
3. Проверка гипотезы: Подтверждает важную гипотезу Олингера и Шаллита о структуре последовательностей Роте

Ограничения существующих исследований

• Хотя Шаллит и Шур, а также Олингер и Шаллит доказали существование и оптимальность последовательностей Роте, избегающих $(5/2)^+$-степеней, полная структурная характеризация отсутствовала
• Существующие работы предоставляют только конкретные примеры конструкций без общей структурной теоремы

Исследовательская мотивация

Установить полную структурную теорему, аналогичную теореме Рестиво-Салеми для характеризации двоичных слов без перекрытий, чтобы обеспечить теоретическую основу для понимания свойств избегания степеней в последовательностях низкой сложности.

Основные вклады

1. Введены концепции собственных и антисобственных последовательностей: Определены два важных подкласса троичных последовательностей
2. Установлена первая структурная теорема: Охарактеризована рекурсивная структура собственных и антисобственных последовательностей
3. Доказана вторая структурная теорема: Полностью охарактеризована структура последовательностей Роте, избегающих $(5/2)^+$-степеней
4. Подтверждена гипотеза Олингера-Шаллита: Предоставлена полная структурная характеризация с участием морфизмов $f$ и $g$
5. Предоставлена вычислительная верификация: Через поиск с возвратом проверена корректность ключевых лемм

Подробное описание методов

Определение задачи

Входные данные: Двоичная бесконечная последовательность $w$Ограничения:

1. $w$ — последовательность Роте (факторная сложность $2n$)
2. $w$ избегает $(5/2)^+$-степеней

Выходные данные: Структурная характеризация $w$, то есть доказательство того, что $w$ может быть представлена как применение специфических морфизмов к собственной или антисобственной последовательности

Ключевые определения

Собственные и антисобственные последовательности

Для троичной последовательности $u \in \Sigma_3^*$ определим вектор Парика $\pi(u) = [|u|_0, |u|_1, |u|_2]$.

Собственные последовательности удовлетворяют:

1. Не содержат фактор $xyxyx$, где $\pi(x) > \pi(y)$
2. Не содержат факторы: $00, 11, 22, 20, 10101, 2121, 10210210$

Антисобственные последовательности: Их обратная последовательность является собственной

Ключевые морфизмы

Определим морфизмы $f: \Sigma_3^* \to \Sigma_3^*$ и $h: \Sigma_3^* \to \Sigma_3^*$:

• $f(0) = 0121$, $f(1) = 021$, $f(2) = 01$
• $h(0) = 1210$, $h(1) = 120$, $h(2) = 10$

Определим морфизм $g: \Sigma_3^* \to \Sigma_2^*$:

• $g(0) = 011$, $g(1) = 0$, $g(2) = 01$

Основные технические методы

1. Метод факторного анализа

Посредством детального анализа факторов длины 4, которые должны содержаться в двоичных последовательностях, избегающих $(5/2)^+$-степеней, определены фундаментальные структурные ограничения этого класса последовательностей.

Ключевые леммы:

• Лемма 1: Любая бесконечная двоичная последовательность, избегающая $(5/2)^+$-степеней, должна содержать факторы $0110$ и $1001$
• Лемма 3: Последовательность с факторной сложностью $\leq 2n$, избегающая $(5/2)^+$-степеней, должна содержать факторы $0011$ и $1100$

2. Вычислительная верификация поиском с возвратом

Использована компьютерная программа для проверки ключевых лемм; посредством конструктивного доказательства определена необходимость ограничивающих условий.

3. Анализ рекурсивной структуры

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

Экспериментальная установка

Метод вычислительной верификации

В статье использована реализация на Python алгоритма поиска с возвратом для проверки ключевых лемм:

def fhpf(w): # Проверка, избегает ли последовательность w степеней 5/2+
    p=1
    while (5*p<2*len(w)):
        if (w[(-(p+1)//2)-p:]==w[(-(p+1)//2)-2*p:-p]):
            return(False)
        p=p+1
    return(True)

Содержание верификации

1. Верификация леммы 1: Максимальная длина последовательности, не содержащей $0110$ и избегающей $(5/2)^+$-степеней, равна 14
2. Верификация леммы 2: Проверено, что по крайней мере 3 элемента из множества $C = \{0010, 0100, 1011, 1101\}$ должны появиться
3. Верификация леммы 3: Проведена детальная проверка каждого элемента из множества $A$
4. Верификация леммы 4: Проверены ограничивающие условия для 17 специфических последовательностей длины 9

Результаты экспериментов

Основные результаты

Теорема 1 (Первая структурная теорема)

1. Для собственной последовательности $u \in \Sigma_3^{\omega}$ некоторый её суффикс имеет вид $f(v)$, где $v$ — собственная последовательность
2. Для антисобственной последовательности $u \in \Sigma_3^{\omega}$ некоторый её суффикс имеет вид $h(v)$, где $v$ — антисобственная последовательность

Теорема 2 (Вторая структурная теорема)

Последовательность Роте $w$, избегающая $(5/2)^+$-степеней, имеет четыре случая, множества факторов длины 4 которых соответственно:

1. $F = \{0110, 1001, 0011, 1100, 0010, 0100, 1101, 1010\}$
2. $\bar{F}$ (дополнение $F$)
3. $F^R$ (обратная последовательность $F$)
4. $\overline{F^R}$ (дополнение обратной последовательности $F$)

В каждом случае некоторый суффикс $w$ может быть представлен в виде $g(f^n(u))$ или $g(h^n(u))$, где $u$ — собственная последовательность.

Результаты вычислительной верификации

• Максимальная длина последовательности, не содержащей $0110$ и избегающей $(5/2)^+$-степеней: 14
• Максимальная длина последовательности, не содержащей двух элементов из $C$: 44
• Максимальная длина последовательности, не содержащей $0011$ и некоторого элемента из $A$: 31
• Максимальные длины последовательностей при различных ограничивающих условиях находятся в ожидаемых диапазонах

Связанные работы

Классические результаты

1. Теорема Рестиво-Салеми: Охарактеризована структура двоичных слов без перекрытий с использованием морфизма Туэ-Морса
2. Теория последовательностей Штурма: Последовательность Фибоначчи избегает $(5+\sqrt{5})/2$-степеней, что является оптимальным результатом среди последовательностей Штурма

Недавний прогресс

1. Работа Шаллита-Шура: Установлена исследовательская база для связи между избеганием степеней и факторной сложностью
2. Работа Олингера-Шаллита: Построены конкретные примеры последовательностей Роте, избегающих $(5/2)^+$-степеней
3. Работа Дворжаковой и др.: Доказано, что $g(f^{\omega}(0))$ избегает $(5/2)^+$-степеней и является последовательностью Роте

Вклад данной работы

Статья предоставляет полную структурную теорему, занимающую положение, аналогичное теореме Рестиво-Салеми в теории слов без перекрытий, заполняя теоретический пробел.

Заключение и обсуждение

Основные выводы

1. Полная характеризация: Предоставлена полная структурная характеризация всех последовательностей Роте, избегающих $(5/2)^+$-степеней
2. Подтверждение гипотезы: Верифицирована гипотеза Олингера-Шаллита о действии морфизмов $f$ и $g$
3. Методологическое новшество: Комбинирование комбинаторных рассуждений и вычислительной верификации обеспечивает строгое доказательство

Ограничения

1. Вычислительная зависимость: Некоторые ключевые леммы зависят от компьютерной верификации; хотя результаты надёжны, отсутствует чисто теоретическое доказательство
2. Специфический показатель: Результаты применимы только к $(5/2)^+$-степеням; обобщение на другие показатели требует дальнейших исследований
3. Двоичное ограничение: Основные результаты сосредоточены на двоичных последовательностях; случай троичных последовательностей остаётся открытым

Направления будущих исследований

1. Троичное обобщение: Исследование связи между сложностью $2n+1$ и избеганием степеней в троичных последовательностях
2. Другие показатели: Изучение структуры последовательностей низкой сложности, избегающих степеней с другими показателями
3. Алгоритмические приложения: Применение структурной теоремы к алгоритмам генерации и распознавания последовательностей

Глубокая оценка

Преимущества

1. Теоретическая полнота: Предоставлена полная структурная характеризация, решающая важную открытую проблему
2. Методологическая строгость: Комбинирование теоретического анализа и вычислительной верификации обеспечивает надёжное доказательство
3. Техническое новшество: Концепции собственных и антисобственных последовательностей обладают оригинальностью
4. Практическая ценность: Структурная теорема предоставляет теоретические инструменты для конструирования и анализа связанных последовательностей

Недостатки

1. Сложность доказательства: Доказательства некоторых лемм зависят от обширного анализа случаев; возможны более элегантные методы
2. Вычислительная верификация: Ключевые этапы зависят от компьютерного поиска, что снижает теоретическую чистоту
3. Обобщаемость: Возможность обобщения результатов на другие параметры или алфавиты недостаточно ясна

Влияние

1. Теоретический вклад: Предоставляет новую структурную теорему для теории комбинаторных слов, обладающую значительной теоретической ценностью
2. Методологическое значение: Демонстрирует эффективность комбинирования теоретического анализа и вычислительной верификации
3. Последующие исследования: Предоставляет новые идеи и инструменты для исследования связанных проблем

Области применения

1. Теоретические исследования: Исследования в теории комбинаторных слов и теории формальных языков
2. Анализ последовательностей: Конструирование и анализ бесконечных последовательностей со специфическими свойствами
3. Проектирование алгоритмов: Алгоритмы генерации последовательностей, избегающих специфических паттернов

Библиография

Статья цитирует важные работы в этой области, включая:

• Классическую структурную теорему Рестиво и Салеми о словах без перекрытий
• Пионерскую работу Шаллита и Шура о связи между избеганием степеней и сложностью
• Последние исследования Олингера и Шаллита о пороге повторяемости последовательностей Роте
• Классические результаты Карпи и де Луки о последовательностях Штурма

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