The F5 Criterion Revised

The purpose of this work is to generalize part of the theory behind Faugere\u27s F5 algorithm. This is one of the fastest known algorithms to compute a Gröbner basis of a polynomial ideal I generated by polynomials f1,…,fm. A major reason for this is what Faugere called the algorithm\u27s new criterion, and we call the F5 criterion : it provides a sufficient condition for a set of polynomialsGto be a Gröbner basis. However. the F5 algorithm is difficult to grasp, and there are unresolved questions regarding its termination. This paper introduces some new concepts that place the criterion in a more general setting:S-Gröbner bases and primitive S-irreducible polynomials. We use these to propose a new, simple algorithm based on a revised F5 criterion. The new concepts also enable us to remove various restrictions, such as proving termination without the requirement that f1,…,fm be a regular sequence. (C) 2011 Elsevier Ltd. All rights reserved