Algebraic osculation and application to factorization of sparse polynomials

Polynomials, factorization in commutative rings (13P05) Divisors, linear systems, invertible sheaves (14C20) Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Residues for several complex variables (32A27)

Abstract: We prove a theorem on algebraic osculation and we apply our result to the Computer Algebra problem of polynomial factorization. We consider X a smooth completion of the complex plane and D an effective divisor supported on the boundary of X. Our main result gives explicit conditions equivalent to that a given Cartier divisor on D extends to X. These osculation criterions are expressed with residues. We derive from this result a toric Hensel lifting which permits to compute the absolute factorization of a bivariate polynomial by taking in account the geometry of its Newton polytope. In particular, we reduce the number of possible recombinations when compared to the Galligo-Rupprecht algorithm.

Review text

Is quite of interest to find good algorithms for factorizations of a form \(f \in K[t_1,t_2]\), where \(K\subset {\mathbb C}\) is a number field. The main existing algorithms present problems when \(f\) is sparse (i.e. when there are many zeros as coefficients in a monomial expression of \(f\)), in fact they are not able to use the amount of information encoded in the Newton polytope \(N_f\) associated to \(f\). In this paper a new algorithm is found which allows to factorize sparse polynomials using the geometry of their Newton polytope. The way to achieve this result is to consider an embedding of the complex affine curve given by \(\{ f=0\}\subset {\mathbb C}^2\) into a compactification \(X\) of \({\mathbb C}^2\). If \(X\) is well-chosen, \(N_f\) can be recovered from the Picard class of a compactification \(C \subset X\) of \(\{ f=0\}\). Let \(\partial X\) be \(X \backslash {\mathbb C}^2\), then Pic(\(\partial X\)) = Pic(\(X\)), so the idea is to use \(C|_D\), where \(D\) is a divisor with support in \(|\partial X|\). The main result of the paper is a theorem which detects the irreducible components of \(C\) via necessary and sufficient conditions for a Cartier divisor on \(D\) to extend to \(C\). This ``osculation criterion is expressed via residues.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Algebraic osculation and application to factorization of sparse polynomials

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