Algorithms for computing sparse shifts for multivariate polynomials (Q1583886)

The authors investigate the problem of finding \(t\)-sparse shifts for multivariate polynomials. Giving a degree \(d\) polynomial \(f\) in \(n\) indeterminates with coefficients in a field \(\mathcal F\) and an integer \(t\), they consider the problem of representing \(f(x)\) as \({\mathcal K}\)-linear combination of the power products of \(u_i\) where \(u_i=x_i-b_i\) for some \(b_i \in {\mathcal K}\), an extension of \({\mathcal F}\), for \(i=1,\ldots ,n\), that is \(f=\sum_{j}F_j u^{\alpha_j}\), in which at most \(t\) of the \(F_j\) are non-zero. The authors provide sufficient conditions for uniqueness of sparse shifts for multivariate polynomials, prove tight bounds on the degree of the polynomial being interpolated in terms of the sparsity bound \(t\) and a bound size of the coefficients of the polynomial in the standard representation, and describe two new efficient algorithms for computing sparse shifts for a multivariate polynomial.