# zbMATH — the first resource for mathematics

Efficient Gröbner bases computation over principal ideal rings. (English) Zbl 1451.13078
In the paper under review, the authors present new techniques for improving the computation of strong Gröbner bases over a principal ideal ring. Let $$R$$ be a principal ideal ring; i.e. a unital commutative ring such that every ideal of $$R$$ is principal. Let $$P=R[x_1,\ldots ,x_n]$$ be the polynomial ring in $$n$$ variables over $$R$$. Let us fix a monomial ordering $$\prec$$ on $$P$$. For any polynomial $$f\in P$$, we can define the leading term of $$f$$, denoted by $$lt(f)$$, as the greatest term (including the coefficient) appearing in $$f$$. For a given ideal $$I\subset R$$, a finite set $$G\subset I$$ is called a strong Gröbner basis of $$I$$ if for any polynomial $$0\ne f\in I$$, there exists $$g\in G$$ such that $$lt(f)\mid lt(g)$$. In order to compute strong Gröbner bases, in addition to S-polynomials proposed by Buchberger, on needs to consider GCD-polynomials and A-polynomials. Based on this discussion, we can describe a variant of Buchberger’s algorithm to construct strong Gröbner bases.
To compute a strong Gröbner basis for an ideal of $$I\subset P$$, the authors apply a kind of modular method by passing to quotient rings. More precisely, they choose an element $$n\in R$$, construct a Gröbner basis of the ideal $$\bar{I}\subset (R/nR)[x]$$ and from this basis a Gröbner basis for the ideal $$I$$ is reconstructed.
This algorithm has been implemented in the Julia package for the special case of $$R=\mathbb{Z}$$. Running standard benchmarks shows the efficiency of the algorithm.
##### MSC:
 13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) 68W30 Symbolic computation and algebraic computation
