💻 computer science

Mahler equations for Zeckendorf numeration

この論文は、ゼッケンドルフ数値体系に基づく Z-マハラー方程式を定義し、Z-正則数列と Z-マハラー方程式の解との関係を拡張し、非孤立方程式の反例を示すとともに、古典的な q-正則数列を生成する重み付きオートマトンの新たな構成法を提供するものである。

原著者： Olivier Carton, Reem Yassawi

公開日 2026-03-17

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Olivier Carton, Reem Yassawi

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

この論文は、「数字の書き方（数え方）」と「複雑なパターンを作る機械（オートマトン）」、そして**「魔法の方程式」**の間に、驚くべきつながりがあることを発見したというお話です。

専門用語を避け、身近な例え話を使って解説しましょう。

1. 舞台設定：2 つの「数え方」の世界

まず、私たちが普段使っている「10 進法（0, 1, 2...9）」や「2 進法（0, 1）」という数え方を知っていますよね。
この論文では、**「ゼッケンドルフ数え方（Zeckendorf numeration）」**という、少し変わった数え方に注目しています。

いつもの数え方（10 進法など）：
10, 100, 1000... という「10 の倍数」の積み重ねで数を表します。
ゼッケンドルフ数え方：
フィボナッチ数列（1, 2, 3, 5, 8, 13, 21...）を使って数を表します。
- 例：「8」はそのまま「8」。
- 「9」は「8 + 1」。
- 「10」は「8 + 2」。
- ルール： 同じフィボナッチ数を 2 回使ったり、隣り合うフィボナッチ数を同時に使ったりしてはいけません（「3+2」は NG、「3+1」は OK）。

この論文は、この「フィボナッチ・ルール」で数を書き表したとき、どんな面白いことが起きるかを調べています。

2. 登場人物：2 つの「魔法の道具」

この研究では、2 つの異なるアプローチを「つなぐ」ことを目指しています。

A. 自動販売機のような「機械（オートマトン）」

想像してください。数字を「フィボナッチ・ルール」で入力すると、機械が「1」か「0」か、あるいは「5」などの数字を吐き出す機械があるとします。

この機械は**「規則正しい（Regular）」**と言われます。
機械の内部は単純で、状態が有限（例えば「状態 A」「状態 B」など）しかありません。
例え： 複雑な曲を演奏するピアノロール。穴の位置（入力）が決まれば、必ず同じ音（出力）が出ます。

B. 魔法の方程式（マラー方程式）

次に、**「Z-マラー方程式」**という特殊な方程式が登場します。

普通の方程式は「x を 2 倍したらどうなるか」を扱いますが、この方程式は**「フィボナッチ・ルールで数字を書き換えたとき、どうなるか」**という操作を含みます。
例え： 「この数字を、フィボナッチのルールに従って『変形』させて、元の式とつなげると、0 になるんだよ」というような、少し不思議なルールです。

3. この論文の最大の発見：「2 つは実は同じ！」

これまでの研究（ベッカーやドゥマスの仕事）では、「普通の 10 進法や 2 進法」の世界で、「機械で計算できるパターン」は「魔法の方程式の解」であり、その逆も真であることが証明されていました。

しかし、「フィボナッチ・ルール（ゼッケンドルフ）」の世界ではどうなるか？ は長い間謎でした。

この論文の結論：

「フィボナッチ・ルール」の世界でも、同じことが成り立ちます！

もし、ある数列が「機械（オートマトン）」で計算できるなら、それは「Z-マラー方程式」の解になります。

もし、ある数列が「Z-マラー方程式」の解で、かつ**「孤立している（isolating）」**という特別な条件を満たすなら、それは「機械」で計算できます。

4. なぜこれが難しいのか？（「直線」の崩壊）

ここが論文の面白い部分です。なぜ「フィボナッチ・ルール」では難しかったのでしょうか？

普通の世界（10 進法）：
数字の最後に「0」をつけることは、「10 倍する」ことと同じです。これは**「直線的」**で簡単です。
- 例：3 → 30（3×10）
フィボナッチの世界：
数字の最後に「0」をつけることは、単純な「2 倍」や「3 倍」にはなりません。フィボナッチ数列の性質上、**「少し歪んだ変形」**になります。
- 例：ある数を「変形」すると、予想より 1 だけ大きくなったり、小さくなったりします。

この「歪み（線形性の欠如）」が、従来の数学的な道具（カルティエ演算子など）をそのまま使えなくしてしまいました。

著者たちの解決策：
彼らは、この「歪み」自体を計算できる**「小さな補助機械」**を新たに作りました。

