Tag Archives: Gröbner basis

Use Gröbner bases to construct the colorings of a finite graph

A finite graph is a pair G = (V, E), where V is a finite set (whose elements are called vertices) and E is a set of unordered pairs from V (whose elements are called edges). We can visualize a graph in the plane by representing the vertices by dots and connecting a to b with a curve if \{a,b\} \in E. Let S be a finite set containing n elements. An n-coloring of a graph G = (V, E) is a mapping \kappa : V \rightarrow S such that, if \{a,b\} \in E, then \kappa(a) \neq \kappa(b). In other words, an assignment of a color to each vertex such that two adjacent vertices do not have the same color.

It turns out that we can represent every graph coloring as a solution to a carefully chosen system of polynomial equations. Conversely, given a finite graph G, we can construct a system of polynomial equations whose solutions are the colorings of G.

Let G = (V, E) be a finite graph, and let F be a field containing at least n elements. Introduce an indeterminate x_t for each vertex of G and let S \subseteq F be a finite subset containing n elements. Introduce an indeterminate z, and let f(z) = \prod_{\alpha \in S} (z - \alpha). Now suppose \kappa : V \rightarrow S is a coloring of G, and let x_t = \kappa(v_t) for each v_t \in V. Note that f(x_t) = 0. Moreover, if \{v_r, v_s\} \in E, then \kappa(v_r) \neq \kappa(v_s), so that x_r \neq x_s, and so x_r - x_s \neq 0. Note that f(x_r) - f(x_s) = \sum c_i (x_r^i - x_s^i) for some coefficients c_i, where c_0 = 0, and so x_r - x_s divides f(x_r) - f(x_s). In particular, letting g(x_r,x_s) = (f(x_r) - f(x_s))/(x_r - x_s) \in F[x_r, x_s], we have g(x_r, x_s) = 0. Thus, the coloring \kappa corresponds to a solution of the following system of equations.

  1. f(x_t) = 0 for each v_t \in V
  2. g(x_r,x_s) = 0 for each \{v_r,v_s\} \in E

Moreover, every solution to this system yields a coloring. It turns out (by some more advanced results that will be proved later (Hilbert’s Nullstellensatz)) that this system has a solution (and hence G has an n-coloring) unless the ideal I \subseteq F[x_1, \ldots, x_m] generated by the f(v_t) and g(x_r, x_s) is not proper. This is equivalent to the statement that the reduced Gröbner basis of I (with respect to any monomial order) is \{1\}. Thus, when a coloring exists, solving this system will find it.

There are many choices we might make for the field F, such as the finite field \mathbb{Z}/(p) or any field containing the distinct nth roots of unity.

  1. Consider the graph G whose vertices are the integers [1,8] and whose edges are \{1,3\}, \{1,4\}, \{1,5\}, \{2,4\}, \{2,7\}, \{2,8\}, \{3,4\}, \{3,6\}, \{3,8\}, \{4,5\}, \{5,6\}, \{6,7\}, \{6,8\}, and \{7,8\}. We can visualize this graph as in the following diagram.

    Let F = \mathbb{Z}/(3) and let S = F = \{0,1,2\} be our set of colors. Supposing we insist that the vertex 1 is colored by 0 \in S, deduce that G has two distinct 3-colorings, which depend on the coloring of vertex 8. Exhibit these two colorings. Show that if \{3,7\} is added to G, then the graph cannot be 3-colored.

  2. Consider the graph G whose vertices are the integers [1,5] and whose edges are \{1,3\}, \{1,4\}, \{1,5\}, \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, and \{4,5\}. (The complete graph on 5 vertices with one edge removed.) We can visualize this graph as in the following diagram.

    Let F = \mathbb{Z}/(5), and let S = \{1,2,3,4\}. Show that this graph can be 4-colored, but cannot be 3-colored.

  3. Let G be the graph having 9 vertices and having the edges \{1,4\}, \{1,6\}, \{1,7\}, \{1,8\}, \{2,3\}, \{2,4\}, \{2,6\}, \{2,7\}, \{3,5\}, \{3,7\}, \{3,9\}, \{4,5\}, \{4,6\}, \{4,7\}, \{4,9\}, \{5,6\}, \{5,7\}, \{5,8\}, \{5,9\}, \{6,7\}, \{6,9\}, and \{7,8\}. We can visualize this graph as in the following diagram.

    Show that this graph has precisely four 4-colorings up to a permutation of the colors. Show that if the edge \{1,5\} is added then G cannot be 4-colored.


