第 181 回 PTT のお知らせ

          葉書の残りは      枚です

差出人(幹事):
113  文京区本郷 7-3-1
     東京大学工学部計数工学科  岩崎英哉
     03-3812-2111  ext. 7411

第 181 回 PTTメモ

不定方程式y^2+k=x^3 (kは0でない有理整数)の全ての有理整数解を求めるアル
ゴリズムについて, 具体的に例を示しながら説明しました. この問題は,
Hilbertの第10問題「任意個数の未知数を含む整数係数不定方程式が, 整数解
を持つか否かを有限の演算で判定する一般的方法を見つけること」に関連する
話題です. 

Hilbertの第10問題は, Matijasevi\check{c}によって否定的に解決したわけで
すが, 不定方程式の形にある制限をつけると, 全ての整数解を見つけられるこ
とが知られています. その中で特に顕著な結果としては, Bakerの一連の仕事
が知られています. 今回, 題材とした不定方程式に対するBakerの結果は, 以
下のとおりです.

定理[Baker68]  k \neg 0 なる任意の整数に対して
	y^2+k=x^3
の全ての整数解(x,y)は,
	max { |x|, |y| } < exp{(10^10 |k|)^{10^4}}
を満たす. 

しかし, 上記の領域をしらみつぶしに調べて解を探すことは, 実際には不可能
でしょう.  そこでBakerの証明をベースに工夫します.

	y^2+63=x^3  	(1)
について考えてみると次のようになります. ２次体Q(\sqrt{-7})で
y^2+63を分解し, y^2+63が平方数であることより,
	y+3\sqrt{-7}=aX^3	y+3\sqrt{-7}=bY^3
ここでa, bはQ(\sqrt{-7})での立方数を含まず, abはQ(\sqrt{-7})で立方数で
す. aとbについてこの２次体上で素因子分解をして若干の式変形を行なうと,
(1)を解くことは
	X^3-12XY^2-2Y^3=\pm 1	(2)
を解くことと同値になります. この式変形では、数式処理システムを使うと便
利です.

(2)を解くために
	f(X,Y)=X^3-12XY^2-2Y^3
とし、f(X,1)=0の一つの解θを考え, 実3次体Q(θ)上で(2)の方程式の考察を
行なうと, 対数の線形形式の線型形式を得ることができます. 細かい話をする
と非常に長くなるので, 詳細は省略します. 式変形と数値計算の結果, (2)を
解くことは, H =< 3のとき
	|\pm α^{b_1}_1 α^{b_2}_2 + α_3 | =< exp(α-δH/4),
4 =< H =< 77のとき
	|b_1 log|α_1| + b_2 log|α_2| - log|α_3|| < 4 exp(-δH/4)
のb_1, b_2を求めることに帰着できます. これを解いて今まで来た道筋をたど
ると, (1)の整数解が(x,y) = (4,1), (4,-1), (563, 13537), (563, -13537)
のみであることが求まります.

ここで省略した部分が実は本質的部分なのですが, PTTで話したときもここだ
けで1時間くらいかかったので割愛させていただきます. この部分でも不等式
の評価のために数値計算をかなり行ないます. いくつかの計算では, 小数点以
下1100桁程度の精度が必要になります. 不等式の評価をいかにうまくやるかが,
計算量を落すための鍵になります.

この証明は構成的になっていますので, 形式的に証明を記述して不定方程式を
解くプログラムを実際に抽出できないかと最近考えています.

当日, 長々とした証明にお付き合いいただいた皆様, ありがとうございました.

参考文献
[Baker68] A. Baker, Contributions to the thory of Diophantine
equations: II. The Diophantine equation y^2=x^3+k, Phil. Trans. Roy.
Soc. London, A263 (1968), 193-208.



		伊知地 宏 	hiro@ksp.fujixerox.co.jp
		Systems & Communications Lab., Fuji Xerox Co., Ltd.