数理解析研究所講究録 1456 巻 2005 年 195-205

195

Stability of Grobner bases and ACGB -revised佐藤洋祐
Yosuke SATO

東京理科大学数理清報科学科
DEPARTMENT 0F MATHEM AT1CAL INFORMATION SCIENCE,TOKYO UNIVERSITY 0F SCIENCE$*$

Abstract

over the coefficient ring
We prove that a Gr\"obner basis of an ideal I in a polynomial ringover the commutative vonwith a field $K$ also becomes a Gr\"obner basis in a polynomial ringunder the assumption that the elimination ideal
Neumann regular ring
. This result gives us an alternative natural proof foris a zero-dimensional proper radical ideal in
the former results concerning stability of the Gr\"obner basis property under specializations obtained by
T. Becker first and further generalized by M. Kalkbrener. We also give a modified ACGB algorithm tooverbner bases in a polynomial ring
compute parametric Gr\"obner bases, which starts froma field $K$ . Our algorithm is a similar but different approach from the algorithms obtained by A. Montes,
over thewhich are essentially based on computation of Gr\"obner bases in a polynomial ring.
quotient field$(K[\overline{A}_{\rfloor}^{\rceil})[\overline{X}|$$R[\overline{X}]$$K[\overline{A}]$$R$$I\cap K[\overline{A}]$$=K[\overline{A}]/I\cap K[\overline{A}]$$K[\overline{A}]$$K[\overline{A}_{\rangle}\overline{X}]$$\mathrm{G}\mathrm{r}\dot{\mathrm{o}}$$K(\overline{A})[\overline{X}]$$K(\overline{A})$1

Introduction

Stability of Grobner bases is an important notion in computer algebra. There have been publishedmany papers by many authors. In , [1] the following result is show$\mathrm{n}$over a field $K$ with variables
Theorem 1.1 (T. Becker) $Lei$ I be an ideal of a polynomial ring. Let
is a zero-dimensional rachcal ideal inand such thatis greater than any
such that each variable
be a Grobner basis of I $w.r$. . a term order $\geq of$is a lexicographical term order. $Lei$ be an m-tuple ofand the restriction $of\geq on$
term inis stable for ,. Then,elements of the algebraic closureof $K$ which is a zero of the ideal
becomes.
becomes a Grobner basis with the specialization by ,that is$K[\overline{A}.\overline{X}1\lrcorner$$\overline{A}$$I\cap K[\overline{A}]$$\overline{X}$$G=\{g_{1}(\overline{A},\overline{X}))\ldots, g_{l}(\overline{A},\overline{X})\}$$K[\overline{A}]$$X_{i}$$T(\overline{A},\overline{X})$$t$$\overline{a}$$T(\overline{A})$$T(\overline{A})$$I$$\overline{K}$$G$$\mathrm{a}$Gr\"obner basis in$\overline{K}[\overline{X}]w.r.t$$\mathrm{i}.e$$|\gamma$$G$$K[\overline{A}]$$\overline{a}$$a$$\{g_{1}(\overline{a},\overline{X}), \ldots, g_{l}(\overline{a},\overline{X})\}$. the term order that is a restiction $of\geq on$$T(\overline{X})$.

In [2], the above result is further generalized by the following result.
,,andTheorem 1.2 (M. Kalkbrener) Let J be an ideal of a polynomial nng
be a zero of J in some algebraic extension field $K’$ of K, then we have the following properties,$K[\overline{A}]$$\overline{a}=a_{1}$$a_{2}$\ldots ,$a_{m}$

1. The maximal ideal $\langle A_{1}-a_{1)}A_{2}-a_{2}, \ldots, A_{m}-a_{m}\rangle$ is the associated prime of some isolated primary
component of in
if and only if is strongly stable for for any Gr\"obner basis in.
such that$J$$K’[\overline{A}]$$\{G\rangle\cap K[\overline{A}]=J${?}ysato@rs.kagu ring ac.JP$G$$\overline{a}$$G$$(K[\overline{A})])[X]$1S6
2. In case the number of the vaiables is more than 1 the maximal ideal
is some isolated primary component of in
if and only if is strongly stable for$=J$ .
such
that
Gr\"obner basis
in$\langle A_{1}-a_{1}, A_{arrow 9}-a_{2}, \ldots, A_{m}-a_{m}\rangle$$\overline{X}$

$J$

$G$

$G$

$K’[\overline{A}]$$a$for any$\langle G\rangle\cap K[\overline{A}]$$(K[\overline{A})])[\overline{X}]$(See Definition 4.2 for the definition of strong stability,)This result actually extends Theorem 1.1 because of the following facts.
.r.t a term
be a Gr\"obner basis of an ideal I of a polynomial ring
Proposition 1.3 Let
Gr\"obner
basis ofis also a, thenis greater than any term inorder $\geq such$ that each vaiable$of\geqon$.
. the term order that is a restiction
I in$K[\overline{A},\overline{X}]\mathrm{w}$

$G$

$G$

$T(\overline{A})$$X_{l}$$T(\overline{X})$$(K[\overline{A}])[\overline{X}]w.r.t$, $K’$ be an algebraic extension
Proposition 1.4 Let J be a 0-dimensional ideal of a polynomial ring
be a zero of $J’$ , then we have the following properties.
field of K and a $=a_{1}$ , ,$K[\overline{A}]$$a_{2}$\ldots ,$a_{m}\in K^{\prime m}$

1. The maximal ideal, where $J’$ is the extension ofof $J’$ inis the associated prime of some primary component.
in$\langle A_{1}-a_{1}, A_{2}-a_{2}, \ldots, A_{m}-a_{m}\rangle$$K’[\overline{A}]$$J$$K’[\overline{A}]$2. In case is a radical ideal, the maximal ideal $A_{1}-a_{1}$ , A2
, where $J’$ is the extension of incomponent of in$J$$\langle$

$J’$

$J$

$K’[\overline{A}]$-a2, . . . ,$K’[\overline{A}]$is some primary$A_{m}-a_{m}\rangle$.

being 0-dimensional(and radical) is indispensable as
The result also shows that the condition
far as concerning strong stability, i.e. we have the following.
$\langle G\rangle\cap K[\overline{A}]$

Lemm a 1.4 Let J be an ideal ofproperties.

$K[\overline{A}]$such that J is not a 0-dimensional ideal, then we have the following

such that $I\cap K[\overline{A}]=J$ and any Grobner basis
1. There exists an ideal I of
is not strongly stable for some zero of .
$K[\overline{A}, X]$$G$

of I in$(K[\overline{A}])[X]$$J$

2. In case the number of is more than 1, with an additional assumption that is not a raaical ideal
and any Grobner basis of I insuch that
there exists an ideal I of
is not strongly stable for some zero of .
$J$$\overline{X}$$I\cap$ $K[\overline{A}]=J$$K[\overline{A},\overline{X}]$$G$$(K_{\lfloor}^{(}\overline{A}])^{r}\lfloor\overline{X}]$$J$

In $[9, 10]$ , we showed that alternative of comprehensive Gr\"obner bases can be defined in terms of Gr\"obnerbases in polynomial rings over commutative von Neumann regular rings, and we called them ACGB
(Alternative Comprehensive Grobner Bases). In [6] , we further optimized ACGB to get the following
result.

