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.

Note

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

Note

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)).

default_orderingMethod
default_ordering(R::MPolyRing)

Return the monomial ordering that is used for computations with ideals in R if no other ordering is specified – either directly by the user or by requirements of a specific algorithm.

source

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 R

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])

Expert users may temporarily choose a different default ordering for a given ring.

with_orderingFunction
with_ordering(f, R::MPolyRing, o::MonomialOrdering)

Use the monomial ordering o for computations in R during the execution of f. This may be used with do block syntax, see the example.

This functionality is meant for advanced users. In general it should not be necessary to explicitly set a monomial ordering. Further, there is no guarantee that o is actually used. For example, if an algorithm requires an elimination ordering, o might be ignored.

Example

julia> R, (x, y, z) = QQ[:x, :y, :z];

julia> f = x + y^2;

julia> I = ideal(R, [y^2 - z, x - z^2]);

julia> normal_form(f, I) # this uses degrevlex
x + z

julia> with_ordering(R, lex(R)) do
           # this uses lex
           normal_form(f, I)
       end
z^2 + z

Notice that in this small example we could have achieved the same by using the keyword argument ordering:

julia> normal_form(f, I, ordering = lex(R))
z^2 + z
source

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 + 1
julia> 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 R

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 = invlex(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 = invlex(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).

Note

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.

reduceMethod
reduce(g::T, F::Union{Vector{T}, IdealGens{T}};
       ordering::MonomialOrdering = default_ordering(g)), complete_reduction::Bool = false) where T <: MPolyRingElem

If 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 <: MPolyRingElem

Return a Vector which contains, for each element g of G, a remainder as above.

Note

The returned remainders are fully reduced if complete_reduction is set to true and ordering is global.

Note

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^5
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> 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^6
source
reduce_with_quotientsMethod
reduce_with_quotients(g::T, F::Union{Vector{T}, IdealGens{T}};
       ordering::MonomialOrdering = default_ordering(parent(g)), complete_reduction::Bool = false) where T <: MPolyRingElem

If 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 <: MPolyRingElem

Return a Vector which contains, for each element g of G, quotients and a remainder as above.

Note

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
true
source
reduce_with_quotients_and_unitMethod
reduce_with_quotients_and_unit(g::T, F::Union{Vector{T}, IdealGens{T}};
       ordering::MonomialOrdering = default_ordering(parent(g)), complete_reduction::Bool = false) where T <: MPolyRingElem

Return 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 <: MPolyRingElem

Return a Vector which contains, for each element g of G, a unit, quotients, and a remainder as above.

Note

The returned remainders are fully reduced if complete_reduction is set to true and ordering is global.

Note

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
true
source

Computing 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.

Note

Every standard basis of $I$ generates $I$.

Note

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$.

Note

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.

Note

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.

Note

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_basisMethod
groebner_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),
  • :modular (implementation of multi-modular approach, if applicable),
  • :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).
Note

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.

Note

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])
-91230304237130414552564280286681870842473427917231798336639893796481988733936505735341479640589040146625319419037353645834346047404145021391726185993823650399589880820226804328750
source
standard_basisMethod
standard_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),
  • :modular (implementation of multi-modular approach, if applicable),
  • :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).
Note

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.

Note

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])
source

Gröbner Bases with transformation matrix

groebner_basis_with_transformation_matrixMethod
groebner_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.

Note

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 3 elements w.r.t. degrevlex([x, y]), [1 0 -x^2-y; 0 1 y^2])

julia> gens(I)*T == gens(G)
true
source
standard_basis_with_transformation_matrixMethod
standard_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.

Note

The returned Gröbner basis is reduced if ordering is a global monomial ordering 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 1 element w.r.t. neglex([x, y]), [-1; 0])

julia> gens(I)*T == gens(G)
true
source

Grö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 fast start_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

fglmMethod
fglm(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.

Note

Both start_ordering and destination_ordering must be global and the base ring of I must be a polynomial ring over a field.

Note

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])
83369589588385815165248207597941242098312973356252482872580035860533111990678631297423089011608753348453253671406641805924218003925165995322989635503951507226650115539638517111445927746874479234
source

Grö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.

  1. 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, set start_ordering to degrevlex and go to step 3.

  2. 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_ordering be the corresponding weight ordering. If not, go to step 5.

  3. Compute a Gröbner basis of $I$ with respect to start_ordering and use this Gröbner basis to compute the Hilbert function of $R/I$.

  4. 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.

  5. 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 degrevlex on R, and homogenize its elements to obtain a Gröbner basis of $I^{h}$ with respect to degrevlex on $S$. Use the latter basis to compute the Hilbert function of $S/I^{h}$. Extend destination_ordering to a block ordering on S. 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.

Note

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_drivenMethod
groebner_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.

Note

The function implements a version of the Hilbert driven Gröbner basis algorithm. See the corresponding section of the OSCAR documentation for some details.

Note

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.

Note

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])
30
julia> 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)
40
julia> 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)
40
source

Faugère's F4 Algorithm

Expert function for computing Gröbner bases

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_f4Method
groebner_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.

Note

At current state only prime fields of characteristic 0 < p < 2^{31} and the rationals are supported.

Possible keyword arguments

  • initial_hts::Int=17: initial hash table size log_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 if 0.
  • 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 for I
  • normalize::Bool=true: normalizes elements in computed Gröbner basis for I
  • truncate_lifting::Int=0: degree up to which the elements of the Gröbner basis are lifted to QQ, 0 for complete lifting
  • info_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])
source

Leading Ideals

leading_idealMethod
leading_ideal(G::Vector{T}; ordering::MonomialOrdering = default_ordering(parent(G[1]))) 
                            where T <: MPolyRingElem

Return 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^3
source
leading_idealMethod
leading_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^3
source

Normal 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_formMethod
normal_form(g::T, I::MPolyIdeal; 
  ordering::MonomialOrdering = default_ordering(base_ring(I))) where T <: MPolyRingElem

Compute 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 <: MPolyRingElem

Return 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 + 5
source

Syzygies

We refer to the section on modules for more on syzygies.

syzygy_generatorsMethod
syzygy_generators(
    a::Vector{T};
    parent::Union{FreeMod{T}, Nothing} = nothing
  ) where {T<:RingElem}

Return generators for the syzygies on the polynomials given as elements of a. The optional keyword argument can be used to specify the parent of the output.

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]
source