Computing the multilinear factors of lacunary polynomials without heights (Q2229711)

The lacunary representation of a polynomial \[P(x_1,\ldots ,x_n)=\sum_{j=1}^{k}a_jx_1^{\alpha_{1,j}}\cdots x_n^{\alpha_{n,j}}\] consists of the list of \(n+1\)-tuples \((a_j,\alpha_{1,j},\ldots ,\alpha_{n,j})\) with \(j=1,\ldots ,k\). This representation allows us to encode a high degree polynomial in a dense way. A well-known problem is the factorization of lacunary polynomials and in this direction, the general form of the Gap theorem states that: If \(F\) is factor of \(P\) then there exists \(\ell\) such that \(F\) is factor of \(\sum_{j=1}^{\ell}a_jx_1^{\alpha_{1,j}}\cdots x_n^{\alpha_{n,j}}\) and \(\sum_{j=\ell+1}^{k}a_jx_1^{\alpha_{1,j}}\cdots x_n^{\alpha_{n,j}}\). In the paper under review, the authors give first some variants of the Gap Theorem adapted to linear and multilinear factors. Using these results, they present a deterministic polynomial-time algorithm which computes the multilinear factors of multivariate lacunary polynomials over number fields. In the sequel, they deal with this computation over other fields of characteristic zero and finite fields of large characteristic. It should be noted that the previous algorithms used Gap Theorems expressed in terms of the heights of the coefficients, however the described Gap Theorems only depend on the exponents of the polynomials and these improvements play important roles in the efficiency of the presented algorithms.