A Division Algorithm in K[x1,x2,...,xn]

 

We all know the following proposition:
Proposition 1 (The Division Algorithm). Let K be a field and let g be a nonzero polynomial in K[x]. Then every f in K[x] can be written as

f = q g + r,

where q and r are in K[x], and either r = 0 or deg(r)<deg(g). Furthermore q and r are unique and they can be found by the following algorithm:

Input: f, g
Output: q, r
q := 0; r := f
WHILE (r<>0 AND LT(g) divides LT(r)) DO

q := q + LT(r)/LT(g)
r := r - (LT(r)/LT(g))g

where LT stands for "leading term", i.e. the term with the highest degree (see also the definition of LT in K[x1,x2,...,xn]).
We will formulate a division algorithm for polynomials in K[x1,x2,...,xn] which extends the algorithm in K[x], but first let us give some definitions.
Definition 2. Fix a monomial order >. Let F = {f1,f2,...,fs} be a finite set of polynomials in K[x1,x2,...,xn]. A polynomial g is reduced with respect to F (or modulo F) if no LM(fi) (1<=i<=s) divides LM(g).
If g is not reduced w.r.t. F, we can subtract from it a multiple of an element of F to eliminate its leading monomial and to get a new polynomial h whose leading monomial is less than the leading monomial of g. This process is called a reduction of g with respect to F and is denoted as g -->F h.
Note that a polynomial g can have several reduction with respect to F (one for each elements in F which leading monomial divides the leading monomial of g). For example, let F = {f1 = x-1, f2 = y-1} and g = xy. Then there are two possible reductions of g w.r.t. F: h1 = g - yf1 = y and h2 = g - xf2 = x.

The definition of polynomial reduction involves only the leading monomial of g. But it is possible to eliminate some other monomials in g. For example, consider g = x + y2 + y and F = {f1 = y - 1} with lex order and x>y. Then g is reduced w.r.t. F since its leading monomial x is not divisible by LM(f1) = y. Nevertheless we can eliminate the monomials y2 and y w.r.t. F. This leads to the following definition.
Definition 3. Fix a monomial order >. Let F = {f1,f2,...,fs} be a finite set of polynomials in K[x1,x2,...,xn]. A polynomial g is completely reduced with respect to F (or modulo F) if no monomial of g is divisible by any of the LM(fi) for all 1<=i<=s.
Examples.
  1. Consider g = x + y+ z2 and F = {xy - 1, xz + y} with lex order and x>y>z. Then g is completely reduced w.r.t. F.
  2. Consider g = x + y2 + y and F = {f1 = y - 1} with lex order and x>y. Then we can eliminate y2 this way: g - yf1 = x + 2y. x + 2y is not completely reduced modulo F; we can continue the reduction process to eliminate also the term 2y: x + 2y - 2f1 = x + 2, which is now completely reduced.

A polynomial g cannot have an infinite chain of reductions: we must end up with a completely reduced polynomial which is called the Normal Form of g. To denote that a polynomial h is a normal form of g with respect to F, we write g -->*F h or h = NormalForm(g, F).

  1. In the previous example, x + 2 is the (we have only one polynomial in F) normal form of the polynomial g modulo F.
  2. Consider g = 2y2z - xz2 and F = {f1 = 7y2 + yz -4, f2 = 2yz -3x - 1} with grlex order and x>y>z. Then we have
    g -->f1 g - (2/7z)f1 = -xz2 - 2/7yz2 + 8/7z,
    -xz2 - 2/7yz2 + 8/7z -->f2 -xz2 - 2/7yz2 + 8/7z - (-1/7z)f2 = -xz2 - 3/7xz - z, which is completely reduced modulo F.
    Thus, g -->*F -xz2 - 3/7xz - z, which tell us that -xz2 - 3/7xz - z is a normal form of g w.r.t. F. Another normal form of g w.r.t. F can be found by first reducing by f2 instead of f1:
    g -->f2 g - (y)f2 = -xz2 + 3xy + y, which is completely reduced modulo F, hence -xz2 + 3xy + y is a normal form of g modulo F.

The process of reduction may be viewed as one step in a generalized division, which states as follows:
Proposition 4 (Division Algorithm in K[x1,x2,...,xn]). Fix a monomial order > on Nn. Let F = (f1,f2,...,fs) be an ordered s-tuple of polynomials in K[x1,x2,...,xn]. Then every f of K[x1,x2,...,xn] can be written as

