In this section, functions for computing with the ideals I of a multivariate polynomial ring R = K[x1,…,xn] will be discussed. Since it is assumed that the base ring K is a field or Euclidean domain, all polynomial rings R are Noetherian, meaning that any ideal I is finitely generated. The notation <a1,…,am> is used to denote the ideal I generated by this collection of elements.
The ideal I can be thought of as coming from the polynomial system a1,…,am and, conversely, any polynomial system generates an ideal I. The significance of the ideal is roughly as follows. The variety V(a1,…,am) of a polynomial system is the set of n-tuples (u1,…,un) over the algebraic closure of K at which all ai simultaneously vanish. The polynomials that vanish on V are precisely those in the radical of I, rad(I). The radical is the ideal formed by all polynomials f such that a power fk∈I for some k ≥ 1. Thus, there is a 1–1 correspondence between algebraic sets (sets of simultaneous solutions/zeroes of sets of polynomials), and radical ideals in the polynomial ring. The variety V(I) = V(a1,…,am) is a (reduced) affine algebraic scheme in the terminology of algebraic geometry.
There will be many possible distinct finite bases for an ideal I. Computationally, the most important bases are the Gröbner bases. There is a unique Gröbner basis for each total ordering satisfying a number of properties of the monomials of R. An appropriate Gröbner basis is used in the algorithms for the implementation of all of the non-trivial functionality on polynomial ideals.
An essential basic function is the one that computes the dimension of an ideal (strictly speaking, the Krull dimension of the quotient ring R/I) which is the Zariski dimension of the associated algebraic set V(I). The ideal I has dimension 0 precisely when V(I) consists of a finite set of points. If I can be generated by r elements, its dimension is at least n – r but equality holds only for the special case of complete intersections. For example, when n = 3, Magma computes that the dimension of < x12 + x22, x23 + x33 > is 1 but that of < x22 – x1x3, x1 – x13 – x2x32, x2 – x12x2 – x33 > is also 1 but the second ideal cannot be generated by two elements.
Two of the most important operations are the computation of the colon ideal (I : J) of two ideals and the saturation (I : J∞). These perform a type of ideal division. The polynomial f∈(I : J) if and only if f*J⊆I and f∈(I : J∞) if and only if there is a power of f, fk with k ≥ 1 such that fk*J⊆I. Geometrically, these correspond to difference operations on varieties. The variety V((I : J∞)), for instance, is the Zariski closure of the difference set V(I)/V(J). As a simple example with n = 2 consider I = <x13 – x1 – x22, x12 + x1x2 – 1> for which V(I) is the finite set of points on the intersection of an elliptic curve and a conic in the affine plane. We compute the saturation of I by <x2> to get <x1x2 + x1 + x22, x12 + x2, x2 – x1x2 + 1>. These new equations define the set of points in V(I) with x2 ≠ 0 (two points have been removed).
Elimination ideals may also be computed. These are the ideals formed by intersecting I with the polynomial subring of R generated by a subset of the variables. This gives the polynomials in I that are polynomials in the chosen subset of the variables and can be thought of as resulting from the elimination of a number of variables from the original system of polynomial equations. Resultants are also available, which can be used to get a partial result when eliminating one variable.
Amongst many other things, elimination ideals are used to compute images of varieties under polynomial maps. For example, to find the image of the affine line under the map t→(t + t2, t3 – t, t3 – t2 + 1) into 3-space, we can eliminate t from the ideal <x – t – t2, y – t3 + t, z – t3 + t2 – 1> to get the ideal of defining equations of the image:
From this point of the section onwards, most of the functions only apply when K is a field and this is now assumed to be the case.
The radical rad(I) of an ideal I gives the full set of polynomials vanishing on V(I). It can be essential to compute this in order to determine #V(I) or the degree of V(I) in the positive dimensional case, and also to compare whether 2 algebraic sets are equal.
More generally, there are a number of important decompositions of an ideal as an intersection of ideals of a particular type. Every ideal has a primary decomposition into primary ideals, which are generalisations of prime-power ideals. Radical decomposition decomposes the radical of the ideal into an intersection of prime ideals. These define the irreducible components of V(I). Equidimensional decomposition is an easier and faster decomposition into an intersection of ideals each of which is the intersection of all primary components of I of a given dimension. This can be computed without computing the individual primary factors and is useful in a number of contexts.
Magma can compute all of these decompositions. They are all heavy computations but we have sped things up significantly in recent years by using homogenisation techniques.
In the particular case of dimension zero, the following may also be computed:
In geometry and other mathematical applications of commutative algebra, homogeneity often plays a key role. A polynomial f is homogeneous with respect to a (positive) integer weighting (w1,…,wn) of the variables if each monomial that occurs in f has the same weight. The standard case is where each variable has weight 1, which is traditionally what is referred to as homogeneity. The term weighted-homogeneous is often used used when referring to properties and functions that apply to cases of more general weightings. An ideal is (weighted)-homogeneous if it can be generated by homogeneous polynomials. Modules with the homogeneity property are referred to as graded and functionality for them will be described in their section.
There is a filtration and finiteness associated to homogeneous ideals and graded modules that is theoretically and computationally very important. The ideal or module breaks up into a direct sum of pieces of given weight (or grading) and each piece is finite-dimensional as a vector space over the base field K. Magma has an option for Hilbert-driven Gröbner basis computation. This allows some the computation to proceed by graded piece with more efficient criteria for termination.
The most fundamental objects associated to a graded module are the Hilbert series and Hilbert polynomial (the latter only for the standard weighting). These are computed in Magma using a fast Gröbner-based algorithm. They are used to determine important geometric invariants of the algebraic scheme in (weighted) projective space defined by I, such as the degree and arithmetic genus. For instance, the Hilbert polynomial of the ideal defining a Veronese surface X in 5-dimensional projective space is computed to be P(t) = 2t2 + 3t + 1. This shows that the degree is 4 = 2×2 (twice the leading coefficient) and the arithmetic genus is 0 = P(0) – 1.
For many operations on ideals it is important to try to minimise the number of generators that define the ideal I. In general, it is a very hard problem to determine a genuinely minimal set of generators of I. However, it is possible in the weighted-homogeneous case and in that case a minimal basis can be computed in Magma.
The following important computational tools for a polynomial ideal I of dimension d or its quotient algebra R/I are also available in Magma:
A nice example of normalisation is for the principal ideal I in R = ℚ[x,y] generated by the polynomial (x – y)x(x2 + y)3 – y3(x3 + xy – y2). This is a singular, affine model of the the modular curve X1(11) that arises naturally. Basic normalisation of I with the function field method is very fast (about 0.03s on our current machines) and returns a reasonable presentation of the normalisation of R/I as a 5-variable algebra which can be tidied up to give 3-variables by some straightforward substitution. The normalisation using the function field method with the option of simplification by Riemann–Roch filtration takes 0.11s but returns the result in the form R/J (so just using the original 2 variables) where J is generated by a single degree 3 polynomial which is an affine form of an elliptic curve equation for X1(11). This is much faster than de Jong's method that can take several hours.