We will use Maple to compute Gröbner bases.

  1. With our choice of F and S, evidently we have f(z) = z(z-1)(z-2) = z^3-z and g(y,w) = y^2+yw+w^2-1. Let I be the ideal I = (x_1) + (x_t^3-x_t \ |\ t \in [2,8]) + (x_r^2+x_rx_s+x_s^2-1 \ |\ \{r,s\} \in E). Using Maple, we find that this ideal has the Gröbner basis G = \{x_1, x_2, x_3 + x_8, x_4-x_8, x_5+x_8, x_6, x_7+x_8, x_8^2-1\}. Now x_8 = \pm 1. If x_8 = 1, then we have the solution (0,0,2,1,2,0,2,1), and if x_8 = -1, we have the solution (0,0,1,2,1,0,1,2). If we assign the color red to 0, blue to 1, and green to 2, this yields the following two actual colorings of the graph G.

    Note that these two colorings are really the same up to a permutation of the colors, namely by swapping “blue” and “green”.

    Now suppose we add the edge \{3,7\} to this graph; we can visualize this as in the following diagram. The added edge is colored in green.

    According to Maple, the ideal I + (x_3^2+x_3x_7+x_7^2-1) has reduced Gröbner basis 1 and thus is not a proper ideal. Thus this graph cannot be 3-colored. Another way to convince ourselves that this is true is to note that any 3-coloring of this graph is also a 3-coloring of the original graph G. However, in every 3-coloring of G, the vertices 3 and 7 have the same color, so that there can be no 3-coloring of G with \{3,7\} added.

  2. In this case, f(z) = (z-1)(z-2)(z-3)(z-4) = z^4-1, and thus g(x_r,x_s) = x_r^3+x_r^2x_s+x_rx_s^2+x_s^3. Let I = (x_t^4-1 \ |\ t \in [1,5]) + (x_r^3+x_r^2x_s+x_rx_s^2+x_s^3 \ |\ \{r,s\} \in E). Using Maple, we see that G = \{g_1 = x_5^4-1, g_2 = x_4^3+x_4^2x_5+x_4x_5^2+x_5^3, g_3 = x_5^2+x_5x_4+x_4^2+x_5x_3+x_4x_3+x_3^2, g_4 = x_2+x_5+x_4+x_3, g_5 = x_1+x_5+x_4+x_3\} is a Gröbner basis for this ideal.

    From g_1 = 0, we may let x_5 be any nonzero element of F; say x_5 = 1. Now g_2 = (x_4-2)(x_4-3)(x_4-4), so that x_4 \in \{2,3,4\}. Let’s say x_4 = 4. Now g_3 = (x_3-2)(x_3-3), so that x_3 \in \{2,3\}. Let’s say x_3 = 2. Then g_4 = x_2-3 and g_5 = x_1-3, so that x_2 = x_1 = 3. This gives a solution (3,3,2,4,1), which corresponds to the following explicit coloring of G if we let 1 be red, 2 be blue, 3 be green, and 4 be purple.

    Now let S = \{0,1,4\}. Then f(z) = z^3-z and g(x_r,x_s) = x_r^2+x_rx_s+x_s^2-1. Letting I be the ideal generated by the f(x_t) and g(x_r,x_s), using Maple we see that \{1\} is a Gröbner basis for this ideal; thus G does not have a 3-coloring.

  3. We let F = \mathbb{Z}/(5), and let S = \{1,2,3,4\}. Then f(z) = z^4-1 and g(x_r,x_s) = x_r^3+x_r^2x_s+x_rx_s^2+x_s^3. Suppose also that (without loss of generality) we insist that x_9 = 1. Using Maple, we see that the ideal I generated by these has as a Gröbner basis the set G = \{ g_1 = x_9-1, g_2 = 1+x_8+x_8^2+x_8^3, g_3 = x_7-1, g_4 = 1+x_6+x_6^2+x_6^3, g_5 = x_6+x_6^2-x_8-x_8^2-x_8x_5+x_6x_5, g_6 = 1+x_5+x_8+x_8^2+x_8x_5+x_5^2, g_7 = x_6+1+x_4+x_5, g_8 = -x_8-x_8^2-x_8x_5+x_3+x_5x_3+x_3^2, g_9 = x_2-x_5, g_{10} = x_1-x_5 \}. We now proceed to find all the solutions of this system.
    • Note that from g_1 = g_3 = 0, we have x_9 = x_7 = 1. From g_2 = (x_8 - 2)(x_8 - 3)(x_8 - 4) = 0, we have x_8 \in \{ 2,3,4 \}.
      • Suppose x_8 = 2. From g_6 = (x_5 - 3)(x_5 - 4) = 0, we have x_5 \in \{3,4\}.
        • Suppose x_5 = 3. Then from g_9 = g_{10} = 0, we have x_2 = x_1 = 3. From g_5 = (x_6 - 2)(x_6 - 4) = 0, we have x_6 \in \{2,4\}; if x_6 = 2, then g_7 = 0 yields x_4 = 4, and if x_6 = 4, then x_4 = 2. From g_8 = (x_3 - 2)(x_3 - 4) = 0, we have x_3 \in \{2,4\}. This yields the four solutions s_1 = (3,3,2,4,3,2,1,2,1), s_2 = (3,3,4,4,3,2,1,2,1), s_3 = (3,3,2,2,3,4,1,2,1), and s_4 = (3,3,4,2,3,4,1,2,1).
        • Suppose x_5 = 4. Then from g_9 = g_{10} = 0, we have x_2 = x_1 = 4. From g_5 = (x_6-2)(x_6-3) = 0, we have x_6 \in \{2,3\}. If x_6 = 2, then g_7 = 0 yields x_4 = 3, and if x_6 = 3, then x_4 = 2. From g_8 = (x_3-2)(x_3-3) = 0 we have x_3 \in \{2,3\}. This yields the four solutions s_5 = (4,4,2,3,4,2,1,2,1), s_6 = (4,4,2,2,4,3,1,2,1), s_7 = (4,4,3,3,4,2,1,2,1), and s_8 = (4,4,3,2,4,3,1,2,1).
      • Suppose x_8 = 3. Then in a similar fashion we get the eight solutions s_9 = (2,2,3,4,2,3,1,3,1), s_{10} = (2,2,3,3,2,4,1,3,1), s_{11} = (2,2,4,4,2,3,1,3,1), s_{12} = (2,2,4,3,2,4,1,3,1), s_{13} = (4,4,2,3,4,2,1,3,1), s_{14} = (4,4,2,2,4,3,1,3,1), s_{15} = (4,4,3,3,4,2,1,3,1), and s_{16} = (4,4,3,2,4,3,1,3,1).
      • Suppose x_8 = 4. Then in a similar fashion we get the eight solutions s_{17} = (2,2,3,4,2,3,1,4,1), s_{18} = (2,2,3,3,2,4,1,4,1), s_{19} = (2,2,4,4,2,3,1,4,1), s_{20} = (2,2,4,3,2,4,1,4,1), s_{21} = (3,3,2,4,3,2,1,4,1), s_{22} = (3.3.2.2.3.4.1.4.1), s_{23} = (3,3,4,4,3,2,1,4,1), and s_{24} = (3,3,4,2,3,4,1,4,1).

    Now S_4 acts on S^9 componentwise. (I.e. by permuting the “colors”.) Under this action, we note the following.

    • (3\ 4) \cdot s_1 = s_5, (2\ 3) \cdot s_1 = s_9, (2\ 4) \cdot s_1 = s_{24}, (2\ 3\ 4) \cdot s_1 = s_{16}, and (2\ 4\ 3) \cdot s_1 = s_{20}. So these six solutions are equivalent up to a permutation of the colors.
    • (3\ 4) \cdot s_2 = s_7, (2\ 3) \cdot s_2 = s_{11}, (2\ 4) \cdot s_2 = s_{22}, (2\ 3\ 4) \cdot s_2 = s_{14}, and (2\ 4\ 3) \cdot s_2 = s_{18}. So these six solutions are equivalent up to a permutation of the colors.
    • (3\ 4) \cdot s_3 = s_6, (2\ 3) \cdot s_3 = s_{10}, (2\ 4) \cdot s_3 = s_{23}, (2\ 3\ 4) \cdot s_3 = s_{15}, and (2\ 4\ 3) \cdot s_3 = s_{19}. So these six solutions are equivalent up to a permutation of the colors.
    • (3\ 4) \cdot s_4 = s_8, (2\ 3) \cdot s_4 = s_{12}, (2\ 4) \cdot s_4 = s_{21}, (2\ 3\ 4) \cdot s_4 = s_{13}, and (2\ 4\ 3) \cdot s_4 = s_{17}. So these six solutions are equivalent up to a permutation of the colors.

    Moreover, we can see that s_1, s_2, s_3, and s_4 are not equivalent up to a permutation of the colors; thus we have four essentially distinct colorings of G. If we let 1 be red, 2 be blue, 3 be green, and 4 be purple, then we can visualize these colorings as follows.

    • s_1:

    • s_2:

    • s_3:

    • s_4:

    Suppose now that we add the edge \{1,5\}. This graph can be visualized as in the following diagram; the added edge is colored green.

    If we include x_1^3+x_1^2x_5+x_1x_5^2+x_5^3 with the generators of the ideal I as before (and omit x_9-1), using Maple we see that this ideal has Gröbner basis \{1\}; that is, the graph with \{1,5\} added cannot be 4-colored.

    Another way to convince ourselves that this graph cannot be colored is to note that any 4-coloring of G with \{1,5\} added also gives a 4-coloring of G. However, in every 4-coloring of G, vertices 1 and 5 have the same color.

