Superlinear complexity of the $(3/2)^n$ steering word

技術的要約：$(3/2)^n$ ステアリング・ワードの超線形複雑性

問題設定
本論文は、写像 $x \mapsto \frac{3}{2}x$ の下での 1 の軌道によって生成される記号力学系、特に最近傍整数への丸め誤差の列に焦点を当てて研究している。数列 $\|(\frac{3}{2})^n\|$（最近傍整数との距離）の分布は数論における長年の未解決問題であるが、本研究では「ステアリング・ワード（操舵語）」$T = (t_n)_{n \geq 0}$ に焦点を移している。このワードは、各ステップで選択される整数の平行移動を記録するもので、$t_n = 2m_{n+1} - 3m_n$ と定義される（ここで $m_n = \text{round}((\frac{3}{2})^n)$ である）。中心となる問いは、このワードの部分語複雑性 $p_T(k)$、すなわち長さ $k$ の異なる因子（factor）の個数である。本論文の目的は、この複雑性が超線形であること、すなわち $\lim_{k \to \infty} p_T(k)/k = \infty$ であることを証明することである。

手法
証明戦略は、代数的数の複雑性の研究（具体的には Adamczewski–Bugeaud 法）の手法を、この力学的な設定へと転移させる 3 つの明確な段階で構成されている。この議論は**部分空間定理（Subspace Theorem）**に大きく依存しており、Lean-4 によって完全に形式化されていることが特筆される。

1. ステージ 0: 正確な恒等式と無条件の境界（セクション 2）
   著者は正確な「反復恒等式」を導出している。もし長さ $k$ の因子が位置 $a$ と $c$ ($a < c$) で繰り返されるならば、それは関係式 $3^k(\varepsilon_c - \varepsilon_a) = 2^k(\varepsilon_{c+k} - \varepsilon_{a+k})$ を強制する（ここで $\varepsilon_n$ は丸め誤差である）。

   • この恒等式は、割り切れる条件 $2^k \mid (m_c - m_a)$ を導き出す。
   • 軌道の成長特性と組み合わせることで、長い反復がワード内で任意に遅い位置で発生することはないことを確立する。
   • 無条件の結果: 本論文は $T$ が最終的に周期的なものではないことを証明し、さらに $p_T(k) \geq \frac{41}{24}k - 3$ という線形の下限を確立している。これは、非周期的ワードの Morse–Hedlund の下限 ($k+1$) を厳密に上回っている。

2. ステージ 1: ディオファントス核への還元（セクション 3）
   部分語複雑性が超線形的であることを証明する問題は、核 (Kernel, K) と呼ばれる単一のディオファントス的な命題へと還元される。

   • 命題 (K): すべての有理数 $\theta \in (0, 1)$ に対して、 $2 \leq a < c$ を満たし $\|(\frac{3}{2})^c - (\frac{3}{2})^a\| \leq \theta^c$ を満たすペア $(a, c)$ の集合は有限である。
   • これは「指数的なペア斥力」特性を表しており、軌道の点間の距離の自明な下限を、底 $2^{-1}$ から任意の底 $\theta < 1$ へと改善している。
   • この還元は、もし (K) が成り立つならば、$p_T(k)/k \to \infty$ となることを示している。

3. ステージ 2: 核の確立（セクション 4 および 5）
   (K) の証明は、潜在的な解の集合を 3 つの「スライス」に分割し、ディオファントス近似の深い結果を適用することによって達成される。

   • 限定的なギャップ・スライス (Bounded Gap Slice): 固定されたギャップ $c-a$ に対して、Corvaja–Zannier の主定理（Schmidt 部分空間定理の帰結）を用いて有限性が証明される。
   • 巨大なギャップ・スライス (Huge-Gap Slice): $a \leq \epsilon' c$ である領域において、これも擬 Pisot 除外の特定の場合として扱うことで、Corvaja–Zannier 定理を通じて有限性が確立される。
   • 中間帯域 (Middle Band): ギャップが増大しているが $a$ が $c$ に対して無視できない大きさである残りの領域では、著者はギャップ二分法を用いる。もし解の集合が無限であれば、異なるギャップを持つ部分族を抽出できる。これは、Nair–Kumar–Rout の S 単位タプル定理を用いると矛盾を招き、$(\frac{3}{2})^c$ がある $c$ において整数になることを意味するが、これは不可能である。

主要な貢献と結果

• 主定理 (Theorem 1.1): ステアリング・ワード $T$ の部分語複雑性は超線形である ($p_T(k)/k \to \infty$)。
• 無条件の下限: 本論文は、未証明の仮定に依存することなく、明示的な無条件の線形下限 $p_T(k) \geq \frac{41}{24}k - 3$ を提供している。
• 形式化: 引数全体が Lean-4 で形式化されている。この形式化は、3 変数における Evertse–Schlickewei 部分空間定理のみに依存しており、これにより Corvaja–Zannier および Nair–Kumar–Rout の結果への依存関係が論理的に妥当であることが確認されている。
• 非周期性: ステアリング・ワードが最終的に周期的ではないことの厳密な証明。

意義と主張
本論文は、記号力学系とディオファントス近似を架橋することによって、この特定の自律的力学系に関する複雑性の問題を解決したと主張している。

• 手法の転移: 通常、代数的数に対して用いられる Adamczewski–Bugeaud 法を、力学的なワードへと成功的に適応させている。著者は、$(3/2)$ 力学の自律的な性質により、帳簿整理（bookkeeping）が簡略化され、繰り返される因子が接頭辞による固定なしに、きれいなディオファントス不等式へと圧縮できると述べている。
• 深い定理への依存: 超線形性の証明は、Corvaja–Zannier 定理（査読済み）および Nair–Kumar–Rout 定理（執筆時点でのプレプリント）に依存している。しかし、Lean-4 による形式化は、これらの依存関係が部分空間定理の論理的な帰結であることを検証する役割を果たしている。
• 限界: 超線形成長に関する結果は非有効的 (ineffective) である。すなわち、部分空間定理は、例外的な集合（ディオファントス不等式の解の集合）のサイズに関する明示的な境界を与えない。本論文は、$\|(\frac{3}{2})^n\| \to 0$ というより広範な未解決問題の解決を主張しているのではなく、丸め列の組合せ論的な複雑性を特徴付けているのである。