×

A combinatorial approach to involution and \(\delta \)-regularity. I: Involutive bases in polynomial algebras of solvable type. (English) Zbl 1175.13012

Summary: Involutive bases are a special form of non-reduced Gröbner bases with additional combinatorial properties. Their origin lies in the Janet-Riquier theory of linear systems of partial differential equations. We study them for a rather general class of polynomial algebras including also non-commutative algebras like those generated by linear differential and difference operators or universal enveloping algebras of (finite-dimensional) Lie algebras. We review their basic properties using the novel concept of a weak involutive basis and present concrete algorithms for their construction. As new original results, we develop a theory for involutive bases with respect to semigroup orders (as they appear in local computations) and over coefficient rings, respectively. In both cases it turns out that generally only weak involutive bases exist.
[For part II, cf. ibid. 20, No. 3–4, 261–338 (2009; Zbl 1175.13011).]

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Citations:

Zbl 1175.13011

Software:

Plural; SINGULAR; SYMMGRP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams, W.W., Loustaunau, P.: An Introduction to Gröbner Bases. Graduate Studies in Mathematics, vol. 3. American Mathematical Society, Providence (1994) · Zbl 0803.13015
[2] Apel, J.: Gröbnerbasen in Nichtkommutativen Algebren und ihre Anwendung. PhD thesis, Universität Leipzig (1988) · Zbl 0716.16001
[3] Apel J.: The computation of Gröbner bases using an alternative algorithm. In: Bronstein, M., Grabmeier, J., Weispfenning, V. (eds) Symbolic Rewriting Techniques, Progress in Computer Science and Applied Logic, vol. 15., pp. 35–45. Birkhäuser, Basel (1998) · Zbl 0985.16034
[4] Apel J.: Theory of involutive divisions and an application to Hilbert function computations. J. Symb. Comput. 25, 683–704 (1998) · Zbl 0943.68191 · doi:10.1006/jsco.1997.0194
[5] Apel J., Hemmecke R.: Detecting unnecessary reductions in an involutive basis computation. J. Symb. Comput. 40, 1131–1149 (2005) · Zbl 1120.13028 · doi:10.1016/j.jsc.2004.04.004
[6] Becker Th., Weispfenning V.: Gröbner Bases. Graduate Texts in Mathematics, vol. 141. Springer, New York (1993) · Zbl 0772.13010
[7] Bell A.D., Goodearl K.R.: Uniform rank over differential operator rings and Poincaré–Birkhoff–Witt extensions. Pacific J. Math. 131, 13–37 (1988) · Zbl 0598.16002
[8] Berger R.: The quantum Poincaré–Birkhoff–Witt theorem. Comm. Math. Phys. 143, 215–234 (1992) · Zbl 0755.17006 · doi:10.1007/BF02099007
[9] Björk J.E.: Rings of Differential Operators. North-Holland Mathematical Library 21. North- Holland, Amsterdam (1979)
[10] Blinkov Yu.A.: Method of separative monomials for involutive divisions. Prog. Comput. Softw. 27, 139–141 (2001) · Zbl 0991.68158 · doi:10.1023/A:1010986332560
[11] Bueso J.L., Gómez-Torrecillas J., Lobillo F.J.: Homological computations in PBW modules. Alg. Rep. Theor. 4, 201–218 (2001) · Zbl 1054.16040 · doi:10.1023/A:1011455831400
[12] Bueso J.L., Gómez-Torrecillas J., Lobillo F.J., Castro-Jiménez F.J.: An introduction to effective calculus in quantum groups. In: Caenepeel, S., Verschoren, A. (eds) Rings, Hopf Algebras, and Brauer Groups. Lecture Notes in Pure and Applied Mathematics, vol. 197, pp. 55–83. Marcel Dekker, New York (1998) · Zbl 0898.17007
[13] Bueso J.L., Gómez-Torrecillas J., Verschoren A.: Algorithmic Methods in Non-Commutative Algebra. Mathematical Modelling: Theory and Applications, vol. 17. Kluwer, Dordrecht (2003) · Zbl 1063.16054
[14] Chen Y.F., Gao X.S.: Involutive directions and new involutive divisions. Comput. Math. Appl. 41, 945–956 (2001) · Zbl 1018.12010 · doi:10.1016/S0898-1221(00)00332-1
[15] Cohn P.M.: Algebra II. John Wiley, London (1977) · Zbl 0341.00002
[16] Cox D., Little J., O’Shea D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185. Springer, New York (1998)
[17] Drinfeld V.G.: Hopf algebras and the quantum Yang-Baxter equations. Sov. Math. Dokl. 32, 254–258 (1985)
[18] Gerdt V.P.: Completion of linear differential systems to involution. In: Ghanza, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing–CASC’99, pp. 115–137. Springer, Berlin (1999)
[19] Gerdt V.P.: On an algorithmic optimization in computation of involutive bases. Prog. Comput. Softw. 28, 62–65 (2002) · Zbl 1037.68063 · doi:10.1023/A:1014816631983
[20] Gerdt V.P., Blinkov Yu.A.: Involutive bases of polynomial ideals. Math. Comput. Simul. 45, 519–542 (1998) · Zbl 1017.13500 · doi:10.1016/S0378-4754(97)00127-4
[21] Gerdt V.P., Blinkov Yu.A.: Minimal involutive bases. Math. Comput. Simul. 45, 543–560 (1998) · Zbl 1017.13501 · doi:10.1016/S0378-4754(97)00128-6
[22] Gerdt V.P., Blinkov Yu.A., Yanovich D.A.: Construction of Janet bases. I. Monomial bases. In: Ghanza, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing–CASC 2001, pp. 233–247. Springer, Berlin (2001a) · Zbl 1015.13012
[23] Gerdt V.P., Blinkov Yu.A., Yanovich D.A.: Construction of Janet bases II. In: Polynomialbases. Ghanza, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing–CASC 2001, pp. 249–263. Springer, Berlin (2001b) · Zbl 1015.13013
[24] Gianni P., Trager B., Zacharias G.: Gröbner bases and primary decomposition of polynomial ideals. J. Symb. Comput. 6, 149–167 (1988) · Zbl 0667.13008 · doi:10.1016/S0747-7171(88)80040-3
[25] Giesbrecht, M., Reid, G.J. and Zhang, Y.: Non-commutative Gröbner bases in Poincaré–Birkhoff–Witt extensions. In: Ghanza, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) Computer Algebra in Scientific Computing–CASC 2002. Fakultät für Informatik, Technische Universität München (2002)
[26] Gräbe H.-G.: The tangent cone algorithm and homogenization. J. Pure Appl. Alg. 97, 303–312 (1994) · Zbl 0813.13027 · doi:10.1016/0022-4049(94)00020-4
[27] Gräbe H.-G.: Algorithms in local algebra. J. Symb. Comput. 19, 545–557 (1995) · Zbl 0844.68066 · doi:10.1006/jsco.1995.1031
[28] Greuel G.-M., Pfister G.: Advances and improvements in the theory of standard bases and syzygies. Arch. Math. 66, 163–176 (1996) · Zbl 0854.13015 · doi:10.1007/BF01273348
[29] Greuel G.-M., Pfister G.: A Singular Introduction to Commutative Algebra. Springer, Berlin (2002) · Zbl 1023.13001
[30] Greuel, G.-M., Pfister, G., Schönemann, H.: Singular 2.0–a computer algebra system for polynomial computations. Technical report, Centre for Computer Algebra, University of Kaiserslautern (2001). http://www.singular.uni-kl.de · Zbl 1344.13002
[31] Hausdorf M., Seiler W.M.: An efficient algebraic algorithm for the geometric completion to involution. Appl. Alg. Eng. Commun. Comput. 13, 163–207 (2002) · Zbl 1095.13550 · doi:10.1007/s002000200099
[32] Hausdorf M., Seiler W.M.: Involutive bases in MuPAD. I. Involutive divisions. mathPAD 11, 51–56 (2002)
[33] Hausdorf, M., Seiler, W.M.: Involutive bases in MuPAD. II. Polynomial algebras of solvable type. mathPAD (to appear)
[34] Hausdorf M., Seiler W.M., Steinwandt R.: Involutive bases in the Weyl algebra. J. Symb. Comput. 34, 181–198 (2002) · Zbl 1054.16023 · doi:10.1006/jsco.2002.0556
[35] Hereman W.: Review of symbolic software for the computation of Lie symmetries of differential equations. Euromath. Bull. 2, 45–82 (1994) · Zbl 0891.65081
[36] Janet M.: Sur les systèmes d’équations aux dérivées partielles. J. Math. Pure Appl. 3, 65–151 (1920) · JFM 47.0440.04
[37] Janet M.: Les modules de formes algébriques et la théorie générale des systèmes différentiels. Ann. École Norm. Sup. 41, 27–65 (1924) · JFM 50.0321.03
[38] Janet, M.: Leçons sur les Systèmes d’Équations aux D érivées Partielles. Cahiers Scientifiques, Fascicule IV. Gauthier-Villars, Paris (1929) · JFM 55.0276.01
[39] Jimbo M.: A q-difference analogue of \({U(\mathfrak{g})}\) and the Yang-Baxter equations. Lett. Math. Phys. 10, 63–69 (1985) · Zbl 0587.17004 · doi:10.1007/BF00704588
[40] Kandry-Rody A., Weispfenning V.: Non-commutative Gröbner bases in algebras of solvable type. J. Symb. Comput. 9, 1–26 (1990) · Zbl 0715.16010 · doi:10.1016/S0747-7171(08)80003-X
[41] Kredel H.: Solvable Polynomial Rings. Verlag Shaker, Aachen (1993) · Zbl 0790.16027
[42] Lazard, D.: Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In: van Hulzen, J.A. (ed) Proc. EUROCAL ’83. Lecture Notes in Computer Science, vol. 162, pp. 146–156. Springer, Berlin (1983) · Zbl 0539.13002
[43] Levandovskyy, V.: On Gröbner bases for non-commutative G-algebras. In: Calmet, J., Hausdorf, M., Seiler, W.M. (eds.) Proc. Under- and Overdetermined Systems of Algebraic or Differential Equations, pp. 99–118. Fakultät für Informatik, Universität Karlsruhe (2002)
[44] Levandovskyy, V.: Non-commutative computer algebra for polynomial algebras: Gröbner bases, applications and implementation. PhD thesis, Fachbereich Mathematik, Universität Kaiserslautern (2005) · Zbl 1094.16030
[45] McConnell J.C., Robson J.C.: Non-commutative Noetherian Rings. Wiley, New York (1987) · Zbl 0644.16008
[46] Méray C., Riquier C.: Sur la convergence des développements des intégrales ordinaires d’un système d’équations différentielles partielles. Ann. Sci. Ec. Norm. Sup. 7, 23–88 (1890) · JFM 22.0348.02
[47] Miller E., Sturmfels B.: Combinatorial Commutative Algebra. Graduate Texts in Mathematics, vol. 227. Springer, New York (2005) · Zbl 1090.13001
[48] Mora, T.: An algorithm to compute the equations of tangent cones. In: Calmet, J.(ed.) Proc. EUROCAM ’82. Lecture Notes in Computer Science, vol. 144, pp. 158–165. Springer, Berlin (1982) · Zbl 0568.68029
[49] Noether E., Schmeidler W.: Moduln in nichtkommutativen Bereichen, insbesondere aus Differential- und Differenzausdrücken. Math. Zeit. 8, 1–35 (1920) · JFM 47.0097.03 · doi:10.1007/BF01212856
[50] Ore O.: Linear equations in non-commutative fields. Ann. Math. 32, 463–477 (1931) · JFM 57.0166.01 · doi:10.2307/1968245
[51] Ore O.: Theory of non-commutative polynomials. Ann. Math. 34, 480–508 (1933) · Zbl 0007.15101 · doi:10.2307/1968173
[52] Riquier C.: Les Systèmes d’Équations aux Derivées Partielles. Gauthier-Villars, Paris (1910)
[53] Saito M., Sturmfels B., Takayama N.: Gröbner Deformations of Hypergeometric Differential Equations Algorithms and Computation in Mathematics, vol. 6. Springer, Berlin (2000) · Zbl 0946.13021
[54] Seiler, W.M.: Involution–The Formal Theory of Differential Equations and its Applications in Computer Algebra. Algorithms and Computation in Mathematics, vol. 24. Springer, Berlin (2009, to appear)
[55] Sturmfels B., White N.: Computing combinatorial decompositions of rings. Combinatorica 11, 275–293 (1991) · Zbl 0739.68051 · doi:10.1007/BF01205079
[56] Thomas J.M.: Differential Systems. Colloquium Publications XXI. American Mathematical Society, New York (1937)
[57] Tresse A.: Sur les invariants différentiels des groupes continus de transformations. Acta Math. 18, 1–88 (1894) · JFM 25.0641.01 · doi:10.1007/BF02418270
[58] Trinks W.: Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen. J. Num. Th. 10, 475–488 (1978) · Zbl 0404.13004
[59] Varadarajan V.S.: Lie Groups, Lie Algebras, and their Representations. Graduate Texts in Mathematics, vol. 102. Springer, New York (1984) · Zbl 0955.22500
[60] Wu W.T.: On the construction of Gröbner basis of a polynomial ideal based on Riquier–Janet theory. Syst. Sci. Math. Sci. 4, 194–207 (1991) · Zbl 0802.13006
[61] Zharkov A.Yu., Blinkov Yu.A.: Involution approach to solving systems of algebraic equations. In: Jacob, G., Oussous, N.E., Steinberg, S. (eds) Proc. Int. IMACS Symp. Symbolic Computation, pp. 11–17. Lille, France (1993)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.