be a set of polynomials in
Theorem 1.6 Let F. Then the quotient ring
, let I be a zero-dimensional proper radical ideal in
a commutative von $N$ eumann regular $nng$ .
in the polynomial ring
be a Grobner basis ofLet$=\{f_{1}(\overline{A},\overline{X})_{:}\ldots, f_{s}(\overline{A},\overline{X})\}$$K[\overline{A}]$$K[\overline{A},\overline{X}]$$G=\{g_{1}(\overline{A},\overline{X}), \ldots :. Then,-tuple of elements$K[\overline{A}]/I$

any

$m$

g\iota(\overline{A},\overline{X})\}$$\langle F\rangle$

becomes$(K[\overline{A}]/I)[\overline{X}]$becomes a Grobner basis of the ideal
in an algebraic extension field of $K$ .
which lies on the variety$\{g_{1}(\overline{a},\overline{X}), \ldots,g_{l}(\overline{a},\overline{X})\}$$\overline{a}$$K[\overline{A}]/I$$\langle fi (\overline{a},\overline{X}), \ldots, f_{s}(\overline{a},\overline{X})\rangle$

over

for

$\mathrm{V}(I)$in Theorem 1.1 actually becomes a Gr\"obner basis in the polynom ial
In this paper, we prove that. iFrom thisover the commutative von Neumann regular ring
rings
result together with Theorem 1.6, the extended version of Theorem 1.1 by Theorem 1.2 directly follows$G$$(K[\overline{A}]/I\cap K[A])[\overline{X}]$$K[\overline{A}]/I\cap K[\overline{A}]$187
Our proof is not only easy but also natural since the notion of Gr\"obner bases in polynomial rings overbner bases are essentiallycommutative von Neumann regular rings and the notion of comprehensive
same as is shown in [13]. We also give a redescription of Lemma 1.2 in terms of ACGB.
even when
We also give a new method to comute a param etric Gr\"obner basis of an ideal I in
is not a zero-dimensional ideal, which is an improvement of our algorithm introduced in $[9, 10]$ .
over
Our new algorithm starts from a usual Grobner basis of an ideal I in the polynomial ring$K$
the field . Our method is a similar but different approach from the algorithms presented in ] thatcompute parametricbner bases with careful consideration of parameters, which are essentially based.
over the quotient fieldon computation of Grobner bases in a polynomial ring
We assume the reader is familiar with a theory of Gr\"obner bases in polynomial rings over commutative
von Neumann regular rings, which was introduced in [11]. Though we give a minim um review in section
2, we strongly recommend reading [5] or [11] for the reader who are not familiar with the theory. In
section 2, we also prove some properties which will be used for proving our main results. In section 3,
we give a brief review of ACGB. Though the contents is self contained, we also refer the reader to $[6, 10]$for more detailed description. Our main results are proved in section 4. In section 5, we discuss a new
approach to computation of parametric Gr\"obner bases.
$\mathrm{G}\mathrm{r}\dot{\mathrm{o}}$$K[\overline{A},\overline{X}]$$I\cap K[\overline{A}]$$K[\overline{A},\overline{X}]$$\lfloor\lceil 4$$\mathrm{G}\mathrm{r}\dot{\mathrm{o}}$$K(\overline{A})$$K(\overline{A})[\overline{X}]$2

von Neumann regular rings and Gr\"obner bases
A commutative ring$R$

with identity 1 is called a von Neumann regular $nng$ if it has the following

property:$Va\in R\exists b\in R$$a^{2}b=a$.

For such a , $a^{*}=ab$ and $a^{-1}=ab^{2}$ are uniquely determ ined and satisfy $aa^{*}=a$ , $aa^{-1}=a^{*}$ , and$(a^{*})^{2}=a^{*}$ .
Notice that every direct product of fields is a von Neumann regular ring. Conversely, any von Neumannregular ring is shown to be isomorphic to a subring of a direct product of fields as follows.
$b$

be a von Neumann regular ring If we define $\neg a=1-a$ , A $b=ab$ andDefinition 2.1 Let$a\vee b=\neg$ () for each , $b\in R$ such that $a^{2}=a$ , $b^{2}=b$ , then $(\{x\in R|x^{2}=x\}, \neg, \wedge, \vee)$ becomesAboolean algebra, which is denoted by $B(R)$ .
$R$$\neg a$$a$$\neg b$$a$$a$Considering $B(R)$ as a boolean ring, Stone representation theorem gives the following isomorphismfrom $B(R)$ to a subring of $\prod_{I\in St(B(R))}B(R)/I$ by $\mathrm{x})=\prod_{I\in St(B(R))}[x]_{I}$ , where $St(B(R))$ is the set of$\Phi$

all ma in al ideals of $B(R)$ . This representation of $B(R)$ is extended to a representation of $R$ as follows.
Theorem 2.1 (Saracino-Weispfenning) For a maximal ideal I of $B(R)_{J}$ if we put $I_{R}=$ {xy $|x\in$
is a maximal ideal of R. if we define a map, thenfrom into $\prod_{I\in St(B(R))}R/I_{R}$ by, $y\in$is a ring embedding.
$\mathrm{x})=\prod_{I\in St(B(R))}[x]_{I_{R}}$ , then$R$$\Phi$$I_{R}$$\mathrm{I}\}$$R$$\Phi$

A maximal ideal coincides with a prim ideal in a boolean ring. In the rest of the paper $Sf(B(R))$ isdenoted by Spec(B(If)) . We use for an elem ent of SPec(B(R)) as in the papers $[11, 13]$ . We also use.
into denote the elernent
andto denote the field
the same notations
In the following unless mentioned, Greek letters , , are used for terms, Roman letters , , forfor polynomials over . Throughout this section, we work in a polynomial
elem ents of , and ,$\mathrm{e}$

$p$

$)$

$R/p_{R}$$R_{\mathrm{p}}$$\alpha$

$R$

$f$

$g$

$h$

)

$[x]_{p_{R}}$$x_{p}$$R$$\beta$$\gamma$$R_{p}$

$a$

$b$

$c$

198
which is a von Neumann regular ring unless mentioned. We also assume that somne termorder is given. The leading term of is denoted by $lt(f)$ and its coefficient by $lc(f)$ . By $li(f)$ we denote$lc(f)’$ . The leading monomial of , i.e., $lc(f)lt(f)$ is denoted by $lm(f)$ . The set of all terms consisting.
is denoted byof variables
ring over

$R$

$f$

$f$

$T(\overline{X})$$\overline{X}$Definition 2.2 For a polynomial $f=a\alpha+g$ with
as follows:$lm(f)=\mathrm{a}\mathrm{a}$, a monomial reduction

is defined$arrow f$

bcxf3 $+h-ba^{-1}\beta(a\alpha+g)$.
where $ab\neq 0$ and baft need not be the leading monomial of$b\alpha\beta$$+harrow f$$b\alpha\beta+h$by a set $F$ of polynomials is also naturally defined. When $F$ is a finite set,
A monomial reduction
has a termination property. Using this monom ial reduction, Grobner bases are defined as follows.
$arrow F$$arrow F$

Definition 2.3 Let I be an ideal of a polynomial ring over R. A finite subset
basis of , if it satisfies the following property:$G$of I is called a Gr\"obner$I$$\forall f$

We simply say$G$is a Grobner basis if$G$$f\in I\Leftrightarrow farrow c0*$.

is a Grobner basis of the ideal$\langle G\rangle$

