Hilbertの第10問題

同義語：Hilbert's tenth problemヒルベルトの第10問題Hilbertの第十問題

概要

前提知識: 帰納的可算集合, 停止問題, Lagrangeの四平方定理

整数係数の多項式方程式 $P(x_1,\dots,x_n)=0$ が整数解をもつかどうかを、有限回の操作で判定する一般的な方法はあるか。これが、Hilbert が 1900 年の国際数学者会議の講演で挙げた問題の 10 番目、Hilbertの第10問題（Hilbert's tenth problem）である（Dav73 p. 233）。答えは否定的で、そのような方法は存在しない。
否定的な解決は、論理学の側の計算可能性の理論と、数論の側の方程式の研究が出会って得られた。Davis、Putnam、J. Robinson は 1961 年に、帰納的可算集合がすべて「指数関数を許した方程式」で定義できることを示し、1970 年に Matiyasevich が指数関数そのものが多項式方程式で定義できることを示して証明を完成させた（Dav73 §9、pp. 264–266）。結論は 4 人の頭文字をとって MRDPの定理（MRDP theorem）とよばれ、「帰納的可算な集合は Diophantus 集合である」と述べる。
この記事では、Diophantus 集合を定義してその基本的な性質を証明し、MRDP の定理（この記事では証明しない）から第 10 問題の否定的な解決を導く。さらに、MRDP の定理の帰結として、正の値の全体がちょうど素数の全体になる多項式が存在すること、未知数の個数と次数を一様に押さえられること、解をもたないことが証明できない方程式があることを示す。

記法と前提

$\mathbb{N}=\{0,1,2,\dots\}$、$\mathbb{Z}$ は整数全体とする。「多項式」は整数係数の多項式を指し、係数に負の数を許す。決定可能・半決定可能（帰納的可算）、自己停止集合 $K$、$W_e$ は停止問題の定義「決定可能と半決定可能」「停止問題」と帰納的可算集合の定義「帰納的可算集合」による。$\mathbb{N}^n$ の部分集合についても、特性関数が計算可能なとき決定可能、ある部分計算可能関数の定義域であるとき帰納的可算という。
多項式に自然数の番号 $\ulcorner P\urcorner$ を付けておく。番号は、変数の個数・各単項式の係数と指数が番号から計算でき、逆にそれらから番号が計算できるように付ける。こうすると、変数に整数を代入した値の計算、変数に多項式を代入した多項式の番号の計算などは、番号の上で計算可能になる（Gödel数化と同じ考え方である）。

問題の定式化

Hilbert の第 10 問題

変数の個数を問わない多項式の番号の集合として
$$ D_{\mathbb{Z}}:=\{\ulcorner P\urcorner\mid P(x_1,\dots,x_n)=0\text{ は }\mathbb{Z}^n\text{ に解をもつ}\},\qquad D_{\mathbb{N}}:=\{\ulcorner P\urcorner\mid P(x_1,\dots,x_n)=0\text{ は }\mathbb{N}^n\text{ に解をもつ}\} $$
とおく。Hilbert の第 10 問題 は、$D_{\mathbb{Z}}$ が決定可能かどうかを問う問題である。

Hilbert が求めたのは「判定の方法」であった。それを「決定可能」と読むことは、機械的な手順を Turing 機械で表す Church–Turingのテーゼによる。解が整数か自然数かは本質的な違いではない。

整数解と自然数解

多項式 $P(x_1,\dots,x_n)$ が $\mathbb{N}^n$ に解をもつことと、$4n$ 変数の多項式
$$ P^{\square}:=P\bigl(a_1^2+b_1^2+c_1^2+d_1^2,\ \dots,\ a_n^2+b_n^2+c_n^2+d_n^2\bigr) $$
が $\mathbb{Z}^{4n}$ に解をもつことは同値である。
多項式 $Q(x_1,\dots,x_n)$ が $\mathbb{Z}^n$ に解をもつことと、$2n$ 変数の多項式 $Q^{-}:=Q(u_1-v_1,\dots,u_n-v_n)$ が $\mathbb{N}^{2n}$ に解をもつことは同値である。
$D_{\mathbb{Z}}$ が決定可能であることと、$D_{\mathbb{N}}$ が決定可能であることは同値である。