Compute the intersection of two polynomial ideals

Use Gröbner bases to compute the intersection of the ideals I = (x^3y-xy^2+1, x^2y^2-y^3-1) and J = (x^2-y^2, x^3+y^3) in F[x,y], where F is a field.


Recall that I \cap J = (tI + (1-t)J) \cap F[x,y], where t is a new indeterminate. Now tI + (1-t)J = (tx^3y-txy^2+t, tx^2y^2-ty^3-t, tx^2-ty^2-x^2+y^2, tx^3+ty^3-x^3-y^3). Using Bichberger’s algorithm (and Maple to keep track of the arithmetic) we find that G = \{ g_1 = xy^2+y^3, g_2 = x^2-y^2, g_3 = ty^4-ty^3-t, g_4 = tx+ty \} is a Gröbner basis of tI + (1-t)J with respect to the lex order induced by t > x > y > z. Proof details are in this Maple worksheet (change file type to .mws) or in plain text here. (Change file type to .txt)

Now G \cap F[x,y] is a Gröbner basis for I \cap J in F[x,y]; and thus we have I \cap J = (xy^2+y^3, x^2-y^2).

Compute the intersection of two polynomial ideals

Let F be a field. Use Gröbner bases to show that (x,z) \cap (y^2, x-yz) = (xy, x-yz) in F[x,y,z].