generated by itself.

Notice that a Grobner basis of I is clearly a basis of .
It is not difficult to show the following property.
$I$

$G$

Lemma 2.2 A finite subset G of an ideal I is a Grobner basis of I if and only if$\langle\{lm(f)|f\in I\}\rangle=\langle\{lm(g)|g\in G\}\rangle$

Proof. Assume thatis a Grobner basis of . Let $f$ be a non-zero polynomial in . Since $farrow G*0$ ,, andthere must exist polynomials , , $g_{s}\in G$ such that $lt(g_{i})|lt(f)$ for each
, , where,
for eachinductively as follows.
,. Define ,$=0$ for each$=1-(c_{1}+\cdots+c_{\mathrm{z}-1})$ for each $i=2$ ,, . (We put $b_{1}=1$ for convenience.) Then we have$g_{1}$$l\mathrm{i}(g_{s}))l\mathrm{i}(f)=l\mathrm{i}(f)$$c_{1}$$\ldots$$i=1_{\dot{\mathit{1}}}\ldots$$\ldots$$c_{\mathit{8}}\in R$$\ldots$

distinct 2 and$c_{s})lc(f)$

.

$j$

and

$I$

$I$

$G$

$((l\mathrm{i}(g_{1})\vee\cdots\vee$$s$$\mathrm{i}=1$$\mathrm{c}_{\iota}=b_{i}l\mathrm{i}(g_{\dot{\tau}})$$s$$\ldots$$b_{i}$$s$$c_{t}cj$$c_{1}+\cdots+c_{s}=\mathrm{l}\mathrm{i}(\mathrm{f})\vee\cdots\vee l\mathrm{i}(g_{s})$. Since$lc(f)=l\mathrm{i}(f)lc,(f).$,we have $lc(f)=(c_{1}+\cdots+$Hence, $lm(f)$ $=(c_{1}+\cdots+c_{s})lc(f)lt(f)=c_{1}lc(f)lt(f)+\cdots[perp] c_{s}fc(f)lt(f)=b_{1}l\mathrm{i}(g_{1})lc(f)lt(f)+$.. . $+b_{s}l\mathrm{i}(g_{s})lc(f)lt(f)=b_{1}l\mathrm{i}(g_{1})lc(f)lt(g_{1})(lt(f)/lt(g_{1}))+\cdots+b_{s}l\mathrm{i}(g_{s})lc(f)lt(g_{s})(lt(f)/lt(g_{s}))=$$b_{1}lc(g_{1})^{-1}lc(g_{1})lc(f)lt(g_{1})(lt(f)/lt(g_{1}))+\cdots+b_{s}lc(g_{s})^{-1}lc(g_{s})lc(f)lt(g_{s})(lt(f)/lt(g_{s}))$$=b_{1}lc(g_{1})^{-1}lc(f)(lt(f)/lt(g_{1}))lm(g_{1})+\cdots+b_{s}fc(g_{\epsilon})^{-1}lc(f)(lt(f)/lt(g_{s}))lm(g_{s})$It follows that$\langle\{lm(f)|f\in \mathrm{I}\}\rangle\subseteq\langle\{lm(g)|g\in G\}\rangle$$\langle\{lm(f)|f\in I\}\rangle\supseteq\langle\{lm(g)|g\in G\}\rangle$.

.

is trivial.

.
Assume conversely that
. ThisTo get a contradiction suppose there exists a non-zero polynom ial in I which is irreducible bymeans that $lc(f)lc\{g$ ) $=0$ for any in satisfying $lt(g)|lt(f)$ . By our assumption, there exists , ,$\in G$ and,...,. Multiplying $lc(f)$monomials
such that $lm(f)$sides,
from both
we get a contradiction $lc(f)lm(f)=0$ .
$\langle\{lm(f)|f\in I\}\rangle=\langle\{lm(g)|g\in G\})$

$f$

$g$

$a_{1}\alpha_{1}$$a_{s}\alpha_{s}$$G$$arrow G$$g_{1}$$\ldots$$g_{s}$$=a_{1}lm\langle$ $g_{1})\alpha_{1}+\cdots+a_{s}lm(g_{s})\alpha_{s}$$\iota$Definition 2.4 For a polynomial f, li $(f)f$ is called the boolean closure of f and denoted by $bc(f)$ .
polynomial f such that f $=bc(f)$ is said to be boolean closed. Notice that $bc(f)$ is boolean closed.

$A$

Lemma 2.3 Let G be a Grobner basis of an ideal I, then $G’=\{bc(g)|g\in G\}$ also becomes a Grobnerbasis of I.

789
Proof. By the definition of boolean closure, $G’$ is clearly a subset of I. Since $lm(g)=lm(bc(g))$ for eachpolynomial g, \langle $\{lm(g)|g\in G\}\}=\langle\{lm(g)|g\in G’\}\rangle$ . So, $G’$ is a Grobner basis of I by Lem ma 2.2. 1
The following result of [3] will be used for proving our main results.

Lemma 2.4 Let be a commutative ring with identity, which need not to be a von Neumann regular
and $G=\{g_{1}, \ldots, g_{m}\}$ be a finite subset of I. Then thering. Let I be an ideal in a polynomial ringfollowing properties are equivalent:$R$$R[\overline{X}]$

1. $\langle\{lm(f)|f\in I\}\rangle=\langle\{lm(g)|g\in G\}\rangle$
2. For any polynomial $f\in I_{J}f$ has a Grobner representation $w.r.t$ . , that’is there exist polynomials,, $m$ .
and $lt(f)\geq lt(p_{i})lt(g_{i})$ for eachsuch that...,$G$$\mathrm{i}=1$$f= \sum_{i=1}^{m}p_{i}g_{i}$$p_{m}$$p_{1}$$\ldots$

We conclude this section with the following fact.

denotes the polynoand $p\in Spec(B(R))$ ,Lemma 2.5 For a polynomial in a polynomial $nng$$F$,polynomials
.
set
For
a
with
replacingeach
bygiven fromrnial inofcoefficient.
$-\{0\}$ . Let
be a Grobner basis of an ideal I in a polynomial
denotes the set$p\in$
Spec(B (R)).
in the polynomial $rmg$
becomes a Gr\"obner basis of the ideal
Thenfor each$R[\overline{X}]$

$f$

$f$

$R_{p}[\overline{X}]$$a$$mR[\overline{X}]$$a_{p}$$G$$\{f_{\mathrm{p}}|f\in F\}$

$F_{p}$$f_{p}$$\uparrow\dot{u}ngR[\overline{X}]$$R_{p}[\overline{X}\overline{\rfloor}$$G_{p}$$I_{p}\mathrm{J}$there exists an element in $R$ such that $a_{p}=e$ . Hence,
Proof. Notice first that for each element in, from which it
such that
there exists a polynomial infor each polynomial in$G$. In case each element of is boolean closed, this lemma is alreadyis an ideal infollows thatshown in [11]. (Where the converse also holds.) If is not a set of boolean closed polynom ials, let $G’$is also a Grobner$=\{bc(g)|g\in G\}$ . Then $G’$ is also a Grobner basis of I by Lemma 2.3. Therefore,
is a subset of . Let 9 be a polynomial in . Notice the following twobasis of . We claim that
$h$

$a$

$R_{p}$$e$$f$$R_{p}[\overline{X}]$$f_{\mathrm{p}}=h$$R[\overline{X}]$$R_{p}[\overline{X}]$$I_{p}$$G$$G_{p}’$

properties:If$l\mathrm{i}(g)_{p}=0$, then $bc(g)_{p}$ $=0$ .

is 0 or 1 for each
Since
is clearly a subset of ,$l\mathrm{i}(g)_{p}$$p$ )$G_{p}$$I_{p}$$G_{p}$

