generalized Euclidean algorithm | multidimensional continued fraction algorithm

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_1 x_1 + a_2 x_2 + ... + a_n x_n = 0, with not all a_i = 0. 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, 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.

constant problem | Ferguson-Forcade algorithm | greedy algorithm | Hermite-Lindemann theorem | HJLS algorithm | knapsack problem | lattice reduction | Lindemann-Weierstrass theorem | LLL algorithm | PSLQ algorithm | PSOS algorithm | real number | Richardson's theorem | subset sum problem