Interpolation of shifted-lacunary polynomials (Q626682)

The authors exhibit an algorithm that computes a representation of a given polynomial in \(\mathbb{Q}\) in the sparsest shifted power basis \[ f(x)=c_1(x-\alpha)^{e_1}+c_2(x-\alpha)^{e_2}+\cdots+c_t(x-\alpha)^{e_t}, \] that is, \(t\) being absolutely minimal. This is done assuming that a black box for evaluation is given, and the resulting algorithm runs in deterministic polynomial time, where bit complexity is meant -- so that intermediate coefficient growth is accounted for. The required black box computes the value of the unknown polynomial over the field \(\mathbb{Z}_p\). The authors motivate their choice of the black box model. The article is partly based on other works by the first author. The hardest part is the calculation of \(\alpha\) (Section 2), which is achieved by reduction of the problem modulo \(p\), where finding the sparsest shift can be done naively, and by using an oracle that produces ``good primes'' for that reduction. A step in the algorithm is borrowed from [the first author, \textit{E. Kaltofen} and \textit{W.-S Lee}, J. Symb. Comput. 36, No. 3--4, 401--424 (2003; Zbl 1074.68078)]. Once \(\alpha\) is known, the shift can be factored out of the black box, effectively reducing the problem to usual interpolation of a sparse polynomial; the authors compile mostly known results and analyse the complexity in regards to their black box model, and show an algorithm that once more works modulo \(p\) and lifts the information (Section 3). In Section 4 an oracle for good primes is presented and the complexity analysis of the whole algorithm is given in Section 5.