The following contains a series of tutorials that illustrate interesting usecases of Groebner bases provided with the code from Groebner.jl.
In particular, these notes are intended as a non-rigorus introduction to the notion of Groebner bases.
We also refer to the Tutorial by Michael Stillman that covers similar examples but in much more detail.
In short, Groebner basis is a good representation of infinite information.
Let us recall some theory from an algebra course. A set of polynomials is said to generate the ideal if
Notice that can be infinite. Informally, the ideal encodes all algebraic relations between polynomials .
A Groebner basis of is a nicer set of generators for . For example, let
using AbstractAlgebra
_, (x, y) = QQ["x", "y"]
F = [x^3 + y^2, x*y + x^2]
2-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
x^3 + y^2
x^2 + x*y
In this example, the Groebner basis of F
is
using Groebner
groebner(F)
3-element Vector{AbstractAlgebra.Generic.MPoly{Rational{BigInt}}}:
y^3 - y^2
x*y^2 + y^2
x^2 + x*y
But why is it nice?
First of all, the Groebner basis is unique! That is, if two sets of polynomials and 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.
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.
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 .
For univariate systems, Groebner basis is Greatest common divisor.
This is so since the ideal generated by univariate is principal: any can be expressed as a multiple of a single polynomial , where . So, we have the equality of ideals
| 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:
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
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 is a Groebner basis of ideal with variables ordered as , then
is a Groebner basis for .
Here, one can see as a fair geometric projection of onto the last two variables .
For example, consider polynomial set 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 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 , meaning the solutions of
are exactly the projection of solutions of to variables and .
With this technique, one can split a complicated variety in parts, and treat each part separately.
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
and we want to produce an implicit curve equation in and without t.
First, let's clear denominators
The Groebner basis of the above with 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 is
Hence, is an implicit formula we were looking for. Indeed, for any every lies on the circle as expected.
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, ). Same method generalizes naturally for 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 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 , nickels , dimes , and quarters . We want to pick a collection that amounts to 117 using the least number of coins possible.
In other words, minimize subject to and
The minimal integer solution is , let's try to find it with Groebner bases.
First, we will represent each collection of coins by a polynomial in variables (e.g., 2 pennies with 5 dimes is ).
We also know that is the same as , is the same as , and so on. The full set of constraints is
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
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 , and compute the normal form w.r.t.
normalform(G, p^17*n^10*d^5)
p^2*n*d*q^4
to obtain the minimial solution .
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 colors for . 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 in a graph we assign variable . To fix that each particular vertex has a color we construct vertex polynomials of form
for each vertex . Then one color out of is represented as one of the -th roots of unity.
Secondly, we add edge polynomials
for each in edges to ensure two neighboring vertices do not share the same color. Such polynomial disallows that colors and for two neighbors and 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
and a bunch of edge polynomials. Note that adding an edge polynomial to a system is equivalent to adding 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. |