A set of real numbers, ..., is said to possess an integer relation if there exist integers
such that
with not all .
For historical reasons, integer relation algorithms are sometimes called generalized
Euclidean algorithms or multidimensional continued fraction algorithms.
An interesting example of such a relation is the 17-vector (1, ,
, ..., ) with , which has an integer relation (1, 0, 0, 0,
, 0, 0, 0, , 0, 0, 0, , 0, 0, 0, 1), i.e.,
This is a special case of finding the polynomial of degree satisfied by .
Integer relation algorithms can be used to solve subset sum problems, as well as to determine if a given numerical constant is equal
to a root of a univariate polynomial of degree or less (Bailey and Ferguson 1989, Ferguson and Bailey 1992).
One of the simplest cases of an integer relation between two numbers is the one inherent in the definition of the greatest common divisor.
The well-known Euclidean algorithm solves
this problem, as well as the more general problem of an integer relation between
two real numbers, yielding either an exact relation or an infinite sequence of approximate
relations (Ferguson et al. 1999). Although attempts were made to generalize
the algorithm to
by Hermite (1850), Jacobi (1868), Poincaré (1884), Perron (1907), Brun (1919,
1920, 1957), and Szekeres (1970), all such routines were known to fail in certain
cases (Ferguson and Forcade 1979, Forcade 1981, Hastad et al. 1989). The first
successful integer relation algorithm was developed by Ferguson and Forcade (1979)
(Ferguson and Bailey 1992, Ferguson et al. 1999).
Plouffe's "Inverse Symbolic Calculator" site includes a huge database of 54 million real numbers which are algebraically related
to fundamental mathematical constants. The Ferguson-Forcade
algorithm has shown that there are no algebraic equations of degree with integer coefficients having Euclidean norms below
certain bounds for ,
, , , , , , and , where e is the
base for the natural logarithm, is pi, and is the Euler-Mascheroni
constant (Bailey 1988).
Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. "Integer Relation Detection."
§2.2 in Experimental
Mathematics in Action. Wellesley, MA: A K Peters, pp. 29-31, 2006.Bailey,
D. H. and Broadhurst, D. J. "Parallel Integer Relation Detection:
Techniques and Applications." Math. Comput.70, 1719-1736, 2001.Bailey,
D. H. and Ferguson, H. R. P. "Numerical Results on Relations
Between Numerical Constants Using a New Algorithm." Math. Comput.53,
649-656, 1989.Bailey, D. and Plouffe, S. "Recognizing Numerical
Constants." Organic
Mathematics. Proceedings of the Workshop Held in Burnaby, BC, December 12-14, 1995
(Ed. J. Borwein, P. Borwein, L. Jörgenson, and R. Corless).
Providence, RI: Amer. Math. Soc., pp. 73-88, 1997. http://www.cecm.sfu.ca/organics/papers/bailey/.Bernstein,
L. The
Jacobi-Perron Algorithm: Its Theory and Applications. Berlin: Springer-Verlag,
1971.Borwein, J. and Bailey, D. Mathematics
by Experiment: Plausible Reasoning in the 21st Century. Wellesley, MA: A
K Peters, pp. 51-52, 2003.Borwein, J. M. and Corless, R. M.
"Emerging Tools for Experimental Mathematics." Amer. Math. Monthly106,
899-909, 1999.Borwein, J. M. and Lisonek, P. "Applications
of Integer Relation Algorithms." Disc. Math.217, 65-82, 2000.Brentjes,
A. J. "Multi-Dimensional Continued Fraction Algorithms." Mathemat.
Centre Tracts, No. 145. Amsterdam, Netherlands: Mathemat. Centrum, 1981.Brun,
V. "En generalisatiken av kjedeboøken, I." Norske Vidensk. Skrifter
I. Matemat. Naturvid. Klasse6, 1-29, 1919.Brun, V. "En
generalisatiken av kjedeboøken, II." Norske Vidensk. Skrifter I. Matemat.
Naturvid. Klasse7, 1-24, 1920.Brun, V. "Algorithmes
euclidiens pour trois et quatre nombres." In Treizième Congrès
des mathématiciens Scandinaves, tenu a Helsinki 18-23 août 1957.
Helsinki: Mercators Trycheri, pp. 46-64, 1958.Centre for Experimental
& Constructive Mathematics. "Integer Relations." http://www.cecm.sfu.ca/projects/IntegerRelations/.Ferguson,
H. R. P. and Bailey, D. H. "A Polynomial Time, Numerically Stable
Integer Relation Algorithm." RNR Techn. Rept. RNR-91-032, Jul. 14, 1992.Ferguson,
H. R. P.; Bailey, D. H.; and Arno, S. "Analysis of PSLQ, An Integer
Relation Finding Algorithm." Math. Comput.68, 351-369, 1999.Ferguson,
H. R. P. and Forcade, R. W. "Generalization of the Euclidean
Algorithm for Real Numbers to All Dimensions Higher than Two." Bull. Amer.
Math. Soc.1, 912-914, 1979.Forcade, R. W. "Brun's
Algorithm." Unpublished manuscript, 1-27, Nov. 1981.Hastad, J.;
Just, B.; Lagarias, J. C.; and Schnorr, C. P. "Polynomial Time Algorithms
for Finding Integer Relations Among Real Numbers." SIAM J. Comput.18,
859-881, 1988.Hermite, C. "Extraits de lettres de M. Ch. Hermite
à M. Jacobi sur differénts objets de la théorie de nombres."
J. reine angew. Math.3/4, 261-315, 1850.Jacobi, C. G.
"Allgemeine Theorie der Kettenbruchahnlichen Algorithmen, in welche jede Zahl
aus Drei vorhergehenden gebildet wird (Aus den hinterlassenen Papieren von C. G. Jacobi
mitgetheilt durch Herrn E. Heine." J. reine angew. Math.69,
29-64, 1868.Lagarias, J. C. and Odlyzko, A. M. "Solving
Low-Density Subset Sum Problems." J. ACM32, 229-246, 1985.Lenstra
A. K.; Lenstra, H. W. Jr.; and Lovász, L. "Factoring Polynomials
with Rational Coefficients." Math. Ann.261, 515-534, 1982.Perron,
O. "Grundlagen für eine Theorie des Jacobischen Kettenbruchalgorithmus."
Math. Ann.64, 1-76, 1907.Plouffe, S. "Plouffe's
Inverter." http://pi.lacim.uqam.ca/eng/.Poincaré,
H. "Sur une généralisation des fractions continues." Comptes
Rendus Acad. Sci. Paris99, 1014-1016, 1884.Szekeres, G.
"Multidimensional Continued Fractions." Ann. Univ. Sci. Budapest Eőtvős
Sect. Math.13, 113-140, 1970.
, ..., 
is said to possess an integer relation if there exist integers
such that
.
For historical reasons, integer relation algorithms are sometimes called generalized
Euclidean algorithms or multidimensional continued fraction algorithms.
,
, ..., 
) with 
, which has an integer relation (1, 0, 0, 0,
, 0, 0, 0, 
, 0, 0, 0, 
, 0, 0, 0, 1), i.e.,
satisfied by 
.
x1, x2, ...
].
or less (Bailey and Ferguson 1989, Ferguson and Bailey 1992).
by Hermite (1850), Jacobi (1868), Poincaré (1884), Perron (1907), Brun (1919,
1920, 1957), and Szekeres (1970), all such routines were known to fail in certain
cases (Ferguson and Forcade 1979, Forcade 1981, Hastad et al. 1989). The first
successful integer relation algorithm was developed by Ferguson and Forcade (1979)
(Ferguson and Bailey 1992, Ferguson et al. 1999).
with integer coefficients having Euclidean norms below
certain bounds for 
,
, 
, 
, 
, 
, 
, and 
, where e is the
base for the natural logarithm, 
is pi, and 
is the Euler-Mascheroni
constant (Bailey 1988).
