Groebner Bases for Polynomial Systems: A Brief Introduction K.O. Geddes Symbolic Computation Group D.R. Cheriton School of Computer Science University of Waterloo Waterloo ON N2L 3G1 CANADA http://www.uwaterloo.ca/~kogeddes

The concept of Groebner bases is introduced using some motivating examples. Two types of applications are considered: (1) canonical forms for polynomials with side relations; and (2) solutions of systems of polynomial equations.

Suppose that we wish to simplify an expression which contains various powers of the symbol NiMlImlH , under the assumption that NiMlImlH represents the complex number NiMtJSVzcXJ0RzYjLCQiIiIhIiI= . For example, restart; e := 4*i^5 - 7*i^4 + i^3 + 3*i^2 - 5*i + 11;

LC4qJiIiJSIiIilJImlHNiIiIiZGJUYlKiYiIihGJSlGJ0YkRiUhIiIqJClGJyIiJEYlRiUqJkYwRiUpRiciIiNGJUYlKiZGKUYlRidGJUYtIiM2RiU=

As a naive approach, we could think of applying transformation rules such as: i^2 --> -1 i^3 --> -i i^4 --> 1 i^5 --> i etc. For the above example, the expression simplifies as follows. subs({i^2=-1, i^3=-i, i^4=1, i^5=i}, e);

LCYqJiIiIyIiIkkiaUc2IkYlISIiRiVGJQ==

An algorithmic approach to the problem is as follows. We wish to simplify the expression NiMlImVH with respect to the following side relation which the variable NiMlImlH must satisfy: NiMvLCYqJCklImlHIiIjIiIiRilGKUYpIiIh . The given expression lies in a polynomial domain NiMlIkRH[NiMlImlH] over some coefficient domain NiMlIkRH but we really want to represent the expression in a canonical form as an element of the quotient ring LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JVEiREYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2JS1GIzYjLUYsNiVRImlGJ0YvRjIvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRictSSNtb0dGJDYwUSIvRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZLLyUpc3RyZXRjaHlHRjEvJSpzeW1tZXRyaWNHRksvJShsYXJnZW9wR0ZLLyUubW92YWJsZWxpbWl0c0dGSy8lJ2FjY2VudEdGSy8lJWZvcm1HUSZpbmZpeEYnLyUnbHNwYWNlR1EudGhpbm1hdGhzcGFjZUYnLyUncnNwYWNlR0Znbi8lKG1pbnNpemVHUSIxRicvJShtYXhzaXplR1EpaW5maW5pdHlGJy1GRDYwUSI8RidGR0ZJRkwvRk9GS0ZQRlJGVEZWRlgvRmZuUS90aGlja21hdGhzcGFjZUYnL0ZpbkZlb0ZqbkZdby1JJW1zdXBHRiQ2JUY6LUkjbW5HRiQ2JFEiMkYnRkcvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnLUZENjBRJyZwbHVzO0YnRkdGSUZMRmNvRlBGUkZURlZGWC9GZm5RMG1lZGl1bW1hdGhzcGFjZUYnL0ZpbkZlcEZqbkZdby1GW3A2JEZcb0ZHLUZENjBRIj5GJ0ZHRklGTEZjb0ZQRlJGVEZWRlhGZG9GZm9Gam5GXW8=-- i.e. as a polynomial modulo the ideal generated by NiMsJiokKSUiaUciIiMiIiJGKEYoRig= . Question: Is it possible to specify a canoncial form for elements of the quotient ring LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiotRiw2JVEiREYnRi9GMi1JKG1mZW5jZWRHRiQ2JS1GIzYjLUYsNiVRImlGJ0YvRjIvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRictSSNtb0dGJDYwUSIvRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZQLyUpc3RyZXRjaHlHRjEvJSpzeW1tZXRyaWNHRlAvJShsYXJnZW9wR0ZQLyUubW92YWJsZWxpbWl0c0dGUC8lJ2FjY2VudEdGUC8lJWZvcm1HUSZpbmZpeEYnLyUnbHNwYWNlR1EudGhpbm1hdGhzcGFjZUYnLyUncnNwYWNlR0Zcby8lKG1pbnNpemVHUSIxRicvJShtYXhzaXplR1EpaW5maW5pdHlGJy1GSTYwUSI8RidGTEZORlEvRlRGUEZVRldGWUZlbkZnbi9GW29RL3RoaWNrbWF0aHNwYWNlRicvRl5vRmpvRl9vRmJvLUklbXN1cEdGJDYlRj8tSSNtbkdGJDYkUSIyRidGTC8lMXN1cGVyc2NyaXB0c2hpZnRHUSIwRictRkk2MFEnJnBsdXM7RidGTEZORlFGaG9GVUZXRllGZW5GZ24vRltvUTBtZWRpdW1tYXRoc3BhY2VGJy9GXm9GanBGX29GYm8tRmBwNiRGYW9GTC1GSTYwUSI+RidGTEZORlFGaG9GVUZXRllGZW5GZ25GaW9GW3BGX29GYm9GKw==? Yes it is possible. Any element of the quotient ring can be represented uniquely in terms of the basis NiM8JCIiIiUiaUc= -- i.e. as a polynomial of degree 1 in the variable NiMlImlH .

For the quotient ring discussed above, transformation to canonical form can be obtained by applying Euclidean division with remainder: NiMlImVH --> LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtRiw2JVEkcmVtRidGL0YyLUkjbW9HRiQ2MFEwJkFwcGx5RnVuY3Rpb247RicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZCLyUpc3RyZXRjaHlHRkIvJSpzeW1tZXRyaWNHRkIvJShsYXJnZW9wR0ZCLyUubW92YWJsZWxpbWl0c0dGQi8lJ2FjY2VudEdGQi8lJWZvcm1HUSZpbmZpeEYnLyUnbHNwYWNlR1EkMGVtRicvJSdyc3BhY2VHRlQvJShtaW5zaXplR1EiMUYnLyUobWF4c2l6ZUdRKWluZmluaXR5RictSShtZmVuY2VkR0YkNiMtRiM2KS1GLDYlUSJlRidGL0YyLUY7NjBRIixGJ0Y+RkAvRkRGMUZFRkdGSUZLRk1GT0ZSL0ZWUTN2ZXJ5dGhpY2ttYXRoc3BhY2VGJ0ZXRlotRjs2MFExJkludmlzaWJsZVRpbWVzO0YnRj5GQEZDRkVGR0ZJRktGTS9GUEYuRlJGVUZXRlotRiM2JkYrLUYjNiVGKy1JJW1zdXBHRiQ2JS1GLDYlUSJpRidGL0YyLUkjbW5HRiQ2JFEiMkYnRj4vJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnRistRjs2MFEiK0YnRj5GQEZDRkVGR0ZJRktGTUZPL0ZTUTBtZWRpdW1tYXRoc3BhY2VGJy9GVkZecUZXRlotRmRwNiRGWUY+Rl9vRmVvRmBwRis= .

e;

LC4qJiIiJSIiIilJImlHNiIiIiZGJUYlKiYiIihGJSlGJ0YkRiUhIiIqJClGJyIiJEYlRiUqJkYwRiUpRiciIiNGJUYlKiZGKUYlRidGJUYtIiM2RiU=

rem(e, i^2+1, i);

LCYqJiIiIyIiIkkiaUc2IkYlISIiRiVGJQ==

Of course, Maple will automatically simplify expressions involving NiMtJSVzcXJ0RzYjLCQiIiIhIiI= which has the alias NiMlIklH in Maple. subs(i=I, e);

LCYiIiJGIyomIiIjRiNeI0YjRiMhIiI=

The above discussion applies to any univariate side relation. As a second example, consider an expression in the symbol NiMlInJH which represents NiMtJSVzcXJ0RzYjIiIj . In this case, the side relation satisfied by the symbol NiMlInJH is: NiMvLCYqJCklInJHIiIjIiIiRilGKCEiIiIiIQ== . f := r^6 - 5/7*r^5 + 23*r^4 + 1/2*r^3 - 35/11*r^2 + r - 1/2;

LDAqJClJInJHNiIiIiciIiJGKComIyIiJiIiKEYoKUYlRitGKCEiIiomIiNCRigpRiUiIiVGKEYoKiYjRigiIiNGKClGJSIiJEYoRigqJiMiI04iIzZGKClGJUY1RihGLkYlRihGNEYu

rem(f, r^2-2, r);

LCYjIiVcPyIjQSIiIiomIyIiJyIiKEYmSSJyRzYiRiYhIiI=

Again, Maple will automatically simplify expressions involving NiMtJSVzcXJ0RzYjIiIj . subs(r=sqrt(2), f);

