Elimination theory for differential difference polynomials

ABSTRACT

In this paper we give an elimination algorithm for differential difference polynomial systems. We use the framework of a generalization of Ore algebras, where the independent variables are non-commutative. We prove that for certain term orderings, Buchberger's algorithm applied to differential difference systems terminates and produces a Gröbner basis. Therefore, differential-difference algebras provide a new instance of non-commutative graded rings which are effective Gröbner structures.

REFERENCES

• 1: Joachim Apel, Computational ideal theory in finitely generated extension rings, Theoretical Computer Science, v.244 n.1-2, p.1-33, Aug. 6, 2000 [doi>10.1016/S0304-3975(00)00172-9]
• 2: J. Apel , W. Lassner, An extension of Buchberger's algorithm and calculations in enveloping fields of lie algebras, Journal of Symbolic Computation, v.6 n.2-3, p.361-370, Oct./Dec. 1988 [doi>10.1016/S0747-7171(88)80053-1]
• 3: F. Baader. Unification in commutative theories, Hilbert's basis theorem and Gröbner bases. In Proc. 3rd UNIF'89, 1989.
• 4: A. D. Bell and K. D. Goodearl. Uniform rank over differential operator rings and Poincaré-Birkhoff-Witt extensions. Pacific Journal of Mathematics, 131(1):13--37, 1988.
• 5: Frédéric Chyzak , Bruno Salvy, Non-commmutative elimination in ore algebras proves multivariate identities, Journal of Symbolic Computation, v.26 n.2, p.187-227, Aug. 1998 [doi>10.1006/jsco.1998.0207]
• 6: D. Cox, J. Little, and D. O'Shea. Ideals, varieties, and algorithms. Springer, 1997.
• 7: D. Eisenbud. Commutative algebra with a view toward algebraic geometry. Springer, 1999.
• 8: André Galligo, Some Algorithmic Questions of Constructing Standard Bases, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.413-421, April 01-03, 1985
• 9: M. Giesbrecht, G. Reid, and Y. Zhang. Non-commutative Gröbner bases in Poincaré-Birkhoff-Witt extensions. In Conference on Computer Algebra and Scientific Computation (CASC'2002), pages 97--106, 2002.
• 10: E. Green. An introduction to non-commutative Gröbner bases. In K. D. Fisher, editor, Computational Algebras, Lecture Notes in Pure and Applied Mathematics 151, pages 167--190. Dekker, New York.
• 11: P. Hydon. Symmetries and first integrals of ordinary difference equations. Proceedings of the Royal Society of London, (A 456):2835--2855, 2000.
• 12: M. Insa and F. Pauer. Gröbner bases in rings of differential operators. In B. Buchberger and F. Winkler, editors, Gröbner bases and applications, LMS Lecture Notes series 251, pages 367--381. Cambridge University Press, 1998.
• 13: A. Kandr-Rody , V. Weispfenning, Non-commutative Gro¨bner bases in algebras of solvable type, Journal of Symbolic Computation, v.9 n.1, p.1-26, Jan. 1990 [doi>10.1016/S0747-7171(08)80003-X]
• 14: H. Kredel. Solvable Polynomial Rings. Verlag Shaker, Aachen., 1993.
• 15: S. Mac Lane. Homology. Springer-Verlag, 1963.
• 16: Klaus Madlener , Birgit Reinert, Computing Gröbner bases in monoid and group rings, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.254-263, July 06-08, 1993, Kiev, Ukraine [doi>10.1145/164081.164139]
• 17: Elizabeth L. Mansfield , Peter A. Clarkson, Applications of the differential algebra package diffgrob2 to classical symmetries of differential equations, Journal of Symbolic Computation, v.23 n.5-6, p.517-533, May/June 1997 [doi>10.1006/jsco.1996.0105]
• 18: Ferdinando Mora, Groebner Bases for Non-Commutative Polynomial Rings, Proceedings of the 3rd International Conference on Algebraic Algorithms and Error-Correcting Codes, p.353-362, July 15-19, 1985
• 19: T. Mora, Standard bases and non-noetherianity: non-commutative polynomial rings, Proceedings of the 4th International Conference, AAECC-4 on Applicable algebra, error-correcting codes, combinatorics and computer algebra, p.98-109, June 1988, Karlsruhe, Germany
• 20: Teo Mora, Groebner Bases in Non-Commutative Algebras, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.150-161, July 04-08, 1988
• 21: Teo Mora, An introduction to commutative and noncommutative Gro¨bner bases, Theoretical Computer Science, v.134 n.1, p.131-173, Nov. 7, 1994
• 22: Amnon Rosenmann, An algorithm for constructing Gro¨bner and free Schreier bases in free group algebras, Journal of Symbolic Computation, v.16 n.6, p.523-549, Dec. 1993 [doi>10.1006/jsco.1993.1061]
• 23: V. Weispfenning, Finite Gröbner bases in non-Noetherian skew polynomial rings, Papers from the international symposium on Symbolic and algebraic computation, p.329-334, July 27-29, 1992, Berkeley, California, United States [doi>10.1145/143242.143346]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms

Keywords:
Gröbner basis, difference equation, differential polynomial, ore algebra