Сбалансированные прямоугольники слов Фибоначчи и их обобщения

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

• ID статьи: 2509.25994
• Название: Balanced Fibonacci word rectangles, and beyond
• Авторы: Jeffrey Shallit (Университет Ватерлоо), Ingrid Vukusic (Университет Йорка)
• Классификация: math.NT cs.DM cs.FL math.CO
• Дата публикации: 15 октября 2025 г. (препринт ArXiv)
• Ссылка на статью: https://arxiv.org/abs/2509.25994

Аннотация

В данной работе, основываясь на недавних исследованиях Anselmo и соавторов, рассматриваются $m \times n$ матричные прямоугольники, образованные словами Фибоначчи. Доказывается, что их свойства сбалансированности могут быть решены с помощью конечных автоматов. Исследование далее обобщает результаты на каждое характеристическое слово Штурма, соответствующее квадратичным иррациональным числам, и рассматривает аналогичные задачи для слов Трибоначчи.

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

Определение проблемы

Основная проблема, изучаемая в данной работе, — это сбалансированность словесных матриц: для заданной бесконечной последовательности $(a_i)_{i≥0}$ строится бесконечная матрица $A = (a_{k,\ell})_{k,\ell≥0}$, где $a_{k,\ell} = a_{k+\ell}$. Для подматрицы $m \times n$ размера $A(i,m,n)$ сумма всех элементов определяется как: $T(i,m,n) := \sum_{k=0}^{m-1}\sum_{\ell=0}^{n-1} a_{i+k+\ell}$

Проблема сбалансированности состоит в следующем: для каких пар $(m,n)$ все значения $T(i,m,n)$ принимают не более двух различных значений?

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

1. Теоретическая значимость: Слова Фибоначчи являются классическими объектами комбинаторики, их свойства сбалансированности тесно связаны с теорией чисел и теорией автоматов
2. Существующие ограничения: Anselmo и соавторы доказали, что прямоугольники сбалансированы, когда $\max(m,n)$ является числом Фибоначчи, однако полная характеризация остаётся неполной
3. Методологическое новшество: Использование конечных автоматов для решения таких задач предоставляет новый вычислительный инструмент

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

1. Полная характеризация: Предоставляется полная автоматная характеризация сбалансированности прямоугольников слов Фибоначчи (теорема 2 и следствие 3)
2. Обобщённые результаты: Результаты распространяются на все слова Штурма, соответствующие квадратичным иррациональным числам (теорема 2)
3. Алгоритмическая реализация: Предоставляется конкретная реализация на основе программного обеспечения Walnut и верификация
4. Результаты о плотности: Доказываются свойства плотности сбалансированных пар $(m,n)$ (предложение 6)
5. Расширение на Трибоначчи: Исследуются аналогичные задачи для слов Трибоначчи (теорема 10)

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

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

Для заданной бесконечной последовательности $(a_i)_{i≥0}$ строится матрица Ганкеля: $A(i,m,n) := \begin{pmatrix} a_i & a_{i+1} & \cdots & a_{i+n-1} \\ a_{i+1} & a_{i+2} & \cdots & a_{i+n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i+m-1} & a_{i+m} & \cdots & a_{i+m+n-2} \end{pmatrix}$

Цель: определить, какие пары $(m,n)$ обеспечивают, чтобы все значения $T(i,m,n)$ принимали не более двух различных значений.

Основная теоретическая база

Свойства слов Штурма

Для слов Штурма определяется $\Delta(i,m,n) := T(i+1,m,n) - T(i,m,n)$, где: $\Delta(i,m,n) \in \{-1, 0, 1\}$

Ключевая лемма 1: Пара $(m,n)$ сбалансирована тогда и только тогда, когда последовательность $(\Delta(i,m,n))_{i≥0}$ не содержит блоков вида $1,0,0,\ldots,0,1$ или $-1,0,0,\ldots,0,-1$.

Метод конечных автоматов

Для квадратичного иррационального числа $\alpha$ существует конечный автомат $M$, который на входе принимает представление $n$ и $x$ в $\alpha$-ичной системе Островского и принимает слово тогда и только тогда, когда $x = \lfloor n\alpha \rfloor$.

Основная теорема 2: Существует алгоритм, который для заданного квадратичного иррационального числа $\alpha \in (0,1)$ конструирует конечный автомат, принимающий на входе пары $(m,n)$ в $\alpha$-ичной системе Островского и принимающий слово тогда и только тогда, когда блок $m \times n$ сбалансирован.

