Shift Equivalence Testing of Polynomials and Symbolic Summation of Multivariate Rational Functions

MaRDI QIDQ6396516zbMATH OpenFDO

Authors Shaoshi Chen, Lixin Du, Hanqian Fang

Publication date 14 April 2022

Mathematics Subject Classification ID

Differential algebra (12H05) Difference algebra (12H10) Symbolic computation and algebraic computation (68W30)

Abstract: The Shift Equivalence Testing (SET) of polynomials is deciding whether two polynomials $p(x_1,ldots,x_m)$ and $q(x_1,ldots,x_m)$ satisfy the relation $p(x_1+a_1,ldots,x_m+a_m)=q(x_1,ldots,x_m)$ for some $a_1,ldots,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, Oliverira 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-Oliverira-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.

This page was built for publication: Shift Equivalence Testing of Polynomials and Symbolic Summation of Multivariate Rational Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396516)