1：$P(m_1,\dots,m_n)=0$（$m_i\in\mathbb{N}$）なら、Lagrangeの四平方定理の定理「Lagrangeの四平方定理」により各 $m_i$ は 4 つの整数の平方の和 $a_i^2+b_i^2+c_i^2+d_i^2$ に書け、それが $P^{\square}$ の整数解を与える。逆に $P^{\square}$ の整数解があれば、$m_i:=a_i^2+b_i^2+c_i^2+d_i^2\in\mathbb{N}$ が $P$ の解である。

詳しい証明を開く

2：$Q(k_1,\dots,k_n)=0$（$k_i\in\mathbb{Z}$）なら、$k_i=u_i-v_i$ となる $u_i,v_i\in\mathbb{N}$（たとえば $u_i=\max(k_i,0)$、$v_i=\max(-k_i,0)$）が $Q^{-}$ の解である。逆は $k_i:=u_i-v_i$ とおけばよい。

3：$\ulcorner P\urcorner\mapsto\ulcorner P^{\square}\urcorner$ と $\ulcorner Q\urcorner\mapsto\ulcorner Q^{-}\urcorner$ は番号の上で計算可能である。1 により $\ulcorner P\urcorner\in D_{\mathbb{N}}\iff\ulcorner P^{\square}\urcorner\in D_{\mathbb{Z}}$ である。多項式の番号の全体 $\mathrm{Pol}$ は決定可能なので、$D_{\mathbb{Z}}$ が決定可能なら、$c\in\mathrm{Pol}$ のとき $\chi_{D_{\mathbb{Z}}}(\ulcorner P^{\square}\urcorner)$（$c=\ulcorner P\urcorner$）、$c\notin\mathrm{Pol}$ のとき $0$ を返す関数として、$D_{\mathbb{N}}$ の特性関数は計算可能である。2 から同様に逆が従う。$\square$

以下では、扱いやすい自然数解の側で考える。

Diophantus 集合

第 10 問題の否定的な解決では、方程式を与えて解を探すのとは逆に、解の集合を与えてそれを定義する方程式を探す。

Diophantus 集合

$S\subset\mathbb{N}^n$ が Diophantus 集合（Diophantine set）であるとは、ある $m\ge0$ と多項式 $P(x_1,\dots,x_n,y_1,\dots,y_m)$ があって、すべての $a\in\mathbb{N}^n$ について
$$ a\in S\iff\text{ある }b\in\mathbb{N}^m\text{ で }P(a,b)=0 $$
となることをいう。このとき $P$ を $S$ の 定義多項式、$y_1,\dots,y_m$ を 未知数 という。写像 $f\colon\mathbb{N}^n\to\mathbb{N}$ は、グラフ $\{(a,f(a))\mid a\in\mathbb{N}^n\}\subset\mathbb{N}^{n+1}$ が Diophantus 集合であるとき Diophantus 関数 であるという。

Dav73 は正の整数の組の集合で定義している。$S\subset\mathbb{N}^n$ に対し $S+\mathbf{1}:=\{(a_1+1,\dots,a_n+1)\mid a\in S\}$ とおくと、$S$ がこの記事の意味の Diophantus 集合であることと、$S+\mathbf{1}$ が正の整数の意味の Diophantus 集合であることは同値である（定義多項式の $x_i,y_j$ を、$S$ から $S+\mathbf{1}$ へ移る向きには $x_i-1,y_j-1$ に、逆の向きには $x_i+1,y_j+1$ に置き換える）。帰納的可算性も $S$ と $S+\mathbf{1}$ で同時に成り立つ（Dav73 p. 234 の定義と p. 267 の注 3）。

Diophantus 集合の例

次の集合は Diophantus 集合である。右側が定義である（未知数は $\mathbb{N}$ を動く）。

大小 $\{(x,y)\mid x\le y\}$：$\exists z\ (y=x+z)$。狭義の大小 $x< y$：$\exists z\ (y=x+z+1)$。
割り切る関係 $\{(x,y)\mid x\text{ は }y\text{ を割り切る}\}$：$\exists z\ (y=xz)$。
合成数の全体：$\exists y,z\ (x=(y+2)(z+2))$。
$2$ の冪でない数の全体（$0$ を含む）：$\exists y,z\ (x=y(2z+3))$。$x\ge1$ が $2$ の冪でないことは、$3$ 以上の奇数の約数をもつことと同値である。
合同 $\{(x,y,c)\mid x\equiv y\pmod c\}$：$\exists z\ \bigl((x-y-cz)(y-x-cz)=0\bigr)$。
不等 $\{(x,y)\mid x\ne y\}$：$\exists z\ \bigl((x-y-z-1)(y-x-z-1)=0\bigr)$。
5・6 では 2 つの方程式のどちらかが成り立つことを積が $0$ であることで表した。6 から、「等しくない」は Diophantus 的に表せる。一方、補集合をとる操作一般では閉じていない（cor-h10-complement）。

