Computing the degree of regularity for a regular sequence spanning a zero-dimensional ideal is easy – the Macaulay bound is the answer we’re looking for. If the polynomial system does not meet these conditions, the problem is a little more intricate. Concretly: computing the degree of regularity for a polynomial system is generally as difficult as computing its Gröbner basis.

This might suggest that computing the degree of regularity from a Gröbner basis is easy. After all, we’ve done all the hard work already! Unfortunately, this is not generally the case, as the following example will make clear.

In this blog post, I will use “degree of regularity” and ”highest degree reached during computation of the Gröbner basis” interchangeably. While this is not true in general, the degrees are close enough for the argument below to be valid still.

Consider the system $\mathcal{F} = \{ x^2 y + 1, x y^2 \} \subseteq \mathbb{F}[x, y]$ for some finite field $\mathbb{F}$. Let’s start computing the Gröbner basis for degrevlex order using Buchberger’s algorithm:

$$\text{S-Poly}(x^2y + 1, xy^2) = \frac{x^2y^2}{x^2y}\cdot (x^2y + 1) – \frac{x^2y^2}{xy^2}\cdot xy^2 = x^2y^2 + y – x^2 y^2 = y.$$

Keeping track, we computed a polynomial of degree 4, even though the highest degree monomial didn’t make it into the end result. One more step and we’ve found the Gröbner basis:

$$\text{S-Poly}(x^2y + 1, y) = \frac{x^2y}{x^2y}\cdot (x^2y + 1) – \frac{x^2y}{y}\cdot y = x^2y + 1 – x^2y = 1.$$

Seems like $\mathcal{F}$ is inconsistent – the reduced Gröbner basis of $\mathcal{F}$ is $\{1\}$, meaning the variety of $\langle \mathcal{F} \rangle$ is empty. Good to know. The degree of regularity of $\mathcal{F}$ is 4, reached during computation of the first S-Polynomial.

Already it becomes apparent that computing the degree of regularity from this Gröbner basis is impossible. Let me drive home the point by considering $\mathcal{F}_a = \{x^a y + 1, xy^a\}$ for positive integer $a$. It is easy to see that the reduced Gröbner basis of $\mathcal{F}_a$ is $\{1\}$ for any $a$. However, the degree of the highest degree polynomial appearing during computation of said Gröbner basis – whether using Buchberger’s algorithm, F4, F5, or Mutant XL – is $2a$.

Identifying classes of polynomial systems for which the degree of regularity can easily be deduced from its Gröbner basis is an interesting question. Are consistent systems such a class? Consistent systems spanning a zero-dimensional ideal? Does regularity of the system play a role? The example above has only shown that it is impossible in general.