Agoston M.K. Computer Graphics and Geometric Modelling: Mathematics

Подождите немного. Документ загружается.

10.10 Gröbner Bases 729

ically, it is known (Theorem B.8.7) that, given polynomials f(X) and g(X), there are

unique polynomials a(X) and r(X) with deg r < deg g, so that

(10.56)

More to the point, there is a simple algorithm for ﬁnding a(X) and r(X). Algorithm

10.10.1 is one variant of this one-variable division algorithm. We show it here to help

motivate the generalization to the multivariable case that we shall describe shortly.

As simple as it is, this division algorithm has many applications. For example, it is

used in the Euclidean algorithm that computes the greatest common divisor of a ﬁnite

set of polynomials. (This algorithm proceeds just like the one for computing the great-

est common divisor of a ﬁnite set of integers. Structurally, the polynomial ring k[X]

looks very much like the integers Z, and many of the constructions that one can use

for Z carry over to k[X].) Algorithm 10.10.1 also leads to simple algorithms that

answer questions (1) and (2), because it is the key ingredient to proving that k[X] is

a PID (Theorem B.8.11), that is, every ideal I Õ k[X] has the form I = <g(X)> for some

g Œ k[X]. This obviously shows that every ideal I has a ﬁnite basis. A polynomial f Œ

k[X] belongs to I if and only if the remainder r(X) in equation (10.56) is zero.

When we try to answer questions (1) and (2) in the multivariable case, the ﬁrst

problem we encounter is that the ring k[X

,...,X

] is not a PID if n > 1. There-

fore, we shall want to reduce a polynomial by long division with respect to a set of k

> 1 polynomials (corresponding to the basis of an ideal), not just one. In k[X], this

task reduces to the case k = 1 because of the PID property. On the other hand, with

polynomials of more than one variable it is in general possible to perform long divi-

sion reductions in different ways which lead to different remainders. Without unique

remainders we would lose some good algorithms. Fortunately, we can get uniqueness

if we choose the basis carefully (and deﬁne a good division algorithm). This is where

Gröbner bases come in. The fact that some bases are better than others is hardly new.

For example, in the case of vector spaces, orthonormal bases are often particularly

desirable.

fX aXgX rX

()

()()

()

Inputs:

f(X), g(X)

k[X] , g(X)

Outputs:

a(X), r(X)

k[X] satisfying f(X) = a(X) g(X)

r(X) with either

r(X) = 0 or deg r < deg g

a := 0; r := f;

while

and

(lt(g) divides lt(r))

{ lt(p) returns the leading term of p }

begin

a := a + lt(r)/lt(g);

r := r - (lt(r)/lt(g)) g;

end

;

Algorithm 10.10.1. The one-variable polynomial division algorithm.

730 10 Algebraic Geometry

Next, consider questions (3) and (4). To see the possible role of polynomial divi-

sion and bases in answers to those questions, we look at the special case of linear

equations and parameterizations. The standard solution to the problem in question

(3) when we have linear equations is to turn it into a matrix problem and apply the

Gauss-Jordan elimination method and standard row reductions. This approach can

be thought of as a method for ﬁnding certain bases.

10.10.1. Example. Consider two linear equations

(10.57)

Applying the standard row reduction method to the matrix which represents the

system of equations (10.57) leads to the row echelon form of that matrix:

It follows that solving (10.57) is equivalent to solving

(10.58)

Equations (10.58) are easily solved for X and Y in terms of Z and turned into a para-

metric solution of the form

A similar approach works for question (4) in the linear case.

10.10.2. Example. Consider the parameterization

(10.59)

which we rewrite as

(10.60)

Again, the matrix associated to the system in (10.60) can brought into standard form

using row reductions:

tt x

12 1

12 2

210

350

+- -=

-- +=

--=.

xt t

xtt

11 2

212

=+ -

=-+

=-,

20.

121

234

121

012

105

012

fXYZ X Y Z

gXYZ X Y Z

,, .

()

=- +=

()

=-+=

2340

10.10 Gröbner Bases 731

The last row leads to the equation

which is an implicit representation of the plane deﬁned parametrically by equations