Diophantus 集合の閉包性

$S,T\subset\mathbb{N}^n$、$R\subset\mathbb{N}^{n+1}$ を Diophantus 集合とする。

$S\cap T$ と $S\cup T$ は Diophantus 集合である。
射影 $\{a\in\mathbb{N}^n\mid\text{ある }c\in\mathbb{N}\text{ で }(a,c)\in R\}$ は Diophantus 集合である。
$U\subset\mathbb{N}^k$ を Diophantus 集合、$f_1,\dots,f_k\colon\mathbb{N}^n\to\mathbb{N}$ を Diophantus 関数とすると、$\{a\in\mathbb{N}^n\mid(f_1(a),\dots,f_k(a))\in U\}$ は Diophantus 集合である。

方程式の和・積と未知数の追加

1：$S,T$ の定義多項式を、未知数が重ならないように $P(x,y)$、$Q(x,z)$ とする。$P,Q$ の値は整数なので、$P^2+Q^2=0$ は $P=0$ かつ $Q=0$ と同値であり、$PQ=0$ は $P=0$ または $Q=0$ と同値である。よって $P(x,y)^2+Q(x,z)^2$ は $S\cap T$ を、$P(x,y)Q(x,z)$ は $S\cup T$ を定義する。後者で $a\in S$ のときは、$y$ を $P(a,y)=0$ となるようにとり、$z$ は任意にとればよい。

詳しい証明を開く

2：$R$ の定義多項式を $P(x,x_{n+1},y)$ とすると、パラメータ $x_{n+1}$ を未知数に読み替えた $P$ が射影を定義する。

3：$a$ が集合に属することは、ある $c\in\mathbb{N}^k$ で $(a,c_i)$ が $f_i$ のグラフに属し（$i=1,\dots,k$）かつ $c\in U$ となることと同値である。$\mathbb{N}^{n+k}$ の部分集合として、$f_i$ のグラフの条件と $U$ の条件はどれも Diophantus 集合を定める（定義多項式の変数を付け替えるだけである）。1 でその共通部分をとり、2 で $c_1,\dots,c_k$ を 1 つずつ射影すればよい。$\square$

Diophantus 集合は計算で確かめられる側の性質をもつ。

Diophantus 集合は帰納的可算

Diophantus 集合 $S\subset\mathbb{N}^n$ は帰納的可算である。

未知数を順に試す

定義多項式を $P(x,y)$（$y=(y_1,\dots,y_m)$）とし、$P=P^{+}-P^{-}$ と係数が自然数の多項式 $P^{\pm}$ の差に書く。有限列の符号 $\langle\cdots\rangle$ と $i$ 番目の項 $(w)_i$ を帰納的可算集合の「記法と前提」のものとすると、$R(a,w):\Leftrightarrow P^{+}(a,(w)_0,\dots,(w)_{m-1})=P^{-}(a,(w)_0,\dots,(w)_{m-1})$ は、加法・乗法・$(w)_i$ が原始再帰関数であることから原始再帰的な関係である。$f(a):\simeq\mu w\,R(a,w)$ は部分計算可能関数で、$f(a)$ が定義されるのは $P(a,b)=0$ となる $b$ があるとき、すなわち $a\in S$ のときちょうどである。よって $S=\operatorname{dom}f$ は帰納的可算である。$\square$

MRDP の定理

prop-h10-re の逆が成り立つ。これが第 10 問題の否定的な解決の核心である。

MRDP の定理

$S\subset\mathbb{N}^n$ について、$S$ が Diophantus 集合であることと、$S$ が帰納的可算であることは同値である（Dav73 Theorem 8.1、p. 264。正の整数の版で、def-h10-diophantine の後の注意で自然数の版に移る。この記事では証明しない）。

Diophantus 集合なら帰納的可算であることは prop-h10-re である。逆向きの証明は、Dav73 では次の段階を踏む。

