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 metadatas

https://hal-polytechnique.archives-ouvertes.fr/hal-00936318
Contributor : Bruno Grenet <>
Submitted on : Friday, January 24, 2014 - 7:14:33 PM
Last modification on : Wednesday, November 20, 2019 - 3:20:54 AM

Links full text

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

291