🔢 mathematics

Beatty Sequences for a Quadratic Irrational: Decidability and Applications

この論文は、二次無理数に基づく非斉次ベアティ数列がオストロフスキー表現を用いた有限オートマトンによって同期可能であることを示し、これにより加法を含むその一階論理理論の決定可能性を証明するとともに、加法的基底に関する決定問題や既存の未解決問題の解決を可能にした。

原著者： Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

公開日 2026-04-03

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Luke Schaeffer, Jeffrey Shallit, Stefan Zorcic

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

数学の「自動翻訳機」と「数列の謎」

～ベアティ数列と「Walnut」という魔法の箱～

この論文は、一見すると難解な数学の話題（「ベアティ数列」や「二次無理数」）を扱っていますが、核心は非常にシンプルで、**「複雑な数字の並びを、小さな機械（自動機械）で簡単にチェックできる」**という驚くべき発見です。

まるで、**「数字の迷路を、小さなロボットが瞬時に通り抜ける」**ような話です。

以下に、専門用語を避け、日常の比喩を使ってこの研究の面白さを解説します。

1. 物語の舞台：「数字の階段」と「不規則なリズム」

まず、**ベアティ数列（Beatty sequence）**というものを想像してください。
ある irrational（無理数、例えば $\sqrt{2}$ や黄金比 $\phi$ ）を「階段の段数」だと思ってください。
「1 段目、2 段目、3 段目…」と階段を登るたびに、その高さを切り捨てて整数にします。
例えば、 $\sqrt{2} \approx 1.414$ なら：

1 段目： $1 \times 1.414 = 1.414 \to$ 1
2 段目： $2 \times 1.414 = 2.828 \to$ 2
3 段目： $3 \times 1.414 = 4.242 \to$ 4
4 段目： $4 \times 1.414 = 5.656 \to$ 5

こうしてできる「1, 2, 4, 5, 7, 8...」という数字の並びがベアティ数列です。
これは一見ランダムに見えますが、実は**「黄金比」や「 $\sqrt{2}$ 」のような、特定の「魔法の数字」から生まれる規則的なリズム**を持っています。

2. 従来の問題：「巨大な計算機」が必要だった

昔の数学では、この数列の性質（例えば「この数列の数字を 2 つ足すと、すべての整数が作れるか？」など）を調べるには、膨大な計算や複雑な論理が必要でした。
まるで、**「巨大な図書館で、一冊一冊本を開いて情報を集める」**ような作業でした。特に、2 つの異なる「魔法の数字」が絡むと、計算が爆発的に複雑になり、人間には解けない問題も出てきました。

3. この論文の発見：「小さな自動翻訳機」の登場

著者たちは、**「この数列は、実は小さな『自動機械（オートマトン）』でチェックできる」**ことを発見しました。

比喩：自動改札機
この自動機械は、**「オストロフスキー表現」**という特別な「数字の言語」で入力を受け取ります。
普通の計算機は「10 進法」で計算しますが、この機械は「黄金比のルール」や「 $\sqrt{2}$ のルール」に合わせた独自の言語を使います。

この機械は、**「入力された数字 $n$ と、その結果 $y$ が、ベアティ数列のルールに合致しているか？」を、まるで「自動改札機が切符をスキャンする」**ように、一瞬で判定します。
- 合っていれば：「ピッ！」と緑のランプが点灯（OK）。
- 合っていなければ：「ブッ！」と赤のランプが点灯（NG）。
この機械は**「有限の大きさ」**です。つまり、無限に続く数列のルールも、この小さな箱の中にすべて詰め込めるのです。

4. 魔法の箱「Walnut」：証明を瞬時に実行する

この研究のすごいところは、理論だけでなく、**「実際に動くプログラム」があることです。
著者たちは、「Walnut（クルミ）」**という無料のソフトウェアを使って、この自動機械を動かしました。

Walnut の役割：
数学者が「この数列は、すべての整数を 2 つの和で表せるかな？」と質問すると、Walnut は**「はい、できます（TRUE）」**と即座に答え、その証明過程まで見せてくれます。

以前は数ヶ月かかっていた証明が、**「数秒」で終わってしまいます。まるで、「数学の難問を、魔法の杖で瞬時に解決する」**ようなものです。

5. この発見で何がわかったのか？（具体的な成果）

この「小さな自動機械」を使うことで、これまで未解決だった多くの謎が解けました。