3$G_{p}$$G_{p}’$$I_{p}$$G$, then $bc(g)_{p}=g_{p}$ .
we have $bc(g)_{p}=0$ or $bc(g)_{p}=g_{p}$ , from which our claim follows. Since.
bner basis of in
is a

If

$l\mathrm{i}(g)_{p}=1$$\mathrm{G}\mathrm{r}\dot{\mathrm{o}}$$R_{p}[\overline{X}]$$I_{p}$$\mathrm{I}$

ACGB

,...’
is not a von Neumann regularover a field $K$ with variables
A polynomial ringcan be considered as
to ,as a function fromring. But considering a polynomial inThis idea leads us to define an ACG#(Alternativea subring of a von Neumann regular ringfollows,
Comprehensive Gr\"obner Basis) as$\overline{A}=A_{1}$$K[\overline{A}]$$A_{m}$$\overline{K}$$K[\overline{A}]$$\overline{K}$$K[\overline{A}]$$\overline{K}^{\overline{K}^{m}}$Definition 3.1 Let $F$ be a finite set of polynomials in a polynomial $nng$,,. Let be a Grobner basis of,
and,variables. is called an ACGB of $F$ with parameters .

$K[\overline{A},\overline{X}]$$\overline{A}=A_{1}$$\overline{K}^{\overline{K}^{m}}[\overline{X}]$$\ldots$$\overline{X}=X_{1}$$A_{m}$$\ldots$$X_{n}$$G$$G$$\overline{A}$$\overline{K}$$\overline{a}=a_{1}$$\langle\{f_{1}(\overline{a}\overline{X}))\} \ldots, f_{s}(\overline{a},\overline{X})\}\rangle$

given frorn(Remember that$7^{\cdot}\cdot lng$

with parameters .
becomes a Grobner basis of the idealof polynomials , ,$F=\{f1(\overline{A},\overline{X}), \ldots :$\overline{K}[\overline{X}]$in the polynomial$\overline{A}$Theorem 3.1 Let $G=\{g_{1}, \ldots, g_{l}\}$ be an ACGB of,,Then, for each $m$ -tmple
of elements in ,. Wheredenotes the setinin$\langle F\rangle$

over a field $K$ wzil$c$$g_{1}$,$\ldots$$\ldots$$G_{\overline{a}}$$a_{m}$$\overline{K}[\overline{X}]$,$\mathit{9}\iota$$G_{\overline{a}}$by replacing each coefficientis an element of$\overline{K}^{\overline{K}^{m}}$

).

$c$

f_{s}(\overline{A},\overline{X})\}$$\{g_{1\overline{a}}, \ldots,g_{l\overline{a}}\}$

with$c(\overline{a})$.

$g_{1\overline{a}}$$\ldots$$g_{l\overline{a}}$200or. Notice that for any element of $R$ , $c^{2}=c$ if and only if
Proof. Let$R$or. Hence, the boolean ring $B\{R$ ) consists of all of such thatfor each element of
$R$
and
for
and
. ( $B(R)$ is not a subring of , the addition offor each elem ent of
B(R)|c(\overline{a})=0\}$$\{c\in
form
Clearly
the
set
Z2.)
in $B(R)$ is defined as the addition of the finite field
and be the prime ideala prime ideal in $B(R)$ for any element of Kr Let be an element of$R$ has the following$\{c\in B(R)|c(\overline{a})=0\}$ . Notice also that the maximal ideal $p_{R}=\{xy|x\in R, y\in p\}$ inis the quotient field $R/pr$ . Since $c-c’\in PR$ if andform: $pu=\{c\in R|c(\overline{a})=0\}$ . Rememb er thatisdefined byfor any and in , the mapping ffom $R/pR$ to
only if. Remember thatis equal toan isomorphism. If we identify $R/p_{R}$ with by this isomorphism,$R=\overline{K}^{\overline{K}^{\pi\iota}}$$c(\overline{a})=0$$c$$\overline{a}$$\overline{K}^{m}$$c(\overline{a})=1$$c(\overline{a})=1$$c(\overline{a})=0$$c$$\overline{K}^{m}$$c$$c’(\overline{a})$$c(\overline{a})$$\overline{a}$$c’$$\mathrm{s}$$\overline{K}$$p$$\overline{a}$$\overline{a}$$R_{p}$$\theta([c]_{pR})=c(\overline{a})$$\overline{K}$

$R$

$c’$

$c$

$\mathrm{c}(\mathrm{a})=c’(\overline{a})$$\theta$$[c]_{pR}$$\overline{K}$$c(\overline{a})$is denoted by . So the theorem follows from Lem ma 2.5.
In ACGB we implicitly assume that a specialization can take any value fromon specializations, we can generalize ACGB as follows.
$[c]_{\mathrm{p}R}$$\mathrm{I}$$c_{\mathrm{p}}$$\overline{K}$. If we give a restriction

Let $F$ be a finite set of polynomials in a polynomial ring
be a subset ofDefinition 3.2 Let.
is called an A $CGB$ on ofin the polynomial ring
. Let be a Grobner basis of$F$with parameters . We simply simply call $G$ an ACGB on of $F$ when is clear from contexts. We
an ACGB on when is an ACGB on of .
also simply call$\overline{K}$$S$$\langle F\rangle$$S$$\overline{A}$$\overline{A}$

$G$

$S$

$G$

$S$

$G$

$S$

$G$

$\overline{K}^{S}[\overline{X}]$$G$$K[\overline{A},\overline{X}]$We have the following theorem by an exactly same proof of Theorem 3.1.
be an ACGB on S of F
and G
Theorem 3.2 Let S be a subset
becomes a Grobner basis of the ideal,. Then, for each $m$ -tuple a- in 3,$=\{g_{1}, \ldots,g\iota\}$$of\overline{K}$$G_{\overline{a}}$$f_{s}(\overline{A},\overline{X})\}$$=\{fi(\overline{A},\overline{X})$$\langle F(\overline{a})\rangle$

in,$\overline{K}[\overline{X}]$$\ldots$.

Notice that we can not generally construct ACGB ’s on for arbitrary set . Even when we can construct
we usually can not represent them in a form of a set of polynomials
ACGB ’s on such as the case
. In the rest of this section, we show that we can always construct ACGB’s on in a form ofinwhen is given in a form of a variety of zero-dimensional ideal.
a set of polynomials inwhich consists of all elements
Let $V$ be the variety of an ideal . Let $K[V]$ denote a subring of$K[V]$
is isomorphic to the quotient ringthat can be represented as polynomial functions. Notice that
]
is
every
for
ideal
, wheredenotes the}. In general,{is zero-dimensional, it becomes a von Neumann
not a von Neumann regular ring. However, in caseis a radical ideaj it can be represented as an intersection of distinct prime ideals
regular ring. Sinceis also zero-dim en sional, so it is maximal. Therefore,. if
is zero-dimensional, eachof fields by the Chinese remainder
is isomorphic to the direct productbecomes a von Neumann regular ring. These observations lead us to have thetheorem. So,
$S$

$S$

$S=\overline{K}$

$S$

)

