Integer relation algorithm - Revision history

Altenmann: Reverted 1 edit by Harajaru345tyu (talk): Rv stupid ai spellchecker

2025-04-14T06:13:47Z

Reverted 1 edit by Harajaru345tyu (talk): Rv stupid ai spellchecker

Harajaru345tyu at 06:04, 14 April 2025

2025-04-14T06:04:02Z

2601:447:CD80:E200:D12E:8E36:D8F3:D30F at 04:10, 24 March 2025

2025-03-24T04:10:36Z

← Previous revision		Revision as of 04:10, 24 March 2025
Line 17:		Line 17:

	==Applications==		==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''<sup>2</sup>, ..., ''x''<sup>''n''</sup>}. The second application is to search for an integer relation between a real number ''x'' and a set of mathematical constants such as ''e'', π and ln(2), which will lead to an expression for ''x'' as a linear combination of these constants.		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''<sup>2</sup>, ..., ''x''<sup>''n''</sup>}. 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]].		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]].

133.86.227.82: /* History */

2025-01-25T09:00:48Z

History

← Previous revision		Revision as of 09:00, 25 January 2025
Line 13:		Line 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 '''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 '''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>{{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 '''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.		*The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with ''n'' above 500.

133.86.227.82: /* History */

2025-01-25T08:49:29Z

History

← Previous revision		Revision as of 08:49, 25 January 2025
Line 13:		Line 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 '''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 '''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>{{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 '''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>{{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.		*The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with ''n'' above 500.

Karldray: correct grammar & meaning of first sentence. an integer relation is ...

2024-10-24T05:33:54Z

correct grammar & meaning of first sentence. an integer relation *is* ...

← Previous revision		Revision as of 05:33, 24 October 2024
Line 1:		Line 1:
	{{Short description\|Mathematical procedure}}		{{Short description\|Mathematical procedure}}
	An '''integer relation''' between a set of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> ~~and~~ a set of integers ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>, not all 0, such that		An '''integer relation''' between a set of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> is a set of integers ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>, not all 0, such that

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

LucasBrown at 18:54, 7 June 2024

2024-06-07T18:54:27Z

← Previous revision		Revision as of 18:54, 7 June 2024
Line 1:		Line 1:
			{{Short description\|Mathematical procedure}}
	An '''integer relation''' between a set of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> and a set of integers ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>, not all 0, such that		An '''integer relation''' between a set of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> and a set of integers ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>, not all 0, such that

Tamfang: /* top */

2023-11-26T02:32:00Z

top

← Previous revision		Revision as of 02:32, 26 November 2023
Line 1:		Line 1:
	An '''integer relation''' between a set of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> is a set of integers ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>, not all 0, such that		An '''integer relation''' between a set of real numbers ''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub> and a set of integers ''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>, not all 0, such that

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

Tamfang: Reverted edit by 175.110.56.44 (talk) to last version by Bruce1ee

2023-10-19T05:28:52Z

Reverted edit by 175.110.56.44 (talk) to last version by Bruce1ee

← Previous revision		Revision as of 05:28, 19 October 2023
Line 28:		Line 28:

	== External links ==		== External links ==
	* §[https://web.archive.org/web/20080422084455/http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html ''Recognizing Numerical Constants''] by [[David H. Bailey (mathematician)\|David H. Bailey]] and [[Simon Plouffe]]		* [https://web.archive.org/web/20080422084455/http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html ''Recognizing Numerical Constants''] by [[David H. Bailey (mathematician)\|David H. Bailey]] and [[Simon Plouffe]]
	* [http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf ''Ten Problems in Experimental Mathematics''] {{Webarchive\|url=https://web.archive.org/web/20110610051846/http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf \|date=2011-06-10 }} by David H. Bailey, [[Jonathan Borwein\|Jonathan M. Borwein]], Vishaal Kapoor, and [[Eric W. Weisstein]]		* [http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf ''Ten Problems in Experimental Mathematics''] {{Webarchive\|url=https://web.archive.org/web/20110610051846/http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf \|date=2011-06-10 }} by David H. Bailey, [[Jonathan Borwein\|Jonathan M. Borwein]], Vishaal Kapoor, and [[Eric W. Weisstein]]

175.110.56.44: /* External links */ 213

2023-10-06T16:25:28Z

External links: 213

← Previous revision		Revision as of 16:25, 6 October 2023
Line 28:		Line 28:

	== External links ==		== External links ==
	* [https://web.archive.org/web/20080422084455/http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html ''Recognizing Numerical Constants''] by [[David H. Bailey (mathematician)\|David H. Bailey]] and [[Simon Plouffe]]		* §[https://web.archive.org/web/20080422084455/http://oldweb.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html ''Recognizing Numerical Constants''] by [[David H. Bailey (mathematician)\|David H. Bailey]] and [[Simon Plouffe]]
	* [http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf ''Ten Problems in Experimental Mathematics''] {{Webarchive\|url=https://web.archive.org/web/20110610051846/http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf \|date=2011-06-10 }} by David H. Bailey, [[Jonathan Borwein\|Jonathan M. Borwein]], Vishaal Kapoor, and [[Eric W. Weisstein]]		* [http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf ''Ten Problems in Experimental Mathematics''] {{Webarchive\|url=https://web.archive.org/web/20110610051846/http://crd.lbl.gov/~dhbailey/dhbpapers/tenproblems.pdf \|date=2011-06-10 }} by David H. Bailey, [[Jonathan Borwein\|Jonathan M. Borwein]], Vishaal Kapoor, and [[Eric W. Weisstein]]

← Previous revision		Revision as of 06:13, 14 April 2025
Line 4:		Line 4:
	:<math>a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,</math>		:<math>a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,</math>

	An '''integer relation algorithm''' is an [[algorithm]] for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain [[upper bound]].<ref>Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.</ref>		An '''integer relation algorithm''' is an [[algorithm]] for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain [[upper bound]].<ref>Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.</ref>

	== History ==		== History ==
Line 10:		Line 10:

	*The Ferguson–Forcade algorithm was published in 1979 by [[Helaman Ferguson]] and [[R.W. Forcade]].<ref>{{MathWorld\|urlname=IntegerRelation\|title=Integer Relation}}</ref> Although the paper treats general ''n'', it is not clear if the paper fully solves the problem because it lacks the detailed steps, proofs, and a precision bound that are crucial for a reliable implementation.		*The Ferguson–Forcade algorithm was published in 1979 by [[Helaman Ferguson]] and [[R.W. Forcade]].<ref>{{MathWorld\|urlname=IntegerRelation\|title=Integer Relation}}</ref> Although the paper treats general ''n'', it is not clear if the paper fully solves the problem because it lacks the detailed steps, proofs, and a precision bound that are crucial for a reliable implementation.
	*The first algorithm with complete proofs was the '''[[Lenstra–Lenstra–Lovász lattice basis reduction algorithm\|LLL algorithm]]''', developed by [[Arjen Lenstra]], [[Hendrik Lenstra]], and [[László Lovász]] in 1982.<ref>{{MathWorld\|urlname=LLLAlgorithm\|title=LLL Algorithm}}</ref>		*The first algorithm with complete proofs was the '''[[Lenstra–Lenstra–Lovász lattice basis reduction algorithm\|LLL algorithm]]''', developed by [[Arjen Lenstra]], [[Hendrik Lenstra]] and [[László Lovász]] in 1982.<ref>{{MathWorld\|urlname=LLLAlgorithm\|title=LLL Algorithm}}</ref>
	*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 '''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 '''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 '''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.		*The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with ''n'' above 500.

	== Applications ==		==Applications==
	Integer relation algorithms have numerous applications. The first application is to determine whether a given real number ''x'' is likely to be an [[algebraic number\|algebraic]], by searching for an integer relation between a set of powers of ''x'' {1, ''x'', ''x''<sup>2</sup>, ..., ''x''<sup>''n''</sup>}. 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.		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''<sup>2</sup>, ..., ''x''<sup>''n''</sup>}. 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 ~~methods~~]] 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]].		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]].

	A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the [[Bailey–Borwein–Plouffe formula]] for the value of [[pi\|{{pi}}]]. PSLQ has also helped find new identities involving [[multiple zeta ~~functions~~]] and their appearance in [[quantum field theory]]; and in identifying bifurcation points of the [[logistic map]]. For example, where B<sub>4</sub> is the logistic map's fourth bifurcation point, the constant α = −''B''<sub>4</sub>(''B''<sub>4</sub> − 2) is a root of a 120th-degree polynomial whose largest coefficient is 257<sup>30</sup>.<ref>David H. Bailey and David J. Broadhurst, [http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf "Parallel Integer Relation Detection: Techniques and Applications,"] {{Webarchive\|url=https://web.archive.org/web/20110720013234/http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf \|date=2011-07-20 }} Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719–1736; LBNL-44481.</ref><ref>I. S. Kotsireas, and K. Karamanos, "Exact Computation of the bifurcation Point B4 of the logistic Map and the Bailey–Broadhurst Conjectures", I. J. Bifurcation and Chaos 14(7):2417–2423 (2004)</ref> Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the [[Inverse Symbolic Calculator]] or [[Plouffe's Inverter]].		A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the [[Bailey–Borwein–Plouffe formula]] for the value of [[pi\|{{pi}}]]. PSLQ has also helped find new identities involving [[multiple zeta function]]s and their appearance in [[quantum field theory]]; and in identifying bifurcation points of the [[logistic map]]. For example, where B<sub>4</sub> is the logistic map's fourth bifurcation point, the constant α = −''B''<sub>4</sub>(''B''<sub>4</sub> − 2) is a root of a 120th-degree polynomial whose largest coefficient is 257<sup>30</sup>.<ref>David H. Bailey and David J. Broadhurst, [http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf "Parallel Integer Relation Detection: Techniques and Applications,"] {{Webarchive\|url=https://web.archive.org/web/20110720013234/http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf \|date=2011-07-20 }} Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719–1736; LBNL-44481.</ref><ref>I. S. Kotsireas, and K. Karamanos, "Exact Computation of the bifurcation Point B4 of the logistic Map and the Bailey–Broadhurst Conjectures", I. J. Bifurcation and Chaos 14(7):2417–2423 (2004)</ref> Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the [[Inverse Symbolic Calculator]] or [[Plouffe's Inverter]].

	Integer relation finding can be used to [[Factorization of polynomials\|factor polynomials]] of high degree.<ref>M. van Hoeij: ''Factoring polynomials and the knapsack problem.'' J. of Number Theory, 95, 167–189, (2002).</ref>		Integer relation finding can be used to [[Factorization of polynomials\|factor polynomials]] of high degree.<ref>M. van Hoeij: ''Factoring polynomials and the knapsack problem.'' J. of Number Theory, 95, 167–189, (2002).</ref>

← Previous revision		Revision as of 06:04, 14 April 2025
Line 4:		Line 4:
	:<math>a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,</math>		:<math>a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0.\,</math>

	An '''integer relation algorithm''' is an [[algorithm]] for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them, or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain [[upper bound]].<ref>Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.</ref>		An '''integer relation algorithm''' is an [[algorithm]] for finding integer relations. Specifically, given a set of real numbers known to a given precision, an integer relation algorithm will either find an integer relation between them or will determine that no integer relation exists with coefficients whose magnitudes are less than a certain [[upper bound]].<ref>Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.</ref>

	== History ==		== History ==
Line 10:		Line 10:

	*The Ferguson–Forcade algorithm was published in 1979 by [[Helaman Ferguson]] and [[R.W. Forcade]].<ref>{{MathWorld\|urlname=IntegerRelation\|title=Integer Relation}}</ref> Although the paper treats general ''n'', it is not clear if the paper fully solves the problem because it lacks the detailed steps, proofs, and a precision bound that are crucial for a reliable implementation.		*The Ferguson–Forcade algorithm was published in 1979 by [[Helaman Ferguson]] and [[R.W. Forcade]].<ref>{{MathWorld\|urlname=IntegerRelation\|title=Integer Relation}}</ref> Although the paper treats general ''n'', it is not clear if the paper fully solves the problem because it lacks the detailed steps, proofs, and a precision bound that are crucial for a reliable implementation.
	*The first algorithm with complete proofs was the '''[[Lenstra–Lenstra–Lovász lattice basis reduction algorithm\|LLL algorithm]]''', developed by [[Arjen Lenstra]], [[Hendrik Lenstra]] and [[László Lovász]] in 1982.<ref>{{MathWorld\|urlname=LLLAlgorithm\|title=LLL Algorithm}}</ref>		*The first algorithm with complete proofs was the '''[[Lenstra–Lenstra–Lovász lattice basis reduction algorithm\|LLL algorithm]]''', developed by [[Arjen Lenstra]], [[Hendrik Lenstra]], and [[László Lovász]] in 1982.<ref>{{MathWorld\|urlname=LLLAlgorithm\|title=LLL Algorithm}}</ref>
	*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 '''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 '''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 '''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.		*The LLL algorithm has been improved by numerous authors. Modern LLL implementations can solve integer relation problems with ''n'' above 500.

	==Applications==		== 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''<sup>2</sup>, ..., ''x''<sup>''n''</sup>}. 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.		Integer relation algorithms have numerous applications. The first application is to determine whether a given real number ''x'' is likely to be an [[algebraic number\|algebraic]], by searching for an integer relation between a set of powers of ''x'' {1, ''x'', ''x''<sup>2</sup>, ..., ''x''<sup>''n''</sup>}. 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]].		A typical approach in [[experimental mathematics]] is to use [[numerical methods]] 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]].

	A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the [[Bailey–Borwein–Plouffe formula]] for the value of [[pi\|{{pi}}]]. PSLQ has also helped find new identities involving [[multiple zeta ~~function~~]]s and their appearance in [[quantum field theory]]; and in identifying bifurcation points of the [[logistic map]]. For example, where B<sub>4</sub> is the logistic map's fourth bifurcation point, the constant α = −''B''<sub>4</sub>(''B''<sub>4</sub> − 2) is a root of a 120th-degree polynomial whose largest coefficient is 257<sup>30</sup>.<ref>David H. Bailey and David J. Broadhurst, [http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf "Parallel Integer Relation Detection: Techniques and Applications,"] {{Webarchive\|url=https://web.archive.org/web/20110720013234/http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf \|date=2011-07-20 }} Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719–1736; LBNL-44481.</ref><ref>I. S. Kotsireas, and K. Karamanos, "Exact Computation of the bifurcation Point B4 of the logistic Map and the Bailey–Broadhurst Conjectures", I. J. Bifurcation and Chaos 14(7):2417–2423 (2004)</ref> Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the [[Inverse Symbolic Calculator]] or [[Plouffe's Inverter]].		A notable success of this approach was the use of the PSLQ algorithm to find the integer relation that led to the [[Bailey–Borwein–Plouffe formula]] for the value of [[pi\|{{pi}}]]. PSLQ has also helped find new identities involving [[multiple zeta functions]] and their appearance in [[quantum field theory]]; and in identifying bifurcation points of the [[logistic map]]. For example, where B<sub>4</sub> is the logistic map's fourth bifurcation point, the constant α = −''B''<sub>4</sub>(''B''<sub>4</sub> − 2) is a root of a 120th-degree polynomial whose largest coefficient is 257<sup>30</sup>.<ref>David H. Bailey and David J. Broadhurst, [http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf "Parallel Integer Relation Detection: Techniques and Applications,"] {{Webarchive\|url=https://web.archive.org/web/20110720013234/http://crd.lbl.gov/~dhbailey/dhbpapers/ppslq.pdf \|date=2011-07-20 }} Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719–1736; LBNL-44481.</ref><ref>I. S. Kotsireas, and K. Karamanos, "Exact Computation of the bifurcation Point B4 of the logistic Map and the Bailey–Broadhurst Conjectures", I. J. Bifurcation and Chaos 14(7):2417–2423 (2004)</ref> Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the [[Inverse Symbolic Calculator]] or [[Plouffe's Inverter]].

	Integer relation finding can be used to [[Factorization of polynomials\|factor polynomials]] of high degree.<ref>M. van Hoeij: ''Factoring polynomials and the knapsack problem.'' J. of Number Theory, 95, 167–189, (2002).</ref>		Integer relation finding can be used to [[Factorization of polynomials\|factor polynomials]] of high degree.<ref>M. van Hoeij: ''Factoring polynomials and the knapsack problem.'' J. of Number Theory, 95, 167–189, (2002).</ref>

Integer relation algorithm - Revision history

Altenmann: Reverted 1 edit by Harajaru345tyu (talk): Rv stupid ai spellchecker

Harajaru345tyu at 06:04, 14 April 2025

2601:447:CD80:E200:D12E:8E36:D8F3:D30F at 04:10, 24 March 2025

133.86.227.82: /* History */

133.86.227.82: /* History */

Karldray: correct grammar & meaning of first sentence. an integer relation *is* ...

LucasBrown at 18:54, 7 June 2024

Tamfang: /* top */

Tamfang: Reverted edit by 175.110.56.44 (talk) to last version by Bruce1ee

175.110.56.44: /* External links */ 213

Karldray: correct grammar & meaning of first sentence. an integer relation is ...