主題
Search

整數關係

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

一組 實數 x_1, ..., x_n 被稱為具有整數關係，如果存在整數 a_i 使得

a_1x_1+a_2x_2+...+a_nx_n=0,

並非所有 a_i=0。 由於歷史原因，整數關係演算法有時被稱為廣義歐幾里得演算法或多維連分數演算法。

一個有趣的此類關係的例子是 17-向量 (1, x, x^2, ..., x^(16)) 其中 x=3^(1/4)-2^(1/4)，它具有整數關係 (1, 0, 0, 0, -3860, 0, 0, 0, -666, 0, 0, 0, -20, 0, 0, 0, 1)，即，

1-3860x^4-666x^8-20x^(12)+x^(16)=0.

這是尋找由 x=3^(1/r)-2^(1/s) 滿足的 n=rs 次多項式的特例。

可以在 Wolfram 語言中使用以下方法找到整數關係FindIntegerNullVector[{x1, x2, ...}]。

整數關係演算法可用於解決子集和問題，以及確定給定的數值常數是否等於次數為 n 或更小的單變數多項式的根 (Bailey and Ferguson 1989, Ferguson and Bailey 1992)。

兩個數之間整數關係的最簡單情況之一是最大公約數的定義中固有的關係。 著名的歐幾里得演算法解決了這個問題，以及兩個實數之間更一般的整數關係問題，產生精確的關係或無限近似關係序列 (Ferguson et al. 1999)。 儘管 Hermite (1850)、Jacobi (1868)、Poincaré (1884)、Perron (1907)、Brun (1919, 1920, 1957) 和 Szekeres (1970) 嘗試將該演算法推廣到 n>=3，但已知所有這些程式在某些情況下都會失敗 (Ferguson and Forcade 1979, Forcade 1981, Hastad et al. 1989)。 第一個成功的整數關係演算法由 Ferguson 和 Forcade (1979) 開發 (Ferguson and Bailey 1992, Ferguson et al. 1999)。

用於查詢整數關係的演算法包括 Ferguson-Forcade 演算法、HJLS 演算法、LLL 演算法、PSLQ 演算法、PSOS 演算法以及 Lagarias 和 Odlyzko (1985) 的演算法。 也許最簡單（但不幸的是效率最低）的此類演算法是貪婪演算法。

Plouffe 的“逆符號計算器”網站包含一個龐大的資料庫，其中包含 5400 萬個與基本數學常數代數相關的實數。 Ferguson-Forcade 演算法表明，對於 e/pi、e+pi、lnpi、gamma、e^gamma、gamma/e、gamma/pi 和 lngamma，不存在次數 <=8 的代數方程，其整數係數的歐幾里得範數低於某些界限，其中 e 是自然對數的底數，pi 是 pi，gamma 是 尤拉-馬歇羅尼常數 (Bailey 1988)。

常數界限
e/pi6.1030×10^(14)
e+pi2.2753×10^(18)
lnpi8.7697×10^9
gamma3.5739×10^9
e^gamma1.6176×10^(17)
gamma/e1.8440×10^(11)
gamma/pi6.5403×10^9
lngamma2.6881×10^(10)

另請參閱

常數問題, Ferguson-Forcade 演算法, 貪婪演算法, Hermite-Lindemann 定理, HJLS 演算法, 揹包問題, 格約化, Lindemann-Weierstrass 定理, LLL 演算法, PSLQ 演算法, PSOS 演算法, Richardson 定理, 實數, 子集和問題

使用 探索

