Complexity bound of absolute factoring of parametric polynomials

A. Ayad

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 5-29

Résumé

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 the polynomials with coefficients in each piece is given uniformly. Namely, for each piece there exist a positive integer $l\leqslant d$, $l$ variables $C_1,\dots,C_l$ algebraically independent over a ground field $F$ and rational functions $b_{J,j}$ of the parameters and of the variables $C_1,\dots,C_l$ such that for any parametric polynomial $f$ with coefficients in this piece, there exist $c_1,\dots,c_l\in\overline{F}$ with $f=\prod_jG_j$ where $G_j=\sum_{|J|}B_{J,j}Z^J$ is absolutely irreducible. Where $Z=(Z_0,\dots,Z_n)$ are the variables of $f$, each $B_{J,j}$ is the value of $b_{J,j}$ at the coefficients of $f$ and $c_1,\dots,c_l$. $\overline{F}$ denotes the algebraic closure of $F$.