ヒルベルトの第10問題

ヒルベルトの第10問題は、ドイツの数学者ダフィット・ヒルベルトが1900年に提起した数学的問題リストの10番目の問題である。これは、任意のディオファントス方程式（整数係数と有限個の未知数を持つ多項式方程式）に対して、すべての未知数が整数値をとる解が存在するかどうかを判定できる一般的なアルゴリズムを提供することを課題としている。

例えば、ディオファントス方程式${\displaystyle 3x^{2}-2xy-y^{2}z-7=0}$整数解を持つ：${\displaystyle x=1,\ y=2,\ z=-2}$対照的に、ディオファントス方程式は${\displaystyle x^{2}+y^{2}+1=0}$そのような解決策は存在しない。

ヒルベルトの第 10 問題の解は、そのような一般的なアルゴリズムは存在しないことを示しています。これは、マーティン デイビス、ユーリ マティヤセヴィッチ、ヒラリー パトナム、ジュリア ロビンソンの21 年にわたる共同研究の結果であり、マティヤセヴィッチが 1970 年に定理を完成させました。^{[ 1 ] [ 2 ] [ 3 ]}この定理は現在、マティヤセヴィッチの定理または MRDP 定理 (その解に大きく貢献した 4 人の姓の頭文字) として知られています。

すべての係数と変数が正の整数に制限されている場合、関連する多項式恒等式テストの問題は、タルスキの高校代数問題の決定可能な（指数計算なしの）変種であり、時には次のように表記されます。${\displaystyle {\overline {HSI}}.}$^{[ 4 ]}

マティヤセビッチ/MRDP定理は、計算可能性理論と数論という2つの概念を結びつけ、いくつかの驚くべき結果をもたらす。おそらく最も驚くべきことは、普遍的なディオファントス方程式の存在である。

多項式が存在する${\displaystyle p(a,n,x_{1},\ldots ,x_{k})}$任意のディオファントス集合が与えられた場合${\displaystyle S}$数があります${\displaystyle n_{0}}$そのため

$${\displaystyle S=\{\,a\mid \exists x_{1},\ldots ,x_{k}\,[p(a,n_{0},x_{1},\ldots ,x_{k})=0]\,\}.}$$

これは、ディオファントス集合が再帰的に列挙可能な集合と等しいため、チューリングマシンとも等しいという事実から明らかです。チューリングマシンには、あらゆるアルゴリズムを実行できる万能チューリングマシンが存在することはよく知られています。

^{ヒラリー・パトナムは[ 8 ]}任意のディオファントス集合について指摘している。${\displaystyle S}$正の整数の多項式が存在する

${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})}$

そのため${\displaystyle S}$は、 が想定する値の中の正の数のみで構成される。${\displaystyle q}$変数として

${\displaystyle x_{0},x_{1},\ldots ,x_{n}}$

すべての自然数の範囲。これは次のように見ることができます。

${\displaystyle p(a,y_{1},\ldots ,y_{n})=0}$

ディオファントス的な定義を提供する${\displaystyle S}$そうすれば、設定するだけで十分です

$${\displaystyle q(x_{0},x_{1},\ldots ,x_{n})=x_{0}[1-p(x_{0},x_{1},\ldots ,x_{n})^{2}].}$$

例えば、値域の正の部分が素数のみとなるような多項式が存在する。（一方で、素数のみをとる多項式は存在しない。）これは、階乗、二項係数、フィボナッチ数列など、再帰的に列挙可能な他の自然数の集合にも当てはまる。

その他の応用例は、論理学者が$\displaystyle \Pi _{1}^{0}}$命題、またはゴールドバッハ型命題とも呼ばれる。^{[ b ]}これらは、すべての自然数が、それぞれの数に対してアルゴリズム的に検証可能な特定の性質を持つという点で、ゴールドバッハ予想に似ている。 ^{[ c ]}マティヤセビッチ/MRDP定理は、このような命題のそれぞれが、特定のディオファントス方程式が自然数で解を持たないという主張と同等であることを示唆している。^{[ d ]}多くの重要かつ有名な問題がこの形式である。特に、フェルマーの最終定理、リーマン予想、四色定理などである。さらに、ペアノ算術やZFCなどの特定の形式体系が無矛盾であるという主張は、次のように表現できる。$\displaystyle \Pi _{1}^{0}}$文。そのアイデアは、クルト・ゲーデルに倣って証明を自然数で符号化し、証明を表す数であるという性質がアルゴリズム的に検証可能であるようにすることである。