$S$

$K[\overline{A},\overline{X}]$$S$$K[\overline{A},\overline{X}]$$K^{V}$$I$$K[\overline{A}]/\mathrm{I}(V)$$\overline{a}\in V$$f\in K[\overline{A}]|f(\overline{a})=0$$\mathrm{I}(V)$$K\lfloor\overline{A}$$/\mathrm{I}(V)$$\mathrm{I}(V)$$\mathrm{I}(V)$$P_{1}\cap\cdots\cap P_{k}$$P_{i}$$\mathrm{I}(V)$$K[\overline{A}]/P_{1}\cross$$K[\overline{A}]/\mathrm{I}(V)$$\cdots \mathrm{x}$$K[\overline{A}]/P_{k}$$K[\overline{A}]/\mathrm{I}(V)$following theorem.

be a finite set of polynomials in a polynomial ring
Theorem 3.3 Let,,with variables
and X. Let I be a zero-dimensional proper radical ideal in. Let $G$ be a Grobner basis
becomes a von Neumann regular. Then the quotient ringin. Each coefficient of a polynomial
overof (F) in the polynomial ringHence,.
can, so it can be represented by a polynomial in
is a member of. Therefore,
also be represented as a polynomial in
can be represented by a set of polynomials), . . ., yt. Then, for any -tuple of elements in the algebraic closure of $K${ (} inwhich is a zero of ,becomes a Grobner basis of the ideal.
in$F=\{f_{1}(\overline{A},\overline{X}), \ldots, f_{s}(\overline{A},\overline{X})\}$$\overline{A}=A_{1}$$K[\overline{A},\overline{X}]$$\ldots$$A_{m}$$K[\overline{A}]/I$$K[\overline{A}]$$7^{\cdot}mg$$(K[\overline{A}]/I)[\overline{X}]$$K[\overline{A}]/I$$K[\overline{A}]/I$$(K[\overline{A}1\lrcorner/I)[\overline{X}]$$K[\overline{A}]$$g_{1}$$(\overline{A},\overline{X})$$I$$\overline{K}[\overline{X}]$$K[\overline{A},\overline{X}]$$\{g_{1}(\overline{a},\overline{X}), \ldots,g_{l}(\overline{a},\overline{X})\}$$h(\overline{X})$$G$$K[\overline{A}\overline{X}])$$A-,\overline{X}$$h(\overline{X})$$m$$\overline{K}$$\overline{a}$$\langle f1 (\overline{a},\overline{X}), \ldots, f_{s}(\overline{a},\overline{X})\rangle$

201
Proof. If $K$ is an algebraically closed field, let be the variety of . Since $\mathrm{I}(V)=I$ , $K[V]$ is isomorphic. Thereforetois actually an ACGB on
of $F$ with param term , from which the theorem
directly follows from Theorem 3.2. In case $K$ is not an algebraically closed field, we need to optimize theabove proof. Represent $I=P_{1}\cap\cdots\cap P_{k}$ as an intersection of distinct prime(maximal) ideals in. For
b a zero of . If we put, , ieteach $i=1$ ,for each ,becomes. Define a map boma field which is isomorphic totobyHence,. Then is an isomorphism.
can be considered as a boolean algebra
has a form
which consists of all subsets of 1, , . A prime ideal of. If we denoteby ,for som
can be identified withand
. By Lemma 2.5,
for eachbecomes a Gr\"obner
is equal toin
Since the Grobner basis property is conservativebasis of the ideal.
under a field extension, it is also a Gr\"obner basis in
$V$

$G$

$K[\overline{A}]/I$

$I$

$V$

$\overline{A}$$K[\mathrm{A}]$$\overline{a}_{i}\in\overline{K}$$k$$K_{l}=\{f(\overline{a}_{i})|f(\overline{A})\in K[\overline{A}]\}$$P_{i}$$\mathrm{e}$$\ldots$$K[\overline{A}]/P_{i}$$(f(\overline{a}_{1}), \ldots, f(\overline{a}_{k}))$$\{$$\ldots$$B(K[\overline{A}]/I)$$k\}$$\{s\underline{\subseteq}\{1, \ldots, k\}|\mathrm{i}\not\in s\}$$\langle$$\cdots \mathrm{x}$$K_{i}$$\Phi(f(\overline{A}))=$$K_{k}$$p_{i}$$fi(\overline{a}_{i},\overline{X}))\ldots)$$\{s\subseteq\{1, \ldots, k\}|\mathrm{i}\not\in s\}$$(K[\overline{A}]/I)_{pi}$$f(\overline{A})\in K[\overline{A}]/I$$f(\overline{a}_{i})$$K_{1}\mathrm{x}$$B(K[\overline{A}]/I)$$\Phi$$\mathrm{e}i$$K[\overline{A}]/I$$\Phi$$\prime \mathrm{i}$$K_{i}$$f(\overline{A})_{pi}$$\{g_{1}(\overline{a}_{i},\overline{X}), \ldots, g\iota(\overline{a}_{i},\overline{X})\}$$f_{s}(\overline{a}_{i},\overline{X}))$$K_{i}[\overline{X}]$,$\overline{K}[\overline{X}]$$\mathrm{I}$Stability of Grobner bases

4

In this section we prove our main results. Let us begin with the standard definition of Grobner bases.

over a field $K$ with va riables and .
Definition 4.1 Let I be an ideal of a polynomial ringover the coefficient
as a polynomial $ring$
Let be a finite subset of I. Consider,
iswith a term order $\geq of$. If toe have $\langle\{lm(f)|f\in I\}\rangle=\langle\{lm(g)|g\in G\}\rangle$ in.
.r.tcalled a Gr\"obner basis of I in
$G$$(K[\overline{A}])[\overline{X}]$$K[\overline{A},\overline{X}]$$\mathit{7}Yng$$G$$T(\overline{X})$$(K[\overline{A}])[\overline{X}]$$K[\overline{A}]$$(K[\overline{A}])[\overline{X}]\mathrm{w}$$\overline{X}$$\overline{A}$$K[\overline{A},\overline{X}]$$\geq$The next fact is a special instance of a well-known result shown in [8, 14].

over a field $K$ with variables andProposition 4.1 Let I be an ideal of a polynomial $nng$. Let
is a zero-dimensional proper radical ideal insuch that$\geqof$
as a set of$w.r.t$. If we consider
order
.
a
term
be a Gr\"obner basis of I in,over the von Neumann regular ring
polynomials in a $polynom\iota al$ ring.
then atso becomes a Gr\"obner basis in this polynomial $nng$ .r.t
$G=\{g_{1}(\overline{A},\overline{X}), \ldots, gl(\overline{A},\overline{X})\}$$K[\overline{A}]$$I\cap K[\overline{A}]$$T(\overline{X})$$(K[\overline{A}])[\overline{X}]$$\overline{X}$$\overline{A}$$K[\overline{A},\overline{X}]$$G$$K[\overline{A}]/I\cap K[\overline{A}]$$(K[\overline{A}]/I\cap K[\overline{A}])[\overline{X}]$$G$$\mathrm{w}$$\geq$

