0. Algorithms for Polynomials

Back

In this section, we first review some basic definitions from commutative algebra,

and then we derive some algorithms for working in polynomial rings. Those not

interested in algorithms can skip the section.

Throughout the section, k will be a field (not necessarily algebraically).

Ideals. Let A be a ring. Recall that an ideal a in A is a subset such that

(a) a is a subgroup of A regarded as a group under addition;

(b) a ∈ a, r ∈ A ⇒ ra ∈ A.

The ideal generated by a subset S of A is the intersection of all ideals A containing

a — it is easy to verify that this is in fact an ideal, and that it consists of all finite

sums of the form

_

risi with ri ∈ A, si ∈ S. When S = {s1, . . . , sm}, we shall write

(s1, . . . , sm) for the ideal it generates.

Let a and b be ideals in A. The set {a + b | a ∈ a, b ∈ b} is an ideal, denoted

by a + b. The ideal generated by {ab | a ∈ a, b ∈ b} is denoted by ab. Note that

ab ⊂ a ∩ b. Clearly ab consists of all finite sums

_

aibi with ai ∈ a and bi ∈ b, and

if a = (a1, . . . , am) and b = (b1, . . . , bn), then ab = (a1b1, . . . , aibj, . . . , ambn).

Let a be an ideal of A. The set of cosets of a in A forms a ring A/a, and a _→ a+a is

a homomorphism ϕ: A → A/a. Themap b _→ ϕ−1(b) is a one-to-one correspondence

between the ideals of A/a and the ideals of A containing a.

An ideal p if prime if p _= A and ab ∈ p ⇒ a ∈ p or b ∈ p. Thus p is prime if and

only if A/p is nonzero and has the property that

ab = 0, b_= 0 ⇒ a = 0,

i.e., A/p is an integral domain.

An ideal m is maximal if m _= A and there does not exist an ideal n contained

strictly between m and A. Thus m is maximal if and only if A/m has no proper

nonzero ideals, and so is a field. Note that

m maximal ⇒ m prime.

The ideals of A × B are all of the form a × b, with a and b ideals in A and B. To

see this, note that if c is an ideal in A×B and (a, b) ∈ c, then (a, 0) = (a, b)(1, 0) ∈ c

and (0, b) = (a, b)(0, 1) ∈ c. This shows that c = a × b with

a = {a | (a, b) ∈ c some b ∈ b}

and

b = {b | (a, b) ∈ c some a ∈ a}.

Proposition 0.1. The following conditions on a ring A are equivalent:

(a) every ideal in A is finitely generated;

(b) every ascending chain of ideals a1 ⊂ a2 ⊂ · · · becomes stationary, i.e., for some

m, am = am+1 = · · · .

(c) every nonempty set of ideals in A has maximal element, i.e., an element not

properly contained in any other ideal in the set.

Algebraic Geometry: 0. Algorithms for Polynomials 5

Proof. (a) ⇒ (b):I f a1 ⊂ a2 ⊂ · · · is an ascending chain, then ∪ai is again an

ideal, and hence has a finite set {a1, . . . , an} of generators. For some m, all the ai

belong am and then

am = am+1 = · · · = a.

(b) ⇒ (c):I f (c) is false, then there exists a nonempty set S of ideals with no

maximal element. Let a1 ∈ S; because a1 is not maximal in S, there exists an

ideal a2 in S that properly contains a1. Similarly, there exists an ideal a3 in S

properly containing a2, etc.. In this way, we can construct an ascending chain of

ideals a1 ⊂ a2 ⊂ a3 ⊂ · · · in S that never becomes stationary.

(c) ⇒ (a):L et a be an ideal, and let S be the set of ideals b ⊂ a that are finitely

generated. Let c = (a1, . . . , ar) be a maximal element of S. If c _= a, so that there

exists an element a ∈ a, a /∈ c, then c_ = (a1, . . . , ar, a) ⊂ a and properly contains c,

which contradicts the definition of c.

A ring A is Noetherian if it satisfies the conditions of the proposition. Note that,

in a Noetherian ring, every ideal is contained in a maximal ideal (apply (c) to the

set of all proper ideals of A containing the given ideal). In fact, this is true in any