LCYjIiVcPyIjQSIiIiomIyIiJyIiKEYmKSIiIyNGJkYsRiYhIiI=

Suppose, for example, that we have a trigonometric expression involving NiMtJSRzaW5HNiMlInhH and NiMtJSRjb3NHNiMlInhH and we wish to simplify the expression with respect to the following side relation: NiMvLCYqJCktJSRzaW5HNiMlInhHIiIjIiIiRiwqJCktJSRjb3NHRilGK0YsRixGLA== . We can choose to think of this as a polynomial side relation NiMvLCYqJCklInNHIiIjIiIiRikqJCklImNHRihGKUYpRik= and to represent NiMtJSRzaW5HNiMlInhH and NiMtJSRjb3NHNiMlInhH in the expression by the symbols NiMlInNH and NiMlImNH, respectively. We are then faced with the problem of simplifying a multivariate polynomial with respect to a multivariate side relation. Expressing this in the notation of algebra, the original expression lies in a bivariate polynomial domain NiMlIkRH[NiQlInNHJSJ0Rw==] and we wish to express it (in a canonical form, if possible) as an element of the quotient ring LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYsLUkjbWlHRiQ2JVEiREYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2JS1GIzYlLUYsNiVRInNGJ0YvRjItSSNtb0dGJDYwUSIsRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0YxLyUpc3RyZXRjaHlHRkUvJSpzeW1tZXRyaWNHRkUvJShsYXJnZW9wR0ZFLyUubW92YWJsZWxpbWl0c0dGRS8lJ2FjY2VudEdGRS8lJWZvcm1HUSZpbmZpeEYnLyUnbHNwYWNlR1EkMGVtRicvJSdyc3BhY2VHUTN2ZXJ5dGhpY2ttYXRoc3BhY2VGJy8lKG1pbnNpemVHUSIxRicvJShtYXhzaXplR1EpaW5maW5pdHlGJy1GLDYlUSJ0RidGL0YyLyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnLUY+NjBRIi9GJ0ZBRkMvRkdGRS9GSUYxRkpGTEZORlBGUi9GVlEudGhpbm1hdGhzcGFjZUYnL0ZZRmpvRmVuRmhuLUY+NjBRIjxGJ0ZBRkNGZ29GSEZKRkxGTkZQRlIvRlZRL3RoaWNrbWF0aHNwYWNlRicvRllGYHBGZW5GaG4tSSVtc3VwR0YkNiVGOi1JI21uR0YkNiRRIjJGJ0ZBLyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJy1GPjYwUScmcGx1cztGJ0ZBRkNGZ29GSEZKRkxGTkZQRlIvRlZRMG1lZGl1bW1hdGhzcGFjZUYnL0ZZRmBxRmVuRmhuLUZjcDYlLUYsNiVRImNGJ0YvRjJGZXBGaXAtRj42MFEoJm1pbnVzO0YnRkFGQ0Znb0ZIRkpGTEZORlBGUkZfcEZhcEZlbkZobi1GZnA2JEZnbkZBLUY+NjBRIj5GJ0ZBRkNGZ29GSEZKRkxGTkZQRlJGX3BGYXBGZW5GaG4=. Question: Is it possible to specify a canoncial form for elements of the quotient ring LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYsLUkjbWlHRiQ2JVEiREYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2JS1GIzYlLUYsNiVRInNGJ0YvRjItSSNtb0dGJDYwUSIsRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0YxLyUpc3RyZXRjaHlHRkUvJSpzeW1tZXRyaWNHRkUvJShsYXJnZW9wR0ZFLyUubW92YWJsZWxpbWl0c0dGRS8lJ2FjY2VudEdGRS8lJWZvcm1HUSZpbmZpeEYnLyUnbHNwYWNlR1EkMGVtRicvJSdyc3BhY2VHUTN2ZXJ5dGhpY2ttYXRoc3BhY2VGJy8lKG1pbnNpemVHUSIxRicvJShtYXhzaXplR1EpaW5maW5pdHlGJy1GLDYlUSJ0RidGL0YyLyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnLUY+NjBRIi9GJ0ZBRkMvRkdGRS9GSUYxRkpGTEZORlBGUi9GVlEudGhpbm1hdGhzcGFjZUYnL0ZZRmpvRmVuRmhuLUY+NjBRIjxGJ0ZBRkNGZ29GSEZKRkxGTkZQRlIvRlZRL3RoaWNrbWF0aHNwYWNlRicvRllGYHBGZW5GaG4tSSVtc3VwR0YkNiVGOi1JI21uR0YkNiRRIjJGJ0ZBLyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJy1GPjYwUScmcGx1cztGJ0ZBRkNGZ29GSEZKRkxGTkZQRlIvRlZRMG1lZGl1bW1hdGhzcGFjZUYnL0ZZRmBxRmVuRmhuLUZjcDYlLUYsNiVRImNGJ0YvRjJGZXBGaXAtRj42MFEoJm1pbnVzO0YnRkFGQ0Znb0ZIRkpGTEZORlBGUkZfcEZhcEZlbkZobi1GZnA2JEZnbkZBLUY+NjBRIj5GJ0ZBRkNGZ29GSEZKRkxGTkZQRlJGX3BGYXBGZW5GaG4=? The answer is not obvious. For example, the following expressions are mathematically equivalent: e1 := sin(x)^2 * cos(x)^2;

KiYpLUkkc2luRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiNJInhHRikiIiMiIiIpLUkkY29zR0YmRipGLEYt

e2 := expand( subs(cos(x)^2 = 1-sin(x)^2, e1) );

LCYqJCktSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIkYuKiQpRiUiIiVGLiEiIg==

e3 := expand( subs(sin(x)^2 = 1-cos(x)^2, e1) );

LCYqJCktSSRjb3NHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIkYuKiQpRiUiIiVGLiEiIg==

Which form is "best"? "simplest"? It depends on your point of view. The more general Question is: Given a multivariate polynomial domain NiMlIkRH[NiUmJSJ4RzYjIiIiJSQuLi5HJkYkNiMlInZH] and one or more side relations NiMvLSYlInJHNiMlImpHNiUmJSJ4RzYjIiIiJSQuLi5HJkYrNiMlInZHIiIh (NiUvJSJqRyIiIiIiIyUkLi4uRw== ), is it possible to specify a canonical form for elements of the quotient ring NiMlIkRH[NiUmJSJ4RzYjIiIiJSQuLi5HJkYkNiMlInZH] / NiMlI0lkRw== where NiMlI0lkRw== is the ideal generated by the polynomials NiMtJiUickc2IyUiakc2JSYlInhHNiMiIiIlJC4uLkcmRio2IyUidkc= ? Until the 1960s it was not known whether this question could be answered in the affirmative. It turns out that the answer is Yes, via the theory of Groebner bases.

Before proceeding further, consider a Maple example. For the simplification of expressions modulo side relations in Maple, see the help page ?simplify[siderels] . The syntax of the command is NiMtJSlzaW1wbGlmeUc2JCUlZXhwckclKXNpZGVyZWxzRw== where NiMlKXNpZGVyZWxzRw== is a set of one or more side relations. When the simplify command is invoked in this form, Maple applies the theory of Groebner bases. Specifically, a Groebner basis for NiMlKXNpZGVyZWxzRw== is computed and then NiMlJWV4cHJH is reduced modulo this Groebner basis by transformations to be described in a subsequent section. Note: This yields a canonical form. But which canonical form? It depends on the choice of ordering for the variables. The user can control the ordering by using the 3-argument syntax NiMtJSlzaW1wbGlmeUc2JSUlZXhwckclKXNpZGVyZWxzRyUldmFyc0c= where NiMlJXZhcnNH is a list of variables in the desired order.

siderels := {sin(x)^2 + cos(x)^2 = 1};

PCMvLCYqJCktSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGLCIiIyIiIkYwKiQpLUkkY29zR0YpRi1GL0YwRjBGMA==

e := sin(x)^3 - 11*sin(x)^2*cos(x) + 3*cos(x)^3 - sin(x)*cos(x) + 2;

LCwqJCktSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiJCIiIkYuKigiIzZGLilGJSIiI0YuLUkkY29zR0YnRitGLiEiIiomRi1GLilGM0YtRi5GLiomRiVGLkYzRi5GNUYyRi4=

The following command indicates that we wish to "favour" transforming cos(x) into sin(x) as much as possible. simplify(e, siderels, [cos(x),sin(x)]);

LCwqJCktSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiJCIiIkYuKigiIzlGLilGJSIiI0YuLUkkY29zR0YnRitGLiEiIiomRiVGLkYzRi5GNUYyRi4qJkYtRi5GM0YuRi4=