指数関数．$(n,k)\mapsto n^k$ が Diophantus 関数である（同 Theorem 3.3、p. 246）。これが Matiyasevich の寄与の中心である。証明には Pell方程式 $x^2-(a^2-1)y^2=1$ の解の列 $x_k(a),y_k(a)$ の整除と合同の性質を使い、$x=x_k(a)$ となる $(a,x,k)$ の集合を 8 個の方程式の連立で定める（同 Theorem 3.1、p. 245）。
有界な全称量化．定義の中に $\forall z\le y$ の形の量化を許しても、定義される集合は Diophantus 集合である（同 Theorem 5.1、p. 253）。$\exists$ の側（prop-h10-closure の 2）と違い、こちらは中国剰余定理で有限個の未知数の組を 1 つの数にまとめる議論を要する。
帰納的な関数．原始再帰と μ 作用素で作られる関数（μ再帰関数）のうち全域的なものはすべて Diophantus 関数である（同 Theorem 6.1、p. 258）。帰納的可算集合は、全域的な μ再帰関数 $f,g$ について $\exists x\,(f(x,a)=g(x,a))$ の形に書けるので、prop-h10-closure から Diophantus 集合になる。
指数関数を含む方程式で帰納的可算集合を定義できることは Davis・Putnam・J. Robinson が先に示しており、1 の段階が最後に残っていた（同 §9、pp. 265–266）。

第 10 問題の否定的な解決

第 10 問題の決定不能性

$D_{\mathbb{N}}$ と $D_{\mathbb{Z}}$ はどちらも決定可能でない。すなわち、整数係数の多項式方程式が整数解（自然数解）をもつかどうかを判定する Turing 機械は存在しない。さらに、多項式 $P(x,y_1,\dots,y_m)$ で、パラメータ $e\in\mathbb{N}$ ごとの方程式 $P(e,y)=0$ が $\mathbb{N}^m$ に解をもつかどうかが $e$ について決定可能でないものが存在する。

自己停止集合を方程式で表す

自己停止集合 $K$ は帰納的可算である（停止問題の定理「停止集合は半決定可能」）。thm-h10-mrdp により、多項式 $P(x,y_1,\dots,y_m)$ があって
$$ e\in K\iff\text{ある }b\in\mathbb{N}^m\text{ で }P(e,b)=0 $$
となる。$P_e(y):=P(e,y)$ は $x$ に数 $e$ を代入した $m$ 変数の多項式で、$g(e):=\ulcorner P_e\urcorner$ は計算可能な全域関数である。$e\in K\iff g(e)\in D_{\mathbb{N}}$ なので、$D_{\mathbb{N}}$ が決定可能なら $\chi_K=\chi_{D_{\mathbb{N}}}\circ g$ が計算可能になり、$K$ が決定可能でないこと（停止問題の定理「停止問題の決定不能性」）に反する。同じ議論で、$\{e\mid P(e,y)=0\text{ が解をもつ}\}=K$ も決定可能でない。$D_{\mathbb{Z}}$ については prop-h10-z-n の 3 による。$\square$

最後の主張は、決定不能性が「多項式の形を自由に選べる」ことからだけ来るのではなく、1 つの多項式のパラメータ $x$ に数 $e$ を代入するだけですでに現れることを述べている。どの方程式についても解があるかどうかは個別には決まっているが、すべての $e$ に一様に答える手順はない。

補集合が Diophantus 集合でない例

$K$ の補集合 $\mathbb{N}\setminus K$ は Diophantus 集合でない。とくに、Diophantus 集合の全体は補集合をとる操作で閉じていない。

$\mathbb{N}\setminus K$ は帰納的可算でない（停止問題の系「停止しない側は半決定可能でない」）ので、prop-h10-re により Diophantus 集合でない。$K$ は thm-h10-unsolvable の証明のとおり Diophantus 集合である。$\square$

解をもたないことの証明

解をもつ方程式は、解を探せばいつか見つかる。解をもたない方程式の側は、どんな機械的な方法でも取りこぼしが出る。

解をもたない方程式の枚挙

多項式の番号の集合 $A$ が帰納的可算で、$A$ のどの番号の方程式も $\mathbb{N}$ に解をもたないとする。このとき、$\mathbb{N}$ に解をもたない多項式で、番号が $A$ に属さないものが存在する。

