数論の有効な結果

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

数論の結果をディオファントス方程式の解法へ応用するためには、論理が計算可能か否かを、数学の他の分野より精密に精査する。これには歴史的理由がある。整数の一覧が有限であると主張されているとき、問題はその一覧を原理的に計算機で計算した後にプリントアウトできるかどうかでということある。

リトルウッドの結果[編集]

初期の非有効な(計算可能でない)結果の例は、1914年のジョン・エデンサー・リトルウッド(J. E. Littlewood)の定理[1]である。この定理は、素数定理で漸近見積もりを持つ ψ(x) と π(x) との差は、符号を無限回変えるという定理である。[2] 現在はスキューズ数として知られているが、1993年、スタンレー・スキューズ英語版(Stanley Skewes)は、符号が変わる計算可能な値をはじめて発見した。

(この定理を)さらに詳しくいうと、数値の列を f(n) を書き、この数列が符号を無限回頻繁に変更するということが有効な(計算可能な)結果ということは、全ての N のに対し、f(N) と f(M) の値が異なる符号を持ち、M > N となるような M を有限の資源で計算することが可能であるということを意味する定理であるはずである。実践的には、M は N よりも大きな n をとることにより計算できるはずで、ここで問題は「どこまで行かねばならないのか?」と言う問題である。特別な場合としては、最初に符号を変える n を見つけることである。問題の面白いところは、符号が変わらないことを示す数値的な証拠があるということであったのであり、リトルウッドの結果は「この数値的証拠は小さな数で有効なだけである」という結果であり、ここでの「小さい」とは n は 1,000,000 ほどを意味していた。

計算可能であれとの要求は、数論の結果を証明するための解析的整数論で使われる方法に反映されると同時に対比もされる。例えば、ランダウの記号の使い方やランダウの記号の定数の意味は何かとの疑問が湧く。論理的に純粋にそのような定数の存在定理が肯定されるか、それとも、言わば 1000 がその定数の中に含まれるということを再現可能なのかという疑問である。言い換えると、M > N が存在し符号を変えて、

であることが知れられているとすると、べきや、対数や指数というような明らかな函数 G が存在し、全体にかかる定数 A が存在して、

となるだろうかという疑問である。A の値は、いわゆる暗黙の定数であるが、ある計算を目的として明白な(定数)とする必要があるということかもしれない。「ランダウの記号が有名なこの問題への入口であった」という理由は、正確に A が何であるかを背後に持っていることにある。形が間接的な証明では、暗黙の定数の明白性は全て明らかであるとは言えない。

ジーゲルの時期[編集]

1900年から1950年までの間に証明された解析的整数論の原理的結果の多くは、実際は、非有効である(計算可能ではない)。主要な例を挙げると、

類数の下限問題(イデアル類群が大きくなるにつれて、ある数体の族が存在する数について)のような理論的に不完全なまま残っている具体的情報や、分母で表されている代数的数の最良な有理数での近似の境界の問題は、アクセル・トゥエ英語版(Axel Thue)の仕事以後、ディオファントス方程式の結果として直接的に理解されるようになった。証明にリウヴィル数を使った結果は、平均値の定理へ応用された方法は有効であるが、(現在は、トゥエ・ジーゲル・ロスの定理として知られているものへの)改造がなされていなかった。

その後の結果[編集]

その後の結果、特に、アラン・ベイカー(Alan Baker)の結果は、(計算可能、有効な結果という観点からは、)位置が異なる。ベイカーの定理は、量的に言うと、一見、弱く見えるが、しかし、明白な定数を持ち、実際に計算機での計算へ応用することができ、(完全であろうと推測されている)解の一覧が、真に解全部の集合であることを証明することができる。

理論的な結果[編集]

有効な結果の(計算可能である)ための困難さを克服するには、背理法による証明を使うときに非常な注意を払うが、根底的に異なる証明テクニックが必要になる。そこでの論理は、計算可能理論計算可能函数の論理よりも証明論の論理により近くなる。むしろ緩やかではあるが、困難さは計算複雑さにあるのではないかと予想されている。非有効な結果(計算可能でない結果)は、形 A 「ないしは」 B の中で証明する中に既に存在していて、このことを言う方法があるわけではない。

脚注[編集]

  1. ^ Littlewood, J. E. (1914). “Sur la distribution des nombres premiers”. Comptes Rendus 158: 1869–1872. JFM 45.0305.01. 
  2. ^ Solomon Feferman, Kreisel's "unwinding" program [1], p.9.
  3. ^ H. Heilbronn, E. Linfoot, On the imaginary quadratic corpora of class-number one. Quart. J. Math. Oxford Ser. 5 (1934), pp. 293–301.
  4. ^ Sprindzhuk (2001) "Diophantine approximations" [2], in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 – 限界値の非有効性についてのコメント

外部リンク[編集]

  • Sprindzhuk (2001) "Diophantine approximations" [3], in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4