An algorithm for deciding the summability of bivariate rational functions

Let Δxf(x,y)=f(x+1,y)−f(x,y) and Δyf(x,y)=f(x,y+1)−f(x,y) be the difference operators with respect to x and y. A rational function f(x,y) is called summable if there exist rational functions g(x,y) and h(x,y) such that f(x,y)=Δxg(x,y)+Δyh(x,y). Recently, Chen and Singer presented a method for deciding whether a rational function is summable. To implement their method in the sense of algorithms, we need to solve two problems. The first is to determine the shift equivalence of two bivariate polynomials. We solve this problem by presenting an algorithm for computing the dispersion sets of any two bivariate polynomials. The second is to solve a univariate difference equation in an algebraically closed field. By considering the irreducible factorization of the denominator of f(x,y) in a general field, we present a new criterion which requires only finding a rational solution of a bivariate difference equation. We give a new estimation of the universal denominators based on the m-fold Gosper representation and transform the bivariate difference equation to a system of linear difference equations in one variable. Combining these algorithms, we can decide the summability of a bivariate rational function.