In this article we state and prove a corrected version of Theorem 3.5 in [SIAM J. Comput., 18 (1989), pp. 859--881].

This paper presents for the first time a higher-dimensional continued fraction algorithm (abbreviated “cfa”) that produces diophantine approximations of more than linear goodness. On input $x_1 , \cdots ,x_{n - 1} \in {\bf R}$, it produces vectors $(p_1^{(k)} , \cdots p_{n - 1}^{(k)} ,q^{(k)} ) \in {\bf Z}^n ,k = 1,2, \cdots $, such that \[ \max\limits_{1 \leq i \leq n - 1} \left| x_i - \frac{p_i^{(k)}}{q^{(k)} } \right| \leq \frac{||x|| \cdot {\text{const}}(n)}{| q^{(k)} |^{1 + 1/(2n(n - 1))}}. \] By a theorem of Dirichlet, there is no algorithm that replaces the term $1/(2n(n - 1))$ by a term bigger than $1/(n - 1)$. The higher-dimensional cfa’s analyzed so far do not achieve better than $\max_{1 \leq i \leq n - 1} |x_i - p_i^{(k)} /q^{(k)} |\leq o(1)/|q^{(k)} |$. The $o(1)$ term decreases with k but is not known to be related with $q^{(k)} $. Other properties of the cfa are also generalized by the algorithm. On input $x_1 , \cdots ,x_{n - 1} $ it starts with the standard basis of ${\bf Z}^n $ and then constructs by performing elementary basis transformations a sequence $(\mathcal{B}^{(k)} )_{k} $ of bases of ${\bf Z}^n $. The sequence $(\mathcal{B}^{(k)} )_{k} $ is finite if and only if the numbers $x_1 , \cdots ,x_{n - 1} $, 1 are ${\bf Z}$-linearly dependent; a linear dependence is found in case of existence. The maximal distance between the vectors of $\mathcal{B}^{(k)} $ and the straight line $(x_1 , \cdots, x_{n - 1} ,1)$${\bf R}$, tends to zero exponentially fast in k. For each k, the above-mentioned vector $(p_1^{(k)} , \cdots ,p_{n - 1}^{(k)} ,q^{(k)} )$ is the first vector of basis $\mathcal{B}^{(k)} $. The algorithm is a variant of an algorithm for the integer relation problem presented in [G. Bergman, Notes on Ferguson and Forcade’s Generalized Euclidean Algorithm, preprint, Univ. California, Berkeley, 1980] and analyzed in [J. Hastad, B. Just, J. Lagarias, and C. P Schnorr, SIAM J. Comput.,18 (1989), pp. 859–881]. The bound on the goodness of the diophantine approximations is proven with a “parallel induction” technique.

A higher dimensional continued fraction algorithm (CFA) that produces diophantine approximations of more than linear goodness is given. The algorithm is also ideally convergent and detects integer relations.>

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.