本物の機械が「メインの計算」をする。
補助機械が「フィボナッチ・ルール特有の歪み（ズレ）」を常にチェックして補正する。
この 2 つを合体させることで、複雑な方程式を解く機械を作ることができました。

5. 具体的な例え話：パズルとレシピ

Z-マラー方程式 = 複雑な料理のレシピ（「材料 A を変形させて、材料 B と混ぜて…」という指示）。
機械（オートマトン） = そのレシピ通りに料理を作るロボット。
発見 = 「このレシピ（方程式）通りに作れば、必ずこのロボット（機械）で再現できる料理ができるよ！」と証明したことです。
- ただし、レシピが「孤立している（特定の条件を満たしている）」場合に限ります。条件を満たさないレシピは、ロボットが作れない（無限に複雑になる）こともあります。

6. なぜこれが重要なのか？

数学の美しさ： 「代数（方程式）」と「計算（機械）」という、一見関係なさそうな 2 つの世界が、フィボナッチ数列という美しいパターンを通じて繋がっていることが分かりました。
新しい世界への扉： この手法を使えば、フィボナッチだけでなく、他の「 Pisot 数（ピソット数）」と呼ばれる特殊な数え方でも、同じようなつながりが見つかるかもしれません。
実用的な応用： 乱数生成や、効率的なデータ圧縮、あるいは「超越数（円周率のような、分数で表せない数）」を見つけるための新しい方法につながる可能性があります。

まとめ

この論文は、**「フィボナッチ数列という特別なルールで数を表すとき、複雑な方程式と、単純な計算機械は実は双子のような関係にある」**ことを発見し、その理由を解明した素晴らしい研究です。

「数字の書き方」を変えるだけで、数学の世界に新しい扉が開かれたような、ワクワクするお話です。

1. 問題設定と背景

背景:

