Integer relation algorithm: Difference between revisions

Revision as of 02:32, 26 November 2023

Latest revision as of 06:13, 14 April 2025

(6 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Mathematical procedure}}

An '''integer relation''' between a set of real numbers ''x''₁, ''x''₂, ..., ''x''_''n'' andis a set of integers ''a''₁, ''a''₂, ..., ''a''_''n'', not all 0, such that

:<math>a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,</math>

Line 12 ⟶ 13:

*The '''HJLS algorithm''', developed by [[Johan Håstad]], Bettina Just, [[Jeffrey Lagarias]], and [[Claus P. Schnorr|Claus-Peter Schnorr]] in 1986.<ref>{{MathWorld|urlname=HJLSAlgorithm|title=HJLS Algorithm}}</ref><ref>Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: ''Polynomial time algorithms for finding integer relations among real numbers.'' Preliminary version: 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</ref>

*The '''PSOS algorithm''', developed by Ferguson in 1988.<ref>{{MathWorld|urlname=PSOSAlgorithm|title=PSOS Algorithm}}</ref>

*The '''PSLQ algorithm''', developed by Ferguson and [[David H. Bailey (mathematician)|Bailey]] in 1992 and substantially simplified by Ferguson, Bailey, and Arno in 1999.<ref>Helaman R. P. Ferguson, David H. Bailey, and Steve Arno: "Analysis of PSLQ, an integer relation finding algorithm", Math. Comp., vol.68, no.225 (Jan. 1999), pp.351-369.</ref><ref>[https://www.davidhbailey.com/dhbpapers/pslq-comp-alg.pdf David H. Bailey and J.M. Borwein: "PSLQ: An Algorithm to Discover Integer Relations" (May 14, 2020)]</ref><ref>{{MathWorld|urlname=PSLQAlgorithm|title=PSLQ Algorithm}}</ref><ref>[http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf ''A Polynomial Time, Numerically Stable Integer Relation Algorithm''] {{Webarchive|url=https://web.archive.org/web/20070717073907/http://crd.lbl.gov/~dhbailey/dhbpapers/pslq.pdf |date=2007-07-17 }} by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992</ref> In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by [[Jack Dongarra]] and Francis Sullivan<ref>{{cite journal |author-first=Barry Arthur |author-last=Cipra |author-link=Barry Arthur Cipra |url=http://www.uta.edu/faculty/rcli/TopTen/topten.pdf |title=The Best of the 20th Century: Editors Name Top 10 Algorithms |journal=SIAM News |volume=33 |issue=4 |access-date=2012-08-17 |archive-date=2021-04-24 |archive-url=https://web.archive.org/web/20210424004030/https://www.uta.edu/faculty/rcli/TopTen/topten.pdf |url-status=dead }}</ref> even though it is considered essentially equivalent to HJLS.<ref>Jingwei Chen, Damien Stehlé, Gilles Villard: [http://perso.ens-lyon.fr/damien.stehle/downloads/PSLQHJLS.pdf ''A New View on HJLS and PSLQ: Sums and Projections of Lattices.''], [http://www.issac-conference.org/2013/ ISSAC'13]</ref><ref>Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM: [http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/cpslq.pdf]</ref>

*The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with ''n'' above 500.

==Applications==

Integer relation algorithms have numerous applications. The first application is to determine whether a given real number ''x'' is likely to be [[algebraic number|algebraic]], by searching for an integer relation between a set of powers of ''x'' {1, ''x'', ''x''², ..., ''x''^''n''}. The second application is to search for an integer relation between a real number ''x'' and a set of mathematical constants such as ''e'', π{{pi}} and ln(2), which will lead to an expression for ''x'' as a linear combination of these constants.

A typical approach in [[experimental mathematics]] is to use [[numerical method]]s and [[arbitrary precision arithmetic]] to find an approximate value for an [[series (mathematics)|infinite series]], [[infinite product]] or an [[integral]] to a high degree of precision (usually at least 100 significant figures), and then use an integer relation algorithm to search for an integer relation between this value and a set of mathematical constants. If an integer relation is found, this suggests a possible [[closed-form expression]] for the original series, product or integral. This conjecture can then be validated by formal algebraic methods. The higher the precision to which the inputs to the algorithm are known, the greater the level of confidence that any integer relation that is found is not just a [[Almost integer|numerical artifact]].