University of Vlora - Conference Center, ACA'10, Applications of Computer Algebra

Font Size:  Small  Medium  Large

Stability of Gr\"obner Bases in terms of a commutative von Neumann regular ring

Yosuke Sato

Last modified: 2010-05-28

Abstract


Let $K$ be a field and $K'$ be its extension field.
$K[\bar A,\bar X]$ denotes a polynomial ring with variables
$\bar A=A_1,\ldots,A_m$ and $\bar X=X_1,\ldots,X_n$.
Let $\sigma$ be a homomorphism from $K[\bar A]$
to $K'$, i.e. a specialization of $\bar A$ with
elements $a_1,\ldots,a_m$ of $K'$, it is also naturally extended to
a homomorphism from $K[\bar A,\bar X]$ to $K'[\bar X]$.
We fix a term order $>$ of $\bar X$,  
$LM(h)$ and $LT(h)$ denotes the leading monomial and the
leading term of $h$ $\in K[\bar A,\bar X]$ w.r.t. $>$
regarding $K[\bar A,\bar X]$ as a polynomial
ring $(K[\bar A])[\bar X]$
over the coefficient ring $K[\bar A]$.
The following fact plays an important role in
Suzuki-Sato's algorithm to compute comprehensive Gr\"obner Systems \cite{SuSa06}.
\\ \\
{\bf Lemma 1}
\\
Let $I$ be an ideal of $K[\bar A,\bar X]$ and $G$ be its Gr\"obner basis
w.r.t. $>$
regarding $K[\bar A,\bar X]$ as a polynomial
ring $(K[\bar A])[\bar X]$
over the coefficient ring $K[\bar A]$. Let $G$ $=$ $\{ g_1,\ldots,g_s,\ldots,g_t\}$
such that $G\cap K[\bar A] = \{ g_{s+1},\ldots,g_t\}$.
If $\sigma(LM(g_1))\not=0,\ldots,\sigma(LM(g_s))\not=0$ and
$\sigma(g_{s+1})=0,\ldots,\sigma(g_t)=0$,
then $\sigma(G)$ $=$ $\{ \sigma(g_1),\ldots,$
$\sigma(g_s)\}$ is a
Gr\"obner basis of $\langle\sigma(I)\rangle$ w.r.t. $>$.
Where,  $\langle\sigma(I)\rangle$ denotes the
ideal of $K'[\bar X]$ generated by $\sigma(I)$.
\\ \\
This lemma is a special instance of the following theorem shown as
Theorem 3.1 in \cite{Kal97}.
\\\\
{\bf Theorem 1}
\\
Using the same notations as in the above lemma,
If $G$ $=$ $\{ g_1,\ldots,g_s,\ldots,g_t\}$
satisfies that $\sigma(LM(g_1))\not=0,\ldots,\sigma(LM(g_s))\not=0$ and
$\sigma(LM(g_{s+1}))=0,\ldots,$
$\sigma(LM(g_t))=0$.
Then $G'$ $=$ $\{ \sigma(g_1),\ldots,\sigma(g_s)\}$ is a Gr\"obner basis
of $\langle\sigma(I)\rangle$ in $K'[X]$ if and only if
$\sigma(g_i)\stackrel{*}{\to}_{G'}0$ for each $i=s+1,\ldots,t$.
\\ \\
The above lemma is further extended
in \cite{KaSuWa10} and \cite{Ku10}
independently for improving Suzuki-Sato's algorithm.
\\ \\
{\bf Lemma 2}(\cite{KaSuWa10} and \cite{Ku10})
\\
Using the same notations as in the above lemma,
let $G$ $=$ $\{ g_1,\ldots,g_s,\ldots,g_t\}$
such  that $G\cap K[\bar A] = \{ g_{s+1},\ldots,g_t\}$ and
$\sigma(g_{s+1})=0,\ldots,\sigma(g_t)=0$.
Let $\{ LT(g_{n_1}),\ldots,LT(g_{n_l})\}$ be the minimal subset of
$\{ LT(g_1),\ldots,LT(g_s)\}$ concerning the order of divisibility,
that is each term of $\{ LT(g_1),\ldots,LT(g_s)\}$ is divisible by
some term of $\{ LT(g_{n_1}),\ldots,LT(g_{n_l})\}$ and
any term of $\{ LT(g_{n_1}),\ldots,LT(g_{n_l})\}$ is not divisible
by others.
Then $G'$ $=$ $\{ \sigma(g_{n_1}),\ldots,\sigma(g_{n_l})\}$ is a Gr\"obner basis of
$\langle\sigma(I)\rangle$ w.r.t. $>$ regardless whether
$\sigma(LM(g_i))=0$ or not for each $i \in
\{1,\ldots,s\}-\{n_1,\ldots,n_l\}$.
\\ \\
At a glance, this extension looks a new result, however, unfortunately
it is a special instance of the following theorem which is an extension
of Theorem 1.
\\ \\
{\bf Theorem 2}
\\
Using the same notations as in the above lemma,
If $G$ $=$ $\{ g_1,\ldots,g_u,\ldots,g_s,\ldots,$
$g_t\}$
satisfies that $\sigma(LM(g_1))\not=0,\ldots,\sigma(LM(g_u))\not=0$,
each term of $\{ LT(g_{u+1}),$
$\ldots,LT(g_{s})\}$
is divisible by some term of $\{ LT(g_1),\ldots,LT(g_{u})\}$
but none of $\{ LT(g_{s+1}),\ldots,LT(g_t)\}$ is divisible by
any term of $\{ LT(g_1),\ldots,LT(g_{u})\}$ and\\
$\sigma(LM(g_{s+1}))=0,\ldots,$
$\sigma(LM(g_t))=0$.
Then $G'$ $=$ $\{ \sigma(g_1),\ldots,\sigma(g_u)\}$ is a Gr\"obner basis
of $\langle\sigma(I)\rangle$ in $K'[X]$ if and only if
$\sigma(g_i)\stackrel{*}{\to}_{G'}0$ for each $i=s+1,\ldots,t$.
\\ \\
If we carefully read the proof of Theorem 1, then we should notice
the above extension is actually proved. However, the proof is based
on stability of initials of ideals and it seems far from a natural and
simple proof.
\\ \\
In this presentation, we give a simple and natural proof
of Theorem 2 using the the theory of Gr\"obner bases
in a polynomial ring over a commutative von Neumann regular ring
introduced in \cite{We89} and studied in \cite{SuSa03} from a viewpoint of
comprehensive Gr\"obner systems.
We also show that several results concerning stability of Gr\"obner
bases obtained in \cite{Kal97} and others are {\em trivial}
with the theory of
Gr\"obner bases
in a polynomial ring over a commutative von Neumann regular ring.

\begin{thebibliography}{99}
\bibitem{Kal97}
 Kalkbrener, M.
  On the Stability of Gr\"obner Bases Under Specializations.
   \textit{J. Symbolic Computation}. Vol. 24/1, pp. 51--58. 1997.

\bibitem{KaSuWa10}
Kapur, D., Sun, Y. and Wang, D.
A New Algorithm for Computing Comprehensive Gr\"obner Systems.
To appear in ISSAC2010.

\bibitem{Ku10}
Kurata, Y.
Improving Suzuki-Sato’s CGS Algorithm by Using
Stability of Gr\"obner Bases and Basic Manipulations for
Efficient Implementation.
To appear in Communications of JSSAC.

\bibitem{SuSa03}
         Suzuki, A. and Sato, Y.
         An alternative approach to Comprehensive Gr\"obner Bases.
         \textit{J. Symbolic Computation}. Vol. 36/3-4,
         pp. 649--667. 2003.

\bibitem{SuSa06}
     Suzuki, A. and Sato, Y.
     A Simple Algorithm to Compute Comprehensive Gr\"obner Bases
     Using Gr\"obner Bases.
     \textit{Proc. International Symposium on Symbolic and Algebraic
     Computation (ISSAC '06)}, ACM Press, New York,
    pp. 326--331. 2006.

\bibitem{We89}
Weispfenning, V.
Gr\"obner bases in polynomial ideals over commutative regular
rings. In Davenport Ed., editor, EUROCAL’87, pages 336–347
Springer LNCS 378, 1989.

\end{thebibliography}

\end{document}