Integer Relation

A set of Real Numbers $x_1$, ..., $x_n$ is said to possess an integer relation if there exist integers $a_i$ such that

$$a_1x_1+a_2x_2+\ldots+a_nx_n=0,$$

with not all $a_i=0$. An interesting example of such a relation is the 17-Vector (1, $x$, $x^2$, ..., $x^{16}$) with $x=3^{1/4}-2^{1/4}$, which has an integer relation (1, 0, 0, 0, $-3860$, 0, 0, 0, $-666$, 0, 0, 0, $-20$, 0, 0, 0, 1), i.e.,

$$1-3860x^4-666x^8-20x^{12}+x^{16}=0.$$

This is a special case of finding the polynomial of degree $n=rs$ satisfied by $x=3^{1/r}-2^{1/s}$.

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.

See also Constant Problem, Ferguson-Forcade Algorithm, Greedy Algorithm, Hermite-Lindemann Theorem, HJLS Algorithm, Lattice Reduction, LLL Algorithm, PSLQ Algorithm, PSOS Algorithm, Real Number, Lindemann-Weierstraß Theorem

References

Bailey, D. and Plouffe, S. ``Recognizing Numerical Constants.'' http://www.cecm.sfu.ca/organics/papers/bailey/.

Lagarias, J. C. and Odlyzko, A. M. ``Solving Low-Density Subset Sum Problems.'' J. ACM 32, 229-246, 1985.

Plouffe, S. ``Inverse Symbolic Calculator.'' http://www.cecm.sfu.ca/projects/ISC/.