Using Maple's Groebner Basis Package.with(Groebner);The commands that we will mainly use are Basis - for computing a Groebner basisNormalForm - for computing the remainder of a polynomial divided by a (Groebner) basisLets execute Buchberger's algorithm on the ideal I = <LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYjLUkjbW5HRiQ2JFEiMUYnL0Y2USdub3JtYWxGJy8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYn, LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYjLUkjbW5HRiQ2JFEiMkYnL0Y2USdub3JtYWxGJy8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYn> below..f1 := x*y-y^2;
f2 := x^3-z^2;
G0 := [f1,f2];We'll use the SPolynomial and LeadingMonomial commands.
And we'll use lexicographical order with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbWlHRiQ2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1GLDYlUSJ5RidGL0YyRjUtRiw2JVEiekYnRi9GMi8lMGZvbnRfc3R5bGVfbmFtZUdRJ05vcm1hbEYnRjk=LeadingMonomial(f1,plex(x,y,z));
LeadingMonomial(f2,plex(x,y,z));f3 := SPolynomial(f1,f2,plex(x,y,z));The NormalForm computes the remainder of S(f1,f2) divided by G.f3 := NormalForm(f3,G0,plex(x,y,z));The remainder is not 0 so we add f3 to the basis.G1 := [f1,f2,f3];map(LeadingMonomial,G1,plex(x,y,z));Now S(f2,f3) reduces to 0 by Proposition 4 of 2.9 so we only need to considerf4 := SPolynomial(f1,f3,plex(x,y,z));f4 := NormalForm(f4,G1,plex(x,y,z));So G1 is a Groebner basis for I = <f1,f2>. It happens to be also reduced. Let's check with Maple.G := Basis([f1,f2],plex(x,y,z));G1;This polynomial is in the ideal I. Let's test thisf := expand(x*f1+y*f2);NormalForm(f,G,plex(x,y,z));NormalForm(f+x+1,G,plex(x,y,z));Monomial Orderings in Maple
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEia0YnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYoLUYsNiVRInhGJ0YvRjItSSNtb0dGJDYtUSIsRicvRjNRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0YxLyUpc3RyZXRjaHlHRkUvJSpzeW1tZXRyaWNHRkUvJShsYXJnZW9wR0ZFLyUubW92YWJsZWxpbWl0c0dGRS8lJ2FjY2VudEdGRS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHUSwwLjMzMzMzMzNlbUYnLUYsNiVRInlGJ0YvRjJGPS1GLDYlUSJ6RidGL0YyRkFGQS8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJ0ZBCox, Little O'Shea textMapleLexicographical orderlex with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1GLDYlUSJ5RidGL0YyRjUtRiw2JVEiekYnRi9GMkY5plex(x,y,z)Graded lexicographical ordergrlex with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1GLDYlUSJ5RidGL0YyRjUtRiw2JVEiekYnRi9GMkY5grlex(x,y,z)Graded reverse lexicographical ordergrevlex with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUkjbWlHRiQ2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1GLDYlUSJ5RidGL0YyRjUtRiw2JVEiekYnRi9GMkY5tdeg(x,y,z)
f := 3*x^3 + 4*x*y*z^2 + 5*y^3*z;Notice that the LeadingTerm command in Maple returns a pair (leading coefficient, LeadingMonomial(f,plex(x,y,z));
LeadingCoefficient(f,plex(x,y,z));
LeadingTerm(f,plex(x,y,z));LeadingMonomial(f,grlex(x,y,z));
LeadingCoefficient(f,grlex(x,y,z));LeadingMonomial(f,tdeg(x,y,z));
LeadingCoefficient(f,tdeg(x,y,z));Graph ColoringLet's try to color the graph C3, a cycle on three vertices with k=2 colors (it's not 2-colorable).LSUlUExPVEc2Ki0lJ0NVUlZFU0c2JzckNyQkISM1ISIiJCIiISEiIjckJCIiISEiIiQiIzUhIiI3JDckJCEjNSEiIiQiIiEhIiI3JCQiIzUhIiIkIiIhISIiNyQ3JCQiIiEhIiIkIiM1ISIiNyQkIiM1ISIiJCIiISEiIi0lJkNPTE9SRzYmJSRSR0JHJCIiISEiIiQiIiEhIiIkIiM1ISIiLSUqVEhJQ0tORVNTRzYjIiIkLSUlVEVYVEc2JTckJCIiISEiIiQiIzYhIiItJSlfVFlQRVNFVEc2Iy1JJW1yb3dHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHNiI2Ni1JI21zRzYjL0krbW9kdWxlbmFtZUc2IkksVHlwZXNldHRpbmdHSShfc3lzbGliRzYiNiNRIjE2Ii8lJ2ZhbWlseUdRMFRpbWVzfk5ld35Sb21hbjYiLyUlc2l6ZUdRIzEyNiIvJSVib2xkR1EmZmFsc2U2Ii8lJ2l0YWxpY0dRJmZhbHNlNiIvJSp1bmRlcmxpbmVHUSZmYWxzZTYiLyUqc3Vic2NyaXB0R1EmZmFsc2U2Ii8lLHN1cGVyc2NyaXB0R1EmZmFsc2U2Ii8lK2ZvcmVncm91bmRHUShbMCwwLDBdNiIvJStiYWNrZ3JvdW5kR1EuWzI1NSwyNTUsMjU1XTYiLyUnb3BhcXVlR1EmZmFsc2U2Ii8lK2V4ZWN1dGFibGVHUSZmYWxzZTYiLyUpcmVhZG9ubHlHUSZmYWxzZTYiLyUpY29tcG9zZWRHUSZmYWxzZTYiLyUqY29udmVydGVkR1EmZmFsc2U2Ii8lK2ltc2VsZWN0ZWRHUSZmYWxzZTYiLyUscGxhY2Vob2xkZXJHUSZmYWxzZTYiLyU2c2VsZWN0aW9uLXBsYWNlaG9sZGVyR1EmZmFsc2U2Ii8lMGZvbnRfc3R5bGVfbmFtZUdRJ05vcm1hbDYiLyUsbWF0aHZhcmlhbnRHUSdub3JtYWw2Ii0lJUZPTlRHNiQlKkhFTFZFVElDQUciIz0tJSVURVhURzYlNyQkISM2ISIiJCIiISEiIi0lKV9UWVBFU0VURzYjLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkc2IjY2LUkjbXNHNiMvSSttb2R1bGVuYW1lRzYiSSxUeXBlc2V0dGluZ0dJKF9zeXNsaWJHNiI2I1EiMzYiLyUnZmFtaWx5R1EwVGltZXN+TmV3flJvbWFuNiIvJSVzaXplR1EjMTI2Ii8lJWJvbGRHUSZmYWxzZTYiLyUnaXRhbGljR1EmZmFsc2U2Ii8lKnVuZGVybGluZUdRJmZhbHNlNiIvJSpzdWJzY3JpcHRHUSZmYWxzZTYiLyUsc3VwZXJzY3JpcHRHUSZmYWxzZTYiLyUrZm9yZWdyb3VuZEdRKFswLDAsMF02Ii8lK2JhY2tncm91bmRHUS5bMjU1LDI1NSwyNTVdNiIvJSdvcGFxdWVHUSZmYWxzZTYiLyUrZXhlY3V0YWJsZUdRJmZhbHNlNiIvJSlyZWFkb25seUdRJmZhbHNlNiIvJSljb21wb3NlZEdRJmZhbHNlNiIvJSpjb252ZXJ0ZWRHUSZmYWxzZTYiLyUraW1zZWxlY3RlZEdRJmZhbHNlNiIvJSxwbGFjZWhvbGRlckdRJmZhbHNlNiIvJTZzZWxlY3Rpb24tcGxhY2Vob2xkZXJHUSZmYWxzZTYiLyUwZm9udF9zdHlsZV9uYW1lR1EnTm9ybWFsNiIvJSxtYXRodmFyaWFudEdRJ25vcm1hbDYiLSUlRk9OVEc2JCUqSEVMVkVUSUNBRyIjPS0lJVRFWFRHNiU3JCQiIzYhIiIkIiIhISIiLSUpX1RZUEVTRVRHNiMtSSVtcm93RzYjL0krbW9kdWxlbmFtZUc2IkksVHlwZXNldHRpbmdHSShfc3lzbGliRzYiNjYtSSNtc0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkc2IjYjUSIyNiIvJSdmYW1pbHlHUTBUaW1lc35OZXd+Um9tYW42Ii8lJXNpemVHUSMxMjYiLyUlYm9sZEdRJmZhbHNlNiIvJSdpdGFsaWNHUSZmYWxzZTYiLyUqdW5kZXJsaW5lR1EmZmFsc2U2Ii8lKnN1YnNjcmlwdEdRJmZhbHNlNiIvJSxzdXBlcnNjcmlwdEdRJmZhbHNlNiIvJStmb3JlZ3JvdW5kR1EoWzAsMCwwXTYiLyUrYmFja2dyb3VuZEdRLlsyNTUsMjU1LDI1NV02Ii8lJ29wYXF1ZUdRJmZhbHNlNiIvJStleGVjdXRhYmxlR1EmZmFsc2U2Ii8lKXJlYWRvbmx5R1EmZmFsc2U2Ii8lKWNvbXBvc2VkR1EmZmFsc2U2Ii8lKmNvbnZlcnRlZEdRJmZhbHNlNiIvJStpbXNlbGVjdGVkR1EmZmFsc2U2Ii8lLHBsYWNlaG9sZGVyR1EmZmFsc2U2Ii8lNnNlbGVjdGlvbi1wbGFjZWhvbGRlckdRJmZhbHNlNiIvJTBmb250X3N0eWxlX25hbWVHUSdOb3JtYWw2Ii8lLG1hdGh2YXJpYW50R1Enbm9ybWFsNiItJSVGT05URzYkJSpIRUxWRVRJQ0FHIiM9LSYlJl9BWElTRzYjIiIiNictJStfR1JJRExJTkVTRzYmLSUmQ09MT1JHNiYlJFJHQkckIiIhISIiJCIiISEiIiQiIiEhIiItJSpMSU5FU1RZTEVHNiMiIiEtJSpUSElDS05FU1NHNiMiIiEtJS1UUkFOU1BBUkVOQ1lHNiMkIiIhISIiLSUmQ09MT1JHNiYlJFJHQkckIiIhISIiJCIiISEiIiQiIiEhIiItJSpMSU5FU1RZTEVHNiMiIiEtJSpUSElDS05FU1NHNiMiIiEtJS1UUkFOU1BBUkVOQ1lHNiMkIiIhISIiLSYlJl9BWElTRzYjIiIjNictJStfR1JJRExJTkVTRzYmLSUmQ09MT1JHNiYlJFJHQkckIiIhISIiJCIiISEiIiQiIiEhIiItJSpMSU5FU1RZTEVHNiMiIiEtJSpUSElDS05FU1NHNiMiIiEtJS1UUkFOU1BBUkVOQ1lHNiMkIiIhISIiLSUmQ09MT1JHNiYlJFJHQkckIiIhISIiJCIiISEiIiQiIiEhIiItJSpMSU5FU1RZTEVHNiMiIiEtJSpUSElDS05FU1NHNiMiIiEtJS1UUkFOU1BBUkVOQ1lHNiMkIiIhISIiLSUqQVhFU1NUWUxFRzYjJSVOT05FRy0lJVJPT1RHNictJSlCT1VORFNfWEc2IyQiJFMiISIiLSUpQk9VTkRTX1lHNiMkIiRTIiEiIi0lLUJPVU5EU19XSURUSEc2IyQiJWc3ISIiLSUuQk9VTkRTX0hFSUdIVEc2IyQiJUk3ISIiLSUpQ0hJTERSRU5HNiI=k := 2;
S := [x1^k-1,x2^2-1,x3^2-1];The colors are the roots of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2I1EhRictRiM2JkYrLUYjNiMtSSVtc3VwR0YkNiUtRiw2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21uR0YkNiRRIjJGJy9GPVEnbm9ybWFsRicvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnLUkjbW9HRiQ2LVEoJm1pbnVzO0YnRkMvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRk4vJSlzdHJldGNoeUdGTi8lKnN5bW1ldHJpY0dGTi8lKGxhcmdlb3BHRk4vJS5tb3ZhYmxlbGltaXRzR0ZOLyUnYWNjZW50R0ZOLyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGZ24tRkA2JFEiMUYnRkNGKw== which are 1 and -1. These equations say each vertex can be colored with either color. But vertex 1 may not be the same color as vertex 2. So we should add the equation x1 + x2 = 0. Same for the other two edges. We haveS := [op(S), x1+x2, x1+x3, x2+x3 ];Basis(S,grlex(x1,x2,x3));This means G is not 2-colorable. But it is 3-colorable.k := 3;
S := [x1^k-1,x2^k-1,x3^k-1,
normal((x1^k-x2^k)/(x1-x2)),
normal((x1^k-x3^k)/(x1-x3)),
normal((x2^k-x3^k)/(x2-x3))];Basis(S,grlex(x1,x2,x3));This means x3 can be any color, x2 must be different from x3, and x1, x2, x3 must have all different colors.Solving Polynomial Equations using lex Groebner bases.Lets work with one of the ideals we saw in class, namely
I = < LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbWlHRiQ2I1EhRictRiM2KkYrLUYjNiMtSSVtc3VwR0YkNiUtRiw2JVEieEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21uR0YkNiRRIjJGJy9GPVEnbm9ybWFsRicvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnLUkjbW9HRiQ2LVEiK0YnRkMvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRk4vJSlzdHJldGNoeUdGTi8lKnN5bW1ldHJpY0dGTi8lKGxhcmdlb3BHRk4vJS5tb3ZhYmxlbGltaXRzR0ZOLyUnYWNjZW50R0ZOLyUnbHNwYWNlR1EsMC4yMjIyMjIyZW1GJy8lJ3JzcGFjZUdGZ24tRiw2JVEieUYnRjlGPEZILUYsNiVRInpGJ0Y5RjwtRkk2LVEoJm1pbnVzO0YnRkNGTEZPRlFGU0ZVRldGWUZlbkZobi1GQDYkUSIxRidGQy1GSTYtUSIsRidGQ0ZML0ZQRjtGUUZTRlVGV0ZZL0ZmblEmMC4wZW1GJy9GaW5RLDAuMzMzMzMzM2VtRictRiM2KUY2RkgtRiM2Iy1GNDYlRmpuRj9GRUZIRl1vRmBvRmNvRmZvLUYjNilGNkZIRmpuRkgtRiM2Iy1GNDYlRl1vRj9GRUZgb0Zjb0Yr >F := [x^2+y+z-1,x+y^2+z-1,x+y+z^2-1];G := Basis(F,grlex(x,y,z));H := Basis(F,plex(x,y,z));We can see that the first polynomial has repeated roots.factor(H[1]);The Solve command in the Groebner basis package drops multiple solutions.Solve(H,[x,y,z]);This has split up the solutions. We can solve them explicitly using solve_EnvExplicit := true;
V := {solve(H,{x,y,z})};nops(V);There are 5 distinct solutions in the variety V.The PolynomialIdeals package.The PolynomialIdeals package has additional operations for ideals.
It also allows me to use < > brackets for ideals.with(PolynomialIdeals);interface(imaginaryunit = iii);The above is to let me use the capital letter I for an ideal.F;I := <F>;The radical operation gets rid of all repeated solutions.J := Radical(I);Compute a Groebner basis for JBasis(J,plex(x,y,z));The PrimeDecompostion operation splits the ideal J into prime components, each of which corresponds to an irreducible variety.P := [PrimeDecomposition(J)];P := map(Simplify,P);From which we can see 1, 1, 2, 1 solutions. From which we can understand the output of the Solve command above.