Integer relation algorithm

An integer relation between a set of real numbers x₁, x₂, ..., x_n is a set of integers a₁, a₂, ..., a_n, not all 0, such that

a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=0.\,

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.^[1]

History

For the case n = 2, an extension of the Euclidean algorithm can find any integer relation that exists between any two real numbers x₁ and x₂. The algorithm generates successive terms of the continued fraction expansion of x₁/x₂; if there is an integer relation between the numbers, then their ratio is rational and the algorithm eventually terminates.

The Ferguson–Forcade algorithm was published in 1979 by Helaman Ferguson and R.W. Forcade.^[2] 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 LLL algorithm, developed by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982.^[3]
The HJLS algorithm, developed by Johan Håstad, Bettina Just, Jeffrey Lagarias, and Claus-Peter Schnorr in 1986.^[4]^[5]
The PSOS algorithm, developed by Ferguson in 1988.^[6]
The PSLQ algorithm, developed by Ferguson and Bailey in 1992 and substantially simplified by Ferguson, Bailey, and Arno in 1999.^[7]^[8] In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by Jack Dongarra and Francis Sullivan^[9] even though it is considered essentially equivalent to HJLS.^[10]^[11]
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, by searching for an integer relation between a set of powers of x {1, x, x², ..., xⁿ}. 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.

A typical approach in experimental mathematics is to use numerical methods and arbitrary precision arithmetic to find an approximate value for an 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 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 $π$ . 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₄ is the logistic map's fourth bifurcation point, the constant α = −B₄(B₄ − 2) is a root of a 120th-degree polynomial whose largest coefficient is 257³⁰.^[12]^[13] 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 factor polynomials of high degree.^[14]

References

^ 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.
^ Weisstein, Eric W. "Integer Relation". MathWorld.
^ Weisstein, Eric W. "LLL Algorithm". MathWorld.
^ Weisstein, Eric W. "HJLS Algorithm". MathWorld.
^ 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
^ Weisstein, Eric W. "PSOS Algorithm". MathWorld.
^ Weisstein, Eric W. "PSLQ Algorithm". MathWorld.
^ A Polynomial Time, Numerically Stable Integer Relation Algorithm Archived 2007-07-17 at the Wayback Machine by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992
^ Cipra, Barry Arthur. "The Best of the 20th Century: Editors Name Top 10 Algorithms" (PDF). SIAM News. 33 (4). Archived from the original (PDF) on 2021-04-24. Retrieved 2012-08-17.
^ Jingwei Chen, Damien Stehlé, Gilles Villard: A New View on HJLS and PSLQ: Sums and Projections of Lattices., ISSAC'13
^ Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM: [1]
^ David H. Bailey and David J. Broadhurst, "Parallel Integer Relation Detection: Techniques and Applications," Archived 2011-07-20 at the Wayback Machine Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719–1736; LBNL-44481.
^ 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)
^ M. van Hoeij: Factoring polynomials and the knapsack problem. J. of Number Theory, 95, 167–189, (2002).

External links

Recognizing Numerical Constants by David H. Bailey and Simon Plouffe
Ten Problems in Experimental Mathematics Archived 2011-06-10 at the Wayback Machine by David H. Bailey, Jonathan M. Borwein, Vishaal Kapoor, and Eric W. Weisstein

[1] 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.

[2] Weisstein, Eric W. "Integer Relation". MathWorld.

[3] Weisstein, Eric W. "LLL Algorithm". MathWorld.

[4] Weisstein, Eric W. "HJLS Algorithm". MathWorld.

[5] 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

[6] Weisstein, Eric W. "PSOS Algorithm". MathWorld.

[7] Weisstein, Eric W. "PSLQ Algorithm". MathWorld.

[8] A Polynomial Time, Numerically Stable Integer Relation Algorithm Archived 2007-07-17 at the Wayback Machine by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992

[9] Cipra, Barry Arthur. "The Best of the 20th Century: Editors Name Top 10 Algorithms" (PDF). SIAM News. 33 (4). Archived from the original (PDF) on 2021-04-24. Retrieved 2012-08-17.

[10] Jingwei Chen, Damien Stehlé, Gilles Villard: A New View on HJLS and PSLQ: Sums and Projections of Lattices., ISSAC'13

[11] Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM: [1]

[12] David H. Bailey and David J. Broadhurst, "Parallel Integer Relation Detection: Techniques and Applications," Archived 2011-07-20 at the Wayback Machine Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719–1736; LBNL-44481.

[13] 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)

[14] M. van Hoeij: Factoring polynomials and the knapsack problem. J. of Number Theory, 95, 167–189, (2002).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t e Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp Kunerth
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL; KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms