Degree upper bounds for H-bases. (English) Zbl 1427.13037
Classically, Gröbner bases have been used to solve the ideal membership problem, but they have definite drawbacks.
They are not numerically stable; moreover, since they depend on fixing a term order, the Gröbner basis of an ideal generated by a set of symmetric polynomials may break the symmetry among the variables.
The authors use an alternative approach by using the notion of \(H\)-bases, which was introduced by F. S. Macaulay [The algebraic theory of modular systems. Cambridge: University press, XIV u (1916; JFM 46.0167.01)]. These \(H\)-bases are independent of the choice of monomial order.
The authors produce upper bounds for the maximal degree of the elements of an \(H\)-basis of a given ideal in terms of the Hilbert regularity, satiety and dimension of the ideal. After defining the notion of a reduced \(H\)-basis, the authors demonstrate that the maximal degree of the elements of an \(H\)-basis is independent of the choice of basis. In addition, this degree remains fixed when performing any linear change of variables. Using this upper bound, the authors conclude that general \(H\)-bases may be computed in fewer steps than Grobner bases.
The authors produce upper bounds for the maximal degree of the elements of an \(H\)-basis of a given ideal in terms of the Hilbert regularity, satiety and dimension of the ideal. After defining the notion of a reduced \(H\)-basis, the authors demonstrate that the maximal degree of the elements of an \(H\)-basis is independent of the choice of basis. In addition, this degree remains fixed when performing any linear change of variables. Using this upper bound, the authors conclude that general \(H\)-bases may be computed in fewer steps than Grobner bases.
Reviewer: Edward Mosteig (Los Angeles)
MSC:
| 13P10 | Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) |
| 68W30 | Symbolic computation and algebraic computation |
| 33F10 | Symbolic computation of special functions (Gosper and Zeilberger algorithms, etc.) |
Citations:
JFM 46.0167.01Software:
SINGULARReferences:
| [1] | Bayer, D., 1982. The division algorithm and the Hilbert scheme. Ph.D. thesis, Harvard University. |
| [2] | Bayer, D., Stillman, M., 1987. A criterion for detecting m-regularity. Invent. Math. 87, 1-11. · Zbl 0625.13003 |
| [3] | Bermejo, I., Gimenez, P., 2001. Computing the Castelnuovo-Mumford regularity of some subschemes of PnKusing quotients of monomial ideals. J. Pure Appl. Algebra 164 (1-2), 23-33. · Zbl 0989.13008 |
| [4] | Bermejo, I., Gimenez, P., 2006. Saturation and Castelnuovo-Mumford regularity. J. Algebra 303 (2), 592-617. · Zbl 1105.13010 |
| [5] | Binaei, B., Hashemi, A., Seiler, W. M., 2018. A Pommaret bases approach to the degree of a polynomial ideal. Appl. Algebra Eng. Commun. Comput., 29 (4), 283-301. · Zbl 1410.13017 |
| [6] | Brownawell, W., Masser, D., 1980. Multiplicity estimates for analytic functions. II. Duke Math. J. 47, 273-295. · Zbl 0461.10027 |
| [7] | Bruns, W., Herzog, J., 1998. Cohen-Macaulay rings. Cambridge University Press. · Zbl 0909.13005 |
| [8] | Buchberger, B., 1985. Gr¨obner bases: an algorithmic method in polynomial ideal theory. Multidimensional systems theory, Progress, directions and open problems, Math. Appl., D. Reidel Publ. Co. 16, 184-232 (1985). · Zbl 0587.13009 |
| [9] | Buchberger, B., 2006. Bruno Buchberger’s PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German. J. Symb. Comput. 41 (3-4), 475-511. · Zbl 1158.01307 |
| [10] | Cartan, E., 1901. Sur l’int´egration des syst‘emes d’´equations aux diff´erentielles totales. Ann. Sci. ´Ec. Norm. Sup´er. (3) 18, 241-311. · JFM 32.0351.04 |
| [11] | Cartan, E., 1911. Sur les syst‘emes en involution d’´equations aux d´eriv´ees partielles du second ordre ‘a une fonction inconnue de trois variables ind´ependantes. Bulletin de la Soci´et´e Math´ematique de France. 39, 352-443. |
| [12] | Cartan, E., 1945. Les syst‘emes diff´erentiels ext´erieurs et leurs applications g´eom´etriques. Paris: Hermann. · Zbl 0063.00734 |
| [13] | Ceria, M., Mora, T., Roggero, M., 2015. Term-ordering free involutive bases. J. Symb. Comput. 68, 87-108. · Zbl 1311.13036 |
| [14] | Cox, D., Little, J., O’Shea, D., 2007. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. 3rd ed., 3rd Edition. New York, NY: Springer. · Zbl 1118.13001 |
| [15] | Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C., 1991. The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Appl. Math. 33 (1-3), 73-94. · Zbl 0747.13018 |
| [16] | Dub´e, T. W., 1990. The structure of polynomial ideals and Gr¨obner bases. SIAM J. Comput. 19 (4), 750-773. · Zbl 0697.68051 |
| [17] | Eisenbud, D., Goto, S., 1984. Linear free resolutions and minimal multiplicity. J. Algebra 88, 89-133. · Zbl 0531.13015 |
| [18] | Fr¨oberg, R., 1997. An introduction to Gr¨obner bases. Chichester: John Wiley & Sons. · Zbl 0997.13500 |
| [19] | Galligo, A., 1974. A propos du th´eor‘eme de preparation de Weierstrass. Fonctions de plusieurs Variables complexes, Sem. Francois Norguet, Oct. 1970 - Dec. 1973, Lect. Notes Math. 409, 543-579 (1974). · Zbl 0297.32003 |
| [20] | Galligo, A., 1979. Th´eor‘eme de division et stabilit´e en g´eom´etrie analytique locale. Ann. Inst. Fourier 29 (2), 107-184. · Zbl 0412.32011 |
| [21] | Giusti, M., 1984. Some effectivity problems in polynomial ideal theory. EUROSAM 84, Symbolic and algebraic computation, Proc. int. Symp., Cambridge/Engl. 1984, Lect. Notes Comput. Sci. 174, 159-171 (1984). · Zbl 0585.13010 |
| [22] | Greuel, G.-M., Pfister, G., 2007. A Singular introduction to commutative algebra. With contributions by Olaf Bachmann, Christoph Lossen and Hans Sch¨onemann. 2nd extended ed., 2nd Edition. Berlin: Springer. · Zbl 1133.13001 |
| [23] | Hartshorne, R., 1997. Algebraic geometry. 8rd printing. Graduate Texts in Mathematics, Springer-Verlag. |
| [24] | Hashemi, A., 2010. Strong Nœther position and stabilized regularities. Commun. Algebra 38 (2), 515-533. · Zbl 1193.13019 |
| [25] | Hashemi, A., Schweinfurter, M., Seiler, W. M., 2012. Quasi-stability versus genericity. In: Computer algebra in scientific computing. 14th international workshop, CASC 2012, Maribor, Slovenia, September 3-6, 2012. Proceedings. Berlin: Springer, pp. 172-184. · Zbl 1373.13028 |
| [26] | Hashemi, A., Schweinfurter, M., Seiler, W. M., 2018. Deterministic Genericity for Polynomial Ideals. J. Symb. Comput. 86, 20-50. · Zbl 1446.13021 |
| [27] | Hilbert, D., 1890. ¨Ueber die Theorie der algebraischen Formen. Math. Ann 36, 473-534. · JFM 22.0133.01 |
| [28] | Janet, M., 1927. Les syst‘emes d’´equations aux d´eriv´ees partielles. 55 p. Paris, Gauthier-Villars (Memorial des sciences mathematiques fasc. 21) (1927). |
| [29] | Kaplansky, I., 1974. Commutative rings, revised Edition. The University of Chicago Press, Chicago, Ill.-London. · Zbl 0296.13001 |
| [30] | Kehrein, A., Kreuzer, M., 2006. Computing border bases. J. Pure Appl. Algebra 205 (2), 279-295. · Zbl 1097.13036 |
| [31] | Kreuzer, M., Robbiano, L., 2005. Computational commutative algebra. II. Berlin: Springer. · Zbl 1090.13021 |
| [32] | Lazard, D., 1983. Gr¨obner bases, Gaussian elimination and resolution of systems of algebraic equations. Computer algebra, EUROCAL ’83, Proc. Conf., London 1983, Lect. Notes Comput. Sci. 162, 146-156 (1983). · Zbl 0539.13002 |
| [33] | Lejeune-Jalabert, M., 1984. Effectivit´e de calculs polynomiaux. Cours de D.E.A, Institute Fourier, Grenoble. |
| [34] | Lundqvist, S., 2010. Vector space bases associated to vanishing ideals of points. J. Pure Appl. Algebra 214 (4), 309-321. · Zbl 1194.13023 |
| [35] | Macaulay, F. S., 1994. The algebraic theory of modular systems. With a new introduction by Paul Roberts. Reprint of the 1916 orig., reprint of the 1916 orig. · Zbl 0802.13001 |
| [36] | Malgrange, B., 2003. Cartan involutiveness = Mumford regularity. In: Commutative algebra. Interactions with algebraic geometry. Proceedings of the international conference, Grenoble, France, July 9-13, 2001 and the special session at the joint international meeting of the American Mathematical Society and the Soci´et´e Math´ematique de France, Lyon, France, July 17-20, 2001. Providence, RI: American Mathematical Society (AMS), pp. 193-205. · Zbl 1062.58004 |
| [37] | Marinari, M. G., M¨oller, H. M., Mora, T., 1991. Gr¨obner bases of ideals given by dual bases. In:Proceedings of ISSAC’91. New York, NY: ACM Press, pp. 55-63. · Zbl 0925.13011 |
| [38] | Mayr, E. W., Ritscher, S., 2013. Dimension-dependent bounds for Gr¨obner bases of polynomial ideals. J. Symb. Comput. 49, 78-94. · Zbl 1258.13032 |
| [39] | M¨oller, H., Mora, F., 1984. Upper and lower bounds for the degree of Gr¨obner bases. EUROSAM 84, Symbolic and algebraic computation, Proc. int. Symp., Cambridge/Engl. 1984, Lect. Notes Comput. Sci. 174, 172-183 (1984). · Zbl 0564.68030 |
| [40] | M¨oller, H. M., Mora, F., 1986. New constructive methods in classical ideal theory. J. Algebra 100, 138-178. · Zbl 0621.13007 |
| [41] | M¨oller, H. M., Sauer, T., 2000. H-bases for polynomial interpolation and system solving. Adv. Comput. Math. 12 (4), 335-362. · Zbl 0943.65059 |
| [42] | Mora, T., 2005. Solving polynomial equation systems. II. Macaulay’s paradigm and Gr¨obner technology. Cambridge: Cambridge University Press. · Zbl 1161.13306 |
| [43] | Mora, T., 2016. Solving polynomial equation systems. Vol. IV. Buchberger theory and beyond. Cambridge: Cambridge University Press. · Zbl 1362.12001 |
| [44] | Mumford, D., 1966. Lectures on curves on an algebraic surface. Annals of Mathematics Studies 59. Princeton, N.J.: Princeton University Press. XI, 200 p. (1966). · Zbl 0187.42701 |
| [45] | Pe˜na, J. M., Sauer, T., 2007. Efficient polynomial reduction. Adv. Comput. Math. 26 (1-3), 323-336. · Zbl 1109.13024 |
| [46] | Sauer, T., 2001. Gr¨obner bases, H-bases and interpolation. Trans. Am. Math. Soc. 353 (6), 2293-2308. · Zbl 0967.65005 |
| [47] | Seiler, W. M., 2009. A combinatorial approach to involution and δ -regularity. I: Involutive bases in polynomial algebras of solvable type. Appl. Algebra Eng. Commun. Comput. 20 (3-4), 207-259. · Zbl 1175.13012 |
| [48] | Seiler, W. M., 2009. A combinatorial approach to involution and δ -regularity. II: Structure analysis of polynomial modules with Pommaret bases. Appl. Algebra Eng. Commun. Comput. 20 (3-4), 261-338. · Zbl 1175.13011 |
| [49] | Seiler, W. M., 2010. Involution. The formal theory of differential equations and its applications in computer algebra. Berlin: Springer. · Zbl 1205.35003 |
| [50] | Sharp, R. Y., 2000. Steps in commutative algebra. 2nd ed., 2nd Edition. Cambridge: Cambridge University Press. · Zbl 0969.13001 |
| [51] | Sombra, M., 1999. A sparse effective Nullstellensatz. Adv. Appl. Math. 22 (2), 271-295. · Zbl 0933.14001 |
| [52] | Spear, D. A., 1977. A constructive approach to commutative ring theory. In: ProDEGREE UPPER BOUNDS FOR H-BASES405 |
| [53] | Wiesinger-Widi, M., 2015. Gr¨obner bases and generalized Sylvester matrices. · Zbl 1305.68375 |
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.
