On computing sparse shifts for univariate polynomials
Y. N. Lakshman, B. David Saunders · 1994
) Introduction In this paper, we consider the problem of computing t-sparse shifts for univariate polynomials. Given a polynomial f(x) 2 F [x] of degree d (where F is a field of characteristic 0), consider the representation of f(x) in the basis 1; x \\Gamma ff; (x \\Gamma ff) 2 ; . . . for some ff 2 K; an extension of F ; i.e., f(x) = d X i=0 f i (x \\Gamma ff) i : Let t be a positive integer d: We say that ff is a t-sparse shift for f(x) (or, f(x) is t-sparse in the shifted basis 1; x \\Gamma ff; (x \\Gamma ff) 2 ; . . .) if at most t of the coefficients f i are non-zero. The main problem that we address is: given an f(x) and t as above, can we efficiently compute a t-sparse shift for f(x) if one exists? We construct an efficient algorithm for solving this problem and answer several related questions of interest, such as: When is a shift unique? When is a shift rational (meaning when does ff 2 F?)? How many evaluations does one need to distinguish 2 polynomials that are shi...