Gröbner/Standard Bases Over Fields
We fix our notation in the context of standard (Gröbner) bases and present relevant OSCAR functions.
Let $K[x] = K[x_1, \dots, x_n]$ be a polynomial ring over a field $K$, and let $>$ be a monomial ordering on $\text{Mon}_n(x)$.
Given a polynomial $f\in K[x]\setminus \{0\}$, write $f$ as the sum of its nonzero terms as follows:
\[f = a_\alpha x^\alpha + a_{\beta_1} x^{\beta_1} + \dots + a_{\beta_s} x^{\beta_s},\quad x^\alpha > x^{\beta_1} > \dots > x^{\beta_s} .\]
Then, with respect to $>$, we refer to $\text{LT}_>(f) = a_\alpha x^\alpha$, $\text{LM}_>(f) = x^\alpha$, $\text{LE}_>(f) = \alpha$, $\text{LC}_>(f) = a_\alpha$, and $\text{tail}_>(f) = f - \text{LT}_>(f)$ as the leading term, the leading monomial, the leading exponent, the leading coefficient, and the tail of $f$, respectively.
Next note that the set
\[U_>:= \{u\in K[x]\setminus \{0\} \mid {\text{LM}}_>(u)=1 \}\]
is a multiplicatively closed subset of $K[x]$. Consider the localization
\[K[x]_>:= K[x][U^{-1}] = \left\{ \frac{f}{u} \:\bigg|\: f \in K[x], \, u\in U_>\right\}.\]
Then $K[x]\subseteq K[x]_>\subseteq K[x]_{\langle x \rangle},$ where $K[x]_{\langle x \rangle}$ is the localization of $K[x] $ at the maximal ideal $\langle x \rangle .$ Moreover,
$K[x] = K[x]_>$ iff $>$ is global, and
$K[x]_> = K[x]_{\langle x \rangle}$ iff $>$ is local.
Extending the notation introduced for polynomials, let now $f\in K[x]_>\setminus \{0\}$. Choose $u\in U_>$ such that $uf\in K[x]$. Then, with respect to $>$, the leading term of $f$ is defined to be $\text{LT}_>(f) = \text{LT}_>(uf)$ (this definition is independent of the choice of $u$). The leading monomial $\text{LM}_>(f)$, the leading exponent $\text{LE}_>(f)$, the leading coefficient $\text{LC}_>(f)$, and the tail $\text{tail}_>(f)$ of $f$ are defined similarly.
Given a monomial ordering $>$ on a free $K[x]$-module $F = K[x]^p$ with basis $e_1, \dots, e_p$, the above notation extends naturally to elements of $K[x]^p$ and $K[x]_>^p$, respectively. There is one particularity: Given an element $f = K[x]^p\setminus \{0\}$ with leading term $\text{LT}(f) = x^\alpha e_i$, we write $\text{LE}_>(f) = (\alpha, i)$.
Default Orderings
The OSCAR functions discussed in this section depend on a monomial ordering which is entered as a keyword argument. Given a polynomial ring $R$, the default_ordering for this is degrevlex except if $R$ is $\mathbb Z$-graded with positive weights. Then the corresponding wdegrevlex ordering is used. Given a free $R$-module $F$, the default_ordering is default_ordering(R)*lex(gens(F)).
Here are some illustrating OSCAR examples:
Examples
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])
julia> default_ordering(R)
degrevlex([x, y, z])
julia> F = free_module(R, 2)
Free module of rank 2 over Multivariate polynomial ring in 3 variables over QQ
julia> default_ordering(F)
degrevlex([x, y, z])*lex([gen(1), gen(2)])
julia> S, _ = grade(R, [1, 2, 3])
(Graded multivariate polynomial ring in 3 variables over QQ, MPolyDecRingElem{QQFieldElem, QQMPolyRingElem}[x, y, z])
julia> default_ordering(S)
wdegrevlex([x, y, z], [1, 2, 3])Monomials, Terms, and More
Here are examples which indicate how to recover monomials, terms, and more from a given polynomial.
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[x, y, z])
julia> f = 3*z^3+2*x*y+1
2*x*y + 3*z^3 + 1
julia> terms(f)
terms iterator of 3*z^3 + 2*x*y + 1
julia> collect(ans)
3-element Vector{QQMPolyRingElem}:
3*z^3
2*x*y
1
julia> monomials(f, ordering = lex(R))
monomials iterator of 2*x*y + 3*z^3 + 1
julia> coefficients(f)
coefficients iterator of 3*z^3 + 2*x*y + 1
julia> exponents(f, ordering = neglex(R))
exponents iterator of 1 + 3*z^3 + 2*x*y
julia> coefficients_and_exponents(f)
coefficients and exponents iterator of 3*z^3 + 2*x*y + 1
julia> collect(ans)
3-element Vector{Tuple{QQFieldElem, Vector{Int64}}}:
(3, [0, 0, 3])
(2, [1, 1, 0])
(1, [0, 0, 0])
julia> leading_term(f)
3*z^3
julia> leading_monomial(f, ordering = lex(R))
x*y
julia> leading_exponent(f, ordering = neglex(R))
3-element Vector{Int64}:
0
0
0
julia> leading_coefficient(f)
3
julia> tail(f)
2*x*y + 1julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> F = free_module(R, 3)
Free module of rank 3 over Multivariate polynomial ring in 2 variables over QQ
julia> f = (5*x*y^2-y^10+3)*F[1]+(4*x^3+2*y) *F[2]+16*x*F[3]
(5*x*y^2 - y^10 + 3)*e[1] + (4*x^3 + 2*y)*e[2] + 16*x*e[3]
julia> default_ordering(F)
degrevlex([x, y])*lex([gen(1), gen(2), gen(3)])
julia> collect(terms(f))
6-element Vector{FreeModElem{QQMPolyRingElem}}:
-y^10*e[1]
4*x^3*e[2]
5*x*y^2*e[1]
16*x*e[3]
2*y*e[2]
3*e[1]
julia> collect(terms(f, ordering = lex(F)*lex(R)))
6-element Vector{FreeModElem{QQMPolyRingElem}}:
5*x*y^2*e[1]
-y^10*e[1]
3*e[1]
4*x^3*e[2]
2*y*e[2]
16*x*e[3]
julia> tail(f)
(5*x*y^2 + 3)*e[1] + (4*x^3 + 2*y)*e[2] + 16*x*e[3]
julia> leading_exponent(f)
([0, 10], 1)
julia> leading_exponent(f, ordering = lex(F)*lex(R))
([1, 2], 1)Division With Remainder
The computation of Gröbner (standard) bases relies on multivariate division with remainder which is interesting in its own right. If a monomial ordering $>$ is given, the basic idea is to mimic Euclidean division with remainder, allowing more than one divisor: At each step of the resulting process, this amounts to removing the leading term of the intermediate dividend, using the leading term of some divisor by which it is divisible. In its basic form, the process works well if $>$ is global, but may not terminate for local and mixed orderings. In the latter case, Mora's division algorithm, which relies on a more restricted selection strategy for the divisors to be used, comes to our rescue.
We discuss this in more detail:
First suppose that $>$ is global and let polynomials $g\in K[x]$ and $f_1, \dots, f_r\in K[x]\setminus \{0\}$ be given. In this situation, multivariate division with remainder allows us to compute expressions
\[g = q_1f_1+\dots q_rf_r + h, \; h\in K[x], \;\text{ all }\; q_i \in K[x]\]
such that:
- $\text{LM}_>(g) \ge \text{LM}_>(q_if_i)$ whenever both sides are nonzero.
- If $h$ is nonzero, then $\text{LM}_>(h)$ is not divisible by any $\text{LM}_>(f_i)$.
Each such expression is called a standard representation for $g$ with quotients $q_i$ and remainder $h$ (on division by the $f_i$, with respect to $>$). If, at each step of the division process, we allow to remove some term of the current dividend instead of just focusing on its leading term, then the algorithm will return a standard expression in which the remainder is fully reduced. That is, $h$ satisfies the stronger condition below:
- If $h$ is nonzero, then no term of $h$ is divisible by any $\text{LM}_>(f_i)$.
Without restrictions on $>$, let elements $g\in K[x]_>$ and $f_1, \dots, f_r\in K[x]\setminus \{0\}$ be given. In this situation, Mora division with remainder allows us to compute expressions
\[ug = q_1f_1+\dots q_rf_r + h, \; h\in K[x]_>, \;\text{ all }\; q_i \in K[x]_>\]
such that:
- $u$ is a unit of $K[x]_>$, that is, $\text{LM}_>(u)=1$.
- $\text{LM}_>(g) \ge \text{LM}_>(q_if_i)$ whenever both sides are nonzero.
- If $h$ is nonzero, then $\text{LM}_>(h)$ is not divisible by any $\text{LM}_>(f_i)$.
Each such expression is called a weak standard representation for $g$ with quotients $q_i$ and remainder $h$ (on division by the $f_i$, with respect to $>$). If $g\in K[x]$, we speak of a polynomial weak standard representation if $u$ and the $q_i$ are elements of $K[x].$ Using power series expansions, it makes still sense to speak of fully reduced remainders. However, even if we start from polynomial data, such remainders may not be computable (in finitely many steps).
Given a monomial ordering $>$ on a free $K[x]$-module $F = K[x]^p$ with basis $e_1, \dots, e_p$, the above notation and the division algorithms extend naturally to $K[x]^p$ and $K[x]_>^p$, respectively.
The OSCAR functions discussed below compute standard representations and polynomial weak standard representations, respectively.
reduce — Methodreduce(g::T, F::Union{Vector{T}, IdealGens{T}};
ordering::MonomialOrdering = default_ordering(g)), complete_reduction::Bool = false) where T <: MPolyRingElemIf ordering is global, return the remainder in a standard representation for g on division by the polynomials in F with respect to ordering. Otherwise, return the remainder in a weak standard representation for g on division by the polynomials in F with respect to ordering.
reduce(G::Vector{T}, F::Union{Vector{T}, IdealGens{T}};
ordering::MonomialOrdering = default_ordering(parent(G[1])), complete_reduction::Bool = false) where T <: MPolyRingElemReturn a Vector which contains, for each element g of G, a remainder as above.
The returned remainders are fully reduced if complete_reduction is set to true and ordering is global.
The reduction strategy behind the reduce function and the reduction strategy behind the functions reduce_with_quotients and reduce_with_quotients_and_unit differ. As a consequence, the computed remainders may differ.
Examples
julia> R, (z, y, x) = polynomial_ring(QQ, ["z", "y", "x"]);
julia> f1 = y-x^2; f2 = z-x^3;
julia> g = x^3*y-3*y^2*z^2+x*y*z;
julia> reduce(g, [f1, f2], ordering = lex(R))
-3*x^10 + x^6 + x^5julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> f1 = x^2+x^2*y; f2 = y^3+x*y*z; f3 = x^3*y^2+z^4;
julia> g = x^3*y+x^5+x^2*y^2*z^2+z^6;
julia> reduce(g, [f1, f2, f3], ordering = lex(R))
x^5 + x^3*y + x^2*y^2*z^2 + z^6
julia> reduce(g, [f1,f2, f3], ordering = lex(R), complete_reduction = true)
x^5 - x^3 + y^6 + z^6reduce_with_quotients — Methodreduce_with_quotients(g::T, F::Union{Vector{T}, IdealGens{T}};
ordering::MonomialOrdering = default_ordering(parent(g)), complete_reduction::Bool = false) where T <: MPolyRingElemIf ordering is global, return the quotients and the remainder in a standard representation for g on division by the polynomials in F with respect to ordering. Otherwise, return the quotients and the remainder in a weak standard representation for g on division by the polynomials in F with respect to ordering.
reduce_with_quotients(G::Vector{T}, F::Union{Vector{T}, IdealGens{T}};
ordering::MonomialOrdering = default_ordering(parent(G[1])), complete_reduction::Bool = false) where T <: MPolyRingElemReturn a Vector which contains, for each element g of G, quotients and a remainder as above.
The returned remainders are fully reduced if complete_reduction is set to true and ordering is global.
Examples
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> f1 = x^2+x^2*y; f2 = y^3+x*y*z; f3 = x^3*y^2+z^4;
julia> g = x^3*y+x^5+x^2*y^2*z^2+z^6;
julia> Q, h = reduce_with_quotients(g, [f1,f2, f3], ordering = lex(R));
julia> h
x^5 - x^3 + y^6 + z^6
julia> g == Q[1]*f1+Q[2]*f2+Q[3]*f3+h
truereduce_with_quotients_and_unit — Methodreduce_with_quotients_and_unit(g::T, F::Union{Vector{T}, IdealGens{T}};
ordering::MonomialOrdering = default_ordering(parent(g)), complete_reduction::Bool = false) where T <: MPolyRingElemReturn the unit, the quotients and the remainder in a weak standard representation for g on division by the polynomials in F with respect to ordering.
reduce_with_quotients_and_unit(G::Vector{T}, F::Union{Vector{T}, IdealGens{T}};
ordering::MonomialOrdering = default_ordering(parent(G[1])), complete_reduction::Bool = false) where T <: MPolyRingElemReturn a Vector which contains, for each element g of G, a unit, quotients, and a remainder as above.
The returned remainders are fully reduced if complete_reduction is set to true and ordering is global.
The reduction strategy behind the reduce function and the reduction strategy behind the functions reduce_with_quotients and reduce_with_quotients_and_unit differ. As a consequence, the computed remainders may differ.
Examples
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> f1 = x^2+x^2*y; f2 = y^3+x*y*z; f3 = x^3*y^2+z^4;
julia> g = x^3*y+x^5+x^2*y^2*z^2+z^6;
julia> u, Q, h =reduce_with_quotients_and_unit(g, [f1,f2, f3], ordering = lex(R));
julia> u
[1]
julia> G = [g, x*y^3-3*x^2*y^2*z^2];
julia> U, Q, H = reduce_with_quotients_and_unit(G, [f1, f2, f3], ordering = negdegrevlex(R));
julia> U
[y + 1 0]
[ 0 y + 1]
julia> Q
[ x^3 - x*y^2*z^2 + x*y + y^2*z^2 0 y*z^2 + z^2]
[x*y*z^2 + y^3*z - 3*y^2*z^2 - y*z -x^2*y*z - x^2*z + x*y + x 0]
julia> H
2-element Vector{QQMPolyRingElem}:
0
0
julia> U*G == Q*[f1, f2, f3]+H
trueComputing Gröbner/Standard Bases
Still keeping the notation introduced at the beginning of this section, let $G$ be a subset of $K[x]_>$. Then the leading ideal of $G$ is the ideal of $K[x]$ defined by
\[\text{L}_>(G)=\langle \text{LT}_>(g) \mid g\in G\setminus\{0\}\rangle\subset K[x].\]
A finite subset $G$ of an ideal $I\subset K[x]_>$ is called a standard basis of $I$ (with respect to $>$) if $\text{L}_>(G) = \text{L}_>(I)$. A finite subset of $K[x]_>$ is a standard basis if it is a standard basis of the ideal it generates. A standard basis with respect to a global monomial ordering is also called a Gröbner basis.
Every standard basis of $I$ generates $I$.
Gröbner bases (standard bases) can be computed using Buchberger's algorithm (Buchberger's algorithm as enhanced by Mora).
We call a standard basis $G = \{g_1,\dots, g_r\}\subset K[x]_>\setminus \{0\}$ minimal if $\text{LM}_>(g_i)\neq \text{LM}_>(g_j)$ for $i\neq j$.
The definition of minimal above deviates from the definition in most textbooks as we do not ask that the leading coefficients of the standard basis elements are 1.
The standard bases returned by OSCAR are always minimal in the sense above.
We call a standard basis $G = \{g_1,\dots, g_r\}$ with respect to a global monomial ordering reduced if it is minimal and no term of $g_i$ is divisible by $\text{LM}_>(g_j)$, for $i\neq j$. Using power series expansions, we may extend this notion to local and mixed orderings. However, while reduced standard bases can be computed in the global case, they may not be computable (in finitely many steps) in the other cases.
Given a monomial ordering $>$ on a free $K[x]$-module $F = K[x]^p$ with basis $e_1, \dots, e_p$, the above notation and results extend naturally to submodules of $K[x]_>^p$.
Here are the relevant OSCAR functions for computing Gröbner and standard bases. The elements of a computed basis can be retrieved by using the elements function or its alias gens.
groebner_basis — Methodgroebner_basis(I::MPolyIdeal;
ordering::MonomialOrdering = default_ordering(base_ring(I)),
complete_reduction::Bool = false, algorithm::Symbol = :buchberger)If ordering is global, return a Gröbner basis of I with respect to ordering.
The keyword algorithm can be set to
:buchberger(implementation of Buchberger's algorithm in Singular),:hilbert(implementation of a Hilbert driven Gröbner basis computation in Singular),:fglm(implementation of the FGLM algorithm in Singular), and:f4(implementation of Faugère's F4 algorithm in the msolve package).
See the description of the functions groebner_basis_hilbert_driven, fglm, and f4 in the OSCAR documentation for some more details and for restrictions on the input data when using these versions of the standard basis algorithm.
The returned Gröbner basis is reduced if complete_reduction = true.
Examples
julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> I = ideal(R, [y-x^2, z-x^3]);
julia> G = groebner_basis(I)
Gröbner basis with elements
1 -> y^2 - x*z
2 -> x*y - z
3 -> x^2 - y
with respect to the ordering
degrevlex([x, y, z])
julia> elements(G)
3-element Vector{QQMPolyRingElem}:
-x*z + y^2
x*y - z
x^2 - y
julia> elements(G) == gens(G)
true
julia> groebner_basis(I, ordering = lex(R))
Gröbner basis with elements
1 -> y^3 - z^2
2 -> x*z - y^2
3 -> x*y - z
4 -> x^2 - y
with respect to the ordering
lex([x, y, z])julia> R, (x, y) = graded_polynomial_ring(QQ, ["x", "y"], [1, 3]);
julia> I = ideal(R, [x*y-3*x^4,y^3-2*x^6*y]);
julia> groebner_basis(I)
Gröbner basis with elements
1 -> 3*x^4 - x*y
2 -> 2*x^3*y^2 - 3*y^3
3 -> x*y^3
4 -> y^4
with respect to the ordering
wdegrevlex([x, y], [1, 3])julia> R, (x, y, z) = polynomial_ring(QQ, ["x", "y", "z"]);
julia> V = [3*x^3*y+x^3+x*y^3+y^2*z^2, 2*x^3*z-x*y-x*z^3-y^4-z^2,
2*x^2*y*z-2*x*y^2+x*z^2-y^4];
julia> I = ideal(R, V);
julia> G = groebner_basis(I, ordering = lex(R), algorithm = :fglm);
julia> length(G)
8
julia> total_degree(G[8])
34
julia> leading_coefficient(G[8])
-91230304237130414552564280286681870842473427917231798336639893796481988733936505735341479640589040146625319419037353645834346047404145021391726185993823650399589880820226804328750standard_basis — Methodstandard_basis(I::MPolyIdeal; ordering::MonomialOrdering = default_ordering(base_ring(I)),
complete_reduction::Bool = false, algorithm::Symbol = :buchberger)Return a standard basis of I with respect to ordering.
The keyword algorithm can be set to
:buchberger(implementation of Buchberger's algorithm in Singular),:f4(implementation of Faugère's F4 algorithm in the msolve package),:fglm(implementation of the FGLM algorithm in Singular),:hc(implementation of Buchberger's algorithm in Singular trying to first compute the highest corner modulo some prime), and:hilbert(implementation of a Hilbert driven Gröbner basis computation in Singular).
See the description of the functions groebner_basis_hilbert_driven, fglm, and f4 in the OSCAR documentation for some more details and for restrictions on the input data when using these versions of the standard basis algorithm.
The returned standard basis is reduced if ordering is global and complete_reduction = true.
Examples
julia> R,(x,y) = polynomial_ring(QQ, ["x","y"]);
julia> I = ideal([x*(x+1), x^2-y^2+(x-2)*y]);
julia> standard_basis(I, ordering = negdegrevlex(R))
Standard basis with elements
1 -> x
2 -> y
with respect to the ordering
negdegrevlex([x, y])Gröbner Bases with transformation matrix
groebner_basis_with_transformation_matrix — Methodgroebner_basis_with_transformation_matrix(I::MPolyIdeal;
ordering::MonomialOrdering = default_ordering(base_ring(I)),
complete_reduction::Bool=false)Return a pair G, T, say, where G is a Gröbner basis of I with respect to ordering, and T is a transformation matrix from gens(I) to G. That is, gens(I)*T == G.
The returned Gröbner basis is reduced if complete_reduction = true.
Examples
julia> R,(x,y) = polynomial_ring(QQ,["x","y"]);
julia> I = ideal([x*y^2-1,x^3+y^2+x*y]);
julia> G, T = groebner_basis_with_transformation_matrix(I)
(Gröbner basis with elements
1 -> x*y^2 - 1
2 -> x^3 + x*y + y^2
3 -> y^4 + x^2 + y
with respect to the ordering
degrevlex([x, y]), [1 0 -x^2-y; 0 1 y^2])
julia> gens(I)*T == gens(G)
truestandard_basis_with_transformation_matrix — Methodstandard_basis_with_transformation_matrix(I::MPolyIdeal;
ordering::MonomialOrdering = default_ordering(base_ring(I)),
complete_reduction::Bool=false)Return a pair G, T, say, where G is a standard basis of I with respect to ordering, and T is a transformation matrix from gens(I) to G. That is, gens(I)*T == G.
The returned Gröbner basis is reduced if ordering is a global monomial odering and complete_reduction = true.
Examples
julia> R,(x,y) = polynomial_ring(QQ,["x","y"]);
julia> I = ideal([x*y^2-1,x^3+y^2+x*y]);
julia> G, T = standard_basis_with_transformation_matrix(I, ordering=neglex(R))
(Standard basis with elements
1 -> 1 - x*y^2
with respect to the ordering
neglex([x, y]), [-1; 0])
julia> gens(I)*T == gens(G)
trueGröbner Basis Conversion Algorithms
The performance of Buchberger's Gröbner basis algorithm is sensitive to the choice of monomial ordering. A Gröbner basis computation with respect to a less favorable ordering such as lex may easily run out of time or memory even in cases where a Gröbner basis computation with respect to a more efficient ordering such as degrevlex is very well feasible. Gröbner basis conversion algorithms and the Hilbert driven Buchberger algorithm discussed subsequently take their cue from this observation.
Gröbner basis conversion algorithms proceed along the following lines:
- Given an ideal $I$ of a multivariate polynomial ring over a field and a slow
destination_ordering, compute a Gröbner basis for $I$ with respect to an appropriately chosen faststart_ordering. - Convert the result to a Gröbner basis with respect to the given slow
destination_ordering.
The algorithms differ in how they perform the conversion.
The FGLM Algorithm
fglm — Methodfglm(I::MPolyIdeal; start_ordering::MonomialOrdering = default_ordering(base_ring(I)),
destination_ordering::MonomialOrdering)Given a zero-dimensional ideal I, return the reduced Gröbner basis of I with respect to destination_ordering.
Both start_ordering and destination_ordering must be global and the base ring of I must be a polynomial ring over a field.
The function implements the Gröbner basis conversion algorithm by Faugère, Gianni, Lazard, and Mora. See [FGLM93] for more information.
Examples
julia> R, (a, b, c, d, e) = polynomial_ring(QQ, ["a", "b", "c", "d", "e"]);
julia> f1 = a+b+c+d+e;
julia> f2 = a*b+b*c+c*d+a*e+d*e;
julia> f3 = a*b*c+b*c*d+a*b*e+a*d*e+c*d*e;
julia> f4 = b*c*d+a*b*c*e+a*b*d*e+a*c*d*e+b*c*d*e;
julia> f5 = a*b*c*d*e-1;
julia> I = ideal(R, [f1, f2, f3, f4, f5]);
julia> G = fglm(I, destination_ordering = lex(R));
julia> length(G)
8
julia> total_degree(G[8])
60
julia> leading_coefficient(G[8])
83369589588385815165248207597941242098312973356252482872580035860533111990678631297423089011608753348453253671406641805924218003925165995322989635503951507226650115539638517111445927746874479234Gröbner Walk Algorithms
The Hilbert driven Buchberger Algorithm
Calling the functions standard_basis and groebner_basis with algorithm = :hilbert in OSCAR triggers a version of the Hilbert driven Gröbner basis algorithm which proceeds along the following lines.
Given an ideal $I$ of a multivariate polynomial ring $R$ over a field $K$ and a slow
destination_ordering, check whether $I$ is homogeneous with respect to the standard $\mathbb Z$-grading on $R$. If so, setstart_orderingtodegrevlexand go to step 3.Check whether there exists a $\mathbb Z$-grading on $R$ with positive weights such that $I$ is homogeneous with respect to this grading. If so, let
start_orderingbe the corresponding weight ordering. If not, go to step 5.Compute a Gröbner basis of $I$ with respect to
start_orderingand use this Gröbner basis to compute the Hilbert function of $R/I$.Compute a Gröbner basis with respect to
destination_ordering, proceeding by increasing (weighted) degree, and skipping all further Buchberger tests in a given (weighted) degree as soon as the leading terms found so far account for the Hilbert function in that (weighted) degree. Return the computed Gröbner basis.Extend $R$ to a polynomial ring $S$ by appending an extra variable, equip $S$ with the standard $\mathbb Z$-grading, and let $I^{h}\subset S$ be the homogenization of $I$ with respect to the extra variable. Compute a Gröbner basis of $I$ with respect to
degrevlexonR, and homogenize its elements to obtain a Gröbner basis of $I^{h}$ with respect todegrevlexon $S$. Use the latter basis to compute the Hilbert function of $S/I^{h}$. Extenddestination_orderingto a block ordering onS. Following the recipe in step 4, compute a Gröbner basis of $S/I^{h}$ with respect to the extended ordering. Return the dehomogenization of this basis with respect to the extra variable.
If the characteristic of $K$ is zero, by semi-continuity of the Hilbert function, it is sufficient to perform step 3 for the reduction of $I$ modulo a conveniently chosen prime number rather than for $I$ itself.
If appropriate weights and/or the Hilbert function with respect to appropriate weights are already known to the user, this information can be entered when calling the Hilbert driven Gröbner basis algorithm as follows:
groebner_basis_hilbert_driven — Methodgroebner_basis_hilbert_driven(I::MPolyIdeal{P}; destination_ordering::MonomialOrdering,
complete_reduction::Bool = false,
weights::Vector{Int} = ones(Int, ngens(base_ring(I))),
hilbert_numerator::Union{Nothing, ZZPolyRingElem} = nothing)
where {P <: MPolyRingElem}Return a Gröbner basis of I with respect to destination_ordering.
The function implements a version of the Hilbert driven Gröbner basis algorithm. See the corresponding section of the OSCAR documentation for some details.
All weights must be positive. If no weight vector is entered by the user, all weights are set to 1. An error is thrown if the generators of I are not homogeneous with respect to the corresponding (weighted) degree.
If $R$ denotes the parent ring of $I$, and $p, q\in\mathbb Z[t]$ are polynomials such that $p/q$ represents the Hilbert series of $R/I$ as a rational function with denominator $q = (1-t^{w_1})\cdots (1-t^{w_n}),$ where $n$ is the number of variables of $R$, and $w_1, \dots, w_n$ are the assigned weights, then hilbert_numerator is meant to be $p$. If this numerator is not entered by the user, it will be computed internally.
Examples
julia> R, (a, b, c, d, e, f, g) = polynomial_ring(QQ, ["a", "b", "c", "d", "e", "f", "g"]);
julia> V = [-3*a^2+2*f*b+3*f*d, (3*g*b+3*g*e)*a-3*f*c*b,
-3*g^2*a^2-c*b^2*a-g^2*f*e-g^4, e*a-f*b-d*c];
julia> I = ideal(R, V);
julia> o = degrevlex([a, b, c])*degrevlex([d, e, f, g]);
julia> G = groebner_basis_hilbert_driven(I, destination_ordering = o);
julia> length(G)
296
julia> total_degree(G[49])
30julia> R, (x, y, z) = polynomial_ring(GF(32003), ["x", "y", "z"]);
julia> f1 = x^2*y+169*y^21+151*x*y*z^10;
julia> f2 = 6*x^2*y^4+x*z^14+3*z^24;
julia> f3 = 11*x^3+5*x*y^10*z^10+2*y^20*z^10+y^10*z^20;
julia> I = ideal(R, [f1, f2,f3]);
julia> W = [10, 1, 1];
julia> GB = groebner_basis_hilbert_driven(I, destination_ordering = lex(R), weights = W);
julia> length(GB)
40julia> R, (x, y, z) = polynomial_ring(GF(32003), ["x", "y", "z"]);
julia> f1 = x^2*y+169*y^21+151*x*y*z^10;
julia> f2 = 6*x^2*y^4+x*z^14+3*z^24;
julia> f3 = 11*x^3+5*x*y^10*z^10+2*y^20*z^10+y^10*z^20;
julia> I = ideal(R, [f1, f2,f3]);
julia> W = [10, 1, 1];
julia> S, t = polynomial_ring(ZZ, "t")
(Univariate polynomial ring in t over ZZ, t)
julia> hn = -t^75 + t^54 + t^51 + t^45 - t^30 - t^24 - t^21 + 1
-t^75 + t^54 + t^51 + t^45 - t^30 - t^24 - t^21 + 1
julia> GB = groebner_basis_hilbert_driven(I, destination_ordering = lex(R), weights = W, hilbert_numerator = hn);
julia> length(GB)
40Faugère's F4 Algorithm
With many adjustable keyword arguments, the following function provides low-level implementations of various versions of the Gröbner basis algorithm. Use these functions only if you know what you are doing.
groebner_basis_f4 — Methodgroebner_basis_f4(I::MPolyIdeal, <keyword arguments>)Compute a Gröbner basis of I with respect to degrevlex using Faugère's F4 algorithm. See [Fau99] for more information.
At current state only prime fields of characteristic 0 < p < 2^{31} are supported.
Possible keyword arguments
initial_hts::Int=17: initial hash table sizelog_2.nr_thrds::Int=1: number of threads for parallel linear algebra.max_nr_pairs::Int=0: maximal number of pairs per matrix, only bounded by minimal degree if0.la_option::Int=2: linear algebra option: exact sparse-dense (1), exact sparse (2, default), probabilistic sparse-dense (42), probabilistic sparse(44).eliminate::Int=0: size of first block of variables to be eliminated.complete_reduction::Bool=true: compute a reduced Gröbner basis forIinfo_level::Int=0: info level printout: off (0, default), summary (1), detailed (2).
Examples
julia> R,(x,y,z) = polynomial_ring(GF(101), ["x","y","z"])
(Multivariate polynomial ring in 3 variables over GF(101), FqMPolyRingElem[x, y, z])
julia> I = ideal(R, [x+2*y+2*z-1, x^2+2*y^2+2*z^2-x, 2*x*y+2*y*z-y])
Ideal generated by
x + 2*y + 2*z + 100
x^2 + 100*x + 2*y^2 + 2*z^2
2*x*y + 2*y*z + 100*y
julia> groebner_basis_f4(I)
Gröbner basis with elements
1 -> x + 2*y + 2*z + 100
2 -> y*z + 82*z^2 + 10*y + 40*z
3 -> y^2 + 60*z^2 + 20*y + 81*z
4 -> z^3 + 28*z^2 + 64*y + 13*z
with respect to the ordering
degrevlex([x, y, z])Leading Ideals
leading_ideal — Methodleading_ideal(G::Vector{T}; ordering::MonomialOrdering = default_ordering(parent(G[1])))
where T <: MPolyRingElemReturn the leading ideal of G with respect to ordering.
Examples
julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> L = leading_ideal([x*y^2-3*x, x^3-14*y^5], ordering=degrevlex(R))
Ideal generated by
x*y^2
y^5
julia> L = leading_ideal([x*y^2-3*x, x^3-14*y^5], ordering=lex(R))
Ideal generated by
x*y^2
x^3leading_ideal — Methodleading_ideal(I::MPolyIdeal; ordering::MonomialOrdering = default_ordering(base_ring(I)))Return the leading ideal of I with respect to ordering.
Examples
julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> I = ideal(R,[x*y^2-3*x, x^3-14*y^5])
Ideal generated by
x*y^2 - 3*x
x^3 - 14*y^5
julia> L = leading_ideal(I, ordering=degrevlex(R))
Ideal generated by
x*y^2
x^4
y^5
julia> L = leading_ideal(I, ordering=lex(R))
Ideal generated by
y^7
x*y^2
x^3Normal Forms
Given a polynomial $g\in K[x]$, an ideal $I\subset K[x]$, and a global monomial ordering $>$ on the monomials in $x$, the fully reduced remainder $h$ in a standard expression on division by the elements of a Gröbner basis of $I$ with respect to $>$ is uniquely determined by $g$, $I$, and $>$ (and does not depend on the choice of Gröbner basis). We refer to such a remainder as the normal form of $g$ mod $I$, with respect to $>$.
normal_form — Methodnormal_form(g::T, I::MPolyIdeal;
ordering::MonomialOrdering = default_ordering(base_ring(I))) where T <: MPolyRingElemCompute the normal form of g mod I with respect to ordering.
normal_form(G::Vector{T}, I::MPolyIdeal;
ordering::MonomialOrdering = default_ordering(base_ring(I))) where T <: MPolyRingElemReturn a Vector which contains for each element g of G a normal form as above.
Examples
julia> R,(a,b,c) = polynomial_ring(QQ,["a","b","c"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[a, b, c])
julia> J = ideal(R,[-1+c+b,-1+b+c*a+2*a*b])
Ideal generated by
b + c - 1
2*a*b + a*c + b - 1
julia> gens(groebner_basis(J))
2-element Vector{QQMPolyRingElem}:
b + c - 1
a*c - 2*a + c
julia> normal_form(-1+c+b+a^3, J)
a^3
julia> R,(a,b,c) = polynomial_ring(QQ,["a","b","c"])
(Multivariate polynomial ring in 3 variables over QQ, QQMPolyRingElem[a, b, c])
julia> A = [-1+c+b+a^3,-1+b+c*a+2*a^3,5+c*b+c^2*a]
3-element Vector{QQMPolyRingElem}:
a^3 + b + c - 1
2*a^3 + a*c + b - 1
a*c^2 + b*c + 5
julia> J = ideal(R,[-1+c+b,-1+b+c*a+2*a*b])
Ideal generated by
b + c - 1
2*a*b + a*c + b - 1
julia> gens(groebner_basis(J))
2-element Vector{QQMPolyRingElem}:
b + c - 1
a*c - 2*a + c
julia> normal_form(A, J)
3-element Vector{QQMPolyRingElem}:
a^3
2*a^3 + 2*a - 2*c
4*a - 2*c^2 - c + 5Syzygies
We refer to the section on modules for more on syzygies.
syzygy_generators — Methodsyzygy_generators(G::Vector{<:MPolyRingElem})Return generators for the syzygies on the polynomials given as elements of G.
Examples
julia> R, (x, y) = polynomial_ring(QQ, ["x", "y"])
(Multivariate polynomial ring in 2 variables over QQ, QQMPolyRingElem[x, y])
julia> S = syzygy_generators([x^3+y+2,x*y^2-13*x^2,y-14])
3-element Vector{FreeModElem{QQMPolyRingElem}}:
(-y + 14)*e[2] + (-13*x^2 + x*y^2)*e[3]
(-169*y + 2366)*e[1] + (-13*x*y + 182*x - 196*y + 2744)*e[2] + (13*x^2*y^2 - 2548*x^2 + 196*x*y^2 + 169*y + 338)*e[3]
(-13*x^2 + 196*x)*e[1] + (-x^3 - 16)*e[2] + (x^4*y + 14*x^4 + 13*x^2 + 16*x*y + 28*x)*e[3]