NEW RESULTANT INEQUALITIES AND COMPLEX POLYNOMIAL FACTORIZATION

The author deduces some new probabilistic estimates on the distances b etween the zeros of a polynomial p(chi) by using some properties of th e discriminant of p(chi) and applies these estimates to improve the fa stest deterministic algorithm for approximating polynomial factorizati on over the complex field. Namely given a natural n, positive epsilon, such that log(1/epsilon) = O(n logn), and the complex coefficients of a polynomial p(chi) = Sigma(i=0)(n)p(i) chi(i), such that p(n) not eq ual 0, Sigma(i)\pi\less than or equal to 1, a factorization of p(chi) (within the error norm epsilon) is computed as a product of factors of degrees at most n/2, by using O(log(2) n) time and n(3) processors un der the PRAM arithmetic model of parallel computing or by using O(n(2) log(2) n) arithmetic operations. The algorithm is randomized, of Las V egas type, allowing a failure with a probability at most delta, for an y positive delta < 1 such that log(1/delta) = O(log n). Except for a n arrow class of polynomials p(chi), these results can be also obtained for a such that log(1/epsilon) = O(n(2) log n).