Recall that I \cap J = (tI + (1-t)J) \cap F[x,y,z], where t is a new indeterminate. Now tI + (1-t)J = (tx, tz, ty^2-y^2, tx-tyz-x+yz). Using Buchberger’s algorithm and Maple to keep track of the arithmetic, we find that this ideal has the reduced Gröbner basis G = \{ g_1 = y^2z, g_2 = x-yz, g_3 = tz, g_4 = ty^2-y^2 \} with respect to the lexicographic order induced by t > x > y > z. The details of this computation can be found in this Maple worksheet (change file type to .mws) or in plain text here (change file type to .txt).

Now G_2 = G \cap F[x,y,z] = \{ g_1 = y^2z, g_2 = x-yz \} is a Gröbner basis of I \cap J with respect to the lex order induced by x > y > z, and moreover is reduced. It is also easy to see using Buchberger’s criterion that G_2 is also the reduced Gröbner basis for (xy, x-yz) with respect to the lex order induced by x > y > z.

Thus (x,z) \cap (y^2, x-yz) = (xy, x-yz) in F[x,y,z].

Solve a system of polynomial equations in two variables

Use Gröbner bases to find all six solutions of the system 2x^3+2x^2y^2+3y^3=0 and 3x^5+2x^3y^3+2y^5=0 over \mathbb{C}.


Using Buchberger’s algorithm (and Maple to keep track of the arithmetic) we find that, using the lex order induced by x > y, the polynomials

  1. g_1 = x^3+x^2y^2+\frac{3}{2}y^3
  2. g_2 = x^2y^3+\frac{4}{9}xy^7-\frac{97}{81}xy^5-\frac{8}{27}y^8-\frac{16}{81}y^7-\frac{4}{9}y^5
  3. g_3 = xy^5+\frac{633744}{4418725}y^{11}+\frac{54}{85}y^{10}-\frac{1916118}{4418725}y^9-\frac{8517981}{4418725}y^8+\frac{7008109}{1767490}y^7+\frac{27}{8}y^6
  4. g_4 = y^{12}+\frac{97}{24}y^{11}-\frac{9}{2}y^{10}-\frac{195}{16}y^9+\frac{453}{16}y^8+\frac{6305}{384}y^7

is a Gröbner basis for the ideal I = (2x^3+2x^2y^2+3y^3, 3x^5+2x^3y^3+2y^5). The proof details can be found in a Maple worksheet here (file type .mws) or as a read-only version in plain text here. (File type .txt)

Certainly the system \{g_1, g_2, g_3, g_4\} has the same solution as our original system.

Consider first g_4 = 0; we may reduce the degree of this equation by canceling y^7, yielding the quintic polynomial g_4^\prime = y^{5}+\frac{97}{24}y^{4}-\frac{9}{2}y^{3}-\frac{195}{2}y^9+\frac{453}{16}y^1+\frac{6305}{384}. By clearing denominators, we get a polynomial in \mathbb{Z}[x] whose leading coefficient is 384 and whose constant coefficient is 6305; certainly these are relatively prime. Using the rational root theorem, we have a finite list of possible rational roots for this polynomial. Checking each of these in turn reveals that \frac{-1}{2}, \frac{-5}{2}, and \frac{-97}{24} are rational roots of g_4^\prime, and thus of g_4. In fact, g_4^\prime = (y+\frac{1}{2})(y+\frac{5}{2})(y+\frac{97}{24})(y^2-3y+\frac{13}{4}). Using the quadratic formula, we see that the roots of g_4 are \{ 0, \frac{-1}{2}, \frac{-5}{2}, \frac{-97}{24}, \frac{3}{2}+i, \frac{3}{2}-i \}.

