数論における効果的な結果

歴史的な理由とディオファントス方程式の解法への応用のため、数論の結果は他の数学の分野よりも綿密に調べられ、その内容が効果的に計算可能かどうかが調べられてきた^{[要出典] 。}整数のリストが有限であると主張される場合、そのリストを原理的に機械計算後に印刷できるかどうかが問題となる。

有効でない結果の初期の例としては、1914年のJEリトルウッドの定理^{[1]があり、}素数定理では、 ψ( x )とπ( x )の差とその漸近推定値は、符号が無限に頻繁に変化するというものでした。^[2] 1933年にスタンレー・スキューズは、最初の符号変化の有効な上限を得ました。^{[3]これは現在}スキューズ数として知られています。

もっと詳しく言うと、数列f  ( n ) について、その符号が無限に変化することに関する有効な結果は、 Nのすべての値に対して、 f  ( N ) とf  ( M ) が異なった符号を持ち、指定されたリソースでM を計算できるような値M > Nを含む定理となるでしょう。実際的には、M はN以降のnの値を取ることによって計算され、問題は「どこまで行かなければならないか」です。特別な場合は、最初の符号の変化を見つけることです。この問題の興味深い点は、既知の数値的証拠が符号の変化を示さなかったことです。リトルウッドの結果は、この証拠が単なる少数の効果であることを保証しましたが、ここでの「小さい」にはnが10 億までの値が含まれていました。

計算可能性の要件は、解析的整数論で結果を証明するために使用されるアプローチに反映され、対照的である。例えば、ランダウ記法とその暗黙の定数の使用に疑問が生じる。主張はそのような定数の純粋存在定理なのか、それとも（例えば）1000が暗黙の定数の代わりとなるバージョンを復元できるのか？言い換えれば、符号が変わる M > Nがあり、

M = O( G ( N )) です。

べき乗、対数、指数関数から構成される明示的な関数 Gの場合、それは

M < A . G ( N )

絶対定数Aについてです。 Aの値、いわゆる暗黙の定数も、計算上の目的で明示的にする必要があるかもしれません。ランダウ記法が人気の導入となった理由の 1 つは、Aが正確に何であるかを隠すことができるからです。間接的な証明形式によっては、暗黙の定数を明示的にできることがまったく明らかでない場合があります。

1900年から1950年にかけて証明された解析的数論の主要な結果の多くは、実際には役に立たなかった。主な例は以下のとおりである。

• トゥー・ジーゲル・ロス定理
• シーゲルの積分点に関する定理、1929年
• 1934年のハンス・ハイルブロンとエドワード・リンフットによるクラス数1問題に関する定理^[4]
• 1935年のジーゲルゼロの結果^[5]
• ジーゲル零点に基づくジーゲル・ワルフィスの定理。

理論的に不完全のまま残された具体的な情報には、類数の下限値（数体の族によっては理想的な類群が大きくなる）や、分母の観点から見た代数的数の最良有理近似値の境界値などがある。後者は、アクセル・トゥーの研究に倣って、ディオファントス方程式の結果として直接的に読み取ることができる。証明でリウヴィル数に使用された結果は、平均値定理を適用するという点では効果的であるが、（現在のトゥー・ジーゲル・ロスの定理への）改良は効果的ではなかった。

その後、特にアラン・ベイカーによる結果によって、この立場は変わりました。定性的に言えば、ベイカーの定理は弱いように見えますが、明示的な定数があり、機械計算と組​​み合わせて実際に適用して、解のリスト（完全であると疑われる）が実際には解の集合全体であることを証明することができます。

ここでの困難は、根本的に異なる証明技法によって対処され、背理法による証明により多くの注意が払われました。関連する論理は、計算可能性理論や計算可能関数の論理よりも、証明理論に近いものです。困難は計算複雑性理論の領域にあるのではないかと、かなり漠然と推測されています。効果のない結果は、形状AまたはBでまだ証明されていますが、どちらであるかを判断する方法はありません。

• Sprindzhuk, VG (2001) [1994]、「ディオファントス近似」、数学百科事典、EMS Press