B Mishra.

Notes on Grobner bases online

. (page 1 of 3)
Online LibraryB MishraNotes on Grobner bases → online text (page 1 of 3)
Font size
QR-code for this ebook


Robotics Research
Ifechnical Report







Notes on Grobner Bases
by

B. Mishra

C. K. Yap

Technical Report No. 257

Robotics Report No. 87

November, 1986




\



o «*
^



New York University
nstitute of Mathematical Sciences

Computer Science Division

. j> 1 Mercer Street New York, NX 1 00 1 2



pjKnrfPT-^




.f*> -



//




Notes on Grobner Bases
by

B. Mishra

C. K. Yap

Technical Report No. 257

Robotics Report No. 87

November, 1986



New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012



Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-
0381, National Science Foundation CER Grant DCR-83-20085, and by grants from the Digi-
tal Equipment Corporation and the IBM Corporation.



CONTENTS 1

Contents

1 Introduction 2

2 Basic Terminology 3

3 Normal Form Algorithm 6

4 Bounds on Normal Form Algorithms 9

5 Characterizations of Grobner Basis 12

6 The Basic Algorithm of Buchberger 20

7 Uniqueness of Reduced Grobner Bases 22

8 Applications 26

8.1 Ideal Theoretic Problems 26

8.2 Residue Class Ring Modulo an Ideal 28

8.3 Solving Systems of Polynomial Equations 30



r



1 INTRODUCTION



Abstract
We present a self-contained expKieition of the theory of Grobner
basis and its applications.



1 Introduction

These notes attempt to present in a self-contained manner the basic facts
about the theory of Grobner basis and related algorithms. Except for an
excellent survey on the subject by Buchberger [Buchberger 1985] the liter-
ature on the subject is somewhat scattered. Since our interest is in com-
plexity of algorithms, we attempt to give quantitative forms of theorems
whenever possible. Of course, much of this material is ultimately owed to
B. Buchberger even if not explicitly mentioned.

A Grobner basis is a special basis for a multivariate polynomial ideal
over a field with certain attractive computational properties. It turns out
that many important computational problems involving ideals can be eaisily
solved once we have a Grobner basis for the ideals. Such bases were first
defined by Hironaka in 1964 who called them standard bases. Buchberger
independently defined the concept in his PhD thesis in 1965, naming it in
honor of his teacher, W. Grobner. Hironaka only proved the existence of
such bases; Buchberger gave an aJgorithm (the 'basic algorithm' in section
3) to construct them.

More generally, this area falls under that of computational algebraic ge-
ometry. Hilbert is often cited as launching the niainstream modern math-
ematical trend which favors non-constructive results. In particular Hilbert
solved the outstanding problem in the theory of invariants via his cele-
brated Basis Theorem: that every polynomial ideal has a finite bjisis. In a
sense, he invented his solution of Basis Theorem because his solution was
not in the spirit of what the geometers of his day (Gordon wzis the princi-
pal representative) were trying to do. The geometers were trying to give
constructive or algorithmic solutions. Hilbert tiirned it into an existence
question, although he Weis later able to return to the original problem to
give a satisfactory construction. As for the trend towards non-constructive
abstractions, the subject of algebraic geometry itself is the best illustration
of the phenomenon (see the historical survey of the whole subject till present



2 BASIC TERMINOLOGY 3

day in [Dieudonn^ 1985]). Meanwhile, the constructive spirit in algebraic
geometry has survived, though not thrived. A key paper in this regards is
that of Hermann [Hermann 1926]. Another more modem attempt to re-
turn to the classical questions is Seidenberg [Seidenberg 1974]. Since then a
number of papers have begun to revitalize this area, and among the reasons
for this is the promise of practical computational algebra systems.

We would like to noake two remarks here: a prominent algebraic geome-
ter advocating the constructive viewpoint is Abhyankar (see his delightful
historical expos6 in [Abhyankar 1976]). As computer scientists, we take
Professor Abhyankar's viewpoint to the extreme': we regard the existence
of a construction only as a first step towards a precise clzissification of the
inherent computational complexity of a computational algebraic problem.
Studies motivated by this extreme requirement might be termed algorith-
mic algebraic geometry. It is our belief that this standpoint can transform
a large area of classical algebraic geometry to a new level of beauty and
understanding. Already this algorithmic standpoint has revived the study
of elementary Euclidean geometry. The other remark is this: the study of
algorithmic algebraic geometry Implies quantitative algebraic geometry in
which a variety of bounds are sought. To illustrate this p>oint, Hilbert's
baisis theorem tells us that all ascending chains of polynomial ideals are
finite. We seek to bound the length of such chains. (It appears that we
cannot bound the length as a fimction of the initial ideal alone). Or again,
Hillbert's Nullstellensatz says that if / vanishes at all the zeroes of am ideal
/ C ik[ii, . . . , i„] where k is algebraically closed then f^ £ I for some d. In
fact it had been noted that d depends only on /, not on /. We again ask
for good bounds on d as a function of the size of /.