(10.59).

Let us see how we can interpret what we did in these examples in polynomial

terms. For example, in Example 10.10.1 the row reductions in the matrices corre-

spond to showing that

where g

= g - 2f and f

= f + 2g

. Replacing g by g

will be called a reduction. It corre-

sponds to eliminating the X term in g. How this is done is via a long division of g by f:

If there are more equations, then more divisions may be needed and by more than

one polynomial. In analyzing what is going on here, there are two points to observe

as we prepare to generalize this process:

(1) We ordered the terms of the linear polynomials – we decided to eliminate X

ﬁrst in Example 10.10.1 and we listed the x

after the t

in Example 10.10.2.

(2) We subtract multiples of a polynomial to eliminate the current “leading” terms

from remaining polynomials.

In the nonlinear case for arbitrary polynomials in k[X

,...,X

] we shall try to

use similar steps, but things get more complicated. We address question (1) ﬁrst. If an

ideal I is generated by polynomials g

, g

,..., g

, then to determine whether or not the

polynomial f belongs to I reduces to ﬁnding polynomials a

, a

,..., a

, so that

(10.61)

Finding such polynomials a

or showing that they do not exist is not as easy as in the

linear case, especially, since we cannot assume anything about their degree even if we

fag ag ag

=+++

11 22

... .

)

XYZXYZ

XYZ

-+ -+

2234

242

Vfg Vfg Vf g,, ,,

()

111

xxx

123

50--+=,

11 10 0 7

210 101

03 0 0 1 5

100

010 0

001

---

732 10 Algebraic Geometry

know something about the degrees of f and the g

. For example, if the g

all have degree

2 and f has degree 4, we cannot assume that the a

will have degree at most 2. Nev-

ertheless, the approach will be to try to reduce f to 0 by successively subtracting appro-

priate multiples of g

from f, then multiples of g

, etc. We will need some criteria that

will tell us that as we change f we are making progress. To do this we deﬁne a notion

for when a term of a polynomial is more complicated than another one. We need an

ordering of monomials. One such well-known ordering is the following:

Deﬁnition. The lexicographic order or lex order < of the monomials in indeterminates

, X

,..., X

over a ring R is deﬁned as follows: Given monomials

then u < v if the left-most nonzero entry in the vector d = (f

,...,f

) - (e

,...,e

)

in Z

is positive. The reverse lexicographic order deﬁnes u < v if the right-most nonzero

entry in the vector d is negative.

For example, if X = X

and Y = X

, then

with respect to the lexicographic order. Note that the lexicographic order is deter-

mined by the order in which the indeterminates X

are listed. In essence, one has

chosen a ﬁxed ordering of the variables, namely, X

< X

n-1

< ...< X

The lexicographic order is only one of many orderings. Other orderings actually

work better with certain problems. Here are two other standard ones; however, the

reader should be aware of the fact that the terminology varies between authors.

Deﬁnition. The degree lexicographic order or deglex order < of the monomials in inde-

terminates X

, X

,..., X

over a ring R is deﬁned by saying that any monomial of

total degree d is less than any monomial of degree e if d < e and monomials of equal

total degree are ordered using the lexicographic order.

For example, if X = X

and Y = X

, then

Deﬁnition. The degree reverse lexicographic order or degrevlex order < of the mono-

mials in indeterminates X

, X

,..., X

over a ring R is deﬁned by saying that any

monomial of total degree d is less than any monomial of degree e if d < e and mono-

mials of equal total degree are ordered using the reverse lexicographic order.

In the case of two variables, the degrevlex and deglex order are the same

(Exercise 10.10.2). On the other hand, when X

< X

then

for deglex order, but

XX XXX

<<< < <<YXY XY X ....

2222

<< < < < << < << < <YY Y

XXYXY X XY... ... ... ...

u cX X X and v dX X X

12 12

... ...

10.10 Gröbner Bases 733

for degrevlex order.

We would like to isolate the essential properties that an ordering should possess

to be useful. Since ordering monomials

will ignore the constant c and will be equivalent to ordering their exponent tuples

in N

