Adapted from Ideals, Varieties, and Algorithms Third Edition, 2007

Appendix C

Computer Algebra Systems

1 AXIOM

For us, the most important AXIOM commands are [normalForm]?, for doing the division algorithm, and [groebner]?, for computing a Groebner basis.

A distinctive feature of AXIOM is that every object has a specific type. In particular, this affects the way AXIOM works with monomial orders: an order is encoded in a special kind of type. For example, suppose we want to use lex order on with . This is done using the type:

  DMP([x,y,z], FRAC INT)

(remember that AXIOM encloses a list inside brackets [...]). Here DMP stands for "Distributed Multivariate Polynomial", and FRAC INT means fractions of integers, i.e. rational numbers. Similarly, grevlex for with means using the type:

  HDMP([x,y,z],FRAC INT)

where HDMP stands for "Homogeneous Distributed Multivariate Polynomial". At the end of the section, we will explain how to get AXIOM to work with grlex order.

To see how this works in practice, we will divide by and using grevlex order with . We first give the three polynomials names and declare their types:

f : HDMP([x,y], FRAC INT) := x^3+3*y^2

(1)

g : HDMP([x,y], FRAC INT) := x^2+y

(2)

h : HDMP([x,y], FRAC INT) := x+2*x*y

(3)

(Here colon : indicates a type declaration. You can save typing by giving:

  HDMP([x,y], FRAC INT)

a symbolic name.) Then the remainder is computed by the command:

normalForm(f,[g,h])

(4)

The output is the remainder of f on division by g, h. In general the syntax of the command is:

  normalForm(poly, polylist)

where poly is the polynomial to be divided by the polynomials in the list polylist (assuming that everything has been declared to be of the appropriate type).

To do the same computation using lex order with , first issue the command:

Lex := DMP([x,y], FRAC INT)

(5)

to give:

  DMP([x,y], FRAC INT)

the symbolic name Lex, and then type:

normalForm(f::Lex, [g::Lex, h::Lex])

(6)

Here, we are using AXIOM's type conversion facility :: to convert from one type to another.

The syntax for the groebner command is:

  groebner(polylist)

This computes a Groebner basis for the ideal generated by the polynomials in polylist (of the appropriate type). The answer is reduced in the sense of Chapter 2, 7. For example, if g, h are as above, then the command:

gb := groebner([g,h])

(7)

computes a list (and gives it the symbolic name gb) which is a Groebner basis for the ideal with respect to grevlex for . Also, if you want information about the intermediate stages of the calculation, you can include the options "redcrit" or "info" in the groebner command. For example, the command:

groebner([g,h], "redcrit")

    reduced Critpair - Polynom :

    2   1
   y  + - y
        2

    reduced Critpair - Polynom :

   0

       THE GROEBNER BASIS POLYNOMIALS

(8)

will print out the remainders of S-polynomials (only one in this case) generated during the course of the computation. Adding the "info" option yields even more information.

AXIOM can also work with coefficients in a variety of fields besides . this is easily done by replacing FRAC INT in the type declarations. For instance, to compute Groebner basis over the field of rational functions in polynomials with integer coefficients, one uses FRAC POLY INT. To see how this works, let us compute a Groebner basis for the ideal using lex order with . This is accomplished by the following AXIOM commands:

m : List DMP([x,y], FRAC POLY INT)

m := [v*x^2 + y, u*x*y + y^2]

(9)

groebner(m)

(10)

Notice that this illustrates another method for declaring the type of polynomials used in a Grobner basis computation.

Other fields are just as easy: one uses FRAC COMPLEX INT for the field of Gaussian rational numbers (note that AXIOM writes as %i) and PrimeField(p) for a finite field with p elements (where p is a prime). It is also possible to compute Groebner bases over arbitrary finite fields. AXIOM's method of working with finite fields is explained in Section 8.11 of JENKS and SUTOR (1992) (See: Axiom Documentation). The ability to "insert" the field you want to compute Groebner bases over is a good illustration of the power of AXIOM.

