A quasi-linear irreducibility test in \(\mathbb{K}[[x]][y]\) (Q2149947)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A quasi-linear irreducibility test in \(\mathbb{K}[[x]][y]\) |
scientific article |
Statements
A quasi-linear irreducibility test in \(\mathbb{K}[[x]][y]\) (English)
0 references
27 June 2022
0 references
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.
0 references
irreducibility test
0 references
Newton polygon
0 references
residual polynomial
0 references
Puiseux series
0 references
approximate roots
0 references
algorithm
0 references
complexity
0 references
0 references