## 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 $n$th 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$.