f = a1f 1 + a2f 2 + ... + asfs + r,

where ai and r are in K[x1,x2,...,xn], and either r = 0 or r is completely reduced with respect to F. We will call r the remainder of f on division by F. Furthermore if aifi <> 0 then multideg(f) >= multideg(aifi).
The existence of a1,a2 ,...,as and r is proved by the following constructive algorithm.

Generalized Division Algorithm.

Input: f1,f2,...,fs, f
Output: a1,a2,...,as, r
ai := 0 1<=i<=s; r := 0; p := f
WHILE (p<>0) DO

i := 1
dividing := true
 WHILE ((i<=s) AND (dividing)) DO

IF LT(fi) divides LT(p) THEN

ai := ai + LT(p)/LT(fi)
p := p - (LT(p)/LT(fi))fi
dividing := false

ELSE

i := i+1

IF (dividing) THEN

r := r + LT(p)
p := p - LT(p)

Clearly the algorithm is a generalized form of the high school division algorithm. The variable p represents the intermediate dividend at each stage. As long as the leading term of a divisor divides the leading term of p, the algorithm proceeds as in the one-variable case. Otherwise, we remove the leading term of p and add it to the remainder.

Example.

  1. f = x2y + xy2 + y2, F = (f1 = xy - 1,f2 = y2 - 1), with lex order and x>y.
    ai := 0 for 1<=i<=2; r := 0; p := f
    a1 := x
    p := x2y + xy2 + y2 - x(xy - 1)= xy2 + x + y2
    a1 := a1 + y = x + y
    p := p - y(xy - 1)= x + y2 + y

Neither LT(f1) = xy nor LT(f2) = y2 divides LT(p) = x. However x + y2 + y is not completely reduced since LT(f2) divides y2. Thus we move LT(p) = x to the remainder and continue dividing:

r := x
p := p - x = y2 + y
a2 := 1
p := p - (y2 - 1) = y + 1
r : = r + y = x + y
p := p - y = 1
r := r + 1 = x + y + 1
p := p - 1 = 0

Thus the remainder is x + y + 1 and we obtain

x2y + xy2 + y2 = (x + y)(xy - 1) + 1(y2 - 1) + x + y + 1.

Note that the generalized division algorithm does not have several of the same nice properties as the one variable case:

  • the remainder is not uniquely characterized by the requirement that if it is nonzero then it is completely reduced w.r.t. F. The remainder r is a normal form of f with respect to F.
  • the ai's are not unique and they change if the fi's are rearranged (see what happens if we divide f of the previous example by F = (f2 = y2 - 1, f1 = xy - 1)).
    However, if we follow the algorithm precisely as stated, testing LT(p) for divisibility by LT(f1), LT(f2), ... in that order, then the ai's and r are uniquely determined.
  • it does not solve the ideal membership problem (at least not completely).
    In fact, if on dividing f by F = (f1,f2,...,fs) we get r = 0, then f = a1f 1 + a2f2 + ... + asfs, hence f is in <f 1,f2,...,f s>. Thus r = 0 is a sufficient condition for ideal membership. However it is not a necessary condition as shown by the following example:

Example.

Let f1 = xy + 1, f2 = y2 - 1 be two polynomials in K[x,y] with lex order and x>y. Dividing xy2 - x by F = (f1, f2) we get

xy2 - x = y(xy + 1) + 0(y2 - 1) + (-x - y),

whereas with F = (f 2, f1) we have

xy2 - x = x(y2 - 1) + 0(xy + 1) + 0 .

The second result shows that xy2 - x is in <f1, f2> . The first calculation shows that even if xy2 - x is in <f1, f 2> it is possible to have a nonzero remainder on dividing by F = (f 1, f2).

We can ask whether there might be a "good" basis {g1,g2,...,gt} of the ideal <f1,f2,...,fs>, for which the remainder r on the division by the generators gi is uniquely determined and the condition r = 0 is equivalent to membership in the ideal. Fortunately the answer is yes: a Groebner basis does have this good properties.

In terms of normal forms, the previous example tells us that we could get a nonzero normal form of g w.r.t. F as a result of the division algorithm, while g -->*F 0. This is due to the particular relative order of the fi. We will see that it is very important to know a priori when a polynomial g has a zero normal form modulo some polynomial set F (i.e. g -->*F 0) without carrying out all the possible reductions.

 

Last updated 09/14/2009 08:07:06