Integer Relation

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 relations can be found in the Wolfram Language using FindIntegerNullVector[x1, x2, ...].

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).

Constant	Bound

REFERENCES:

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. https://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." https://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." https://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.