Commutative Algebra
Commutative algebra is the study of rings of (multivariate) polynomials over a field. For example, the ring Q[x,y,z] is the ring of polynomials in the variables x, y, and z, with coefficients in Q. The main thing that commutative algebra is used for is algebraic geometry - where we're interested in the relationship between an ideal (a set of polynomials) and the curve, surface, or in general, the variety which it defines (the set of zeros of the polynomials). For example, we know that the equation x^2+y^2=1 has the unit circle as its zero-set.
The reason commutative algebra is so useful in algebraic geometry is that there is a kind of translation dictionary so that questions about varieties can be translated into questions about ideals, and vice versa. For example, if we want to look at the union of two varieties, we look at the intersection of the corresponding ideals.
The relationship between commutative algebra and algebraic geometry is very natural. However, commutative algebra can also be used to study other areas of mathematics, such as combinatorics or topology. In these cases, the "translation dictionaries" are more like inventions than discoveries. The reason this is worth doing is that problems in combinatorics or topology can often become more tractable, or be dealt with more elegantly, when translated into commutative algebra.
The core algorithm in computational commutative algebra is Buchberger algorithm. It allows us to find a "Groebner basis" for an ideal. This is a kind of canonical form, from which many of the properties that we are interested in can be more easily calculated.
module MPoly
This module defines our representation of multivariate polynomials, and the standard operations on them.
We generally work either over the rationals, or over a finite field.
Exports
data MPoly a - the type of multivariate polynomials over a field a. (The code has only been tested for MPoly QQ and MPoly FF.)
x, y, z, s, t, u, v, w, a, b, c, d :: MPoly QQ - stock variables from which mpolys can be constructed using the arithmetic operations +, -, * (and ^)
- for example x^2 + y*z - 1.
x0, x1, x2, x3 :: MPoly QQ - an alternative set of indexed variables. These are generally more useful when we're constructing our mpolys
in code from some other mathematical object.
Note that the two sets of variables can't be mixed - x1+y will produce an error.
x_ :: Int -> MPoly QQ - construct the ith variable, for example x_ 4 + x_ 5.
degMP :: MPoly a -> Int - the degree of an mpoly.
quotRemMP - the multivariate division algorithm, used for calculation of Groebner bases
(%%) :: MPoly a -> [MPoly a] -> MPoly a - compute the residue of an mpoly relative to an mpoly basis.
(/%) :: MPoly QQ -> Integer -> MPoly FF - convert an mpoly over QQ to an mpoly over a finite field.
Examples
(a+b)^2 %% [a^2-2, b^2-3] returns 2ab+5 (which says that (sqrt2+sqrt3)^2 is 5+2sqrt6).
(x+2)*(x+3) /% 5 returns x^2+1 an mpoly over F5
module GBasis
This module provides an efficient implementation of the Buchberger algorithm to find Groebner bases. The implementation is based on the paper
"One sugar cube please, or Selection strategies in the Buchberger algorithm", by Giovini, Mora, Niesi, Robbiano, Traverso.
Exports
gb :: [MPoly a] -> [MPoly a] - given a set of polynomials, returns a minimal reduced Groebner basis for the ideal they generate.
Examples
gb [x^3-y^5, x^2-y^6] returns [x^6-x^2y^4,y^5-x^3,x^3y-x^2].
By default, Grevlex term order is used. Lex and Grlex are also supported - see the code for details.
module Ideals
This module provides some standard operations on ideals, many of which have geometrical significance:
Exports
<==> - equality testing
memberIdeal, memberGB - membership testing
idealSum - the sum of two ideals. Geometrically, this corresponds to the intersection of two varieties.
idealProduct - this corresponds to the union of two varieties.
idealIntersection - this also corresponds to the union of two varieties.
idealQuotient - this is an algebraic construction which corresponds to taking the difference of two varieties.
idealSaturation
eliminatev - elimination ideals. These can be used to convert from a parametric representation of a variety to an implicit representation (see examples).
Examples
Consider the ideals [x] and [y], corresponding to the lines x=0 and y=0. Then
idealSum [x] [y] returns [x,y], which corresponds to the point (0,0), the intersection of the two lines.
idealProduct [x] [y] returns [xy], which corresponds to the union of the two lines.
idealQuotient [x*y] [y] returns [x] - this says that if you start with the union of the two lines, and take away the line y=0,
you are left with the line x=0. (In fact the ideal quotient corresponds to the Zariski closure of the difference between the varieties,
which is why we didn't lose the point (0,0).)
eliminatev [t] [x*(1+t^2)-(1-t^2), y*(1+t^2)-2*t] returns [x^2+y^2-1]
- we have converted from the parametric representation of the circle to the implicit representation.
eliminatev [s,t] [x-s^3, y-s^2*t, z-s*t^2, w-t^3] returns [y^2-xz,yz-xw,z^2-yw] - this is the "twisted cubic".
(Ideally, I'd also have functions for computing radicals and primary decompositions.)
module HilbertFunction
The Hilbert function is an algebraic invariant which gives us important geometric information about a variety. Let R = k[x1,...,xn] be a polynomial ring
and I the ideal corresponding to a variety V. (For example, R=C[x,y], I=< x^2+y^2-1 >, V=the unit circle.) Then the ring of polynomial functions on V,
denoted k[V], can be identified with the quotient ring R/I. We can consider R/I as a vector space over k, and find a basis consisting of monomials.
We can split the space into pieces by collecting together monomials of the same degree. The Hilbert function is then the number of monomials of degree i.
Its geometrical significance is that it gives us a picture of how big the space of polynomial functions on V is.
Among other things, this can be used to find out the dimension of V (in the sense that a curve is one-dimensional, a surface two-dimensional, etc).
Exports
mbasis vs - return the monomials over variables vs, sorted by degree
mbasisQR vs fs - return the monomials over variables vs which are not in the ideal generated by fs, sorted by degree
hilbertFunctionQR vs fs i - return the number of monomials of degree i over variables vs which are not in the ideal generated by fs
hilbertSeriesQR vs fs - return the values of the Hilbert function for i = 0, 1, .. as a list
hilbertPolyQR vs fs - it turns out that for large i, the value of the Hilbert function is given by a polynomial in i
dimension vs fs - the dimension of an affine variety, defined to be the 1 + degree of the Hilbert polynomial
Examples
take 5 (mbasis [x,y]) returns [[1],[x,y],[x^2,xy,y^2],[x^3,x^2y,xy^2,y^3],[x^4,x^3y,x^2y^2,xy^3,y^4]]
mbasisQR [x,y] [x^2+y^2-1] returns [[1],[x,y],[xy,y^2],[xy^2,y^3],[xy^3,y^4]... What's happening is that the polynomial x^2+y^2-1
means that in the quotient ring, x^2 == 1-y^2 - so x^2 is not linearly independent of {1,y^2} in the vector space. That is why the monomial basis
doesn't include any monomials which are divisible by x^2. This leads to an obvious pattern - for i > 0, there are exactly two monomials of degree i.
Hence take 10 (hilbertSeriesQR [x,y] [x^2+y^2-1]) returns [1,2,2,2,2,2,2,2,2,2], and
hilbertPolyQR [x,y] [x^2+y^2-1] returns 2.