The following command indicates that we wish to "favour" transforming sin(x) into cos(x) as much as possible. simplify(e, siderels, [sin(x),cos(x)]);

LC4qJiIjOSIiIiktSSRjb3NHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGLCIiJEYlRiUqJi1JJHNpbkdGKUYtRiVGJ0YlISIiIiIjRiUqJilGJ0Y0RiVGMUYlRjNGMUYlKiYiIzZGJUYnRiVGMw==

Try simplifying the following expression NiMlImZH . f := sin(x)^2 * cos(x)^2;

KiYpLUkkc2luRzYkJSpwcm90ZWN0ZWRHSShfc3lzbGliRzYiNiNJInhHRikiIiMiIiIpLUkkY29zR0YmRipGLEYt

simplify(f, siderels, [cos(x),sin(x)]);

LCYqJCktSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIkYuKiQpRiUiIiVGLiEiIg==

simplify(f, siderels, [sin(x),cos(x)]);

LCYqJCktSSRjb3NHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIkYuKiQpRiUiIiVGLiEiIg==

The expression NiMlImdH is equivalent to zero, and therefore its canonical form must be 0 (regardless of ordering). g := f - sin(x)^2 + sin(x)^4;

LCgqJiktSSRzaW5HNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2I0kieEdGKiIiIyIiIiktSSRjb3NHRidGK0YtRi5GLiokRiRGLiEiIiokKUYlIiIlRi5GLg==

simplify(g, siderels);

IiIh

Consider the polynomial domain Q[NiUlInhHJSJ5RyUiekc=] in three variables over the field Q of rational numbers. Suppose that the following three side relations are specified. siderels := {x^3*y*z = x*z^2, x*y^2*z = x*y*z, x^2*y^2 = z^2};

PCUvKigpSSJ4RzYiIiIkIiIiSSJ5R0YnRilJInpHRidGKSomRiZGKSlGKyIiI0YpLyooRiZGKSlGKkYuRilGK0YpKihGJkYpRipGKUYrRikvKiYpRiZGLkYpRjFGKSokRi1GKQ==

Consider the following polynomial expression. p := x*z^4 - x*y*z^3;

LCYqJkkieEc2IiIiIilJInpHRiUiIiVGJkYmKihGJEYmSSJ5R0YlRiYpRigiIiRGJiEiIg==

Problem: Express NiMlInBH in a canonical form with respect to NiMlKXNpZGVyZWxzRw== . This can be accomplished in Maple as follows. simplify(p, siderels);

IiIh

Offhand, you would not be able to recognize that NiMlInBH is equivalent to zero. How would you proceed to try to "reduce" NiMlInBH with respect to the given side relations? The mathematical framework is as follows. In the original polynomial domain Q[NiUlInhHJSJ5RyUiekc=] we can specify a "vector space" basis for this domain. There are various orderings of the monomials which can be chosen. For the moment, let us choose a basis corresponding to the total degree ordering with monomials of the same total degree ordered by a particular lexicographical ordering (called inverse lexicographical order), as follows. tdegBasis := [1,z,y,x,z^2,y*z,x*z,y^2,x*y,x^2,z^3,y*z^2,x*z^2,y^2*z,x*y*z,x^2*z,y^3,x*y^2,x^2*y,x^3,z^4,` . . . `];

NzgiIiJJInpHNiJJInlHRiVJInhHRiUqJClGJCIiI0YjKiZGJkYjRiRGIyomRidGI0YkRiMqJClGJkYqRiMqJkYnRiNGJkYjKiQpRidGKkYjKiQpRiQiIiRGIyomRiZGI0YpRiMqJkYnRiNGKUYjKiZGLkYjRiRGIyooRidGI0YmRiNGJEYjKiZGMUYjRiRGIyokKUYmRjRGIyomRidGI0YuRiMqJkYxRiNGJkYjKiQpRidGNEYjKiQpRiQiIiVGI0kofi5+Ln4ufkdGJQ==

Given the polynomial expression NiMlInBH in the domain Q[NiUlInhHJSJ5RyUiekc=] , we are required to simplify NiMlInBH with respect to NiMlKXNpZGVyZWxzRw== ; in other words, we want to express NiMlInBH in a canonical form as an element of the quotient ring Q[NiUlInhHJSJ5RyUiekc=] / NiMlI0lkRw== where NiMlI0lkRw== is the ideal generated by the side relations. For NiMlKXNpZGVyZWxzRw== as specified above, the corresponding ideal is NiMlI0lkRw== = < NiUsJiooKSUieEciIiQiIiIlInlHRiglInpHRihGKComRiZGKCokKUYqIiIjRihGKCEiIiwmKihGJkYoKiQpRilGLkYoRihGKkYoRigqKEYmRihGKUYoRipGKEYvLCYqJilGJkYuRihGM0YoRihGLEYv > . Objective: Define a basis for the quotient ring Q[NiUlInhHJSJ5RyUiekc=] / NiMlI0lkRw== and specify an algorithm to express any particular polynomial NiMlInBH in terms of that basis. The basis NiMlKnRkZWdCYXNpc0c= specified above for the domain Q[NiUlInhHJSJ5RyUiekc=] clearly is not a basis for the quotient ring. The monomials are not all independent in the quotient ring; e.g., NiMvKiYpJSJ4RyIiIyIiIiklInlHRidGKCokKSUiekdGJ0Yo . Question: Which monomials should be deleted from NiMlKnRkZWdCYXNpc0c= in order to obtain a basis for the quotient ring? To answer this question, we proceed as follows. Step 1: Compute a Groebner basis for the ideal NiMlI0lkRw== . Step 2: Examine each monomial NikiIiIlInpHJSJ5RyUieEcqJClGJCIiI0YjKiZGJUYjRiRGIyUofi5+Ln4ufkc= with respect to the Groebner basis for NiMlI0lkRw== to determine whether, as an element of Q[NiUlInhHJSJ5RyUiekc=] / NiMlI0lkRw== , it can be reduced to a lower-order monomial (with respect to the specified ordering of monomials). (E.g., NiMqJiklInhHIiIjIiIiKSUieUdGJkYn reduces to NiMqJCklInpHIiIjIiIi.) Note: The above concept is vague at this moment, but we will make it more precise. Also, it should be noted that what we will do, in practice, is to apply the reductions indicated in Step 2 on each particular term in the polynomial NiMlInBH that we wish to simplify.

The terminology "basis" used in the context of a Groebner basis is not the concept of a "vector space" or "polynomial" basis. Specifically, the elements in the basis will not be linearly independent in the sense of a vector space basis. Rather, it is the concept of an "ideal basis" which means a "set of generators for the ideal". Indeed, for the ideal NiMlI0lkRw== = < NiUsJiooKSUieEciIiQiIiIlInlHRiglInpHRihGKComRiZGKCokKUYqIiIjRihGKCEiIiwmKihGJkYoKiQpRilGLkYoRihGKkYoRigqKEYmRihGKUYoRipGKEYvLCYqJilGJkYuRihGM0YoRihGLEYv > the corresponding Groebner basis will have more elements (i.e. more generators) than the three specified in the original definition of NiMlI0lkRw== . Using Maple, we can determine a Groebner basis NiMlI0diRw== for the ideal NiMlI0lkRw== as seen in the following Example. (Note that the ideal is represented by specifying the generators in a Maple list. The "angle bracket" notation used above is a common mathematical notation for ideals, but angle brackets in Maple are used for a different purpose.)

Id := [x^3*y*z - x*z^2, x*y^2*z - x*y*z, x^2*y^2 - z^2];

NyUsJiooKUkieEc2IiIiJCIiIkkieUdGJ0YpSSJ6R0YnRilGKSomRiZGKSlGKyIiI0YpISIiLCYqKEYmRikpRipGLkYpRitGKUYpKihGJkYpRipGKUYrRilGLywmKiYpRiZGLkYpRjJGKUYpKiRGLUYpRi8=

nops(Id);

IiIk

TermOrder := tdeg(x,y,z);

LUkldGRlZ0c2IjYlSSJ4R0YkSSJ5R0YkSSJ6R0Yk

Gb := Groebner:-Basis(Id, TermOrder);

NyosJiomSSJ5RzYiIiIiKUkiekdGJiIiJEYnRicqJEYoRichIiIsJiomSSJ4R0YmRicpRikiIiNGJ0YsKiZGL0YnRihGJ0YnLCYqKEYlRidGL0YnRjBGJ0YnRi5GLCwmKiQpRikiIiVGJ0YsKiYpRi9GMUYnRjBGJ0YnLCYqKEYvRicpRiVGMUYnRilGJ0YnKihGL0YnRiVGJ0YpRidGLCwmRitGLCooRjpGJ0YlRidGKUYnRicsJiomRjpGJ0Y9RidGJyokRjBGJ0YsLCYqJClGKSIiJkYnRidGNkYs