, the deﬁnition of an ordering often deals simply with orderings of elements of

rather than monomials. We shall state both deﬁnitions for comparison purposes

but concentrate on N

Deﬁnition. A monomial ordering of N

is a total ordering < on N

that satisﬁes

(1) 0 £ e for all e Œ N

, and

(2) if whenever e, f Œ N

and e < f, then e+g < f+g for all g Œ N

Deﬁnition. A monomial ordering of k[X

,...,X

] is a total ordering < on the

monomials of k[X

,...,X

] satisfying

(1) c < X

for all c Œ k and all i.

(2) For all monomials u, v, w Œ k[X

,...,X

], u < v implies that uw < vw.

10.10.3. Theorem. Every monomial ordering of N

is a well-ordering.

Proof. Let < be monomial ordering. We need to show that every subset of N

has a

smallest element, or, equivalently, that every decreasing sequence

(10.62)

must terminate after a ﬁnite number of steps. The theorem will be proved by induc-

tion on n.

If n = 1, then it is easy to show that < is just the standard less than relation on the

nonnegative integers. Assume that n ≥ 2 and that the theorem is true for n - 1. Suppose

that we have a decreasing sequence of elements e

as shown in (10.62).

Claim 1. The theorem is true if there is a j so that all the jth entries in the e

are

constant.

Without loss of generality we may assume that j = n. Suppose that e

= c for all

i. Because

ff f c gg g c

ff f gg g

il i in il i in

, ,..., , , ,..., ,

, ,..., , , ,..., , ,

21 2 1

()

if and only if

... ... , ..., ,

<<<<< =

()

ee eee N

ii iii in

ee e

12112

e =

()

ee e

n12

, ,...,

cX x X

...

XXX XX

23 1

734 10 Algebraic Geometry

we may also assume that c = 0. Deﬁne an ordering < of N

n-1

by:

(10.63)

It is easy to check that this deﬁnes a monomial ordering on N

n-1

. Our inductive

hypothesis applied to the sequence e

¢=(e

,...,e

in-1

) in now proves Claim 1.

Claim 2. If x = (x

,..., x

), y = (y

,..., y

) Œ N

n-1

satisﬁes x

< y

for all j,

then x < y.

Let d

= y

- x

and d = (d

,...,d

). Then 0 < d implies that x = 0 + x < d + x =

y and Claim 2 is proved.

Now consider the sequence in (10.62) again and assume that it is an inﬁnite

sequence. If any of the sequences of nonnegative integers e

, j = 1,2,..., is bounded

for some ﬁxed i, then we can choose a subsequence of the e

so that the jth entries in

that subsequence are constant. By Claim 1 we would be done. Assume therefore that

the sequences e

, j = 1,2,..., are unbounded for all i. Choose a subsequence of the e

so that for that subsequence the ﬁrst components form a strictly increasing sequence

of integers going to inﬁnity. Let f

be this new decreasing sequence of elements of N

Now look at the second components of all the f

and choose a subsequence so that

the second components form a strictly increasing sequence of integers going to inﬁn-

ity. Continue in this way until we ﬁnally end up with a subsequence g

= (g

...,g

) of the original sequence e

with the property that g

i+1,j

> g

for all i and j. By

Claim 2 we would have g

i+1

> g

, which is impossible since the sequence e

was decreas-

ing. This contradiction proves the theorem.

Theorem 10.10.3 is important because we need monomial orderings to have the

well-ordering property in addition to the total order to ensure that various algorithms

we shall deﬁne will terminate.

10.10.4. Proposition. The lex, deglex, and degrevlex orders of k[X

,...,X

] are

monomial orderings.

Proof. Obvious.

We need some more terminology before we can state the multivariable long divi-

sion theorem.

