整数関係アルゴリズム

実数の集合x ₁、x ₂、 ...、x _n間の整数関係は、すべて0ではない整数の集合a ₁、a ₂、 ...、a _nであり、

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=0.\,}$

整数関係アルゴリズムは、整数関係を見つけるためのアルゴリズムです。具体的には、与えられた精度で知られている実数の集合が与えられた場合、整数関係アルゴリズムはそれらの間の整数関係を見つけるか、または大きさが特定の上限より小さい係数を持つ整数関係が存在しないと判断するかのいずれかを行います。 [ ^1]

n = 2の場合、ユークリッドの互除法の拡張により、任意の2 つの実数x ₁とx _{2間に存在する整数関係を見つけることができます。このアルゴリズムは、} x ₁ / x ₂の連分数展開の連続項を生成します。数値間に整数関係がある場合、それらの比は有理数となり、アルゴリズムは最終的に終了します。

• ファーガソン・フォーカードアルゴリズムは、1979年にヘラマン・ファーガソンとRWフォーカードによって発表されました。^[2]この論文では一般的なnを扱っていますが、信頼性の高い実装に不可欠な詳細な手順、証明、精度の上限が欠けているため、問題が完全に解決されているかどうかは明らかではありません。
• 完全な証明を備えた最初のアルゴリズムは、1982 年にArjen Lenstra、Hendrik Lenstra、László Lovászによって開発されたLLL アルゴリズム^{でした。 [3]}
• HJLSアルゴリズム、 1986 年にJohan Håstad、Bettina Just、Jeffrey Lagarias、Claus-Peter Schnorrによって開発されました。 ^{[4] [5]}
• PSOSアルゴリズムは、1988年にファーガソンによって開発された。^[6]
• PSLQアルゴリズムは、1992年にファーガソンとベイリーによって開発され、1999年にファーガソン、ベイリー、アルノによって大幅に簡略化されました。 ^{[7] [8]} 2000年にPSLQアルゴリズムは、本質的にHJLSと同等であると考えられているにもかかわらず、ジャック・ドンガラとフランシス・サリバンによって「世紀のトップ10アルゴリズム」の1つに選ばれました。[ ^{9 ] [10] [11]}
• LLL アルゴリズムは多くの著者によって改良されてきました。最新の LLL 実装では、nが500 を超える整数関係の問題を解決できます。

整数関係アルゴリズムには、数多くの用途があります。最初の用途は、与えられた実数x が代数的であるかどうかを判断することです。これは、 xの累乗の集合{1, x , x ² , ..., x ⁿ } 間の整数関係を検索することによって行われます。2 番目の用途は、実数xとe 、 π 、 ln(2)などの数学定数の集合との間の整数関係を検索することです。これにより、xの式がこれらの定数の線形結合として得られます。

実験数学における典型的なアプローチは、数値法と任意精度の演算を使用して、無限級数、無限積、または積分の近似値を高精度（通常は少なくとも 100 桁の有効数字）で求め、次に整数関係アルゴリズムを使用して、この値と一連の数学定数との間の整数関係を検索することです。整数関係が見つかった場合、元の級数、積、または積分の閉じた形式の表現が可能であることが示唆されます。この推測は、正式な代数的手法によって検証できます。アルゴリズムへの入力が知られている精度が高いほど、見つかった整数関係が単なる数値アーティファクトではないという信頼度が高くなります。

このアプローチの注目すべき成功は、PSLQアルゴリズムを使用して、πの値に対するベイリー・ボーウェイン・プルーフの公式につながる整数関係を見つけたことです。PSLQは、多重ゼータ関数を含む新しい恒等式の発見と量子場の理論でのそれらの出現、およびロジスティック写像の分岐点の特定にも役立ちました。たとえば、B _{4 が}ロジスティック写像の4番目の分岐点である場合、定数α = − B ₄ ( B _{4 − 2) は、最大係数が257} ³⁰ である120次多項式の根です。^{[12] [13]整数関係アルゴリズムは、}逆シンボリック計算機やプルーフのインバータなどのアプリケーションで、高精度の数学定数の表やヒューリスティックな検索方法と組み合わされています。

整数関係の発見は高次多項式の因数分解に使用できる。 ^[14]

• 数値定数の認識 ( David H. BaileyおよびSimon Plouffe著)
• 実験数学における 10 の問題 2011-06-10 にWayback Machineでアーカイブされました著者: David H. Bailey、Jonathan M. Borwein、Vishaal Kapoor、Eric W. Weisstein