It is well-known that the resultant, as a basic concept in algebraic geometry and a powerful tool in elimination theory, gives conditions for an over-determined system of polynomial equations to have common solutions (Cox, 2004). Since most polynomials are sparse as they only contain certain fixed monomials, Gelfand, Kapranov, Sturmfels, and Zelevinsky introduced the concept of sparse resultant (Gelfand, 1994; Sturmfels, 1993). Canny and Emiris showed that the sparse resultant is a factor of the determinant of a Macaulay style matrix and gave efficient algorithms to compute the sparse resultant based on this matrix representation (Canny, 1995; Emiris, 2012a, b). D’Andrea further showed that the sparse resultant is the quotient of two determinants where the denominator is a minor of the numerator (D’Andrea, 2011).

With the resultant and sparse resultant theories becoming more mature, it is a natural idea to extend the algebraic results to differential and difference cases due to their broad applications. However, such results in differential and difference cases are not complete parallel with algebraic case. For the ordinary differential case, differential resultants and sparse differential resultants are studied successively (Li, 2015a; Rueda, 2010; Yang, 2011). For the ordinary difference case, Li et al. introduced the concept of sparse difference resultant for a Laurent transformally essential system consisting of n + 1 Laurent difference polynomials in n difference variables and its basic properties are proved (Li, 2015b). Based on the degree and the order bounds, they proposed a single exponential algorithm in terms of the number of variables, the Jacobi number, and the size of the Laurent transformally essential system, which is essentially to search for the sparse difference resultant with the given order and degree bound.

Sparse difference resultant arises in many areas of pure and applied mathematics and has potential applications beside the symbolic computation community. For example, the vanishing of the sparse difference resultant gives a necessary condition for the corresponding difference polynomial system to have non-zero solutions (Li, 2015b). Thus, it has great potentials to solve some important problems in difference algebra, such as elimination of difference indeterminates, solving difference equations in difference fields and so on (Cohn, 1965; Ovchinnikov, 2020; Hrushovski, 2007). Some natural phenomena in real world are described by difference equations (Gao, 2009; Ovchinnikov, 2020; Roeger, 2004; Henson, 2007; Ekhad, 2014). However, since the case of difference polynomial system is traditionally significantly harder, there are only few efficient algorithms and techniques about difference resultants so far. Up to now using mature techniques of the algebraic case to deal with differential or difference cases is an effective way (Yang, 2011; Li, 2015b). In the difference case one need to convert difference polynomials into an algebraic polynomial system, then to compute the classical sparse resultant, and finally convert the results back in the world of difference polynomials. One of the key observations of the conversion is the effective order of sparse difference resultant. Thus, the order bound of sparse difference resultant is particularly important and has a direct impact on the complexity of the associated algorithm.

In this paper, the authors show that the sparse difference resultant of a generic Laurent transformally essential system can be computed via the sparse resultant of a simple algebraic system arising from the difference system. Moreover, new order bounds of sparse difference resultant are found. Then, the authors propose an efficient algorithm to compute sparse difference resultant which is the quotient of two determinants whose elements are the coefficients of the polynomials in the algebraic system. The complexity of the algorithm is analyzed, and experimental results show the efficiency of the algorithm.

Publication:

-    Journal of Symbolic Computation, 107, 279-298 (2021).

Authors:

-    Chunming Yuan (Institute of Systems Science, AMSS, Chinese Academy of Sciences)

-    Zhiyong Zhang (Minzu University of China)