Tutorials

First of all, the Groebner basis is unique! That is, if two sets of polynomials $F_1$ and $F_2$ generate the same ideal (which is actually infinite), then their Groebner bases (which are finite) are the same and can be compared directly

F2 = [
  x^6 + 2*x^3*y^2 + y^4,
  x^3 - x^2*y^3 - x*y^4 + y^2,
  x^2 + x*y
]
# the ideals generated by F and F2 coincide
groebner(F) == groebner(F2)

true

So, Groebner bases provide a unique and finite representation of symbolic systems, combinatorial relations, varieties, and everything else that can be encoded with polynomials.

Moreover, every ideal generated by a finite set of polynomials has a Groebner basis^[1]. Thus, Groebner basis is a universal tool that can be used to draw conclusions about polynomial ideals, as we will see in the next sections.

Gcd & Ref

Computing a Groebner basis for a general system of nonlinear polynomials can be nontrivial. Still, two known algorithms may give us some intuition behind this process.

Groebner basis is Gaussian Elimination

For linear systems, Groebner basis is Row echelon form.

This is due to the fact that in the process of computing a Groebner basis polynomials are repeatedly reduced by each other until a certain condition is met, and in case polynomials are linear, polynomial reduction coincides with Gaussian elimination.

using DynamicPolynomials

@polyvar x y z
system = [
  x - y + z + 1,
  x + 2y + 3z + 4,
  x + y + 5z + 3
]

groebner(system)  # rref

3-element Vector{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Int64}}:
 z
 1 + y
 2 + x

This implies $z = 0, ~y = -1, ~x = -2$ .

Groebner basis is Euclidean Algorithm

For univariate systems, Groebner basis is Greatest common divisor.

This is so since the ideal $I$ generated by univariate $f_1(x), f_2(x)$ is principal: any $h_1f_1 + h_2f_2 \in I$ can be expressed as a multiple of a single polynomial $f(x)$ , where $f(x) = gcd(f_1(x), f_2(x))$ . So, we have the equality of ideals

\{h_1f_1 + h_2f_2\} = \{ hf \} ~~~ | ~~~ h_1,h_2,h ~~\text{are arbitrary}.

| h1,h2,h ~~\text{are arbitrary}. $

@polyvar x
f = (x^2 - 1)^7*(x + 3)*(x - 7)^4
g = (x + 3)*(x + 7)

groebner([f, g])   # gcd by groebner

1-element Vector{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Int64}}:
 3 + x

gcd(f, g)          # usual gcd

3 + x

Naturally, the same holds for several input polynomials:

groebner(f_1, \ldots, f_m) = gcd(gcd(gcd(f_1, f_2), \ldots), f_m)

So, you can compute the GCD of several polynomials at once using Groebner.jl (but you probably should not)!

We take this chance to demonstrate that Groebner.jl has only a small runtime overhead over the classic GCD implementation.

With DynamicPolynomials.jl:

h = (x + 3)^5

@btime gcd(gcd($f, $g), $h)

  69.440 μs (939 allocations: 58.41 KiB)
3 + x

With Groebner.jl:

F = [f, g, h]
@btime groebner($F)

  165.428 μs (2218 allocations: 236.62 KiB)
1-element Vector{DynamicPolynomials.Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, MultivariatePolynomials.Graded{MultivariatePolynomials.LexOrder}, Int64}}:
 3 + x

Variable Elimination

One can also use Groebner bases to eliminate indeterminates from equations. A layer of theory lies behind this topic, however, the main simple observation here is that

If $G$ is a Groebner basis of ideal $I$ with variables ordered as $x > y > z$ , then

G \cap R[y, z]

is a Groebner basis for $I_{y, z}~ =~ I \cap R[y, z]$ .

Here, one can see $I_{y, z}$ as a fair geometric projection of $I$ onto the last two variables $y, z$ .

For example, consider polynomial set $F$ that encodes some complicated algebraic variety in 3D:

_, (x, y, z) = QQ["x", "y", "z"]

