Termination of algorithm for computing relative Gröbner bases and difference differential dimension polynomials

Abstract

We introduce the concept of difference-differential degree compatibility on generalized term orders. Then we prove that in the process of the algorithm the polynomials with higher and higher degree would not be produced, if the term orders ‘\prec’ and ‘{\prec }^{\prime }’ are difference-differential degree compatibility. So we present a condition on the generalized orders and prove that under the condition the algorithm for computing relative Gröbner bases will terminate. Also the relative Gröbner bases exist under the condition. Finally, we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.

Keywords

Relative Gröbner basis / difference-differential module / bivariate dimension polynomial / termination of algorithm

References

[1] Dönch C. Bivariate difference-differential dimension polynomials and their computation in Maple. Proceedings of the 8th International Conference on Applied Informatics, Eger, Hungary, January 27-30, 2010, Vol 1. 2010, 221-228

[2] Dönch C. Characterization of relative Gröbner bases. J Symbolic Comput, 2013, 55: 19-29

[3] Insa M, Pauer F. Gröbner bases in rings of differential operators. In: Buchberger B, Winkler F, eds. Gröbner Bases and Applications. London Math Soc Lecture Note Ser,Vol 251. Cambridge: Cambridge University Press, 1998, 367-380

[4] Kolchin E R. The notion of dimension in the theory of algebraic differential equations. Bull Amer Math Soc, 1964, 70: 570-573

[5] Levin A.B. Reduced Gröbner bases, free difference-differential modules and differencedifferential dimension polynomials. J Symbolic Comput, 2000, 30(4): 357-382

[6] Levin A B. Gröbner bases with respect to several orderings and multivariable dimension polynomials. J Symbolic Comput, 2007, 42(5): 561-578

[7] Noumi N M. Wronskian determinants and the Gröbner representation of linear differential equation. In: Algebraic Analysis. Boston: Academic Press, 1988, 549-569

[8] Oaku T, Shimoyama T. A Gröbner basis method for modules over rings of differential operators. J Symbolic Comput, 1994, 18(3): 223-248

[9] Pauer F, Unterkircher A. Gröbner bases for ideals in Laurent polynomial rings and their applications to systems of difference equations. Appl Algebra Engrg Comm Comput, 1999, 9: 271-291

[10] Takayama N. Gröbner basis and the problem of contiguous relations. Japan J Appl Math, 1989, 6: 147-160

[11] Zhou M, Winkler F. Gröbner bases in difference-differential modules. Proceedings ISSAC 2006. New York: ACM Press, 2006: 353-360

[12] Zhou M, Winkler F. Computing difference-differential dimension polynomials by relative Gröbner bases in difference-differential modules. J Symbolic Comput, 2008, 43: 726-745

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg