An integer relation between a set of real numbers ''x''
1, ''x''
2, ..., ''x''
''n'' is a set of integers ''a''
1, ''a''
2, ..., ''a''
''n'', not all 0, such that
:
An integer relation algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
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
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an eleme ...
.
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''
1 and ''x''
2. The algorithm generates successive terms of the
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 ...
expansion of ''x''
1/''x''
2; 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
Helaman Rolfe Pratt Ferguson (born 1940 in Salt Lake City, Utah) is an American sculptor and a digital artist, specifically an algorist. He is also well known for his development of the PSLQ algorithm, an integer relation detection algorithm.
E ...
and
R.W. Forcade. 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
Arjen Klaas Lenstra (born 2 March 1956, in Groningen) is a Dutch mathematician, cryptographer and computational number theorist. He is currently a professor at the École Polytechnique Fédérale de Lausanne (EPFL) where he heads of the Laborator ...
,
Hendrik Lenstra
Hendrik Willem Lenstra Jr. (born 16 April 1949, Zaandam) is a Dutch mathematician.
Biography
Lenstra received his doctorate from the University of Amsterdam in 1977 and became a professor there in 1978. In 1987 he was appointed to the faculty o ...
and
László Lovász
László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...
in 1982.
*The HJLS algorithm, developed by
Johan Håstad
Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation ...
, Bettina Just,
Jeffrey Lagarias
Jeffrey Clark Lagarias (born November 16, 1949 in Pittsburgh, Pennsylvania, United States) is a mathematician and professor at the University of Michigan.
Education
While in high school in 1966, Lagarias studied astronomy at the Summer Science ...
, 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 Joseph Dongarra (born July 18, 1950) is an American computer scientist and mathematician. He is the American University Distinguished Professor of Computer Science in the Electrical Engineering and Computer Science Department at the Unive ...
and Francis Sullivan even though it is considered essentially equivalent to HJLS.
*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'' . 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 is an approach to mathematics in which computation is used to investigate mathematical objects and identify properties and patterns. It has been defined as "that branch of mathematics that concerns itself ultimately with th ...
is to use
numerical methods and
arbitrary precision arithmetic to find an approximate value for an
infinite series
In mathematics, a series is, roughly speaking, a description of the operation of adding infinitely many quantities, one after the other, to a given starting quantity. The study of series is a major part of calculus and its generalization, math ...
,
infinite product In mathematics, for a sequence of complex numbers ''a''1, ''a''2, ''a''3, ... the infinite product
:
\prod_^ a_n = a_1 a_2 a_3 \cdots
is defined to be the limit of the partial products ''a''1''a''2...''a'n'' as ''n'' increases without bound. ...
or an
integral
In mathematics, an integral assigns numbers to functions in a way that describes displacement, area, volume, and other concepts that arise by combining infinitesimal data. The process of finding integrals is called integration. Along wit ...
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
In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th ro ...
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
The Bailey–Borwein–Plouffe formula (BBP formula) is a formula for . It was discovered in 1995 by Simon Plouffe and is named after the authors of the article in which it was published, David H. Bailey, Peter Borwein, and Plouffe. Before that, ...
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
4 is the logistic map's fourth bifurcation point, the constant α = −''B''
4(''B''
4 − 2) is a root of a 120th-degree polynomial whose largest coefficient is 257
30. Integer relation algorithms are combined with tables of high precision mathematical constants and heuristic search methods in applications such as the
Inverse Symbolic Calculator __NOTOC__
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 (Burnaby, ...
or
Plouffe's Inverter.
Integer relation finding can be used to
factor polynomials of high degree.
[M. van Hoeij: ''Factoring polynomials and the knapsack problem.'' J. of Number Theory, 95, 167–189, (2002).]
References
External links
''Recognizing Numerical Constants''by
David H. Bailey and
Simon Plouffe
Simon Plouffe (born June 11, 1956) is a mathematician who discovered the Bailey–Borwein–Plouffe formula (BBP algorithm) which permits the computation of the ''n''th binary digit of π, in 1995. His other 2022 formula allows extracting the '' ...
''Ten Problems in Experimental Mathematics'' by David H. Bailey,
Jonathan M. Borwein, Vishaal Kapoor, and
Eric W. Weisstein
Eric Wolfgang Weisstein (born March 18, 1969) is an American mathematician and encyclopedist who created and maintains the encyclopedias ''MathWorld'' and ''ScienceWorld''. In addition, he is the author of the '' CRC Concise Encyclopedia of M ...
{{number theoretic algorithms
Number theoretic algorithms