🔢 mathematics

Positivity of Nearly Linearly Recurrent Sequences

本論文は、線形再帰の一般化である「ほぼ線形再帰」の正性問題（すべての項が正かどうかの判定）を定式化し、特に 2 次の場合について、新たな超越数論の結果を用いた決定手続きを提案するものである。

原著者： Amaury Pouly, Mahsa Shirmohammadi, James Worrell

公開日 2026-03-04

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

原著者： Amaury Pouly, Mahsa Shirmohammadi, James Worrell

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

この論文は、数学とコンピュータサイエンスの境界にある少し難しそうな問題を、**「未来が明るいか（正の数か）、暗いか（負の数か）」**というシンプルな問いに落とし込んで、それを解くための新しい方法を見つけたというお話です。

専門用語を全部捨てて、**「予測不能な未来を予測する機械」**という物語として説明しましょう。

1. 物語の舞台：「揺れる未来の機械」

まず、想像してみてください。ある機械が毎日、ある数値を出力しているとします。
普通の機械（線形漸化式）なら、昨日の数値と一昨日の数値を足して、きっちり明日の数値が決まります。これは**「完全な予測」**ができる機械です。

しかし、この論文で扱っているのは**「揺れる未来の機械（Nearly Linear Recurrent Sequence）」です。
この機械は、計算式には決まりがあるのですが、「少しだけノイズ（誤差）」**が入ります。
例えば、「明日の値は、昨日の値の 2 倍」というルールがあるのに、実際には「±0.1 くらいはズレるかもしれない」という不確実性があるのです。

現実世界での例え：
- 普通の機械： 振り子時計。正確に刻む。
- この機械： 風が吹く中を歩く人。「まっすぐ進め」というルールはあるが、風（ノイズ）で少し左に行ったり右に行ったりする。

2. 問いかけ：「この機械は永遠に『プラス（前向き）』でいられるか？」

研究者たちが知りたいのは、この「揺れる機械」が、どんな風の吹き方（ノイズの入り方）をしても、永遠に「正の数（プラス）」を出し続けることができるか？ という問題です。

もし「いいえ」なら： 風が強く吹きすぎた瞬間に、機械が「マイナス（絶望）」の値を出して、もう元に戻れないかもしれません。
もし「はい」なら： どんなに風が吹いても、機械は決してマイナスにはならず、常に前向きに動き続けます。

この問題は、**「ポジティブ問題（Positivity Problem）」**と呼ばれています。

3. 過去の壁：「2 次元までは解けたが、3 次元は難しすぎる」

実は、この「ノイズのない完全な機械（普通の数学の数列）」の「プラス問題」は、50 年前から**「解けるかどうかわからない」**という難問でした。
特に、機械の動きが複雑になる（次元が高くなる）と、答えを出すのが不可能に近いと言われています。

しかし、この論文のすごいところは、「揺れる機械」の中でも、動きが比較的単純な「2 次元（平面上の動き）」の場合に限り、この問題を「解ける！」と証明した点です。

4. 解決の鍵：「無限の足し算と、超越数という魔法」

彼らがどうやって解いたのか？ここが最も面白い部分です。

彼らは、この「揺れる機械」が最悪のケース（一番マイナスになりやすい風）をどう動くかを計算しました。すると、その答えは**「無限に続く足し算」**の形になりました。

「この無限の足し算の結果が、『0』になることは絶対にない」

これが証明できれば、「機械がマイナスになるかどうか」を計算機でチェックすればいいことになります。

ここで登場するのが、**「超越数（Transcendental Number）」**という魔法のような概念です。

代数数： 整数の式で表せる数（例： $\sqrt{2}$ や $1/3$ ）。
超越数： 整数のどんな式でも表せない、もっと不思議な数（例： $\pi$ や $e$ ）。

彼らは、この「無限の足し算」の結果が、**「超越数（つまり、0 にも、どんな整数の式にもならない不思議な数）」**であることを証明しました。
「0 ではない超越数」であれば、その値は「0 に極めて近いが、0 ではない」ので、コンピュータで計算すれば、それが「プラス」か「マイナス」か、有限の計算で判断できるのです。

