Константа Трибоначчи и конечные автоматы

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

• ID статьи: 2510.10834
• Название: The Tribonacci constant and finite automata
• Автор: Jeffrey Shallit (University of Waterloo)
• Классификация: cs.FL cs.DM math.NT
• Дата публикации: 21 октября 2025 г. (препринт arXiv)
• Ссылка на статью: https://arxiv.org/abs/2510.10834

Аннотация

В данной статье доказано, что не существует автомата, способного параллельно принимать представления n и x в системе Трибоначчи, где ψ = 1.839··· — константа Трибоначчи, x = ⌊nψ⌋. Аналогично, не существует автомата Трибоначчи, способного генерировать характеристическую последовательность Штурма с наклоном ψ-1.

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

Предпосылки проблемы

1. Успешный случай Фибоначчи: Для золотого сечения φ = (1+√5)/2 последовательность (⌊φn⌋)_{n≥0} является синхронной по Фибоначчи, то есть существует конечный автомат, который параллельно принимает представления n и x в системе Цекендорфа тогда и только тогда, когда x = ⌊φn⌋.
2. Естественное обобщение: Существуют ли аналогичные свойства для обобщений чисел Фибоначчи (например, чисел Трибоначчи)?
3. Пересечение теории чисел и теории автоматов: Данная проблема связывает глубокие свойства иррациональных чисел из теории чисел с теорией конечных автоматов из теоретической информатики.

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

• Исследование того, сохраняется ли распознаваемость автоматами при переходе от рекуррентных соотношений второго порядка (Фибоначчи) к третьему порядку (Трибоначчи)
• Понимание фундаментальных различий между рекуррентными последовательностями высокого порядка и конечными автоматами
• Обеспечение теоретической базы для связанных проблем логической теории и разрешимости

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

1. Главный отрицательный результат: Доказано, что последовательность (⌊ψn⌋)_{n≥0} не является синхронной по Трибоначчи, где ψ — константа Трибоначчи
2. Неавтоматичность последовательностей Штурма: Доказано, что соответствующая характеристическая последовательность Штурма не является автоматной по Трибоначчи
3. Влияние на логическую теорию: Доказано, что отображение n → ⌊ψn⌋ не может быть выражено в теории первого порядка ⟨N,+,V'(n)⟩
4. Глубокие математические выводы: Выявлены фундаментальные различия между случаями второго и третьего порядков, заключающиеся в отсутствии периодичности

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

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

Исследование двух классов проблем автоматов:

1. Синхронные автоматы: Принимают функцию f: N → N, параллельно обрабатывая входные данные n и x (представление Трибоначчи), принимают тогда и только тогда, когда x = f(n)
2. Выходные автоматы (DFAO): Вычисляют последовательность (a_n)_{n≥0}, на входе получают представление n в системе Трибоначчи, на выходе дают a_n

Основные математические конструкции

Свойства чисел Трибоначчи

• Рекуррентное соотношение: T_i = T_ + T_ + T_, начальные значения T_0 = 0, T_1 = 1, T_2 = 1
• Замкнутая форма: T_n = c_1ψ^n + c_2α^n + c_3β^n
• где ψ ≈ 1.839 — действительный корень уравнения X³ - X² - X - 1 = 0, α, β — комплексно сопряженные корни

Ключевые технические конструкции

Определения:

• a(n) = ⌊ψn⌋
• b(n) = ⌊(ψ-1)(n+2)⌋ - ⌊(ψ-1)(n+1)⌋
• c(n) = ⌊ψ(n+1)⌋ - ⌊ψn⌋

Стратегия доказательства

Основной подход доказательства

1. Редукционный аргумент: Доказывается, что если a(n) синхронна, то b(n) автоматна
2. Различение состояний: Конструируется бесконечно много различимых состояний автомата
3. Применение теоремы Майхилла-Нероде: Использование различения состояний для доказательства несуществования конечного автомата

Ключевой математический анализ

Использование свойств дробной части:

{ψT_n} = {2Re c_2(ψ-α)α^n}

где:

• γ = arg c_2(ψ-α) = 2.536155···
• ζ = arg α = 4.10695···
• значение c(T_n) зависит от v(n) := γ + nζ mod 2π

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

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

Статья содержит в основном теоретические доказательства с использованием методов верификации:

1. Численные вычисления: Верификация точных значений комплексных коэффициентов и параметров
2. Применение теоремы Кронекера: Доказательство свойств плотности
3. Верификация линейной независимости: Подтверждение линейной независимости ζ и 2π над рациональными числами

Вычисление ключевых параметров

• |c_2(ψ-α)| = 0.608085···
• |α| = 0.73735···
• Верифицировано, что |2Re c_2(ψ-α)α^n| < 2-ψ для n ≥ 5

Экспериментальные результаты

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

Завершение доказательства теоремы 1

Доказано:

1. Последовательность (a(n))_{n≥0} не является синхронной по Трибоначчи
2. Последовательность (b(n))_{n≥0} не является автоматной по Трибоначчи

Конструктивное доказательство различения состояний

• Для всех i < j существует k такое, что c(T_{i+k}) ≠ c(T_{j+k})
• Применение теоремы Кронекера гарантирует существование бесконечно многих таких k
• Успешно построено бесконечно много различимых состояний

Результаты логической теории

Теорема 2

Доказано, что отображение n → ⌊ψn⌋ не может быть выражено в теории первого порядка ⟨N,+,V'(n)⟩, где V'(n) — минимальное число Трибоначчи в представлении n.

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

Известные результаты для случая Фибоначчи

• Mousavi и др., а также Hieronymi независимо доказали, что n → ⌊φn⌋ выразимо в соответствующей структуре
• Khani и Zarei получили аналогичные результаты альтернативными методами
• Аналогичные свойства справедливы для произвольных квадратичных иррациональных чисел

Теория числовых систем

• Теория представления Цекендорфа
• Теория представления обобщенных последовательностей Фибоначчи
• Исследования, связанные с числами Пизано

Выводы и обсуждение

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

1. Фундаментальные различия: Существуют существенные различия между случаями Фибоначчи и Трибоначчи
2. Отсутствие периодичности: Знак F_{n+1} - φF_n периодичен, но знак T_{n+1} - ψT_n не периодичен
3. Существование приближенных результатов: Хотя точные результаты недостижимы, существуют автоматы-приближения с ошибкой в пределах ±1

Ограничения

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

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

1. Другие числа Пизано: Исследование числовых систем, основанных на других кубических числах Пизано
2. Обобщение на более высокие порядки: Рассмотрение случаев k-порядковых рекуррентных последовательностей
3. Приближенные алгоритмы: Улучшение точности и эффективности приближенных автоматов

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

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

1. Теоретическая глубина: Выявлены фундаментальные влияния порядка рекуррентного соотношения на распознаваемость автоматами
2. Техники доказательства: Искусное сочетание комплексного анализа, теории чисел и теории автоматов
3. Полнота: Не только доказаны основные результаты, но и проанализировано влияние на логическую теорию
4. Математическая строгость: Доказательства строгие, вычисления точные

Недостатки

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

Влияние

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

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

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

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

Статья цитирует 17 важных работ, охватывающих:

• Классические учебники по теории автоматов (Hopcroft & Ullman)
• Пионерские работы по автоматам Фибоначчи (Bruyère и др.)
• Основы теории чисел (Hardy & Wright)
• Связанные современные исследования (Mousavi и др., Hieronymi и др.)

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