Integer relation algorithm
Encyclopedia
An integer relation between a set of real numbers x1, x2, ..., xn is a set of integers a1, a2, ..., an, not all 0, such that
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
.
can determine whether there is an integer relation between any two real numbers x1 and x2. The algorithm generates successive terms of the continued fraction
expansion of x1/x2; if there is an integer relation between the numbers then their ratio is rational and the algorithm eventually terminates.
The first general algorithm that was proved to work for all values of n was the Ferguson–Forcade algorithm, published in 1979 by Helaman Ferguson
and R.W. Forcade. Subsequent developments, focussing on improving both efficiency and numerical stability, produced the following algorithms:
In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by Jack Dongarra
and Francis Sullivan.
, by searching for an integer relation between a set of powers of x {1, x, x2, ..., xn}. 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 B4 is the logistic map's fourth bifurcation point, the constant α=-B4(B4-2) appears to be a root of a 120th-degree polynomial whose largest coefficient is 25730 or about 2·1072.
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.
The same applications can also be done with the LLL algorithm. Recent versions of LLL can handle problems with n above 500.
An integer relation algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
Upper bound
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
.
History
For the case n = 2, an extension of the Euclidean algorithmEuclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
can determine whether there is an integer relation between any two real numbers x1 and x2. The algorithm generates successive terms of the continued fraction
Continued fraction
In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on...
expansion of x1/x2; if there is an integer relation between the numbers then their ratio is rational and the algorithm eventually terminates.
The first general algorithm that was proved to work for all values of n was the Ferguson–Forcade algorithm, published in 1979 by Helaman Ferguson
Helaman Ferguson
Helaman Rolfe Pratt Ferguson is an American sculptor and a digital artist, specifically an algorist.Ferguson's mother died when he was about three and his father went off to serve in the Second World War. He was adopted and raised in New York. He was a graduate of Hamilton College and received a...
and R.W. Forcade. Subsequent developments, focussing on improving both efficiency and numerical stability, produced the following algorithms:
- The LLL algorithmLenstra–Lenstra–Lovász lattice basis reduction algorithmThe LLL-reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982, see...
, developed by Arjen LenstraArjen LenstraArjen Klaas Lenstra is a Dutch mathematician. He studied mathematics at the University of Amsterdam.He is currently a professor at the EPFL , in the Laboratory for Cryptologic Algorithms, and...
, Hendrik LenstraHendrik LenstraHendrik Willem Lenstra, Jr. is a Dutch mathematician.-Biography:Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978...
and László LovászLászló LovászLászló Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
in 1982. - The HJLS algorithm, developed by Johan Hastad, Bettina Just, Jeffrey Lagarias, and Claus-Peter Schnorr in 1986.
- The PSOS algorithm, developed by Ferguson in 1988.
- The PSLQ algorithm, developed by Ferguson and Bailey in 1992 and substantially simplified by Ferguson, Bailey, and Arno in 1999.
In 2000 the PSLQ algorithm was selected as one of the "Top Ten Algorithms of the Century" by Jack Dongarra
Jack Dongarra
Jack J. Dongarra is a University Distinguished Professor of Computer Sciencein the Electrical Engineering and Computer Science Department at the University of Tennessee...
and Francis Sullivan.
Applications
Integer relation algorithms have two main applications. The first application is to determine whether a given real number x is likely to be algebraicAlgebraic number
In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients. Numbers such as π that are not algebraic are said to be transcendental; almost all real numbers are transcendental...
, by searching for an integer relation between a set of powers of x {1, x, x2, ..., xn}. 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
Experimental mathematics
Experimental mathematics is an approach to mathematics in which numerical computation is used to investigate mathematical objects and identify properties and patterns...
is to use numerical methods and arbitrary precision arithmetic to find an approximate value for an infinite series
Series (mathematics)
A series is the sum of the terms of a sequence. Finite sequences and series have defined first and last terms, whereas infinite sequences and series continue indefinitely....
, infinite product or an integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
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
Closed-form expression
In mathematics, an expression is said to be a closed-form expression if it can be expressed analytically in terms of a bounded number of certain "well-known" functions...
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 π
Pi
' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
. PSLQ has also helped find new identities involving multiple zeta functions and their appearance in quantum field theory
Quantum field theory
Quantum field theory provides a theoretical framework for constructing quantum mechanical models of systems classically parametrized by an infinite number of dynamical degrees of freedom, that is, fields and many-body systems. It is the natural and quantitative language of particle physics and...
; and in identifying bifurcation points of the logistic map
Logistic map
The logistic map is a polynomial mapping of degree 2, often cited as an archetypal example of how complex, chaotic behaviour can arise from very simple non-linear dynamical equations...
. For example, where B4 is the logistic map's fourth bifurcation point, the constant α=-B4(B4-2) appears to be a root of a 120th-degree polynomial whose largest coefficient is 25730 or about 2·1072.
Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the Inverse Symbolic Calculator
Inverse Symbolic Calculator
The Inverse Symbolic Calculator is an online number checker established July 18, 1995 by Peter Benjamin Borwein, Jonathan Michael Borwein and Simon Plouffe of the Canadian Centre for Experimental and Constructive Mathematics...
or Plouffe's Inverter.
The same applications can also be done with the LLL algorithm. Recent versions of LLL can handle problems with n above 500.
External links
- Recognizing Numerical Constants by David H. BaileyDavid H. BaileyDavid Harold Bailey is a mathematician and computer scientist. He received his B.S. in mathematics from Brigham Young University in 1972 and his Ph.D. in mathematics from Stanford University in 1976...
and Simon PlouffeSimon PlouffeSimon Plouffe is a Quebec mathematician born on June 11, 1956 in Saint-Jovite, Quebec. He discovered the formula for the BBP algorithm which permits the computation of the nth binary digit of π, in 1995... - Ten Problems in Experimental Mathematics by David H. Bailey, Jonathan M. BorweinJonathan BorweinJonathan Michael Borwein is a Scottish mathematician who holds an appointment as Laureate Professor of mathematics at the University of Newcastle, Australia. Noted for his prolific and creative work throughout the international mathematical community, he is a close associate of David H...
, Vishaal Kapoor, and Eric W. WeissteinEric W. WeissteinEric W. Weisstein is an encyclopedist who created and maintains MathWorld and Eric Weisstein's World of Science . He currently works for Wolfram Research, Inc.-Education:...