Complexity of a standard basis of a 𝐷-module

Grigoriev, D.; Chistov, A.

doi:10.1090/S1061-0022-09-01069-3

Complexity of a standard basis of a $D$-module
HTML articles powered by AMS MathViewer

by D. Yu. Grigoriev and A. L. Chistov
Translated by: The authors

St. Petersburg Math. J. 20 (2009), 709-736

DOI: https://doi.org/10.1090/S1061-0022-09-01069-3

Published electronically: July 21, 2009

PDF | Request permission

Abstract:

A double-exponential upper bound is obtained for the degree and for the complexity of constructing a standard basis of a $D$-module. This generalizes a well-known bound for the complexity of a Gröbner basis of a module over the algebra of polynomials. It should be emphasized that the bound obtained cannot be deduced immediately from the commutative case. To get the bound in question, a new technique is developed for constructing all the solutions of a linear system over a homogeneous version of a Weyl algebra.

References

D. A. Bayer, The division algorithm and the Hilbert scheme, Ph.D. Thesis, Harvard, 1982.
A. L. Chistov and D. Yu. Grigor′ev, Complexity of quantifier elimination in the theory of algebraically closed fields, Mathematical foundations of computer science, 1984 (Prague, 1984) Lecture Notes in Comput. Sci., vol. 176, Springer, Berlin, 1984, pp. 17–31. MR 783435, DOI 10.1007/BFb0030287
David Cox, John Little, and Donal O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer-Verlag, New York, 1998. MR 1639811, DOI 10.1007/978-1-4757-6911-1
Thomas W. Dubé, The structure of polynomial ideals and Gröbner bases, SIAM J. Comput. 19 (1990), no. 4, 750–775. MR 1053942, DOI 10.1137/0219053
André Galligo, Some algorithmic questions on ideals of differential operators, EUROCAL ’85, Vol. 2 (Linz, 1985) Lecture Notes in Comput. Sci., vol. 204, Springer, Berlin, 1985, pp. 413–421. MR 826576, DOI 10.1007/3-540-15984-3_{3}01
M. Giusti, Some effectivity problems in polynomial ideal theory, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 159–171. MR 779123, DOI 10.1007/BFb0032839
Dima Grigoriev, Weak Bézout inequality for D-modules, J. Complexity 21 (2005), no. 4, 532–542. MR 2152720, DOI 10.1016/j.jco.2004.09.006
Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann. 95 (1926), no. 1, 736–788 (German). MR 1512302, DOI 10.1007/BF01206635
Maurice Janet, Les modules de formes algébriques et la théorie générale des systèmes différentiels, Ann. Sci. École Norm. Sup. (3) 41 (1924), 27–65 (French). MR 1509256
Huishi Li, Noncommutative Gröbner bases and filtered-graded transfer, Lecture Notes in Mathematics, vol. 1795, Springer-Verlag, Berlin, 2002. MR 1947291, DOI 10.1007/b84211
F. S. Macaulay, Some properties of enumeration in the theory of modular systems, Proc. London Math. Soc. 26 (1927), 531–555.
H. Michael Möller and Ferdinando Mora, Upper and lower bounds for the degree of Groebner bases, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 172–183. MR 779124, DOI 10.1007/BFb0032840
Gunter Ritter and Volker Weispfenning, On the number of term orders, Appl. Algebra Engrg. Comm. Comput. 2 (1991), no. 1, 55–79. MR 1209244, DOI 10.1007/BF01810855
Fritz Schwarz, Janet bases for symmetry groups, Gröbner bases and applications (Linz, 1998) London Math. Soc. Lecture Note Ser., vol. 251, Cambridge Univ. Press, Cambridge, 1998, pp. 221–234. MR 1708880
Chee-K. Yap, A new lower bound construction for commutative Thue systems with applications, J. Symbolic Comput. 12 (1991), no. 1, 1–27. MR 1124303, DOI 10.1016/S0747-7171(08)80138-1