Analysis of computing Gröbner bases and Gröbner degenerations via theory of signatures

The history of computing Gröbner bases began with the Buchberger’s algorithm, which selects polynomials by running a multivariate division algorithm and adding them to the set of generators until it satisfies the Buchberger’s criterion [Buc65]. The ideas of the Buchberger’s algorithm are still the basis of Gröbner basis computation algorithms, and most algorithms gradually approximate the input polynomial system to a Gröbner basis by iteratively computing the S-polynomials generated by the cancellations of the leading terms. A practical problem with this method is that the artifacts produced by the procedure are unpredictable for the choice of generators, term order, and so on. This implies a computational difficulty in applications of the Gröbner basis theory.

Our motivations in this paper are:

• •

  to obtain a quantitative cost function of a tuple of polynomials $F$ that predicts the complexity of the computation of a Gröbner basis from $F$,

• •

  to answer the question of whether the S-polynomial computation is always necessary to determine a Gröbner basis, and

• •

  to represent the computation of Gröbner bases in the geometrical context,

for the construction of new efficient algorithms intrinsically different from Buchberger’s algorithm, such as Newton’s method, midpoint method and so on, in the future. To realize it, we give an algebraic or geometric analysis of the syzygies of $F$ in the computational aspects via the theory of the signatures. Then we obtain an object $\mathrm{Gobs(\mathit{F})}{}$ that corresponds to the computation of a Gröbner basis from $F$ and a Gröbner degeneration of $F$. And we prove that remainders of divisions of S-polynomials must be determined to obtain homogeneous Gröbner bases with respect to graded orders.

Let $R=K[x_{1},\ldots,x_{n}]$ be the polynomial ring with a term order $<$ over a field $K$, $F=(f_{1},f_{2},\ldots,f_{m})$ a tuple of elements in $R$, and $I$ the ideal generated by $F$. By $R^{m}=\oplus_{i=1}^{m}Re_{i}$ we denote the free $R$-module with the basis $(e_{1},e_{2},\ldots,e_{m})$ corresponding to $F$. Assume that $R^{m}$ equips a term order $\prec$. The signature $S(f)$ of a non-zero element $f$ in $I$ is defined as

where $\bar{u}$ is the image of $u$ under the canonical surjection $R^{m}\rightarrow I\rightarrow 0$ (see also Definition 3.1, Proposition 3.2). Faugère first introduced the concept of signatures in his $F_{5}$ algorithm for efficient computation of Gröbner bases by avoiding reductions to zero [Fau02]. Several researchers proposed many variants of the $F_{5}$ algorithm, nowadays called signature based algorithms. Arri-Perry introduced another definition of the signatures to give a proof of the termination and correctness of the $F_{5}$ algorithm or signature based algorithms for any input [AP11]. It is difficult to determine the signature for a general polynomial without a Gröbner basis of $I$ or the syzygy module $\mathrm{Syz}(F)$. Vaccon-Yokoyama defined the “guessed” signatures of the S-polynomials as an alternative object of signatures [VY17]. The guessed signatures are only determined from the computational history of the running instance. Then they made a simple implementation of a signature based algorithm. In this paper we introduce a definition of guessed signatures that is different from [VY17]. We define the guessed signatures for pairs $(x^{\alpha}e_{i},x^{\beta}e_{j})$ of monomials in $R^{m}$ such that $x^{\alpha}\operatorname{LM}(f_{i})=x^{\beta}\operatorname{LM}(f_{j})\ (i<j)$ as the monomials $x^{\beta}e_{j}$ in the second components (Definition 3.3).

If we attach the Schreyer order on $R^{m}$ (Definition 2.2), the guessed signature of a pair $(x^{\alpha}e_{i},x^{\beta}e_{j})$ is the leading monomial of $x^{\alpha}e_{i}-x^{\beta}e_{j}$. In fact, the guessed signature of a pair $(x^{\alpha}e_{i},x^{\beta}e_{j})$ is not always the signature of the S-polynomial $\frac{1}{\operatorname{LC}(f_{i})}x^{\alpha}f_{i}-\frac{1}{\operatorname{LC}(f_{j})}x^{\beta}f_{j}$. It partly depends on whether the reduction of the S-polynomial is zero or not. From this point of view, in this paper we suppose that the difference between the set of guessed signatures and the set of signatures might predict the behavior to computations of Gröbner bases from $F$, and then we focus on this difference. From the Schreyer’s theorem, the set of guessed signatures is the set of the leading monomials $\operatorname{LM}(\mathrm{Syz}(\operatorname{LM}(F)))$ of the syzygy module of the tuple $\operatorname{LM}(F)=(\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m}))$ [Eis95, Theorem 15.10]. Then our main target is the residue module