「足し算の基礎」の判定：
「この数列の数字を何回か足せば、すべての整数を作れるか？」という問題が、**「常に答えが出せる（決定可能）」**ことがわかりました。
レブルとキンバリングの謎：
長年、数学者たちが頭を悩ませていた「特定の数列が、ある規則に従っているか？」という問い（OEIS という数字の辞書にある問題）を、Walnut で即座に解決しました。
グラハムの質問：
「複数の異なる数列が、重なり合うことなく、すべての整数を埋め尽くすか？」という複雑な問いも、同じ方法で解けることが証明されました。

6. まとめ：なぜこれが重要なのか？

この論文は、**「数学の複雑な世界を、単純な機械のルールに落とし込む」**という画期的なアプローチを示しました。

昔：数学の問題は、天才の直感や膨大な計算で解くものだった。
今：「この問題は、小さな自動機械でチェックできるか？」と変換すれば、コンピュータが瞬時に答えを出せることがわかった。

まるで、**「複雑な迷路の地図を、小さなロボットがすべて記憶して、最短ルートを瞬時に案内してくれる」**ようなものです。

著者たちは、この技術を使って、数学の奥深い部分（特に「黄金比」や「 $\sqrt{2}$ 」に関連する部分）の謎を次々と解き明かしています。これは、数学の「自動化」への大きな一歩であり、今後、さらに多くの難問が「クルミ（Walnut）」という魔法の箱で解決されるかもしれません。

一言で言うと：
「数学の難しい数列のルールを、**『小さな自動機械』でチェックできるようにし、『Walnut』というプログラムを使って、長年解けなかった謎を『瞬時』**に解き明かす方法を見つけた！」という画期的な研究です。

論文「Beatty Sequences for a Quadratic Irrational: Decidability and Applications」の技術的サマリー

この論文は、Luke Schaeffer、Jeffrey Shallit、Stefan Zorcic によって執筆され、二次無理数（quadratic irrational）に関連する非斉次 Beatty 数列の決定可能性と、その自動機理論に基づく応用について論じています。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題設定

Beatty 数列とは、実数 $\alpha$ に対して $(\lfloor n\alpha \rfloor)_{n \ge 1}$ で定義される数列です。さらに、定数 $\beta$ を加えた非斉次 Beatty 数列 $(\lfloor n\alpha + \beta \rfloor)_{n \ge 1}$ が研究対象となります。

従来の研究では、 $\alpha$ が黄金比などの特定の値の場合や、Sturmian 数列との関連性が調べられてきましたが、 $\alpha$ と $\beta$ が同じ二次体（quadratic field）に属する一般的な場合において、この数列の性質を第一階述語論理（first-order logical theory）の枠組みで決定可能（decidable）にするための体系的な手法は十分に確立されていませんでした。

本研究の核心的な問いは以下の通りです：

$\alpha, \beta$ が同じ二次体に属する場合、数列 $(\lfloor n\alpha + \beta \rfloor)$ は「同期（synchronized）」されているか？
この性質を用いることで、この数列に関する第一階論理式（加法を含む）の真理値を決定するアルゴリズムは存在するか？
この決定手続きを用いて、加法的基底（additive basis）や他の未解決問題（Reble, Kimberling, Graham などの予想）を解決できるか？

2. 手法と理論的基盤

本研究は、Ostrowski 数値系と有限オートマトン、およびWalnutという定理証明ソフトウェアを組み合わせるアプローチを採用しています。

2.1 Ostrowski 数値系と同期性

Ostrowski 数値系: 自然数を、ある無理数 $\gamma$ の連分数展開の収束項（convergents） $q_i$ の線形結合として一意に表現する方式です。特に $\gamma$ が二次無理数の場合、この表現は有限オートマトンで加法関係 $x+y=z$ を認識可能です。
同期数列（Synchronized Sequence）: 数列 $(s_n)$ が「同期」されているとは、入力として $n$ と $y$ の Ostrowski 表現を並列に受け取り、 $y = s_n$ である場合にのみ受理する有限オートマトンが存在することを意味します。
主要な定理（Theorem 9）: $\gamma$ $γ$ が二次無理数であり、その逆数 $1/\gamma$ $1/ γ$ の連分数展開が純周期的である場合、 $\alpha, \beta \in \mathbb{Q}(\gamma)$ $α, β \in Q (γ)$ かつ $\alpha \ge 0, \alpha+\beta \ge 0$ $α \geq 0, α + β \geq 0$ ならば、非斉次 Beatty 数列 $(\lfloor n\alpha + \beta \rfloor)$ $(⌊ n α + β ⌋)$ は $\gamma$ $γ$ -Ostrowski 同期数列となります。
- 証明の鍵は、連分数の周期性を利用した行列アプローチ（Theorem 5）と、Ostrowski 表現におけるシフト操作の自動化にあります。