F = [x + y^2 + z - 1,
     x + y + z^2 - 1]

2-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 x + y^2 + z - 1
 x + y + z^2 - 1

Let's try to simplify it a bit. Now, the Groebner basis of $F$ is

G = groebner(F)

2-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 y^2 - y - z^2 + z
 x + y + z^2 - 1

Notice that the first polynomial in G does not contain x! The observation implies that G[1] is a Groebner basis of $I_{y, z}$ , meaning the solutions of

y^2 - y - z^2 + z = 0

are exactly the projection of solutions of $F$ to variables $y$ and $z$ .

With this technique, one can split a complicated variety in parts, and treat each part separately.

Curve Implicitization

Moreover, Groebner.jl can help converting a parametric curve representation to an implicit one. Say, we have a parametrization of the circle on a plane

\left\{\begin{aligned} x = \frac{1 - t^2}{1 + t^2},\\ y = \frac{2t}{1 + t^2} \end{aligned}\right.

and we want to produce an implicit curve equation in $x, y$ and without t.

First, let's clear denominators

\left\{\begin{aligned} t^2y - 2t + y = 0,\\ t^2x + t^2 + x - 1 = 0 \end{aligned}\right.

The Groebner basis of the above with $t > x > y$ in lexicographic order is

using AbstractAlgebra
_, (t, x, y) = polynomial_ring(QQ, ["t", "x", "y"], internal_ordering=:lex)

groebner([t^2*y - 2t + y, t^2*x + t^2 + x - 1])

3-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 x^2 + y^2 - 1
 t*y + x - 1
 t*x + t - y

There, the only two-variable equation in $x, y$ is

x^2 + y^2 - 1 = 0

Hence, $x^2 + y^2 - 1 = 0$ is an implicit formula we were looking for. Indeed, for any $t$ every $(x, y)$ lies on the circle as expected.

Solving Systems

Groebner bases can be used to solve systems exactly, given the number of solutions is finite.

In this section we assume the usual lexicographic ordering of variables and consider the case with three variables (i.e, $x > y > z$ ). Same method generalizes naturally for $n$ indeterminates.

_, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"], internal_ordering=:lex);

To illustrate the method, we consider the following polynomial system to solve

system = [x + y + z,
          x*y + x*z + y*z,
          x*y*z - 1];

Recall that the solutions of a system coincide with zeros of a Groebner basis of this system (since the original system and its basis are equivalent). Let's calculate a Groebner basis then!

groebner(system)

3-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 z^3 - 1
 y^2 + y*z + z^2
 x + y + z

Notice that z^3 - 1 in the basis is a univariate equation. Solving it over the desired domain one obtains some roots z = ....

Then, substitute z into the second equation y^2 + y*z + z^2, which in turn becomes univariate in variable y. Solving it and obtaining zeros in y, one moves to the next equation in the basis.

Substituting each y and z to x + y + z, one easily produces a single solution in x for each solution in y, z.

Solving general polynomial systems (assuming the set of solutions is finite) using Groebner bases relies on the same technique:

In the Groebner basis there is a univariate equation;
Solve it, and substitute found roots into other equations;
Go to 1.

Integer Programming

⚠ Note

This cool example is adapted from Christopher Hillar (MSRI) presentation on Groebner Bases.

Integer programming is the problem of solving linear equations where the solution must be in non-negative integers and should minimize a given "cost function".

Our strategy here is to convert the integer programming problem into a problem about polynomials, and then solve this polynomial problem using Groebner bases.

The classic example problem is the following. Say we have coins of 4 nominal values: pennies $P$ , nickels $N$ , dimes $D$ , and quarters $Q$ . We want to pick a collection that amounts to 117 using the least number of coins possible.

In other words, minimize $P + N + D + Q$ subject to $P, N, D, Q \ge 0$ and

P + 5N + 10D + 25Q = 117

The minimal integer solution is $(P, N, D, Q) = (2, 1, 1, 4)$ , let's try to find it with Groebner bases.

First, we will represent each collection of coins by a polynomial $p^an^bd^cq^d$ in variables $p, n, d, q$ (e.g., 2 pennies with 5 dimes is $p^2d^5$ ).

We also know that $p^5$ is the same as $n$ , $p^{10}$ is the same as $d$ , and so on. The full set of constraints is

F = \{p^5 - n, p^10 - d, p^25 - q\}

The idea is to construct a more useful set of constraints using a Groebner basis

_, (p, n, d, q) = polynomial_ring(QQ, ["p","n","d","q"], internal_ordering=:deglex)

F = [p^5 - n, p^10 - d, p^25 - q]   # initial constraints

G = groebner(F)   # more nice and useful constraints

4-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 n^2 - d
 d^3 - n*q
 n*d^2 - q
 p^5 - n

⚠ Note

Notice that we construct polynomials in deglex ordering, instead of the default lex.

These new constraints express a useful set of replacement (rewrite) rules. E.g., the expression d^3 - n*q in the basis translates to: replace 3 dimes with a nickel and a quarter.

Now, we take an arbitrary solution (not necessarily minimal), say $p^{17}n^{10}d^5$ , and compute the normal form w.r.t. $G$

normalform(G, p^17*n^10*d^5)

p^2*n*d*q^4

to obtain the minimial solution $(P, N, D, Q) = (2, 1, 1, 4)$ .

Graph Coloring

In graph theory, Graph coloring is a problem of assigning a color to each vertex of a graph in a way that no two neighboring vertices the same color.

The common hard question is the existence of a proper coloring with $k$ colors for $k > 2$ . In this section, we will show how the question can be tackled using the Groebner bases approach.

The approach is to

Establish relation between k-coloring and system of polynomial equations
Solve the system or prove unsolvable

There are two types of polynomials forming a typical graph coloring system.

First, for each vertex $j$ in a graph we assign variable $x_j$ . To fix that each particular vertex $j$ has a color we construct vertex polynomials of form

x_j^k - 1 = 0

for each vertex $j$ . Then one color out of $k$ is represented as one of the $k$ -th roots of unity.

Secondly, we add edge polynomials

\frac{x_i^k - x_j^k}{x_i - x_j}

for each $i \rightarrow j$ in edges to ensure two neighboring vertices do not share the same color. Such polynomial disallows that colors $x_i$ and $x_j$ for two neighbors $i$ and $j$ coincide. Finally, solutions of a system constructed this way correspond to proper k-colorings in a 1 to 1 relation.

For example, the coloring system for k=3 in the graph above must contain vertex polynomials

\{ x_1^3 - 1,~ x_2^3 - 1,~ x_3^3 - 1,~ x_4^3 - 1 \}

and a bunch of edge polynomials. Note that adding an edge polynomial $\frac{x_i^3 - x_j^3}{x_i - x_j}$ to a system is equivalent to adding $x_i^2 + x_ix_j + x_j$ to it.

Now consider the resulting coloring system for the graph from the picture

_, (x1, x2, x3, x4) = QQ["x1","x2","x3","x4"]

coloring_system = [
  x1^3 - 1, x2^3 - 1, x3^3 - 1, x4^3 - 1,
  x1^2 + x1*x2 + x2^2,
  x1^2 + x1*x3 + x3^2,
  x1^2 + x1*x4 + x4^2,
  x2^2 + x2*x3 + x3^2,
  x3^2 + x3*x4 + x4^2
]

groebner(coloring_system)

4-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
 x4^3 - 1
 x3^2 + x3*x4 + x4^2
 x2 - x4
 x1 + x3 + x4

From the x2 - x4 equation in the basis we understand 2nd and 4th vertices should be of the same color. It only remains to assign colors to the remaining vertices

[1]	See, for example, Theorem 2.4.6 in the wonderful book "Computational Commutative Algebra 1" by Martin Kreuzer and Lorenzo Robbiano https://link.springer.com/book/10.1007/978-3-540-70628-1.

Groebner.jl