整数関係アルゴリズム
数学的手順

実数の集合x 1 , x 2 , ..., x n間の整数関係は、すべて0ではない 整数の集合a 1 , a 2 , ..., a n であり、

1つの 1 × 1 + 1つの 2 × 2 + ⋯ + 1つの n × n ＝ 0。 {\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=0.\,}

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

歴史

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

  • Ferguson–Forcadeアルゴリズムは、1979年にHelaman FergusonとRW Forcadeによって発表されました。[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] [9] [10] 2000年にPSLQアルゴリズムは、本質的にHJLSと同等であると考えられているにもかかわらず、ジャック・ドンガラとフランシス・サリバンによって「世紀のトップ10アルゴリズム」の1つに選ばれました。[11] [12 ] [13]
  • LLLアルゴリズムは多くの著者によって改良されてきました。現代のLLL実装では、nが500を超える整数関係問題を解くことができます。

アプリケーション

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

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

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

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

参考文献

  1. ^ 実数の集合は有限の精度までしか指定できないため、係数の大きさに制限を設けないアルゴリズムは、十分に大きな係数に対しては常に整数関係を見つけることができる。整数関係における係数の大きさが、実数を指定する精度に比べて小さい場合、興味深い結果が得られる。
  2. ^ ワイスタイン、エリック W.「整数関係」。マスワールド。
  3. ^ Weisstein, Eric W.「LLLアルゴリズム」。MathWorld。
  4. ^ ワイスタイン、エリック W.「HJLS アルゴリズム」。マスワールド。
  5. ^ Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr:実数間の整数関係を見つけるための多項式時間アルゴリズム。暫定版: STACS 1986 ( Symposium Theoret. Aspects Computer Science ) Lecture Notes Computer Science 210 (1986), p. 105–118. SIAM J. Comput. , Vol. 18 (1989), pp. 859–881
  6. ^ ワイスタイン、エリック W.「PSOS アルゴリズム」。マスワールド。
  7. ^ Helaman RP Ferguson、David H. Bailey、Steve Arno：「整数関係発見アルゴリズムPSLQの分析」、Math. Comp.、vol.68、no.225（1999年1月）、pp.351-369。
  8. ^ David H. BaileyとJM Borwein：「PSLQ：整数関係を発見するアルゴリズム」（2020年5月14日）
  9. ^ ワイスタイン、エリック W.「PSLQ アルゴリズム」。マスワールド。
  10. ^ 多項式時間で数値的に安定な整数関係アルゴリズム（ Helaman RP FergusonとDavid H. Bailey著、 Wayback Machineに2007年7月17日アーカイブ）; RNR技術報告書RNR-91-032; 1992年7月14日
  11. ^ Cipra, Barry Arthur . 「20世紀のベスト：編集者が選ぶトップ10アルゴリズム」（PDF） . SIAM News . 33 (4). 2021年4月24日時点のオリジナル（PDF）からアーカイブ。 2012年8月17日閲覧。
  12. ^ Jingwei Chen、Damien Stehlé、Gilles Villard：「HJLS と PSLQ に関する新たな視点：格子の和と射影」、ISSAC'13
  13. ^ Helaman RP Ferguson、David H. Bailey、Steve Arno、PSLQ の分析、整数関係検出アルゴリズム: [1]
  14. ^ David H. Bailey および David J. Broadhurst、「Parallel Integer Relation Detection: Techniques and Applications」、Wayback Machineに 2011 年 7 月 20 日にアーカイブ、Mathematics of Computation、vol. 70、no. 236 (2000 年 10 月)、pp. 1719–1736、LBNL-44481。
  15. ^ IS Kotsireas、K. Karamanos、「ロジスティック写像の分岐点B4の正確な計算とベイリー・ブロードハースト予想」、IJ Bifurcation and Chaos 14(7):2417–2423 (2004)
  16. ^ M. van Hoeij:因数分解多項式とナップサック問題.整数論誌, 95, 167–189, (2002).
「https://en.wikipedia.org/w/index.php?title=Integer_relation_algorithm&oldid=1285523551」より取得