🔢 mathematics

An AI Proof of 18-Variable Undecidability for Diophantine Equations over $\mathbb Z[i]$

本論文は、最適化された変数削減技術を通じて、マチャティセビッチとサンによる従来の20変数の境界を改善し、ガウス整数上におけるディオファントス方程式の可解性がわずか18変数で決定不能であることを示す、AIによって生成された証明を提示するものである。

原著者： Yuchen Ding, Junfeng Li

公開日 2026-06-12

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

CC BY 4.0

原著者： Yuchen Ding, Junfeng Li

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

大きな全体像：「解けないパズル」

巨大で魔法のようなパズルボックスを想像してみてください。その中には、多くの未知数（変数）を含む複雑な方程式（数学の問題）が入っています。あなたの目標は、**「この方程式には解が存在するか？」**という問いに答えることです。

長い間、数学者たちは、変数の数が十分に多くなると、この問いにコンピュータプログラムで答えることは不可能になることを知っていました。それは、あらゆる迷路に出口があるかどうかを判定するルールブックを作ろうとするようなものです。迷路が複雑になりすぎると、どんなルールブックでもすべてをカバーできなくなってしまいます。

この論文は、ガウス整数（$a + bi $という形をした、$ -1 $の平方根$ i$ を含む数）と呼ばれる特定の種類のパズルボックスに関するものです。著者である Yuchen Ding と Junfeng Li は、AI を用いて、もしパズルボックスに 18 個の未知数があれば、解が存在するかどうかを常に判定できるコンピュータプログラムは存在しないことを証明しました。

前回の記録：20 変数

この論文より前では、マチヤセビッチと Sun による研究が、パズルを解けなくするために 20 個の未知数が必要であるという、最も優れた既知の結果でした。彼らは、これらの「解けないパズル」を構築するための特定のレシピを持っていました。

この論文の著者たちは、「私たちはもっと少ないパーツでそれができる」と言いました。彼らは、レシピを 20 個のパーツから 18 にまで縮小することに成功したのです。

彼らがどのように行ったか：2つの巧妙なトリック

変数を2つ節約した方法を理解するために、複素数の世界の中で、ある数が「実数（整数）」であるかどうかをテストする機械を作っていると考えてみてください。

トリック 1：「余分なカップを使わない」戦略

従来の方法：
材料を混ぜるレシピがあり、その指示に分数が含まれている場合を想像してください。コンピュータで計算を成立させるために、通常は分母（分数の下の数）を取り除いてすべてを整数にするための**「余分なカップ」**（新しい変数）が必要です。この余分なカップが、20 変数の制限の中でスペースを占有します。

新しい方法：
著者たちは、その余分なカップは必要ないと気づきました。分数を片付けるために新しい変数（カップ）を追加する代わりに、既存の材料に対して2つの厳格なルールを追加したのです。

比喩： こぼれたものをキャッチするために新しいバケツを持ってくるのではなく、中身がこぼれないように既存のバケツの蓋をきつく閉めたのです。
結果： 数学的な整合性を保つためにヘルパー変数（変数）を必要としなくなったため、1 つの変数を節約できました。

トリック 2：「魔法の鍵」ガジェット

従来の方法：
古いレシピでは、特定の数がゼロではないことを確認するため（これはパズルが機能するために極めて重要です）、2 つの異なる変数が「安全確認」として機能する必要がありました。それは、ドアが詰まっていないかを確認するために、2 つの異なる鍵を使うようなものでした。

新しい方法：
著者たちは、特別な「魔法の鍵」ガジェットを発明しました。彼らは次のような特定の公式を作成しました： $(2R + 1)(3R + 1)$ 。

魔法の性質： この公式は、どんな数字を代入しても、決してゼロにはなりません。しかし、チェックしたい「ゼロではない数」がある場合、 $R$ の値を適切に選べば、この公式はその数で割り切れるようになります。
節約の仕組み： この単一の公式が 2 つの独立した安全確認の役割を果たすため、2 つの変数ではなく、たった 1 つの変数（ $R$ ）だけで済んだのです。
結果： これにより、2 番目の変数を節約できました。

最終的なカウント

これら 2 つのトリックを組み合わせることで、パズルが解けないことを証明するために必要な未知数の総数を削減しました。

メインのパズルのための 10 個の変数（先行研究より）
最初の「整数テスト」（数字が整数であるかの確認）のための 3 つの変数
2 番目の「整数テスト」のための 3 つの変数
「結合」ステップのための 1 つの変数
「魔法の鍵」ガジェットのための 1 つの変数
合計：18 変数

これが意味すること

この論文は、どのようなコンピュータプログラムであっても、問題が解けなくなる（不可能になる）変数の数には限界があることを証明しています。

以前： その限界は 20 であると知られていました。
現在： 限界は 18 であることが証明されました（あるいは、さらに低い可能性もありますが、18 が新たに確定した下限です）。

著者たちは、絶対的な最小値を見つけたわけではない（おそらく 17 や 16 もあり得る）ものの、これら 2 つの具体的な「省スペース」トリックを用いることで、ハードルを 20 から 18 へと下げることに成功したと強調しています。

まとめ

これは、旅行の荷造りに例えられます。古いルールでは、「服を運ぶには 20 個のスーツケースが必要です」と言われていました。これらの著者たちは、服をよく観察し、「もっときつく畳める（トリック 1）」ことや「圧縮袋が使える（トリック 2）」ことに気づき、「実際には 18 個のスーツケースだけで十分だ」と証明したのです。

