AN ALGORITHM FOR MINIMAL GENERATING SET OF PARAMETRIC HOMOGENEOUS POLYNOMIAL IDEALS
Abstract
We introduce comprehensive minimal generating systems (CMGS), a framework for computing minimal generating sets of homogeneous polynomial ideals with parametric coefficients, which is a non-trivial problem. While Schreyer’s syzygy theorem (1980) solved this problem for constant coefficients, the parametric case was recently addressed by the author’s MGSystem algorithm [9], which computes minimal generating sets for homogeneous parametric ideals forming Gr¨obner bases in the variables. In this paper, we extend these results to arbitrary homogeneous parametric polynomial ideals. Our approach combines completed Gr¨obner systems [6] with an extension of Schreyer’s theorem to partition the parameter space into regions where minimal generators are uniformly computed. The CMGS algorithm utilizes syzygy computations to systematically eliminate redundant generators, resulting in significant reductions in generating set sizes under parameter constraints. A Maple implementation demonstrates practical efficiency, with examples showing how parameter specializations simplify ideals. This work bridges a 40-year gap in computational algebra, offering theoretical advances (e.g., structural invariants of parametric ideals) and practical algorithms for applications in algebraic geometry, homological algebra, and symbolic computation.
Downloads
References
[1] T. Becker and V. Weispfenning. Gr¨obner bases: a computational approach to commutative algebra. In cooperation with Heinz Kredel. New York: Springer-Verlag, 1993. 1
[2] B. Buchberger. A criterion for detecting unnecessary reductions in the construction of Gr¨obner-bases. Symbolic and algebraic computation, EUROSAM ’79, int. Symp., Marseille 1979, Lect. Notes Comput. Sci. 72, 3-21 (1979)., 1979. 2
[3] B. Buchberger. 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, 2006. 2
[4] D. Cox, J. Little, and D. O’Shea. Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. 3rd ed. New York, NY: Springer, 3rd ed. edition, 2007. 1, 2
[5] D. A. Cox, J. Little, and D. O’Shea. Using algebraic geometry. 2nd ed. New York, NY: Springer, 2nd ed. edition, 2005. 1,2, 2.2, 2, 2.4, 4, 4
[6] M. Dehghani Darmian. Minimal Generating Sets for Parametric Polynomial Ideals. Journal of Algebraic Systems (JAS), Accepted, 2025. (document), 1
[7] M. Dehghani Darmian. Transformation Matrices in Gr¨obner Systems Computation. Submitted, 2025. (document), 1, 2, 3, 3
[8] M. Dehghani Darmian. Efficient Algorithm for Computing Inverse of Parametric Matrices. Scientific Annals of Computer Science, 34(1):1–22, 2024. 3
[9] M. Dehghani Darmian. Improvement of an Incremental Signature-Based Comprehensive Gr¨obner System Algorithm. Math.Comput.Sci., 18(12), 2024. 3
[10] M. Dehghani Darmian and A. Hashemi. Parametric FGLM algorithm. J. Symb. Comput., 82:38–56, 2017. 3, 3
[11] M. Dehghani Darmian and A. Hashemi. A Parametric F4 Algorithm. Iranian Journal of Mathematical Sciences and
Informatics, 19(1):117–133, 2024. 3
[12] J.-C. Faug`ere. A new efficient algorithm for computing Gr¨obner bases (F4). J. Pure Appl. Algebra, 139(1-3):61–88, 1999. 2
[13] J.-C. Faug`ere. A new efficient algorithm for computing Gr¨obner bases without reduction to zero (F5). In Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002, Lille, France, July 07–10, 2002., pages 75–83. New York, NY: ACM Press, 2002. 2
[14] S. Gao, Y. Guan, and F. Volny. A new incremental algorithm for computing Gr¨obner bases. In Proceedings of the 35th international symposium on symbolic and algebraic computation, ISSAC 2010, Munich, Germany, July 25–28, 2010, pages 13–19. New York, NY: Association for Computing Machinery (ACM), 2010. 2
[15] S. Gao, F. I. Volny, and M. Wang. A new framework for computing Gr¨obner bases. Math. Comput., 85(297):449–465, 2016. 2
[16] A. Hashemi, M. Dehghani Darmian, and M. Barkhordar. Gr¨obner systems conversion. Math. Comput. Sci.,11(1):61–77, 2017. 3, 3, 3
[17] A. Hashemi, M. Dehghani Darmian, and B. M.-Alizadeh. Applying Buchberger’s criteria on Montes’s DisPGB algorithm. Bull. Iran. Math. Soc., 38(3):715–724, 2012. 3
[18] A. Hashemi, B. M.-Alizadeh, and M. Dehghani Darmian. Minimal polynomial systems for parametric matrices. Linear Multilinear Algebra, 61(2):265–272, 2013. 3
[19] A. Hashemi, B. M.-Alizadeh, and M. Dehghani Darmian. Computing comprehensive Gr¨obner systems: a comparison of two methods. Comput. Sci. J. Mold., 25(3(75)):278–302, 2017. 3
[20] M. Kalkbrener. On the complexity of Gr¨obner bases conversion. J. Symb. Comput., 28(1-2):265–273, 1999. 3
[21] D. Kapur, Y. Sun, and D. Wang. A new algorithm for computing comprehensive Gr¨obner systems. In Proceedings of the 35th international symposium on symbolic and algebraic computation, ISSAC 2010, Munich, Germany, July 25–28, 2010, pages 29–36. New York, NY: Association for Computing Machinery (ACM), 2010. 3
[22] D. Lazard. 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)., 1983. 2
[23] M. Manubens and A. Montes. Improving the DisPGB algorithm using the discriminant ideal. J. Symb. Comput.,
41(11):1245–1263, 2006. 3, 3
[24] M. Manubens and A. Montes. Minimal canonical comprehensive Gr¨obner systems. J. Symb. Comput., 44(5):463–478, 2009. 3
[25] A. Montes. A new algorithm for discussing Gr¨obner bases with parameters. J. Symb. Comput., 33(2):183–208, 2002. 3, 3
[26] A. Montes and J. Castro. Solving the load flow problem using the Gr¨obner basis. SIGSAM Bull., 29(1):1–13, 1995. 3
[27] I. Peeva and M. Stillman. Open Problems on Syzygies and Hilbert Functions. Journal of Commutative Algebra, 1(1):159– 195, 2009. 2
[28] F.-O. Schreyer. Die berechnung von syzygien mit dem verallgemeinerten weierstraßschen divisionssatz. Diplom Thesis, University of Hamburg, Germany, 1980. 1, 2
[29] A. Suzuki and Y. Sato. A simple algorithm to compute comprehensive Gr¨obner bases using Gr¨obner bases. In In Proceedings of the 2006 international symposium on symbolic and algebraic computation, ISSAC 06, Genova, Italy, July 9–12, 2006, pages 326–331. New York, NY: ACM Press, 2006. 3
[30] V. Weispfenning. Comprehensive Gr¨obner bases. J. Symb. Comput., 14(1):1–29, 1992. 3, 3
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Dr. Mahdi Dehghani Darmian
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