ring, but the proof for non-Noetherian rings requires the axiom of choice (Atiyah and

MacDonald 1969, p3).

Algebras. Let A be a ring. An A-algebra is a ring B together with a homomorphism

iB : A → B. A homomorphism of A-algebras B → C is a homomorphism of rings

ϕ: B → C such that ϕ(iB(a)) = iC(a) for all a ∈ A.

An A-algebra B is said to be finitely generated (or of finite-type over A) if there

exist elements x1, . . . , xn ∈ B such that every element of B can be expressed as

a polynomial in the xi with coefficients in i(A), i.e., such that the homomorphism

A[X1, . . . ,Xn] → B sending Xi to xi is surjective.

A ring homomorphism A → B is finite, and B is a finite A-algebra, if B is finitely

generated as an A-module4.

Let k be a field, and let A be a k-algebra. If 1 _= 0 in A, then the map k → A is

injective, and we can identify k with its image, i.e., we can regard k as a subring of

A. If 1 = 0 in a ring R, the R is the zero ring, i.e., R = {0}.

Polynomial rings. Let k be a field. A monomial in X1, . . . ,Xn is an expression of

the form

Xa1

1

· · ·Xan

n , aj ∈ N.

The total degree of the monomial is

_

ai. We sometimes abbreviate it by Xα, α =

(a1, . . . , an) ∈ Nn.

The elements of the polynomial ring k[X1, . . . ,Xn] are finite sums

_

ca1···anXa1

1

· · ·Xan

n , ca1···an

∈ k, aj ∈ N.

with the obvious notions of equality, addition, and multiplication. Thus the monomials

from a basis for k[X1, . . . ,Xn] as a k-vector space.

4The term “module-finite” is used in this context only by the English-insensitive.

6 Algebraic Geometry: 0. Algorithms for Polynomials

The ring k[X1, . . . ,Xn] is an integral domain, and the only units in it are the

nonzero constant polynomials. A polynomial f(X1, . . . ,Xn) is irreducible if it is

nonconstant and has only the obvious factorizations, i.e., f = gh ⇒g or h is constant.

Theorem 0.2. The ring k[X1, . . . ,Xn] is a unique factorization domain, i.e., each

nonzero nonconstant polynomial f can be written as a finite product of irreducible

polynomials in exactly one way (up to constants and the order of the factors).

Proof. This is usually proved in basic graduate algebra courses. There is a detailed

proof in Herstein, Topics in Algebra, 1975, 3.11. It proceeds by induction on the

number of variables:i f R is a unique factorization domain, then so also is R[X].

Corollary 0.3. A nonzero principal ideal (f) in k[X1, . . . ,Xn] is prime if and

only f is irreducible.

Proof. Assume (f) is a prime ideal. Then f can’t be a unit (otherwise (f) is the

whole ring), and if f = gh then gh ∈ (f), which, because (f) is prime, implies that

g or h is in (f), i.e., that one is divisible by f, say g = fq. Now f = fq h implies

that q h = 1, and that h is a unit. Conversely, assume f is irreducible. If gh ∈ (f),

then f|gh, which implies that f|g or f|h (here we use that k[X1, . . . ,Xn] is a unique

factorization domain), i.e., that g or h ∈ (f).

The two main results of this section will be:

(a) (Hilbert basis theorem) Every ideal in k[X1, . . . ,Xn] has a finite set of generators

(in fact, of a special sort).

(b) There exists an algorithm for deciding whether a polynomial belongs to an ideal.

This remainder of this section is a summary of Cox et al.1992, pp 1–111, to which

I refer the reader for more details.

Division in k[X]. The division algorithm allows us to divide a nonzero polynomial

into another:l et f and g be polynomials in k[X] with g _= 0; then there exist unique

polynomials q, r ∈ k[X] such that f = qg + r with either r = 0 or degr < deg g.

Moreover, there is an algorithm for deciding whether f ∈ (g), namely, find r and

check whether it is zero.

In Maple,

quo(f, g, X); computes q

rem(f, g, X); computes r

Moreover, the Euclidean algorithm allows you to pass from a finite set of generators

for an ideal in k[X] to a single generator by successively replacing each pair of

generators with their greatest common divisor.

Orderings on monomials. Before we can describe an algorithm for dividing in

k[X1, . . . ,Xn], we shall need to choose a way of ordering monomials. Essentially this

amounts to defining an ordering on Nn. There are two main systems, the first of

which is preferred by humans, and the second by machines.

(Pure) lexicographic ordering (lex). Here monomials are orderd by lexicographic

(dictionary) order. More precisely, let α = (a1, . . . , an) and β = (b1, . . . , bn) be two

Algebraic Geometry: 0. Algorithms for Polynomials 7

elements of Nn; then

α > β and Xα >Xβ (lexicographic ordering)

if, in the vector difference α − β ∈ Z, the left-most nonzero entry is positive. For

example,

XY 2 > Y3Z4; X3Y 2Z4 > X3Y 2Z.

Note that this isn’t quite how the dictionary would order them:i t would put

XXXYYZZZZ after XXXYYZ.

Graded reverse lexicographic order (grevlex). Here monomials are ordered by total

degree, with ties broken by reverse lexicographic ordering. Thus, α > β if

_

_ ai >

bi, or

_

ai =

_

bi and in α − β the right-most nonzero entry is negative. For

example:

X4Y 4Z7 > X5Y 5Z4 (total degree greater)

XY 5Z2 > X4Y Z3, X5Y Z > X4Y Z2.

Orderings on k[X1, . . . ,Xn]. Fix an ordering on the monomials in k[X1, . . . ,Xn].

Then we can write an element f of k[X1, . . . ,Xn] in a canonical fashion, by re-ordering

its elements in decreasing order. For example, we would write

f = 4XY 2Z + 4Z2 − 5X3 + 7X2Z2

as

f = −5X3 + 7X2Z2 + 4XY 2Z + 4Z2 (lex)

or

f = 4XY 2Z + 7X2Z2 − 5X3 + 4Z2 (grevlex)

Let f =

_

aαXα ∈ k[X1, . . . ,Xn]. Write it in decreasing order:

f = aα0Xα0 + aα1Xα1 + · · ·, α0 > α1 > · · ·, aα0

_= 0.

Then we define:

(a) the multidegree of f to be multdeg(f) = α0;

(b) the leading coefficient of f to be LC(f) = aα0;

(c) the leading monomial of f to be LM(f) = Xα0;

(d) the leading term of f to be LT(f) = aα0Xα0 .

For example, for the polynomial f = 4XY 2Z + · · · , the multidegree is (1, 2, 1),

the leading coefficient is 4, the leading monomial is XY 2Z, and the leading term is

4XY 2Z.

The division algorithm in k[X1, . . . ,Xn]. Fix a monomial ordering in Nn. Suppose

given a polynomial f and an ordered set (g1, . . . , gs) of polynomials; the division

algorithm then constructs polynomials a1, . . . , as and r such that

f = a1g1 + · · · + asgs + r

where either r = 0 or no monomial in r is divisible by any of LT(g1), . . . , LT(gs).

8 Algebraic Geometry: 0. Algorithms for Polynomials

Step 1: If LT(g1)|LT(f), divide g1 into f to get

f = a1g1 + h, a1 =

LT(f)

LT(g1)

∈ k[X1, . . . ,Xn].

If LT(g1)|LT(h), repeat the process until

f = a1g1 + f1

(different a1) with LT(f1) not divisible by LT(g1). Now divide g2 into f1, and so on,

until

f = a1g1 + · · · + asgs + r1

with LT(r1) not divisible by any of LT(g1), . . . , LT(gs).

Step 2: Rewrite r1 = LT(r1) + r2, and repeat Step 1 with r2 for f:

f = a1g1 + · · · + asgs +LT(r1) + r3

(different ai’s).

Step 3: Rewrite r3 = LT(r3) + r4, and repeat Step 1 with r4 for f. f=a

f = a1g1 + · · · + asgs +LT(r1) + LT(r3) + r3

(different ai’s).

Continue until you achieve a remainder with the required property. In more detail,5

after dividing through once by g1, . . . , gs, you repeat the process until no leading term

of one of the gi’s divides the leading term of the remainder. Then you discard the

leading term of the remainder, and repeat . . . .

Example 0.4. (a) Consider

f = X2Y + XY 2 + Y 2, g1 = XY − 1, g2 = Y 2 − 1.