nops(Gb);

IiIp

Note that the original specification of the ideal NiMlI0lkRw== has 3 generators whereas the Groebner basis NiMlI0diRw== has 8 generators. However, the same ideal is being specified with different sets of generators: NiMvLSUmSWRlYWxHNiMlI0lkRy1GJTYjJSNHYkc= . (See the definition of a Groebner basis in the next section.) For the polynomial NiMlInBH specified above, our task now is to reduce NiMlInBH with respect to the Groebner basis NiMlI0diRw== . The function NormalForm in the Groebner package performs "reduction to normal form" of a given polynomial with respect to a particular specification of an ideal. (See the next section for details of the reduction process.) p;

LCYqJkkieEc2IiIiIilJInpHRiUiIiVGJkYmKihGJEYmSSJ5R0YlRiYpRigiIiRGJiEiIg==

Groebner:-NormalForm(p, Gb, TermOrder);

IiIh

If the original list of generators NiMlI0lkRw== was used to specify the ideal then the reduction process applied by the NormalForm function would fail to recognize that NiMlInBH reduces to zero modulo the ideal. Groebner:-NormalForm(p, Id, TermOrder);

LCYqJkkieEc2IiIiIilJInpHRiUiIiVGJkYmKihGJEYmSSJ5R0YlRiYpRigiIiRGJiEiIg==

The S-polynomial of two polynomials NiQlImFHJSJiRw== is defined by NiMvLSUiU0c2JCUiYUclImJHKiYsJiomLSUiaEc2I0YoIiIiRidGL0YvKiYtRi02I0YnRi9GKEYvISIiRi8tJSRHQ0RHNiRGMUYsRjM= where NiMtJSJoRzYjJSJwRw== denotes the "head term" of a polynomial NiMlInBH , meaning the leading monomial (with respect to a specified term ordering).

An important property of NiMtJSJTRzYkJSJhRyUiYkc= is that the head term of NiMlImFH will be eliminated in the case where NiMtJSJoRzYjJSJiRw== | NiMtJSJoRzYjJSJhRw== , in which case we have NiMvLSUiU0c2JCUiYUclImJHLCZGJyIiIiooLSUiaEc2I0YnRipGKEYqLUYtNiNGKCEiIkYx .

p;

LCYqJkkieEc2IiIiIilJInpHRiUiIiVGJkYmKihGJEYmSSJ5R0YlRiYpRigiIiRGJiEiIg==

Let's choose one particular element from the Groebner basis NiMlI0diRw== . G1 := x*y*z^2 - x*z^2;

LCYqKEkieUc2IiIiIkkieEdGJUYmKUkiekdGJSIiI0YmRiYqJkYnRiZGKEYmISIi

With NiMvLSUiaEc2IyUicEcsJCooJSJ4RyIiIiUieUdGKyklInpHIiIkRishIiI= and NiMvLSUiaEc2IyUjRzFHKiglInhHIiIiJSJ5R0YqKSUiekciIiNGKg== we see that NiMtJSJoRzYjJSNHMUc= | NiMtJSJoRzYjJSJwRw== . Hence the NiMlIlNH-polynomial NiMtJSJTRzYkJSJwRyUjRzFH is as follows. headp := -x*y*z^3;

LCQqKEkieEc2IiIiIkkieUdGJUYmKUkiekdGJSIiJEYmISIi

headG1 := x*y*z^2;

KihJInlHNiIiIiJJInhHRiRGJSlJInpHRiQiIiNGJQ==

S := (headG1*p - headp*G1) / gcd(headp,headG1): S := normal(S,expanded);

LCYqJkkieEc2IiIiIilJInpHRiUiIiRGJiEiIiomRiRGJilGKCIiJUYmRiY=

or equivalently, S := p - (headp/headG1)*G1;

LCgqJkkieEc2IiIiIilJInpHRiUiIiVGJkYmKihGJEYmSSJ5R0YlRiYpRigiIiRGJiEiIiomRihGJiwmKihGK0YmRiRGJilGKCIiI0YmRiYqJkYkRiZGMkYmRi5GJkYm

S := expand(S);

LCYqJkkieEc2IiIiIilJInpHRiUiIiRGJiEiIiomRiRGJilGKCIiJUYmRiY=

The point to be noted in the above example is that the computation of the NiMlIlNH-polynomial NiMtJSJTRzYkJSJwRyUjRzFH results in a reduction of NiMlInBH in the following sense: The computed polynomial NiMlIlNH is equivalent to NiMlInBH in the quotient ring Q[NiUlInhHJSJ5RyUiekc=] / NiMtJSZJZGVhbEc2IyUjR2JH (equivalently, Q[NiUlInhHJSJ5RyUiekc=] / NiMtJSZJZGVhbEc2IyUjSWRH ) because all we did was to subtract from NiMlInBH a multiple of NiMlI0cxRw== , which is an element of the ideal (i.e. NiMvJSNHMUciIiE= ). Moreover, the head term NiMvLSUiaEc2IyUiU0cqJiUieEciIiIqJCklInpHIiIlRipGKg== is smaller (in the specified term ordering) than the original head term NiMvLSUiaEc2IyUicEcsJCooJSJ4RyIiIiUieUdGKyklInpHIiIkRishIiI= . It is precisely this type of reduction of the terms in the polynomial NiMlInBH that we wish to perform, and we wish to be guaranteed that NiMlInBH will get reduced to a canonical form. The desired guarantee comes from the definition of a Groebner basis for the ideal.

A polynomial NiMlInBH is F-reduced modulo the ideal basis LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JVEiRkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNjBRIj1GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0ZPLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUkobWZlbmNlZEdGJDYlLUYjNjAtRiw2JVEhRidGL0YyLUklbXN1YkdGJDYlLUYsNiVRImZGJ0YvRjItSSNtbkdGJDYkRlRGOS8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnLUY2NjBRIixGJ0Y5RjsvRj9GMUZARkJGREZGRkhGSi9GTlEkMGVtRicvRlFRM3Zlcnl0aGlja21hdGhzcGFjZUYnRlJGVS1GNjYwUTEmSW52aXNpYmxlVGltZXM7RidGOUY7Rj5GQEZCRkRGRkZIRkpGam8vRlFGW3BGUkZVLUY2NjBRIi5GJ0Y5RjtGPkZARkJGREZGRkhGSkZqb0ZhcEZSRlVGXnBGYnBGXnBGYnAtRjY2MEZgcEY5RjtGPkZARkJGREZGRkhGSkZNRlBGUkZVRmZvRl5wLUZbbzYlRl1vLUYsNiVRImtGJ0YvRjJGY29GZ24vJSVvcGVuR1EifGZyRicvJSZjbG9zZUdRInxockYnRmdu if no head term NiMtJSJoRzYjJiUiZkc2IyUiaUc= divides NiMtJSJoRzYjJSJwRw== , for NiYvJSJpRyIiIiIiIyUofi5+Ln4ufkclImtH .

