Decomposition of polynomials and approximate roots

Abstract:

We state a kind of Euclidian division theorem: given a polynomial $P(x)$ and a divisor $d$ of the degree of $P$, there exist polynomials $h(x),Q(x),R(x)$ such that $P(x) = h\circ Q(x) +R(x)$, with $\deg h=d$. Under some conditions $h,Q,R$ are unique, and $Q$ is the approximate $d$-root of $P$. Moreover we give an algorithm to compute such a decomposition. We apply these results to decide whether a polynomial in one or several variables is decomposable or not.