これは、旅行が簡単になったという意味ではありません。単に、「不可能」という閾値に、以前考えられていたよりも少ないリソースで到達できるようになったことを意味しています。

技術要約： $\mathbb{Z}[i]$ 上のディオファントス方程式における18変数非決定性のAIによる証明

問題設定
本論文は、ガウス整数環 $\mathbb{Z}[i]$ におけるヒルベルトの第10問題に対処するものである。この問題は、与えられた環上の任意の多項式方程式が解を持つかどうかを判定するアルゴリズムの存在を問うものである。整数 $\mathbb{Z}$ 上でのこの問題の非決定性は、マティヤセヴィッチ、デイビス、プトゥナム、およびロビンソンによる定理によって確立されているが、自然な洗練として、非決定性を維持するために必要な未知数の最小数が問題となる。マティヤセヴィッチとSunによる先行研究では、 $\mathbb{Z}[i]$ における非決定性は20個の未知数で保持されることが確立されていた。本論文は、この境界を18個の未知数へと削減する証明を提示する。

手法と枠組み
本証明は、以下の3つの核となる構成要素に基づく、マティヤセヴィッチとSunによる一般的な枠組みを継承している。

Sunの固定変数定理： 再帰的に列挙可能であるが非再帰的な集合 $A \subseteq \mathbb{N}$ と、集合 $A$ への属性は $P(a, z_1, \dots, z_{10}) = 0$ （ただし $z_{10} \neq 0$ ）の整数解の存在と等価であるような多項式 $P(Z_0, \dots, Z_{10})$ を利用する。
有理整数に対するディオファントス・テスト： $\mathbb{Z}[i]$ の要素が実際に有理整数であるかどうかを判定するための特定の多項式テスト（補題3）を用いる。
有理性基準： 特定の構成された和の有理性に基づいて、変数を有理整数に強制するための $\mathbb{Q}(i)$ 上の基準（補題4）を適用する。

著者らは、以下の2つの具体的な修正を導入することで、変数数を20から18へと削減することに成功した。

主要な貢献と技術的修正

分母除去変数の排除：
20変数の構成では、有理性基準を適用する際に分母を除去するための補助変数（auxiliary variable）が導入されていた。著者らはこれを、変数 $Z_1, \dots, Z_{10}$ に課される2つの直接的な整数条件に置き換えた。
$Y = 2 \prod_{k=1}^{10} (3Z_k + 1)$ とする。分母を除去するための変数を追加する代わりに、証明では以下の条件を課す：
$Y^{10} \in \mathbb{Z} \quad \text{および} \quad Y^{11} + \sum_{k=1}^{10} Z_k Y^{10-k} \in \mathbb{Z}.$
$Y \neq 0$ であるため、これらの条件により、量 $Y + \sum Z_k Y^{-k}$ が有理数であることが保証される。この修正により、変数が1つ節約される。
一変数ガジェットによる非ゼロ条件の吸収：
従来の構成では、非ゼロ条件（具体的には積 $Z_{10}V_0V_1$ ）を強制するために2つの変数が必要であった。著者らは、一変数多項式ガジェット $Q(R) = (2R + 1)(3R + 1)$ を導入した。

特性： $Q(R)$ は $\mathbb{Z}[i]$ 上で決して零にならない。さらに、任意の非ゼロ整数 $n$ に対して、ある整数 $R$ が存在して $n \mid Q(R)$ を満たす。
適用： このガジェットは「関係結合補題」（補題2）に組み込まれる。非ゼロ条件を強制するための別個の方程式を用意する代わりに、条件は単一の方程式 $f(C_0, C_1, N, Q(R), M) = 0$ に吸収される。もし $N=0$ であれば、方程式は $Q(R)^4 = 0$ に帰着するが、これは不可能である。したがって、この方程式は追加の変数を必要とせずに、暗黙的に $N \neq 0$ を強制する。この修正により、2つ目の変数が節約される。

変数数の内訳
結果として得られるシステムは、正確に18個の変数を使用する：

$Z_1, \dots, Z_{10}$ ：Sunの固定変数入力からの10個の変数。
$V_0, X_0, Y_0$ および $V_1, X_1, Y_1$ ： $U_0 = Y^{10}$ および $U_1 = W$ （ $W$ は和から導出される）に対する整数テストに使用される2組の3変数。
$M$ ：関係結合補題からの結合変数。
$R$ ：非ゼロガジェットからの単一の変数。
合計： $10 + 3 + 3 + 1 + 1 = 18$ 。

主要な結果
本論文は定理1を証明する： $\mathbb{Z}$ に係数を持つ任意の多項式方程式 $F(X_1, \dots, X_{18}) = 0$ が $\mathbb{Z}[i]^{18}$ に解を持つかどうかを判定するアルゴリズムは存在しない。

本証明は、非再帰的集合 $A$ への属性が、18個の未知数を持つ $\mathbb{Z}[i]$ 上の単一の多項式方程式によって表現できることを示している。補題1によれば、構成から導かれる有限の方程式系は、新しい変数を導入することなく、整数係数を保持したまま単一の多項式方程式へと結合することができる。

意義と主張
著者らは、この結果が変数数を2つ減少させることにより、マティヤセvichとSunの20未知数の定理を改善したと述べている。本論文は、これが絶対的な最適性を主張するものではないことを明記している。例えば、17個への削減を実現するには、より小さな整数テスト、整数条件のための共有ウィットネス、より強力な固定変数入力、あるいは異なる結合メカニズムなどのさらなる改善が必要となる。本研究は、ガウス整数上のディオファントス非決定性の確立された枠組み内における技術的な洗練として機能するものである。