2.2 決定可能性と Walnut

Theorem 2 と Corollary 11: 同期数列は、加法、定数倍、自動数列、同期数列の合成などに対して閉じています。したがって、 $\alpha, \beta$ が二次体に属する場合、自然数集合 $\mathbb{N}$ に加法と関数 $n \mapsto \lfloor n\alpha + \beta \rfloor$ を加えた第一階論理理論は決定可能です。
Walnut: 決定手続きを実装するオープンソースのソフトウェアです。論理式を入力として、自動機を構築し、その真理値（TRUE/FALSE）を計算したり、自由変数を持つ式に対する解の自動機を生成したりします。

3. 主要な貢献と結果

論文は理論的な証明だけでなく、Walnut を用いた具体的な計算による証明や、数多くの未解決問題の解決を提示しています。

3.1 加法的基底の決定可能性（Section 7）

数列 $(\lfloor n\alpha + \beta \rfloor)$ が「 $r$ 次加法的基底」または「漸近的加法的基底」を形成するかどうかを決定するアルゴリズムを提供しました。
具体的な例として、黄金比 $\phi$ に関連する数列 $c = (\lfloor n\phi + 1/2 \rfloor)$ について、「1 以外のすべての非負整数が $c$ の 2 要素の和で表せる」ことを Walnut で証明しました。

3.2 未解決問題の解決

Reble の予想（Section 8）: Fibonacci 単語における単色算術級数の存在に関する Don Reble の予想（OEIS A189377, A189378, A189379 に関連）を、Walnut による第一階論理式の評価で証明し、すべて TRUE であることを示しました。
Graham の問題（Section 9）: 有限個のペア $\{(\alpha_i, \beta_i)\}$ に対して、十分大きな整数がちょうど 1 つの Beatty 集合に属するかどうか（Eventual Covering Family）の問題について、 $\alpha_i, \beta_i$ が同じ二次体に属する場合に決定可能であることを示し、具体例を証明しました。
Hildebrand らの数列（Section 10）: Hildebrand, Li, Li, Xie によって研究された数列 $\tilde{c}(n)$ について、 $0 \le c(n) - \tilde{c}(n) \le 2$ という不等式を証明し、その差を計算する自動機を構成しました。
Kimberling の問題（Section 11, 12）: Kimberling が提唱した「swappage sequence」や「sums-complement set」に関する予想を証明し、具体的な自動機を構成しました。
$\sqrt{2}$ に関連する数列（Section 13）: OEIS に登録された $\sqrt{2}$ に関連する 7 つの数列について、Ostrowski 自動機を構成し、いくつかの予想（Dekking の予想など）を証明しました。

3.3 逆定理の証明（Section 15）

Theorem 28: Beatty 数列 $(\lfloor n\alpha + \beta \rfloor)$ が $\gamma$ -Ostrowski 同期であるならば、 $\alpha$ と $\beta$ は必ず $\mathbb{Q}(\gamma)$ に属する（逆定理）ことを証明しました。これは、同期性が二次体の構造と密接に関連していることを示しています。

3.4 小数部の比較（Section 14）

小数部 $\{x\}$ の大小比較 $\{ \alpha x + \beta \} < \{ \alpha' y + \beta' \}$ を、床関数 $\lfloor \cdot \rfloor$ を用いた第一階論理式に変換する手法（Proposition 24）を提案し、Walnut での実装を可能にしました。これにより、円周上の順序関係などの問題も扱えるようになりました。

4. 意義と結論

この論文の最大の意義は、二次無理数に基づく Beatty 数列の理論を、計算機で検証可能な「決定可能な論理理論」の枠組みに完全に組み込んだ点にあります。

手法の単純化と一般化: 従来の複雑な数論的証明を、Ostrowski 数値系と有限オートマトン、および Walnut による機械的証明に置き換えることで、証明を簡素化し、一般化しました。
実用性: 多くの未解決問題や OEIS 上の予想が、数秒〜数分の計算時間で証明可能であることを示しました。これは、数論的数列の研究において、実験的検証と厳密な証明を融合させる強力なツールを提供します。
逆定理の確立: 同期性という自動機理論的な性質が、数論的な二次体の構造と等価であることを示したことは、理論的な深みをもたらしています。

総じて、この研究は自動機理論、数論、論理学の交差点において、Beatty 数列の研究に新たなパラダイムをもたらす重要な成果です。