20050518　ヒルベルト第十問題

　「ヒルベルト第十問題」というのがある。ヒルベルトという数学者が提起した二十三題の数学の問題$${^{*1}}$$中の十番目の問題$${^{*2}}$$だ。どういう問題かというと「任意個数の未知量に関する、整数を係数とするような一つのディオファンタス方程式に整数解があるかどうかを有限回の手順で判定する方法を示せ」というものである。ディオファンタス方程式$${^{*3}}$$というのは、例えば$${x^2+y^2-3=0}$$といった方程式を考えた時、XとYとを整数に限定して解を求める。例の場合、これをディオファンタス方程式と考えた時、解は存在しない。$${x^2+y^2-1=0}$$ならば$${(x,y)=(1,0)}$$、$${(x,y)=(0,1)}$$、$${(x,y)=(-1,0)}$$、$${(x,y)=(0,-1)}$$と四つの解がある。

　「任意個数の未知量」なので未知数は$${x}$$、$${y}$$だけではなく、いくつでも設定される。更に次数も任意である。上手い手順$${^{*4}}$$がなければ、手当たり次第数値を当てはめていくことになる。解が見つかればそこで止めることができるが、もともと解がない場合は当てはめる作業は永遠に終わらないことになる。$${x^2+y^2-3=0}$$には解がないので上記のような手当たり次第の機械的な方法では永遠に動作は止まらない。

　ヒルベルトは与えられた方程式に解があるかないかだけを判定する方法を求めている。問題の内容自体は簡単に理解できるが、こうやって考えると途方もない問題であることが判る。

　1970年にこの問題が解かれた$${^{*5}}$$。問題がヒルベルトによって提示されたのは1900年だから解くのに70年かかった。問題は解けたのだが、実は「有限回の手順で判定する方法は存在しない」ということが判ったのであった。それを示したのはソ連のマチャセヴィッチ$${^{*6}}$$という二十二歳の青年だった。

　ディオファンタス方程式に整数解があるかどうかを有限回の手順で判定する方法は「存在しない」という事を証明するには、ある特徴を持ったディオファンタス方程式$${^{*7}}$$の実例を示せばよいということがアメリカの数学者ロビンソン$${^{*8}}$$などによって1960年に証明された$${^{*9}}$$。

　マチャセヴィッチはその実例を見出した。それは次のようなものだった。

$${u+w-v-2=0}$$
$${l-2v-2a-1=0}$$
$${l^2-lz-z^2-1=0}$$
$${g-bl^2=0}$$
$${g^2-gh-h^2-1=0}$$
$${m-c(2h+g)-3=0}$$
$${m-fl-2=0}$$
$${x^2-mxy+y^2-1=0}$$
$${(d-1)l+u-x-1=0}$$
$${x-v-(2h+g)(9e-1)=0}$$

これら十個の方程式をそれぞれ自乗して全て加え合わせて得られる方程式がその実例らしい。こんな複雑な式をどうやって思い付いたのだろう。

*1　ダフィット・ヒルベルト - Wikipedia
*2　Hilbert's Problems -- from MathWorld
*3　『ディオファントスの方程式』
*4　５－２－２　拡張ユークリッドの互除法
*5　Hilbert's tenth problem
*6　Yuri Matiyasevich's home page (original in Russia)
*7　Matiyasevich theorem - Scholarpedia
*8　Robinson_Julia
*9　Hilbert's Tenth Problem. Diophantine Equations. By K.Podnieks