##### Keywords:
Gröbner bases; principal ideal rings
##### Software:
Julia ; SINGULAR; Nemo; Magma; Hecke
Full Text:
##### References:
  Adams, W. W.; Loustaunau, P., An Introduction to Gröbner Bases, Graduate Studies in Mathematics (1994), AMS · Zbl 0803.13015  Arnold, E. A., Modular algorithms for computing Gröbner bases, J. Symb. Comput., 35, 4, 403-419 (2003) · Zbl 1046.13018  Bach, E.; Driscoll, J.; Shallit, J., Factor refinement, J. Algorithms, 15, 2, 199-222 (1993) · Zbl 0784.11058  Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039  Buchberger, B., Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (1965), University of Innsbruck, Ph.D. thesis · Zbl 1245.13020  Buchberger, B., Gröbner-Bases: An Algorithmic Method in Polynomial Ideal Theory (1985), Reidel Publishing Company: Reidel Publishing Company Dordrecht - Boston - Lancaster · Zbl 0587.13009  Buchberger, B., An algorithm for finding the basis elements of the residue class ring of zero dimensional polynomial ideal, J. Symb. Comput., 41, 3-4, 475-511 (2006) · Zbl 1158.01307  Decker, W.; Greuel, G.-M.; Pfister, G.; Schönemann, H., Singular 4-1-2 — a computer algebra system for polynomial computations (2019)  Eder, C. (2019), gb  Eder, C.; Hofmann, T. (2019), gb  Eder, C.; Pfister, G.; Popescu, A., On signature-based Gröbner bases over Euclidean rings, (ISSAC 2017: Proceedings of the 2011 International Symposium on Symbolic and Algebraic Computation (2017)), 141-148 · Zbl 1458.13032  Eder, C.; Pfister, G.; Popescu, A., Standard bases over Euclidean domains (2018)  Faugère, J.-C., A new efficient algorithm for computing Gröbner bases (F4), J. Pure Appl. Algebra, 139, 1-3, 61-88 (June 1999)  Fieker, C.; Hart, W.; Hofmann, T.; Johansson, F., Nemo/Hecke: computer algebra and number theory packages for the Julia programming language, (ISSAC’17—Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation (2017), ACM: ACM New York), 157-164 · Zbl 1457.68325  Fieker, C.; Hofmann, T., Computing in quotients of rings of integers, LMS J. Comput. Math., 17, suppl. A, 349-365 (2014) · Zbl 1369.11104  Francis, M.; Verron, T., Signature-based Möller’s algorithm for strong Gröbner bases over PIDs (2019), CoRR  von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (2003), Cambridge University Press: Cambridge University Press Cambridge, England · Zbl 1055.68168  Grauert, H., Über die Deformation isolierter Singularitäten analytischer Mengen, Invent. Math., 15, 3, 171-198 (1972) · Zbl 0237.32011  Hashemi, A.; Alvandi, P., Applying Buchberger’s criteria for computing Gröbner bases over finite-chain rings, J. Algebra Appl., 12, 7, Article 1350034 pp. (2013) · Zbl 1281.13017  Hironaka, H., Resolution of singularities of an algebraic variety over a field of characteristic zero: I, Ann. Math., 79, 1, 109-203 (1964) · Zbl 0122.38603  Hironaka, H., Resolution of singularities of an algebraic variety over a field of characteristic zero: II, Ann. Math., 79, 2, 205-326 (1964) · Zbl 1420.14031  Kandri-Rody, A.; Kapur, D., Algorithms for computing Gröbner bases of polynomial ideals over various Euclidean rings, (Fitch, J., EUROSAM 84 (1984), Springer: Springer Berlin, Heidelberg), 195-206 · Zbl 0564.13001  Kandri-Rody, A.; Kapur, D., Computing a Gröbner basis of a polynomial ideal over a Euclidean domain, J. Symb. Comput., 6, 1, 37-57 (1988) · Zbl 0658.13016  Kapur, D.; Cai, Y., An algorithm for computing a Gröbner basis of a polynomial ideal over a ring with zero divisors, Math. Comput. Sci., 2, 601-634 (2009) · Zbl 1205.13032  Lichtblau, D., Effective computation of strong Gröbner bases over Euclidean domains, Ill. J. Math., 56, 1, 177-194 (2012) · Zbl 1275.13021  Möller, H. M., On the construction of Gröbner bases using syzygies, J. Symb. Comput., 6, 2, 345-359 (1988) · Zbl 0695.13003  Norton, G. H.; Sălăgean, A., Strong Gröbner bases and cyclic codes over a finite-chain ring, (International Workshop on Coding and Cryptography. International Workshop on Coding and Cryptography, Paris, 2001. International Workshop on Coding and Cryptography. International Workshop on Coding and Cryptography, Paris, 2001, Electron. Notes Discrete Math., vol. 6 (2001), Elsevier Sci. B. V.: Elsevier Sci. B. V. Amsterdam), 11  Norton, G. H.; Sǎlǎgean, A., Strong Gröbner bases for polynomials over a principal ideal ring, Bull. Aust. Math. Soc., 64, 3, 505-528 (2001) · Zbl 1046.13019  Pauer, F., On lucky ideals for Gröbner basis computations, J. Symb. Comput., 14, 5, 471-482 (1992) · Zbl 0776.13014  Pauer, F., Gröbner bases with coefficients in rings, J. Symb. Comput., 42, 11, 1003-1011 (2007) · Zbl 1127.13024  Pauer, F.; Pfeifhofer, M., The theory of Gröbner bases, Enseign. Math. (2), 34, 3-4, 215-232 (1988) · Zbl 0702.13019  Popescu, A., Signature Standard Bases over Principal Ideal Rings (2016), Technische Universität Kaiserslautern, Ph.D. thesis  Storjohann, A.; Mulders, T., Fast algorithms for linear algebra modulo N, (Algorithms—ESA ’98. Algorithms—ESA ’98, Venice. Algorithms—ESA ’98. Algorithms—ESA ’98, Venice, Lecture Notes in Comput. Sci., vol. 1461 (1998), Springer: Springer Berlin), 139-150 · Zbl 0929.65019  Trinks, W., Über B. Buchbergers Verfahren, Systeme algebraischer Gleichungen zu lösen, J. Number Theory, 10, 4, 475-488 (1978) · Zbl 0404.13004  Wienand, O., Algorithms for Symbolic Computation and Their Applications - Standard Bases over Rings and Rank Tests in Statistics (2011), Technische Universität Kaiserslautern, Ph.D. thesis
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.