參考文獻

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. "Integer Relation Detection." §2.2 in 實驗數學實踐。 Wellesley, MA: A K Peters, pp. 29-31, 2006.Bailey, D. H. and Broadhurst, D. J. "Parallel Integer Relation Detection: Techniques and Applications." Math. Comput. 70, 1719-1736, 2001.Bailey, D. H. and Ferguson, H. R. P. "Numerical Results on Relations Between Numerical Constants Using a New Algorithm." Math. Comput. 53, 649-656, 1989.Bailey, D. and Plouffe, S. "Recognizing Numerical Constants." 有機數學。1995 年 12 月 12 日至 14 日在不列顛哥倫比亞省伯納比舉行的研討會論文集 (Ed. J. Borwein, P. Borwein, L. Jörgenson, and R. Corless). Providence, RI: Amer. Math. Soc., pp. 73-88, 1997. http://www.cecm.sfu.ca/organics/papers/bailey/.Bernstein, L. Jacobi-Perron 演算法：理論與應用。 Berlin: Springer-Verlag, 1971.Borwein, J. and Bailey, D. 實驗數學：21 世紀的合理推理。 Wellesley, MA: A K Peters, pp. 51-52, 2003.Borwein, J. M. and Corless, R. M. "Emerging Tools for Experimental Mathematics." Amer. Math. Monthly 106, 899-909, 1999.Borwein, J. M. and Lisonek, P. "Applications of Integer Relation Algorithms." Disc. Math. 217, 65-82, 2000.Brentjes, A. J. "Multi-Dimensional Continued Fraction Algorithms." Mathemat. Centre Tracts, No. 145. Amsterdam, Netherlands: Mathemat. Centrum, 1981.Brun, V. "En generalisatiken av kjedeboøken, I." Norske Vidensk. Skrifter I. Matemat. Naturvid. Klasse 6, 1-29, 1919.Brun, V. "En generalisatiken av kjedeboøken, II." Norske Vidensk. Skrifter I. Matemat. Naturvid. Klasse 7, 1-24, 1920.Brun, V. "Algorithmes euclidiens pour trois et quatre nombres." In Treizième Congrès des mathématiciens Scandinaves, tenu a Helsinki 18-23 août 1957. Helsinki: Mercators Trycheri, pp. 46-64, 1958.Centre for Experimental & Constructive Mathematics. "Integer Relations." http://www.cecm.sfu.ca/projects/IntegerRelations/.Ferguson, H. R. P. and Bailey, D. H. "A Polynomial Time, Numerically Stable Integer Relation Algorithm." RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.Ferguson, H. R. P.; Bailey, D. H.; and Arno, S. "Analysis of PSLQ, An Integer Relation Finding Algorithm." Math. Comput. 68, 351-369, 1999.Ferguson, H. R. P. and Forcade, R. W. "Generalization of the Euclidean Algorithm for Real Numbers to All Dimensions Higher than Two." Bull. Amer. Math. Soc. 1, 912-914, 1979.Forcade, R. W. "Brun's Algorithm." Unpublished manuscript, 1-27, Nov. 1981.Hastad, J.; Just, B.; Lagarias, J. C.; and Schnorr, C. P. "Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers." SIAM J. Comput. 18, 859-881, 1988.Hermite, C. "Extraits de lettres de M. Ch. Hermite à M. Jacobi sur differénts objets de la théorie de nombres." J. reine angew. Math. 3/4, 261-315, 1850.Jacobi, C. G. "Allgemeine Theorie der Kettenbruchahnlichen Algorithmen, in welche jede Zahl aus Drei vorhergehenden gebildet wird (Aus den hinterlassenen Papieren von C. G. Jacobi mitgetheilt durch Herrn E. Heine." J. reine angew. Math. 69, 29-64, 1868.Lagarias, J. C. and Odlyzko, A. M. "Solving Low-Density Subset Sum Problems." J. ACM 32, 229-246, 1985.Lenstra A. K.; Lenstra, H. W. Jr.; and Lovász, L. "Factoring Polynomials with Rational Coefficients." Math. Ann. 261, 515-534, 1982.Perron, O. "Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus." Math. Ann. 64, 1-76, 1907.Plouffe, S. "Plouffe's Inverter." http://pi.lacim.uqam.ca/eng/.Poincaré, H. "Sur une généralisation des fractions continues." Comptes Rendus Acad. Sci. Paris 99, 1014-1016, 1884.Szekeres, G. "Multidimensional Continued Fractions." Ann. Univ. Sci. Budapest Eőtvős Sect. Math. 13, 113-140, 1970.

在 中引用

整數關係

引用為

Weisstein, Eric W. “整數關係。” 來自 Web 資源。 https://mathworld.tw/IntegerRelation.html

主題分類