A quasi-linear irreducibility test in K[[x]][y]

DOI10.1007/S00037-022-00221-WMaRDI QIDQ2149947zbMATH OpenOpenAlexFDO

Authors Adrien Poteaux, Martin Weimann

Publication date 27 June 2022

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.03551

zbMATH Keywords

algorithmapproximate rootscomplexityirreducibility testNewton polygonPuiseux seriesresidual polynomial

Mathematics Subject Classification ID

Polynomials (11S05) Polynomials, factorization in commutative rings (13P05) Singularities in algebraic geometry (14B05) Singularities of curves, local rings (14H20) Symbolic computation and algebraic computation (68W30)

Abstract: We provide an irreducibility test in the ring Kx[y] whose complexity is quasi-linear with respect to the discriminant valuation, assuming the input polynomial F square-free and K a perfect field of characteristic zero or greater than deg(F). The algorithm uses the theory of approximate roots and may be seen as a generalisation of Abhyankhar's irreducibility criterion to the case of non algebraically closed residue fields.

Review text

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 Kx[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 Kx[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 \(Kx[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.

Recommendations

• scientific article; zbMATH DE number 849914
• Irreducible polynomials with coefficients in a complete discrete valuation field
• On testing a bivariate polynomial for analytic reducibility
• Irreducibility of a polynomial over the field of p elements with p prime.
• Irreducibility testing over local fields

Cites work

• A Construction for Absolute Values in Polynomial Rings
• A construction for prime ideals as absolute values of an algebraic field
• A discriminant criterion of irreducibility
• A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function
• Accelerated tower arithmetic
• An algorithm for computing an integral basis in an algebraic function field
• Approximated roots, generating sequences, sufficiency of jets
• Characterization of Jacobian Newton polygons of plane branches and new criteria of irreducibility
• Complexity bounds for the rational Newton-Puiseux algorithm over finite fields
• Complexity of OM factorizations of polynomials over local fields
• Computing Puiseux series: a fast divide and conquer algorithm
• Computing the equisingularity type of a pseudo-irreducible polynomial
• Directed evaluation
• Good reduction of Puiseux series and applications
• Greatest common divisors of polynomials given by straight-line programs
• scientific article; zbMATH DE number 4146129 (Why is no real title available?)
• scientific article; zbMATH DE number 3944020 (Why is no real title available?)
• scientific article; zbMATH DE number 2020227 (Why is no real title available?)
• scientific article; zbMATH DE number 2120365 (Why is no real title available?)
• Improving complexity bounds for the computation of Puiseux series over finite fields
• Irreducibility criterion for germs of analytic functions of two complex variables
• Modern computer algebra
• Newton polygons of higher order in algebraic number theory
• Relaxed Hensel lifting of triangular sets
• The Computational Complexity of the Resolution of Plane Curve Singularities

Cited in

(5)

• scientific article; zbMATH DE number 3935187 (Why is no real title available?)
• [[:Publication:4848389|A Simple Algorithm for Deciding Primes in K[[x,y]]]]
• Irreducibility testing over local fields
• Polynomial factorization over Henselian fields
• Plane curve germs and contact factorization

This page was built for publication: A quasi-linear irreducibility test in \(\mathbb{K}x[y]\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2149947)