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