reduce-historical/r35/lib/ideals.tex

\documentstyle[12pt]{article}
\begin{document}
\begin{center} {\Large Polynomial Ideals} \end{center}
\begin{center} Arithmetic for polynomial ideals supported by 
Gr\"obner bases \end{center}
\begin{center} Version 1.0 May 1992 \end{center}

\begin{center} Herbert Melenk \\ Konrad-Zuse-Zentrum f\"ur
Informationstechnik \\
Heilbronner Str. 10 \\ D1000 Berlin 31 \\ Federal Republic of Germany \\ 
melenk@sc.zib-berlin.de \\ May 1992 \end{center}

\section{Introduction}

This package implements the basic arithmetic for polynomial ideals
by exploiting the Gr\"obner bases package of REDUCE.
In order to save computing time all intermediate Gr\"obner bases
are stored internally such that time consuming repetitions
are inhibited. A uniform setting facilitates the access.

\section{Initialization}

Prior to any computation the set of variables has to be declared
by calling the operator $I\_setting$ . E.g. in order to initiate
computations in the polynomial ring $Q[x,y,z]$ call
\begin{verbatim}
    I_setting(x,y,z);
\end{verbatim}
A subsequent call to $I\_setting$ allows one to select another set
of variables; at the same time the internal data structures
are cleared in order to free memory resources.

\section{Bases}

An ideal is represented by a basis (set of polynomials) tagged
with the symbol $I$, e.g.
\begin{verbatim}
   u := I(x*z-y**2, x**3-y*z);
\end{verbatim}
Alternatively a list of polynomials can be used as input basis; however,
all arithmetic results will be presented in the above form. The
operator $ideal2list$ allows one to convert an ideal basis into a
conventional REDUCE list.

\subsection{Operators}

Because of syntactical restrictions in REDUCE, special operators
have to be used for ideal arithmetic: 

\begin{verbatim}
         .+            ideal sum (infix)
         .*            ideal product (infix)
         .:            ideal quotient (infix)
         ./            ideal quotient (infix)
         .=            ideal equality test (infix)
         subset        ideal inclusion test (infix)
         intersection  ideal intersection (prefix,binary)
         member        test for membership in an ideal
                         (infix: polynomial and ideal)
         gb            Groebner basis of an ideal (prefix, unary)
         ideal2list    convert ideal basis to polynomial list 
                         (prefix,unary)
\end{verbatim}

Example:

\begin{verbatim}
    I(x+y,x^2) .* I(x-z);

      2                      2    2
   I(X  + X*Y - X*Z - Y*Z,X*Y  - Y *Z)
\end{verbatim}

The test operators return the values 1 (=true) or 0 (=false)
such that they can be used in REDUCE $if-then-else$ statements
directly.

The results of $sum,product, quotient,intersction$ are ideals
represented by their Gr\"obner basis in the current setting and
term order. The term order can be modified using the operator
$torder$ from the Gr\"obner package. Note that ideal equality 
cannot be tested with the REDUCE equal sign:

\begin{verbatim}

   I(x,y)  = I(y,x)       is false
   I(x,y) .= I(y,x)       is true

\end{verbatim}

\section{Algorithms}

The operators $groebner$, $preduce$ and $idealquotient$ of the 
REDUCE Gr\"obner package support the basic algorithms:

$GB(Iu_1,u_2...) \rightarrow groebner(\{u_1,u_2...\},\{x,...\})$

$p \in I_1 \rightarrow p=0 \ mod \ I_1$

$I_1 : I(p) \rightarrow (I_1 \bigcap I(p)) / p \ elementwise$

\noindent
On top of these the Ideals package implements the following 
operations:


$I(u_1,u_2...)+I(v_1,v_2...) \rightarrow GB(I(u_1,u_2...,v_1,v_2...))$


$I(u_1,u_2...)*I(v_1,v_2...)\rightarrow 
 GB(I(u_1*v_1,u_1*v2,...,u_2*v_1,u_2*v_2...))$


$I_1 \bigcap I_2 \rightarrow
  Q[x,...] \bigcap GB_{lex}(t*I_1 + (1-t)*I_2,\{t,x,..\}) $


$I_1 : I(p_1,p_2,...) \rightarrow I_1 : I(p_1) \bigcap I_1 : I(p_2)
\bigcap ...$

$I_1 = I_2 \rightarrow GB(I_1)=GB(I_2)$

$I_1 \subseteq I_2
   \rightarrow \ u_i \in I_2 \ \forall \ u_i \in I_1=I(u_1,u_2...)$

\section{Examples}

Please consult the file $ideals.tst$.
\end{document}