多項式の番号の全体を $\mathrm{Pol}$ とし、$N^{c}:=\mathrm{Pol}\setminus D_{\mathbb{N}}$ とおく。$\mathrm{Pol}$ は決定可能で、$D_{\mathbb{N}}$ は解を順に試すことで半決定可能である（prf-h10-re と同じ議論）。$N^{c}$ が帰納的可算なら、$\mathbb{N}\setminus D_{\mathbb{N}}=(\mathbb{N}\setminus\mathrm{Pol})\cup N^{c}$ も帰納的可算になり（帰納的可算集合の命題「帰納的可算集合の閉包性」）、停止問題の定理「決定可能性と半決定可能性」により $D_{\mathbb{N}}$ が決定可能になって thm-h10-unsolvable に反する。よって $N^{c}$ は帰納的可算でない。仮定から $A\subset N^{c}$ で $A$ は帰納的可算なので、$A\ne N^{c}$ である。$\square$

公理が機械的に列挙でき、「方程式 $P=0$ は自然数解をもたない」という主張を表すことができて、正しいことしか証明しない数学の体系では、「方程式 $P=0$ は自然数解をもたない」と証明できる $P$ の番号の全体は帰納的可算で、解をもたない方程式だけからなる。cor-h10-incompleteness により、解をもたないのにそのことが体系の中で証明できない方程式がある（Dav73 Theorem 7.7、p. 263）。これは Gödelの不完全性定理を、方程式の言葉で述べ直したものになっている。

帰結

素数を値にもつ多項式

正の値の集合による特徴づけ

$S\subset\{1,2,3,\dots\}$ について、次は同値である（Dav73 Theorem 1.4、p. 238 は変数を正の整数とした版。もとは Putnam による）。

$S$ は Diophantus 集合である。
ある多項式 $Q(z_1,\dots,z_k)$ があって、$S=\{Q(c)\mid c\in\mathbb{N}^k,\ Q(c)>0\}$ である。

定義多項式を値に埋め込む

2 ⇒ 1：$x\in S\iff\exists c\,\exists w\ \bigl(x=Q(c)\land x=w+1\bigr)$ であり、prop-h10-closure の 1・2 により Diophantus 集合である。

詳しい証明を開く

1 ⇒ 2：$S$ の定義多項式を $P(x,y)$ とし、$Q(x,y):=x\bigl(1-P(x,y)^2\bigr)$ とおく。$x\in S$ なら $P(x,b)=0$ となる $b$ をとって $Q(x,b)=x>0$ である。逆に $Q(a,b)>0$ とする。$P(a,b)^2$ は $0$ 以上の整数なので $1-P(a,b)^2\le1$ であり、$a\ge0$ と $Q(a,b)>0$ から $a>0$ かつ $1-P(a,b)^2>0$、すなわち $P(a,b)=0$ である。よって $a\in S$ で $Q(a,b)=a$ となる。$\square$

素数を表す多項式

多項式 $Q(z_1,\dots,z_k)$ で、$\{Q(c)\mid c\in\mathbb{N}^k,\ Q(c)>0\}$ が素数の全体と一致するものが存在する。

$x$ が素数かどうかは $2\le d< x$ の $d$ で割ってみれば判定できるので、素数の全体は決定可能であり、とくに帰納的可算である（帰納的可算集合の例「帰納的可算集合の例」の 1）。thm-h10-mrdp により Diophantus 集合であり、thm-h10-putnam の 1 ⇒ 2 を当てればよい。$\square$

この多項式は 0 以下の値もとる（定数でないので ex-h10-counterexamples の 1 行目により素数でない値をとり、正の値はすべて素数だからである）。負の値を許さず「すべての値が素数」とすることはできない（ex-h10-counterexamples の 1 行目）。

未知数の個数と次数

未知数の個数の一様な上界

自然数 $m$ で、$\mathbb{N}$ のすべての Diophantus 集合が $m$ 個以下の未知数の定義多項式をもつものが存在する（Dav73 Theorem 7.6、p. 263）。

1 つの方程式にすべてを読み込む

$U:=\{(e,x)\in\mathbb{N}^2\mid x\in W_e\}$ は帰納的可算である（$x\in W_e$ は帰納的可算集合の「記法と前提」により $\exists s\,T(e,x,s)$ と同値で、$T$ は原始再帰的）。thm-h10-mrdp により、$m$ 個の未知数の多項式 $P(e,x,y_1,\dots,y_m)$ で $U$ を定義するものがある。$S\subset\mathbb{N}$ が Diophantus 集合なら、prop-h10-re により帰納的可算で、ある $e$ で $S=W_e$ である。すると $x\in S\iff\exists y\ P(e,x,y)=0$ なので、$e$ を数として代入した $P(e,x,y)$ が $m$ 個の未知数の定義多項式である。$\square$

