Generalization of Buchberger’s Algorithm with Respect to Several Orderings on Difference Modules

Authors
hamzeh harfsheno
abdolali basiri
sajjad rahmany
Damghan university
10.52547/mmr.7.3.513
Abstract
Grobner basis with respect to several orderings is a powerful tool to compute multivariate difference dimension polynomials. In this paper, an algorithm for computing a Grobner basis of a difference module over a ground difference field with respect to several term orderings is presented. In this direction, a representation of an element of a difference module with respect to several term orderings is introduced. Based on such representation, we generalize the Buchberger theorem to the case of free modules over difference rings with several term orderings associated with a partition of the set of variables. Furthermore, the necessary and sufficient condition is given for the existence of a Grobner basis with respect to several term orderings. In the sequel, we present our implementation of the algorithm on Maple.



./files/site1/files/%D8%AD%D8%B1%D9%81_%D8%B4%D9%86%D9%88%D8%A8%D8%B5%DB%8C%D8%B1%DB%8C(1).pdf


p { margin-bottom: 0.1in; direction: ltr; line-height: 115%; text-align: left; }
Keywords
Difference ring
Difference module
Groebner basis
Buchberger algorithm
1. Buchberger B., “On finding a vector space basis of the residue class ring modulo a zero dimensional polynomial ideal (in German)”, PhD Thesis, Universitate Innsbruck, Innsbruck (1965).

2. Cohn R.M., “Difference Algebra”, In: Tracts in Mathematics, vol. 17, Interscience, New York (1965).

3. Cox D., Little J., OShea D., “Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra”, 3rd edition, Springer, New York (2007).

4. Dönch C., “Standard Bases in Finitely Generated Difference-Skew-Differential Modules and Their Application to Dimension Polynomials”, PhD thesis, Johannes Kepler University Linz, Research Institute for Symbolic Computation (RISC) (2012).

5. Dönch C., Winkler F., “Bivariate difference-differential dimension polynomials and their computation in Maple”, 8 th International Conference on Applied Informatics Eger, Hungary, January 27–30(2010).

6. Einstein A., “The Meaning of Relativity. Appendix II (Generalization of Gravitation Theory)”, 4th ed. Princeton, (1953) 133–165.

7. Gerdt V. P., “Groebner bases in perturbative calculations” , Nucl. Phys. 135 (Proc. Suppl.) 232 (2004) [hep-ph/0501053].

8. Gerdt V.P., Robertz D., “Computation of Difference Grobner Bases”, Computer Science Journal of Moldova, vol.20, no.2(59) (2012).

9. Johnson J., Sit W., “On the differential transcendence polynomials of finitely generated differential field extensions”, Amer. J. Math. 101 (6) (1978) 1249–1263.

10. Kolchin E. R., “Differential Algebra and Algebraic Groups”, Academic Press, NewYork –London (1973).

11. Kolchin E. R., “The notion of dimension in the theory of algebraic difierential equations”, Bull. Am. Math. Soc.,70 (1964) 570-573.

12. Levin A. B., “Computation of the Strength of Systems of Difference Equations via Generalized Grobner Bases”, Grobner Bases in Symbolic Analysis, Walter de Gruyter, Berlin, (2007) 43-74.

13. Levin A. B., “Characteristic polynomials of filtered difference modules and of difference fleld extensions”, Russ. Math. Surv., 33 (1978) 165-166.

14. Levin A. B., “Difference Algebra”, Springer (2008).

15. Levin A. B., “Grobner bases with respect to several orderings and multivariable dimension polynomials”, Journal of Symbolic Computation ,42 (2007) 561–578.

16. Levin A. B., “Difference dimension quasi-polynomials”, Advances in Applied Mathematics ,89 (2017) 1–17.

17. Levin A. B., “Multivariable Difference Dimension Polynomials”, Journal of Mathematical Sciences, Vol. 131, No. 6 (2005).

18. Martin, B., Levandovskyy V., “Symbolic Approach to Generation and Analysis of Finite Difierence Schemes of Partial Difierential Equations”,. In: U. Langer, P. Paule (Eds.) Numerical and Symbolic Scientiflc Computing: Progress and Prospects, Springer, Wien, (2012) 123-156.

19. Mikhalev A. V., Levin A. B., Pankratiev E. V., Kondratieva M. V., “Differential and Difference Dimension Polynomials”, Mathematics and Its Applications, Kluwer, Dordrecht (1999).

20. Mikhalev A. V., PankratevKahler E. V. “Computer Algebra, Computations in Differential and Difference Algebra”, Moscow: Moscow State Univ Press (1989).

21. Mikhalev A.V., Pankratev E.V., “Differential dimension polynomial of a system of differential equations”, In: Algebra, Moscow State Univ. Press, Moscow, (1980) 57–67. Collection of papers (in Russian).

22. Ritt J. F., “Differential Algebra”, Dover Publications Inc., New York (1950).http ://www.am.:org/onlinebks/coll33.

23. Ritt J. F., “Differential equations from the algebraic standpoint”, volume 14 of American Mathematical Society Colloquium Publications, AMS., New York (1932) .

24. Scala R.L., “Grobner bases and gradings for partial difference ideals”, Mathematics of computation, Vol. 84, No. 292 (2015) 959–985.

25. The Maple implementation of our algorithms is available at the address http :

//faculty.du.ac.ir/rahmani/.

26. Zhou M., Winkler F., “Computing difference-differential dimension polynomials by relative Grobner bases in difference-differential modules”, Journal of Symbolic Computation, no. 43 (2008) 726–745.

27. Zhou M., Winkler F., “Grobner bases in difference-differential modules and differencedifferential dimension polynomials”, Science in China, Ser. A, Mathematics, 51/9 (2008) 1732-1752.
Mathematical Research
Volume 7, Issue 3 - Serial Number 18
Autumn 2021
Pages 513-526