Технические инновации

1. Автоматная реализация критериев сбалансированности: Условия леммы 1 преобразуются в формулы логики первого порядка, а затем в автомат
2. Обработка представления Цекендорфа: Искусная обработка проблемы отрицательных чисел с использованием $T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$
3. Реализация в Walnut: Предоставляется полная реализация кода, генерирующая автомат с 15 состояниями

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

Инструменты и реализация

• Программное обеспечение Walnut: Специализированный инструмент для конструирования и верификации автоматов
• Представление Цекендорфа: Стандартная система представления чисел Фибоначчи
• Представление Трибоначчи: Используется для анализа слов Трибоначчи

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

1. Конструирование автомата: Генерирование bal-автомата через Walnut (15 состояний)
2. Верификация теорем: Проверка результатов Anselmo и соавторов как частных случаев
3. Анализ плотности: Вычисление свойств распределения сбалансированных пар

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

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

Следствие 3: Автомат с 15 состояниями на рис. 1 полностью решает проблему сбалансированности прямоугольников слов Фибоначчи.

Следствие 4: Верифицируется теорема Anselmo и соавторов: если $\max(m,n)$ является числом Фибоначчи, то матрица $m \times n$ сбалансирована.

Структурные свойства

Предложение 5: Для $n ≥ 2$:

• $(i,j)$ сбалансирована тогда и только тогда, когда $(i',j)$ сбалансирована, где $F_{n+1} < i,i' < F_{n+2}$ и $j ≥ F_{n-1}$
• $(F_{n+1}+i,j)$ сбалансирована тогда и только тогда, когда $(F_{n+2}-i,j)$ сбалансирована

Предложение 6 (результат о плотности): Если $F_i < m ≤ F_{i+1}$, то для всех $n ≥ 1$ существует $j$, $1 ≤ j ≤ F_{i+1}$ такое, что $(m,n+j)$ сбалансирована.

Результаты о многообразии

Теорема 8: Для $m = n = F_{3k}/2$ количество различных значений $T(i,m,n)$ не менее $k+1$.

Следствие 9: Количество различных значений $T(i,F_{3n}/2,F_{3n}/2)$ равно $\Theta(n)$.

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

Теорема 10: Предположим $m ≤ n$:

• Если $m = 1$, все матрицы $m \times n$ являются 2-сбалансированными
• Если $m = 2$, существует автомат с 77 состояниями, принимающий все $n$ такие, что матрица $m \times n$ является 2-сбалансированной
• Если $m ≥ 3$, не существует $n$ таких, что матрица $m \times n$ является 2-сбалансированной

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

1. Теория слов Штурма: Основана на классических работах Berstel, Brown и других
2. Исследования сбалансированности: Расширяет исследования Vuillon и соавторов о сбалансированности слов
3. Методы автоматов: Использует теорию p-распознаваемых множеств Bruyère и соавторов
4. Свойства слов Фибоначчи: Основана на обширных существующих исследованиях слов Фибоначчи

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

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

1. Полностью решена проблема сбалансированности прямоугольников слов Фибоначчи с предоставлением характеризации автоматом с 15 состояниями
2. Метод обобщается на все слова Штурма, соответствующие квадратичным иррациональным числам
3. Случай слов Трибоначчи более сложен и требует автомата с 77 состояниями для обработки случая $m=2$

Ограничения

1. Метод применим только к словам Штурма, соответствующим квадратичным иррациональным числам
2. Полная характеризация слов Трибоначчи остаётся сложной
3. Случаи высшего порядка (например, Трибоначчи с $m≥3$) могут быть неразрешимы

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

1. Обобщение на более общие морфические слова
2. Исследование многомерных случаев
3. Оптимизация количества состояний автомата

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

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

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

Недостатки

1. Сложность: Хотя метод автоматов полон, он может быть недостаточно интуитивным
2. Ограничения обобщения: Применим только к определённым типам иррациональных чисел
3. Анализ сложности: Временная сложность автомата не проанализирована подробно

Влияние

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

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

1. Исследования сбалансированности в комбинаторике
2. Приложения теории автоматов
3. Исследования свойств иррациональных чисел в теории чисел
4. Задачи принятия решений в проектировании алгоритмов

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

В статье цитируются 19 важных источников, включая:

• Классические работы Allouche & Shallit об автоматических последовательностях
• Фундаментальные работы Berstel о словах Фибоначчи и словах Штурма
• Недавние исследования Anselmo и соавторов
• Литературу по теории автоматов и теории чисел

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