クリストル定理 (Christol's Theorem): 有限体上の形式的冪級数が代数的であることと、その係数が有限状態オートマトン（ $p$ -自動的系列）によって生成されることは同値であるという古典的な結果。
正則系列 (Regular Sequences): Allouche と Shallit によって導入された概念。重み付きオートマトン（Weighted Automata）によって生成される系列。これは自動的系列を一般化し、無限の値域（環 $R$ 上の値）を持つ系列を扱える。
マヘル方程式 (Mahler Equations): $k$ -正則系列と密接に関連する関数方程式。 $k$ -正則系列は $k$ -マヘル方程式の解となり、逆に「分離的 (isolating)」な $k$ -マヘル方程式の解は $k$ -正則系列となる（Becker と Dumas の結果）。

課題:

これまでの理論は主に $k$ 進法（基数 $k$ ）の体系に基づいていた。 $k$ 進法では、桁に 0 を追加することが $k$ 倍（ $n \mapsto kn$ ）に対応し、この線形性が証明の鍵（Cartier 演算子の使用など）となっている。
しかし、**ゼッケンドルフ数体系（Zeckendorf numeration）**のように、フィボナッチ数 $F_n$ を基底とする Pisot 数体系では、桁に 0 を追加する操作が単純な線形変換（ $n \mapsto \phi(n)$ ）に対応せず、非線形性を持つ。
核心的な問い: ゼッケンドルフ数体系（および一般的な Pisot 数体系）において、正則系列とマヘル型の方程式の間の同値関係は成立するか？特に、非線形性のために従来の Cartier 演算子が使えない場合、どのようにして重み付きオートマトンの構成が可能か？

2. 手法とアプローチ

この論文は、 $k$ 進法の証明手法をゼッケンドルフ数体系に拡張するために、以下の新しい構成と手法を採用しています。

A. 線形性の欠損 (Linearity Defect) の自動機による計算:

基底 $k$ の場合、 $n \mapsto kn$ は線形だが、ゼッケンドルフ体系では $\phi(n)$ （桁に 0 を追加する操作）は線形ではない（例： $\phi(2) \neq \phi(1) + \phi(1)$ ）。
著者らは、この非線形性の度合いを「線形性の欠損 (linearity defect)」 $\delta(m, n) = \phi(m+n) - \phi(m) - \phi(n)$ として定義し、これが常に $\{-1, 0, 1\}$ の値をとることを示した。
さらに、この欠損 $\delta(m, n)$ を、入力として $(m)_Z$ と $(n)_Z$ （ゼッケンドルフ展開）を受け取り、出力として $\delta$ を返す決定性オートマトンによって計算可能であることを証明した（Frougny と Solomyak の加法正規化の理論に基づく）。

B. 汎用重み付きオートマトンの構成:

$k$ -マヘル方程式の解を生成する重み付きオートマトンを構成する際、従来の Cartier 演算子に依存しない直接的な構成法を提案した。
汎用重み付き $k$ -オートマトン: 任意の分離的 $k$ -マヘル方程式の解を生成できる「普遍的な」オートマトンの構造を定義し、方程式の係数によって重みをインスタンス化することで、特定の解を生成するオートマトンを導出する。
この手法をゼッケンドルフ体系に適用する際、状態集合に「線形性の欠損をトラッキングするための情報（状態 $q$ と文字列 $u$ ）」を追加し、非線形性を補正しながら係数を計算するオートマトンを構築した。

C. Z-マヘル方程式の定義:

通常の $k$ -マヘル方程式における作用素 $\Phi(f(x)) = f(x^k)$ のアナログとして、ゼッケンドルフ体系における作用素 $\Phi$ を定義した。
$\Phi\left(\sum f_n x^n\right) = \sum f_n x^{\phi(n)}$
これを用いて、Z-マヘル方程式 $P(x, y) = \sum A_i(x) \Phi^i(y) = 0$ を定義し、その解と正則性の関係を研究した。

3. 主要な貢献と結果

定理 1 (主定理): 分離的 Z-マヘル方程式の解は Z-正則である

可換環 $R$ 上の分離的（ $A_0(x)=1$ ）な Z-マヘル方程式 $P(x, f(x)) = 0$ の解 $f(x)$ は、ゼッケンドルフ数体系における重み付きオートマトンによって生成される（すなわち、Z-正則系列である）。
証明のポイント: 線形性の欠損を計算するオートマトンと、マヘル方程式の係数から係数を再帰的に計算する汎用オートマトンを組み合わせることで、解の係数を生成する重み付きオートマトンを明示的に構成した。

定理 2 (汎用オートマトンの存在):

任意の整数 $k \ge 2$ に対して、任意の分離的 $k$ -マヘル方程式の解を生成する「汎用重み付き $k$ -オートマトン」が存在することを示した。これは Christol の定理の一方の方向（代数的 $\implies$ 自動的）の新しい構成法を提供し、Cartier 演算子を使わない証明を可能にした。

逆方向の結果 (Corollary 34):

Z-正則系列は、何らかの Z-マヘル方程式の解となる。これは標準的な手法（核 (kernel) の有限性）を用いて示された。

反例の提示 (Proposition 38):

「分離的 (isolating)」という条件が重要であることを示すため、分離的ではない Z-マヘル方程式の解が Z-正則にならない例を提示した。
- 例： $(1-x)f(x) = \Phi(f(x))$ の解は、係数の成長が速すぎて（多項式成長を超え）、Z-正則系列の必要条件（係数が多項式有界であること）を満たさない。

状態数の評価:

構成されたオートマトンの状態数の上限を、方程式の次数 $d$ 、高さ $h$ 、および黄金比 $\phi$ を用いて評価した。 $k$ 進法の場合に比べて、線形性の欠損を管理するための追加情報により、状態数がより複雑になる（ $O(d h^2)$ のオーダー）ことが示された。

4. 意義と今後の展望

学術的意義:

数体系の一般化: 自動的・正則系列の理論を、単なる $k$ 進法から、より一般的な Pisot 数体系（特にゼッケンドルフ体系）へ拡張した最初の包括的な結果の一つである。
証明手法の革新: 従来の代数的手法（Cartier 演算子）に依存せず、線形性の欠損を自動機でトラッキングする組み合わせ論的・構成的なアプローチを確立した。これは、非線形な数体系における正則性の研究に対する新しいパラダイムを提供する。
代数的性質と計算可能性の橋渡し: 有限体上の Christol 定理の精神を、より一般的な環上の正則系列とマヘル方程式の関係へと拡張し、代数的性質（マヘル方程式の解）と計算可能性（重み付きオートマトン）の対応を Pisot 数体系でも成立させることを示した。

今後の課題:

完全な特徴付け: 分離的でない Z-マヘル方程式の解が Z-正則となるための完全な条件（ $k$ -正則の場合の BCCD19 のような結果）は未解決である。
超越数論への応用: マヘル方程式の解が超越数を与えるという Mahler 法が、Z-マヘル方程式においても同様に機能するかどうかの検討が期待される。
Cobham 型定理の拡張: 異なる数体系（例： $k$ -進法とゼッケンドルフ法）の両方でマヘル的である系列が有理式になるかどうかなど、Cobham 型定理の拡張が今後の研究課題として挙げられている。

結論

この論文は、ゼッケンドルフ数体系という非線形な数体系において、正則系列とマヘル方程式の間の深い関係を確立した画期的な研究です。特に、非線形性の欠損を自動機によって管理する新しい構成法は、従来の代数的手法では扱えなかった問題に対する強力な解決策を提供しており、数論的自動機理論の分野における重要な進展と言えます。