Polynomial Time Algorithms for Finding Integer Relations among Real Numbers

Abstract

This paper considers variants and generalizations of the following computational problem. Given a real input ${\bf x} \in \mathbb{R}^n $, find a small integer relation ${\bf m}$ for x that is a nonzero vector $m \in \mathbb{Z}^n $ orthogonal to ${\bf x}$, or prove that no integer relation ${\bf m}$ exists with $\|{\bf m}\| \leqq 2^\lambda $. An algorithm is presented that solves this problem in $O(n^3 (k + n))$ arithmetic operations over real numbers. The algorithm is a variation of the multidimensional Euclidean algorithm proposed by Ferguson and Forcade [Bull. Amer. Math. Soc., 1(1979), pp. 912–914] and Bergman [Notes on Ferguson and Forcade’s Generalized Euclidean Algorithm, University of California, Berkeley, CA, 1980]. A connection between such multidimensional Euclidean algorithms and the Lattice Basis Reduction Algorithm of Lenstra, Lenstra Jr., and Lovász [Math. Ann., 21 (1982), pp. 515–534] is shown. Polynomial time solutions are also established for finding linearly independent sets of small integer relations and for finding small simultaneous integer relations for several real vectors, using real input vectors and counting arithmetic operations over real numbers at unit cost. For integer input vectors ${\bf x}$ a different algorithm is given for finding integer relations (that always exist) that uses at most $O(n^3 \log \|x\|)$ arithmetic operations on $O(n + \log \|{\bf x}\|)$ bit integers.