Dav73 p. 263 は、当時 Matiyasevich と J. Robinson によって $m=14$ で足りることが示されたと述べている。次数についても、未知数を増やせば一様に押さえられる。

次数 4 への帰着

すべての Diophantus 集合 $S\subset\mathbb{N}^n$ は、全次数 $4$ 以下の定義多項式をもつ（Dav73 Theorem 7.5、pp. 262–263）。

単項式を新しい未知数で置き換える

$S$ の定義多項式を $P(x,y)$ とし、変数をまとめて $v_1,\dots,v_r$（$x$ と $y$）と書く。次数 $2$ 以上の単項式 $v_{i_1}v_{i_2}\cdots v_{i_s}$（$s\ge2$、重複を許す）ごとに新しい未知数 $u_1,\dots,u_{s-1}$ を用意し、
$$ u_1=v_{i_1}v_{i_2},\qquad u_{j}=u_{j-1}v_{i_{j+1}}\quad(2\le j\le s-1) $$
という次数 $2$ の方程式を立てる。$P$ の各単項式を対応する $u_{s-1}$ で置き換えた多項式を $\tilde P$ とすると、$\tilde P$ は全次数 $1$ 以下である。$a\in\mathbb{N}^n$ を固定する。$P(a,b)=0$ なら、$u$ を上の方程式で順に定めると $u$ は自然数の積なので $\mathbb{N}$ に入り、$u_{s-1}$ はもとの単項式の値に等しいので $\tilde P=0$ と方程式の連立が満たされる。逆に連立が自然数で解ければ、方程式から $u_{s-1}$ は単項式の値に等しく、$P(a,b)=\tilde P=0$ である。よって、連立の各式（左辺 $-$ 右辺）の平方と $\tilde P^2$ の和は、全次数 $4$ 以下で $S$ を定義する。$\square$

例：判定できる場合

第 10 問題が否定的に解決されたことは、個々の方程式や、制限された形の方程式の判定ができないことを意味しない。

判定の手順がある方程式の類

1 変数の方程式．$P(t)=c_dt^d+\cdots+c_1t+c_0$（$c_d\ne0$）の整数解 $t$ は、$c_0=0$ なら $t=0$ が解であり、$c_0\ne0$ なら $t\ne0$ で $c_0=-t(c_1+c_2t+\cdots+c_dt^{d-1})$ から $t$ は $c_0$ を割り切る。$c_0$ の約数は有限個なので、すべて代入して調べれば判定できる。
1 次方程式．$c_1x_1+\cdots+c_nx_n=c_0$（$c_i$ のどれかは $0$ でない）が整数解をもつことは、$c_1,\dots,c_n$ の最大公約数が $c_0$ を割り切ることと同値である。解があれば左辺は最大公約数の倍数であり、逆は Bézoutの等式による。最大公約数は Euclidの互除法で計算できる。
実数解．$P(x)=0$ が $\mathbb{R}^n$ に解をもつかどうかは、文 $\exists x_1\cdots\exists x_n\,(P(x)=0)$ が順序体 $\mathbb{R}$ で真かどうかであり、実閉体の理論は決定可能なので判定できる（決定可能な理論の例の表、Tarski–Seidenbergの定理）。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
正の値だけを集める（cor-h10-primes）	値の全体（負の値も含む）が素数だけからなる、定数でない多項式	素数を表す多項式の存在
未知数の個数を制限しない（thm-h10-unsolvable）	未知数が 1 個以下の方程式 $P(e,y)=0$	決定不能性
解を整数で探す（thm-h10-unsolvable）	同じ方程式の実数解	決定不能性
存在量化だけで定義する（def-h10-diophantine）	補集合 $\mathbb{N}\setminus K$	Diophantus 集合であること

反例の確かめ

1 行目：そのような多項式は存在しない。多項式 $Q(z_1,\dots,z_k)$ が定数でなく、すべての $c\in\mathbb{N}^k$ で $Q(c)$ が素数であったとして矛盾を導く。

詳しい確かめを開く