2 Basic Terminology

Let us fix a polynomial ring R = K[xi, . . . , x„], n > 1, and K is any field.
Given elements a,b e Rv/e say that a divides b, equivalently fc is a multiple
of a, if 6 = ac for some c E R. If Oi, . . . , a„ are elements in R and F C R



^Alternatively, as computer scientists, we have more precise notions of constructiveness
and a rich vocabulary to make finer distinctions.



2 BASIC TERMINOLOGY 4

then the ideals generated by {ai, . . . ,o„} and F (respectively) are denoted
by (ai,...,a„) and {F).

A power product is an element of R of the form

p = i^'i'j'-i'„", c.>0.

Sometimes power products are also called terms. The total degree of p is
deg[p) = 52"^ 1 c,. The degree of p in any variable i, is (feff,_(p) = c^. The
/eas< common multiple (LCM) of two power products p = xj'xj' " " " ^n" and
9 = xf'i^ - -i^ isgivenbyxr*^'''"^ - -ir^t'^''"^ A monomto/ is a term
of the form ap where a ^ K and p is a power product. The length of a
polynomial is the number of monomials that occurs in it. The LCM of two
monomials am and a'm', where a,a' e K and m,m' are power products, is
defined as follows:

LCM{am,am') = aa' • LCM{m,m').

We remark that if K is an Euclidean domain then it is better to define the
LCM as LCM{a,a') ■ LCM{m,m').

Let PP = PP(ii,. .. ,i„) be the set of all power products involving
Zi, . . . , z„. A total ordering < on the set of power products is said to be

A

admissible if for all power products p, q, (i) 1 < p for all p € PP and (ii)

(Va e PP) p < 9 =^ ap g
if f ^ g and g< f. Let / e J? be a polynomial. The head monomial

A

Hmono(/) of / is the monomial in / whose power product is largest relative
to h — > h, and we write NFg(/) for the
set of all G-normal forms of /. It is important to realize that the G-normal
form of / is not unique in general, and the central idea in Grobner basis is
to enlarge G so that it becomes unique. Finally, we are ready for the main
definition: A finite set G C i? is seiid to be a Grobner basis (for the ideal
generated by G) if the G-normal form of every polynomial / is unique, i.e.,
|NFa(/)| = l.

Remark: Computationally, it may be more efficient (asymptotically)
to use the reflexive transitive closure of — >. If =$• denotes this closure,



3 NORMAL FORM ALGORITHM 6

then f ^ h implies that no monomial in /i is a multiple of Hmono(3).

Exercise. Prove that h is imiquely determined by / and g.

It turns out that the concept of a Grobner basis is intimately related

to that of the S- polynomial S{f,g) of two polynomials f,g £ R. This is

defined by

m "^



Hmono(/) Hmono(^)

where m = LCM(Hmono(/),Hmono(y)). For example, assuming a total
degree ordering,

5(2i'y + zy + y' - 3,5y' - y + i) = 5y(iy + y^ - 3) - 2i'(-y + i).

Example: Admissible orderings can be quite complex. The following
example is due to T. Dube: it shows an ordering on PP(x,y,2) with the
property that the restriction of the ordering to PP(x,y) is a total degree
ordering with y > x, x> z* and y > z* for all i and yet xz > y. The rule is

A A A A

this. Suppose m = x'y^'z' and m' = z" y*' and z**. Then m> m' iff one of

the following sequence of tests yields an affirmative answer when applied
in the indicated order: (1) a + b> a' + b', (2) c > c\ (3) a < a!. One should
check that this is an admissible ordering and has the claimed properties.



3 Normal Form Algorithm

Henceforth we fix some admissible ordering < on monomials. For any finite

A

set F C R, we define a "non-deterministic" aJgorithm which for any input
polynomial /, computes an element in NFf (/). The algorithm is trivial:
apply any reduction — >, y E F, to transform the input polynomizil /. Now
as long as the (transformed input) polynomial is not in NF/'(/), repeat the
reduction. We write nfj?(/) for the polynomial produced by this aJgorithm.
All reductions in this section are relative to a fixed but arbitrary set F.

Before proving the termination of this algorithm we prove Dixon's lemma
[Dixon 1913] and two general results on well-ordering.

Lemma 1 [Dixon] Every stt X C PP of monomials contains a finite subset
F C X such that each m ^ X is a multiple of some monomial in F.



3 NORMAL FORM ALGORITHM 7

Proof. We use induction on the number n of variables. If n = 1 then we let
F consist of the unique polynomial in X of minimum degree. So we may
assume n > 1. Pick any /o € X and say



Then every m G A" that is not divisible by /o belongs to one of J2i=i c»
different sets: let t = l,...,n and v = 0, 1, . . . ,Cj — 1. Then the set X,_„
consists of those monomials m G X such that degi_(m) = v. Let X,'„ denote
the set of monomials obtained by omitting the factor x^ from monomials
in X, „. By inductive hypothesis, there exists finite subsets /"/^ C X,'„ such
that each monomiaJ in X,'„ is a multiple of some monomial in F/^. We
obtain Fj „ as {m ■ x" : m G F/^}. It is then clear that every monomial in
X is a multiple of some monomial in the finite set

{/o}uUn-
Q.E.D.
Lemma 2 Every admissible ordering < on PP is a well-ordering.

A

Proof. This is an easy consequence of the Dixon's lemma. Suppose we have
an infinite descending sequence of monomials

mi > mj > • • • > m, > • • • .

A A A A

Let X = {'Tii,»7i2, . . . ,m,, . . .} and let F C X be a finite subset such that
every m G X is a multiple of some monomial in F. Let m' be the mono-
mial that is smallest in F imder the ordering ' • ■ • is an infinite
descending chain in S{X). Lee a, = (2^1,1,2, ... ,2:, ,„(,)). There are two
cases.

(i) The n(t)'s are bounded, say k = majc{n(t) : t = 1,2, - -}. We use
induction on k. We get an immediate contradiction for k = 1, so assume
k > 1. li there are infinitely many t's such that n(i) = 1 then we get a
contradiction from the subsequence consisting of such a,'s. Hence we may
assume that the n(t)'8 are all greater than 1. Now there is an to such
that for all t > to» ^i,i = ^i+i,i- Let a,' = (2:i,j,i,,s5 • • • >a^i,n(i)) he obtained
from -* g) is 2^^"*"^^". Since all the
gi are distinct, the desired boimd in the lemma follows. Q.E.D.

We next give a better bound under the assumption that the normal
form algorithm always chooses to eliminate the • • •> rrik.

AAA

In the sequence (l), assume m, is eliminated by application of /, G F. Thus

9i - 9i-i - OLtfi

for some monomial a,.

Lemma 6 Under the total ordering, the length of an ordered reduction se-
quence is at most {D + l)".

The proof is immediate. However we note that there may be members
of NFj?(a;n-i > •••>Xi.

A A A

We define a weighting function Wp : PP — > N (N is the set of natural
niimbers) as follows:

V^'^(xl' •••i;-) = ci((f + 1)° + ej(d+ 1)^ + •■• + e„((f + 1)"-'

If / is any polynomial, we extend the weight function to let Wf{f) denote
the weight function applied to the heaA term in /. Note: Unlike the case



4 BOUNDS ON NORMAL FORM ALGORITHMS 11

of total ordering, oiir bounds for lexicographical ordering will depend on
the set F. This is reflected in the appearance of the subscript F in the
weighting function Wp (and also Wp to be introduced below).

Lemma 7 Let f ^ F and let m be any monomial. Write f as a sum of
monomials, f = /i + /z + • • • + A where /i > /: > • • • > A- Then for any
monomial m, we have that WF{mfj-i) > Wp{mfj) for j = 2, . . . , fc..

Proof. Let /y_i = xf ' • • • ij|" and /, = xV ■ ■ ■ x'n- Then /y_i > fj iff there
is some t = l,...,n such that d„ = c„,(f„_i = e„_i, . . . ,rf,+ i = e.+i and
di > e,. We get

l^f(m/;_i)-VVf(m/y) = Wp{f,_,)-Wp{f,)

(c,_, - 1. Since there are at most
£ — 1 new monomials in g, the increase in the weight of g over / due to
their presence is at most (£ - i)t^''i"^^). Hence

Wjr{f) - WF[g) > l^"^"^^) -{t- i)£W('^^)

_ fWr{mhi) _ fl + Wr(mh3) _^_ fW(mh2)

By the previous lemma, Wplmhi) > Wf (m/ij). Hence Wplf] - Wpig) >
fWimh,) > 0. Q.E.D.

We immediately conclude:

Theorem 9 Assuming the lexicographical ordering, the length of any se-
quence of reductions beginning from an input polynomial g is at most

where L is the length of g, I is the maximum length of a polynomial in F
and D is the maximum degree of g in any variable.

In a subsequent paper [Dub^, Mishra and Yap 1986], we will extend the
preceding analysis of normaJ form algorithms to arbitrary admissible order-
ings.

5 Characterizations of Grobner Basis

Recall that a finite set G C fi is a Grobner basis (for the ideal / = (G)) if
the G-normal form of every polynomial is unique. We now increase under-
standing of this definition by giving several alternative characterizations.

We first note two general results on partial ordering relations. Let X
be any set and — > be a binary relation on X and — ► be its reflexive
transitive closure. Let g,g',h G X. We call h a common successor of g and
g' if g — *h and g' — *h. We say the relation — > is Church-Rosser if for
all elements /, 5, ^ G X we have:



5 CHARACTERIZATIONS OF GROBNER BASIS 13

/ — ► g and / — > y* implies that g and g' have a common suc-
cessor.

The relation — ► is locall]/ Church-Rosstr if for all elements f,g,g' € AT we
have:

/ — ► g and / — ► g* implies that g and g' have a conunon suc-
cessor.

(Note: "confluent" is an alternative terminology for "Church-Rosser".)
The relation — > is Notthtrian if there is no infinite sequence of the form
/i — »^ /j — ► • • •. Note that if — * is Noetherian then / — * f must not hold
for any / G AT. An element / 6 X such that / — ► g implies that f — g
is said to be in normal form. Thus normal form elements are "minimal"
elements (assuming the reduct of an element is smaller than the original).
We say ff is a normal form of / if / — ► g\ the set of all normal forms of /
is denoted NF(/).

Following are two general results about Noetherian relations. The first
proof uses a very powerful principle called the Principle of Noetherian In-
duction:

For a Noetherian relation — y, to establish the validity of a
predicate P{x) for all x 6 X, it is sufficient to show: if P{y)
holds for all y such that x — > y and x j^ y then P{x) holds.

Let us demonstrate the validity of this principle. Suppose that it is shown
that P{x) holds whenever P{y) holds for all y 7^ i where x — »y. For the
sake of contradiction, suppose P(io) fails. Then for some Xi ^ xo, Xo — ^ Xi
and P{xi) fails. Continuing in this fashion, we obtain an infinite descending
sequence xq, xi, Xj, . . . , which contradicts the Noetherian property.

Lemma 10 Let — > be a Noetherian relation. Then it is Church-Rosser if
and only if it is locally Church-Rosser.

Proof. One direction is immediate. In the other direction, assume that
the relation is locally Church-Rosser. Let / — ► g and / — ► h. \{ f — g
OT f = h then the result is irmnediate. Otherwise, let / — > g' — > g and



5 CHARACTERIZATIONS OF GROBNER BASIS 14

/ — > h' — ► h. Since the relation is locally Church-Rosser, g' and h' have a
comnion successor /'. By the principle of Noetherian induction (as applied
to &')' 9 ^^^ f have a common successor g"; similarly, h and /' have a
common successor h". By a third application of the principle to /', we
get that g" and h" have a common successor /". Clearly /" is a common
successor of § and h. Q.E.D.

Exercise. Reprove this lemma avoiding the Principle of Noetherian
induction.

Lemma 11 Let — > be a Noetherian relation on X. Then — > is Church-
Rosser if and only if every element / G AT has a unique normal form.,

|NF(/)| = 1.

Proof. (=>) By our assumption that the relation is Noetherian, NF(/) is
non-empty for any /. li g,g' G NF(/), then the Church-Rosser property
implies that g and g' have a common successor h. But g is in normal fonn


1 3

Online LibraryB MishraNotes on Grobner bases → online text (page 1 of 3)