From now on we always attach the Schreyer order on $R^{m}$. Our contributions in this paper are the following.

• (A)

  We give a criterion for Gröbner bases: $F$ is a Gröbner basis if and only if $\mathrm{Gobs(\mathit{F})}{}=0$ (Theorem 3.5).

• (B)

  We show that for any homogeneous Gröbner basis $G$ of $I$ including $F$ with respect to a graded term order $<$, $G$ contains an element $g$ such that $\operatorname{LM}(g)=\operatorname{LM}(r)$, where $r$ is the remainder of a reduction of an S-polynomial. If $G$ satisfies some common condition, then $g=cr\ (\exists\,c\in K)$ (Corollary 4.4).

• (C)

  We give examples of transitions of $\mathrm{Gobs(\mathit{F})}{}$ in a signature based algorithm (Section 5).

• (D)

  We find a closed subscheme $X$ in $\operatorname{Spec}R\times_{K}\mathbb{A}_{K}^{1}$ and direct summand $N(F)$ of $\mathrm{Gobs(\mathit{F})}{}$ such that $X$ is a flat deformation of $\operatorname{Spec}R/I$ to $\operatorname{Spec}R/\langle\operatorname{LM}(F)\rangle$ over $\mathbb{A}_{K}^{1}$ if and only if $N(F)=0$ (Theorem 6.6, Lemma 6.8).

For (A), a key lemma is the following (see also Lemma 3.7).

(B) is based on Lemma 1.1. Let us consider about finding an element of the leading monomial not in $\langle\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m})\rangle$. Let $f_{m+1}$ be an element of $I$ such that $\operatorname{LM}(f_{m+1})\not\in\langle\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m})\rangle$ and put $F^{\prime}=(f_{1},f_{2},\ldots,f_{m},f_{m+1})$. Assume that $f_{m+1}=\bar{u}$ for an element $u$ in $R^{m}$ and $\operatorname{LM}(u)=S(f)$. By Lemma 1.1, the equivalent class of $S(f_{m+1})$ in $\mathrm{Gobs(\mathit{F})}{}$ is not zero. On the other hand, since $u-e_{m+1}\in\mathrm{Syz}(F^{\prime})$ and $\operatorname{LM}(u-e_{m+1})=\operatorname{LM}(u)$ (see Lemma 3.7), we can show that the equivalent class of $S(f_{m+1})$ in $\mathrm{Gobs(\mathit{F}^{\prime})}$ is zero. Then one may interpret that finding an element $f_{m+1}$ that the leading monomial not in $\langle\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m})\rangle$ is vanishing a non-zero element of $\mathrm{Gobs(\mathit{F})}{}$. If $F$ consists of homogeneous elements and the term order $<$ on $R$ is graded lexicographic order or graded reverse lexicographic order, one may consider that the signature $S(f)$ is an index of the computational cost of representing $f$ by $F$, since degrees are a factor of the complexity of computing polynomials [MM84, Dub90, Giu05, BFSY05]. Therefore a naive idea to compute Gröbner bases efficiently is to choose polynomials of small signatures. In fact, several signature based algorithms follow this idea [AP11, VY17, Sak20] (see also Algorithm 1). Then we identify the polynomials of the signature that is smallest in $\mathrm{Gobs(\mathit{F})}{}$.

Let us assume again that $F$ consists of homogeneous elements and the term order $<$ on $R$ is graded lexicographic order or graded reverse lexicographic order. What would happen if we choose a homogeneous polynomial $f_{m+1}$ that satisfies

In fact, it will happen that

(Theorem 4.3). Namely, $s$ do not vanish in $\mathrm{Gobs(\mathit{F}\cup\{\mathit{f}_{m+1}\})}$ and then $F\cup\{f_{m+1}\}$ can not be a Gröbner basis. Therefore we obtain the following theorem that gives the necessity of the S-polynomial computation.

