| We have found out from
the previous pages that the system of polynomial
equations f1(x1,x2,...,xn) = f2(x1,x2,...,xn) =
... = fs(x1,x2,...,xn) =
0 is equivalent to g1(x1,x2,...,xn) = g2(x1,x2,...,xn) =
... = gt(x1,x2,...,xn) =
0 where {g1,g2,...,gt}is a Groebner basis for <f1,f2,...,fs>. This becomes useful
when the Groebner basis is computed w.r.t. the lex order
which ensures the elimination of the variables (see The
Elimination Theorem in [3]).
Moreover, the order of elimination corresponds to the
ordering of the variables: if x1>x2>...>xn, then x1 is
eliminated first, then x2
is eliminated second, and so on. Anyway, if we want to
eliminate only some variables from our equations, a much
more efficient way is to use a monomial order of k-elimination type since lex
order may lead to some very unpleasant Groebner bases. Example[3].
Let us consider the system
f1 = x2
+ y + z - 1 = 0
f2 = x
+ y2 + z - 1 = 0
f3 = x
+ y + z2 - 1 =
0.
Then, a Groebner basis for I = <f1,f2,f3> w.r.t. lex order with x>y>z is given by
g1 = x
+ y + z2 - 1
g2 = y2
- y - z2 + z
g3 =
2yz2 + z4
- z2
g4 = z6
- 4z4
+ 4z3 - z2.
Hence the systems f1
= f2
= f3
= 0 and g1 = g2 = g3 = g4 = 0 have the same
solutions. But, in the second one, g4 = z6
- 4z4
+ 4z3 - z2
= z2(z - 1)2(z2
+ 2z -1) = 0involves only z
and it is easy to solve: we get 0, 1, -1-sqrt(2), -1+sqrt(2)as the possible z's.
Substituting these values into g2 = y2
- y - z2 + z = 0 and g3 =
2yz2 + z4
- z2 = 0, we get the
possible y's
and, finally, g1 = x
+ y + z2 - 1 = 0gives the
corresponding x's. So the system f1 = f2 = f3 = 0 has exactly five
solutions:
(1,0,0), (0,1,0),
(0,0,1), (-1-sqrt(2),-1-sqrt(2),-1-sqrt(2)), (-1+sqrt(2),-1+sqrt(2),-1+sqrt(2)).
Note that changing the order of the variables will
also change the order of their elimination. If we had
used lex order with z>y>x
we would have eliminated z
first, instead of x.
In this example we have seen that each possible value
of z could
be extended to a complete solution of the system. This is
not always possible, as shown by the following example.
Example[3].
Consider the system
f1 = xy
- 1 = 0
f2 = xz
- 1 = 0.
A Groebner basis for I =
<f1,f2> w.r.t. lex order is
given by
g1 = xy
- 1
g2 = y
- z.
Hence, from g2 = y
- z = 0 we get the partial
solutions (a, a) which all extends
to complete solutions (1/a,
a, a) except for the
partial solution (0, 0).
The Extension Theorem tells us when a partial solution
can be extended to a complete solution in an
algebraically closed field. Before stating it, we
must premit the following definition.
|
Definition 1.
Given I = <f1,f2,...,fs> in K[x1,x2,...,xn],
the kth elimination
ideal Ik
is the ideal of K[xk+1,...,xn]
defined by
Ik
= I I
K[xk+1,...,xn].
|
Thus, Ik
consists of all consequences of f1 = ... =
fs
= 0 which eliminates the
variables x1,...,xk.
In the first example above we have I1
= <g2, g3, g4> and I2
= <g4>, whereas in the latest
example I1
= <g2>. |
| Theorem 2 (The Extension Theorem)[3]. Let I = <f1,f2,...,fs> be an ideal in C[x1,x2,...,xn]
and let I1
be the first elimination ideal of I. Rearrange the
terms of the generators fi
with respect to the decreasing powers of x1.
If the leading coefficients hi(x2,...,xn) (with respect to
this new order) do not vanish simultaneously at the
partial solution (a2,...,an), then there exists a1 in C
such that the partial solution (a2,...,an) extends to the
complete solution (a1,a2,...,an). |
Example[3].
- In C[x,y,z], consider
the system
f1
= x2 -
y = 0
f2
= x2 -
z = 0.
A Groebner basis for I = <f1,f2> w.r.t. lex order is
given by
g1
= x2 -
y
g2
= x2 -
z
g3
= y - z.
All partial solutions y = z = a do extend in C
to complete solutions since 1 never
vanishes at y = z = a.
Note that over R, only the partial
solutions with a
>= 0 extend.
Although the Extension Theorem is stated only for the
case of eliminating the first variable x1, it can be
used multiple times to eliminate any number of variables;
this follows from the fact that Ik+1 C K[xk+2,...,xn] is the first
elimination ideal of Ik C K[xk+1,...,xn].
Example[3].
In C[x,y,z], consider the
system
f1 = x2
+ y2 + z2
- 1 = 0
f2 = xyz
- 1 = 0.
A Groebner basis for I =
<f1,f2> w.r.t. lex order is
given by
g1 = y4z2
+ y2z4
- y2z2
+ 1
g2 = x
+ y3z + yz3
- yz.
We have
I1
= I
I C[y,z]
= <g1>
I2
= I
I C[z]
= I1I C[z] = {0}.
Every z = c in C is a
partial solution, but which partial solutions c extend to (a,b,c) in V(I)? We use the
Extension Theorem one coordinate at a time. We first
go from I2
to I1:
since the coefficient of y4
in g1
is z2, c extends to
(b,c) whenever c<>0. Now (b,c) can be extended to
(a,b,c) because in f1 the
coefficient of x2 is
1
which never vanishes.
Thus the Extension Theorem tells us that all partial
solutions c<>0 extend to V(I) in C.
We will find an interesting application of the
Extension Theorem when we talk about the implicitization problem.
Now we will conclude this section with two results about
how to detect unsolvable systems and systems with
finitely many solutions. Buchberger [2] proved the following two
facts.
|
| Theorem 3 (Unsolvable systems).
Let I = <f1,f2,...,fs> be an ideal in C[x1,x2,...,xn].
Then the system of polynomial equations f1(x1,x2,...,xn) = f2(x1,x2,...,xn) =
... = fs(x1,x2,...,xn) =
0is unsolvable if and only if
the reduced
Groebner basis of I
is {1}. |
| We must be careful when we work on R[x1,x2,...,xn]:
a system might be unsolvable even though the groebner
basis of the ideal is other than {1} (consider the equation
x2
+ 1 = 0!). However, if {1}is the reduced Groebner
basis of our ideal, we are sure that the system cannot be
solved. Example[1].
Consider the system
f1 = x2y
- z3 = 0
f2 = 2xy
- 4z - 1 = 0
f3 = y2
- z = 0
f4 = x3
- 4yz = 0.
The reduced Groebner basis for I = <f1,f2,f3,f4> w.r.t. lex order is {1}, hence the system is unsolvable.
|
| Theorem 4 (Systems with finitely
many solutions). Let I
= <f1,f2,...,fs> be an ideal in C[x1,x2,...,xn].
Then the system of polynomial equations f1(x1,x2,...,xn) = f2(x1,x2,...,xn) =
... = fs(x1,x2,...,xn) =
0 has finitely many solutions
if and only if for all i
(1<=i<=s)
there exists a power of xi
which belongs to <LT(I)>. |
| For an example of a polynomial
system with finitely many solutions see the first example in this page. You will see
that x, y2
and z6 are in <LT(I)>. |