Efficient computation of Castelnuovo-Mumford regularity

Hashemi, Amir

doi:10.1090/S0025-5718-2011-02515-9

Efficient computation of Castelnuovo-Mumford regularity
HTML articles powered by AMS MathViewer

by Amir Hashemi PDF

Math. Comp. 81 (2012), 1163-1177 Request permission

Abstract:

In this paper, we introduce the notion of a homogeneous ideal in quasi stable position (QSP); a new definition for the notion of generic coordinates to compute efficiently the Castelnuovo-Mumford regularity of a homogeneous ideal. This definition is simple to check, because it is tested on the initial ideal for the degree reverse lexicographic ordering. It is explicit, because we provide an algorithm to decide whether a monomial ideal is in QSP or not. The main result of this paper is that the Castelnuovo-Mumford regularity of an ideal in QSP is the maximal degree of the elements of its reduced Gröbner basis with respect to the reverse lexicographic ordering. We have implemented an algorithm in (the distributed library noether.lib of) Singular based on the above results for computing the Castelnuovo-Mumford regularity of a general ideal, and we evaluate its performance via some examples.

References

Amir Hashemi. noether.lib. A Singular 3.0.3 distributed library for computing Castelnuovo-Mumford regularity, 2007.
Dave Bayer. The Division Algorithm and the Hilbert Scheme. PhD thesis, Harvard University, 1982.
David Bayer and Michael Stillman, A criterion for detecting $m$-regularity, Invent. Math. 87 (1987), no. 1, 1–11. MR 862710, DOI 10.1007/BF01389151
Isabel Bermejo and Philippe Gimenez, Computing the Castelnuovo-Mumford regularity of some subschemes of ${\Bbb P}_K^n$ using quotients of monomial ideals, J. Pure Appl. Algebra 164 (2001), no. 1-2, 23–33. Effective methods in algebraic geometry (Bath, 2000). MR 1854328, DOI 10.1016/S0022-4049(00)00143-2
Isabel Bermejo and Philippe Gimenez, Saturation and Castelnuovo-Mumford regularity, J. Algebra 303 (2006), no. 2, 592–617. MR 2255124, DOI 10.1016/j.jalgebra.2005.05.020
Wolfram Decker, Gert-Martin Greuel, and Gerhard Pfister, Primary decomposition: algorithms and comparisons, Algorithmic algebra and number theory (Heidelberg, 1997) Springer, Berlin, 1999, pp. 187–220. MR 1672046
David Eisenbud, Commutative algebra, Graduate Texts in Mathematics, vol. 150, Springer-Verlag, New York, 1995. With a view toward algebraic geometry. MR 1322960, DOI 10.1007/978-1-4612-5350-1
David Eisenbud and Shiro Goto, Linear free resolutions and minimal multiplicity, J. Algebra 88 (1984), no. 1, 89–133. MR 741934, DOI 10.1016/0021-8693(84)90092-9
Shalom Eliahou and Michel Kervaire, Minimal resolutions of some monomial ideals, J. Algebra 129 (1990), no. 1, 1–25. MR 1037391, DOI 10.1016/0021-8693(90)90237-I
André Galligo, À propos du théorème de-préparation de Weierstrass, Fonctions de plusieurs variables complexes (Sém. François Norguet, octobre 1970–décembre 1973; à la mémoire d’André Martineau), Lecture Notes in Math., Vol. 409, Springer, Berlin, 1974, pp. 543–579 (French). Thèse de 3ème cycle soutenue le 16 mai 1973 à l’Institut de Mathématique et Sciences Physiques de l’Université de Nice. MR 0402102
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
Mark L. Green, Generic initial ideals, Six lectures on commutative algebra (Bellaterra, 1996) Progr. Math., vol. 166, Birkhäuser, Basel, 1998, pp. 119–186. MR 1648665
G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2005.
D. Lazard, Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations, Computer algebra (London, 1983) Lecture Notes in Comput. Sci., vol. 162, Springer, Berlin, 1983, pp. 146–156. MR 774807, DOI 10.1007/3-540-12868-9_{9}9
Daniel Lazard, Résolution des systèmes d’équations algébriques, Theoret. Comput. Sci. 15 (1981), no. 1, 77–110 (French, with English summary). MR 619687, DOI 10.1016/0304-3975(81)90064-5