Sparse shifts for univariate polynomials (Q1924546)

A \(t\)-sparse shift for a polynomial \(f(x)\) over the rationals with degree greater than or equal to \(t\) is an algebraic number \(\alpha\) such that \(f(x)= \sum a_i (x- \alpha)^i\) with at most \(t\) of the coefficients \(a_i\) nonzero. The authors develop some condition on the uniqueness and rationality of the \(t\)-sparse shift and an algorithm for computing a sparse shift for a given polynomial. In addition, a criterion is given for distinguishing two polynomials which are sparse with respect to bounded shifts together with a description of a polynomial time algorithm for computing sparse decomposition of univariate polynomials.