Besides working with lists of polynomials, AXIOM also allows the user to declare a list of polynomials to be an ideal. The syntax of the ideal command is:

  ideal polylist

where polylist is a list of polynomials of the appropriate type. This is useful because AXIOM has a number of commands which apply to ideals (PolynomialIdeals?):

• intersect, which computes the intersection of a list of ideals.
• zeroDim?, which determines (using the methods of Chapter 5, 3) if the equations have finitely many solutions over an algebraically closed field.
• dimension, which computes the dimension of the variety defined by an ideal.
• prime?, which determines whether an ideal is prime.
• radical, which computes the radical of an ideal.
• primaryDecomp, which computes the primary decomposition of an ideal.

Examples of how to use these and other related commands can be found in Section 8.12 of JENKS and SUTOR (1992). We should also mention that there are the commands leadingMonomial and leadingCoefficient for extracting the leading term and coefficient of a polynomial.

All of the commands described so far require that you declare in advance the type of polynomial you'll be using. However, if you only need Groebner bases in lex or grevlex order with rational coefficients, then a simpler approach is to use the AXIOM commands lexGroebner and totalGroebner. For example, the command:

lexGroebner([2*x^2+y,2*y^2+x], [x,y])

(11)

computes a Greobner basis (reduced up to constants) for the ideal using lex order with . Notice that we didn't have to declare the type of the polynomials in advance - lexGroebner takes care of this. To do the same computation using grevlex, simply replace lexGroebner with totalGoebner.

We will end this section by explaining how to get AXIOM to work with grlex order. All of the raw material need is present in AXIOM, though it takes a little work to put it together. For concreteness, suppose we want grlex order on x>y$. Then issue the commands:

)set expose add constructor GDMP

   GeneralDistributedMultivariatePolynomial is now explicitly exposed 
      in frame initial 

)set expose add constructor ODP

   OrderedDirectProduct is now explicitly exposed in frame initial 
Grlex := GDMP([x,y], FRAC INT, ODP(2,NNI,totalLex$ORDFUNS(2,NNI)));

The basic idea here is that GDMP stands for "Generalized Distributed Multivariate Polynomial", this can be used to create an AXIOM type for any monomial order, and totalLex is the function which orders exponent vectors using grlex. By declaring polynomials to be of type Grlex, you can now compute Groebner bases using grlex with .

groebner([g::Grlex, h::Grlex])

   Cannot convert the value from type 
      HomogeneousDistributedMultivariatePolynomial([x,y],Fraction(
      Integer)) to GeneralDistributedMultivariatePolynomial([x,y],
      Fraction(Integer),OrderedDirectProduct(2,NonNegativeInteger,
      theMap(ORDFUNS;totalLex;2VB;2,303))) .

We should caution that type conversion doesn't work between Grlex and the monomial orders created by DMP and HDMP, though it is possible to write type conversion routines.

j : Grlex := x^2+y

(12)

k : Grlex := x+2*x*y

(13)

groebner([j, k])

(14)

Using the AXIOM concept of a package, one could write a package which knows all of the monomial orders mentioned in the exercises to Chapter 2, 4, along with commands to convert one type to the other.

When constructing multivariate polynomials with symbolic parameters variable names (generators) must be specified. Unspecified names default to parameters. The choice of variables and parameters will affect the computation of a basis.

param := FRAC POLY INT

(15)

--vars := [ca,cb,sa,sb,x,y,r1,r2,r3,lab,lac]
--vars := [ca,sa,x,y]
vars := [ca,cb,sa,sb,x,y]

(16)

mm:List DMP(vars,param) := [x^2+y^2-r1^2,(x+lab*ca)^2+(y+lab*sa)^2-r2^2,(x+lac*(ca*cb-sa*sb))^2+(y+lac*(sa*cb+ca*sb))^2-r3^2,ca^2+sa^2-1]

(17)

b := groebner(mm); #b

(18)

for i in b repeat
  outputAsTex i

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

(27)

(28)

(29)

(30)