Polynomial time algorithms for finding integer relations among real numbers

Reviewer: Laureano Gonzalez-Vega

All algorithms shown in this paper use as their main idea the Lattice Basis Reduction Algorithm introduced by Lenstra, Lenstra Jr., and Lova´sz [1]. The authors demonstrate several algorithms related to the following problem: “Given a vector of real numbers <__?__Pub Fmt italic>x<__?__Pub Fmt /italic>, compute nonzero vector with integer coefficients <__?__Pub Fmt italic>m<__?__Pub Fmt /italic>, orthogonal to <__?__Pub Fmt italic>x<__?__Pub Fmt /italic>, or decide that such relation does not exist with ?m??2 k. ” The Small Integer Relation Algorithm solves this problem in the general case (real inputs). Using this algorithm, two problems close to the initial one can be solved: (1) Given a real vector <__?__Pub Fmt italic>x<__?__Pub Fmt /italic>, compute several nonzero integer vectors, orthogonal to the given <__?__Pub Fmt italic>x<__?__Pub Fmt /italic> and linearly independent, or decide that they cannot exist with ?m??2 k ,<__?__Pub Caret> and (2) Given <__?__Pub Fmt italic>r<__?__Pub Fmt /italic> real vectors <__?__Pub Fmt italic>x(i)<__?__Pub Fmt /italic>, find <__?__Pub Fmt italic>l<__?__Pub Fmt /italic> nonzero integer coefficients orthogonal to the given <__?__Pub Fmt italic>x(i)<__?__Pub Fmt /italic> and linearly independent, or decide that they cannot exist into some range. The authors make a careful complexity study of these algorithms into the arithmetic model of complexity of real numbers. The authors use the Lattice Basis Reduction Algorithm to solve the first problem when the input vector has integer coefficients, that differs from the one shown for the real case. They find a bound for the number of bit operations needed to terminate the algorithm for a generic input. The paper clearly explains a new application of the powerful Lattice Basis Reduction Algorithm.