Together with Theorem 3.3, we directly have the following.
isover a field $K$ such that
Theorem 4.2 Let I be an ideal of a polynomial ring.
zero-limensional radical ideal in$w.r.t$ . a term order $\geq of$.
be a Gr\"obner basis of I inLet.
Let be an $m$ -tuple of elements of the algebraic closureof $K$ which is a zero of the ideal
becomesbecomes a Gr\"obner basis with the specialization by , that is
Then,
$r.t$
.
.
in
Grobner basis of the ideal$I\cap K[\overline{A}]$$K[\overline{A},\overline{X}]$$a$$K[\overline{A}]$$G=\{g_{1}(\overline{A}, \mathrm{X}), \ldots, g_{l}(\overline{A},\overline{X})\}$$T(\overline{X})$$(K[\overline{A}])[\overline{X}]$$I\cap K[\overline{A}]$$\overline{K}$$\overline{a}$$G$$\{g_{1}(\overline{a},\overline{X}), \ldots, g_{l}(\overline{a},\overline{X})\}$$\overline{a}$$\langle g_{1}(\overline{a},\overline{X}), \ldots,g_{l}(\overline{a},\overline{X})\rangle$$\overline{K}[\overline{X}]w$$a$$\geq_{-}$

is not a proper ideal, the result is trivial, otherwise aPPly Proposition 4.1 andProof. When
Theorem 3.2.
We can get a slightly stronger result as follows.
$I\cap K[\overline{A}]$Definition 4.2 Let
K. $Let\geq be$ a term order ofis said to be strongly stable for$G=\{g_{1}(\overline{A}_{1}\overline{X}), \ldots , g\iota(A,\overline{X})\}$$T(\overline{X})$and a be an$\overline{a}w.r.t$.

$m$vnth a field
be a finite set of polynomials of$K’$-tmple of elements of some extension fieldof K.
becomes a Gr\"obner basis of the$\geq\iota f$ $\{g_{n_{1}}(\overline{a},\overline{X}), \ldots, \mathit{9}n_{k}(\overline{a},\overline{X})\}$$K[\overline{A},\overline{X}]$

$G$

202
in
. $r.t$ .
where
ideal
.( We consider as a polynomial insuch that$G$. $r.t$ .
is also simply said to be stable for$K’[\overline{X}]w.r.t$ .
.
in
the ideal$K’[\overline{X}]w$$\langle g_{1}(\overline{a},\overline{X}), \ldots 7 g_{l}(\overline{a},\overline{X})\rangle$$lc(g)(\overline{a})\neq 0$$g$$\geq if$$\overline{a}w$

is the set of all polynomials of $G$, so $lc(g)$ is a polynomial in)
becomes a Grobner basis of$\{g_{n_{1}}, \ldots:\mathit{9}n_{k}\}$$\geq_{l}$$\langle g_{1}(\overline{a},\overline{X}), \ldots, g_{l}(\overline{a}, X)\rangle$$(K[\overline{A}])[\overline{X}]$$g$$K\underline{\lceil}\overline{A}].$$\{g_{1}(\overline{a},\overline{X}), \ldots, g\iota(\overline{a},\overline{X})\}$$\geq$The strong stability condition is actually much stronger than the stability condition.
Example 1.

Let $G=\{A*X_{1}+X_{2}-1, X_{2}^{2}-1\}$ with a lexicographic term order $X_{1}>X_{2}$ . Then is not strongly stable, but is stable for 0 i.e. {X2-1, $X_{2}^{2}-1$ }for 0 since $\{X_{2}^{2}-1\}$ is not a Grobner basis of {
$G$

$G$

$\mathrm{X}2-1_{7}X_{2}^{2}-1\rangle$

is a Gr\"obner basis of X2 –1,$\langle\langle$$X_{\underline{9}}^{2}-1\rangle$

Corollary 4.3 Let I be an ideal of a polynomial ring$K[\overline{A},\overline{X}]$over a field $K$ such that$I\cap K[\overline{A}]$.
zero-dimensional radical ideal in$w.r.t$ . a term order $\geq of$
be a Grobner basis of I inLet
$K$Let be an $m$ -tuple of elements of the algebraic closureof which is a zero of the ideal.
.
Then is strongly stable for

is

$a$

$K[\overline{A}]$$G=\{g_{1}(\overline{A},\overline{X}), \ldots , g\iota(\overline{A},\overline{X})\}$$\overline{K}$$\overline{a}$$G$$T(\overline{X})$.

$I\cap K[\overline{A}]$.

$(K[\overline{A}])[\overline{X}]$$\overline{a}w.r.t$$\geq$in Definition 8 correspond toandProof. Notice that
,
,
by {
and
in the proof of Lemma 2.5. So we can replacein Theorem 3.3, from which our corollary follows.l
By Proposition 1, the following facts are direct consequences from Proposition 41 and Corollary 4.3.
$\{g_{n_{1}}(\overline{a},\overline{X}), \ldots,g_{n_{k}}(\overline{a},\overline{X})\}$$G_{p}’$$\{g_{1}(\overline{a},\overline{X}), \ldots, \mathit{9}\iota(\overline{a},\overline{X})\}$$\{g_{1}(\overline{a},\overline{X}), , , .

$G_{p}$, g\iota(\overline{a},\overline{X})\}$$g_{n_{1}}(\overline{a},\overline{X})$$\ldots$$g_{n_{k}}(\overline{a},\overline{X})\}$

over a field $K$ with variables and $X$ such
Theorem 4.3 Let I be an ideal of a polynomial ring
, . . . , qt)} be
. Let $G=$ {thai
is a zero-dimensional proper rachcal ideal in
Gr\"obner basis of I $w.r.t$ . a term order $\geq such$ that each variable
is greater than any term in. If$N$over the von eumann
we consider as a set of polynomials in the polynomial ringin this polynomial ring
, then also becomes a Grobner basis of the ideal
regular ring$w.r.t$ . the term order that is a restriction $of\geq on$.
$\overline{A}$$K[\overline{A},\overline{X}]$$K[\mathrm{A}]$$I\cap K[\overline{A}]$$g_{1}(\overline{A},\overline{X})$$(\overline{A},\overline{X}$

$G$

$a$

$T(\overline{A})$$X_{i}$$(K[\overline{A}]/I\cap K[\overline{A}])\lfloor.\overline{X}]$$G$$K[\overline{A}]/I\cap K[\overline{A}]$$\langle G\rangle$$T(\overline{X})$Corollary 4.5 Let I be an ideal of a polynomial ringover a field $K$ such thatis.
zero-dimensional radical ideal inLet
be a Grobner basis of I $w.r.t$ . a term order $\geq such$ that each variable
is greater than any term in. Let be an $m$ -tuple of elements of the algebraic closure of $K$. Then,. the term order that iswhich is a zero of the ideal
is strongly stable for.
restriction $of\geq on$$I\cap K[\overline{A}]$$K[\overline{A},\overline{X}]$$a$$K[\overline{A}]$$G=\{g_{1}(\overline{A},\overline{X}), \ldots, g\iota(\overline{A},\overline{X})\}$$\overline{K}$$T(\overline{A})$$X_{i}$$\overline{a}$$G$$I\cap K[\overline{A}]$$\overline{a}w.r.t$$a$$T(\overline{X})$

We conclude this section by the following fact which is a redescription of Lemma 1 in terms of ACGB.
Proposition 4.6 Let J be an ideal offollowing properties.

1. There eits an ideal I of
is not an ACGB on $V(J)$ .

$K[\overline{A}, X]$$K[\overline{A}]$such that J is not a 0-dimensional ideal, then we have thesuch that$I\cap K[\overline{A}]$$=J$ and any Grobner basis $G$of I in$(K[\overline{A}])[X]$

2. In case the number of is rnore than 1 with an additional assumption that is not a radical ideal,
there eits an ideal I ofsuch that $I\cap K[\overline{A}]=J$ and any Grobner basis of I in
is not an ACGB on $V(J)$ .
$\overline{X}$$K[\overline{A},\overline{X}]$

$J$

$G$

$(K[\overline{A}])[\overline{X}]$203
Computation of parametric Grobner bases5. Com pute a Grobner
be a finite set of polynomials inLetof the ideal
w.r.t. a term order such that any
basis, whereis a set of all polynomials in thatis greater than any term invariableIn
is a zero dimensional
empty
might
,
it
be
an
set.
case
variableany
do not include,,,
becomes a parametric Grobner basis of $F$ that is {radical ideal infor any -tuple ofinbner basis of the ideal
becomes a
...7
not
a
zero
dimensional radicaliselements of , as is shown in Corollary 4.5. When
ideal, is not a parametric Gr\"obner basis of in general. If we want to construct a param etric Gr\"obnerbasis of using , the most interesting question is whether we can construct a computable condition ofwhich is necessary and sufficient for to be stable for w.r.t. .
With a minor change, that is replacing ’stable’ by ’strongly stabl\’e, we can construct such a condition.
using the following fact which is also presented in$F=\{f1(\overline{A},\overline{X}), \ldots, f_{s}(\overline{A}.,\overline{X})\}$$K[\overline{A},\overline{X}_{\rfloor}^{\rceil}$$G=\{g_{1}(\overline{A},\overline{X}), \ldots,g\iota(\overline{A},\overline{X}), h_{1}(\overline{A}), \ldots , h_{k}(\overline{A})\}$$\langle h_{1}(\overline{A}), \ldots, h_{k}(\overline{A})\rangle$$X_{:}$$K[\mathrm{A}]$$G$$g_{1}(\overline{a},\overline{X}))\ldots$$g\iota(\overline{a},\overline{X}))h_{1}(\overline{a})$$\overline{K}[\overline{X}]$$\langle f1(\overline{a},\overline{X}), \ldots, f_{s}(\overline{a},\overline{X})\rangle$$\mathrm{G}\mathrm{r}\dot{\mathrm{o}}$$h_{k}(\overline{a})\}$$G$$\{h_{1}(\overline{A}), \ldots, h_{k}(\overline{A})\}$$T(\overline{A})$$X_{i}$$\geq$$\langle F\rangle$$\overline{a}$$\mathrm{m}$$\langle h_{1}(\overline{A}), \ldots) h_{k}(\overline{A})\rangle$$\overline{K}$

