LOWER BOUNDS FOR DIOPHANTINE APPROXIMATIONS

We introduce a subexponential algorithm for geometric solving of multi variate polynomial equation systems whose bit complexity depends mainl y on intrinsic geometric invariants of the solution set. From this alg orithm, we derive a new procedure for the decision of consistency of p olynomial equation systems whose bit complexity is subexponential, too . As a byproduct, we analyze the division of a polynomial module a red uced complete intersection ideal and from this, we obtain an intrinsic lower bound for the logarithmic height of diophantine approximations to a given solution of a zero-dimensional polynomial equation system. This result represents a multivariate version of Liouville's classical theorem on approximation of algebraic numbers by rationals. A special feature of our procedures is their polynomial character with respect to the mentioned geometric invariants when instead of bit operations o nly arithmetic operations are counted at unit cost. Technically our pa per relies on the use of straight-line programs as a data structure fo r the encoding of polynomials, on a new symbolic application of Newton 's algorithm to the Implicit Function Theorem and on a special, basis independent trace formula for affine Gorenstein algebras. (C) 1997 Pub lished by Elsevier Science B.V.