|
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).
Algorithms for finding integer relations include the Ferguson-Forcade algorithm, HJLS
algorithm, LLL algorithm,
PSLQ algorithm, PSOS algorithm, and the algorithm of Lagarias and Odlyzko (1985).
Perhaps the simplest (and unfortunately most inefficient) such algorithm is the greedy algorithm.
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. Monthly 106, 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. Klasse 6, 1-29, 1919.
Brun, V. "En generalisatiken av kjedeboøken, II." Norske Vidensk.
Skrifter I. Matemat. Naturvid. Klasse 7, 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. ACM 32, 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. Paris 99, 1014-1016, 1884.
Szekeres, G. "Multidimensional Continued Fractions." Ann. Univ. Sci.
Budapest Eőtvős Sect. Math. 13, 113-140, 1970.
|
Contact the MathWorld Team
