ParametricGroebnerBases

Documentation for ParametricGroebnerBases. This is a package for computing and working with parametric Gröbner bases and Gröbner systems.

Introduction to Gröbner bases

Gröbner bases are a fundamental technique in the study of polynomial ideals over fields. Let $K$ be a field and let $X = (x_1, x_2, \dots, x_n)$ be variables. A Gröbner basis is a finite subset $G \subseteq K[X]$ such that the ideal generated by leading terms of $G$ is equal to the ideal generated by leading terms of the ideal generated by $G$.In other words, $\langle \operatorname{lt}(G) \rangle = \langle \operatorname{lt}(\langle G \rangle) \rangle$. $G$ is called a Gröbner basis of an ideal $I$ if $\langle G \rangle = I$.

Gröbner bases can be used to solve a variety of problems. Let's warm up with an example. Consider the unit circle centered at the origin. Does this circle intersect the line $x = 1$? Of course, the answer is yes, but let's see how Gröbner bases can tell us the same thing.

The unit circle centered at the origin is described by the polynomial equation $x^2 + y^2 - 1 = 0$. The line $x = 1$ is described by $x - 1 = 0$. The two curves intersect if and only if there is a point $(x_0, y_0)$ that satisfies both of these equations. If we compute a Gröbner basis of the ideal generated by those two polynomials, we get the following.

julia> using Nemo
julia> using Groebner

julia> R, (x, y) = QQ[:x, :y]
julia> I = [x^2 + y^2 - 1, x - 1]
julia> groebner(I)
2-element Vector{QQMPolyRingElem}:
 y^2
 x - 1

This gives us an equivalent system, which is much easier to solve. We get $(x_0, y_0) = (1, 0)$, which is what we expected. What if I asked whether the line $x = 3$ intersected the circle? The answer is no. Using Gröbner bases, we get the equivalent system

julia> I = [x^2 + y^2 - 1, x - 3]
julia> groebner(I)
2-element Vector{QQMPolyRingElem}:
 y^2 + 8
 x - 3

Since $y^2 + 8$ has no real solutions, the two curves do not intersect in the real plane. The situation is different in the complex plane, where there is in fact a solution to the system.

Introduction to parametric Gröbner bases

We could ask ourselves for which values of $r$ and $a$ the circle centered at the origin with radius $r$ intersects the line $x - a$. To answer this, we can compute another Gröbner basis.

julia> R, (x, y, r, a) = QQ[:x, :y, :r, :a]
julia> I = [x^2 + y^2 - r^2, x - a]
julia> groebner(I)
2-element Vector{QQMPolyRingElem}:
 y^2 - r^2 + a^2
 x - a

Since the equation $y^2 - r^2 + a^2$ has a real solution if and only if $-r^2 + a^2 \geq 0$, that answers the question. The two lines interesect exctly when $r \geq a$.

However, this doesn't always work. Let's look at a (slightly contrived) example. When does the line $y = a x$ pass through the lines $y = \pm 1$? The answer is, when $a \neq 0$. Let us see if Gröbner bases tells us the same thing. Notice, that the two lines $y = \pm 1$ can be described by the single polynomial equation $y^2 - 1 = 0$.

julia> R, (x, y, a) = QQ[:a, :x, :u]
julia> I = [a*x - y, y^2 - 1]
2-element Vector{QQMPolyRingElem}:
 y^2 - 1
 x*a - y

This is no longer easy to answer by looking at the equations independently. $y^2 - 1$ has the solutions $\pm 1$, and $ax - y$ always has the solution $x = \frac{y}{a}$, except when $a = 0$, then it's $y = 0$. However, we need to consider the two equations together to see that there is no solution for $a = 0$-

To remedy this situation, we have Gröbner systems.

julia> using ParametricGroebnerBases

julia> R, (a, b) = QQ[:a, :b]
julia> S, (x, y) = R[:x, :y]
julia> I = [a*x - y, y^2 - 1]
julia> CGS(I)
2-element Vector{Tuple{Vector{AbstractAlgebra.Generic.MPoly{QQMPolyRingElem}}, Vector{AbstractAlgebra.Generic.MPoly{QQMPolyRingElem}}, Vector{AbstractAlgebra.Generic.MPoly{QQMPolyRingElem}}}}:
 ([], [a], [y^2 - 1, a*x - y])
 ([a], [1], [1])

The way to read this output is line by line. The first line reads "when $a \neq 0$, then the reduced Gröbner basis is given by $\{y^2 - 1, ax - y\}$". In this case, we always have a solution. The second line reads "when $a = 0$ and $1 \neq 0$, then the reduced Gröbner basis is given by $1$". Since there is no point $(x_0, y_0)$ which satisfies the equation $1 = 0$, there is no solution when $a = 0$.