Generic Gröbner basis of a parametric ideal and its application to a comprehensive Gröbner system

We consider a classical problem regarding the relationship between a parametric ideal and its generic Gröbner basis, and introduce a new algorithm for computing comprehensive Gröbner systems as an application of the answer of the problem.

Let \(t=\{t_1,\ldots , t_m\}\) and \(x=\{x_1,\ldots ,x_n\}\) be sets of variables such that \(x \cap t\ne \emptyset\), K a field with characteristic zero and \(\overline{K}\) an algebraic closure field of K. Let K[t][x] be a polynomial ring with coefficients in the polynomial ring K[t] and K(t)[x] a polynomial ring with coefficients in the field K(t) of rational functions. For \(\bar{t} \in \overline{K}^m\), let \(\sigma _{\bar{t}}\) be the canonical specialization homomorphism \(K[t][x] \rightarrow \overline{K}[x]\) (or \(K[t] \rightarrow \overline{K}\)) that substitutes t by \(\bar{t}\) in \(h(t,x) \in K[t][x]\). Further, since for a subset \(F \subset K[t][x]\), the ideal \(\langle F \rangle\) in K[t][x] can be regarded as an ideal in K(t)[x], the reduced Gröbner basis G of \(\langle F \rangle\), w.r.t. a given term order \(\prec\) on x, can be computed by utilizing Buchberger algorithm. In general, the set G is called the “generic” reduced Gröbner basis of \(\langle F \rangle\) w.r.t. \(\prec\). The generic reduced Gröbner basis has often been used to analyze the ideal \(\langle F \rangle\) in K[t][x] because it is well-known that for a random point \(\bar{t} \in \overline{K}^m\), \(\sigma _{\bar{t}}(G)\) becomes the reduced Gröbner basis of \(\langle \sigma _{\bar{t}}(F)\rangle\) w.r.t. \(\prec\) in \(\overline{K}[x]\) with high probability where \(\sigma _{\bar{t}}(G)=\{\sigma _{\bar{t}}(g)| g\in G\}\) and \(F=\{\sigma _{\bar{t}}(f)| f \in F\}\). However, it is also well-known that there is a possibility that, for some \(\bar{t} \in \overline{K}^m\), \(\sigma _{\bar{t}}(G)\) is not a Gröbner basis of \(\langle \sigma _{\bar{t}}(F)\rangle\) w.r.t. \(\prec\) in \(\overline{K}[x]\) which gives rise to the following classical problem.

Problem 1

What is a parameter space \({{\,\mathrm{\mathbb {A}}\,}}\subset \overline{K}^m\), for the parameters t, that satisfies “for all \(\bar{t} \in {{\,\mathrm{\mathbb {A}}\,}}\), \(\sigma _{\bar{t}}(G)\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{t}}(F) \rangle\) w.r.t. \(\prec\) in \(\overline{K}[x]\)”?

In the first part of this paper, we consider the problem and introduce the answer. In the second part, we introduce a new algorithm for computing comprehensive Gröbner systems as an application of the answer.

The concepts of comprehensive Gröbner bases and comprehensive Gröbner systems were introduced by Weispfenning [18] as a special basis of a parametric polynomial system and have been regarded as one of important tools to study parametric systems. Since then, several effective algorithms for computing comprehensive Gröbner bases (or systems) have been published (for instance, see [5, 6, 8,9,10,11, 13, 16, 19, 20]). Especially, the algorithms, introduced by Kapur-Sun-Wang [5, 6] are effective in execution timings, and provide nice outputs.

We show that the answer to Problem 1 allows us to make a new algorithm for computing comprehensive Gröbner systems.

We implement the proposed algorithm and Kapur-Sun-Wang’s algorithm in the computer algebra system Risa/Asir [15] and experiment with a number of examples. We compare its performance (execution timings) with Kapur-Sun-Wang’s algorithm for computing comprehensive Gröbner systems.

This paper is organized as follows. In Sect. 2, we briefly review the results of Kapur-Sun-Wang [5, 6] and Nabeshima [13], that are stability conditions of a Gröbner basis. Sect. 3 is the discussion of Problem 1, and presents new stability conditions. Section 4 introduces the new algorithm for computing comprehensive Gröbner systems and results of several benchmark tests.

Here we briefly recall notation and some basics that will be used in this paper. We refer the reader to [5,6,7, 12, 13].

Symbols \({ Term}(t)\), \({ Term}(x)\) and \({ Term}(t,x)\) mean the set of terms of t, the set of terms of x and the set of terms of \(t\cup x\), respectively. Fix a term order \(\prec\) on \({ Term}(x)\) and let \(f \in R[x]\). Then \({{\,\textrm{lt}\,}}(f), {{\,\textrm{lm}\,}}(f)\) and \({{\,\textrm{lc}\,}}(f)\) denote the leading term, leading monomial and leading coefficient of f i.e. \({{\,\textrm{lm}\,}}(f)={{\,\textrm{lc}\,}}(f){{\,\textrm{lt}\,}}(f)\), where R is K, K(t) or K[t]. For \(F \subset R[x]\) and \(f_1,\ldots ,f_\nu \in R[x]\), \({{\,\textrm{lt}\,}}(F)=\{{{\,\textrm{lt}\,}}(f) | f \in F\}\) and \(\langle f_1,\ldots , f_\nu \rangle = \{\sum _{i=1}^\nu h_if_i | h_1,\ldots , h_\nu \in R[x]\}\).

The set of natural numbers \({{\,\mathrm{\mathbb {N}}\,}}\) includes zero, and \({{\,\mathrm{\mathbb {C}}\,}}\) is the field of complex numbers.

Definition 1

(block term order) Let \(\prec _t\) and \(\prec _x\) be term orders on \({ Term}(t)\) and \({ Term}(x)\), respectively, and \(t^{\alpha _1}, t^{\alpha _2} \in { Term}(t)\), \(x^{\beta _1}, x^{\beta _2} \in { Term}(x)\) where \(\alpha _1, \alpha _2 \in {{\,\mathrm{\mathbb {N}}\,}}^m\) and \(\beta _1,\beta _2 \in {{\,\mathrm{\mathbb {N}}\,}}^n\). Then, a term order \(\prec _{t,x}\) on Term(t, x) is defined as follows:

The term order \(\prec _{t,x}\) is called a block term order on Term(t, x), and is written as \(\prec _{t,x}:=(\prec _t,\prec _x)\).

Definition 2

(Gröbner basis in K[t][x]) Fix a term order \(\prec _x\) on \({ Term}(x)\). A finite subset \(G=\{g_1,\ldots ,g_\ell \}\) of an ideal I in K[t][x] is said to be a Gröbner basis of I w.r.t. \(\prec _x\) if \(\langle {{\,\textrm{lm}\,}}(g_1),\ldots , {{\,\textrm{lm}\,}}(g_\ell )\rangle =\langle {{\,\textrm{lm}\,}}(I) \rangle .\)

Let I be an ideal in K[t][x]. It is possible to regard I as an ideal in K[t, x] and compute a Gröbner basis G of I w.r.t. a block term order \((\prec _t,\prec _x)\) with \(t \ll x\) in K[t, x] where \(\prec _t\) and \(\prec _x\) are term orders on Term(t) and Term(x), respectively. Then, it is well-known that G is a Gröbner basis of I w.r.t. \(\prec _x\) in K[t][x] (see [12, 14]). This fact is summarized as Algorithm 1 for computing a Gröbner basis of an ideal in K[t][x].

We remark that the output of Algorithm 1 may contain redundant polynomials. See the details in [12].

