A signature-based algorithm for computing Gröbner bases over principal ideal domains (Q782709): Difference between revisions

[\textit{J.-C. Faugère}, in: Proceedings of the 2002 international symposium on symbolic and algebraic computation, ISSAC 2002, Lille, France, July 07--10, 2002. New York, NY: ACM Press. 75--83 (2002; Zbl 1072.68664)] introduced \(F_5\), the first signature-based algorithm to compute Gröbner bases of ideals of polynomial rings over a field. The algorithm achieved fame in part for quickly computing Gröbner bases that previously had been intractable, but even more appealing was its new criterion to detect a kind of useless computation called ``zero reduction''. Most Gröbner basis algorithms until then detected only a small number of these reductions, with the notable exception of the syzygy-based algorithm that \textit{H. M. Möller} et al. described in [in: International symposium on Symbolic and algebraic computation 92. ISSAC 92. Berkeley, CA, USA, July 27--29, 1992. Baltimore, MD: ACM Press. 320--328 (1992; Zbl 0925.13010)]. By contrast, Faugère proved that the \(F_5\) criterion detected all zero reductions if the input was a regular sequence, and was highly effective even when the input was not regular. Since then, significant effort has gone into both understanding and generalizing the algorithm. This article by Francis and Verron focuses mainly on the second: extending signature-based algorithms to the ideal of a polynomial ring over a commutative integral domain. It re-presents Möller's algorithm to compute a weak Gröbner basis for an ideal in a polynomial ring over a Noetherian integral domain (Algorithm 1) and generalizes it to a new algorithm that applies signature-based criteria (Algorithm 3). The authors prove correctness and termination in the setting of principal ideal domains. They also introduce a distinction between ``singular'' and ``1-singular'' \(\mathfrak s\)-reductions, which generalize a previous, related notion of ``signature-redundant'' polynomials. The authors pay careful attention to generalizing these ideas for the more general situation, and point out that the algorithm appears to extend to more general settings. The article is clearly written and well organized. Two short, effective examples help illuminate some concepts for those less familiar with computation of Gröbner bases outside a field. The authors have created a toy implementation in Magma, with the code publicly available on GitHub. The paper provides a hyperlink to this repository, and includes a direct link to a page that elaborates a fully computed example.