Shift Equivalence Testing of Polynomials and Symbolic Summation of Multivariate Rational Functions
share
The Shift Equivalence Testing (SET) of polynomials is deciding whether two polynomials p(x_1, …, x_m) and q(x_1, …, x_m) satisfy the relation p(x_1 + a_1, …, x_m + a_m) = q(x_1, …, x_m) for some a_1, …, a_m in the coefficient field. The SET problem is one of basic computational problems in computer algebra and algebraic complexity theory, which was reduced by Dvir, Oliveira and Shpilka in 2014 to the Polynomial Identity Testing (PIT) problem. This paper presents a general scheme for designing algorithms to solve the SET problem which includes Dvir-Oliveira-Shpilka's algorithm as a special case. With the algorithms for the SET problem over integers, we give complete solutions to two challenging problems in symbolic summation of multivariate rational functions, namely the rational summability problem and the existence problem of telescopers for multivariate rational functions. Our approach is based on the structure of isotropy groups of polynomials introduced by Sato in 1960s. Our results can be used to detect the applicability of the Wilf-Zeilberger method to multivariate rational functions.
READ FULL TEXT