Now from g_3 = 0, we have x = \frac{-633744}{4418725}y^6-\frac{54}{85}y^5+\frac{1916118}{4418725}y^4+\frac{8517981}{4418725}y^3-\frac{7008109}{1767490}y^2-\frac{27}{8}y. Substituting each of our y candidates yields the following points in \mathbb{R}^2: (0,0), (\frac{1}{2}, \frac{-1}{2}), (\frac{-5}{2}, \frac{-5}{2}), (\frac{-97}{36}, \frac{-97}{24}), (1-\frac{3}{2}i, \frac{3}{2}+i), and (1+\frac{3}{2}i, \frac{3}{2}-i). Evidently these points are all solutions of our system.

Use Gröbner bases to find the points of intersection of two curves

Find a Gröbner basis for the ideal I = (x^2+xy+y^2-1, x^2+4y^2-4) with respect to the lex order induced by x > y and use it to find the four points of intersection of the ellipse x^2+xy+y^2 = 1 with the ellipse x^2+4y^2 = 4 in \mathbb{R}^2.


Using Buchberger’s algorithm (and Maple to keep track of the arithmetic), we find that G = \{g_1 = x-\frac{13}{3}y^3+\frac{13}{3}y, g_2 = y^4-\frac{22}{13}y^2+\frac{9}{13} \} is the reduced Gröbner basis of the ideal I with respect to the lex order induced by x > y. (Proof details in this Maple worksheet (file type .mws) and plain text version here (file type .txt).) Moreover, this basis has precisely the same solution as the original system.

Evidently, g_2 = (y^2-1)(y^2-\frac{9}{13}). From g_2 = 0, then, we have y^2 = 1 or y^2 = \frac{9}{13}. Hence y \in \{1, -1, \frac{3}{\sqrt{13}}, -\frac{3}{\sqrt{13}} \}. Now from g_1 = 0, we have x = \frac{13}{3}y^3 - \frac{13}{3}y; substituting each of our choices for y yields the following four solutions: (0,1), (0,-1), (\frac{-4}{\sqrt{13}}, \frac{3}{\sqrt{13}}), and (\frac{4}{\sqrt{13}}, -\frac{3}{\sqrt{13}}).

Indeed, we can plot these curves in \mathbb{R}^2 as follows.

Use Gröbner bases to solve a system of polynomial equations over the complex numbers

Solve the system of equations x^2-yz = 3, y^2-xz = 4, z^2 - xy = 5 over \mathbb{C}.


First, we define h_1 = x^2-yz-3, h_2 = y^2-xz-4, and h_3 = z^2-xy-5.

Using Maple to help with the arithmetic, we use Buchberger’s algorithm to compute that G = \{g_1 = x+\frac{11}{13}z, g_2 = y-\frac{1}{13}z, g_3 = z^2-\frac{169}{36} \} is the reduced Gröbner basis for I = (h_1, h_2, h_3).

(A Maple worksheet containing the proof details is here (change the file type to .mws) and a plain text version is here (change file type to .txt).)

The original system has precisely the same solutions as our reduced basis. From g_3 = 0, we see that z = \pm\frac{13}{6}. If z = \frac{13}{6}, then g_2 = 0 yields y = \frac{1}{6}, and then g_1 = 0 yields x = -\frac{11}{6}. Likewise, if z = - \frac{13}{6}, we get y = -\frac{1}{6} and x = \frac{11}{6}. Thus the solutions to our system are (-\frac{11}{6}, \frac{1}{6}, \frac{13}{6}) and (\frac{11}{6}, -\frac{1}{6}, -\frac{13}{6}).

Compute the reduced Gröbner basis of an ideal with respect to three different monomial orders

Let I = (x^4-y^4+z^3-1, x^3+y^2+z^2-1). Compute the reduced Gröbner bases of I with respect to the following monomial orders:

  1. lex induced by x > y > z
  2. lex induced by y > z > x
  3. grevlex induced by x > y > y.

I finally broke down and used Maple (a computer algebra system) to keep track of the steps in Buchberger’s algorithm, since for all but the most carefully chosen examples it is excruciating to do by hand.

