Effective Bezout Identities in Q[z1,...,Zn]
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1987
- Accession Number
- ADA453878
Entities
People
- Alain Yger
- Carlos A. Berenstein
Organizations
- University of Maryland