Method of F-reduction: If NiMtJSJoRzYjJiUiZkc2IyUiaUc= | NiMtJSJoRzYjJSJwRw== then replace NiMlInBH by the NiMlIlNH-polynomial LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtRiw2JVEiU0YnRi9GMi1JI21vR0YkNjBRMCZBcHBseUZ1bmN0aW9uO0YnL0YzUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGQi8lKXN0cmV0Y2h5R0ZCLyUqc3ltbWV0cmljR0ZCLyUobGFyZ2VvcEdGQi8lLm1vdmFibGVsaW1pdHNHRkIvJSdhY2NlbnRHRkIvJSVmb3JtR1EmaW5maXhGJy8lJ2xzcGFjZUdRJDBlbUYnLyUncnNwYWNlR0ZULyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUkobWZlbmNlZEdGJDYjLUYjNictRiw2JVEicEYnRi9GMi1GOzYwUSIsRidGPkZAL0ZERjFGRUZHRklGS0ZNRk9GUi9GVlEzdmVyeXRoaWNrbWF0aHNwYWNlRidGV0ZaLUY7NjBRMSZJbnZpc2libGVUaW1lcztGJ0Y+RkBGQ0ZFRkdGSUZLRk0vRlBGLkZSRlVGV0ZaLUklbXN1YkdGJDYlLUYsNiVRImZGJ0YvRjItRiM2Iy1GLDYlUSJpRidGL0YyLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGK0Yr . I.e., perform the reduction NiMlInBH --> LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiUtRiw2JVEiU0YnRi9GMi1JI21vR0YkNjBRMCZBcHBseUZ1bmN0aW9uO0YnL0YzUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGQi8lKXN0cmV0Y2h5R0ZCLyUqc3ltbWV0cmljR0ZCLyUobGFyZ2VvcEdGQi8lLm1vdmFibGVsaW1pdHNHRkIvJSdhY2NlbnRHRkIvJSVmb3JtR1EmaW5maXhGJy8lJ2xzcGFjZUdRJDBlbUYnLyUncnNwYWNlR0ZULyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUkobWZlbmNlZEdGJDYjLUYjNictRiw2JVEicEYnRi9GMi1GOzYwUSIsRidGPkZAL0ZERjFGRUZHRklGS0ZNRk9GUi9GVlEzdmVyeXRoaWNrbWF0aHNwYWNlRidGV0ZaLUY7NjBRMSZJbnZpc2libGVUaW1lcztGJ0Y+RkBGQ0ZFRkdGSUZLRk0vRlBGLkZSRlVGV0ZaLUklbXN1YkdGJDYlLUYsNiVRImZGJ0YvRjItRiM2Iy1GLDYlUSJpRidGL0YyLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGK0Yr . Continue performing reductions until Definition 2 is satisfied. It is clear that if a polynomial NiMlInBH NiMlIkZH-reduces to zero then NiMlInBH is in NiMtJSZJZGVhbEc2IyUiRkc= . We would like the converse implication to hold. That is, we would have an effective method to answer the ideal membership question if, for an ideal basis NiMlIkdH , we would have the property: NiMlInBH is in NiMtJSZJZGVhbEc2IyUiR0c= if and only if NiMlInBH NiMlIkdH-reduces to zero. This property is precisely what a Groebner basis gives us.

A set of polynomials NiMlIkdH in a polynomial domain NiMlIkRH[NiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGJDYjJSJ2Rw==] is a Groebner basis (with respect to a specified term ordering) if NiMlInBH is in NiMtJSZJZGVhbEc2IyUiR0c= if and only if NiMlInBH NiMlIkdH-reduces to 0 .

An equivalent definition is provided by the following theorem, which tells us that for a Groebner basis NiMlIkdH the process of NiMlIkdH-reduction produces a unique canonical form.

A set of polynomials NiMlIkdH in a polynomial domain NiMlIkRH[NiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGJDYjJSJ2Rw==] is a Groebner basis if and only if the following property holds: NiMlInBH NiMlIkdH-reduces to NiMlInFH and NiMlInBH NiMlIkdH-reduces to NiMlInJH implies NiMvJSJxRyUickc= .

For a detailed development of Buchberger's algorithm to compute a Groebner basis, see [1]. The general idea is that, given an ideal basis NiMlI0lkRw== , we must compute another ideal basis NiMlIkdH such that NiMvLSUmSWRlYWxHNiMlIkdHLUYlNiMlI0lkRw== and NiMlIkdH is a Groebner basis. The algorithm consists of a sequence of operations based on computing NiMlIlNH-polynomials and applying the process of NiMlIkZH-reduction. The known algorithms for computing a Groebner basis have time complexity which is exponential in the number of variables. Therefore, if there are too many variables the computation becomes "hopeless". However, for many reasonably-sized problems, the method has proved to be very useful. As mentioned above, we can answer the general ideal membership question once we have computed a Groebner basis NiMlIkdH for the ideal. Specifically, to determine whether a given polynomial NiMlInBH is a member of NiMtJSZJZGVhbEc2IyUiR0c= we simply apply NiMlIkdH-reductions to determine whether NiMlInBH NiMlIkdH-reduces to zero. In Maple's Groebner package, the NormalForm function can be used for this purpose.

Consider the polynomial domain Q[NiUlInhHJSJ5RyUiekc=] and the ideal NiMlI0lkRw== specified above. Id;

NyUsJiooKUkieEc2IiIiJCIiIkkieUdGJ0YpSSJ6R0YnRilGKSomRiZGKSlGKyIiI0YpISIiLCYqKEYmRikpRipGLkYpRitGKUYpKihGJkYpRipGKUYrRilGLywmKiYpRiZGLkYpRjJGKUYpKiRGLUYpRi8=

The Groebner basis for NiMlI0lkRw== was determined to be as follows. Gb;

NyosJiomSSJ5RzYiIiIiKUkiekdGJiIiJEYnRicqJEYoRichIiIsJiomSSJ4R0YmRicpRikiIiNGJ0YsKiZGL0YnRihGJ0YnLCYqKEYlRidGL0YnRjBGJ0YnRi5GLCwmKiQpRikiIiVGJ0YsKiYpRi9GMUYnRjBGJ0YnLCYqKEYvRicpRiVGMUYnRilGJ0YnKihGL0YnRiVGJ0YpRidGLCwmRitGLCooRjpGJ0YlRidGKUYnRicsJiomRjpGJ0Y9RidGJyokRjBGJ0YsLCYqJClGKSIiJkYnRidGNkYs

Let NiMlInBH be the polynomial defined above. Is NiMlInBH in NiMtJSZJZGVhbEc2IyUjSWRH ? p;

LCYqJkkieEc2IiIiIilJInpHRiUiIiVGJkYmKihGJEYmSSJ5R0YlRiYpRigiIiRGJiEiIg==

Groebner:-NormalForm(p, Gb, TermOrder);

IiIh

Since NiMlInBH NiMlI0diRw==-reduces to zero we conclude that NiMlInBH is in NiMvLSUmSWRlYWxHNiMlI0lkRy1GJTYjJSNHYkc= . Create two different polynomials NiMlI3AxRw== and NiMlI3AyRw== which are known to be equivalent modulo NiMtJSZJZGVhbEc2IyUjSWRH . q := 3*x^5*y*z^2 - 1/2*x^4*y^3 + x*y*z;

LCgqKiIiJCIiIilJInhHNiIiIiZGJUkieUdGKEYlKUkiekdGKCIiI0YlRiUqKCNGJUYtRiUpRiciIiVGJSlGKkYkRiUhIiIqKEYnRiVGKkYlRixGJUYl

p1 := expand(q + (x^2 + y^2 + z^2)*p);

LDQqKiIiJCIiIilJInhHNiIiIiZGJUkieUdGKEYlKUkiekdGKCIiI0YlRiUqKCNGJUYtRiUpRiciIiVGJSlGKkYkRiUhIiIqKEYnRiVGKkYlRixGJUYlKiYpRixGMUYlKUYnRiRGJUYlKihGN0YlRipGJSlGLEYkRiVGMyooRidGJSlGKkYtRiVGNkYlRiUqKEYyRiVGJ0YlRjlGJUYzKiYpRiwiIidGJUYnRiVGJSooRidGJUYqRiUpRixGKUYlRjM=

p2 := expand(q + (x^3*y^2 - 3/4*x^2*z + 1/4*x*z^3 - 4/5)*p);

LDgqKiIiJCIiIilJInhHNiIiIiZGJUkieUdGKEYlKUkiekdGKCIiI0YlRiUqKCNGJUYtRiUpRiciIiVGJSlGKkYkRiUhIiIqKEYnRiVGKkYlRixGJUYlKihGMEYlKUYqRi1GJSlGLEYxRiVGJSooRjBGJUYyRiUpRixGJEYlRjMqKCNGJEYxRiUpRidGJEYlKUYsRilGJUYzKipGO0YlRjxGJUYqRiVGN0YlRiUqKCNGJUYxRiUpRidGLUYlKUYsIiIoRiVGJSoqRkBGJUZBRiVGKkYlKUYsIiInRiVGMyooI0YxRilGJUYnRiVGN0YlRjMqKkZIRiVGJ0YlRipGJUY5RiVGJQ==

Applying NormalForm to each of NiMlI3AxRw== and NiMlI3AyRw== should yield the same canoncial form. Groebner:-NormalForm(p1, Gb, TermOrder);

LCgqKEkieEc2IiIiIkkieUdGJUYmSSJ6R0YlRiZGJiomI0YmIiIjRiYpRigiIiVGJiEiIiooIiIkRiZGJEYmKUYoRitGJkYm

Groebner:-NormalForm(p2, Gb, TermOrder);

LCgqKEkieEc2IiIiIkkieUdGJUYmSSJ6R0YlRiZGJiomI0YmIiIjRiYpRigiIiVGJiEiIiooIiIkRiZGJEYmKUYoRitGJkYm

This must also be the canonical form of the polynomial NiMlInFH . Groebner:-NormalForm(q, Gb, TermOrder);

LCgqKEkieEc2IiIiIkkieUdGJUYmSSJ6R0YlRiZGJiomI0YmIiIjRiYpRigiIiVGJiEiIiooIiIkRiZGJEYmKUYoRitGJkYm

