COMPLEXITY BOUND FOR THE ABSOLUTE FACTORIZATION OF PARAMETRIC POLYNOMIALS

    loading  Checking for direct PDF access through Ovid

Abstract

An algorithm is constructed for the absolute factorization of polynomials with algebraically independent parametric coefficients. It divides the parameter space into pairwise disjoint pieces such that the absolute factorization of polynomials with coefficients in each piece is given uniformly. Namely, for each piece there exist a positive integer l ≤ d, l variables C1,…, Cl algebraically independent over the ground field F, and rational functions bJ,j of the parameters and of the variables C1,…, Cl such that for any parametric polynomial f with coefficients in this piece, there exist c1,…, Cl∈F with f = FΠjGj where Gj = Σ|j|BJ,jZJ is absolutely irreducible. Here Z = (Z0,…, Zn) are the variables of f, each BJ,j is the value of bJ,j at the coefficients of f and c1,…, cl, and F denotes the algebraic closure of F. The number of pieces does not exceed (2d2+1)2n+3dv5, and the algorithm performs dO (n dr2) arithmetic operations in F (thus the number of operations is exponential in the number r = (n+1n+1+d) of coefficients of f), and its binary complexity is bounded by dO(n dr)2 if F =ℚ and by (pdndr2) if F = 𝔽p, where d is an upper bound on the degrees of polynomials. The techniques used include the Hensel lemma and the quantifier elimination in the theory of algebraically closed fields. Bibliography: 20 titles.

Related Topics

    loading  Loading Related Articles