アナロジー：
まるで、**「無限に続く迷路」の出口が、地図には載っていない「幻の島（超越数）」**にあると証明したようなものです。「幻の島は 0 地点（海）ではない」と分かれば、もう地図（計算機）を使って「島が東か西か」を調べるだけでいいのです。

5. 結論：なぜこれが重要なのか？

この研究は、単なる数学の遊びではありません。

制御理論： ロボットや自動運転車が、センサーの誤差（ノイズ）があっても、安全な範囲（プラスの領域）から外れないかを保証する技術に応用できます。
プログラム解析： ソフトウェアが無限ループで止まってしまうか、あるいは安全に動作し続けるかを判定するのにも役立ちます。

まとめると：
この論文は、**「少しズレる未来を予測する機械」が、「どんなズレがあっても、決して絶望（マイナス）に陥らないか」を判断する新しい方法を発見しました。
その鍵は、「無限の足し算の結果は、0 にはなり得ない不思議な数（超越数）だ」**という、数学の奥深い真理（数論）を突き止めたことでした。

これにより、2 次元の動きをするシステムについては、もう「答えがわからない」という状態から脱出し、コンピュータが自動的に「安全か否か」を判定できるようになったのです。

この論文「Positivity of Nearly Linearly Recurrent Sequences（ほぼ線形漸化式列の正性）」の技術的な要約を以下に示します。

1. 問題の定義と背景

ほぼ線形漸化式（Nearly Linear Recurrence Sequences: NLRS）
従来の線形漸化式（LRS）の一般化として、以下の不等式で定義される数列 $u = (u_n)_{n=0}^\infty$ を「ほぼ線形漸化式列」と呼びます。
$\varepsilon_0 \le u_{n+d} - a_{d-1}u_{n+d-1} - \dots - a_0 u_n \le \varepsilon_1$
ここで、 $a_i, \varepsilon_0, \varepsilon_1$ は有理数（または実代数数）であり、 $a_0 \neq 0$ です。

$\varepsilon_0 = \varepsilon_1 = 0$ の場合、これは古典的な線形漸化式になります。
$\varepsilon_0 = \varepsilon_1$ の場合、非斉次線形漸化式になります。
一般の $\varepsilon_0, \varepsilon_1$ は、制御理論における「線形時不変（LTI）システム」における外乱や、プログラム解析における「線形制約ループ」の非決定性をモデル化したものと見なせます。

正性問題（Positivity Problem）
与えられた漸化式（係数 $a_i, \varepsilon_0, \varepsilon_1$ ）と初期値 $u_0, \dots, u_{d-1}$ に対して、その漸化式を満たすすべての数列 $u$ について、すべての $n$ に対して $u_n \ge 0$ となるかどうかを決定する問題です。

これは、線形漸化式列（LRS）の正性問題（Skolem 問題とも関連）の一般化です。LRS の正性問題は 50 年以上の未解決問題であり、次数 5 以下では決定可能ですが、一般の次数では未解決です。
NLRS の正性問題は、LTI システムにおける「非到達性問題（non-reachability problem）」の特殊ケースでもあります。

2. 主要な貢献と結果

この論文の中心的な成果は、次数 2 のほぼ線形漸化式に対する正性問題の決定手続き（アルゴリズム）の構築です。

決定可能性: 次数 2 の NLRS について、正性問題が決定可能であることを証明しました。
係数の一般性: 漸化式の定数係数が実代数数であっても適用可能です。
核心的な技術的貢献: 無限級数の正則性（超越性）に関する新しい結果（定理 2）を導き出し、これを決定手続きの終止証明に利用しました。

3. 手法とアプローチ

決定手続きは、以下の 3 つの主要なステップで構成されます。

3.1 行列べき形式への定式化と最小値の導出

まず、NLRS を制御理論の LTI システムの形式（ $x_{n+1} = A x_n + r_n e_1$ ）で記述します。ここで $r_n \in [\varepsilon_0, \varepsilon_1]$ は制御入力です。