For the lex order induced by x > y > z, I found the following Gröbner basis for I:

  1. g_1 = x^3+y^2+z^2-1
  2. g_2 = xy^2+xz^2-x+y^4-z^3+1
  3. g_3 = x^2z^4-x^2z^3-2x^2z^2 +2x^2+2xz^6-2xz^5 -6xz^4+2xz^3+8xz^2 -4x+y^8-2y^6z^2+2y^6 +2y^4z^4-2y^4z^3 -4y^4z^2+3y^4+2y^2z^5 -2y^2z^3-4y^2z^2 +4y^2-2z^7 +z^6+4z^5+z^4 -4z^3-2z^2+2
  4. g_4 = xz^8-2xz^7-3xz^6+4xz^5 +8xz^4-4xz^3-8xz^2 +4x-y^10+y^8z^2 -y^8-y^6z^4+3y^6z^3 +2y^6z^2-3y^6+y^4z^6 -3y^4z^5-3y^4z^4+3y^4z^3 +9y^4z^2-7y^4+y^2z^7 -2y^2z^6-2y^2z^5 +2y^2z^4+5y^2z^3 -4y^2z^2-z^9 +2z^8+3z^7-7z^5 -6z^4+5z^3+8z^2-4
  5. g_5 = y^12-3y^8z^3+2y^8 -4y^6z^2+4y^6+3y^4z^6 -6y^4z^4-6y^4z^3+12y^4z^2 -3y^4-4y^2z^6 +12y^2z^4-12y^2z^2+4y^2 -z^9-z^8+7z^6-6z^4 -3z^3+4z^2

The steps used to arrive at this can be found in this Maple worksheet. (After downloading, change the file type to .mws to open in Maple. I understand WordPress not allowing uploads of arbitrary file type, but I would have preferred to use .txt instead. Why on earth would WP allow .docx but not plain text?) If you don’t have access to Maple, you can also see a plain text version of the work. (Change the file type to .txt.)

With respect to the lex order induced by y > z > x, I found the following Gröbner basis:

  1. g_1 = y^2+z^2+x^3-1
  2. g_2 = z^4-z^3+2z^2x^3 -2z^2+x^6-x^4-2x^3+2

The Maple worksheet with the proof details is here (change the file type to .mws) and a read-only version in plain text is here (Change file type to .txt).

With respect to the grevlex order induced by x > y > z, I find the following Gröbner basis.

  1. g_1 = x^3+y^2+z^2-1
  2. g_2 = y^4+xy^2+xz^2-z^3-x+1

A Maple worksheet with proof details is here (change file type to .mws) and a read-only version in plain text is here (change file type to .txt).

Note in particular that Buchberger’s algorithm took far longer to complete using the lex order induced by x > y > z than using the grevlex order induced by x > y > z.

Compute the reduced Gröbner basis of an ideal with respect to a grlex order

Compute the reduced Gröbner basis of I = (x^2+xy^5+y^4, xy^6-xy^3+y^5-y^2, xy^5-xy^2) with respect to the grlex order induced by x > y.