In this section we note, by looking at some examples, that a Groebner basis can be a very powerful tool for the problem of computing solutions to systems of polynomial equations. Specifically, the term ordering which is most desirable for this application is pure lexicographical ordering . For example, in the polynomial domain Q[NiUlInhHJSJ5RyUiekc=] the pure lexicographical ordering implies NiMiIiI= < NiMlInpH < NiMqJCklInpHIiIjIiIi < NiMlKH4ufi5+Ln5H < NiMlInlH < NiMqJiUieUciIiIlInpHRiU= < NiMqJiUieUciIiIqJCklInpHIiIjRiVGJQ== < NiMlKH4ufi5+Ln5H < NiMqJCklInlHIiIjIiIi < NiMqJiklInlHIiIjIiIiJSJ6R0Yn < NiMlKH4ufi5+Ln5H < NiMlInhH < NiMqJiUieEciIiIlInpHRiU= < NiMlKH4ufi5+Ln5H < NiMqJiUieEciIiIlInlHRiU= < NiMlKH4ufi5+Ln5H . The Problem Given a system of polynomial equations NiMvLSYlInBHNiMiIiI2JSYlInhHRiclKH4ufi5+Ln5HJkYrNiMlIm5HIiIh NiMvLSYlInBHNiMiIiM2JSYlInhHNiMiIiIlKH4ufi5+Ln5HJkYrNiMlIm5HIiIh NiMlKH4ufi5+Ln5H NiMvLSYlInBHNiMlImtHNiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGKzYjJSJuRyIiIQ== we wish to find values of ( NiUmJSJ4RzYjIiIiJSh+Ln4ufi5+RyZGJDYjJSJuRw== ) which simultaneously satisfy the NiMlImtH polynomial equations. Solution Technique Consider NiMtJSZJZGVhbEc2IyUiRkc= , the ideal generated by the given polynomials LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2JVEiRkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNjBRIj1GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUlZm9ybUdRJmluZml4RicvJSdsc3BhY2VHUS90aGlja21hdGhzcGFjZUYnLyUncnNwYWNlR0ZPLyUobWluc2l6ZUdRIjFGJy8lKG1heHNpemVHUSlpbmZpbml0eUYnLUkobWZlbmNlZEdGJDYlLUYjNi8tRiw2JVEhRidGL0YyLUklbXN1YkdGJDYlLUYsNiVRInBGJ0YvRjItSSNtbkdGJDYkRlRGOS8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnLUY2NjBRIixGJ0Y5RjsvRj9GMUZARkJGREZGRkhGSi9GTlEkMGVtRicvRlFRM3Zlcnl0aGlja21hdGhzcGFjZUYnRlJGVS1GNjYwUTEmSW52aXNpYmxlVGltZXM7RidGOUY7Rj5GQEZCRkRGRkZIRkpGam8vRlFGW3BGUkZVLUY2NjBRIi5GJ0Y5RjtGPkZARkJGREZGRkhGSkZqb0ZhcEZSRlVGXnBGYnBGXnBGYnAtRjY2MEZgcEY5RjtGaW9GQEZCRkRGRkZIRkpGam9GXHBGUkZVRmZvLUZbbzYlRl1vLUYsNiVRImtGJ0YvRjJGY29GZ24vJSVvcGVuR1EifGZyRicvJSZjbG9zZUdRInxockYnLUY2NjBGYHBGOUY7Rj5GQEZCRkRGRkZIL0ZLRmluRmpvRmFwRlJGVQ==, and compute its Groebner basis NiMlIkdH using pure lexicographical ordering. Then the set of common zeros of NiMlIkZH is identical to the set of common zeros of NiMlIkdH and, moreover, we can obtain much more information about the common zeros from NiMlIkdH than from the original polynomials NiMlIkZH .

Suppose that we wish to solve the three polynomial equations: NiUvJSNxMUciIiEvJSNxMkdGJS8lI3EzR0Yl defined as follows. restart; q1 := x^2*y + 4*y^2 - 17: q2 := 2*x*y - 3*y^3 + 8: q3 := x*y^2 - 5*x*y + 1: F := [q1, q2, q3];

NyUsKComKUkieEc2IiIiIyIiIkkieUdGJ0YpRikqJiIiJUYpKUYqRihGKUYpIiM8ISIiLCgqKEYoRilGJkYpRipGKUYpKiYiIiRGKSlGKkYzRilGLyIiKUYpLCgqJkYmRilGLUYpRikqKCIiJkYpRiZGKUYqRilGL0YpRik=

G := Groebner:-Basis(F, plex(x,y,z));

NyMiIiI=

The system of equations specified by the Groebner basis is 1 = 0 which has no solution. Therefore the original set of polynomial equations has no solution.

Suppose that we wish to solve the following system of three polynomials. p1 := x^2 + y*z - 2: p2 := y^2 + x*z - 3: p3 := x*y + z^2 - 5: F := [p1, p2, p3];

NyUsKCokKUkieEc2IiIiIyIiIkYpKiZJInlHRidGKUkiekdGJ0YpRilGKCEiIiwoKiQpRitGKEYpRikqJkYmRilGLEYpRikiIiRGLSwoKiZGJkYpRitGKUYpKiQpRixGKEYpRikiIiZGLQ==

G := Groebner:-Basis(F, plex(x,y,z));

NyUsLComIiIpIiIiKUkiekc2IkYlRiZGJiomIiRRJUYmKUYoIiIlRiZGJiomIiRnKEYmKUYoIiIjRiYhIiIiJGgkRiYqJiIkKyJGJilGKCIiJ0YmRjIsLComRjNGJkkieUdGKUYmRiYqJiIjX0YmKUYoIiImRiZGJiomIiRTKEYmKUYoIiIkRiZGMiomIiVEOUYmRihGJkYmKiZGJUYmKUYoIiIoRiZGJiwsKiZGM0YmSSJ4R0YpRiZGJiomIiMpKUYmRkZGJkYyKiYiJSFwI0YmRkFGJkYyKiYiJXZCRiZGKEYmRiYqJiIkcylGJkY9RiZGJg==

From the original system of polynomials it is difficult to determine information about the solutions. However, the system of polynomial equations specified by the Groebner basis has a very interesting structure: the system has been triangularized ! Namely, in one equation the variable NiMlInhH is isolated as a function of NiMlInpH ; in another equation the variable NiMlInlH is isolated as a function of NiMlInpH; and the remaining equation involves a univariate polynomial in the variable NiMlInpH . Therefore, the solutions can be described as follows. xpoly := select(has, G, x)[];

LCwqJiIkaCQiIiJJInhHNiJGJUYlKiYiIykpRiUpSSJ6R0YnIiIoRiUhIiIqJiIlIXAjRiUpRisiIiRGJUYtKiYiJXZCRiVGK0YlRiUqJiIkcylGJSlGKyIiJkYlRiU=

ypoly := select(has, G, y)[];

LCwqJiIkaCQiIiJJInlHNiJGJUYlKiYiI19GJSlJInpHRiciIiZGJUYlKiYiJFMoRiUpRisiIiRGJSEiIiomIiVEOUYlRitGJUYlKiYiIilGJSlGKyIiKEYlRiU=

zpoly := remove(has, G, {x,y})[];

LCwqJiIiKSIiIilJInpHNiJGJEYlRiUqJiIkUSVGJSlGJyIiJUYlRiUqJiIkZyhGJSlGJyIiI0YlISIiIiRoJEYlKiYiJCsiRiUpRiciIidGJUYx

We can solve explicitly for NiMlInhH and NiMlInlH as a function of NiMlInpH . xval := solve(xpoly, x);

LCoqJiMiIykpIiRoJCIiIilJInpHNiIiIihGJ0YnKiYjIiUhcCNGJkYnKUYpIiIkRidGJyomIyIkRCIiIz5GJ0YpRichIiIqJiMiJHMpRiZGJylGKSIiJkYnRjU=

yval := solve(ypoly, y);

LCoqJiMiIikiJGgkIiIiKUkiekc2IiIiKEYnISIiKiYjIiNfRiZGJylGKSIiJkYnRiwqJiMiJFMoRiZGJylGKSIiJEYnRicqJiMiI3YiIz5GJ0YpRidGLA==

