Polynomial factorization over Henselian fields (Q7004732)

We let \((K,v)\) be a valued field, \(K^h\) be its Henselization, \(\overline{K}\) be its algebraic closure, \(p\) be the residue characteristic of \((K,v)\) and \(\bar{v}\) be an extension of \(v\) to \(\overline{K}\). This paper provides two deterministic algorithms. Given an irreducible polynomial \(g\in K[x]\) such that \(p\nmid \mbox{deg}(g)\), the second algorithm tests if \(g\) is irreducible in \(K^h[x]\), and in this case it computes the ramification index and the residual degree of the unique extension of \(v\) to the field \(K[x]/(g)\). In the first algorithm, in addition \(v\) has rank one and \(p>\mbox{deg}(g)\). This algorithm outputs all extensions of \(v\) to \(K[x]/(g)\), together with a computation of their ramification indices and residual degrees. Furthermore, it outputs approximations to all irreducible factors of \(g\) over \(K^h[x]\) up to an arbitrary given precision. It remains to define approximants of irreducible factors, and the precision of an approximation.\N\NLet \(F\) be monic irreducible polynomial of \(K^h[x]\), \(\theta\) be a root of \(F\) in \(\overline{K}\); for any \(f\in K[x]\) set \(w_F(f)=\bar{v}(f(\theta))\), (which doesn't depend on \(\theta\)). We let \(\mathcal{T}\) be the set of all valuations on \(K[x]\) with images in \(v(K^*)\otimes \mathbb{Q}\cup \{\infty\}\) which extend \(v\) (where \(v(K^*)\otimes \mathbb{Q}\) is the divisible hull of \(v(K^*)\)), and \(\mathcal{T}^{\mathrm{inn}}\) be the set of valuations in \(\mathcal{T}\) which are residually transcendental. Note that in this paper a valuation on \(K[x]\) needs not satisfy \(v(f)=\infty \Leftrightarrow f=0\); the set \(v^{-1}(\{\infty\})\) is a prime ideal. For any \(\mu\), \(\nu\) in \(\mathcal{T}\), we set \(\mu \leq \nu\) if \(\forall f\in K[x]\; \mu(f)\leq \nu(f)\). Let \(\mu\in \mathcal{T}\); a monic polynomial \(\phi\in K[X]\) of degree \(d\geq 1\) is a key polynomial for \(\mu\) if every \(f_1\), \(f_2\) in \(K[X]\) of degrees lower than \(d\) we have \(\mu(f_1f_2)= \mu(r)<\mu(q\phi)\), where \(q\) and \(r\) are the quotient and the remainder of the euclidean division of \(f_1f_2\) by \(\phi\). Now, we assume that \(\mu\in \mathcal{T}^{\mathrm{inn}}\) and \(\phi\) is a key polynomial for \(\mu\). Denote by \(\mathcal{F}_{\mu,\phi}(g)\) the set of all monic irreducible factors \(G\) of \(g\) in \(K^h[x]\) such that \(\mu< w_G\) and \(\mu(\phi)<w_G(\phi)\). The irreducible polynomial \(\phi\in K[x]\) has a unique monic irreducible factor \(Q_{\mu,\phi}\in K^h[x]\) such that for every \(f\in K[x]\) we have \(w_{Q_{\mu,\phi}}(f)=\infty \Leftrightarrow \phi \mid f\) and \(\mbox{deg}(f)<\mbox{deg}(\phi)\Rightarrow w_{Q_{\mu,\phi}}(f)=\mu(f)\). If \(\mathcal{F}_{\mu,\phi}(g)=\{G\}\), \(\mbox{deg}(G)=\mbox{deg}(Q_{\mu,\phi})\) and \(\phi\) is irreducible in \(K^h[x]\), then \(\phi\) is called an approximant of \(G\). The precision of the approximation is the measure of the quality of the approximant \(Q\), which is given by the value \(w_G(Q-G)=w_G(Q)\).