A quasi-linear irreducibility test in \(\mathbb{K}[[x]][y]\) (Q2149947)

In the paper under review, the authors address the problem of factorizing a univariate polynomial over a ring of formal power series. This problem has applications in the study of singularities of algebraic plane curves. Suppose that \(F \in K[[x]][y]\) is a square-free polynomial of degree \(d\). Furthermore, let \(\delta\) denote the valuation of the discriminant of \(F\). Assume that the base field \(K\) is such that its characteristic does not divide \(d\) and an effective univariate polynomial irreducibility test over \(K\) is available. The polynomial \(F=a_0(x)+a_1(x)y+\cdots + a_d(x)y^d\in K[[x]][y]\) is called Weierstrass if \(a_d=1\) and \(a_i(0)=0\) for \(i<d\). Let \(\mathcal{O}\) denote the number of arithmetic operations by ignoring logarithmic factors. The main constitution of this paper is that there exists a Las Vegas algorithm that tests whether a Weierstrass polynomial \(F\) is irreducible in \(K[[x]][y]\) in the time \(\mathcal{O}(\delta)\) along with a univariate irreducibility test over \(K\) of a polynomial of degree at most \(d\). This result is also extended to non-Weierstrass polynomials.