First, on dividing g1 into f, we obtain

X2Y + XY 2 + Y 2 = (X + Y )(XY − 1) + X + Y 2 + Y.

This completes the first step, because the leading term of Y 2 − 1 does not divide the

leading term of the remainder X + Y 2 + Y. We discard X, and write

Y 2 + Y = 1· (Y 2 − 1) + Y + 1.

Altogether

X2Y + XY 2 + Y 2 = (X + Y ) · (XY − 1) + 1 · (Y 2 − 1) + X + Y + 1.

(b) Consider the same polynomials, but with a different order for the divisors

f = X2Y + XY 2 + Y 2, g1 = Y 2 − 1, g2 = XY − 1.

In the first step,

X2Y + XY 2 + Y 2 = (X + 1) · (Y 2 − 1) + X · (XY − 1) + 2X + 1.

Thus, in this case, the remainder is 2X + 1.

5This differs from the algorithm in Cox et al. 1992, p63, which says to go back to g1 after every

successful division.

Algebraic Geometry: 0. Algorithms for Polynomials 9

Remark 0.5. (a) If r = 0, then f ∈ (g1, . . . , gs).

(b) Unfortunately, the remainder one obtains depends on the ordering of the gi’s.

For example, (lex ordering)

XY 2 − X = Y · (XY + 1)+0 · (Y 2 − 1) + −X − Y

but

XY 2 − X = X · (Y 2 − 1) + 0 · (XY − 1) + 0.

Thus, the division algorithm (as stated) will not provide a test for f lying in the ideal

generated by g1, . . . , gs.

Monomial ideals. In general, an ideal a will contain a polynomial without containing

the individual terms of the polynomial; for example, the ideal a = (Y 2 − X3)

contains Y 2 − X3 but not Y 2 or X3.

Definition 0.6. An ideal a is monomial if _

cαXα ∈ a ⇒ Xα ∈ a all α with cα _= 0.

Proposition 0.7. Let a be a monomial ideal, and let A = {α | Xα ∈ a}. Then A

satisfies the condition

α ∈ A, β ∈ Nn ⇒ α + β ∈ A. (*)

and a is the k-subspace of k[X1, . . . ,Xn] generated by the Xα, α ∈ A. Conversely, if

A is a subset of Nn satisfying (*), then the k-subspace a of k[X1, . . . ,Xn] generated

by {Xα | α ∈ A} is a monomial ideal.

Proof. It is clear from its definition that a monomial ideal a is the k-subspace

of k[X1, . . . ,Xn] generated by the set of monomials it contains. If Xα ∈ a and

Xβ ∈ k[X1, . . . ,Xn], then XαXβ = Xα+β ∈ a, and so A satisfies the condition (*).

Conversely,

_

_

α∈A

cαXα

__

_

β∈Nn

dβXβ

_

=

_

α,β

cαdβXα+β (finite sums),

and so if A satisfies (*), then the subspace generated by the monomials Xα, α ∈ A,

is an ideal.

The proposition gives a classification of the monomial ideals in k[X1, . . . ,Xn]:t hey

are in one-to-one correspondence with the subsets A of Nn satisfying (*). For example,

the monomial ideals in k[X] are exactly the ideals (Xn), n ≥ 1, and the zero ideal

(corresponding to the empty set A). We write

_Xα | α ∈ A_

for the ideal corresponding to A (subspace generated by the Xα, α ∈ A).

Lemma 0.8. Let S be a subset of Nn. Then the ideal a generated by {Xα | α ∈ S}

is the monomial ideal corresponding to

A

df

= {β ∈ Nn | β − α ∈ Nn, some α ∈ S}.

Thus, a monomial is in a if and only if it is divisible by one of the Xα, α ∈ S.

10 Algebraic Geometry: 0. Algorithms for Polynomials

Proof. Clearly A satisfies (*), and a ⊂ _Xβ | β ∈ A_. Conversely, if β ∈ A, then

β−α ∈ Nn for some α ∈ S, and Xβ = XαXβ−α ∈ a. The last statement follows from

the fact that Xα|Xβ ⇐⇒ β − α ∈ Nn.

Let A ⊂ N2 satisfy (*). From the geometry of A, it is clear that there is a finite

