Wikipedia

数論の有効な結果

数論において、有効な結果(英: Effective results)であるとは、主張の内容が具体的に計算可能であることを表す。 数論における結果は、歴史的理由やディオファントス方程式の解法への応用を理由に、主張の内容が計算可能か否かを判断することを数学の他の分野よりも精査されてきた。例えばある整数のリストが有限であると主張されているならば、原理的に計算機で計算してそのリストを出力できるかどうかが問題となる。

リトルウッドの結果

編集

初期の有効でない(ineffective)結果の例は、1914年のリトルウッドの定理[1]であり、素数定理における　ψ(x) と π(x) の差の漸近的な見積もりとして、符号を無限回変えるという定理である[2]。1933年、スタンレー・スキューズ(Stanley Skewes)は、現在スキューズ数として知られている、最初に符号が変わる有効な上限を発見した[3] 。

詳しくいえば、数列 f(n) を考えたとき、無限回の符号変化に関する有効な結果とは、「すべての N に対して、f(N) と f(M) が異なる符号となる値 M ( > N) が特定の計算資源下で計算できる」ということを含む定理となる。実際には M は N 以降の値 n によって計算されるが、問題はどのくらい大きな n まで見なければいけないかということである。最初に符号を変える n を探すのはその特別な場合である。この問題の要点は、既知の数値的な証拠によって符号が変わらないことが示されたということである。リトルウッドの結果から、この数値的証拠が小さな数では有効であると保証されたが、ここでの「小さい」とは n が 1,000,000 までの場合を含んでいた。

計算可能性の要求は、数論の結果を証明するための解析的整数論で使われる方法に反映されると同時に対比もされる。例えば、ランダウの記号の使用やそれが存在を暗示する定数に関して疑問が生ずる。「ランダウの記号はそのような定数が単に存在することを示すのか？もしくは、暗黙の定数の代わりに（例えば）1000 が使われるバージョンを再現できるか？」というものである。言い換えると、符号が変わる M > N が存在し、ある陽関数 G （例えばべき乗、対数、指数）に対して

 

であることが既知とすると、これはある絶対定数 A に対して、単に

 

であるだろうか、ということである。

A は、いわゆる暗黙の定数であるが、計算を目的とすれば定数として明示する必要が生じうる。ランダウの記号がよくこの話題の導入に使われる理由の一つは、 A が正確には何であるか、という問題が背後にあるからである。間接的な形の証明では、暗黙の定数を明示できるかが全くわからないものもある。

ジーゲルの時期

編集

1900年から1950年までの間に証明された解析的整数論の主要な結果の多くは、実際には有効でなかった。下に主要な例を列挙する。

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

その後の成果

編集

その後の結果、特にアラン・ベイカーの成果によって上記の状況から変化した。定性的に言うとベイカーの定理の主張は弱く見えるが、式に陽的な定数を含んでいるため、（完全だろうと推測される）解のリストが実際に全ての解の集合であることを計算機を使って証明することができる。

理論的な問題

編集

有効な結果を導出することは困難であるが、背理法の使用に注意し、背理法とは根本的に異なる証明方法で解決されてきた。この考え方は、計算可能性理論や計算可能函数よりも証明論に近い。難しさはむしろ計算複雑性理論の領域にあるのではないかと大まかに予想されている。有効でない結果は、今もなお「A または B である」という形で証明されているが、そのどちらが真であるかを知る方法はない。

脚注

編集
  1. ^ Littlewood, J. E. (1914). “Sur la distribution des nombres premiers”. Comptes Rendus 158: 1869–1872. JFM 45.0305.01. 
  2. ^ Feferman, Solomon (1996). “Kreisel's "unwinding" program”. Kreiseliana. Wellesley, MA: A K Peters. pp. 247–273. MR1435765. http://math.stanford.edu/~feferman/papers/unwind.pdf  プレプリント版の p. 9 を参照。
  3. ^ Skewes, S. (1933). “On the difference π(x) − Li(x)”. Journal of the London Mathematical Society 8: 277–283. doi:10.1112/jlms/s1-8.4.277. JFM 59.0370.02. Zbl 0007.34003. 
  4. ^ Heilbronn, H.; Linfoot, E. H. (1934). “On the imaginary quadratic corpora of class-number one”. Quarterly Journal of Mathematics. Oxford Series 5 (1): 293–301. doi:10.1093/qmath/os-5.1.293. .
  5. ^ Sprindzhuk (2001) "Diophantine approximations" [1], in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 – 範囲の非有効性についてのコメント

外部リンク

編集
  • Sprindzhuk (2001) "Diophantine approximations" [2], in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
「https://ja.wiki.x.io/w/index.php?title=数論の有効な結果&oldid=94470924」から取得