For \(g_1,\ldots ,g_\ell \in K[t]\), \(\mathbb {V}(g_1,\ldots ,g_\ell ) \subset \overline{K}^m\) denotes the affine variety of \(g_1,\ldots ,\) \(g_\ell\), i.e. \(\mathbb {V}(g_1,\ldots ,g_\ell )=\{\bar{t} \in \overline{K}^m | g_1(\bar{t})=\cdots =g_\ell (\bar{t})=0\}\), and \(\mathbb {V}(\emptyset )=\overline{K}^m\). We use an algebraically constructible set that has a form \(\mathbb {V}(f_1,\ldots ,f_\ell ) \backslash \mathbb {V}(\) \(f_1',\ldots ,f'_{\ell '}) \subset \overline{K}^m\) where \(f_1,\ldots ,f_\ell , f_1',\ldots ,f'_{\ell '} \in K[t]\). For \(\bar{t} \in \overline{K}^m\), the canonical specialization homomorphism \(\sigma _{\bar{t}}: K[t][x] \rightarrow \overline{K}[x]\) (or \(K[t] \rightarrow \overline{K}\)) is defined as the map that substitutes t by \(\bar{t}\) in \(f(t,x) \in K[t][x]\). The image \(\sigma _{\bar{t}}\) of a set \(F \subset K[t][x]\) is denoted by \(\sigma _{\bar{t}}(F)=\{\sigma _{\bar{t}}(f) | f \in F\} \subset \overline{K}[x]\).

Let I be a monomial ideal in K[x] and \(q \in K[t]\). Then, the minimal basis of I is written as \({ MB}(I)\) and the squarefree part of q is written as \(\sqrt{q}\).

In [5, 6], Kapur-Sun-Wang introduce the following nice theorem that is based on the results of Kalkbrener [4].

Theorem 1

(Kapur-Sun-Wang [5, 6]) Let \(\prec _x\) be a term order on Term(x), F a finite set of polynomials in K[t][x], E a finite set of polynomials in K[t], G a Gröbner basis of \(\langle F \cup E \rangle\) w.r.t. \(\prec _x\) in K[t][x] and \(G_b=G\backslash (G \cap \langle E \rangle )\). Assume that \(G_b\ne \emptyset\) and let \({ MB}(\langle {{\,\textrm{lt}\,}}(G_b) \rangle )=\{w_1,\ldots ,w_\ell \}\) in K[t][x]. For each \(i \in \{1,\ldots ,\ell \}\), let \(G_{w_i}=\{g \in G | {{\,\textrm{lt}\,}}(g)=w_i\}\) and \(G'=\{g_1,\ldots ,g_\ell \}\) where \(g_i \in G_{w_i}\) \((1\le i \le \ell )\).

Then, for all \(\bar{a} \in \mathbb {V}(E) \backslash \mathbb {V}\left( \sqrt{\prod _{j=1}^\ell {{\,\textrm{lc}\,}}(g_j)}\right)\), \(\sigma _{\bar{a}}(G')\) is a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\).

Example 1

Let \(F=\{sx^2-xy+y^2,txy+y,sx^2-y,(t+1)xy^2+sx\}\subset {{\,\mathrm{\mathbb {Q}}\,}}[s,t][x,y]\), \(E=\emptyset\) and \(\prec\) the lexicographic term order with \(y \prec x\) on Term\((\{x,\) \(y\})\). Algorithm 1 outputs the following Gröbner basis G of \(\langle F \rangle\) w.r.t. \(\prec\):

Thus, as MB\((\langle {{\,\textrm{lt}\,}}(G) \rangle )=\{x,y\}\), we obtain \(G_{x}=\{sx+ty\}\) and \(G_{y}=\{(s+t^2+t)y, (st-2\,s+1)y, (s^2+6\,s-t-3)y\}\). Set \(G'=\{sx+ty, (s+t^2+t)y\}\) where \(sx+ty \in G_x\) and \((s+t^2+t)y\in G_y\). Then, for all \(\bar{a} \in {{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s(s+t^2+t))\), \(\sigma _{\bar{a}}(G')\) is a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec\) in \(\mathbb {C}[x,y]\).

Note that G is not a reduced Gröbner basis of \(\langle F \rangle\) w.r.t. \(\prec\) in \({{\,\mathrm{\mathbb {Q}}\,}}(s,t)[x,y]\) where \({{\,\mathrm{\mathbb {Q}}\,}}(s,t)\) is a field of rational functions with variables s, t.

After obtaining the pair \(({{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s(s+t^2+t)), G')\), we can re-compute the reduced Gröbner basis B of \(\langle G'\rangle\) w.r.t. \(\prec\) in \({{\,\mathrm{\mathbb {Q}}\,}}(s,t)[x,y]\), and B satisfies “for all \(\bar{a} \in {{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s(s+t^2+t))\) \(\sigma _{\bar{a}}(B)\) is a reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec\) in \(\mathbb {C}[x,y]\).

Corollary 1

Using the same notation as in Theorem 1, if \(G_b=\emptyset\), then, for all \(\bar{a} \in {{\,\mathrm{\mathbb {V}}\,}}(E)\), \(\sigma _{\bar{a}}(F)=\{0\}\).

In [13], the author gives the following theorem.

Theorem 2

([13]) Using the same notation as in Theorem 1, then for all \(\bar{a} \in \mathbb {V}(E) \backslash\) \(\bigcup _{i=1}^\ell \mathbb {V}({{\,\textrm{lc}\,}}(G_{w_i}))\), \(\sigma _{\bar{a}}(G_{w_1} \cup G_{w_2} \cup \cdots \cup G_{w_\ell })\) is a Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\) and \({{\,\textrm{lt}\,}}(\sigma _{\bar{a}}(G_{w_1} \cup G_{w_2} \cup \cdots \cup G_{w_\ell }))=\{w_1,\ldots ,w_\ell \}\).

Example 2

Let us consider Example 1, again. By utilizing Theorem 2, we obtain the following: for all \(\bar{a} \in {{\,\mathrm{\mathbb {C}}\,}}^2\backslash \left( \mathbb {V}(s)\cup \mathbb {V}(s+t^2+t, st-2\,s+1, s^2+6\,s \right.\) \(\left. -t-3)\right)\), \(\sigma _{\bar{a}}(G_x \cup G_y)\) is a Gröbner basis of \(\langle \sigma _{\bar{a}}(F)\rangle\) w.r.t. \(\prec\) in \(\mathbb {C}[x,y]\).

Note that since \(\mathbb {V}(E) \backslash \mathbb {V}(h) \subset \mathbb {V}(E) \backslash \bigcup _{i=1}^\ell \mathbb {V}({{\,\textrm{lc}\,}}(G_{w_i}))\), Theorem 2 provides a stronger condition of parameters than Theorem 1. The stronger condition of parameters is often required to compute “quantifier elimination” [2, 3]. Thus, if one needs the stronger condition of parameters, it would be better to select Theorem 2. On the other hand, if one needs minimal Gröbner bases, then it is better to select Theorem 1.

Here, first we give a new result that is an answer of Problem 1 in Sect. 1. Second, we generalize the new result to make a new algorithm for computing comprehensive Gröbner systems.

Let \(\prec _x\) be a term order on Term(x), F a finite set of polynomials in K[t][x] and G the reduced Gröbner basis of \(\langle F \rangle\) w.r.t. \(\prec _x\) in K(t)[x] where K(t) is the field of rational functions of t. As we describe in Sect. 1, we call the set G the “generic” reduced Gröbner basis of \(\langle F \rangle\).

For \(q \in K(t)[x]\), we define \({{\,\textrm{dlcm}\,}}(q)\) as the least common multiple of all denominators of coefficients in K(t) of q. For instance, set \(q=x^2y+\frac{1}{s^2}xy+\frac{4}{t}y\) in \({{\,\mathrm{\mathbb {C}}\,}}(s,t)[x,y]\), then, \({{\,\textrm{dlcm}\,}}(q)=s^2t\). Hence \({{\,\textrm{dlcm}\,}}(q)\cdot q=s^2tx^2y+txy+4\,s^2y\) in \({{\,\mathrm{\mathbb {C}}\,}}[s,t][x,y]\).

The following theorem gives us an answer of Problem 1.

Theorem 3

Let \(\prec _x\) be a term order on Term(x), F a finite set of polynomials in K[t][x], G a reduced Gröbner basis of \(\langle F \rangle\) w.r.t. \(\prec _x\) in K(t)[x]. Let \(G_D=\{{{\,\textrm{dlcm}\,}}(g) g\; |\; g \in G\}\) and \(h=\sqrt{\prod _{g' \in G_D}{{\,\textrm{lc}\,}}(g')}\) in K[t][x]. Consider F to be a subset of K[t, x], and let S to be a reduced Gröbner basis of the ideal quotient \(\langle F \rangle : \langle G_D \rangle\) w.r.t. a block term order \((\prec _t, \prec _x)\) in K[t, x] where \(\prec _t\) is a term order on Term(t). Then, the following holds:

1. (1)

   \(S \cap K[t]\ne \emptyset\),

2. (2)

   for all \(\bar{a} \in \overline{K}^m \backslash \left( \mathbb {V}(S \cap K[t]) \cup \mathbb {V}(h)\right)\), \(\sigma _{\bar{a}}(G)\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\).

Proof

Let \(G=\{g_1,\ldots , g_\ell \}\) and \(G_D=\{{{\,\textrm{dlcm}\,}}(g_1)g_1,\ldots , {{\,\textrm{dlcm}\,}}(g_\ell )g_\ell \}\).

(1) Since G is the reduced Gröbner basis of \(\langle F \rangle\) in K(t)[x], for all \(g_i \in G\), \(g_i \in \langle F \rangle \cap K(t)[x]\) and there exists \(p_i \in K[t]\) such that \(p_ig_i \in \langle F \rangle\) in K[t][x]. Then, \(p_i{{\,\textrm{dlcm}\,}}(g_i)g_i \in \langle F \rangle\). Set \(p=p_1\cdots p_\ell\) in K[t]. We have \(p {{\,\textrm{dlcm}\,}}(g_i)g_i \in \langle F \rangle\). Hence, \(p \in \langle F \rangle : \langle G_D \rangle\). As S is the reduced Gröbner basis of \(\langle F \rangle : \langle G_D \rangle\) w.r.t. \((\prec _t, \prec _x)\) in K[t, x], there exists \(q \in S\) such that \({{\,\textrm{lt}\,}}(q)\) divides \({{\,\textrm{lt}\,}}(p)\) in K[t, x]. Therefore, we have \(q \in S \cap K[t]\), namely, \(S \cap K[t]\ne \emptyset\).

(2) For all \(\bar{a} \in \overline{K}^m \backslash \left( {{\,\mathrm{\mathbb {V}}\,}}(S \cap K[t])\cup {{\,\mathrm{\mathbb {V}}\,}}(h)\right)\), there exists \(q \in S\cap K[t]\) such that \(\sigma _{\bar{a}}(q)\ne 0\) and \(\sigma _{\bar{a}}(q) \in \overline{K}\). Since, for all \(g \in G_D\), \(q g \in \langle F \rangle\), thus \(\sigma _{\bar{a}}(q)\sigma _{\bar{a}}(g) \in \langle \sigma _{\bar{a}}(F)\rangle\), therefore \(\sigma _{\bar{a}}(g) \in \langle \sigma _{\bar{a}}(F)\rangle\) in \(\overline{K}[x]\). Conversely, as \(F \subset \langle G_D \rangle\), we have \(\sigma _{\bar{a}}(F) \subset \langle \sigma _{\bar{a}}(G_D) \rangle\). Therefore, we have \(\langle \sigma _{\bar{a}}(F)\rangle = \langle \sigma _{\bar{a}}(G_D) \rangle\). Since G is reduced in K(t)[x] and \({{\,\textrm{lt}\,}}(\sigma _{\bar{a}}(G))={{\,\textrm{lt}\,}}(G)\), \(\sigma _{\bar{a}}(G)\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\succ _x\) in \(\overline{K}[x]\). \(\square\)

The following corollary is a direct consequence of Theorem 3.

Corollary 2

Using the same notation as in Theorem 3, let \(q \in S \cap K[t]\). Then, for all \(\bar{a} \in \overline{K}^m \backslash \mathbb {V}(h\cdot q)\), \(\sigma _{\bar{a}}(G)\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\).

Proof

Since \({{\,\mathrm{\mathbb {V}}\,}}(S\cap K[t]) \subset {{\,\mathrm{\mathbb {V}}\,}}(q)\), we have

Therefore, by Theorem 3, this corollary holds. \(\square\)

The parameter spaces \(\overline{K}^m \backslash \left( \mathbb {V}(S \cap K[t]) \cup \mathbb {V}(h)\right)\) and \(\overline{K}^m \backslash \mathbb {V}(h\cdot q)\), that are from Theorem 3 and Corollary 2, are answers of Problem 1.

We illustrate Theorem 3 and Corollary 2 with the following examples.

Example 3

Let \(\prec _x\) be the graded lexicographic term order with \(y \prec x\) on \(Term(\{x,\) \(y\})\) and \(F=\{x^2y+sx^2+y^2,xy+ty^2\} \subset {{\,\mathrm{\mathbb {C}}\,}}[s,t][x,y]\) where x, y are variables and s, t are parameters. Then, the reduced Gröbner basis G of \(\langle F \rangle\) w.r.t. \(\prec _x\) in \({{\,\mathrm{\mathbb {C}}\,}}(s,t)[x,y]\) is

Thus, we have \(G_D=\{{{\,\textrm{dlcm}\,}}(g) g \; |\; g \in G\}=\{xy+ty^2, t^2y^3+sx^2+y^2, x^3-stx^2-ty^2\}\). The reduced Gröbner basis of the ideal quotient \(\langle F \rangle : \langle G_D \rangle\) w.r.t. the block term order \((\prec _t,\prec _x)\) is \(S=\{s, y\}\) in \({{\,\mathrm{\mathbb {C}}\,}}[s,t,x,y]\) where \(\prec _t\) is the graded lexicographic term order with \(s \prec t\). Since \(\sqrt{\prod _{d \in G_D}{{\,\textrm{lc}\,}}(d)}=t\) and \(S\cap {{\,\mathrm{\mathbb {C}}\,}}[s,t]=\{s\}\), thus, for all \(\bar{a} \in {{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(st)\), \(\sigma _{\bar{a}}(G)\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \({{\,\mathrm{\mathbb {C}}\,}}[x,y]\).

Example 4

Let us consider Example 1, again. The reduced Gröbner basis of \(\langle F \rangle\) w.r.t. \(\prec\) is \(\{x,y\}\) in \({{\,\mathrm{\mathbb {C}}\,}}(s,t)[x,y]\), and the reduced Gröbner basis of the ideal quotient \(\langle F \rangle : \langle x,y \rangle\) w.r.t. \((\prec ', \prec )\) in \({{\,\mathrm{\mathbb {Q}}\,}}[s,t,x,y]\) is

where \(\prec '\) is the graded reverse lexicographic term order with \(t \prec ' s\) on \(Term(\{s,t\}).\) Since

if we apply Theorem 3, we obtain a parameter space \({{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s^2+st^2+st,-s^2t+2s^2-s,s^3+6s^2-ts-3s)\), namely, for all \(\bar{a} \in {{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s^2+st^2+st,-s^2t+2\,s^2-s,s^3+6\,s^2-ts-3\,s)\), \(\{x,y\}\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec\) in \({{\,\mathrm{\mathbb {C}}\,}}[x,y]\).

If we apply Corollary 2 and select \(s^2+st^2+st\) from \(S\cap {{\,\mathrm{\mathbb {C}}\,}}[s,t]\), then it holds that for all \(\bar{a} \in {{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s^2+st^2+st)\), \(\{x,y\}\) is the reduced Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec\) in \({{\,\mathrm{\mathbb {C}}\,}}[x,y]\).

Note that \({{\,\mathrm{\mathbb {V}}\,}}(s^2+st^2+st,-s^2t+2\,s^2-s,s^3+6\,s^2-ts-3\,s)={{\,\mathrm{\mathbb {V}}\,}}(s)\cup {{\,\mathrm{\mathbb {V}}\,}}(s+t^2+t,-st+2\,s-1,s^2+6\,s-t-3)\) and \({{\,\mathrm{\mathbb {V}}\,}}(s^2+st^2+st)={{\,\mathrm{\mathbb {V}}\,}}(s)\cup {{\,\mathrm{\mathbb {V}}\,}}(s+t^2+t)\).

Let us turn to the generalization of Theorem 3 that is utilized to construct a new algorithm for computing comprehensive Gröbner systems in Sect. 4.

Definition 3

Let I be a proper ideal of K[x] and \(u=\{u_1,\ldots ,u_r\}\) a subset of x. Then, u is called independent modulo I if \(I \cap K[u]=\{0\}\). Moreover, u is called maximally independent modulo I if it is independent modulo I and the cardinality of u is equal to the dimension of I.

The following theorem is the generalization of Theorem 3.

Theorem 4

Let \(\prec _x\) be a term order on Term(x), F a finite set of polynomials in K[t][x], E a finite set of polynomials in K[t] with \(\langle E \rangle \ne \langle 1 \rangle\), \(u \subset t\) a maximally independent set modulo \(\langle E \rangle\) in K[t]. Regard \(F \cup E\) as a set of \((K(u)[t \backslash u])[x]\), and let B be a Gröbner basis of \(\langle F \cup E \rangle\) w.r.t. \(\prec _x\) in \((K(u)[t \backslash u])[x]\) (an output of Algorithm 1), \(G=\{{{\,\textrm{dlcm}\,}}(g)g| g \in B\}\) and \(G_b=G \backslash (G \cap \langle E \rangle )\) in \((K(u)[t\backslash u])[x]\). Assume that \(G_b\ne \emptyset\), and let \({ MB}(\langle {{\,\textrm{lt}\,}}(G_b)\rangle )=\{w_1,\ldots ,w_\ell \}\) in \((K(u)[t\backslash u])[x]\). For each \(i \in \{1,\ldots ,\ell \}\), denote \(G_{w_i}=\{f \in G_b | {{\,\textrm{lt}\,}}(f)=w_i\}\) and take one polynomial \(g_i\) from \(G_{w_i}\). Set \(G'=\{g_1,\ldots ,g_\ell \}\) and \(G_D=\{{{\,\textrm{dlcm}\,}}(g)g \;|\; g \in G'\} \subset K[t][x]\). Let S be the reduced Gröbner basis of the ideal quotient \(\langle F \cup E \rangle : \langle G \rangle\) w.r.t. a block term order \((\prec _u,\prec _{t \backslash u, x})\) in K[t, x] where \(\prec _{t\backslash u}\) is a term order on Term\((t\backslash u)\), \(\prec _{t \backslash u, x}:=(\prec _{t \backslash u}, \prec _{x})\) and \(\prec _{u}\) is a term order on Term(u). Then, the following holds:

1. (1)

   \(S \cap K[u]\ne \emptyset\), and

2. (2)

   for all \(\bar{a} \in \mathbb {V}(E) \backslash \left( \mathbb {V}(S \cap K[u]) \cup \mathbb {V}(h)\right)\), \(\sigma _{\bar{a}}(G')\) is a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\) where \(h=\sqrt{\prod _{g \in G_D} {{\,\textrm{lc}\,}}(g)}\).

Proof

If \(\langle E \rangle\) is zero-dimensional in K[t] i.e. \(u=\emptyset\), then as it is obvious that \(S=\{1\}\), (1) and (2) follow from Theorem 1.

Assume that \(\langle E \rangle\) is not zero-dimensional i.e. \(u \ne \emptyset\).

(1) Since \(B \subset \langle F \cup E\rangle\) in \((K(u)[t\backslash u])[x]\), for all \(g_i \in B\), there exists \(p_i \in K[u]\) such that \(p_ig_i \in \langle F \cup E \rangle\) in K[t][x]. Then, \(p_i {{\,\textrm{dlcm}\,}}(g_i)g_i \in \langle F \cup E \rangle\). Set \(p=p_1\cdots p_\ell\) in K[u]. We have \(p{{\,\textrm{dlcm}\,}}(g_i)g_i \in \langle F \cup E\rangle\) in K[t][x]. Hence, \(p \in \langle F \cup E \rangle : \langle G \rangle\). As S is the reduced Gröbner basis of the ideal quotient \(\langle F \cup E \rangle : \langle G \rangle\) w.r.t. a block term order \((\prec _u, \prec _{t \backslash u, x})\) in K[t, x], there exists \(q \in S\) such that \({{\,\textrm{lt}\,}}(q)\) divides \({{\,\textrm{lt}\,}}(p)\) in K[t, x]. Therefore, we have \(q \in S\cap K[u]\), namely, \(S \cap K[u]\ne \emptyset\).

(2) For all \(\bar{a} \in {{\,\mathrm{\mathbb {V}}\,}}(E)\backslash \left( {{\,\mathrm{\mathbb {V}}\,}}(S\cap K[u])\cup {{\,\mathrm{\mathbb {V}}\,}}(h)\right)\), there exists \(q \in S\cap K[u]\) such that \(\sigma _{\bar{a}}(q)\ne 0\). Set \(G_q=\{qg| g\in G\}\). As G is a Gröbner basis of \(\langle F \cup E \rangle\) w.r.t. \(\succ _x\) in \(K(u)[t\backslash u][x]\), \(G_q\subset K[t][x]\) is also a Gröbner basis of \(\langle F \cup E\rangle\) in \(K(u)[t\backslash u][x]\). Moreover, we have \(G_q\backslash (G_q \cap \langle E \rangle )=\{qg| g \in G_b\} \subset K[t][x]\) where \(G_b=G \backslash (G \cap \langle E \rangle )\). Thus, \({ MB}(\langle {{\,\textrm{lt}\,}}(G_q)\rangle )={ MB}(\langle {{\,\textrm{lt}\,}}(G_b)\rangle )=\{w_1,\ldots ,w_\ell \}\), in K[t][x], and \(G_{w_i}=\{f | {{\,\textrm{lt}\,}}(f)=w_i, f \in G_b\}=\{g | {{\,\textrm{lt}\,}}(qg)=w_i, qg \in G_q\}\) where \(1\le i \le \ell\). By applying Theorem 1 to \(G_q\), we obtain the fact that \(\sigma _{\bar{a}}(G')\) is a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\). \(\square\)

We remark that as for all \(\bar{a} \in \mathbb {V}(E) \backslash \left( \mathbb {V}(S \cap K[u]) \cup \mathbb {V}(h)\right)\) we have \({{\,\textrm{lt}\,}}(\sigma _{\bar{a}}(G_D))={{\,\textrm{lt}\,}}(\sigma _{\bar{a}}(G'))\), \(\sigma _{\bar{a}}(G_D)\) is also a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\). Furthermore, if \(G_b=\emptyset\), then, for all \(\bar{b} \in {{\,\mathrm{\mathbb {V}}\,}}(E)\), \(\sigma _{\bar{b}}(F)=\{0\}\).

We illustrate Theorem 4 with the following example.

Example 5

Let \(\prec\) be the graded lexicographic term order with \(y \prec x\), \(F=\{s^2x^3+xy+t,x^2y^4+ty^2\}\subset {{\,\mathrm{\mathbb {C}}\,}}[s,t][x,y]\) and \(E=\langle s+t\rangle \subset {{\,\mathrm{\mathbb {C}}\,}}[s,t]\) where s, t are parameters and x, y are variables. Then, a maximally independent set modulo \(\langle E \rangle\) in \({{\,\mathrm{\mathbb {C}}\,}}[s,t]\) is \(\{t\}\) and a Gröbner basis G of \(\langle F \cup E \rangle\) w.r.t. \(\prec\) in \(({{\,\mathrm{\mathbb {C}}\,}}(t)[s])[x,y]\) is

Since \({ MB}(\langle {{\,\textrm{lt}\,}}(G\backslash (G \cap \langle E \rangle ))\rangle )=\{x^3,xy^3,x^2y^2 \}\), we have

and \(h=\sqrt{t^2\cdot t^3 \cdot t^2}=t\). The reduced Gröbner basis of the ideal quotient \(\langle F \cup E \rangle : \langle G \rangle\) w.r.t. a block term order \((\prec _t, \prec _s, \prec )\) (i.e. \(t \ll s \ll \{x,y\}\)) is \(S=\{t,s,x\}\) where \(\prec _t\) and \(\prec _s\) are the lexicographic term orders on Term(t) and Term(s), respectively. Therefore, by Theorem 4,

\(\sigma _{\bar{a}}(G_D)\) is a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec\) in \(\mathbb {C}[s,y]\).

Corollary 3

Using the same notation as in Theorem 4, let \(q \in S\) in K[u]. Then, for all \(\bar{a} \in \mathbb {V}(E) \backslash \mathbb {V}(h\cdot q)\), \(\sigma _{\bar{a}}(G')\) is a minimal Gröbner basis of \(\langle \sigma _{\bar{a}}(F) \rangle\) w.r.t. \(\prec _x\) in \(\overline{K}[x]\).

Proof

Since \({{\,\mathrm{\mathbb {V}}\,}}(S \cap K[u]) \subset {{\,\mathrm{\mathbb {V}}\,}}(q)\), this corollary holds. \(\square\)

Let us compare Theorem 1 with Thereof 4. The main computational part in Theorem 1 is “\((*1):\) a Gröbner basis of \(\langle F \cup E \rangle\) w.r.t. \(\prec _x\) in K[t][x]”. On the other hand, Theorem 4 mainly needs to compute “\((*2):\) a Gröbner basis of \(\langle F \cup E \rangle\) w.r.t. \(\prec _x\) in \((K(u)[t\backslash u])[x]\) and the reduced Gröbner basis of the ideal quotient \(\langle F \cup E \rangle : \langle G \rangle\) w.r.t. a block term order \((\prec _u, \prec _{t \backslash u, x})\) in K[t, x]”. These are the big differences.

Here we give a new algorithm for computing comprehensive Gröbner systems as an application of Theorem 3 and Corollary 3.

We adopt the following as a definition of comprehensive Gröbner system.

Definition 4

Fix a term ordering \(\prec\) on Term(x). Let \(F \subset K[t][x]\), \(\mathbb {A}_1,\ldots , \mathbb {A}_r \subset \overline{K}^m\), \(G_1,\ldots , G_r \subset K[t][x]\). If a finite set \({\mathcal G}=\{(\mathbb {A}_1,G_1),\ldots ,(\mathbb {A}_r,G_r)\}\) of pairs satisfies the properties such that

1. (1)

   for \(i\ne j\), \(\mathbb {A}_i \cap \mathbb {A}_j=\emptyset\), and

2. (2)

   for all \(\bar{t} \in \mathbb {A}_i\) and \(g \in G_i\), \({{\,\textrm{lt}\,}}(g)={{\,\textrm{lt}\,}}(\sigma _{\bar{t}}(g))\) and \(\sigma _{\bar{t}}(G_i)\) is a Gröbner basis of \(\langle \sigma _{\bar{t}}(F) \rangle\) in \(\overline{K}[x]\),

then, \({\mathcal G}\) is called a comprehensive Gröbner system (CGS) of \(\langle F \rangle\) over \(\overline{K}\) on \(\mathbb {A}_1\cup \cdots \cup \mathbb {A}_r\). We call a pair \((\mathbb {A}_i, G_i)\) segment of \({\mathcal G}\). We simply say that \({\mathcal G}\) is a comprehensive Gröbner system of \(\langle F \rangle\) over \(\overline{K}\) if \(\mathbb {A}_1\cup \cdots \cup \mathbb {A}_r=\overline{K}^m.\)

In [5, 6], Kapur-Sun-Wang introduce a nice algorithm that is based on Theorem 1 for computing a comprehensive Gröbner system. In Algorithm 2, for finite subsets \(A, B \subset K[t]\), \(A \wedge B\) means the set \(\{fg| f \in A, g \in B\}\).

Remark 1

If \(\langle E \rangle \subset K[t]\) is zero-dimensional in Corollary 3 (or Theorem 4), then the maximally independent set modulo \(\langle E \rangle\) is empty and the reduced Gröbner basis of \(\langle F \cup E \rangle : \langle G \rangle\) is \(\{1\}\). Thus, in this case, Corollary 3 is essentially same as Theorem 1, because \({{\,\mathrm{\mathbb {V}}\,}}(S \cap K[t])={{\,\mathrm{\mathbb {V}}\,}}(1)=\emptyset\). Therefore, in order to avoid the redundancy (i.e. computing the reduced Gröbner basis of the ideal quotient \(\langle F \cup E \rangle : \langle G \rangle\)), we adopt Algorithm 2, that is introduced by Kapur-Sun-Wang in [5, 6], for computing a comprehensive Gröbner systems when \(\langle E \rangle\) is zero-dimensional in K[t].

Now, we are ready to introduce a new algorithm (Algorithm 3) that is based on Theorem 4 for computing a comprehensive Gröbner system. As we described in Remark 1, the new algorithm includes Algorithm 1 (KSW) and is designed based on Corollary 3.

One of the optimizations is the use of factorization(h) that outputs the factorization of h in K[t]. The techniques in [5, 6, 13, 16, 17] are applicable to obtain small and nice outputs of a comprehensive Gröbner system. In order to keep the presentation simple, we have deliberately avoided tricks and optimizations. Note that we adopt \(G_D \subset K[t][x]\), as a form of the Gröbner basis, instead of \(G' \subset K(t)[x]\) at \((\triangle )\) because \(G_1,\ldots ,G_r\) of Definition 4 are in K[t][x].

As the proofs of the correctness and termination are same as the proofs given in [5, 6, 13, 17], we omit the proofs.

As we described in the end of Sect. 3, the main computational part of Algorithm 2 is \((*1)\) (that is marked in Algorithm 2) and that of Algorithm 3 is \((*2)\). Otherwise, Algorithm 2 and Algorithm 3 are almost the same. Hence, if the part \((*1)\) of Algorithm 2 is faster than the part \((*2)\) of Algorithm 3, then Algorithm 2 seems to be faster than Algorithm 3. Otherwise, Algorithm 3 is faster than Algorithm 2.

Currently, all existing algorithms that are presented in [5,6,7, 13, 17] use the part \((*1)\) of Algorithm 2 for computing comprehensive Gröbner systems. Therefore, if we cannot obtain an output of GröbnerBasis (Algorithm 1) within realistic time, then we cannot obtain a comprehensive Gröbner system from the algorithms within a realistic time, neither. We emphasize that Algorithm 3 provides a different computational way.

Note that one can directly apply Theorem 4 to design an algorithm for computing comprehensive Gröbner systems, like an algorithm given in [13]. Since we would like to compare the new algorithm with the famous Kapur-Sun-Wang’s algorithm (i.e. Algorithm 2), we adopted Corollary 3 in Algorithm 3 because the algebraically constructible set of Corollary 3 is much similar than that of Theorem 1 and Theorem 4.

We illustrate Algorithm 3 with the following example.

Example 6

Let \(F=\{sx^3y^2+y^4,tx^3y^2+sy^3+x,txy^3+x^3y^2\} \subset {{\,\mathrm{\mathbb {C}}\,}}[s,t][x,y]\) and \(\prec _{x,y}\) the graded lexicographic term order with \(y \prec x\).

1. 1.

   The reduced Gröbner basis G of \(\langle F \rangle\) w.r.t. \(\prec _{x,y}\) is \(B=\left\{ xy,x^2,y^3+\frac{1}{s}x\right\}\). Set \(G=\{{{\,\textrm{dlcm}\,}}(g)g| g \in B\}=\{xy,x^2,sy^3+x\}\) and \({ MB}(\langle {{\,\textrm{lt}\,}}(G)\rangle )=\{xy, x^2,y^3\}\). Thus,we have \(G'=G\), \(G_D=\{{{\,\textrm{dlcm}\,}}(g)g \;|\; g \in G'\}=\{xy,x^2,sy^3+x\}\) and \(h=\sqrt{\prod _{p \in G_D}{{\,\textrm{lc}\,}}(p)}=s\). The reduced Gröbner basis S of the ideal quotient \(\langle F \rangle : \langle G \rangle\) w.r.t. the block term order \((\prec _{s,t},\prec _{x,y})\) is

   $$\begin{aligned} S=\{s^6t^{11}-s^6t^7+1,y+s^2t^3,x-st^2\} \end{aligned}$$

   where \(\prec _{s,t}\) is the lexicographic term order with \(t \prec s\). As \(S\cap {{\,\mathrm{\mathbb {C}}\,}}[s,t]=\{s^6t^{11}-s^6t^7+1\}\), we obtain a segment

   $$\begin{aligned} \left( {{\,\mathrm{\mathbb {C}}\,}}^2\backslash {{\,\mathrm{\mathbb {V}}\,}}(s(s^6t^{11}-s^6t^7+1)), G_D\right) . \end{aligned}$$
2. 2.

   Set \(E_1=\{s\}\). Then, a maximally independent set modulo \(\langle E_1 \rangle\) in \({{\,\mathrm{\mathbb {C}}\,}}[s,t]\) is \(\{t\}\), and a Gröbner basis \(G_1\) of \(\langle F \cup \{s\} \rangle \subset ({{\,\mathrm{\mathbb {C}}\,}}(t)[s])[x,y]\) w.r.t. \(\prec _{x,y}\) is

   $$\begin{aligned} G_1=\{s,x,y^4\}. \end{aligned}$$

   Thus, we have \(G_b=G_1 \backslash (G_1 \cap \langle E_1 \rangle )=\{x,y^4\}\), \({ MB}(\langle {{\,\textrm{lt}\,}}(G_b)\rangle )=\{x,y^4\}\) and \(G_1'=G_b\). Hence, \(G_D'=\{{{\,\textrm{dlcm}\,}}(g) g| g \in G_1'\}=G_1'\) and \(\sqrt{\prod _{p \in G_D'}{{\,\textrm{lc}\,}}(p)}=1\). The reduced Gröbner basis \(S_1\) of the ideal quotient \(\langle F\cup E_1 \rangle : \langle G_1 \rangle\) w.r.t. the block term order \((\prec _{s,t},\prec _{x,y})\) is \(\{1\}\). Hence, we obtain a segment

   $$\begin{aligned} \left( {{\,\mathrm{\mathbb {V}}\,}}(s), G_1' \right) . \end{aligned}$$
3. 3.

   Set \(E_2=\{s^6t^{11}-s^6t^7+1\}\). Then, a maximally independent set modulo \(\langle E_2 \rangle\) in \({{\,\mathrm{\mathbb {C}}\,}}[s,t]\) is \(\{t\}\), and a Gröbner basis \(G_2\) of \(\langle F \cup \{s^6t^{11}-s^6t^7+1\} \rangle \subset {{\,\mathrm{\mathbb {C}}\,}}(t)[s][x,y]\) w.r.t. \(\prec _{x,y}\) is

   $$\begin{aligned} G_2&= \{s^6t^{11}-s^6t^7+1,x^2-s^5t^{10}xy+s^5t^6xy, \\&\ \ \ \ \ \ \ y^3-s^3t^8xy-s^5t^{11}x+s^5t^7x, xy^2+s^2t^3xy\}. \end{aligned}$$

   Set \(G_b=G_2 \backslash (G_2 \cap \langle E_2 \rangle )=\{x^2-s^5t^{10}xy+s^5t^6xy, y^3-s^3t^8xy-s^5t^{11}x+s^5t^7x, xy^2+s^2t^3xy\}\). Then, we have \({ MB}(\langle {{\,\textrm{lt}\,}}(G_b)\rangle )=\{x^2, y^3, xy^2\}\) and \(G_2'=G_b\). Hence, \(G_D''=\{{{\,\textrm{dlcm}\,}}(g)g | g \in G_2'\}=G_2'\) and \(\sqrt{\prod _{p \in G_D''}{{\,\textrm{lc}\,}}(p)}=1\). The reduced Gröbner basis \(S_2\) of the ideal quotient \(\langle F\cup E_2 \rangle : \langle G_2 \rangle\) w.r.t. the block term order \((\prec _{s,t},\prec _{x,y})\) is \(\{1\}\). Hence, we obtain a segment

   $$\begin{aligned} \left( {{\,\mathrm{\mathbb {V}}\,}}(s^6t^{11}-s^6t^7+1), G_2' \right) . \end{aligned}$$

Therefore, we obtain a comprehensive Gröbner system of \(\langle F \rangle\) w.r.t. \(\prec _{x,y}\) as

We have implemented Algorithm 2 and Algorithm 3 in the computer algebra system Risa/Asir [15]. One can download the source codes from the following website:

https://www.rs.tus.ac.jp/~nabeshima/softwares.html

Here we give results of benchmark tests. Table 1 shows comparisons of Algorithm 2 (KSW) and Algorithm 3 (New) in computation time (CPU time) and numbers of segments. All results have been computed on a PC with [OS: Windows 10, CPU: Intel(R) Core(TM) i9-C7900X CPU @ 3.30 GHz, RAM:128GB]. The time is given in seconds. In Table 1, >10 h means it takes more than 10 h. The following seventeen problems, namely, \(F_1,F_2,\ldots , F_{17}\) have been used for the comparisons.

The main variables are x, y, z (or x, y) and the parameters are a, b, c, d. The graded reverse lexicographic term order with (x, y, z) (or (x, y)) is used for the comparisons.

As is evident from Table 1, we cannot say which one is better unconditionally. In problems \(F_4, F_7, F_9, F_{12}, F_{14}\) and \(F_{16}\), Algorithm 2 is much faster than Algorithm 3, namely, the part \((*1)\) of Algorithm 2 is much faster the part \((*2)\) of Algorithm 3. In particular, the computations of ideal quotients are costly at \((*2)\) in the problems \(F_4, F_7, F_9, F_{12}, F_{14}\) and \(F_{16}\). However, in problems \(F_{5}, F_6, F_8, F_{10}, F_{11},\) \(F_{13}, F_{15}\) and \(F_{17}\), Algorithm 2 is much slower than Algorithm 3, because the computations of Gröbner bases in K[t][x] (i.e. \((*1)\) of Algorithm 2) are costly. One can find a lot of examples that Algorithm 2 is faster than Algorithm 3 and the opposite in computation time.

Through empirical observation, Algorithm 3 seems to be much faster than Algorithm 2 if a (reduced) Gröbner basis of \(\langle F \rangle\) w.r.t. \(\prec _x\) in K(t)[x] (or \((K(u)[t\backslash u])[x]\)) contains monomial elements.

We recommend trying the two algorithms when one computes a comprehensive Gröbner system, because we cannot say which one is better unconditionally.

Remark 2

The computer algebra system Singular [1] is also able to compute a Gröbner basis of a polynomial ideal in K(t)[x] and a reduced Gröbner basis of an ideal quotient in K[t, x]. However, from our experience, Risa/Asir-implementation is faster than that of Singular’s ones in the Gröbner basis computation in K(t)[x] as well as in the ideal quotient computation. Therefore, the computer algebra system Risa/Asir is very suitable for Algorithm 3. In fact, we could not obtain the same results of benchmark tests when we used the computer algebra system Singular.