We carry out Buchberger’s algorithm using the given generators.

  1. Let G_1 = \{ g_1 = xy^5+y^4+x^2, g_2 = xy^6+y^5-xy^3-y^2, g_3 = xy^5-xy^2 \}. Evidently, S(g_1,g_2) = xy^3+x^2y+y^2 \equiv xy^3+x^2y+y^2 mod G_1. We append this to G_1 and start over.
  2. Let G_2 = \{ g_1 = xy^5+y^4+x^2, g_2 = xy^6+y^5-xy^3-y^2, g_3 = xy^5-xy^2, g_4 = xy^3+x^2y+y^2 \}. Evidently, S(g_1,g_3) = y^4+xy^2+x^2 \equiv y^4+xy^2+x^2 mod G_2. We append this to G_2 and start over.
  3. Let G_3 = \{ g_1 = xy^5+y^4+x^2, g_2 = xy^6+y^5-xy^3-y^2, g_3 = xy^5-xy^2, g_4 = xy^3+x^2y+y^2, g_5 = y^4+xy^2+x^2 \}. Evidently, S(g_1,g_4) = -x^2y^3+x^2 \equiv x^3y+xy^2+x^2 mod G_3. We append this to G_3 and start over.
  4. Let G_4 = \{ g_1 = xy^5+y^4+x^2, g_2 = xy^6+y^5-xy^3-y^2, g_3 = xy^5-xy^2, g_4 = xy^3+x^2y+y^2, g_5 = y^4+xy^2+x^2, g_6 = x^3y+xy^2+x^2 \}. Evidently, S(g_1,g_6) = -xy^6+x^4 \equiv x^4+x^2y+y^2 mod G_4. We append this to G_4 and start over.
  5. Let G_5 = \{ g_1 = xy^5+y^4+x^2, g_2 = xy^6+y^5-xy^3-y^2, g_3 = xy^5-xy^2, g_4 = xy^3+x^2y+y^2, g_5 = y^4+xy^2+x^2, g_6 = x^3y+xy^2+x^2, g_7 = x^4+x^2y+y^2 \}. Evidently, S(g_2,g_6) = -xy^7-x^3y^3-x^2y^2 \equiv -x^3+y^3 mod G_5. We append x^3-y^3 to G_5 and start over.
  6. Let G_6 = \{ g_1 = xy^5+y^4+x^2, g_2 = xy^6+y^5-xy^3-y^2, g_3 = xy^5-xy^2, g_4 = xy^3+x^2y+y^2, g_5 = y^4+xy^2+x^2, g_6 = x^3y+xy^2+x^2, g_7 = x^4+x^2y+y^2, g_8 = x^3-y^3 \}.
    1. Evidently, S(g_1,g_2) = xy^3+x^2y+y^2 \equiv 0 mod G_6.
    2. Evidently, S(g_1,g_3) = y^4+xy^2+x^2 \equiv 0 mod G_6.
    3. Evidently, S(g_1,g_4) = -x^2y^3+x^2 \equiv 0 mod G_6.
    4. Evidently, S(g_1,g_5) = -x^2y^3-x^3y+y^4+x^2 \equiv 0 mod G_6.
    5. Evidently, S(g_1,g_6) = -xy^6+x^4 \equiv 0 mod G_6.
    6. Evidently, S(g_1,g_7) = -x^2y^6+x^3y^4-y^7+x^5 \equiv 0 mod G_6.
    7. Evidently, S(g_1,g_8) = y^8+x^2y^4=x^4 \equiv 0 mod G_6.
    8. Evidently, S(g_2,g_3) = y^5-y^2 \equiv 0 mod G_6.
    9. Evidently, S(g_2,g_4) = -x^2y^4-xy^3-y^2 \equiv 0 mod G_6.
    10. Evidently, S(g_2,g_5) = -x^2y^4-x^3y^2+y^5-xy^3-y^2 \equiv 0 mod G_6.
    11. Evidently, S(g_2,g_6) = -xy^7-x^3y^3-x^2y^2 \equiv 0 mod G_6.
    12. Evidently, S(g_2,g_7) = -x^2y^7+x^3y^5-x^4y^3-y^7-x^3y^2 \equiv 0 mod G_6.
    13. Evidently, S(g_2,g_8) = y^9+x^2y^5-x^3y^3-x^2y^2 \equiv 0 mod G_6.
    14. Evidently, S(g_3,g_4) = -x^2y^3-y^4-xy^2 \equiv 0 mod G_6.
    15. Evidently, S(g_3,g_5) = -x^2y^3-x^3y-xy^2 \equiv 0 mod G_6.
    16. Evidently, S(g_3,g_6) = -xy^6-x^2y^4-x^3y^2 \equiv 0 mod G_6.
    17. Evidently, S(g_3,g_7) = -x^2y^6-y^7-x^4y^2 \equiv 0 mod G_6.
    18. Evidently, S(g_3,g_8) = y^8-x^3y^2 \equiv 0 mod G_6.
    19. Evidently, S(g_4,g_5) = -x^3+y^3 \equiv 0 mod G_6.
    20. Evidently, S(g_4,g_6) = x^4y-xy^4 \equiv 0 mod G_6.
    21. Evidently, S(g_4,g_7) = x^5y-x^2y^4+x^3y^2-y^5 \equiv 0 mod G_6.
    22. Evidently, S(g_4,g_8) = y^6+x^4y+x^2y^2 \equiv 0 mod G_6.
    23. Evidently, S(g_5,g_6) = x^4y^2-xy^5+x^5-x^2y^3 \equiv 0 mod G_6.
    24. Evidently, S(g_5,g_7) = x^5y^2-x^2y^5+x^6-y^6 \equiv 0 mod G_6.
    25. Evidently, S(g_5,g_8) = y^7+x^4y^2+x^5 \equiv 0 mod G_6.
    26. Evidently, S(g_6,g_7) = x^3-y^3 \equiv 0 mod G_6.
    27. Evidently, S(g_6,g_8) = y^4+xy^2+x^2 \equiv 0 mod G_6.
    28. Evidently, S(g_7,g_8) = xy^3+x^2y+y^2 \equiv 0 mod G_6.

Thus G_6 is a Gröbner basis for I. To reduce G_6, we discard the redundant generators. Letting G = \{g_1 = xy^3+x^2y+y^2, g_2 = y^4+xy^2+x^2, g_3 = x^3-y^3 \}, we see that G is the reduced Gröbner basis for I with respect to the grlex order induced by x > y.

Compute the reduced Gröbner bases of an ideal with respect to two different monomial orders