Deﬁnition. Fix a monomial order < on k[X

,...,X

] and let f Œ k[X

,...,X

The largest monomial in f with respect to this order is called the leading term of f and

is denoted by lt(f). Its coefﬁcient is called the leading coefﬁcient and is denoted by lc(f).

The leading power product, denoted by lpp(f), is deﬁned by the equation lt(f) =

lc(f)lpp(f) and is the largest power product appearing in f.

For example, assuming deglex order and Y < X, if

fXY XY XY Y,,

()

=+-7

ff f gg g

il i in il i in

, ,..., , ,...,

, ,..., , , ,..., , .

21 2 1

()

if and only if

10.10 Gröbner Bases 735

then

In the future, whenever we talk about leading terms, etc., we shall always assume

a monomial order has been chosen even if we do not say so explicitly.

10.10.5. Theorem. (The Division Algorithm for k[X

,...,X

]) Fix a monomial

order < on k[X

,...,X

] and let P = {p

,...,p

} be a ﬁxed set of m nonzero

polynomials in k[X

,...,X

]. Then every f Œ k[X

,...,X

] can be expressed

where a

, r Œ k[X

,...,X

] , and either r is zero or none of the monomials appear-

ing in r is divisible by any of the lt(p

). The polynomial r will be called a remainder of

f by division with respect the sequence of polynomials P. Furthermore,

Proof. Algorithm 10.10.2 is an algorithm that ﬁnds the a

and r. Therefore, the proof

of the division theorem boils down to showing that that algorithm does what it claims.

The reader should compare this algorithm with Algorithm 10.10.1 for one variable.

Two key observations for a proof of Algorithm 10.10.2 are:

(1) f = a

+ a

+ ···+ a

+ g + r at each stage.

(2) The leading term of g in (1) decreases with respect to the ordering so that the

algorithm terminates.

See [CoLO97] or [AdaL94].

See Exercise 10.10.4 for a simple variant of a multivariable division algorithm.

Deﬁnition. Let f and g be two polynomials. We say that f is simpler than g if lt(f)

< lt(g).

For example, if

then f is simpler than g. Algorithm 10.10.2 shows how to simplify polynomials with

respect to any set of polynomials. We introduce some other common terminology.

Deﬁnition. Fix a monomial order. Let P be a set of polynomials and f an arbitrary

polynomial. Assume that some monomial term u of f is divisible by the leading term

of a polynomial p in P, that is,

f XY X and g X Y Y=+ =+

23 3 3

lpp f lpp a lpp p lpp a lpp p lpp a lpp p lp r

()

() () () () ( ) ( ) ()

{}

max , ,..., , .

11 2 2

fap ap ap r

=+++ +

11 22

... ,

lt f X Y lc f and lpp f X Y

()

=77

,, .

736 10 Algebraic Geometry

for some monomial h. Let g = f - hp. We shall say that the polynomial g is obtained

from f via an elementary P-reduction and write f ﬁ g. If no such polynomial p exists,

then we shall say that f is P-irreducible. If there exists a sequence of elementary P-

reductions f = f

ﬁ f

ﬁ ...ﬁ f

= g, then we say that f P-reduces to g and

write . If f P-reduces to g and g is P-irreducible, we shall call g a P-normal

form for f and denote such g by NF(f,P).

æÆæ

u h lt p=

()

Inputs:

f, p

, p

k[X

] , p

Outputs:

, a

, r

k[X

] satisfying

f = a

+º+

where either r is zero or none of the monomials appearing in r is divisible

by any of the lt(p

)

integer

boolean

noDivision;

:= a

:= r := 0; g := f;

while g π 0 do

begin

i := 1; noDivision := true;

while

and

noDivision

then

begin

:= a

lt(g)/lt(p

);

g := g

(lt(g)/lt(p

))

;

noDivision :=

false

;

end

else

i := i

noDivision

then

begin

r := r

lt(g);

g := g

lt(g);

end

;

if lt(pi) divides lt(g)

Algorithm 10.10.2. The multivariable polynomial division algorithm.

10.10 Gröbner Bases 737

The term “P-normal form” for a polynomial is not quite just another name for a

remainder in Algorithm 10.10.2. The reason is that an elementary reduction of f does not

require that the term u in f is a leading term. In practical algorithms, however, u always

will be chosen to be a leading term because of Algorithm 10.10.2.

10.10.6. Example. Choose the lexicographic order for k[X,Y] with X > Y and let

and

The ﬁrst term of each of the polynomials p

is the leading term. Deﬁne polynomials

and h

This shows that

Thus, f P-reduces to g

and h

. Since both g

and h

are P-irreducible, they are both

P-normal forms for f.

Note that Example 10.10.6 shows that P-normal forms (or remainders in

Algorithm 10.10.2) are not unique in general. Now, an elementary P-reduction intro-

duces potentially new terms to the original polynomial. It might seem initially that

we could have an inﬁnite chain of elementary P-reductions. This is not possible

however. See [AdaL94]. (The termination part of the proof for Algorithm 10.10.2 does

not apply directly because elementary P-reductions of f do not necessarily pick a

leading term of f. One needs a simple modiﬁcation of that proof.)

10.10.7. Proposition. Let P be a ﬁnite set of polynomials and f an arbitrary poly-

nomial. If the P-normal form g for f is unique, then g = 0 if and only if f belongs to

the ideal <P>.

Proof. Let P = {p

,...,p

}. Now, if , then

for some polynomials a

. Therefore, if g = 0 then f Œ<P>. Conversely, let f Œ<P>. It is

not true in general that every P-normal form of f is 0. See Exercise 10.10.6. On the

other hand, at least one will be because if

fap ap ap g

=+++ +

11 22

...

æÆæ

f g g g g and f h h hﬁﬁﬁﬁ ﬁﬁﬁ

1234 123

h f Xp XY XY

hhp XYX

hh XYp X

22 2

212

32 3

12 9

=- =- +

=+= -

=- =-

g f Xp X Y X XY

g g p X XY X

g g XY p X X

ggp

22 2 2

212

32 3

434

449

=- =- - +

=+ =- + -

=- =- -

=+=

fXYXYXY=-+12 9

322 2

P p XY X p XY X p Y p X X== + = - = =+

{}

34,,,

738 10 Algebraic Geometry

for some polynomials a

(each of which is a sum of monomials), then f is sum of

products b

, where b

is a monomial and q

Œ P, and this provides a sequence of

elementary P-reductions that lead to 0. It follows that if the P-normal form is unique,

then all P-normal forms will be 0.

Proposition 10.10.7 motivates us to ﬁnd bases P for ideals so that they induce unique

P-normal forms on polynomials. Such bases will be called Gröbner bases. There are

many possible equivalent deﬁnitions for these. We choose one based on leading term

properties rather than the unique P-normal form property because it is the former that

play the central role in all the proofs and practical algorithms.

Deﬁnition. Fix a monomial order and let I be a nonzero ideal in k[X

,...,X

A ﬁnite set P = {p

,...,p

} of nonzero polynomials in I is called a Gröbner basis or

standard basis for I if and only if for all nonzero f Œ I, there is some j, 1 £ j £ n, so

that lt(p

) divides lt(f).

Note that if we have a Gröbner basis P for an ideal I, then no nonzero polynomial

in I is P-irreducible.

Deﬁnition. Let S be an arbitrary nonempty subset of k[X

,...,X

]. Deﬁne the set

of leading terms of S, lt(S), by

10.10.8. Theorem. Fix a monomial order and let I be a nonzero ideal in

k[X

,...,X

]. The following statements are equivalent for a ﬁnite set P = (p

...,p

) of nonzero polynomials in I:

(1) P is a Gröbner basis for I.

(2) f Œ I if and only if .

(3) f Œ I if and only if

for some polynomials a

(4) <lt(P)>=<lt(I)>.

(5) Every polynomial f Œ k[X

,...,X

] has a unique P-normal form.

Proof. We shall only prove that (1)–(4) are equivalent. For a proof showing that (5)

is equivalent to (2) see [AdaL94].

(1) ﬁ (2): Let f Œ I. Let r = NF(f,P). Clearly, r Œ I. But r must be 0, otherwise one

would be able to reduce it further by the deﬁnition of a Gröbner basis. The converse

is also immediate.

f a p and lpp f lpp a lpp p

()

() ()

{}

££

max ,

æÆæ 0

1t S lt f f S

()

{}

fap ap ap

=+++

11 2 2

...