set of elements S = {α1, . . . , αs} of A such that

A = {β ∈ N2 | β − αi ∈ N2, some αi ∈ S}.

(The αi’s are the “corners” of A.) Moreover, a df = _Xα | α ∈ A_ is generated by the

monomials Xαi , αi ∈ S. This suggests the following result.

Theorem 0.9 (Dickson’s Lemma). Let a be the monomial ideal corresponding to

the subset A ⊂ Nn. Then a is generated by a finite subset of {Xα | α ∈ A}.

Proof. This is proved by induction on the number of variables — Cox et al. 1992,

p70.

Hilbert Basis Theorem.

Definition 0.10. For a nonzero ideal a in k[X1, . . . ,Xn], we let (LT(a)) be the

ideal generated by

{LT(f) | f ∈ a}.

Lemma 0.11. Let a be a nonzero ideal in k[X1, . . . ,Xn]; then (LT(a)) is a monomial

ideal, and it equals (LT(g1), . . . , LT(gn)) for some g1, . . . , gn ∈ a.

Proof. Since (LT(a)) can also be described as the ideal generated by the leading

monomials (rather than the leading terms) of elements of a, it follows from Lemma 0.8

that it is monomial. Now Dickson’s Lemma shows that it equals (LT(g1), . . . , LT(gs))

for some gi ∈ a.

Theorem 0.12 (Hilbert Basis Theorem). Every ideal a in k[X1, . . . ,Xn] is

finitely generated; more precisely, a = (g1, . . . , gs) where g1, . . . , gs are any elements

of a whose leading terms generate LT(a).

Proof. Let f ∈ a. On applying the division algorithm, we find

f = a1g1 + · · · + asgs + r, ai, r ∈ k[X1, . . . ,Xn],

where either r = 0 or no monomial occurring in it is divisible by any LT(gi). But

r = f − _

aigi ∈ a, and therefore LT(r) ∈ LT(a) = (LT(g1), . . . , LT(gs)), which,

according to Lemma 0.8, implies that every monomial occurring in r is divisible by

one in LT(gi). Thus r = 0, and g ∈ (g1, . . . , gs).

Standard (GrЁobner) bases. Fix a monomial ordering of k[X1, . . . ,Xn].

Definition 0.13. A finite subset S = {g1, . . . , gs} of an ideal a is a standard

(Grobner, Groebner, GrЁobner) basis for 6 a if

(LT(g1), . . . , LT(gs)) = LT(a).

6Standard bases were first introduced (under that name) by Hironaka in the mid-1960s, and

independently, but slightly later, by Buchberger in his Ph.D. thesis. Buchberger named them after

his thesis adviser GrЁobner.

Algebraic Geometry: 0. Algorithms for Polynomials 11

In other words, S is a standard basis if the leading term of every element of a is

divisible by at least one of the leading terms of the gi.

Theorem 0.14. Every ideal has a standard basis, and it generates the ideal; if

{g1, . . . , gs} is a standard basis for an ideal a, then f ∈ a ⇐⇒ the remainder on

division by the gi is 0.

Proof. Our proof of the Hilbert basis theorem shows that every ideal has a standard

basis, and that it generates the ideal. Let f ∈ a. The argument in the same

proof, that the remainder of f on division by g1, . . . , gs is 0, used only that {g1, . . . , gs}

is a standard basis for a..

Remark 0.15. The proposition shows that, for f ∈ a, the remainder of f on

division by {g1, . . . , gs} is independent of the order of the gi (in fact, it’s always

zero). This is not true if f /∈ a — see the example using Maple at the end of this

section.

Let a = (f1, . . . , fs). Typically, {f1, . . . , fs} will fail to be a standard basis because

in some expression

cXαfi − dXβfj, c,d∈

k, (**)

the leading terms will cancel, and we will get a new leading term not in the ideal

generated by the leading terms of the fi. For example,

X2 = X · (X2Y + X − 2Y 2) − Y · (X3 − 2XY )

is in the ideal generated by X2Y +X −2Y 2 and X3 −2XY but it is not in the ideal

generated by their leading terms.

There is an algorithm for transforming a set of generators for an ideal into a standard

basis, which, roughly speaking, makes adroit use of equations of the form (**)

