Effective Bezout identities in Q[z1, ..., zn]
Carlos A. Berenstein, Alain Yger · Acta Mathematica · 1991
If p(sub 1)..... , P(sub m)are n-variate polynomials with integral coefficients and no common zeros in C(exp n), Brownawell has shown in 1986 that there exist q(sub 1 )%...., q(sub m) polynomials with integral coefficients and nu is an element of Z(+) such that p(sub 1) q(sub 1) + ... + p(sub m) q(sub m) = nu, and max deg q(sub j) </= [max deg p(sub j) (exp n))]. On the other hand if h = logarithm of the largest coefficient of all the p(sub j), and h(sub 1) is the corresponding quantity for the q(sub j), then there is no sharp estimate of h(sub 1) in terms of h and max deg p(sub j). In this paper we show that when the variety of common zeros at infinity of the p(sub j) is discrete then (essentially) we have: h(sub 1) </= D(exp cn)h for an absolute constant c. If there were an algorithm to compute the q(sub j) in D(exp cn) time one would obtain exactly the above estimate. Current algorithms require about D(exp n squared) operations.