Polynomial-time algorithm for Hilbert series of Borel type ideals

ABSTRACT

In this paper, it is shown that the Hilbert series of a Borel type ideal may be computed within a complexity which is polynomial in Dⁿ where n + 1 is the number of unknowns and D is the highest degree of a minimal generator of input (monomial) ideal.

REFERENCES

• 1: D. Bayer and M. Stillman. A criterion for detecting m-regularity. Invent. Math., 87(1):1--11, 1987.
• 2: Dave Bayer , Mike Stillman, Computation of Hilbert functions, Journal of Symbolic Computation, v.14 n.1, p.31-50, July 1992 [doi>10.1016/0747-7171(92)90024-X]
• 3: I. Bermejo and P. Gimenez. Computing the Castelnuovo-Mumford regularity of some subschemes of PnK using quotients of monomial ideals. J. Pure Appl. Algebra, 164(1-2):23--33, 2001. Effective methods in algebraic geometry (Bath, 2000).
• 4: I. Bermejo and P. Gimenez. Saturation and Catelnuovo-Mumford regularity. J. Algebra, 303:592--617, 2006.
• 5: Anna Maria Bigatti , Pasqualina Conti , Lorenzo Robbiano , Carlo Traverso, A "Divide and Conquer" Algorithm for Hilbert-Poincaré Series, Multiplicity and Dimension of Monomial Ideals, Proceedings of the 10th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.76-88, May 10-14, 1993
• 6: D. Cox, J. Little, and D. O'Shea. Using algebraic geometry, volume 185 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1998.
• 7: S. Eliahou and M. Kervaire. Minimal resolutions of some monomial ideals. J. Algebra, 129(1):1--25, 1990.
• 8: R. Fröberg. An introduction to Gröbner bases. Pure and Applied Mathematics (New York). John Wiley & Sons Ltd., Chichester, 1997.
• 9: 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. http://www.singular.uni-kl.de.
• 10: A. Hashemi. Strong Noether Position and Stabilized Regularities. submitted to Applicable Algebra in Engineering, Communication and Computing, 2006.
• 11: J. Herzog, D. Popescu, and M. Vladoiu. On the Ext-modules of ideals of Borel type. In Commutative algebra (Grenoble/Lyon, 2001), volume 331 of Contemp. Math., pages 171--186. Amer. Math. Soc., Providence, RI, 2003.
• 12: A. Imran and A. Sarfraz. Regularity of ideals of Borel type is linearly bounded. Preprint (see math.AC/0610537), 2007.
• 13: E. W. Mayr and A. R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. in Math., 46(3):305--329, 1982.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Castelnuovo-Mumford regularity, Gröbner bases, Hilbert series, complexity, satiety