Detecting lacunary perfect powers and computing their roots

We consider solutions to the equation f=hrf=hr for polynomials ff and hh and integer r≥2r≥2. Given a polynomial ff in the lacunary (also called sparse or super-sparse  ) representation, we first show how to determine if ff can be written as hrhr and, if so, to find such an rr. This is a Monte Carlo randomized algorithm whose cost is polynomial in the number of non-zero terms of ff and in logdegflogdegf, i.e., polynomial in the size of the lacunary representation, and it works over Fq[x]Fq[x] (for large characteristic) as well as Q[x]Q[x]. We also give two deterministic algorithms to compute the perfect root hh given ff and rr. The first is output-sensitive (based on the sparsity of hh) and works only over Q[x]Q[x]. A sparsity-sensitive Newton iteration forms the basis for the second approach to computing hh, which is extremely efficient and works over both Fq[x]Fq[x] (for large characteristic) and Q[x]Q[x], but depends on a number-theoretic conjecture. Work of Erdös, Schinzel, Zannier, and others suggests that both of these algorithms are unconditionally polynomial-time in the lacunary size of the input polynomial ff. Finally, we demonstrate the efficiency of the randomized detection algorithm and the latter perfect root computation algorithm with an implementation in the C++ library NTL.

► We show how to determine if a sparse polynomial is a perfect power.
► We show how to compute the polynomial root of a sparse polynomial if it exists.
► Algorithms are polynomial-time in the sparse size of the polynomial and the root.
► We demonstrate our algorithms with efficient implementations.