$Q$ が定数でないので、ある変数、たとえば $z_1$ について $Q=\sum_{j=0}^{r}Q_j(z_2,\dots,z_k)z_1^j$、$r\ge1$、$Q_r\ne0$ と書ける。$0$ でない多項式は $\mathbb{N}^{k-1}$ の上で恒等的に $0$ にはならないので、$Q_r(c_2,\dots,c_k)\ne0$ となる $c_2,\dots,c_k\in\mathbb{N}$ がある。$f(t):=Q(t,c_2,\dots,c_k)$ は次数 $r\ge1$ の 1 変数多項式で、すべての $t\in\mathbb{N}$ で $f(t)$ は素数である。$p:=f(0)$ とおく。$j\in\mathbb{N}$ について $f(jp)\equiv f(0)=p\equiv0\pmod p$ であり、$f(jp)$ は素数なので $f(jp)=p$ である。すると $f(t)-p$ は無限個の根 $t=0,p,2p,\dots$ をもち、$0$ でない多項式の根は次数以下の個数しかないので $f(t)-p=0$ となり、$r\ge1$ に反する。

2 行目：未知数が $0$ 個なら $P(e)$ を計算すればよい。未知数が 1 個なら、$P(e,y)$ は $y$ の 1 変数多項式である。零多項式なら解をもち、そうでなければ、ex-h10-decidable-classes の 1 の手順を $\mathbb{N}$ の解に制限して（負の約数を除いて）当てはめれば判定できる。$e$ から $P(e,y)$ の係数は計算できるので、$\{e\mid P(e,y)=0\text{ が解をもつ}\}$ は決定可能である。

3 行目：ex-h10-decidable-classes の 3 により、実数解をもつかどうかは判定できる。

4 行目：cor-h10-complement である。$K$ は Diophantus 集合なので、定義に否定（補集合）を許すと Diophantus 集合から外れる。

1 行目と cor-h10-primes を比べると、「正の値だけを集める」という操作が本質的であることが分かる。thm-h10-putnam の証明で、$x(1-P^2)$ は $P\ne0$ のとき $0$ 以下の値になり、素数でない値はすべてここから出る。

補足

有理数解． 多項式が有理数解をもつかどうかを判定する方法があるかは知られていない。代数体（有理数体の有限次拡大）の上の方程式でも同じで、一方、有限体上の 1 変数有理関数体のような大域関数体の上ではそのような方法は存在しない（Poo17 §2.6.4、Question 2.6.6 の後、p. 50）。有理数解の問題は、整数解の問題とは別の深さをもつ Diophantus幾何学の問題である。
解の個数． 解の個数が $0$ かどうかに限らず、解の個数が与えられた集合（空でも全体でもない）に入るかどうかも一般に判定できない（Dav73 §9、p. 267）。この記事では証明しない。
個別の方程式． 決定不能性は、特別な形の方程式に対する方法を否定しない。3 次以上の既約な 2 元形式 $F$ による $F(x,y)=m$ の形の方程式や、右辺の 3 次式が重根をもたない $y^2=ax^3+bx^2+cx+d$ の形の方程式のような 2 変数の方程式の類については、Baker らが解を求める有限の手順を与えた（Dav73 p. 267 とその文献 [1]・[2]）。Thue の方程式の解が有限個であることは Thueの定理(ディオファントス方程式)、個々の方程式を解く技法は不定方程式の解法にある。

参考文献

[1]

Martin Davis, Hilbert's Tenth Problem is Unsolvable, The American Mathematical Monthly 80 (1973), no. 3, 233–269, 1973, 冒頭（Hilbert の講演と問題の述べ方）p. 233、§1 の定義 p. 234、Theorem 1.4（正の値による特徴づけ）p. 238、Theorem 3.1 p. 245、Theorem 3.3（指数関数は Diophantus 関数）p. 246、Theorem 5.1（有界な全称量化）p. 253、Theorem 6.1（帰納的な関数は Diophantus 関数）p. 258、Theorem 7.5（次数 4）pp. 262–263、Theorem 7.6（未知数の個数の上界）・Theorem 7.7（証明できない方程式）p. 263、Theorem 8.1（MRDP の定理）p. 264、§9（歴史）pp. 264–267、注 3 p. 267

[2]

Bjorn Poonen, Rational Points on Varieties, Graduate Studies in Mathematics 186, American Mathematical Society, 2017, §2.6.4、Question 2.6.6 とその後の段落（体の上の Hilbert の第 10 問題）p. 50

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。支援について／寄付する