Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Computing the multilinear factors of lacunary polynomials without heights

Abstract : We present a deterministic polynomial-time algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. It is based on a new Gap theorem which allows to test whether $P(X)=\sum_{j=1}^k a_j X^{\alpha_j}(vX+t)^{\beta_j}(uX+w)^{\gamma_j}$ is identically zero in polynomial time. Previous algorithms for this task were based on Gap Theorems expressed in terms of the height of the coefficients. Our Gap Theorem is based on the valuation of the polynomial and is valid for any field of characteristic zero. As a consequence we obtain a faster and more elementary algorithm. Furthermore, we can partially extend the algorithm to other situations, such as absolute and approximate factorizations. We also give a version of our Gap Theorem valid for fields of large characteristic, and deduce a randomized polynomial-time algorithm to compute multilinear factors with at least three monomials of multivariate lacunary polynomials of finite fields of large characteristic. We provide $\mathsf{NP}$-hardness results to explain our inability to compute binomial factors.
Complete list of metadata
Contributor : Bruno Grenet <>
Submitted on : Friday, January 24, 2014 - 7:14:33 PM
Last modification on : Tuesday, August 11, 2020 - 10:02:02 AM

Links full text


  • HAL Id : hal-00936318, version 1
  • ARXIV : 1311.5694



Arkadev Chattopadhyay, Bruno Grenet, Pascal Koiran, Natacha Portier, Yann Strozecki. Computing the multilinear factors of lacunary polynomials without heights. 2013. ⟨hal-00936318⟩



Record views