$F$

$G$

$G$

$F$

$G$

$\overline{a}$$\geq$$\overline{a}$$[2](\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{m}3.1)$

beLet
Theorem 5.1 Let I be an ideal of a polynomial ring
. Let be an $m$ -tuple of elements of the. $r.t$ . a term order $\geq of$
Grobner basis of I in
algebraic closure
be the set of all polynomials of $G$ such
. Let
of $K$ which is a zero of the ideal
becomes. $r.t$ . , that is
is strongly stable forthat $lc(g)(a)\neq 0$ . Thenis reducible to 0 modulo, if and only if
Grobner basis offor every 9 in .
$G=\{g_{1}(\overline{A},\overline{X}), \ldots,g\iota(\overline{A},\overline{X})\}$$K[\overline{A},\overline{X}^{\mathrm{r}}\rfloor\cdot$$(K[\overline{A}])[\overline{X}]$$T(\overline{X})$$w$$I\cap K[\overline{A}]$$\overline{K}$$g$$\{g_{\mathrm{n}_{1}}, \ldots, g_{\mathrm{n}_{k}}\}$$G$$\overline{a}w$$a$$\overline{a}$$a$$\{g_{n_{1}}(\overline{a},\overline{X}), \ldots 2 g_{n_{k}}(\overline{a},\overline{X})\}$$\geq$$g(\overline{a},\overline{X})$$\langle g_{1_{\iota}^{(}}\overline{a},\overline{X}), \ldots, g\iota(\overline{a},\overline{X})\rangle$$G$$\{g_{n_{1}}(\mathrm{a}),\overline{X}), \ldots, g_{n_{k}}(\mathrm{a}),\overline{X})\}$

Algorithm 1.
Let I and be as in the above theorem. We can compute an algebraically constructible set such thatbe a binary
if and only if is strongly stable for aw.r.t. . We calland $\{p_{1}, \ldots,p_{r}\}\cup\{q_{1}, \ldots, q_{s}\}=G$ . (When $r=0(s=$par tition of , if
to denote an empty set.) For such a binary partition, we abuse the notation. Compute a, we put a case distinction
be the set, . Let,for eachinnormal form of modulo
that is a numerator of some coefficient of some . For each a that satisfies
of all polynomials of
if and onlyis strongly stable for w.r.t.
all conditions of the case distinction Cp, we can see that
, , by the theorem. Let $C_{\rho}’=\{h_{1}=0, \ldots, ht=0\}\cup C_{\rho}$ and,for every
if. Thensatisfies all conditions of } and put an algebraically constructible set
{
$S$

$G$

$G$

$\overline{a}\in S$$G$$\rho=$ $(\{p_{1}, \ldots ,p_{r}\}, \{q_{1}, \ldots, q_{s}\})$$\geq$$\{p_{1}, \ldots,p_{r}\}\cap\{q_{1}, \ldots, q_{s}\}=\emptyset$$\{p_{1}, \ldots,p_{r}\}(\{q_{1}, \ldots, q_{s}\})$$0)$$C_{\rho}=\{lc(p_{1})\neq 0_{2}\ldots, lc(p_{r})\neq 0, \mathrm{l}\mathrm{c}(\mathrm{q}\mathrm{i})=0, \ldots, lc(q_{s})=0\}$$\rho$$q_{i}’$$\{p_{1}, \ldots,p_{r}\}$$q_{i}$$\mathrm{i}=1$$K(\overline{A})[\overline{X}]$$\ldots$$q_{i}’$$K[\overline{A}]$$G$$\mathrm{i}=1$$\mathrm{h}\mathrm{i}(\mathrm{a})=0$$\{h_{1}, \ldots , h_{t}\}$$s$$\ldots$$a-\in\overline{K}|\overline{a}$$\geq$$\overline{a}$$S_{\rho}=$$t$$S= \bigcup_{\rho}S_{\rho}$$C_{\rho}’$$S$

has the desired property.

The above algorithm is simple and fast when we do not have so many binary partitions. When 1 is notdoes not include any polynomial consisting of only variables , we have to takesmall, however, if
care of many case distinctions, which of course is not a light job. This difficulty is overcome by using
ACGB. The following algorithm produces the above algebraically constructible set with a minim um
cost. Using the output of the algorithm we can also get an ACGB of , which can be considered as a$\overline{A}$$G$$2^{l}$$S$$I$

param etric Gr\"obner basis of .
$I$

Algorithm 2.
Let I and be as in the above theorem. For each$G$$\mathrm{i}=1$, . . . ’ , compute a normal form$l$$g_{i}’$