$\displaystyle \Pi _{1}^{0}}$文には、もしそれが偽であれば、その事実は通常の形式体系のいずれにおいても証明可能であるという特別な性質があります。これは、偽であるということは、単純な算術で検証できる反例の存在に相当するからです。したがって、もし$\displaystyle \Pi _{1}^{0}}$ある文が、その文自体もその否定もこれらの体系のいずれにおいても証明できないような文であれば、その文は真でなければならない。

ゲーデルの不完全性定理の特に印象的な形式は、マティヤセビッチ/MRDP定理の帰結でもある。

させて

${\displaystyle p(a,x_{1},\ldots ,x_{k})=0}$

計算不可能な集合のディオファントス的定義を提供する。${\displaystyle A}$自然数のシーケンスを出力するアルゴリズムである。${\displaystyle n}$対応する方程式

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0}$

自然数には解がない。すると、ある数が存在する。${\displaystyle n_{0}}$これは、${\displaystyle A}$実際には方程式は

${\displaystyle p(n_{0},x_{1},\ldots ,x_{k})=0}$

自然数には解がない。

この定理が正しいことを確認するには、そのような数が存在しない場合、${\displaystyle n_{0}}$アルゴリズム的に数値のメンバーシップをテストすることができる${\displaystyle n}$この計算不可能なセットで、アルゴリズムを同時に実行することによって${\displaystyle A}$確認する${\displaystyle n}$出力は、すべての可能なものをチェックしながらも出力されます。${\displaystyle k}$-方程式の解を求める自然数の組

${\displaystyle p(n,x_{1},\ldots ,x_{k})=0}$

そしてアルゴリズムを関連付ける${\displaystyle A}$ペアノ算術やZFCなどの通常の形式体系のいずれかと組み合わせることで、公理の帰結を体系的に生成し、数値を出力する。${\displaystyle n}$文が

${\displaystyle \neg \exists x_{1},\ldots ,x_{k}\,[p(n,x_{1},\ldots ,x_{k})=0]}$

生成される。すると、この定理によれば、この形式の偽の命題が証明されるか、または問題のシステムにおいて真の命題が未証明のまま残るかのどちらかであることがわかる。

ディオファントス集合の次数は、その集合を定義する方程式における多項式の最小次数と考えることができます。同様に、そのような集合の次元は、定義方程式における未知数の最小数と考えることができます。普遍的なディオファントス方程式が存在するため、これら2つの量には絶対的な上限が存在することは明らかであり、これらの上限を決定することには大きな関心が寄せられてきました。

1920年代にはすでに、トーラルフ・スコレムが、任意のディオファントス方程式は4次以下の方程式と等価であることを示していた。彼の巧妙な手法は、未知数をある未知数の2乗または2つの未知数の積に等しいとする方程式によって、新たな未知数を導入することであった。このプロセスを繰り返すと、2次方程式の連立方程式が得られ、次にそれらの2乗を合計することで4次方程式が得られる。したがって、すべてのディオファントス方程式は自明に4次以下である。この結果が最良のものであるかどうかは不明である。

ジュリア・ロビンソンとユーリ・マティヤセヴィッチは、すべてのディオファントス集合の次元が13以下であることを示した。後にマティヤセヴィッチは、未知数が9つで十分であることを示し、彼らの方法を洗練させた。この結果が最善ではない可能性は十分にあるが、それ以上の進展はない。^{[ e ]}したがって、特に、未知数が9つ以下のディオファントス方程式の自然数での可解性をテストするアルゴリズムはない。有理整数解の場合（ヒルベルトが最初に提起したように）、4スクエアトリックは、未知数が36以下の方程式に対するアルゴリズムがないことを示している。しかし、孫子偉は、整数の問題は未知数が11以下の方程式でも解けないことを示した。

マーティン・デイビスは、ディオファントス方程式の解の数に関するアルゴリズムの問​​題を研究した。ヒルベルトの第10問題は、その数が0であるかどうかを問うものである。${\displaystyle A=\{0,1,2,3,\ldots ,\aleph _{0}\}}$そして${\displaystyle C}$の真非空部分集合である${\displaystyle A}$デイビスは、与えられたディオファントス方程式の解の数が集合の要素であるかどうかを判定するアルゴリズムは存在しないことを証明した。${\displaystyle C}$したがって、ディオファントス方程式の解の数が有限であるか、奇数であるか、平方数であるか、素数であるかなどを判定するアルゴリズムは存在しない。