About (C), as mentioned above, some signature based algorithms can be intuitively thought of as methods that attempt to reduce the size of $\mathrm{Gobs(\mathit{F})}{}$ by annihilating the smallest elements. However, in Section 5, we observe examples of transitions of $\mathrm{Gobs(\mathit{F})}{}$ in an implementation of a signature based algorithm, and we find examples that the sequence of $\mathrm{Gobs(\mathit{F})}{}$ does not monotonically go to the zero-module in the procedure. On the other hand, observing such examples leads to the conjecture that, in some cases, the first Betti number of $\mathrm{Gobs(\mathit{F})}{}$ represents the phase of the monomial ideal generated by $\operatorname{LM}(F)$. More precisely, some examples satisfy the statement that if the first Betti number increases in a step, then the new leading monomial found in that step divides another leading monomial of the generators (Example 5.1, Example 5.2, Example 5.4). However, the above statement is not true in Example 5.3. Furthermore, in Example 5.3, $\mathrm{Gobs(\mathit{F})}{}$ is generated by a single equivalent class for the input $F$, nevertheless the instance does not terminate by a single step. We still do not know what is going on in the background of all this.

About (D), we show that $\mathrm{Gobs(\mathit{F})}{}$ contains flatness obstructions of a family introduced from $F$ in the context of Gröbner degenerations. Then we call $\mathrm{Gobs(\mathit{F})}{}$ the module of Gröbnerness obstructions of $F$ in this paper. Let us recall Gröbner degenerations. We call a closed subscheme $X$ in $\operatorname{Spec}R\times_{K}\operatorname{Spec}K[t]$ a Gröbner degeneration of $\operatorname{Spec}R/I$ if the projection $X\rightarrow\operatorname{Spec}K[t]$ is flat, generic fibers $X_{t}$ of the projection over $t\neq 0$ are isomorphic to $\operatorname{Spec}R/I$ and the special fiber $X_{0}$ at $t=0$ is isomorphic to $\operatorname{Spec}R/\operatorname{in}_{<}(I)$. There exists a Gröbner degeneration constructed from a weighting on variables [Bay82, Eis95]. Gröbner degenerations are used in studies of degenerations of varieties, homological invariants, Hilbert schemes and so on [Har66, KM05, LR11, CV20, Kam22]. Our main theorem about the relationship between $\mathrm{Gobs(\mathit{F})}{}$ and Gröbner degenerations is the following.

Let $K$ be a field. Let $R=K[x_{1},\ldots,x_{n}]$ be the polynomial ring over $K$ in $n$ variables attached a term order $<$. Here a term order means a total order $<$ of monomials in $R$ such that $1<m$ for any monomial $m\neq 1$ and $m<n$ implies $ml<nl$ for any monomials $m,n,l$. We say a term order $<$ is graded if $m<n$ for any monomials $m,n$ such that $\deg m<\deg n$ for the ordinal total degree of $R$. We use the following notation:

• •

  $\langle A\rangle$: the ideal generated by $A$ in $R$,

• •

  $\operatorname{LM}(f)$: the leading monomial of $f$,

• •

  $\operatorname{LC}(f)$: the leading coefficient of $f$,

• •

  $\operatorname{LT}(f)=\operatorname{LC}(f)\operatorname{LM}(f)$: the leading term of $f$,

• •

  $x^{\alpha}=x_{1}^{\alpha_{1}}x_{2}^{\alpha_{2}}\cdots x_{n}^{\alpha_{n}}$ for a vector $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{n})$.

We always consider a fixed tuple of polynomials $F=(f_{1},\ldots,f_{m})$ such that $f_{i}\neq 0\ (i=1,\ldots,m)$ unless otherwise noted.

In this paper, a division means a reduction by $F$ such that the remainder is $0$ or has no terms in $\langle\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m})\rangle$.

Let $I=\langle F\rangle$ be the ideal generated by $F$ in $R$. We call the ideal $\langle\operatorname{LM}(f)\mid f\in I\setminus\{0\}\rangle$ the initial ideal of $I$ and denote it by $\operatorname{in}_{<}(I)$. We say $F$ is a Gröbner basis if the initial ideal $\operatorname{in}_{<}(I)$ is generated by the tuple $\operatorname{LM}(F)=(\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m}))$. For the elementary of Gröbner bases, see [Eis95, Section 15].