of$\mathit{9}i$modulo$G$

204
over the von Neumann regular ring which is defined as the sm allest von. is defined as a computable ring using so calledthat includes
Neumann regular subring ofis not necessary to be 0 since we do not generally haveterrace. (See [10] for more detail) Notice thatthe property $farrow f0$ in a polynomial ring over a von Neumann regular ring, Put $G’=\{g_{1}’$ , . . . , . Let,
be the set of all coefficients which appear in some polynomial . Let
potent
pair
any
of
idem
elements
andwhere is a boolean sum, i.e. $x\vee y$ is defined by $x+y+xy$ for:. has the following property for any
in the polynomial ring$T$$T[\overline{X}]$$\overline{K}^{\overline{K}^{m}}$$K[\overline{A}]$$T$$g_{\dot{\mathrm{z}}}’$$g_{l}’\}$$g_{i}’$$\{\#\mathrm{i}, \ldots, \theta_{N}\}$$\theta=\theta^{*}\mathrm{i}\vee\cdots\vee\theta_{N}^{*}$$x$$\vee$$\overline{a}\in\overline{K}$$y$$\theta$$\theta(\overline{a})=\{$

9{

1if
0

for some$\mathrm{a})\neq 0$$i$otherwise.

Notice the fact that normal forms of monomial reductions by a set of boolean closed polynom ts inthenis irreducible byandare specialization invariant, that is, if
for any -tuple of elements of and any set
is irreducible byand$H$ of boolean closed polynomials in. Sinceand $arrow bc(h)$ do an exactly same monomial reduction,:
we have the following property for any -tuple of elements of and any set $H$ of polynomials in$T[\overline{X}]$$\mathrm{i}$$f(\overline{A}, X)arrow H*f’(A,\overline{X})$$f’(\overline{A}\overline{X}))$$arrow H$$\overline{K}$$f(\overline{a},\overline{X})$$arrow H_{\overline{a}}*$$f’(\overline{a},\overline{X})$$/(\mathrm{a},\overline{X})$$arrow H_{\overline{a}}$$T[\overline{X}]$$\overline{a}$$\mathrm{m}$$arrow h$$T[\overline{X}]$$\overline{K}$$\overline{a}$$\mathrm{m}$

If
then

$f(\overline{A},\overline{X})$$arrow H*f’(\overline{A},\overline{X})$$f(\overline{a},\overline{X})$

and
and

$f’(\overline{A},\overline{X})$$arrow H_{\overline{a}}’*f’(\overline{a},\overline{X})$is irreducible by$f’(\overline{a},\overline{X})$is irreducible$arrow H$$\mathrm{b}\mathrm{y}arrow H\acute{\frac{}{a}}$.

(Where $H’=\{bc(h)|h\in H$ }.)Notice also that $bc(h)(\overline{a})=0$ if and only if $lc(h)(\overline{a})=0$ . Hence, with the above property of , we can see.
that is strongly stable for if and only if
in a form of algebraically constructible
express
the setNotice also that we can also
set using the structure of terrace. For the construction of , boolean simplification is also useful.
We can further obtain a parametric Grobner basis of I in a form of ACGB as follows.
,ofLetand compute a Gr\"obner basis
formsin. (Notice thatis nothing but an ACGB on
of $G.$ ) Then, that is
a Gr\"obner basis of I in
is an ACGB of .
$\theta$$G$$\theta(\overline{a})=0$$\overline{a}$$S=\{\overline{a}\in\overline{K}|\theta(\overline{a})=0\}$$S$$G_{1}=\{(1-9)\mathrm{g}\mathrm{i}\}\ldots$$\{\theta g_{1}, \ldots , \theta g\iota\}$$(1-\theta)g\iota\}$$\overline{K}^{m}\backslash S$$G_{2}$$T[\overline{X}]$$T[\overline{X}]$6$G_{2}$$G_{1}\cup G_{2}$$G_{1}\cup G_{2}$$I$

Conclusions and Remarks

Theorem 1.2 is given in more general situations in terms of a homomorphism from an arbitrary commutative ring $R$ to a field.(See theorem 3.2 and 3.3 in [2]). In our situation that is $R$ is a polynomial ringover a field $K$ , it is equivalent to Theorem 1.2 since a homomorphism is nothing but a specializationand its kernel is a maximal ideal.
The stability property defined in [2] corresponds to the strong stability property defined in this paper.
We use this terminology since it reflects its meaning more precisely and there is a closed relationshipbetween its notion and the notion of monomial reductions in polynomial rings over von Neumann regularrings as is shown in this paper.
Three theorems of section 3 are originally given for boolean closed Grobner bases in [6, 9, 10]. In this
PaPer, we optimize our proofs so that the theorems hold for arbitrary Gr\"obner bases$K[\overline{A}]$205
References[1] Becker,T. (1994). On Grobner Bases under Specialization. Applicable Algebramunication and Computing. 5, 1-8.

$\ln$

Engineering, Com-

[2] Kalkbrener,M. (1997). On the Stability of Grobner Bases Under Specializations. J. Symb. Comp.
24/1, 51-58.
[3]$\mathrm{M}\dot{\mathrm{o}}$ller,H.M. (1988). On the Construction of Gr\"obner Bases Using Syzygies. J. Symb. Comp. 6/2-3,

345-359.
[4]$\mathrm{M}\mathrm{o}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{s},\mathrm{A}.(2002)$. A New Algorithm for Discussing Gr\"obner Bases with Parameters J. Symb. Comp.

33/2, 183-208.

[5] Sato, Y. (1998). A new type of canonical Grobner bases in polynom ial rings over Von Neum ann
regular rings. International Symposium on Symbolic and Algebraic Computation (ISSAC 98), Proceedings, 317-321.
[6] Sato, Y, Suzuki, A. and Nabeshim a, K. (2003). ACGB on Varieties, Proceedings of the Sixth International Workshop on Computer Algebra in Scientific Computing(CASC 2003), 313-318.
[7] Saracino, D., Weispfenning, V. (1975). On algebraic curves over commutative regular rings, Model
Theory and Algebra, a memorial tribute to A. Robinson, Springer LNM 498, 307-387.
[8] Spear, D.A. (1977). A constructive approach to commutative ring theory, Proc. of the 1977 MACSYMA Users’ Conference, NASA CP-2012, 369-376.
[9] Suzuki, A. and Sato, Y. (2002). An Alternative approach to Comprehensive Gr\"obner Bases. International Symposium on Symbolic and Algebraic Computation (ISSAC 2002), Proceedings, 255-261.
[10] Suzuki, A. and Sato, Y.(2003). An Alternative approach to Comprehensive Grobner Bases. J. Symb.
Com p. 36/3-4649-667.

[11] Weispfenning, V. (1989). Grobner bases in polynom ial ideals over commutative regular rings, EUROCAL ’87, J. H. Davenport Ed., Springer LNCS 378, 336-347,[12] Weispfenning, V. (1992). Com prehensive Grobner bases, J. Symb. Comp. 14/1, 1-29.
[13] Weispfenning, V. (2002). Com prehensive Grobner bases and regular rings, Symposium in Honor of
Bruno Buchberger’s 60th Birthday (LMCS 2002) Proceedings, 256-265.

[14] Zacharias, G. (1978). Generalized Gr\"obner bases in commutative polynom ial rings, Bachelor’s thesis,
M.I.T.