MRDP定理の証明はRocq（以前はCoqとして知られていた）で形式化されている。^{[ 9 ]}

ヒルベルトは有理整数についてこの問題を提起したが、多くの環（特に、要素数が可算である任意の環）についても同様の問題を提起することができる。明らかな例としては、代数体の整数環や有理数環が挙げられる。

代数体上の整数環に関するヒルベルトの第10問題については、多くの研究が行われてきた。ハロルド・N・シャピロとアレクサンドラ・シュラペントフは、ヤン・デネフとレナード・リプシッツによる先行研究に基づき、類体論を用いて、以下のことを証明した。

ヒルベルトの第10問題は、有理数体上のガロア群がアーベル群である任意の代数的数体の整数環に対しては解けない。

シュラペントフとタナセス・フェイダスは（互いに独立に）ちょうど１組の複素共役埋め込みを許容する代数的数体について同じ結果を得た。

上記の結果でカバーされているもの以外の代数的数体の整数環の問題は未解決のままである。同様に、多くの関心が寄せられているにもかかわらず、有理数体上の方程式の問題は未解決のままである。バリー・マズールは、有理数体上の任意の多様体について、解の集合の実数体上の位相的閉包は有限個の成分しか持たないと予想している。^{[ 10 ]}この予想は、整数が有理数体上でディオファントス的ではないことを意味し、したがって、この予想が正しい場合、ヒルベルトの第10問題に対する否定的な回答には、他の環で使用されるアプローチとは異なるアプローチが必要になる。

2024年、ピーター・コイマンスとカルロ・パガーノは、加法的組み合わせ論を用いて、ヒルベルトの第10問題がすべての整数環に対して決定不能であると主張する証明を発表した。^{[ 11 ] [ 12 ]}その後、別の数学者チームが、異なる方法を用いて同じ結果の別の証明を主張した。^{[ 11 ] [ 13 ]}

• タルスキーの高校代数学の問題

• デイヴィッド・ヒルベルト(1901)。 「数学の問題」。数学と物理学のアーカイブ。シリーズ第 3 弾（ドイツ語）。1：44～ 63、213 ～ 247。
• Davis, Martin ; Matiyasevich, Yuri ; Robinson, Julia (1976). 「ヒルベルトの第10問題：ディオファントス方程式：負の解の正の側面」。Felix E. Browder (編) 『ヒルベルト問題から生じる数学的発展』純粋数学シンポジウム論文集、第XXVIII巻、第2号 、アメリカ数学会、 323–378頁。ISBN  0-8218-1428-1. Zbl 0346.02026 . 『ジュリア・ロビンソン全集』（ソロモン・フェファーマン 編、 269 ～ 378ページ、アメリカ数学会、1996年） に再録。
• Martin Davis、「ヒルベルトの第10問題は解けない」、American Mathematical Monthly  、第80巻（1973年）、 233 ～ 269ページ。Martin Davis著『計算可能性と解けなさ』 、ドーバー社再版1982年に付録として再録。
• Davis, Martin ; Hersh, Reuben (1973). "ヒルベルトの第10問題". Scientific American . 229 (5): 84– 91. Bibcode : 1973SciAm.229e..84D . doi : 10.1038/scientificamerican1173-84 .
• Jan Denef、Leonard Lipschitz、Thanases Pheidas、Jan van Geel 編、「ヒルベルトの第 10 問: 1999 年11 月 2 日～ 5 日、ベルギー、ゲント大学でのワークショップ」『現代数学』第 270 巻 (2000 年)、アメリカ数学会。
• M. ラム・マーティとブランドン・フォデン：「ヒルベルトの第10問題：論理学、数論、計算可能性入門」、アメリカ数学会、 ISBN 978-1-4704-4399-3（2019年6月）
• シュラペントフ、アレクサンドラ（2007）。ヒルベルトの第10問題。ディオファントス類と大域体への拡張。新数学モノグラフ第 7巻。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-83360-8. Zbl 1196.11166 . 

• ヒルベルトの第10問題：数学的発見の歴史
• ヒルベルトの第10問題のページ！
• 孫志偉（2000年4月14日）「ヒルベルトの第10問題と関連トピックについて」（PDF）。maths.nju.edu.cn 。 2025年9月27日取得。
• YouTubeで公開中のジュリア・ロビンソンとヒルベルトの第10問題に関する予告編