For each of the 8 roots of the univariate polynomial NiMlJnpwb2x5Rw== we have a triple ( NiUlInhHJSJ5RyUiekc= ) which is a solution of the original system of polynomial equations. The symbolic representation of the roots of NiMlJnpwb2x5Rw== obtained via NiMtJSZzb2x2ZUc2JCUmenBvbHlHJSJ6Rw== is expressed using the NiMlJ1Jvb3RPZkc= construct (by default) and is not very informative. One can note that NiMlJnpwb2x5Rw== is actually just a quartic polynomial in NiMqJCklInpHIiIjIiIi and therefore an explicit symbolic representation of its roots in terms of radicals can be obtained -- the following Maple commands will express the roots in terms of radicals. # _EnvExplicit := true; # solve(zpoly, z); These commands are commented out here because the resulting expressions for the eight roots are somewhat complicated. However, we already have a complete structural specification for the solutions of the given system of polynomial equations. We may choose to do numerical root-finding for the roots of NiMlJnpwb2x5Rw== . zval := fsolve(zpoly, z, 'complex');

NiokIStmOCNHQCMhIiosJiQiKz1zM2w9RiUhIiIqJiQiK3MhKVx5QCEjNSIiIl4jRi5GLkYpLCZGJ0YpRipGLiQhK3ojPSY0JylGLSQiK3ojPSY0JylGLSwmRidGLkYqRiksJkYnRi5GKkYuJCIrZjgjR0AjRiU=

The eight solutions of the original polynomial system NiMlIkZH can be computed as follows. soln := seq( [x = eval(xval, z=zval[i]), y = eval(yval, z=zval[i]), z = zval[i]], i = 1..nops([zval]) );

Nio3JS9JInhHNiIkISlfNGA4ISIoL0kieUdGJiQhKSdRTGsoISIqL0kiekdGJiQhK2Y4I0dAI0YuNyUvRiUsJiQiKWxPanUhIikhIiIqJiQiKUwoSF4qRjgiIiJeI0Y9Rj1GPS9GKywmJCIrJXkib0g4Ri5GOSomJCIrMFVMZ2chIzVGPUY+Rj1GOS9GMCwmJCIrPXMzbD1GLkY5KiYkIitzISlceUBGRkY9Rj5GPUY5NyUvRiUsJkY2RjlGOkY5L0YrLCZGQUY5RkNGPS9GMCwmRklGOUZLRj03JS9GJSQiKz96J2YnPkYuL0YrJCIrTD1DbUBGLi9GMCQhK3ojPSY0JylGRjclL0YlJCErP3onZic+Ri4vRiskIStMPUNtQEYuL0YwJCIreiM9JjQnKUZGNyUvRiUsJkY2Rj1GOkY9L0YrLCZGQUY9RkNGOS9GMCwmRklGPUZLRjk3JS9GJSwmRjZGPUY6RjkvRissJkZBRj1GQ0Y9L0YwLCZGSUY9RktGPTclL0YlJCIpXzRgOEYpL0YrJCIpJ1FMayhGLi9GMCQiK2Y4I0dAI0Yu

Check that each of these eight triples is a zero of the original polynomial system (to the numerical accuracy being used). seq( eval(F,soln[i]), i=1..nops([soln]) );

Nio3JSQiI1whIiokIiNARiYkIiM6RiY3JSwmRiciIiIqJiQiIz1GJkYtXiNGLUYtISIiLCYkIiNFRiZGLSomJCIiJUYmRi1GMUYtRi0sJkYpRi0qJiQiI1AhIzVGLUYxRi1GLTclLCZGJ0YtRi5GLSwmRjRGLUY2RjIsJkYpRi1GOkYyNyUkISIlRiYkIiImRiYkRi1GJkZCRj5GK0Yj

In some cases, the Groebner basis for a polynomial system may contain one or more polynomials which can be factored, in which case the polynomial system breaks into subsystems (corresponding to subvarieties in the solution space). The Solve function in the Groebner package is designed to perform factoring whenever possible while computing the lexicographic Groebner basis, so as to facilitate solving the polynomial system. Hence it is advisable to use the Groebner:-Solve function rather than the more basic Groebner:-Basis function when the objective is to solve a system of polynomial equations. Consider the following system of polynomials. f1 := 4*x^2 + x*y^2 - z + 1/4: f2 := 2*x + y^2*z + 1/2: f3 := x^2*z - 1/2*x - y^2: F := [f1, f2, f3];

NyUsKiomIiIlIiIiKUkieEc2IiIiI0YmRiYqJkYoRiYpSSJ5R0YpRipGJkYmSSJ6R0YpISIiI0YmRiVGJiwoKiZGKkYmRihGJkYmKiZGLkYmRixGJkYmI0YmRipGJiwoKiZGLkYmRidGJkYmKiZGNEYmRihGJkYvKiRGLEYmRi8=

s := Groebner:-Solve(F, [x,y,z]);

PCQ3JTclLCZJInpHNiIiIiJGKCEiIiwmKiYiIiNGKClJInlHRidGLEYoRihGKEYpLCYqJkYsRihJInhHRidGKEYoRihGKC1JJXBsZXhHRic2JUYxRi5GJjwiNyU3JSwwKiYiIztGKClGJiIiJ0YoRigqJiIiKUYoKUYmIiImRihGKComIiIqRigpRiYiIiVGKEYoKiYiI2hGKClGJiIiJEYoRigqJiIkTyJGKClGJkYsRihGKComIiQxI0YoRiZGKEYpIiNnRigsMComIiQlR0YoRi1GKEYoKiYiJWtjRihGP0YoRigqJiIlb2JGKEZDRihGKComIiVtZUYoRkdGKEYoKiYiJmxWI0YoRktGKEYoKiYiJlAqZkYoRiZGKEYoIiZ5UiVGKSwwKiYiJG8mRihGMUYoRigqJiIlT0ZGKEY/RihGKSomIiUhbyNGKEZDRihGKSomIiVyRkYoRkdGKEYpKiYiJiR6NkYoRktGKEYpKiYiJlkqR0YoRiZGKEYpIiYjUUBGKEYyRjU=

The result NiMlInNH consists of a set of two subsystems, as follows. s[1];

NyU3JSwmSSJ6RzYiIiIiRichIiIsJiomIiIjRicpSSJ5R0YmRitGJ0YnRidGKCwmKiZGK0YnSSJ4R0YmRidGJ0YnRictSSVwbGV4R0YmNiVGMEYtRiU8Ig==

s[2];

NyU3JSwwKiYiIzsiIiIpSSJ6RzYiIiInRidGJyomIiIpRicpRikiIiZGJ0YnKiYiIipGJylGKSIiJUYnRicqJiIjaEYnKUYpIiIkRidGJyomIiRPIkYnKUYpIiIjRidGJyomIiQxI0YnRilGJyEiIiIjZ0YnLDAqJiIkJUdGJylJInlHRipGO0YnRicqJiIla2NGJ0YuRidGJyomIiVvYkYnRjJGJ0YnKiYiJW1lRidGNkYnRicqJiImbFYjRidGOkYnRicqJiImUCpmRidGKUYnRiciJnlSJUY+LDAqJiIkbyZGJ0kieEdGKkYnRicqJiIlT0ZGJ0YuRidGPiomIiUhbyNGJ0YyRidGPiomIiVyRkYnRjZGJ0Y+KiYiJiR6NkYnRjpGJ0Y+KiYiJlkqR0YnRilGJ0Y+IiYjUUBGJy1JJXBsZXhHRio2JUZTRkRGKTwi

The notation for each subsystem is a list of three elements: a list of polynomials which is a Groebner basis for the subsystem, the term ordering which was used, and the last element is a set of constraints in the form of polynomials which must not vanish. Note that the simpler of the two subsystems contains a polynomial in NiMlInpH of degree NiMiIiI= . Let NiMlI0cxRw== be the Groebner basis of the simpler subsystem and let NiMlI0cyRw== be the Groebner basis of the more complicated subsystem. (G1,G2) := (s[1][1], s[2][1]): if not member(z-1, G1) then # Make G1 be the simpler subsystem. (G1,G2) := (G2,G1) end if: G1;

NyUsJkkiekc2IiIiIkYmISIiLCYqJiIiI0YmKUkieUdGJUYqRiZGJkYmRicsJiomRipGJkkieEdGJUYmRiZGJkYm

G2;

NyUsMComIiM7IiIiKUkiekc2IiIiJ0YmRiYqJiIiKUYmKUYoIiImRiZGJiomIiIqRiYpRigiIiVGJkYmKiYiI2hGJilGKCIiJEYmRiYqJiIkTyJGJilGKCIiI0YmRiYqJiIkMSNGJkYoRiYhIiIiI2dGJiwwKiYiJCVHRiYpSSJ5R0YpRjpGJkYmKiYiJWtjRiZGLUYmRiYqJiIlb2JGJkYxRiZGJiomIiVtZUYmRjVGJkYmKiYiJmxWI0YmRjlGJkYmKiYiJlAqZkYmRihGJkYmIiZ5UiVGPSwwKiYiJG8mRiZJInhHRilGJkYmKiYiJU9GRiZGLUYmRj0qJiIlIW8jRiZGMUYmRj0qJiIlckZGJkY1RiZGPSomIiYkejZGJkY5RiZGPSomIiZZKkdGJkYoRiZGPSImI1FARiY=

