Hypergeometric dispersion and the orbit problem
Sergei A. Abramov, Manuel Bronstein · 2000
We describe an algorithm for finding the positive integer solutions n of orbit problems of the form αn = β where α and β are given elements of a field K. Our algorithm corrects the bounds given in [7], and shows that the problem is not polynomial in the Euclidean norms of the polynomials involved. Combined with a simplified version of the algorithm of [8] for the “specification of equivalence”, this yields a complete algorithm for computing the dispersion of polynomials in nested hypergeometric extensions of rational function fields. This is a necessary step in computing symbolic sums, or solving difference equations, with coefficients in such fields. We also solve the related equations p(αn) = 0 and p(n, αn) = 0 where p is a given polynomial and α is given.