Let $R^{m}=\oplus_{i=1}^{m}Re_{i}$ be the free $R$-module of rank $m$ with the basis $(e_{1},\ldots,e_{m})$. A monomial in $R^{m}$ is an element of the form $x^{\alpha}e_{i}$. In this paper, we always attach the following order on $R^{m}$.

Let $u$ be a non-zero element in $R^{m}$. The leading monomial of $u$ is the largest monomial with non-zero coefficient occurring in $u$. We define the leading coefficient and leading term as the same. We use the following notation:

• •

  $\operatorname{LM}(u)$: the leading monomial of $u$,

• •

  $\operatorname{LC}(u)$: the leading coefficient of $u$,

• •

  $\operatorname{LT}(u)=\operatorname{LC}(u)\operatorname{LM}(u)$: the leading term of $u$,

• •

  $\operatorname{LM}(M)=\{\operatorname{LM}(u)\mid u\in M\}$ for a subset $M$ in $R^{m}$,

• •

  $\langle N\rangle$: the $R$-submodule generated by a subset $N$ in $R^{m}$.

Let $M$ be an $R$-submodule in $R^{m}$. The initial module $\operatorname{in}_{\prec}(M)$ of $M$ is the $R$-submodule in $R^{m}$ generated by $\operatorname{LM}(M)$. A set of generators $V$ of $M$ is a Gröbner basis of $M$ if the initial module $\operatorname{in}_{\prec}(M)$ is generated by $\operatorname{LM}(V)$.

Let us define the syzygies.

In general, generators of the syzygy module $\mathrm{Syz}(F)$ depend on $F$ and need precise computation to determine. On the other hand, generators of the syzygy module $\mathrm{Syz}(\operatorname{LM}(F))$ is theoretically determined with an explicit form by the Schreyer’s theorem.

We recall the definition of the signatures given in [Fau02, AP11].

As easiest example of signatures, one may hope that $S(f_{i})=e_{i}$. However, it is wrong in general. For example, assume $F=(f_{1},f_{2},f_{3})$, $f_{3}=f_{1}+f_{2}$ and $\operatorname{LM}(f_{1})<\operatorname{LM}(f_{2})$, then the signature of $f_{3}$ is not $e_{3}$. Indeed, put $u=e_{1}+e_{2}$. We have $\bar{u}=f_{3}$ and $\operatorname{LM}(u)=e_{2}$. Thus the signature of $f_{3}$ is less than or equal to $e_{2}$. Since we attach the Schreyer order on $R^{m}$, we have $e_{2}<e_{3}$. Therefore we obtain $S(f_{3})<e_{3}$. Note that, in general, we need a Gröbner basis of $\mathrm{Syz}(F)$ to determine the signature $S(f)$ of given polynomial $f$.

As a more reasonable object than the signatures, we introduce the guessed signatures.

Since it holds that

one may guess that the signature of the S-polynomial is $x^{\delta}e_{\ell}$. This is the reason why we call $x^{\delta}e_{\ell}$ the “guessed” signature. In fact, the equality $S(\mathrm{Spoly}(p))=\hat{S}(p)$ is a non-trivial condition to determine if $F$ is a Gröbner basis or not.

Here we note the mean of the condition (e). Let $u=\sum_{\alpha,i}c_{\alpha,i}x^{\alpha}e_{i}$ be an element of $R^{m}$ such that $\overline{u}=f$ and $\operatorname{LM}(u)=S(f)$. Assume that $S(f)=x^{\beta}e_{j}$ and put $x^{\xi}=\operatorname{LM}\left(\overline{S(f)}\right)=x^{\beta}\operatorname{LM}(f_{j})$. Then by definition of the Schreyer order we have $x^{\xi}=\max\{x^{\alpha}\operatorname{LM}(f_{i})\mid c_{\alpha,i}\neq 0\}$. We divide $f$ into the following two parts:

Therefore the inequality $\operatorname{LM}\left(\overline{S(f)}\right)\succeq\operatorname{LM}(f)$ always holds, and we have $\operatorname{LM}(f)\in\langle\operatorname{LM}(f_{1}),\ldots,\operatorname{LM}(f_{m})\rangle$ if the equality $\operatorname{LM}\left(\overline{S(f)}\right)=\operatorname{LM}(f)$ holds.

We proof Theorem 3.5 after introducing some lemmas we need.