Compute the reduced Gröbner bases of I = (xy+y^2, x^2y+xy^2+x^2) with respect to the lex orders induced by x > y and y > x.


We first carry out Buchberger’s algorithm using the lex order induced by x > y.

  1. Let G_1 = \{ g_1 = xy+y^2, g_2 = x^2y+x^2+xy^2 \}. Evidently, S(g_1,g_2) = -x^2 \equiv -x^2 mod G_1; so we append x^2 to G_1 and start over.
  2. Let G_2 = \{ g_1 = xy+y^2, g_2 = x^2y+x^2+xy^2, g_3 = x^2 \}. Evidently, S(g_1,g_3) = xy^2 \equiv -y^3 mod G_2; so we append y^3 to G_2 and start over.
  3. Let G_3 = \{ g_1 = xy+y^2, g_2 = x^2y+x^2+xy^2, g_3 = x^2, g_4 = y^3 \}.
    1. Evidently, S(g_1,g_2) = -x^2 \equiv 0 mod G_3.
    2. Evidently, S(g_1,g_3) = -y^3 \equiv 0 mod G_3.
    3. Evidently, S(g_1,g_4) = y^4 \equiv 0 mod G_3.
    4. Evidently, S(g_2,g_3) = x^2+xy^2 \equiv 0 mod G_3.
    5. Evidently, S(g_2,g_4) = x^2y^2+xy^4 \equiv 0 mod G_3.
    6. Evidently, S(g_3,g_4) = 0 \equiv 0 mod G_3.

Thus G_3 is a Gröbner basis for I with respect to the lex order induced by x > y. To reduce G_3, we omit the redundant generator g_2; the remaining basis G = \{ g_1 = xy+y^2, g_2 = x^2, g_3 = y^3 \} is certainly reduced.

Now we carry out Buchberger’s algorithm using the lex order induced by y > x.

  1. Let G_1 = \{ g_1 = y^2+xy, g_2 = xy^2+x^2y+x^2 \}. Evidently, S(g_1,g_2) = -x^2 \equiv -x^2 mod G_1. We append x^2 to G_1 and start over.
  2. Let G_2 = \{ g_1 = y^2+xy, g_2 = xy^2+x^2y+x^2, g_3 = x^2 \}.
    1. Evidently, S(g_1,g_2) = -x^2 \equiv 0 mod G_2.
    2. Evidently, S(g_1,g_3) = x^3y \equiv 0 mod G_2.
    3. Evidently, S(g_2,g_3) = x^3y+x^3 \equiv 0 mod G_2.

Thus G_2 is a Gröbner basis for I with respect to the lex order induced by y > x. To reduce G_2, we omit the redundant generator g_2 and reduce each remaining g_i mod G_2 \setminus \{g_i\}; evidently, G = \{ g_1 = y^2+xy, g_2 = x^2 \} is the reduced Gröbner basis for I with respect to the lex order induced by y > x.

Compute the reduced Gröbner basis of a given ideal

Compute the reduced Gröbner basis of I = (x^2+xy^2, x^2-y^3, y^3-y^2) with respect to the lex order induced by x > y in F[x,y].


We carry out Buchberger’s algorithm on the given generators for I.

  1. Let G_1 = \{ g_1 = x^2+xy^2, g_2 = x^2-y^3, g_3 = y^3-y^2 \}. Evidently, S(g_1,g_2) \equiv xy^2+y^2 mod G_1. We append this to G_1 and start over.
  2. Let G_2 = \{ g_1 = x^2+xy^2, g_2 = x^2-y^3, g_3 = y^3-y^2, g_4 = xy^2+y^2 \}.
    1. S(g_1,g_2): Evidently, S(g_1,g_2) = xy^2+y^2 \equiv 0 mod G_2.
    2. S(g_1,g_3): Evidently, S(g_1,g_3) = x^2y^2+xy^5 \equiv 0 mod G_2.
    3. S(g_1,g_4): Evidently, S(g_1,g_4) = xy^4-xy^2 \equiv 0 mod G_2.
    4. S(g_2,g_3): Evidently, S(g_2,g_3) = x^2y^2-y^6 \equiv 0 mod G_2.
    5. S(g_2,g_4): Evidently, S(g_2,g_4) = -xy^2-y^5 \equiv 0 mod G_2.
    6. S(g_3,g_4): Evidently, S(g_3,g_4) = -xy^2-y^3 \equiv 0 mod G_2.

Thus G_2 is a Gröbner basis for I. To reduce G_2, we omit the redundant generator g_2 and compute g_i mod G_2 \setminus \{g_i\} for each remaining i. Evidently then G = \{ g_1 = x^2-y^2, g_2 = y^3-y^2, g_3 = xy^2+y^2 \} is the reduced Gröbner basis of I with respect to the lex order induced by x > y.