From NiMlI0cxRw== we obtain two solutions. _EnvExplicit := true: G1_soln := solve(G1, [x,y,z]);

NyQ3JS9JInhHNiIjISIiIiIjL0kieUdGJiwkKiYjIiIiRilGLylGKUYuRi9GLy9JInpHRiZGLzclRiQvRissJEYtRihGMQ==

From NiMlI0cyRw== , first separate out the three Groebner basis polynomials. xpoly := select(has, G2, x)[];

LDAqJiIkbyYiIiJJInhHNiJGJUYlKiYiJU9GRiUpSSJ6R0YnIiImRiUhIiIqJiIlIW8jRiUpRisiIiVGJUYtKiYiJXJGRiUpRisiIiRGJUYtKiYiJiR6NkYlKUYrIiIjRiVGLSomIiZZKkdGJUYrRiVGLSImI1FARiU=

ypoly := select(has, G2, y)[];

LDAqJiIkJUciIiIpSSJ5RzYiIiIjRiVGJSomIiVrY0YlKUkiekdGKCIiJkYlRiUqJiIlb2JGJSlGLSIiJUYlRiUqJiIlbWVGJSlGLSIiJEYlRiUqJiImbFYjRiUpRi1GKUYlRiUqJiImUCpmRiVGLUYlRiUiJnlSJSEiIg==

zpoly := remove(has, G2, {x,y})[];

LDAqJiIjOyIiIilJInpHNiIiIidGJUYlKiYiIilGJSlGJyIiJkYlRiUqJiIiKkYlKUYnIiIlRiVGJSomIiNoRiUpRiciIiRGJUYlKiYiJE8iRiUpRiciIiNGJUYlKiYiJDEjRiVGJ0YlISIiIiNnRiU=

There is one value of NiMlInhH corresponding to each value of NiMlInpH . xval := solve(xpoly, x);

LC4qJiMiJiR6NiIkbyYiIiIpSSJ6RzYiIiIjRidGJyomIyIkVSQiI3JGJylGKSIiJkYnRicqJiMiJE4kRi9GJylGKSIiJUYnRicqJiMiJXJGRiZGJylGKSIiJEYnRicqJiMiJnRXIiIkJUdGJ0YpRidGJyMiJiJwNUY/ISIi

There are two values of NiMlInlH corresponding to each value of NiMlInpH . yval := solve(ypoly, y);

NiQsJComIyIiIiIkVSJGJiksLiomIidXQFNGJilJInpHNiIiIiZGJiEiIiomIidHYFJGJilGLSIiJUYmRjAqJiInJ1s7JUYmKUYtIiIkRiZGMComIig6Kkg8RiYpRi0iIiNGJkYwKiYiKEZiRCVGJkYtRiZGMCIoUUM3JEYmI0YmRjxGJkYmLCRGJEYw

There are six values of NiMlInpH to be determined zval := solve(zpoly, z);

NigtSSdSb290T2ZHNiQlKnByb3RlY3RlZEdJKF9zeXNsaWJHNiI2JCwwKiYiIzsiIiIpSSNfWkdGJSIiJ0YtRi0qJiIiKUYtKUYvIiImRi1GLSomIiIqRi0pRi8iIiVGLUYtKiYiI2hGLSlGLyIiJEYtRi0qJiIkTyJGLSlGLyIiI0YtRi0qJiIkMSNGLUYvRi0hIiIiI2dGLS9JJmluZGV4R0YlRi0tRiQ2JEYqL0ZGRkAtRiQ2JEYqL0ZGRjwtRiQ2JEYqL0ZGRjgtRiQ2JEYqL0ZGRjQtRiQ2JEYqL0ZGRjA=

Let us express the 12 solutions corresponding to subsystem NiMlI0cyRw== numerically. zval := evalf(zval);

NigkIitPVGRLWyEjNSQiKzJBVSNvJkYlLCYkIis7VlpXJSlGJSIiIiomJCIrSjVqMjwhIipGK14jRitGK0YrLCYkIitccz4/O0YvISIiKiYkIitJJClwbTVGL0YrRjBGK0YrLCZGMkY0RjVGNCwmRilGK0YsRjQ=

G2_soln := NULL: for i to nops([zval]) do zi := zval[i]; G2_soln := G2_soln, [x=eval(xval,z=zi), y=eval(yval[1],z=zi), z=zi], [x=eval(xval,z=zi), y=eval(yval[2],z=zi), z=zi] end do: G2_soln;

Ni43JS9JInhHNiIkISphIkhMcyEiKS9JInlHRiYkIitQdSZmUCYhIiovSSJ6R0YmJCIrT1RkS1shIzU3JUYkL0YrJCErUHUmZlAmRi5GLzclL0YlJCEpbjYlNCRGKS9GKyQiK2kqPkdkJUYzL0YwJCIrMkFVI28mRjM3JUY5L0YrJCEraSo+R2QlRjNGPzclL0YlLCYkIilMbHNpRikiIiIqJiQiKURPV0hGKUZLXiNGS0ZLRksvRissJiQiK0QhPUR5JEYzRksqJiQiK2lFdywiKkYzRktGT0ZLRksvRjAsJiQiKztWWlclKUYzRksqJiQiK0o1ajI8Ri5GS0ZPRktGSzclRkcvRissJkZSISIiRlRGW29GVzclL0YlLCYkIilrODRCRilGW28qJiQiKSE+JT1rRilGS0ZPRktGW28vRissJiQiK19RTj5zRjNGSyomJCIrcnI0YFBGM0ZLRk9GS0Zbby9GMCwmJCIrXHM+PztGLkZbbyomJCIrSSQpcG01Ri5GS0ZPRktGSzclRl1vL0YrLCZGZm9GW29GaG9GS0ZbcDclL0YlLCZGX29GW29GYW9GSy9GKywmRmZvRktGaG9GSy9GMCwmRl1wRltvRl9wRltvNyVGZnAvRissJkZmb0Zbb0Zob0Zbb0ZqcDclL0YlLCZGSUZLRkxGW28vRissJkZSRktGVEZbby9GMCwmRllGS0ZlbkZbbzclRmBxL0YrLCZGUkZbb0ZURktGZHE=

Finally, NiMlKEcxX3NvbG5H and NiMlKEcyX3NvbG5H together represent the 14 solutions of the original polynomial system NiMlIkZH . F;

NyUsKiomIiIlIiIiKUkieEc2IiIiI0YmRiYqJkYoRiYpSSJ5R0YpRipGJkYmSSJ6R0YpISIiI0YmRiVGJiwoKiZGKkYmRihGJkYmKiZGLkYmRixGJkYmI0YmRipGJiwoKiZGLkYmRidGJkYmKiZGNEYmRihGJkYvKiRGLEYmRi8=

Check the solutions. seq( eval(F, G1_soln[i]), i=1..nops(G1_soln) );

NiQ3JSIiIUYkRiRGIw==

seq( eval(F, G2_soln[i]), i=1..nops([G2_soln]) );

Ni43JSQiJWtHISM1JCEkKyNGJiQiIichIilGIzclJCIkUSJGJiQhJFMiRiYkIiQvIkYmRiw3JSwmJCIlUUtGJiIiIiomJCIjJCkhIipGN14jRjdGNyEiIiwmJCIkeiVGO0Y9KiYkIiVLa0YmRjdGPEY3Rj0sJiQiJVBiRiZGNyomJCIkeCdGJkY3RjxGN0Y3RjM3JSwmJCIkRSJGO0Y3KiYkIiM7RjtGN0Y8RjdGNywmJCImTCg+ISM2RjcqJiQiI2FGO0Y3RjxGN0Y9LCYkIiRMKUYmRjcqJiQiJEYmRiZGN0Y8RjdGN0ZKNyUsJkZMRjdGTkY9LCZGUkY3RlVGNywmRllGN0ZlbkY9RmhuNyUsJkY1RjdGOEY3LCZGP0Y9RkFGNywmRkVGN0ZHRj1GXG8=

In addition to reference [1], for further reading on the solution of systems of polynomial equations and related topics, the undergraduate-level textbook [2] is highly recommended.

[1] K.O. Geddes, S.R. Czapor and G. Labahn, Algorithms for Computer Algebra , Kluwer Academic Publishers, Boston, 1992. [2] D. Cox, J. Little and D. O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra , Springer-Verlag, New York, 1992.