to construct enough new elements to make a standard basis — see Cox et al. 1992,

pp80–87.

We now have an algorithm for deciding whether f ∈ (f1, . . . , fr). First transform

{f1, . . . , fr} into a standard basis {g1, . . . , gs}, and then divide f by g1, . . . , gs to

see whether the remainder is 0 (in which case f lies in the ideal) or nonzero (and it

doesn’t). This algorithm is implemented in Maple — see below.

A standard basis {g1, . . . , gs} is minimal if each gi has leading coefficient 1 and,

for all i, the leading term of gi does not belong to the ideal generated by the leading

terms of the remaining g’s. A standard basis {g1, . . . , gs} is reduced if each gi has

leading coefficient 1 and if, for all i, no monomial of gi lies in the ideal generated by

the leading terms of the remaining g’s. One can prove (Cox et al. 1992, p91) that

every nonzero ideal has a unique reduced standard basis.

Remark 0.16. Consider polynomials f, g1, . . . , gs ∈ k[X1, . . . ,Xn]. The algorithm

that replaces g1, . . . , gs with a standard basis works entirely within

k[X1, . . . ,Xn], i.e., it doesn’t require a field extension. Likewise, the division algorithm

doesn’t require a field extension. Because these operations give well-defined

answers, whether we carry them out in k[X1, . . . ,Xn] or in K[X1, . . . ,Xn], K ⊃ k,

we get the same answer. Maple appears to work in the subfield of C generated over

Q by all the constants occurring in the polynomials.

12 Algebraic Geometry: 0. Algorithms for Polynomials

As we said earlier, the reader is referred to Cox et al. 1992 pp1–111 for more details

on standard bases.

We conclude this section with the annotated transcript of a session in Maple applying

the above algorithm to show that

q = 3x3yz2 − xz2 + y3 + yz

doesn’t lie in the ideal

(x2 − 2xz + 5, xy2 + yz3, 3y2 − 8z3).

A Maple Session

> with(grobner);

[This loads the grobner package, and lists the available commands:

finduni, finite, gbasis, gsolve, leadmon, normalf, solvable, spoly

To discover the syntax of a command, a brief description of the command, and an

example, type “?command;”]

>G:=gbasis([x^2-2*x*z+5,x*y^2+y*z^3,3*y^2-8*z^3],[x,y,z]);

[This asks Maple to find the reduced Grobner basis for the ideal generated by the

three polynomials listed, with respect to the indeterminates listed (in that order). It

will automatically use grevlex order unless you add ,plex to the command.]

G : = [x2 − 2xz + 5,−3y2 + 8z3, 8xy2 + 3y3, 9y4 + 48zy3 + 320y2]

> q:=3*x^3*y*z^2 - x*z^2 + y^3 + y*z;

q : = 3x3yz2 − xz2 + y3 + zy

[This defines the polynomial q.]

> normalf(q,G,[x,y,z]);

9z2y3 − 15yz2x − 41

4 y3 + 60y2z − xz2 + zy

[Asks for the remainder when q is divided by the polynomials listed in G using

the indeterminates listed. This particular example is amusing—the program gives

different orderings for G, and different answers for the remainder, depending on which

computer I use. This is O.K., because, since q isn’t in the ideal, the remainder may

depend on the ordering of G.]

Notes:

1. To start Maple on a Unix computer type “maple”; to quit type “quit”.

2. Maple won’t do anything until you type “;” or “:” at the end of a line.

3. The student version of Maple is quite cheap, but unfortunately, it doesn’t have

the Grobner package.

4. For more information on Maple:

(a) There is a brief discussion of the Grobner package in Cox et al. 1992, especially

pp 487–489.

(b) The Maple V Library Reference Manual pp469–478 briefly describes what the

Grobner package does (exactly the same information is available on line, by

typing ?command).

(c) There are many books containing general introductions to Maple syntax.

13

5. Gr¨obner bases are also implemented in Macsyma, Mathematica, and Axiom,

but for serious work it is better to use one of the programs especially designed for

Gr¨obner basis computation, namely, CoCoA (Computations in Commutative Algebra)

or Macaulay (available at: ftp math.harvard.edu, login ftp, password any,

cd Macaulay; better, point your web browser to ftp.math.harvard.edu).

14

Навигация