1\documentstyle[12pt]{article}
2\begin{document}
3\begin{center} {\Large Polynomial Ideals} \end{center}
4\begin{center} Arithmetic for polynomial ideals supported by
5Gr\"obner bases \end{center}
6\begin{center} Version 1.0 May 1992 \end{center}
7
8\begin{center} Herbert Melenk \\ Konrad-Zuse-Zentrum f\"ur
9Informationstechnik \\
10Takustra\"se 7 \\ D14195 Berlin--Dahlem \\ Federal Republic of Germany \\
11melenk@zib.de \\ May 1992 \end{center}
12
13\section{Introduction}
14
15This package implements the basic arithmetic for polynomial ideals
16by exploiting the Gr\"obner bases package of REDUCE.
17In order to save computing time all intermediate Gr\"obner bases
18are stored internally such that time consuming repetitions
19are inhibited. A uniform setting facilitates the access.
20
21\section{Initialization}
22
23Prior to any computation the set of variables has to be declared
24by calling the operator $I\_setting$ . E.g. in order to initiate
25computations in the polynomial ring $Q[x,y,z]$ call
26\begin{verbatim}
27    I_setting(x,y,z);
28\end{verbatim}
29A subsequent call to $I\_setting$ allows one to select another set
30of variables; at the same time the internal data structures
31are cleared in order to free memory resources.
32
33\section{Bases}
34
35An ideal is represented by a basis (set of polynomials) tagged
36with the symbol $I$, e.g.
37\begin{verbatim}
38   u := I(x*z-y**2, x**3-y*z);
39\end{verbatim}
40Alternatively a list of polynomials can be used as input basis; however,
41all arithmetic results will be presented in the above form. The
42operator $ideal2list$ allows one to convert an ideal basis into a
43conventional REDUCE list.
44
45\subsection{Operators}
46
47Because of syntactical restrictions in REDUCE, special operators
48have to be used for ideal arithmetic:
49
50\begin{verbatim}
51         .+            ideal sum (infix)
52         .*            ideal product (infix)
53         .:            ideal quotient (infix)
54         ./            ideal quotient (infix)
55         .=            ideal equality test (infix)
56         subset        ideal inclusion test (infix)
57         intersection  ideal intersection (prefix,binary)
58         member        test for membership in an ideal
59                         (infix: polynomial and ideal)
60         gb            Groebner basis of an ideal (prefix, unary)
61         ideal2list    convert ideal basis to polynomial list
62                         (prefix,unary)
63\end{verbatim}
64
65Example:
66
67\begin{verbatim}
68    I(x+y,x^2) .* I(x-z);
69
70      2                      2    2
71   I(X  + X*Y - X*Z - Y*Z,X*Y  - Y *Z)
72\end{verbatim}
73
74The test operators return the values 1 (=true) or 0 (=false)
75such that they can be used in REDUCE $if-then-else$ statements
76directly.
77
78The results of $sum,product, quotient,intersction$ are ideals
79represented by their Gr\"obner basis in the current setting and
80term order. The term order can be modified using the operator
81$torder$ from the Gr\"obner package. Note that ideal equality
82cannot be tested with the REDUCE equal sign:
83
84\begin{verbatim}
85
86   I(x,y)  = I(y,x)       is false
87   I(x,y) .= I(y,x)       is true
88
89\end{verbatim}
90
91\section{Algorithms}
92
93The operators $groebner$, $preduce$ and $idealquotient$ of the
94REDUCE Gr\"obner package support the basic algorithms:
95
96$GB(Iu_1,u_2...) \rightarrow groebner(\{u_1,u_2...\},\{x,...\})$
97
98$p \in I_1 \rightarrow p=0 \ mod \ I_1$
99
100$I_1 : I(p) \rightarrow (I_1 \bigcap I(p)) / p \ elementwise$
101
102\noindent
103On top of these the Ideals package implements the following
104operations:
105
106
107$I(u_1,u_2...)+I(v_1,v_2...) \rightarrow GB(I(u_1,u_2...,v_1,v_2...))$
108
109
110$I(u_1,u_2...)*I(v_1,v_2...)\rightarrow
111 GB(I(u_1*v_1,u_1*v2,...,u_2*v_1,u_2*v_2...))$
112
113
114$I_1 \bigcap I_2 \rightarrow
115  Q[x,...] \bigcap GB_{lex}(t*I_1 + (1-t)*I_2,\{t,x,..\}) $
116
117
118$I_1 : I(p_1,p_2,...) \rightarrow I_1 : I(p_1) \bigcap I_1 : I(p_2)
119\bigcap ...$
120
121$I_1 = I_2 \rightarrow GB(I_1)=GB(I_2)$
122
123$I_1 \subseteq I_2
124   \rightarrow \ u_i \in I_2 \ \forall \ u_i \in I_1=I(u_1,u_2...)$
125
126\section{Examples}
127
128Please consult the file $ideals.tst$.
129\end{document}
130