主题
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 定理, 实数, 子集和问题

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 中引用

整数关系

引用为

Weisstein, Eric W. “整数关系。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/IntegerRelation.html

主题分类