2025-11-10T03:15:48.044021

Balanced Fibonacci word rectangles, and beyond

Shallit, Vukusic

Following a recent paper of Anselmo et al., we consider $m \times n$ rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word.

academic

バランスの取れたフィボナッチ語矩形、およびその先へ

基本情報

論文ID: 2509.25994
タイトル: Balanced Fibonacci word rectangles, and beyond
著者: Jeffrey Shallit (ウォータールー大学)、Ingrid Vukusic (ヨーク大学)
分類: math.NT cs.DM cs.FL math.CO
発表日: 2025年10月15日 (ArXiv プレプリント)
論文リンク: https://arxiv.org/abs/2509.25994

要約

本論文はAnselmoらによる最新の研究に基づき、フィボナッチ語から形成される $m \times n$ 矩形行列を考察し、それらのバランス性質が有限オートマトンによって解決可能であることを証明している。研究はさらに、二次無理数に対応する各Sturmian特性語への結果の一般化を行い、Tribonacci語の類似問題を検討している。

研究背景と動機

問題定義

本論文が研究する中核的問題は語矩形のバランス性である：無限列 $(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)$ 値が最大2つの異なる値のみを持つのかという問題である。

研究動機

理論的重要性：フィボナッチ語は組合せ数学における古典的対象であり、そのバランス性質は数論およびオートマトン理論と密接に関連している
既存の制限：Anselmoらは $\max(m,n)$ がフィボナッチ数である場合に矩形がバランスしていることを証明したが、完全な特性化はいまだ欠けている
方法の革新性：有限オートマトンを用いてこの種の問題を解決することは、新しい計算ツールを提供する

核心的貢献

完全な特性化：フィボナッチ語矩形のバランス性の完全なオートマトン特性化を提供する（定理2および系3）
一般化結果：すべての二次無理数に対応するSturmian語への結果の一般化（定理2）
アルゴリズム実装：Walnutソフトウェアに基づく具体的な実装と検証の提供
密度結果：バランスの取れた対 $(m,n)$ の密度性質の証明（命題6）
Tribonacci拡張：Tribonacci語の類似問題の研究（定理10）

方法の詳細

タスク定義

無限列 $(a_i)_{i≥0}$ が与えられたとき、Hankel行列を構築する： $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}$

目標：すべての $T(i,m,n)$ 値が最大2つの異なる値のみを持つような $(m,n)$ 対を決定する。

核心的理論フレームワーク

Sturmian語の性質

Sturmian語に対して、 $\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$ が存在し、Ostrowski $\alpha$ 進法表現の $n$ と $x$ を入力として、 $x = \lfloor n\alpha \rfloor$ のときのみ受理する。

主定理2：アルゴリズムが存在し、二次無理数 $\alpha \in (0,1)$ が与えられたとき、有限オートマトンを構築することができる。このオートマトンはOstrowski $\alpha$ 進法表現の $(m,n)$ 対を入力として、 $m \times n$ ブロックがバランスしているときのみ受理する。

技術的革新点

バランス判定基準のオートマトン実装：補題1の条件を一階論理式に変換し、さらにオートマトンに変換する
Zeckendorf表現の処理：負数問題を巧妙に処理し、 $T(i+1,m,n) - T(i,m,n) + 1 \in \{0,1,2\}$ を使用する
Walnut実装：完全なコード実装を提供し、15状態のオートマトンを生成する

実験設定

ツールと実装

Walnutソフトウェア：オートマトン構築と検証用の専用ツール
Zeckendorf表現：フィボナッチ数の標準表現システム
Tribonacci表現：Tribonacci語分析用

検証方法

オートマトン構築：Walnutを通じてbalオートマトン（15状態）を生成する
定理検証：Anselmoらの結果を特殊ケースとして検証する
密度分析：バランスの取れた対の分布特性を計算する

実験結果

フィボナッチ語の主要結果

系3：図1の15状態オートマトンがフィボナッチ語矩形のバランス性問題を完全に解決する。

系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)$ がバランスしている