バンバン制御原理（Bang-Bang Principle）の適用: 数列 $u_n$ が負になるかどうかを判定するため、すべての可能な制御入力 $r_n$ に対して $u_n$ を最小化するケースを考えます。
このとき、最小値を与える制御は、区間 $[\varepsilon_0, \varepsilon_1]$ の端点（ $\varepsilon_0$ または $\varepsilon_1$ ）のいずれかであることが示されます。
これにより、問題の判定は、特定の「最小値数列」 $u^{(\min)}_n$ の正性を調べることに帰着されます。この数列は、ゼロ制御による LRS と、制御入力による LRS の和、および絶対値を含む項の和として表現されます。

3.2 次数 2 の場合のケース分析

次数 2 の場合、特性多項式の根（固有値）の性質に基づいて 4 つのケースに分類して解析します。

あるべき乗が正の実数スペクトルを持つ場合: 数列が特定のクラス（ $C_{pos}$ ）に属し、正性の決定が可能。
スペクトル半径 > 1: 数列は発散し、負の無限大に近づくため、正ではないと判定。
スペクトル半径 = 1: 絶対値の和が発散するため、正ではないと判定。
スペクトル半径 < 1: 数列はある極限値に収束します。この極限値が 0 かどうか、およびその符号を判定する必要があります。

3.3 超越性定理（Theorem 2）の証明

ケース 4（スペクトル半径 < 1）における決定的なステップは、以下の無限級数の超越性を証明することです。
$\alpha := \sum_{n=0}^{\infty} |a\lambda^n + \bar{a}\bar{\lambda}^n|$
ここで、 $|\lambda| < 1$ かつ $\lambda^n \notin \mathbb{R}$ です。

定理 2: 上記の条件を満たすとき、 $\alpha$ は超越数（整数係数多項式の根ではない）である。
証明の概要:
1. 対話法（Contradiction）: $\alpha$ が代数的であると仮定します。
2. ディオファントス近似と連分数: $\lambda$ の偏角 $\theta$ の連分数展開を用いて、数列 $|a\lambda^n + \bar{a}\bar{\lambda}^n|$ が「ほとんどすべての」インデックスで高次の線形漸化式を満たすことを示します。
3. 部分空間定理（Subspace Theorem）: Schlickewei の $p$ -進部分空間定理を適用します。 $\alpha$ が代数的であるという仮定の下で、特定の線形形式が急速に 0 に収束する列が存在すると導き出されます。
4. 対数線形形式の下限（Baker の定理）: 一方で、Baker の定理を用いて、その線形形式の値が 0 に近づく速度の下限（ $|L(\Lambda_n)| \gg |\lambda|^{mn}$ ）を導きます。
5. 矛盾: 部分空間定理から得られる収束速度の上限と、Baker の定理から得られる下限が矛盾するため、 $\alpha$ は超越数でなければなりません。

この結果により、極限値 $\lim_{n\to\infty} u^{(\min)}_n$ が 0 ではないことが保証され、有限精度の数値計算によってその符号を決定できることが示されます。

4. 意義と今後の展望

理論的意義:
- 線形漸化式列（LRS）の正性問題の未解決な一般化に対して、次数 2 のケースで初めて決定可能性を示しました。
- 数論的アプローチ（超越性理論）を、制御理論やプログラム解析の決定問題（到達性・正性）に応用する新しい道筋を開きました。
- 従来の LRS 解析では使われなかった「無限級数の超越性」という強力な道具を導入しました。
応用分野:
- 制御理論: 外乱が存在する LTI システムの安全性（半空間からの非到達性）の検証。
- プログラム解析: 非決定性を持つ線形制約ループの終止性や正性解析。
今後の課題:
- 次数 3 以上の NLRS への拡張は大きな課題ですが、現在進行中の研究課題です。
- 「存在する正数列があるか（Existential variant）」という問題や、より一般的な目標集合（点など）に対する非到達性問題については、バンバン制御原理が適用できないため、異なる手法が必要になると予想されています。

結論

この論文は、制御理論と数論を融合させ、次数 2 のほぼ線形漸化式列の正性問題を解決する決定手続きを提示しました。その核心は、関連する無限級数の超越性を証明する新しい定理（定理 2）にあり、これはディオファントス近似論の強力なツール（部分空間定理と Baker の定理）を駆使して導かれています。この成果は、LTI システムの解析やプログラム検証の分野において、新たな決定可能性の境界を示す重要なステップです。