(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 4.0, MathReader 4.0, or any compatible application. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. ***********************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 70153, 2009]*) (*NotebookOutlinePosition[ 71082, 2038]*) (* CellTagsIndexPosition[ 71038, 2034]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["Using the groebner40.m Package", "Title"], Cell["\<\ By William Gryc, Amherst College \tCongratulations! You've downloaded the new groebner40.m package and are \ now itching to use it. But there are so many commands, and so many \ parameters that your head is spinning. Well, this tutorial is designed for \ you. Before starting, make sure you have your copy of \"Ideals, Varieties, \ and Algorithms\" handy since there will be frequent references to sections of \ the text. On to.....\ \>", "Text"], Cell[CellGroupData[{ Cell["The Basics", "Section"], Cell["\<\ \tThese are the basic commands you will be using in the package. \ Most of the algorithms here are detailed in \"Ideals, Varieties, and \ Algorithms.\" Remember, for this package to work properly, you must have \ \"groebner40.m\". Also, this package might be slow in parts, especially in \ some of the more advanced commands. \tBefore you can do anything with the package, you must load it. Assuming \ you saved the package under the name \"groebner40.m\", load it by typing: \ \ \>", "Text"], Cell[BoxData[ \(<< groebner40.m\)], "Input"], Cell["\<\ \tThe rest of this tutorial will be devoted to demonstrating the \ commands of the groebner40.m package. At the end of the tutorial, there is a \ reference guide that gives more formal information on commands. For quick \ reference, you might want to look at the reference guide instead of searching \ through the tutorial.\ \>", "Text"], Cell[CellGroupData[{ Cell["MonOrder", "Subsection"], Cell[TextData[{ "\tThe most basic command in the package is MonOrder. It sets the monomial \ order (see Chapter 2, Section 2) for all relevant commands in the package \ (i.e. all commands whose output depends on a distinct monomial order). The \ orders that can be set using MonOrder are lex, grlex, grevlex (see Chapter 2, \ Section 2), elimination order (see Chapter 2, Section 4, Exercise 12 and \ Chapter 3, Section 1, Exercise 6), and matrix order. The latter is not dealt \ with in the text explicitly. Say you are working in k[x1,...,xn]. Then a \ matrix order would consist of n linearly independant vectors {", StyleBox["v1, ..., vn", FontWeight->"Bold"], "}, such that \[Alpha] > \[Beta] iff ", StyleBox["v1*", FontWeight->"Bold"], "\[Alpha]>", StyleBox["v1", FontWeight->"Bold"], "*\[Beta], or ", StyleBox["v1*", FontWeight->"Bold"], "\[Alpha]>", StyleBox["v1", FontWeight->"Bold"], "*\[Beta] and ", StyleBox["v2*", FontWeight->"Bold"], "\[Alpha]>", StyleBox["v2", FontWeight->"Bold"], "*\[Beta], or...etc. All monomial orders we will use can be written as \ matrix orders. For example, lex in k[x1, x2, x3] is the matrix order \ {{1,0,0}, {0,1,0},{0,0,1}}. As a matrix, each vector in the list is a row of \ the matrix. Note that the order of the rows is important.\n\tTo see the \ current monomial ordering, type" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[]\)], "Input"], Cell[BoxData[ \(Lex\)], "Output"] }, Open ]], Cell["\<\ \tThe output is Lex, because Lex is the current (i.e. default) \ ordering. Notice that Lex is capitalized. The package will only recognize \ the capitalized versions of Lex, Grlex, and Grevlex. Changing the ordering \ to lex, grlex, or grevlex is very straightforward. Simply type the name of \ the order (capitalized, of course) as a parameter to MonOrder. For example, \ to change the order to grevlex, type\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[Grevlex]\)], "Input"], Cell[BoxData[ \(Grevlex\)], "Output"] }, Open ]], Cell["\<\ \tChanging to an elimination order is different, but not hard. Say \ you want to eliminate the first three of five variables. Then type\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[{3, \ 5}]\)], "Input"], Cell[BoxData[ \({3, 5}\)], "Output"] }, Open ]], Cell["\<\ \tThus, the input is of the form {k, n}, where you want the kth \ elimination order of n variables. Naturally, k must be strictly less than n, \ or else MonOrder will complain and stick with the previous order.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[{4, 3}]\)], "Input"], Cell[BoxData[ \("Error: Not a valid Elimination form"\)], "Print"], Cell[BoxData[ \({3, 5}\)], "Output"] }, Open ]], Cell["\<\ \tMatrix orders are different yet. Say you wanted to use the \ matrix order determined by the matrix {{3, 0, 5}, {0, 9, 1}, {7, 4, 0}}. \ This becomes the input for MonOrder.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[{{3, 0, 5}, {0, 9, 1}, {7, 4, 0}}]\)], "Input"], Cell[BoxData[ \({{3, 0, 5}, {0, 9, 1}, {7, 4, 0}}\)], "Output"] }, Open ]], Cell["\<\ \tMonOrder will complain if the matrix isn't square, or if the rows \ of the matrix aren't linearly independent. Also, notice that with setting \ an elimination or matrix order, the input is a list. Brackets {...} must be \ placed around the list for MonOrder to work properly. \tSo far we've seen how to set the monomial order for the package, but so far \ there is no proof that MonOrder actually is anything more than a mindless \ command that echoes certain input. In the next subsection, we will see that \ it does have an affect on other commands. \ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Division and Computing GroebnerBases", "Subsection"], Cell["\tLet's set the order to Grevlex.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[Grevlex]\)], "Input"], Cell[BoxData[ \(Grevlex\)], "Output"] }, Open ]], Cell["\tLet's create a basis for an ideal", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basis\ = \ {x\ - \ z^4, \ y\ - \ z^5}\)], "Input"], Cell[BoxData[ \({x - z\^4, y - z\^5}\)], "Output"] }, Open ]], Cell[TextData[{ "\tThe package includes two related commands, PRemainder and PQuotient, \ that allow you to find the remainder and quotient, respectively (and \ obviously) of a polynomial divided by a set of polynomials, relative to the \ order set by MonOrder. Both commands simply use ", StyleBox["Mathematica", FontSlant->"Italic"], "'s built-in PolynomialReduce. (Why we bother placing them in the package \ will be explained in a later part of this subsection.) PolynomialReduce is a \ quick implementation of the Divison Algorithm of Chapter 2 Section 3. Let's \ try an example." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(PRemainder[\(-y\)\ + \ x*z, \ basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(\(-y\) + x\ z\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(PQuotient[\(-y\)\ + x*z, \ basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \({0, 0}\)], "Output"] }, Open ]], Cell["\<\ \tEven though -y +xz has a nonzero remainder, it might still be in \ the ideal generated by the basis. What we need is a Groebner basis for the \ ideal. \tBut maybe our ideal is already a Groebner basis. To check, the package \ provides the GroebnerQ command. Its input is a polynomial list, followed by \ the variable list. There is also an optional third parameter which allows \ GroebnerQ to use a monomial order different from the one set by MonOrder. \ For example, let's try GroebnerQ on our basis.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GroebnerQ[basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(False\)], "Output"] }, Open ]], Cell["\tMaybe it's a Groebner basis with respect to Lex order.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GroebnerQ[basis, \ {x, \ y, \ z}, \ Lex]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell["\<\ \tSo it is a Groebner basis in Lex order! Even though GroebnerQ \ used a different monomial order, it did not change the preset order.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[]\)], "Input"], Cell[BoxData[ \(Grevlex\)], "Output"] }, Open ]], Cell["\<\ \tNow we know that are basis isn't a Groebner basis in Grevlex, we \ want to find its Groebner basis (i.e. we want to do exercise 2c in Chapter \ 2 Section 7). This package provides three ways to find it. First, and most \ basic, is the command Buchberger. Buchberger implements the basic Buchberger \ algorithm as detailed in Chapter 2 Section 7. As arguments, Buchberger takes \ a list of polynomials (like our basis), and a list of variables (remember, \ order of the variables is important). The monomial order depends on the \ monomial order already set by MonOrder. So, to find a Groebner basis for our \ basis with respect to Grevlex ordering, we type\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Buchberger[basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": "\ \[InvisibleSpace]{y - x\ z}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 1, ": ", { Plus[ y, Times[ -1, x, z]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ \(" 1 division performed."\)], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]2\[InvisibleSpace]": "\ \[InvisibleSpace]{\(-x\^2\) + y\ z\^3}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 2, ": ", { Plus[ Times[ -1, Power[ x, 2]], Times[ y, Power[ z, 3]]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]2\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 2, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]3\[InvisibleSpace]": "\ \[InvisibleSpace]{x\^3 - y\^2\ z\^2}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 3, ": ", { Plus[ Power[ x, 3], Times[ -1, Power[ y, 2], Power[ z, 2]]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]3\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 3, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]4\[InvisibleSpace]": "\ \[InvisibleSpace]{x\^4 - y\^3\ z}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 4, ": ", { Plus[ Power[ x, 4], Times[ -1, Power[ y, 3], z]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]4\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 4, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]5\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 5, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]5\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 5, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(15\[InvisibleSpace]" divisions total."\), SequenceForm[ 15, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x - z\^4, y - z\^5, y - x\ z, \(-x\^2\) + y\ z\^3, x\^3 - y\^2\ z\^2, x\^4 - y\^3\ z}\)], "Output"] }, Open ]], Cell["\<\ \tNotice that Buchberger prints how many divisions it had to do \ with the S-Polynomials, and every time a polynomial is added to the basis, it \ prints that polynomial and how many divisions there were between what was \ just added and the previous added polynomial. This printing may be removed, \ by setting the PrintSteps option to False.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Buchberger[basis, \ {x, \ y, \ z}, \ PrintSteps\ -> \ False]\)], "Input"], Cell[BoxData[ \({x - z\^4, y - z\^5, y - x\ z, \(-x\^2\) + y\ z\^3, x\^3 - y\^2\ z\^2, x\^4 - y\^3\ z}\)], "Output"] }, Open ]], Cell["\<\ \tSadly, this version of the Buchberger algorithm is very naive \ and, consequently, very slow. There is a minor variation on Buchberger \ called AltBuchberger. In computing the remainders for S-polynomials, \ AltBuchberger uses the most up-to-date basis for division. The algorithm in \ the text is modified so the dividing polynomials is G as opposed to G' (see \ the Buchberger Algorithm Chapter 2 Section 7). This minor refinement can \ yield dramatic results. Consider the following example:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basisprime\ = \ {x^3\ - \ z^2, \ y^3\ + \ z, \ x^2*y\ + \ x*y^2}\)], "Input"], Cell[BoxData[ \({x\^3 - z\^2, y\^3 + z, x\^2\ y + x\ y\^2}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(m\ = Buchberger[basisprime, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": "\ \[InvisibleSpace]{\(-x\)\ z - y\ z\^2, x\^2\ z + x\ y\ z}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 1, ": ", { Plus[ Times[ -1, x, z], Times[ -1, y, Power[ z, 2]]], Plus[ Times[ Power[ x, 2], z], Times[ x, y, z]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]3\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 3, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]2\[InvisibleSpace]": "\ \[InvisibleSpace]{x\ y\^2\ z - z\^3, \(-x\)\ y\^2\ z + z\^3, x\ y\^2\ z - z\^3, \(-x\)\ y\^2\ z + z\^3}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 2, ": ", { Plus[ Times[ x, Power[ y, 2], z], Times[ -1, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ y, 2], z], Power[ z, 3]], Plus[ Times[ x, Power[ y, 2], z], Times[ -1, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ y, 2], z], Power[ z, 3]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]7\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 7, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]3\[InvisibleSpace]": "\ \[InvisibleSpace]{\(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-z\^3\) + z\^4, \(-z\^3\) + z\^4, \(-z\^3\) + z\^4, \(-z\^3\) + z\^4, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 3, ": ", { Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, Power[ z, 3]], Power[ z, 4]], Plus[ Times[ -1, Power[ z, 3]], Power[ z, 4]], Plus[ Times[ -1, Power[ z, 3]], Power[ z, 4]], Plus[ Times[ -1, Power[ z, 3]], Power[ z, 4]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]26\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 26, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]4\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 4, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]174\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 174, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(210\[InvisibleSpace]" divisions total."\), SequenceForm[ 210, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x\^3 - z\^2, y\^3 + z, x\^2\ y + x\ y\^2, \(-x\)\ z - y\ z\^2, x\^2\ z + x\ y\ z, x\ y\^2\ z - z\^3, \(-x\)\ y\^2\ z + z\^3, x\ y\^2\ z - z\^3, \(-x\)\ y\^2\ z + z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-z\^3\) + z\^4, \(-z\^3\) + z\^4, \(-z\^3\) + z\^4, \(-z\^3\) + z\^4, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-x\)\ z\^2 + x\ z\^3}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(n\ = AltBuchberger[basisprime, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": "\ \[InvisibleSpace]{\(-x\)\ z - y\ z\^2, x\^2\ z + x\ y\ z}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 1, ": ", { Plus[ Times[ -1, x, z], Times[ -1, y, Power[ z, 2]]], Plus[ Times[ Power[ x, 2], z], Times[ x, y, z]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]3\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 3, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]2\[InvisibleSpace]": "\ \[InvisibleSpace]{x\ y\^2\ z - z\^3}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 2, ": ", { Plus[ Times[ x, Power[ y, 2], z], Times[ -1, Power[ z, 3]]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]7\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 7, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]3\[InvisibleSpace]": "\ \[InvisibleSpace]{\(-x\)\ z\^2 + x\ z\^3, \(-z\^3\) + z\^4}\[InvisibleSpace]" added."\), SequenceForm[ "Step ", 3, ": ", { Plus[ Times[ -1, x, Power[ z, 2]], Times[ x, Power[ z, 3]]], Plus[ Times[ -1, Power[ z, 3]], Power[ z, 4]]}, " added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]5\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 5, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]4\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 4, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]13\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 13, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(28\[InvisibleSpace]" divisions total."\), SequenceForm[ 28, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x\^3 - z\^2, y\^3 + z, x\^2\ y + x\ y\^2, \(-x\)\ z - y\ z\^2, x\^2\ z + x\ y\ z, x\ y\^2\ z - z\^3, \(-x\)\ z\^2 + x\ z\^3, \(-z\^3\) + z\^4}\)], "Output"] }, Open ]], Cell["\<\ \tNow, to see that both expressions produce a Groebner basis, we \ will use GroebnerQ:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GroebnerQ[m, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(GroebnerQ[n, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell["\<\ \tAltBuchberger blows away Buchberger is this example. There is \ still another Buchberger implementation called QuickBuchberger. It has the \ same parameters as Buchberger and AltBuchberger, but is even faster. The \ command implements the speed improvements found in Chapter 2 Section 9. Here \ are two examples to show the two different improvements :\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basis1 = \ {x^2, \ y^4}\)], "Input"], Cell[BoxData[ \({x\^2, y\^4}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(AltBuchberger[basis1, \ {x, \ y}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 1, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ \(" 1 division performed."\)], "Print"], Cell[BoxData[ InterpretationBox[\(1\[InvisibleSpace]" divisions total."\), SequenceForm[ 1, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x\^2, y\^4}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(QuickBuchberger[basis1, \ {x, \ y}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 1, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]0\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 0, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(0\[InvisibleSpace]" divisions total."\), SequenceForm[ 0, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x\^2, y\^4}\)], "Output"] }, Open ]], Cell[TextData[{ "\tObviously, ", StyleBox["basis1", FontWeight->"Bold"], " already forms a Groebner basis, but AltBuchberger still performs one \ division. QuickBuchberger cuts out this division by noticing that the \ monomials x^2 and y^4 are relatively prime (see Proposition 4 of Chapter 2 \ Section 9)." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basis2\ = \ {x^2, \ x*y^3, \ x^2*y^3}\)], "Input"], Cell[BoxData[ \({x\^2, x\ y\^3, x\^2\ y\^3}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(AltBuchberger[basis2, \ {x, \ y}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 1, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]3\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 3, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(3\[InvisibleSpace]" divisions total."\), SequenceForm[ 3, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x\^2, x\ y\^3, x\^2\ y\^3}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(QuickBuchberger[basis2, \ {x, \ y}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Step "\[InvisibleSpace]1\[InvisibleSpace]": nothing \ added."\), SequenceForm[ "Step ", 1, ": nothing added."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(" "\[InvisibleSpace]2\[InvisibleSpace]" \ divisions performed."\), SequenceForm[ " ", 2, " divisions performed."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\(2\[InvisibleSpace]" divisions total."\), SequenceForm[ 2, " divisions total."], Editable->False]], "Print"], Cell[BoxData[ \({x\^2, x\ y\^3, x\^2\ y\^3}\)], "Output"] }, Open ]], Cell[TextData[{ "\tQuickBuchberger again is able to cut out one division. However, none of \ the leading terms in ", StyleBox["basis2", FontWeight->"Bold"], " are relatively prime, so the second improvment must be at work. Notice \ that the third leading term, x^2*y^3, divides the LCM of x^2 and xy^3. In \ fact, it is the LCM of x^2 and xy^3. By Proposition 10 of Chapter 2 Section \ 9, if the remainders of the S-polynomials of x^2, xy^3 and of x^2, x^2y^3 are \ both calculated, the remainder of the S-polynomial of xy^3 and x^2y^3 need \ not be calculated. Thus, QuickBuchberger does one less division. \n\n\tOne \ last way to find a Groebner basis is using the MathematicaBuchberger command. \ This simply uses the built in ", StyleBox["Mathematica", FontSlant->"Italic"], " GroebnerBasis command, like PRemainder or PQuotient, but provides a \ consistent interface for the rest of the package. ", StyleBox["Mathematica", FontSlant->"Italic"], ", for example, has different names for monomial orders. Lex is called \ Lexicographic and Grevlex is called DegreeReverseLexicographic. To save you \ from having to remember these correspondences, as well as allowing you to use \ the order fixed by MonOrder, MathematicaBuchberger is included in the \ package. You will notice that MathematicaBuchberger is ", StyleBox["much", FontSlant->"Italic"], " faster than Buchberger, AltBuchberger or QuickBuchberger. We include the \ others since they work fine for many of the simpler examples in the text, and \ are direct implementations of algorithms in the text. To see \ MathematicaBuchberger at work, consider" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MathematicaBuchberger[basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \({\(-y\) + x\ z, x - z\^4, \(-x\^2\) + y\ z\^3, x\^3 - y\^2\ z\^2, \(-x\^4\) + y\^3\ z}\)], "Output"] }, Open ]], Cell[TextData[{ "\tNotice that this is ", StyleBox["not", FontSlant->"Italic"], " the same as the output of Buchberger on ", StyleBox["basis", FontWeight->"Bold"], ". This difference reflects that MathematicaBuchberger returns a ", StyleBox["reduced", FontSlant->"Italic"], " (see Chapter 2 Section 7) Groebner basis, while the others do not. There \ is a command in the package called ReduceGroebner that will produce a reduced \ Groebner basis from any Groebner basis:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(ReduceGroebner[ QuickBuchberger[basis, \ {x, \ y, \ z}, \ PrintSteps\ -> \ False], \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \({\(-x\) + z\^4, \(-y\) + x\ z, \(-x\^2\) + y\ z\^3, \(-x\^3\) + y\^2\ z\^2, x\^4 - y\^3\ z}\)], "Output"] }, Open ]], Cell[TextData[{ "\tAs you can see, the reduced Groebner bases are the same for \ QuickBuchberger and MathematicaBuchberger, and that -y + xz is in the ideal.\n\ \n\tUnlike Buchberger, AltBuchberger, and QuickBuchberger, there is no \ PrintSteps option for MathematicaBuchberger, since MathematicaBuchberger is \ basically a front end to internal code. MathematicaBuchberger will never \ print steps.\n\n\tYou might have noticed that these function names are fairly \ cumbersome. That is why each command has a counterpart with an abbrievated \ name. For example, QuickBuchberger and QB are the same function. The \ following is a table of full names and abbreviated names:\n\t\n\t", StyleBox["Full Name\t\t\t\tAbbreviated Name", FontWeight->"Bold"], "\n\tBuchberger\t\t\t\tB\n\tAltBuchberger\t\t\tAB\n\tQuickBuchberger\t\t\t\ QB\n\tMathematicaBuchberger\t\tMB" }], "Text"], Cell["\<\ \tFinally it should be mentioned that there is a command that \ computes S-polynomials (as described in Chapter 2 Section 6) called, \ appropriately, SPoly, that takes two polynomials and a varlist as parameters. \ For example,\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(SPoly[y - \ z^5, \ x\ - \ z^4, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(\(-y\) + x\ z\)], "Output"] }, Open ]], Cell["\<\ \tSo, you can manually (somewhat) do the Buchberger algorithm on \ your own.\ \>", "Text"], Cell["\<\ \tNow that we can find Groebner bases, the next section details how \ we can use them.\ \>", "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Commands that Use Groebner Bases", "Section"], Cell["\<\ \tNow that we can build a Groebner basis, we can solve problems \ like the ideal membership problem (see Chapter 2, Section 8). Let's use the \ Lagrange multipliers example from Chapter 2 Section 8. This gives the basis:\ \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basis\ = \ {3*x^2\ + \ 2*y*z\ - \ 2*x*\[Lambda], \ 2*x*z\ - \ 2*y*\[Lambda], \ 2*x*y\ - \ 2*z\ - \ 2*z*\[Lambda], \ x^2\ + \ y^2\ + \ z^2\ - \ 1}\)], "Input"], Cell[BoxData[ \({3\ x\^2 + 2\ y\ z - 2\ x\ \[Lambda], 2\ x\ z - 2\ y\ \[Lambda], 2\ x\ y - 2\ z - 2\ z\ \[Lambda], \(-1\) + x\^2 + y\^2 + z\^2}\)], "Output"] }, Open ]], Cell[TextData[ "\tTo see if a polynomial is in the ideal, you can use IdealQ, which \ implements the ideal membership algorithm found in Chapter 2 Section 8. \ IdealQ takes a polynomial, a polynomial list that does NOT have to be a \ Groebner basis, and a variable list. Let's see if 2x\[Lambda], or even \ 1152z^7 + 1763z^5 + 655z^3 - 44z is in the ideal generated by the Lagrange \ multipliers: "], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(IdealQ[2*x*\[Lambda], \ basis, \ {\[Lambda], \ x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(False\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(IdealQ[1152*z^7\ - \ 1763*z^5\ + \ 655*z^3\ - \ 44*z, \ basis, \ {\[Lambda], \ x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell["\<\ \tOf course the second polynomial should be in the ideal, as it is \ in the lex Groebner basis of the ideal. As well as testing for ideal \ membership, sometimes one wants to test for radical ideal membership (see \ Chapter 4 Section 2 for the explanation of the radical). RadicalQ implements \ the radical membership algorithm detailed in Chapter 4 Section 2 of the text. \ RadicalQ takes the same arguments as IdealQ. Let's use exercise 7a of \ Chapter 4 Section 2 as an example.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basis\ = \ {x^3, \ y^3, \ xy*\((x\ + y)\)}\)], "Input"], Cell[BoxData[ \({x\^3, y\^3, xy\ \((x + y)\)}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(RadicalQ[x + y, \ basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell[TextData[{ "\t(It should be noted that there is also a command in this package that \ returns the generators of the radical of any zero-dimensional ideal (i.e. an \ ideal ", StyleBox["I", FontSlant->"Italic"], " where ", StyleBox["V", FontWeight->"Bold"], "(", StyleBox["I", FontSlant->"Italic"], ") is finite). Its details will be given in the next section.)\n\n\tOne \ final True/False-type command is the FiniteQ command, which returns True if \ the variety of the given ideal is finite over an algebraically closed field. \ This algorithm uses statement 3 of the theorem of Chapter 5 Section 3 as the \ criterion. Its parameters are a polynomial list that does NOT have to be a \ Groebner basis and a variable list. For an example, let's look at the ideal \ given in the discussion that follows the proof of the aforementioned \ theorem." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[Grlex]\)], "Input"], Cell[BoxData[ \(Grlex\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(basis\ = \ {x^5\ + \ y^3\ + \ z^2\ - \ 1, \ x^2\ + \ y^3\ + \ z\ - \ 1, \ x^4\ + \ y^5\ + \ z^6\ - \ 1}\)], "Input"], Cell[BoxData[ \({\(-1\) + x\^5 + y\^3 + z\^2, \(-1\) + x\^2 + y\^3 + z, \(-1\) + x\^4 + y\^5 + z\^6}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(FiniteQ[basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell[TextData[{ "\tAs indicated by the text, the answer is true. Notice that for the \ previous three commands, the monomial order is irrevelent. The package uses \ Grevlex in all Groebner basis calculations in these functions, because \ Grevlex usually yields the fastest computations.\n\n\tOne final command that \ should be mentioned in this section is VSDimension. Its parameters are a \ polynomial list, and a variable list, with an optional third parameter for \ the monomial order. If the polynomials in the list form a zero-dimensional \ ideal (i.e. if FiniteQ would return True on them), VSDimension returns a list \ of the remainder monomials and the number of remainders (i.e. the dimension \ of the space spanned by the remainder monomials). The number of remainder \ monomials is also a upper bound for the number solutions of the equations of \ the ideal. (As explained in Corollary 2.5 in Chapter 4 of \"Using Algebraic \ Geometry\" by [CLO], this is the number of solutions with multiplicities. \ So, if the ideal is radical, the number is ", StyleBox["exactly", FontSlant->"Italic"], " the number of solutions.) If there are infinitely many remainders, the \ command returns {Infinity, Infinity}. If left unspecified, the monomial \ ordering is the ordering determined by the current order set by MonOrder. \ Let's use the current basis for an example:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(VSDimension[basis, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \({{1, x, x\^2, x\^3, x\^4, y, y\^2, x\ y, x\ y\^2, x\^2\ y, x\^2\ y\^2, x\^3\ y, x\^3\ y\^2, x\^4\ y, x\^4\ y\^2, z, z\^2, z\^3, z\^4, z\^5, x\ z, x\ z\^2, x\ z\^3, x\ z\^4, x\ z\^5, x\^2\ z, x\^2\ z\^2, x\^2\ z\^3, x\^2\ z\^4, x\^2\ z\^5, x\^3\ z, x\^3\ z\^2, x\^3\ z\^3, x\^3\ z\^4, x\^3\ z\^5, x\^4\ z, x\^4\ z\^2, x\^4\ z\^3, x\^4\ z\^4, x\^4\ z\^5, y\ z, y\ z\^2, y\ z\^3, y\ z\^4, y\ z\^5, y\^2\ z, y\^2\ z\^2, y\^2\ z\^3, y\^2\ z\^4, y\^2\ z\^5, x\ y\ z, x\ y\ z\^2, x\ y\ z\^3, x\ y\ z\^4, x\ y\ z\^5, x\ y\^2\ z, x\ y\^2\ z\^2, x\ y\^2\ z\^3, x\ y\^2\ z\^4, x\ y\^2\ z\^5, x\^2\ y\ z, x\^2\ y\ z\^2, x\^2\ y\ z\^3, x\^2\ y\ z\^4, x\^2\ y\ z\^5, x\^2\ y\^2\ z, x\^2\ y\^2\ z\^2, x\^2\ y\^2\ z\^3, x\^2\ y\^2\ z\^4, x\^2\ y\^2\ z\^5, x\^3\ y\ z, x\^3\ y\ z\^2, x\^3\ y\ z\^3, x\^3\ y\ z\^4, x\^3\ y\ z\^5, x\^3\ y\^2\ z, x\^3\ y\^2\ z\^2, x\^3\ y\^2\ z\^3, x\^3\ y\^2\ z\^4, x\^3\ y\^2\ z\^5, x\^4\ y\ z, x\^4\ y\ z\^2, x\^4\ y\ z\^3, x\^4\ y\ z\^4, x\^4\ y\ z\^5, x\^4\ y\^2\ z, x\^4\ y\^2\ z\^2, x\^4\ y\^2\ z\^3, x\^4\ y\^2\ z\^4, x\^4\ y\^2\ z\^5}, 90}\)], "Output"] }, Open ]], Cell["\<\ \tHere is the same example, this time using an elimination order:\ \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(VSDimension[basis, \ {x, \ y, \ z}, \ {1, \ 3}]\)], "Input"], Cell[BoxData[ \({{1, x, y, y\^2, y\^3, y\^4, y\^5, x\ y, x\ y\^2, z, z\^2, z\^3, z\^4, z\^5, z\^6, z\^7, z\^8, z\^9, z\^10, z\^11, z\^12, z\^13, z\^14, z\^15, z\^16, x\ z, x\ z\^2, y\ z, y\ z\^2, y\ z\^3, y\ z\^4, y\ z\^5, y\ z\^6, y\ z\^7, y\ z\^8, y\ z\^9, y\ z\^10, y\ z\^11, y\ z\^12, y\ z\^13, y\ z\^14, y\ z\^15, y\ z\^16, y\^2\ z, y\^2\ z\^2, y\^2\ z\^3, y\^2\ z\^4, y\^2\ z\^5, y\^2\ z\^6, y\^2\ z\^7, y\^2\ z\^8, y\^2\ z\^9, y\^2\ z\^10, y\^2\ z\^11, y\^2\ z\^12, y\^2\ z\^13, y\^2\ z\^14, y\^3\ z, y\^3\ z\^2, y\^3\ z\^3, y\^3\ z\^4, y\^3\ z\^5, y\^3\ z\^6, y\^3\ z\^7, y\^3\ z\^8, y\^3\ z\^9, y\^3\ z\^10, y\^3\ z\^11, y\^4\ z, y\^4\ z\^2, y\^4\ z\^3, y\^4\ z\^4, y\^4\ z\^5, y\^4\ z\^6, y\^4\ z\^7, y\^4\ z\^8, y\^4\ z\^9, y\^4\ z\^10, y\^4\ z\^11, y\^5\ z, y\^5\ z\^2, y\^5\ z\^3, y\^5\ z\^4, y\^5\ z\^5, y\^5\ z\^6, y\^5\ z\^7, y\^5\ z\^8, y\^5\ z\^9, y\^5\ z\^10, y\^5\ z\^11}, 90}\)], "Output"] }, Open ]], Cell["\<\ \tNotice that while the dimension was constant across monomial \ orders, the monomials themselves were not. Since the dimension is \ independent of monomial ordering, you might as well use Grevlex as your \ ordering if you are only interested in the dimension. \tAll the commands described thus far have algorithms that can be found in \ the text. The next commands use algorithms that go beyond the scope of the \ text, but could still be useful for the casual IVA reader.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Beyond IVA", "Section"], Cell["\<\ \tWhile these commands use algorithms not found in IVA, their \ purpose can be easily understood by the IVA reader. The first algorithm was \ previously noted in a parenthetical note, and is the function that return the \ generators, NOT necessarily the Groebner basis, of the radical of a \ zero-dimensional ideal. Do note that this command only works on \ zero-dimensional ideals (i.e. those for which FiniteQ returns True). The \ command is called Radical (makes sense, right?) and takes a polynomial list \ and variable list as parameters. To create generators, the type of monomial \ order does not matter and Radical uses Grevlex. This algorithm is a \ consequence of Proposition 2.7 of Chapter 2 Section 2 of [CLO]. Let's use \ the Lagrange multipliers basis for an example.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(basis\ = {3*x^2\ + \ 2*y*z\ - \ 2*x*\[Lambda], \ 2*x*z\ - \ 2*y*\[Lambda], \ 2*x*y\ - \ 2*z\ - \ 2*z*\[Lambda], \ x^2\ + \ y^2\ + \ z^2\ - \ 1}\)], "Input"], Cell[BoxData[ \({3\ x\^2 + 2\ y\ z - 2\ x\ \[Lambda], 2\ x\ z - 2\ y\ \[Lambda], 2\ x\ y - 2\ z - 2\ z\ \[Lambda], \(-1\) + x\^2 + y\^2 + z\^2}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(radbasis\ = Radical[basis, \ {\[Lambda], x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \({3\ x\^2 + 2\ y\ z - 2\ x\ \[Lambda], 2\ x\ z - 2\ y\ \[Lambda], 2\ x\ y - 2\ z - 2\ z\ \[Lambda], \(-1\) + x\^2 + y\^2 + z\^2, \(-6\)\ x - 25\ x\^2 - 18\ x\^3 + 25\ x\^4 + 24\ x\^5, \(-99\)\ y + 1118\ y\^3 - 2171\ y\^5 + 1152\ y\^7}\)], "Output"] }, Open ]], Cell["\<\ \tThere is also a command RadicalIdealQ, which returns True if the \ ideal is radical. The parameters are the same as Radical. Let's use the \ Lagrange multipliers for an example. \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(RadicalIdealQ[basis, \ {\[Lambda], x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(False\)], "Output"] }, Open ]], Cell["\<\ \tSo the basis alone is not radical. However, after performing \ Radical....\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(RadicalIdealQ[radbasis, \ {\[Lambda], x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Open ]], Cell["\<\ \t....the answer is obviously True. \tThe next command is called ConvertGB, and can convert a GroebnerBasis of \ any monomial order and variable order into a Groebner basis of any variable \ order and either Lex or Grlex. It also returns the remainder monomials of \ the Groebner basis. It can't convert to Grevlex, since Grevlex Groebner \ bases are quick to compute anyway, and there would be no real need to convert \ them. Other monomial orders, such as matrix orders, are not easy to convert \ (i.e. we are not sure how to do it yet). ConvertGB implements the algorithm \ first given in [FGLM], and directly implements the version given of Chapter 2 \ Section 3 of [CLO]. For parameters, ConvertGB takes a list of polynomial \ that form a Groebner basis, a new variable list, and the original variable \ list. The command assumes that the basis that it is getting as a parameter \ has is a Groebner basis with respect to the current order set by MonOrder. \ If the Groebner basis is of some other order, you can set the OldOrderType \ option to the appropriate order (as you would if it were input to MonOrder). \ If the polynomials do not form a Groebner basis under the orignal variable \ list and monomial order, ConvertGB will complain and not produce output. \ There are other options for ConvertGB. OrderType can be set to Lex or Grlex, \ depending on which order you would like to convert your Groebner basis into. \ Its default is Lex. PrintSteps can be set to True or False, depending if you \ would like to see the added element of the Groebner basis and the most \ recently added remainder monomials every time a new equation is added to the \ constructed Groebner basis. Again, we'll use the Lagrange multipliers basis \ for the example.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[Grevlex]\)], "Input"], Cell[BoxData[ \(Grevlex\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(gb\ = MathematicaBuchberger[basis, \ {y, \ x, \ \[Lambda], \ z}]\)], "Input"], Cell[BoxData[ \({x\ z - y\ \[Lambda], 3\ x\^2 + 2\ y\ z - 2\ x\ \[Lambda], x\ y - z - z\ \[Lambda], \(-3\) + 3\ y\^2 - 2\ y\ z + 3\ z\^2 + 2\ x\ \[Lambda], \(-3\)\ x + 15\ y\ z + 14\ z\^2 + 2\ \[Lambda] - 18\ x\ \[Lambda] + 24\ z\^2\ \[Lambda] + 12\ \[Lambda]\^2, 15\ x - 27\ y\ z + 2\ z\^2 - 24\ x\ z\^2 - 10\ \[Lambda] + 18\ x\ \[Lambda] - 12\ \[Lambda]\^2, 12\ z + 17\ x\ z + 17\ y\ z\^2 - 13\ z\^3 - z\ \[Lambda], 4\ z - 10\ z\^3 - 23\ z\ \[Lambda] - 17\ z\ \[Lambda]\^2, \(-6\)\ z - 17\ x\ z - 2\ z\^3 - 8\ z\ \[Lambda] - 17\ x\ z\ \[Lambda], 6\ x + 6\ y\ z + 11\ z\^2 + 23\ \[Lambda] - 12\ \[Lambda]\^3, \(-3\)\ x - 9\ y\ z - 4\ z\^2 - 16\ \[Lambda] + 18\ x\ \[Lambda] - 12\ \[Lambda]\^2 + 12\ x\ \[Lambda]\^2, \(-699\)\ x + 1047\ y\ z - 1850\ z\^2 + 1152\ z\^4 + 466\ \[Lambda] - 1746\ x\ \[Lambda] + 1164\ \[Lambda]\^2}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(ConvertGB[ gb, {\[Lambda], \ x, \ y, \ z}, \ {y, \ x, \ \[Lambda], \ z}]\)], "Input"], Cell[BoxData[ \({{\(-\(\(11\ z\)\/288\)\) + \(655\ z\^3\)\/1152 - \(1763\ z\^5\)\/1152 \ + z\^7, \(-y\)\ z - \(453\ z\^2\)\/118 + y\ z\^3 + \(1605\ z\^4\)\/118 - \(576\ z\^6\)\/59, \(-\(\(3839\ z\)\ \/3835\)\) + y\^2\ z + \(827\ z\^3\)\/295 - \(6912\ z\^5\)\/3835, \(-y\) + y\^3 - \(2562\ z\)\/3835 + y\ z\^2 + \(906\ z\^3\)\/295 - \(9216\ z\^5\)\/3835, \(2556\ \ z\)\/3835 + x\ z + y\ z\^2 - \(108\ z\^3\)\/295 - \(1152\ z\^5\)\/3835, x\ y - \(6403\ z\)\/3835 + \(1999\ z\^3\)\/295 - \(19584\ \ z\^5\)\/3835, \(-1\) + x\^2 + y\^2 + z\^2, \(-\(\(3\ x\)\/2\)\) - \(3\ y\ z\)\/2 - \(134419\ \ z\^2\)\/7670 + \(36717\ z\^4\)\/590 - \(167616\ z\^6\)\/3835 + \[Lambda]}, \ {1, z, z\^2, z\^3, z\^4, z\^5, z\^6, y, y\ z, y\ z\^2, y\^2, x}}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(ConvertGB[ gb, {\[Lambda], \ x, \ y, \ z}, \ {y, \ x, \ \[Lambda], \ z}, \ OldOrderType -> \ Grevlex, \ OrderType\ -> \ Grlex, \ PrintSteps\ -> \ True]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Added to remainders: "\[InvisibleSpace]{1, z, y, x, \[Lambda], z\^2, y\ z, y\^2, x\ z, x\ y}\), SequenceForm[ "Added to remainders: ", {1, z, y, x, \[Lambda], Power[ z, 2], Times[ y, z], Power[ y, 2], Times[ x, z], Times[ x, y]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-1\) \ + x\^2 + y\^2 + z\^2\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ -1, Power[ x, 2], Power[ y, 2], Power[ z, 2]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-x\)\ \ y + z + z\ \[Lambda]\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Times[ -1, x, y], z, Times[ z, \[Lambda]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-x\)\ \ z + y\ \[Lambda]\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Times[ -1, x, z], Times[ y, \[Lambda]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-\(3\ \/2\)\) + \(3\ y\^2\)\/2 - y\ z + \(3\ z\^2\)\/2 + x\ \[Lambda]\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Rational[ -3, 2], Times[ Rational[ 3, 2], Power[ y, 2]], Times[ -1, y, z], Times[ Rational[ 3, 2], Power[ z, 2]], Times[ x, \[Lambda]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to remainders: \ "\[InvisibleSpace]{\[Lambda]\^2, z\^3}\), SequenceForm[ "Added to remainders: ", { Power[ \[Lambda], 2], Power[ z, 3]}], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: \ "\[InvisibleSpace]\(\(-\(\(x\ y\)\/17\)\) + \(13\ z\)\/17 + x\ z + y\ z\^2 - \(13\ z\^3\)\/17\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Times[ Rational[ -1, 17], x, y], Times[ Rational[ 13, 17], z], Times[ x, z], Times[ y, Power[ z, 2]], Times[ Rational[ -13, 17], Power[ z, 3]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: \ "\[InvisibleSpace]\(\(-\(\(6\ x\ y\)\/17\)\) - \(7\ z\)\/17 + y\^2\ z + \(7\ z\^3\)\/17\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Times[ Rational[ -6, 17], x, y], Times[ Rational[ -7, 17], z], Times[ Power[ y, 2], z], Times[ Rational[ 7, 17], Power[ z, 3]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-y\) \ - \(7\ x\ y\)\/17 + y\^3 - \(11\ z\)\/17 - x\ z + \(11\ z\^3\)\/17\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Times[ -1, y], Times[ Rational[ -7, 17], x, y], Power[ y, 3], Times[ Rational[ -11, 17], z], Times[ -1, x, z], Times[ Rational[ 11, 17], Power[ z, 3]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-\(9\ \/8\)\) - \(5\ x\)\/8 + \(9\ y\^2\)\/8 + \(3\ y\ z\)\/8 + \(25\ z\^2\)\/24 + x\ z\^2 + \(5\ \[Lambda]\)\/12 + \[Lambda]\^2\/2\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Rational[ -9, 8], Times[ Rational[ -5, 8], x], Times[ Rational[ 9, 8], Power[ y, 2]], Times[ Rational[ 3, 8], y, z], Times[ Rational[ 25, 24], Power[ z, 2]], Times[ x, Power[ z, 2]], Times[ Rational[ 5, 12], \[Lambda]], Times[ Rational[ 1, 2], Power[ \[Lambda], 2]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-\(9\ \/8\)\) - x\/8 + \(9\ y\^2\)\/8 - \(y\ z\)\/8 + x\ y\ z + \(17\ z\^2\)\/24 + \[Lambda]\/12 + \[Lambda]\^2\/2\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Rational[ -9, 8], Times[ Rational[ -1, 8], x], Times[ Rational[ 9, 8], Power[ y, 2]], Times[ Rational[ -1, 8], y, z], Times[ x, y, z], Times[ Rational[ 17, 24], Power[ z, 2]], Times[ Rational[ 1, 12], \[Lambda]], Times[ Rational[ 1, 2], Power[ \[Lambda], 2]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-\(9\ \/8\)\) - \(5\ x\)\/8 + \(9\ y\^2\)\/8 + x\ y\^2 - \(5\ y\ z\)\/8 + \(25\ z\^2\)\/24 + \(5\ \[Lambda]\)\/12 \ + \[Lambda]\^2\/2\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Rational[ -9, 8], Times[ Rational[ -5, 8], x], Times[ Rational[ 9, 8], Power[ y, 2]], Times[ x, Power[ y, 2]], Times[ Rational[ -5, 8], y, z], Times[ Rational[ 25, 24], Power[ z, 2]], Times[ Rational[ 5, 12], \[Lambda]], Times[ Rational[ 1, 2], Power[ \[Lambda], 2]]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: "\[InvisibleSpace]\(\(-\(x\ \/2\)\) - \(y\ z\)\/2 - \(11\ z\^2\)\/12 - \(23\ \[Lambda]\)\/12 + \ \[Lambda]\^3\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Times[ Rational[ -1, 2], x], Times[ Rational[ -1, 2], y, z], Times[ Rational[ -11, 12], Power[ z, 2]], Times[ Rational[ -23, 12], \[Lambda]], Power[ \[Lambda], 3]]], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("Added to Groebner basis: \ "\[InvisibleSpace]\(\(-\(291\/128\)\) - \(233\ x\)\/384 + \(291\ y\^2\)\/128 \ - \(233\ y\ z\)\/384 + \(769\ z\^2\)\/1152 + z\^4 + \(233\ \[Lambda]\)\/576 + \(97\ \[Lambda]\^2\)\/96\)\), SequenceForm[ "Added to Groebner basis: ", Plus[ Rational[ -291, 128], Times[ Rational[ -233, 384], x], Times[ Rational[ 291, 128], Power[ y, 2]], Times[ Rational[ -233, 384], y, z], Times[ Rational[ 769, 1152], Power[ z, 2]], Power[ z, 4], Times[ Rational[ 233, 576], \[Lambda]], Times[ Rational[ 97, 96], Power[ \[Lambda], 2]]]], Editable->False]], "Print"], Cell[BoxData[ \({{\(-1\) + x\^2 + y\^2 + z\^2, \(-x\)\ y + z + z\ \[Lambda], \(-x\)\ z + y\ \[Lambda], \(-\(3\/2\)\) + \(3\ y\^2\)\/2 - y\ z + \(3\ z\^2\)\/2 + x\ \[Lambda], \(-\(\(x\ y\)\/17\)\) + \(13\ z\)\/17 + x\ z + y\ z\^2 - \(13\ z\^3\)\/17, \(-\(\(6\ x\ y\)\/17\)\) - \(7\ z\)\/17 \ + y\^2\ z + \(7\ z\^3\)\/17, \(-y\) - \(7\ x\ y\)\/17 + y\^3 - \(11\ z\)\/17 - x\ z + \(11\ z\^3\)\/17, \(-\(9\/8\)\) - \(5\ x\)\/8 + \(9\ \ y\^2\)\/8 + \(3\ y\ z\)\/8 + \(25\ z\^2\)\/24 + x\ z\^2 + \(5\ \[Lambda]\)\/12 + \[Lambda]\^2\/2, \(-\(9\/8\)\) - x\/8 + \(9\ y\^2\)\/8 - \(y\ z\)\/8 + x\ y\ z + \(17\ z\^2\)\/24 + \[Lambda]\/12 + \[Lambda]\^2\/2, \ \(-\(9\/8\)\) - \(5\ x\)\/8 + \(9\ y\^2\)\/8 + x\ y\^2 - \(5\ y\ z\)\/8 + \(25\ z\^2\)\/24 + \(5\ \[Lambda]\)\/12 \ + \[Lambda]\^2\/2, \(-\(x\/2\)\) - \(y\ z\)\/2 - \(11\ z\^2\)\/12 - \(23\ \ \[Lambda]\)\/12 + \[Lambda]\^3, \(-\(291\/128\)\) - \(233\ x\)\/384 + \(291\ \ y\^2\)\/128 - \(233\ y\ z\)\/384 + \(769\ z\^2\)\/1152 + z\^4 + \(233\ \[Lambda]\)\/576 + \(97\ \[Lambda]\^2\)\/96}, {1, z, y, x, \[Lambda], z\^2, y\ z, y\^2, x\ z, x\ y, \[Lambda]\^2, z\^3}}\)], "Output"] }, Open ]], Cell[TextData[ "\tAs you can see, PrintSteps can get out of control with chunky bases. \n\n\ \tThe last command in the package is called IdealofPoints, and returns a \ Groebner basis of the ideal of all polynomials that vanish on the points you \ provide, plus a list of its remainder monomials. It is the implementation of \ the Buchberger-M\[ODoubleDot]ller algorithm found in [BM]. Its parameters \ are a list of points, a variable list, and an optional third parameter of the \ monomial order. If left unspecified, the monomial order is the order set by \ MonOrder. Please note that the dimension of the varlist must equal the \ dimension of each point, or else the points don't make much sense and \ IdealofPoints will complain. Also, the points must be written in list form. \ Here is an example:"], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MonOrder[]\)], "Input"], Cell[BoxData[ \(Grevlex\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(points\ = \ {{1, \ 2, \ 6}, \ {8, \ 8, \ 2}, \ {4, \ 5, \ 1}, \ {5, \ 12, \ 0}}\)], "Input"], Cell[BoxData[ \({{1, 2, 6}, {8, 8, 2}, {4, 5, 1}, {5, 12, 0}}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(IdealofPoints[points, \ {x, \ y, \ z}]\)], "Input"], Cell[BoxData[ \({{143\/35 + \(59\ x\)\/35 - \(73\ y\)\/70 - \(463\ z\)\/70 + z\^2, 159\/35 - \(93\ x\)\/35 + \(51\ y\)\/70 - \(179\ z\)\/70 + y\ z, 227\/35 - \(109\ x\)\/35 + \(53\ y\)\/70 - \(127\ z\)\/70 + x\ z, 1767\/35 + \(171\ x\)\/35 - \(1277\ y\)\/70 + y\^2 - \(267\ z\)\/70, 173\/5 - \(31\ x\)\/5 - \(53\ y\)\/10 + x\ y - \(33\ z\)\/10, 1138\/35 - \(381\ x\)\/35 + x\^2 - \(9\ y\)\/35 - \(129\ z\)\/35}, {1, z, y, x}}\)], "Output"] }, Open ]], Cell[TextData[{ "\tThe generators given above form a Groebner basis and generate a radical \ ideal (can you figure out why it's radical?). To prove that these equations \ to vanish on the given points, we will turn the polynomials into equations \ and have ", StyleBox["Mathematica", FontSlant->"Italic"], " solve them." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(polys\ = {143\/35 + \(59\ x\)\/35 - \(73\ y\)\/70 - \(463\ z\)\/70 + z\^2 == 0, 159\/35 - \(93\ x\)\/35 + \(51\ y\)\/70 - \(179\ z\)\/70 + y\ z\ == \ 0, 227\/35 - \(109\ x\)\/35 + \(53\ y\)\/70 - \(127\ z\)\/70 + x\ z\ == 0, 1767\/35 + \(171\ x\)\/35 - \(1277\ y\)\/70 + y\^2 - \(267\ z\)\/70\ == \ 0, 173\/5 - \(31\ x\)\/5 - \(53\ y\)\/10 + x\ y - \(33\ z\)\/10\ == \ 0, 1138\/35 - \(381\ x\)\/35 + x\^2 - \(9\ y\)\/35 - \(129\ z\)\/35\ == \ 0}\)], "Input"], Cell[BoxData[ \({143\/35 + \(59\ x\)\/35 - \(73\ y\)\/70 - \(463\ z\)\/70 + z\^2 == 0, 159\/35 - \(93\ x\)\/35 + \(51\ y\)\/70 - \(179\ z\)\/70 + y\ z == 0, 227\/35 - \(109\ x\)\/35 + \(53\ y\)\/70 - \(127\ z\)\/70 + x\ z == 0, 1767\/35 + \(171\ x\)\/35 - \(1277\ y\)\/70 + y\^2 - \(267\ z\)\/70 == 0, 173\/5 - \(31\ x\)\/5 - \(53\ y\)\/10 + x\ y - \(33\ z\)\/10 == 0, 1138\/35 - \(381\ x\)\/35 + x\^2 - \(9\ y\)\/35 - \(129\ z\)\/35 == 0}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[polys]\)], "Input"], Cell[BoxData[ \({{x \[Rule] 1, y \[Rule] 2, z \[Rule] 6}, {x \[Rule] 4, y \[Rule] 5, z \[Rule] 1}, {x \[Rule] 5, y \[Rule] 12, z \[Rule] 0}, {x \[Rule] 8, y \[Rule] 8, z \[Rule] 2}}\)], "Output"] }, Open ]], Cell["\<\ \tAmazingly enough, these points are the same as the points we \ started with. If you're still not convinced, you could convert the \ polynomial output of IdealofPoints to a Lex Groebner basis, and find the \ solutions yourself. \tI hope this tutorial has been helpful. If you have further questions, you \ can e-mail David Cox at dac@cs.amherst.edu. \tGood luck and have fun!\ \>", "Text", TextAlignment->Left] }, Open ]], Cell[CellGroupData[{ Cell["References", "Section"], Cell[TextData[{ "[CLO] D. Cox, J. Little, D. O'Shea, ", StyleBox["Using Algebraic Geometry,", FontSlant->"Italic"], " Springer-Verlag New York Inc., New York, 1998.\n[FGLM] J. \ Faug\[EGrave]re, P. Gianni, D. Lazrad, and T. Mora. ", StyleBox[ "Efficient computation of zero-dimensional Groebner bases by change of \ ordering", FontSlant->"Italic"], ", J. Symbolic Comput. ", StyleBox["16", FontWeight->"Bold"], " (1993), 329-344.\n[BM] B. Buchberger, H.M. M\[ODoubleDot]ller. ", StyleBox[ "The construction of multivariate polynomials with preassigned zeros,", FontSlant->"Italic"], " J. Lecture Notes in Comp. Sci., ", StyleBox["144", FontWeight->"Bold"], " (1982), 24-31, Marseille, France. Springer." }], "Text", TextAlignment->Left] }, Open ]], Cell[CellGroupData[{ Cell["Reference Guide", "Section"], Cell["\<\ \tThis guide gives formal descriptions of commands in the package. \ Commands are listed in order of complexity. \tNote that there is also on-line documentation for each of these commands. \ For example, to find out about the \"Buchberger\" command, type \t?Buchberger at the Mathematica prompt.. Any parameters listed in parentheses are optional.\ \>", "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["Monorder", "Subsubsection"], "\nThis command is used to set the monomial order used in all other \ commands in the package. The allowable monomial orders are denoted as \ follows:\n Lex (lexicographic order) \n Grlex (graded \ lexicographic order) \n Grevlex (graded reverse lexicographic order)\n \ {k,n} (elimination order, eliminating the first k of n variables) \n \ {{a11,...,a1n},...,{an1,...,ann}} (matrix order for n variables)\nNote the \ use of capital letters in the names of the first three of these orders. \ Thus, to change the monomial order to Grlex, you would issue the command \n\t\ MonOrder[Grlex]\nFurthemore, the command \n\tMonOrder[]\nwill return the \ current monomial order. This is useful if you've forgotten what the order \ is. The default monomial order is Lex." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["PRemainder", "Subsubsection"], "\nThe format for this command is\n\tPRemainder[f,{f1,...,fs},varlist] \n\ where f is the polynomial to be divided and {f1,...,fs} is the list of \ polynomials to divide by. The output will be the remainder of f on division \ by f1,...fs. \n\tThe \"varlist\" is a list of variables. You should be \ aware that the order of the variables in varlist is important since it \ (together with what you specified in MonOrder) determines the monomial \ order." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["PQuotient", "Subsubsection"], "\nThe format is\n\tPQuotient[f,{f1,...,fs},varlist] \nwhere f is the \ polynomial to be divided and {f1,...,fs} is the list of polynomials to divide \ by. The output will be a list of quotients {a1,...,as} of f on division by \ f1,...fs. The \"varlist\" is a list of variables that determines the order \ of the variables in the current monomial order." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["GroebnerQ ", "Subsubsection"], "\nThe format is\n\tGroebnerQ[{f1,...,fs},varlist,(torder)]\nThis command \ returns either True or False, depending on whether {f1,...,fs} forms a \ Groebner basis under the current monomial ordering or torder, if it is \ specified, with \"varlist\" determining the order of the variables used in \ the monomial order." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["Buchberger", "Subsubsection"], " or ", StyleBox["B", "Subsubsection"], "\nThe format is\n\tBuchberger[{f1,...,fs},varlist,options...] or \ B[{f1,...,fs},varlist,options...]\nwhere {f1,...,fs} is a list of polynomials \ and, \"varlist\" determines the order of the variables used in the current \ monomial order. The output of this command is a Groebner basis for the ideal \ with respect to the current monomial order, and it also prints \ out the number of times that PRemainder is performed. The algorithm employed \ is a naive version of the Buchberger algorithm, with the one efficiency that \ no S-polynomial that has already been checked is checked again. The output \ need not be a reduced Groebner basis, and the steps of the computation will \ be printed. If this printing is not desired, the option PrintSteps should be \ set to False." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["AltBuchberger ", "Subsubsection"], "or ", StyleBox["AB", "Subsubsection"], "\nThe format is\n\tAltBuchberger[{f1,...,fs},varlist,options...] or \ AB[{f1,...,fs},varlist,options...]\nThis command is a slightly modified \ version of Buchberger. It returns a Groebner basis for the ideal \ , with respect to the current monomial order and the order of \ varlist. It is the same algorithm as Buchberger, but uses the up-to-date \ constructed basis for all S-polynomial remainder computations. The output \ need not be a reduced Groebner basis, and the steps of the computation will \ be printed. If this printing is not desired, the option PrintSteps should be \ set to False." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["QuickBuchberger ", "Subsubsection"], "or ", StyleBox["QB", "Subsubsection"], "\nThe format is\n\tQuickBuchberger[{f1,...,fs},varlist,options...] or \ QB[{f1,...,fs},varlist,options...]\nThis command uses a more efficient \ version of the Buckberger algorithm to compute a Groebner basis for the ideal \ with respect to the current monomial order. As usual, \ \"varlist\" determines the order of the variables used in the current \ monomial order. The output need not be a reduced Groebner basis, and the \ steps of the computation will be printed. If this printing is not desired, \ the option PrintSteps should be set to False." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["MathematicaBuchberger ", "Subsubsection"], "or ", StyleBox["MB", "Subsubsection"], "\nThe format is\n\tMathematicaBuchberger[{f1,...,fs},varlist] or \ MB[{f1,...,fs},varlist,options...]\nThis command directly uses ", StyleBox["Mathematica", FontSlant->"Italic"], "'s GroebnerBasis command to find a reduced Groebner basis for the ideal \ with respect to the current monomial order. As usual, varlist \ determines the order of the variables." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["ReduceGroebner", "Subsubsection"], "\nThe format is\n\tReduceGroebner[{f1,...,fs},varlist,(torder)]\nThis \ command takes a Groebner basis {f1,...,fs} and produces a reduced Groebner \ basis for the same ideal. If specified, torder is the monomial ordering. \ If left unspecified, the monomial ordering is determined by what is set by \ MonOrder. Be sure not to change the monomial order or \"varlist\" from when \ you produced the Groebner basis." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["SPoly", "Subsubsection"], "\nThe format is\n\tSPoly[poly1,poly2,varlist] \nThis command returns the \ S-polynomial of poly1 and poly2, and \"varlist\" determines the order of the \ variables used in the current monomial order." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["IdealQ\n", "Subsubsection"], "The format is \n\tIdealQ[f,{f1,...,fs},varlist] \nThis is an \ implementation of the Ideal Membership Algorithm. The command returns either \ True or False, depending on whether the polynomial f is in the ideal \ , with \"varlist\"\ndetermining the order of the variables used in \ the current monomial order." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["RadicalQ", "Subsubsection"], "\nThe format is\n\tRadicalQ[f,{f1,...,fs},varlist] \nThis is an \ implementation of the Radical Membership Algorithm. The command returns \ either True or False, depending on whether the polynomial f is in the radical \ of the ideal , with \"varlist\" determining the order of the \ variables used in the current monomial order." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["FiniteQ", "Subsubsection"], "\nThe format is\n\tFiniteQ[{f1,...,fs},varlist] \nThis is an \ implementation of the Finiteness Algorithm. The command returns True or \ False, depending on whether the set of equations specified by f1=...=fs=0 has \ a finite number of solutions over the complex numbers." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["VSDimension", "Subsubsection"], "\nThe format is\n\tVSDimension[{f1,...,fs},varlist, (torder)] \nThis \ command returns the basis remainders and the dimension (as a vector space) of \ the polynomial ring modulo the ideal . The output is {Infinity, \ Infinity} if the quotient is infinite dimensional. If specified, torder sets \ the monomial order, and if unspecified, the monomial order is the order \ currently set by MonOrder." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["Radical", "Subsubsection"], "\nThe format is\n Radical[{f1,...fs}, varlist]\nThis command \ returns generators of the radical of the zero-dimesnional ideal . \ The returned polynomials do NOT necessarily form a Groebner basis." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["RadicalIdealQ", "Subsubsection"], "\n The format is\n RadicalIdealQ[{f1,...,fs}, varlist]\nThis \ command returns True if the zero-dimensional ideal generated by {f1,...,fs} \ is radical, and False otherwise." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["ConvertGB", "Subsubsection"], " \nThe format is\n ConvertGB[{f1,...,fs}, varlist, oldvarlist, \ options...]\nIn this command, {f1,...,fs} form a Groebner basis of a \ zero-dimensional ideal for oldvarlist and the current monomial order set by \ MonOrder. This monomial order specification can be changed by setting the \ option OldOrderType to the appropriate order. The other options are \ OrderType and PrintSteps. When OrderType is set to Grlex, ConvertGB returns \ a Groebner basis with respect to varlist and grlex that generates the same \ ideal as {f1,...,fs}. If set to Lex or left unset, ConvertGB returns a \ Groebner basis with respect to varlist and lex. In both cases, the remainder \ monomials with respect to the monomial ordering are also returned. If \ PrintSteps is set to True, every time the command adds a polynomial to the \ constructed Groebner basis, it will print that polynomial and print the \ remainder monomials added since the last polynomial was added, if any were \ added." }], "Text", TextAlignment->Left], Cell[TextData[{ StyleBox["IdealofPoints", "Subsubsection"], "\n The format is\n IdealofPoints[{P1,...,Ps}, varlist, (torder)]\n\ This command returns the Groebner basis of the ideal of all polynomials which \ vanish on points {P1,...,PS}. Each point is given as an n-dimensional \ vector. If left unspecified, torder is the monomial order set by MonOrder.\n\ " }], "Text", TextAlignment->Left] }, Open ]], Cell[CellGroupData[{ Cell["Acknowledgements", "Section"], Cell[TextData[{ "Will Gryc and David Cox would like to thank the Charleton Trust for \ supporting Will's work on this ", StyleBox["Mathematica", FontSlant->"Italic"], " notebook." }], "Text"] }, Open ]] }, Open ]] }, FrontEndVersion->"4.0 for X", ScreenRectangle->{{0, 1152}, {0, 900}}, WindowSize->{520, 600}, WindowMargins->{{267, Automatic}, {Automatic, 81}}, PrintingPageRange->{Automatic, Automatic}, PrintingOptions->{"PaperSize"->{612, 792}, "PaperOrientation"->"Portrait", "PostScriptOutputFile":>FrontEnd`FileName[{$RootDirectory, "home", "dac", \ "necuse", "gryc"}, "groebner40.nb.ps", CharacterEncoding -> "ISO8859-1"], "Magnification"->1} ] (*********************************************************************** Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. ***********************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1739, 51, 47, 0, 160, "Title"], Cell[1789, 53, 462, 9, 140, "Text"], Cell[CellGroupData[{ Cell[2276, 66, 29, 0, 57, "Section"], Cell[2308, 68, 509, 10, 140, "Text"], Cell[2820, 80, 48, 1, 27, "Input"], Cell[2871, 83, 349, 6, 86, "Text"], Cell[CellGroupData[{ Cell[3245, 93, 30, 0, 45, "Subsection"], Cell[3278, 95, 1405, 34, 230, "Text"], Cell[CellGroupData[{ Cell[4708, 133, 43, 1, 27, "Input"], Cell[4754, 136, 37, 1, 27, "Output"] }, Open ]], Cell[4806, 140, 438, 7, 104, "Text"], Cell[CellGroupData[{ Cell[5269, 151, 50, 1, 27, "Input"], Cell[5322, 154, 41, 1, 27, "Output"] }, Open ]], Cell[5378, 158, 164, 4, 50, "Text"], Cell[CellGroupData[{ Cell[5567, 166, 51, 1, 27, "Input"], Cell[5621, 169, 40, 1, 27, "Output"] }, Open ]], Cell[5676, 173, 235, 4, 68, "Text"], Cell[CellGroupData[{ Cell[5936, 181, 49, 1, 27, "Input"], Cell[5988, 184, 70, 1, 23, "Print"], Cell[6061, 187, 40, 1, 27, "Output"] }, Open ]], Cell[6116, 191, 200, 4, 68, "Text"], Cell[CellGroupData[{ Cell[6341, 199, 76, 1, 27, "Input"], Cell[6420, 202, 67, 1, 27, "Output"] }, Open ]], Cell[6502, 206, 584, 10, 176, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[7123, 221, 58, 0, 45, "Subsection"], Cell[7184, 223, 49, 0, 32, "Text"], Cell[CellGroupData[{ Cell[7258, 227, 50, 1, 27, "Input"], Cell[7311, 230, 41, 1, 27, "Output"] }, Open ]], Cell[7367, 234, 51, 0, 32, "Text"], Cell[CellGroupData[{ Cell[7443, 238, 73, 1, 27, "Input"], Cell[7519, 241, 54, 1, 29, "Output"] }, Open ]], Cell[7588, 245, 611, 11, 140, "Text"], Cell[CellGroupData[{ Cell[8224, 260, 87, 1, 27, "Input"], Cell[8314, 263, 47, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[8398, 269, 84, 1, 27, "Input"], Cell[8485, 272, 40, 1, 27, "Output"] }, Open ]], Cell[8540, 276, 534, 10, 158, "Text"], Cell[CellGroupData[{ Cell[9099, 290, 66, 1, 27, "Input"], Cell[9168, 293, 39, 1, 27, "Output"] }, Open ]], Cell[9222, 297, 72, 0, 32, "Text"], Cell[CellGroupData[{ Cell[9319, 301, 73, 1, 27, "Input"], Cell[9395, 304, 38, 1, 27, "Output"] }, Open ]], Cell[9448, 308, 162, 4, 50, "Text"], Cell[CellGroupData[{ Cell[9635, 316, 43, 1, 27, "Input"], Cell[9681, 319, 41, 1, 27, "Output"] }, Open ]], Cell[9737, 323, 691, 10, 158, "Text"], Cell[CellGroupData[{ Cell[10453, 337, 67, 1, 27, "Input"], Cell[10523, 340, 276, 6, 23, "Print"], Cell[10802, 348, 64, 1, 23, "Print"], Cell[10869, 351, 354, 9, 25, "Print"], Cell[11226, 362, 206, 4, 23, "Print"], Cell[11435, 368, 355, 9, 25, "Print"], Cell[11793, 379, 206, 4, 23, "Print"], Cell[12002, 385, 328, 8, 25, "Print"], Cell[12333, 395, 206, 4, 23, "Print"], Cell[12542, 401, 190, 4, 23, "Print"], Cell[12735, 407, 206, 4, 23, "Print"], Cell[12944, 413, 159, 3, 23, "Print"], Cell[13106, 418, 127, 2, 29, "Output"] }, Open ]], Cell[13248, 423, 367, 6, 86, "Text"], Cell[CellGroupData[{ Cell[13640, 433, 101, 2, 27, "Input"], Cell[13744, 437, 127, 2, 29, "Output"] }, Open ]], Cell[13886, 442, 525, 8, 122, "Text"], Cell[CellGroupData[{ Cell[14436, 454, 110, 2, 27, "Input"], Cell[14549, 458, 76, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[14662, 464, 78, 1, 27, "Input"], Cell[14743, 467, 460, 13, 25, "Print"], Cell[15206, 482, 206, 4, 23, "Print"], Cell[15415, 488, 758, 24, 41, "Print"], Cell[16176, 514, 206, 4, 23, "Print"], Cell[16385, 520, 1855, 65, 61, "Print"], Cell[18243, 587, 208, 4, 23, "Print"], Cell[18454, 593, 190, 4, 23, "Print"], Cell[18647, 599, 210, 4, 23, "Print"], Cell[18860, 605, 161, 3, 23, "Print"], Cell[19024, 610, 525, 8, 83, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[19586, 623, 81, 1, 27, "Input"], Cell[19670, 626, 460, 13, 25, "Print"], Cell[20133, 641, 206, 4, 23, "Print"], Cell[20342, 647, 355, 9, 25, "Print"], Cell[20700, 658, 206, 4, 23, "Print"], Cell[20909, 664, 482, 14, 25, "Print"], Cell[21394, 680, 206, 4, 23, "Print"], Cell[21603, 686, 190, 4, 23, "Print"], Cell[21796, 692, 208, 4, 23, "Print"], Cell[22007, 698, 159, 3, 23, "Print"], Cell[22169, 703, 200, 4, 47, "Output"] }, Open ]], Cell[22384, 710, 110, 3, 50, "Text"], Cell[CellGroupData[{ Cell[22519, 717, 62, 1, 27, "Input"], Cell[22584, 720, 38, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[22659, 726, 62, 1, 27, "Input"], Cell[22724, 729, 38, 1, 27, "Output"] }, Open ]], Cell[22777, 733, 382, 6, 104, "Text"], Cell[CellGroupData[{ Cell[23184, 743, 56, 1, 27, "Input"], Cell[23243, 746, 46, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[23326, 752, 66, 1, 27, "Input"], Cell[23395, 755, 190, 4, 23, "Print"], Cell[23588, 761, 64, 1, 23, "Print"], Cell[23655, 764, 157, 3, 23, "Print"], Cell[23815, 769, 46, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[23898, 775, 68, 1, 27, "Input"], Cell[23969, 778, 190, 4, 23, "Print"], Cell[24162, 784, 206, 4, 23, "Print"], Cell[24371, 790, 157, 3, 23, "Print"], Cell[24531, 795, 46, 1, 29, "Output"] }, Open ]], Cell[24592, 799, 330, 8, 68, "Text"], Cell[CellGroupData[{ Cell[24947, 811, 71, 1, 27, "Input"], Cell[25021, 814, 61, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[25119, 820, 66, 1, 27, "Input"], Cell[25188, 823, 190, 4, 23, "Print"], Cell[25381, 829, 206, 4, 23, "Print"], Cell[25590, 835, 157, 3, 23, "Print"], Cell[25750, 840, 61, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[25848, 846, 68, 1, 27, "Input"], Cell[25919, 849, 190, 4, 23, "Print"], Cell[26112, 855, 206, 4, 23, "Print"], Cell[26321, 861, 157, 3, 23, "Print"], Cell[26481, 866, 61, 1, 29, "Output"] }, Open ]], Cell[26557, 870, 1668, 30, 356, "Text"], Cell[CellGroupData[{ Cell[28250, 904, 78, 1, 27, "Input"], Cell[28331, 907, 127, 2, 29, "Output"] }, Open ]], Cell[28473, 912, 511, 13, 104, "Text"], Cell[CellGroupData[{ Cell[29009, 929, 148, 3, 43, "Input"], Cell[29160, 934, 134, 2, 29, "Output"] }, Open ]], Cell[29309, 939, 887, 14, 320, "Text"], Cell[30199, 955, 252, 5, 68, "Text"], Cell[CellGroupData[{ Cell[30476, 964, 81, 1, 27, "Input"], Cell[30560, 967, 47, 1, 27, "Output"] }, Open ]], Cell[30622, 971, 100, 3, 32, "Text"], Cell[30725, 976, 110, 3, 50, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[30884, 985, 51, 0, 57, "Section"], Cell[30938, 987, 248, 5, 68, "Text"], Cell[CellGroupData[{ Cell[31211, 996, 205, 3, 43, "Input"], Cell[31419, 1001, 177, 3, 47, "Output"] }, Open ]], Cell[31611, 1007, 410, 6, 104, "Text"], Cell[CellGroupData[{ Cell[32046, 1017, 93, 1, 27, "Input"], Cell[32142, 1020, 39, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[32218, 1026, 135, 2, 43, "Input"], Cell[32356, 1030, 38, 1, 27, "Output"] }, Open ]], Cell[32409, 1034, 509, 8, 122, "Text"], Cell[CellGroupData[{ Cell[32943, 1046, 77, 1, 27, "Input"], Cell[33023, 1049, 63, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[33123, 1055, 74, 1, 27, "Input"], Cell[33200, 1058, 38, 1, 27, "Output"] }, Open ]], Cell[33253, 1062, 889, 20, 194, "Text"], Cell[CellGroupData[{ Cell[34167, 1086, 48, 1, 27, "Input"], Cell[34218, 1089, 39, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[34294, 1095, 164, 3, 43, "Input"], Cell[34461, 1100, 127, 2, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[34625, 1107, 64, 1, 27, "Input"], Cell[34692, 1110, 38, 1, 27, "Output"] }, Open ]], Cell[34745, 1114, 1403, 21, 320, "Text"], Cell[CellGroupData[{ Cell[36173, 1139, 68, 1, 27, "Input"], Cell[36244, 1142, 1240, 17, 209, "Output"] }, Open ]], Cell[37499, 1162, 91, 3, 32, "Text"], Cell[CellGroupData[{ Cell[37615, 1169, 80, 1, 27, "Input"], Cell[37698, 1172, 1038, 15, 191, "Output"] }, Open ]], Cell[38751, 1190, 500, 9, 140, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[39288, 1204, 29, 0, 57, "Section"], Cell[39320, 1206, 812, 12, 176, "Text"], Cell[CellGroupData[{ Cell[40157, 1222, 203, 3, 43, "Input"], Cell[40363, 1227, 177, 3, 47, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[40577, 1235, 88, 1, 27, "Input"], Cell[40668, 1238, 301, 5, 65, "Output"] }, Open ]], Cell[40984, 1246, 206, 4, 68, "Text"], Cell[CellGroupData[{ Cell[41215, 1254, 81, 1, 27, "Input"], Cell[41299, 1257, 39, 1, 27, "Output"] }, Open ]], Cell[41353, 1261, 101, 3, 32, "Text"], Cell[CellGroupData[{ Cell[41479, 1268, 84, 1, 27, "Input"], Cell[41566, 1271, 38, 1, 27, "Output"] }, Open ]], Cell[41619, 1275, 1792, 26, 410, "Text"], Cell[CellGroupData[{ Cell[43436, 1305, 50, 1, 27, "Input"], Cell[43489, 1308, 41, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[43567, 1314, 105, 2, 27, "Input"], Cell[43675, 1318, 961, 15, 173, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[44673, 1338, 120, 3, 27, "Input"], Cell[44796, 1343, 803, 12, 306, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[45636, 1360, 206, 4, 59, "Input"], Cell[45845, 1366, 365, 9, 25, "Print"], Cell[46213, 1377, 299, 8, 25, "Print"], Cell[46515, 1387, 286, 7, 23, "Print"], Cell[46804, 1396, 279, 7, 23, "Print"], Cell[47086, 1405, 505, 14, 42, "Print"], Cell[47594, 1421, 239, 6, 25, "Print"], Cell[47836, 1429, 541, 16, 42, "Print"], Cell[48380, 1447, 508, 15, 42, "Print"], Cell[48891, 1464, 536, 15, 42, "Print"], Cell[49430, 1481, 820, 24, 60, "Print"], Cell[50253, 1507, 783, 23, 60, "Print"], Cell[51039, 1532, 823, 25, 60, "Print"], Cell[51865, 1559, 564, 16, 42, "Print"], Cell[52432, 1577, 851, 24, 60, "Print"], Cell[53286, 1603, 1278, 21, 332, "Output"] }, Open ]], Cell[54579, 1627, 820, 11, 194, "Text"], Cell[CellGroupData[{ Cell[55424, 1642, 43, 1, 27, "Input"], Cell[55470, 1645, 41, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[55548, 1651, 124, 2, 27, "Input"], Cell[55675, 1655, 79, 1, 27, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[55791, 1661, 71, 1, 27, "Input"], Cell[55865, 1664, 499, 7, 224, "Output"] }, Open ]], Cell[56379, 1674, 343, 8, 86, "Text"], Cell[CellGroupData[{ Cell[56747, 1686, 585, 10, 224, "Input"], Cell[57335, 1698, 503, 7, 224, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[57875, 1710, 45, 1, 27, "Input"], Cell[57923, 1713, 217, 3, 43, "Output"] }, Open ]], Cell[58155, 1719, 428, 11, 158, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[58620, 1735, 29, 0, 57, "Section"], Cell[58652, 1737, 792, 22, 158, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[59481, 1764, 34, 0, 57, "Section"], Cell[59518, 1766, 408, 11, 176, "Text"], Cell[59929, 1779, 889, 14, 284, "Text"], Cell[60821, 1795, 551, 10, 158, "Text"], Cell[61375, 1807, 451, 8, 122, "Text"], Cell[61829, 1817, 415, 8, 122, "Text"], Cell[62247, 1827, 934, 16, 212, "Text"], Cell[63184, 1845, 759, 14, 176, "Text"], Cell[63946, 1861, 716, 13, 158, "Text"], Cell[64665, 1876, 533, 12, 122, "Text"], Cell[65201, 1890, 517, 9, 140, "Text"], Cell[65721, 1901, 292, 6, 104, "Text"], Cell[66016, 1909, 417, 8, 140, "Text"], Cell[66436, 1919, 436, 8, 140, "Text"], Cell[66875, 1929, 367, 7, 122, "Text"], Cell[67245, 1938, 508, 9, 140, "Text"], Cell[67756, 1949, 311, 6, 104, "Text"], Cell[68070, 1957, 281, 6, 104, "Text"], Cell[68354, 1965, 1083, 17, 248, "Text"], Cell[69440, 1984, 409, 8, 140, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[69886, 1997, 35, 0, 57, "Section"], Cell[69924, 1999, 201, 6, 50, "Text"] }, Open ]] }, Open ]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)