Bounded-degree factors of lacunary multivariate polynomials. (July 2016)

• Record Type: Journal Article
• Authors: Grenet, Bruno
• Is Part Of: Journal of symbolic computation. Volume 75(2016)
• Page Start: 171
• Page End: 192
• Publication Date: 2016-07
• Subjects: Multivariate lacunary polynomials -- Polynomial factorization -- Newton polygon -- Puiseux series -- Wronskian determinant; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.11.013
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d . Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable.